Suricata

This turned out to be more than just choosing and applying a correct sorting order. Isolating this problem was not a good idea.

I think I am more confident now that this is actually indeed a boolean satisfiability problem. These class of problems are unsolvable in polynomial time for more than 2 conditions. A demo for 2-SAT problem is given here: https://www.geeksforgeeks.org/2-satisfiability-2-sat-problem/

Note that we can always run into "unsatisfiable" data paths. For example, the engine accepts the following complex flowbit chains but there's no way to determine the correct order for these as there isn't one:

alert http any any -> any any (http.user_agent; content:"Mozilla"; flowbits:isset, headtest; flowbits:set,moz; sid:10;)
alert http any any -> any any (http.method; content:"GET"; flowbits:set,headtest; flowbits:isset,moz; sid:12;)

So, what we can do is:
1. Apply some restrictions to reduce the number of checks. e.g. cyclic dependencies like in the above mentioned example must be disallowed resulting in errors/commenting of all rules involved.
2. Create a cycle free many to many relationship internal table. i.e. b/w signatures and flowbits.

I'm currently working on listing out the possible restrictions that could/should be applied and what should the relationship table look like.

I think it makes sense to start with banning cyclical dependencies, as they can't be satisfied at runtime anyway. Perhaps we should create subtickets for the distinct steps.

In Review PR: https://github.com/OISF/suricata/pull/15076

TBH, still in the state of "can it be solved for all possible cases?" and it's not looking bright. More info TBD on the PR.