0x01 Reason
Currently, during the product development process, there is a need to detect the types of application layer protocols. To build an efficient rule matching engine, I revisited Snort’s rule engine. The main purpose is to broaden the design ideas and learn from some methods.
0x02 Rule Formulation
Good rule design is the foundation for future rule configuration and expansion. Snort uses the data structures RuleTreeNodes (RTN) and OptTreeNodes (OTN) to store rule data, forming a two-dimensional linked list structure. For the data structures used by Snort, refer to the source code data packet rules.h file. RTNs form a horizontal linked list, and each RTN node is associated with multiple OTNs forming a vertical linked list, thereby constituting a rule tree where each OTN node corresponds to a rule. The rule logic diagram is shown below. One RTN corresponds to several OTNs, which is a characteristic of Snort’s rule library organization. If N rules for detecting X attack activities are defined in one rule file, and they have the same source/destination IP (Src/Des IP) and port number (Src/Des Port), to speed up detection, these N detection rules share one chain header, which records the source/destination IP and port number, while each rule’s detection features are saved in different chain option structures. This way, only one RTN check is needed during rule detection. Excerpt: Research and Improvement of Snort Rule Library_Wang Zhe.pdf 
0x03 Rule Construction
To generate the rule tree, if Snort runs in network intrusion detection mode, it must first parse the rule file (snort.conf) and establish the rule library before detecting network packets. When organizing the rule library, it first classifies by rule type (rule actions: Alert, Pass, Log, Activation, Dynamic) and then divides them into corresponding linked lists by protocol type (Ip/Tcp/Icmp/Uolp). All rules are allocated to these linked lists. Through source code analysis, the main functions used in this process are ParseRulesFile(), ParseRule(), ProcessHeadNode(), and ParseRuleOptions(). ParseRule() handles individual rules. It decomposes the rule statements, extracts the rule type, and if it is alert, pass, log, active, or dynamic, it uses ProcessHeadNode() and ParseRuleOptions() to add the corresponding chain header and chain options by protocol, forming the rule tree. For other rule types like preprocess and output, corresponding functions are called for preprocessing or output plugin parsing. Excerpt: Analysis of Snort Rules and Rule Processing Module.pdf
0x04 Rule Optimization
In Snort’s intrusion detection mode, rule-based pattern matching is the core mechanism of its detection. The intrusion detection process is divided into two main steps: the first step is the rule parsing process, which includes reading rules from the rule file and organizing rules in memory; the second step is using these rules for matching. To improve the speed of rule matching, Snort employs the Boyer-Moore string matching algorithm, two-dimensional list recursive retrieval (RTN and OTN), and function pointer lists. While maintaining these methods, this article attempts to dynamically adjust the order of rule matching to improve packet matching efficiency, thereby enhancing Snort’s overall performance.
0x05 Rule Matching
Using the efficient AC matching algorithm; For cross-packet detection, combining multiple packets of a stream into one large packet is not supported;
0x06 Conclusion
1. The construction of the rule engine requires the completion of the above steps; good rule design can facilitate the addition of rules for future vulnerability exposure; 2. Efficient data structure organization for rules; 3. How to optimize the rule matching algorithm; 4. Detection for cross-packet scenarios;