Method for compressing matching automata through common prefixes in regular expressions
The present disclosure provides a means for compressing Non-deterministic Finite Automata (NFA) for faster matching during Deep Packet Inspection (DPI) when a Network Intrusion Detection System (NIDS) is evaluating traffic to find suspicious network traffic. The present disclosure accomplishes this through four primary components. First, it provides a time-efficient method for accurately comparing two regular expressions so that common prefixes can be identified. Second, it provides a time-efficient method for grouping regular expressions by their common prefixes. Third, it provides a method for subgrouping within groups by longest common prefixes in order to maximize compression. Finally, it provides a method for building a compressed NFA using heuristics derived from the length of the common prefix to a subgroup.
1. A method for compressing matching automata through common prefixes in regular expressions, comprising:
converting a set of regular expressions into transition sequences in such a way that it allows side-by-side comparison of two regular expressions in linear time;
grouping the set of regular expressions into groups based on a predetermined prefix length which is a minimum shared prefix length;
subgrouping the groups into subgroups containing longest common prefixes;
merging the set of regular expressions in the subgroups into a subgroup Non-deterministic Finite Automata (NFA), and then the subgroup NFA into a group NFA and then the group NFA into a final, prefix-minimal NFA comprised of;
merging all regular expressions in a subgroup through a merging of final states of prefix NFA to the start states of remainder NFA, with singleton subgroups being converted directly to NFA;
iteratively merging the subgroups together by longest common prefix until only a single subgroup remains, the single subgroup being the group NFA;
iteratively decrementing the minimum shared prefix length and re-assigning groups to indices within a temporary group map and then merging all the group NFA that share a shorter prefix length; and
creating a start state for the prefix-minimal NFA and adding transitions from the start state to all remaining groups once the minimum shared prefix length reaches zero.
2. The method of claim 1 , wherein the converting a set of regular expressions into transition sequences comprises:
creating parse trees of the set of regular expressions utilizing a readily available library;
recursively converting branches into the transition sequences; and
adding all transition sequence branches to a parent transition sequence.
3. The method of claim 1 , wherein the grouping the set of regular expressions into groups based on a predetermined prefix length comprises:
creating an index from a first predetermined prefix length of transitions in the transition sequences;
adding the set of regular expressions and the transition sequences to the group at the index in a group map; and
creating an entry at the index if no such entry previously existed.
4. The method of claim 1 , wherein the subgrouping the groups into subgroups containing longest common prefixes comprises:
comparing the regular expressions in a group to all other regular expressions in current subgroups; and
adding each regular expression that matches the longest common prefix of a subgroup to the subgroup in such a way that all regular expressions that share the longest common prefix are in the subgroup, or to a singleton subgroup if the regular expression does not have the longest common prefix match for any subgroup.
5. A method in a Network Intrusion Detection System for filtering incoming traffic, comprising:
obtaining a rule set for the filtering of the incoming traffic, the rule set comprising a set of regular expressions;
converting the set of regular expressions into transition sequences in such a way that it allows side-by-side comparison of two regular expressions in linear time;
grouping the set of regular expressions into groups based on a predetermined prefix length which is a minimum shared prefix length;
subgrouping the groups into subgroups containing longest common prefixes;
merging the set of regular expressions in the subgroups into a subgroup Non-deterministic Finite Automata (NFA), and then the subgroup NFA into a group NFA and then the group NFA into a final, prefix-minimal NFA, comprised of;
merging all regular expressions in a subgroup through a merging of final states of prefix NFA to the start states of remainder NFA, with singleton subgroups being converted directly to NFA;
iteratively merging the subgroups together by longest common prefix until only a single subgroup remains, the single subgroup being the group NFA;
iteratively decrementing the minimum shared prefix length and re-assigning groups to indices within a temporary group map and then merging all the group NFA that share a shorter prefix length; and
creating a start state for the prefix-minimal NFA and adding transitions from the start state to all remaining groups once the minimum shared prefix length reaches zero; and
filtering the incoming traffic using the final, prefix minimal NFA to identify suspicious portions of the incoming traffic for further processing.
6. The method of claim 5 , wherein the converting a set of regular expressions into transition sequences comprises:
creating parse trees of the set of regular expressions utilizing a readily available library;
recursively converting branches into the transition sequences; and
adding all transition sequence branches to a parent transition sequence.
7. The method of claim 5 , wherein the grouping the set of regular expressions into groups based on a predetermined prefix length comprises:
creating an index from a first predetermined prefix length of transitions in the transition sequences;
adding the set of regular expressions and the transition sequences to the group at the index in a group map; and
creating an entry at the index if no such entry previously existed.
8. The method of claim 5 , wherein the subgrouping the groups into subgroups containing longest common prefixes comprises:
comparing the regular expressions in a group to all other regular expressions in current subgroups; and
adding each regular expression that matches the longest common prefix of a subgroup to the subgroup in such a way that all regular expressions that share the longest common prefix are in the subgroup, or to a singleton subgroup if the regular expression does not have the longest common prefix match for any subgroup.