The Sibuna Book 1.0.0-beta.3 documentation
Language: English
English简体中文한국어日本語EspañolDeutschहिन्दीالعربية
On this page

Part VI: Automata, Tries, and the Semantic Firewall

We examine the algorithms behind sub-microsecond classification: the tagged Aho-Corasick automaton, the IPv4/IPv6 radix trie, the byte-class tokenizers of the semantic WAF, and the declarative policy engine with WEIGH scoring.

Single-Pass Multi-Pattern Matching

Aho-Corasick as a Dense DFA

Sibuna has two literal-pattern sets: about forty bot signatures and about a hundred attack signatures. Scanning a field against \(N\) patterns one at a time is \(O(NM)\); the automaton of Aho and Corasick (1975) scans it once in \(O(M)\) after building a trie with failure links. Sibuna folds the failure links into the transition table at build time, so scanning is one table load per input byte with no branches on the pattern set. The automaton lives in the sibuna-patterns crate:

/// Advances from `state` (a row offset) over `byte`.
fn step(&self, state: usize, byte: u8) -> usize {
    self.table[state + usize::from(self.classes[usize::from(byte)])] as usize
}

pub fn find_first(&self, haystack: &[u8]) -> Option<Match> {
    let mut state = 0;
    for (index, &byte) in haystack.iter().enumerate() {
        state = self.step(state, byte);
        if state >= self.first_match {
            let id = self.first_output_in(self.match_state(state), self.all_tags)?;
            return Some(self.report(id, index + 1));
        }
    }
    None
}

A state is stored as its row offset in one flat table, so a step is one add and one load. States are numbered so that every match state comes after every other state; detecting a match is then one comparison against first_match, with no second table to load in the inner loop.

A trie from the root through G and GP to the GPTBot match state, and through C and Cl to the ClaudeBot match state; dashed failure edges lead from GP and Cl back to the root.
Fig. 9 Trie states and failure edges for two signatures

The automaton’s state budget is a run-time option. The policy engine reserves at most one root plus the sum of all signature lengths, a safe upper bound on trie states. This avoids historically oversized fixed tables while retaining a dense transition for every byte class. Each pattern carries a small category tag (0 to 63, so a set of tags is one 64-bit word). Case folding uses a 256-entry byte-class table built with the automaton: both cases of a letter share a class, and bytes that occur in no pattern share one class, so a table row is as wide as the number of distinct pattern bytes plus one rather than 256. Exact engine sizes and the comparison with sequential substring search are recorded in Part VIII. The latter uses the same patterns and any-match semantics.

Regular Expressions, SIMD Engines, and the Choice

Three families were weighed for the signature stage:

  • Backtracking regular expressions (a backtracking rule-set style) run hundreds of patterns per request and allocate per match; they are the slowest option and the most prone to false positives.
  • SIMD literal engines (Hyperscan, Vectorscan) prefilter blocks of 16 to 32 bytes with shuffle-based nibble masks (the “Teddy” algorithm) and verify candidates with automata. They excel on long inputs with large literal sets. The cost is a multi-megabyte C++ dependency, a compile-time pattern database, no WebAssembly target, and, for inputs of a hundred bytes, no advantage: the whole field scans in less time than one cache miss.
  • Dense Aho-Corasick plus small structural tokenizers, the libinjection lineage, gives exact linear-time behaviour in a fixed table and needs nothing outside the binary.

Sibuna’s fields are short, so the third family wins on both memory and speed; Part VIII records about 1.56 ns per byte on an 8 KiB body (the semantic scan takes 12,784.3 ns, 8kb_body_semantic_scan in benchmarks/results/primitives-latest.md). That is the one workload where a SIMD prefilter would pay, and SID 0006 keeps it as an open item.

The Radix Trie for IPv4 and IPv6

One binary trie over 128-bit keys serves both families: IPv6 prefixes are inserted as-is, IPv4 prefixes are mapped into ::ffff:0:0/96 so a /24 becomes a depth-120 path. Nodes live in one flat Vec indexed by u32 with index zero as both root and “no child”, so a lookup is at most 128 dependent loads with no pointer chasing. The trie is the PrefixTrie of the sibuna-cidr crate.

Walking the 96 mapped-prefix levels for every IPv4 lookup would cost 96 dependent loads before it reached the first bit of the IPv4 address. So the trie records the node at depth 96 at initialisation and starts IPv4 lookups there:

let (mut node, mut depth, mut best) = if is_ipv4_mapped(key) {
    let start = self.ipv4_root;
    let value = self.nodes[start as usize].value.as_ref();
    (start, IPV4_DEPTH, value.or(self.nodes[0].value.as_ref()))
} else {
    (0, 0, self.nodes[0].value.as_ref())
};

Classifying an IPv4 address costs 32.0 ns and an IPv6 address 79.3 ns (ipv4_cidr_classification and ipv6_cidr_classification in benchmarks/results/primitives-latest.md). The engine consults the trie twice: terminal allow/deny verdicts before the rule table, so a cluster-wide ban beats every rule, and challenge verdicts after it.

The Semantic Firewall

A Lesson in False Positives

The first version of the WAF matched a flat substring list against every header. The list contained /*, and every browser sends Accept: text/html,...,*/*;q=0.8. Every real browser was classified as SQL injection and received 403. The lesson shaped the design: a detector may fire only on structure, and the test suite now passes a complete Chrome request, including a comment body containing select, --, and an apostrophe, through the engine and asserts it comes out clean.

Byte Classes in One Pass

Each inspected field is scanned once to collect which byte classes occur: quotes, =, <, shell separators, %, NUL, canonicalisation triggers, and double spaces. Every detector consults the classes instead of rescanning, and the canonicalised second pass runs only when a trigger was seen. The scan is a 256-entry table lookup per byte, from the WAF module of sibuna-policy. Four accumulators keep the OR chains short, and the two byte pairs (/* and two adjacent spaces) are searched for only when no single byte has already demanded canonicalisation:

pub(crate) fn scan(text: &[u8]) -> Classes {
    let (chunks, remainder) = text.as_chunks::<8>();
    // Four accumulators keep the OR chains short so the loads can issue back to back.
    let mut lanes = [0u16; 4];
    for chunk in chunks {
        lanes[0] |= TABLE[usize::from(chunk[0])] | TABLE[usize::from(chunk[4])];
        lanes[1] |= TABLE[usize::from(chunk[1])] | TABLE[usize::from(chunk[5])];
        lanes[2] |= TABLE[usize::from(chunk[2])] | TABLE[usize::from(chunk[6])];
        lanes[3] |= TABLE[usize::from(chunk[3])] | TABLE[usize::from(chunk[7])];
    }
    let mut bits = lanes[0] | lanes[1] | lanes[2] | lanes[3];
    for &byte in remainder {
        bits |= TABLE[usize::from(byte)];
    }
    // The pairs matter only while no single byte has demanded canonicalisation yet.
    if bits & CANONICAL == 0
        && ((bits & SPACE != 0 && has_pair(text, b' ', b' '))
            || (bits & (SLASH | STAR) == SLASH | STAR && has_pair(text, b'/', b'*')))
    {
        bits |= CANONICAL;
    }
    Classes { bits }
}

Detectors

  • Signatures. All strong signatures of every category live in one tagged automaton; a hit is a terminal deny named waf:sqli, waf:xss, waf:path-traversal, or waf:rce.
  • SQL injection. A single-pass word scanner looks up each alphanumeric word (at most seven bytes) in the keyword table and, on or / and, checks for a literal = literal tautology; id=1 or 1=1 is terminal. Otherwise a quote byte is mandatory and the evidence must score at least 4 out of: quote (1), up to two keywords (2), a comment marker (1), an = (1). admin'-- is terminal by itself. “it’s a group order from the shop” scores 3 and passes.
  • Cross-site scripting. Requires <; fires when a tag that can host script co-occurs with an on<event>= attribute in attribute position. onboarding=1 does not count.
  • Command injection. Requires a separator; fires when ;, |, &&, $(, a backtick, or a newline is followed by a known command name. status ok; done | next passes.
  • Path traversal. Signatures (../, ..%2f, /etc/passwd, id_rsa, …) plus NUL and %00.

Structural headers whose grammar legitimately contains quotes and stars (Accept*, Content-Type, Sec-*, If-*, …) are skipped; the path, query, User-Agent, other headers, and the first 8 KB of the body are inspected, and fields with percent escapes, plus signs, comment openers, or collapsible whitespace are canonicalised into an 8 KB stack buffer and inspected again, so 1%27/**/UnIoN/**/SeLeCt and %252e%252e/ collapse onto the raw signatures.

Cost

The inspection cost depends on the fields and bytes presented to the engine, not just the number of requests. The benchmark chapter reports separate Gate, Shield, and 8 KB body cases. The 8 KB bound is an inspection limit, not a claim that the rest of an upload is safe. An ingress using forward-auth must pass the relevant request information; omitted bytes cannot be inspected by this process.

The Declarative Policy Engine

A rule is a conjunction of optional criteria (path pattern, User-Agent pattern, up to four headers, up to eight IPv4/IPv6 CIDR blocks, one JA4 fingerprint or prefix) with an action ALLOW, DENY, CHALLENGE, or WEIGH, optional per-rule difficulty in work bits and algorithm, and a signed weight. Evaluation order:

  1. Semantic WAF (Shield only): violation is a terminal deny.
  2. Reputation trie: deny or allow prefixes are terminal.
  3. Rules in order: the first terminal match returns; WEIGH matches accumulate.
  4. Score: negative totals allow; totals \(\geq 40\) deny; totals \(\geq 10\) challenge with one extra work bit per 5 points above the threshold, capped at six.
  5. Static bypass paths, then trie challenge verdicts, then the bot automaton.
  6. Default action, challenge unless the policy file says otherwise.

Built-in rules allow /.well-known/*, /favicon.ico, /robots.txt, and /__sibuna/*, deny CF-Worker clients and Amazonbot, and challenge every Mozilla User-Agent: a browser string is free to forge, so admitting it would make the gate decorative.

{
  "default_action": "CHALLENGE",
  "waf": true,
  "thresholds": { "challenge_at": 10, "deny_at": 40, "bits_step": 5 },
  "ip_rules": { "10.0.0.0/8": "ALLOW", "2001:db8::/32": "DENY" },
  "rules": [
    { "name": "internal-api", "path": "/api/*", "headers": { "X-Api-Key": ".*" },
    "action": "ALLOW" },
    { "name": "checkout", "path": "/checkout/*", "action": "CHALLENGE",
      "challenge": { "difficulty": 20, "algorithm": "posw" } },
    { "name": "headless", "user_agent": "Headless", "action": "WEIGH", "weight": 30 },
    { "name": "no-language", "headers": { "Accept-Language": "" },
    "action": "WEIGH", "weight": -5 }
  ]
}

Worked Trace: an Encoded Attack with a Valid Session

Consider GET /search?q=%2527%2520OR%25201%253D1 from a client holding a valid session. First the HTTP parser separates the path and query without copying their bytes. Local limits run, then Shield inspects the request. The percent sign marks the field for canonicalization. One decoding pass exposes %27%20OR%201%3D1; a second exposes ' OR 1=1.

The tokenizer now sees a quote, the keyword OR, and equal literal operands. A denial is a terminal policy result. The valid session does not turn it into an allow: the session check only resolves a challenge decision. The storage hook copies a bounded incident record; SQL runs later. The response path need not hold the engine snapshot while an origin connection is idle.