Suricata

Flowbits is a powerful and useful feature of Suricata and multiple flowbits rules can be applied to the same packet/stream. Unfortunately, there appears to be situations where flowbits rules are processed in an order that prevents them from alerting as expected.

Obviously, rules that set flowbits ("flowbit settters") have to be processed before rules that check flowbits ("flowbit checkers"). However, flowbits rules can both set and check flowbits and flowbits "chains" can exist and these rules must be evauated in a certain order based on the flowbits dependencies. Such dependencies do not appear to be respected in all cases by the Suricata engine when processing rules.

From what I can tell, when it comes to flowbits rules, rules that are only flowbit setters get processed first and rules that are only flowbit checkers get processed last. This makes sense and is appropriate. However, rules that both check and set flowbits seem to be proccessed in order based off of SID and this can create dependency issues for flowbits chains. (Note: this is based off my testing on version 2.0.6; older versions of Suricata like version 1.3.4 appear to base the processing order off of the order that the rules appear in the rules file.)

For example, consider the attached pcap. If it is run against the following ruleset that contains a simple flowbits chain, SIDs 1, 2, and 3 fire as expected:

alert tcp any any -> any any (msg:"First in chain"; content:"GET"; flowbits:set,1; sid:1;)
alert tcp any any -> any any (msg:"Second in chain"; content:"flow"; flowbits:isset,1; flowbits:set,2; sid:2;)
alert tcp any any -> any any (msg:"Third (Last) in chain"; content:"boss"; flowbits:isset,2; flowbits:set,3; sid:3;)

However, if you change the SIDs in the chain like this, then only SIDs 2 and 3 fire:

alert tcp any any -> any any (msg:"First in chain"; content:"GET"; flowbits:set,1; sid:3;)
alert tcp any any -> any any (msg:"Second in chain"; content:"flow"; flowbits:isset,1; flowbits:set,2; sid:2;)
alert tcp any any -> any any (msg:"Third (Last) in chain"; content:"boss"; flowbits:isset,2; flowbits:set,3; sid:1;)

The solution is, when there is a chain of flowbits, the rules need to be processed appropriately so that all necessary setters are processed before all dependent checkers. This may seem like a non-trivial task since complex dependent chains can be exist because rules can set and check more than one flowbit. Fortunately, there is a simple solution (at least in theory).

Flowbits rules can be represented as a directed acyclic graph (DAG) so the solution is nothing more than doing a topologial sort of them in order to determine appropriate processing order. (http://en.wikipedia.org/wiki/Topological_sorting)

If you view each rule as a node, and a directed edge exists from node A to node B if node A sets a flowbit checked by node B, then we end up with a DAG (unless there are loops in which case the graph wouldn't be acyclic and there would be a logical error in the ruleset preventing rules from alerting as expected; flowbits rules should always be able to be represented as a DAG).

In addition to determining rule processing order for flowbits rules, creating a graph of the rules provides other benefits:

1) Flowbits cycles (loops) can be detected and an error message can be thrown.
2) Rules that set flowbits that are never checked can be trivially identified and warning messages can be thrown.