The support of stateful signatures is an important feature of signature-based Network Intrusion Detection Systems (NIDSs) which permits the detection of multi-stage attacks. However, due to the difficulty to completely simulate every application protocol, several NIDS evasion techniques exploit this Achilles' heel, making the NIDS and its protected system see and explain a packet sequence differently. In this paper, we propose an evasion technique to the Snort NIDS which exploits its flowbits feature. We specify the flowbit evasion attack and provide practical algorithms to solve it with controllable false positives and formally prove their correctness and completeness. We implemented a tool called SFET which can automatically parse a Snort rule set, generate all possible sequences that can evade it, as well as produce a patch to guard the rule set against those evasions. Although Snort was used for illustration, both the evasion attack and the solution to it are applicable to any stateful signature-based NIDS.

We identify a new type of stateful IDS evasion, named signature evasion. We formalize the signature evasion on those Stateful IDSs whose state can be modeled using Deterministic Finite State Automata (DFAs). We develop an efficient algorithm which operates on rule set DFAs and derives a minimal rectification of evasive paths. Finally, we evaluate our solution on Snort signatures, identify and rectify existing vulnerable flowbit rule sets.

A major threat to data networks is based on the fact that some traffic can be expensive to classify and filter as it will undergo a longer than average list of filtering rules before being rejected by the default deny rule. An attacker with some information about the access-control list (ACL) deployed at a firewall or an intrusion detection and prevention system (IDS/IPS) can craft packets that will have maximum cost. In this paper, we present a technique that is light weight, traffic-adaptive and can be deployed on top of any filtering mechanism to pre-filter unwanted expensive traffic. The technique utilizes Internet traffic characteristics coupled with a special carefully tuned representation of the policy to generate early defense policies. We use Boolean expressions built as binary decision diagrams (BDD) to represent relaxed versions of the policy that are faster to evaluate. Moreover, it is guaranteed that the technique will not add an overhead that will not be compensated by the gain in filtering time in the underlying filtering method. Evaluation has shown considerable savings to the overall filtering process, thus saving the firewall processing power and increasing overall throughput. Also, the overhead changes according to the traffic behavior, and can be tuned to guarantee its worst case time cost.