Optimize ruleset into a tree

[markuskont]

This is a research issue for major development.

Initial research into this project went entirely into building individual rules themselves and making matching work. Ruleset as a whole was a afterthought and is still implemented as a simple linear list. That means that while individual rules are pretty fast, ruleset as a whole can still take a significant time to process as every event has to be evaluated against every rule.

This can also mean a lot of redundant and slow lookups, as rule might invoke a slow regexp match only to get a negative response from a missing key later. Yet other rules might also get negative matches from missing event keys, making the text matches especially useless.

Idea would be to organize ruleset into a tree (or possibly a skiplist) where branches follow the selection JSON keys. That way each Event could in theory only follow a branch of keys that actually exist in the message, and potentially skip over a lot of redundant and even expensive rule evaluations.

[mjnovice]

Hi @markuskont I would be happy to help on this as I am thinking of contributing to some open source project, as it has been a while.

From what I can infer, we want an intelligent way to do the following

func (r Ruleset) EvalAll(e Event) (Results, bool) {
    results := make(Results, 0)
    for _, rule := range r.Rules {
        if res, match := rule.Eval(e); match {
            results = append(results, *res)
        }
    }
    if len(results) > 0 {
        return results, true
    }
    return nil, false
}

Idea would be to organize ruleset into a tree (or possibly a skiplist) where branches follow the selection JSON keys For the above could you pass a documentation from Sigma for how we branch based on the selection key ?

[markuskont]

Hi @mjnovice

Yep, that's exactly what I had in mind. Thanks a lot!