Characterization and Solution to a Stateful IDS Evasion

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.