Signature-Based Intrusion Detection Systems

Hello! Welcome to the next lesson in our course on architecting security products.

In our previous lesson, we designed a modular inspection pipeline, the chassis for our WAF's security logic. We established that this pipeline would host various inspection modules, each performing a specific security check.

Today, we will design one of the most critical of those modules: the signature-based detection engine. This lesson directly addresses the learning outcome: Architect a signature-based detection engine, including rule storage strategies and string matching algorithm selection (e.g., Aho-Corasick). We'll dive into how a WAF can efficiently find thousands of known attack patterns in web traffic at line rate.

1. The Core Problem: High-Speed Multi-Pattern Matching

A signature-based engine works like an antivirus scanner for web traffic. It maintains a large set of "signatures"—strings or patterns that correspond to known attacks. These can be simple strings like ../../etc/passwd or more complex patterns found in SQL injection attacks, such as ' OR '1'='1.

A production WAF, like one using the OWASP Core Rule Set, may need to check every incoming request against thousands or even tens of thousands of these signatures. The challenge is to do this with minimal latency.

Let's consider the scale:

• Request Volume: A busy web server might handle thousands of requests per second.
• Signature Set Size: 10,000+ signatures.
• Inspection Surface: Each signature must be checked against multiple parts of the request (URL, every header, the entire body).

A naive approach, such as iterating through each signature and scanning the request for it, would lead to (number of signatures) * (request size) work for each request. This is computationally explosive and would never keep up with real-world traffic. The table in the resource "Pattern Matching Algorithms | Survey of Software" under "Practical Performance (English Text)" illustrates this clearly: running a fast single-pattern search 10,000 times is orders of magnitude slower than a proper multi-pattern approach.

This frames our central architectural challenge: we need an algorithm and a data structure that can find any of a large set of patterns within a stream of data in a single pass.

2. The Right Tool for the Job: The Aho-Corasick Algorithm

The classic and industry-standard solution to the multi-pattern matching problem is the Aho-Corasick algorithm. Its core insight, which will appeal to your first-principles mindset, is to preprocess the patterns, not the text. It combines all signatures into a single, powerful finite automaton. This allows you to process the input text (the request data) exactly once, finding all matches as you go.

To understand how to architect our engine, we first need to understand the mechanics of Aho-Corasick.

The video gives you the conceptual framework. Now, let's dive deeper into the algorithm's construction. This understanding is essential for making informed design decisions about rule storage and performance.

Let's consolidate this with a detailed textual resource that you can refer back to.

3. Architecting the Signature Engine Component

Now that we have a firm grasp of the Aho-Corasick algorithm, let's design our WAF module around it. The architecture splits naturally into two phases: an offline compilation phase and an online matching phase.

Phase 1: Rule Compilation (Offline)

This phase happens when the WAF starts up or when its rules are updated. It takes the human-readable rule set (e.g., from a file) and prepares it for high-speed matching.

1. Rule Parsing: WAF rules contain more than just a string to match. They include a rule ID, severity, action (block, log), and the part of the request to inspect (e.g., ARGS, REQUEST_HEADERS:User-Agent). The first step is to parse these rules into structured objects.
2. Pattern Extraction: From the parsed rules, extract all the string patterns that need to be matched.
3. Automaton Construction:
   • Build a Trie from all extracted patterns.
   • As you add each pattern, store the corresponding Rule ID (or a list of IDs, if a pattern is used in multiple rules) in the terminal node. This is the rule storage strategy: the automaton itself becomes the primary storage.
   • Traverse the Trie (using BFS, as explained in the resources) to compute the failure links for every node.
   • Compute output links to handle cases where one match is a suffix of another (e.g., finding "he" when "she" matches). A node's output should point to all rule IDs that end at that state, plus all rule IDs reachable by following its failure link chain.

The final output of this phase is a single, compact, and highly optimized Aho-Corasick automaton object in memory.

Phase 2: Request Inspection (Online)

This is the code that runs for every single request, implementing the Inspector interface we discussed in the last lesson.

1. Data Extraction: Based on the rules, the engine knows which parts of the request need inspection. It iterates through the StructuredRequest object and extracts the data to be scanned (e.g., the value of the q parameter, the Cookie header).
2. Matching: The extracted data string is streamed, character by character, through the pre-compiled Aho-Corasick automaton.
   • The engine maintains a pointer to its currentNode in the automaton, starting at the root.
   • For each character, it tries to follow a child edge.
   • If there's no matching child edge, it follows the failureLink repeatedly until a match is found or it reaches the root. Then it continues with the character. This process is $O(1)$ amortized time per character.
3. Reporting Findings: Whenever the currentNode is a terminal node (or has a non-empty output link chain), a match is found! The engine collects the Rule ID(s) associated with that node.
4. Result Aggregation: The engine looks up the full metadata for the triggered rule IDs (e.g., severity, block action). It then aggregates these findings into an InspectionResult object (e.g., a cumulative risk score or an immediate BLOCK action) to be returned to the main pipeline controller.

4. Advanced Architecture: Learning from Hyperscan

Aho-Corasick is the correct theoretical model. For enterprise-grade performance, especially in network security appliances, specialized implementations are used. Intel's Hyperscan is the de facto industry standard, used in products like Snort, Suricata, and many commercial WAFs.

Understanding Hyperscan's architectural principles shows us the path from a good algorithm to a world-class security product.

Key Architectural Lessons from Hyperscan:

• Holistic Optimization: Hyperscan doesn't just implement Aho-Corasick; it co-designs the algorithm with modern CPU architecture in mind, using SIMD to break the one-character-at-a-time limitation.
• Intelligent Preprocessing: The concept of "regex decomposition" is powerful. Instead of treating a complex regex as a monolithic blob, it finds the most effective string literals to anchor the search, making the process far more efficient. This is a sophisticated rule storage strategy where the "rule" is transformed into an optimal set of sub-components.
• Hybrid Approach: It combines multiple techniques. It uses fast string matching to find candidates and then triggers smaller, more specific FA matching, a much more efficient model than a simple pre-filter.

Conclusion

In this lesson, we have architected the core of a WAF's detection capability: the signature engine. We went from identifying the multi-pattern matching problem to selecting the right theoretical tool, Aho-Corasick, and designing a system around it.

Key Takeaways:

• Problem/Solution Fit: The WAF signature problem is a multi-pattern matching problem, for which Aho-Corasick is the optimal algorithmic solution due to its $O(n+m+z)$ time complexity.
• Architecture: The engine is split into an offline compilation phase (parsing rules, building the automaton) and an online matching phase (streaming request data through the automaton).
• Rule Storage Strategy: The Aho-Corasick trie itself serves as the primary storage mechanism, mapping patterns to rule IDs. Efficient storage depends on choices like dense vs. sparse representations of trie nodes to balance speed and memory, especially for large alphabets like Unicode.
• State of the Art: Advanced implementations like Hyperscan achieve massive performance gains through hardware-aware techniques like SIMD acceleration and sophisticated preprocessing like regex decomposition.

Preview of Next Lesson:

Our signature engine is fast, but in a high-throughput environment, every nanosecond counts. The next lesson will focus on: Design performance optimization strategies for a signature engine, such as caching, rule compilation, and hardware acceleration. We've touched on compilation and hardware acceleration today; next time, we'll explore them and caching strategies in greater detail to make our engine even faster.