Das Sibuna-Handbuch 1.0.0-beta.3 Dokumentation
Sprache: Deutsch
English简体中文한국어日本語EspañolDeutschहिन्दीالعربية
Auf dieser Seite

Teil VI: Automaten, Tries und die semantische Firewall

Wir untersuchen die Algorithmen hinter der Klassifikation in weniger als einer Mikrosekunde: den markierten Aho-Corasick-Automaten, den Radix-Trie für IPv4/IPv6, die Byteklassen-Tokenizer der semantischen WAF und die deklarative Richtlinien-Engine mit WEIGH-Bewertung.

Suche nach vielen Mustern in einem Durchlauf

Aho-Corasick als dichter DFA

Sibuna hat zwei Mengen literaler Muster: etwa vierzig Bot-Signaturen und etwa hundert Angriffssignaturen. Ein Feld nacheinander gegen \(N\) Muster zu durchsuchen kostet \(O(NM)\); der Automat von Aho und Corasick (1975) durchsucht es nach dem Aufbau eines Tries mit Fehlerkanten einmal in \(O(M)\). Sibuna faltet die Fehlerkanten beim Aufbau in die Übergangstabelle, sodass die Suche ein Tabellenzugriff pro Eingabebyte ist, ohne Verzweigungen über die Mustermenge. Der Automat liegt im Crate sibuna-patterns:

/// Rückt von `state` (einem Zeilenoffset) über `byte` vor.
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
}

Ein Zustand wird als sein Zeilenoffset in einer flachen Tabelle gespeichert, sodass ein Schritt aus einer Addition und einem Ladevorgang besteht. Die Zustände sind so nummeriert, dass jeder Trefferzustand nach allen anderen Zuständen kommt; einen Treffer zu erkennen ist dann ein einziger Vergleich mit first_match, ohne eine zweite Tabelle in der inneren Schleife zu laden.

Ein Trie von der Wurzel über G und GP zum Trefferzustand GPTBot und über C und Cl zum Trefferzustand ClaudeBot; gestrichelte Fehlerkanten führen von GP und Cl zurück zur Wurzel.
Abb. 9 Trie-Zustände und Fehlerkanten für zwei Signaturen

Das Zustandsbudget des Automaten ist eine Laufzeitoption. Die Richtlinien-Engine reserviert höchstens eine Wurzel plus die Summe aller Signaturlängen, eine sichere obere Schranke für die Trie-Zustände. Das vermeidet die früher übergroßen festen Tabellen und behält einen dichten Übergang für jede Byteklasse. Jedes Muster trägt eine kleine Kategoriemarke (0 bis 63, sodass eine Menge von Marken ein 64-Bit-Wort ist). Die Faltung der Groß-/Kleinschreibung nutzt eine Byteklassentabelle mit 256 Einträgen, die mit dem Automaten aufgebaut wird: Beide Schreibweisen eines Buchstabens teilen eine Klasse, und Bytes, die in keinem Muster vorkommen, teilen sich eine Klasse. Eine Tabellenzeile ist daher so breit wie die Zahl der verschiedenen Musterbytes plus eins statt 256. Die genauen Engine-Größen und der Vergleich mit der sequenziellen Teilzeichenkettensuche stehen in Teil VIII. Letztere nutzt dieselben Muster und dieselbe Semantik „irgendein Treffer“.

Reguläre Ausdrücke, SIMD-Engines und die Wahl

Für die Signaturstufe wurden drei Familien abgewogen:

  • Reguläre Ausdrücke mit Backtracking (im Stil eines Backtracking-Regelwerks) führen Hunderte Muster pro Anfrage aus und allokieren pro Treffer; sie sind die langsamste Option und am anfälligsten für Fehlalarme.
  • SIMD-Literal-Engines (Hyperscan, Vectorscan) filtern Blöcke von 16 bis 32 Bytes mit Nibble-Masken auf Shuffle-Basis vor (der „Teddy“-Algorithmus) und verifizieren Kandidaten mit Automaten. Bei langen Eingaben mit großen Literalmengen glänzen sie. Der Preis ist eine C++-Abhängigkeit von mehreren Megabyte, eine zur Übersetzungszeit gebaute Musterdatenbank, kein WebAssembly-Ziel und, bei Eingaben von hundert Bytes, kein Vorteil: Das ganze Feld ist schneller durchsucht, als ein einziger Cache-Miss dauert.
  • Dichter Aho-Corasick plus kleine strukturelle Tokenizer, die Linie von libinjection, liefert exaktes Linearzeitverhalten in einer festen Tabelle und braucht nichts außerhalb der Binärdatei.

Sibunas Felder sind kurz, daher gewinnt die dritte Familie sowohl beim Speicher als auch bei der Geschwindigkeit; Teil VIII verzeichnet etwa 1,56 ns pro Byte für einen 8-KiB-Body (der semantische Scan dauert 12.784,3 ns, 8kb_body_semantic_scan in benchmarks/results/primitives-latest.md). Das ist die eine Arbeitslast, bei der sich ein SIMD-Vorfilter lohnen würde, und SID 0006 führt ihn als offenen Punkt.

Der Radix-Trie für IPv4 und IPv6

Ein binärer Trie über 128-Bit-Schlüssel bedient beide Familien: IPv6-Präfixe werden unverändert eingefügt, IPv4-Präfixe werden in ::ffff:0:0/96 abgebildet, sodass ein /24 zu einem Pfad der Tiefe 120 wird. Die Knoten liegen in einem flachen Vec, indiziert mit u32, wobei Index null zugleich Wurzel und „kein Kind“ bedeutet. Eine Suche besteht so aus höchstens 128 abhängigen Ladevorgängen ohne Zeigerverfolgung. Der Trie ist der PrefixTrie des Crates sibuna-cidr.

Die 96 Ebenen des abgebildeten Präfixes bei jeder IPv4-Suche zu durchlaufen, würde 96 abhängige Ladevorgänge kosten, bevor das erste Bit der IPv4-Adresse erreicht ist. Deshalb merkt sich der Trie bei der Initialisierung den Knoten auf Tiefe 96 und beginnt IPv4-Suchen dort:

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())
};

Eine IPv4-Adresse zu klassifizieren kostet 32,0 ns, eine IPv6-Adresse 79,3 ns (ipv4_cidr_classification und ipv6_cidr_classification in benchmarks/results/primitives-latest.md). Die Engine befragt den Trie zweimal: terminale allow/deny-Urteile vor der Regeltabelle, sodass eine clusterweite Sperre jede Regel schlägt, und challenge-Urteile danach.

Die semantische Firewall

Eine Lektion über Fehlalarme

Die erste Version der WAF verglich eine flache Liste von Teilzeichenketten mit jedem Header. Die Liste enthielt /*, und jeder Browser sendet Accept: text/html,...,*/*;q=0.8. Jeder echte Browser wurde als SQL-Injection eingestuft und erhielt 403. Die Lektion prägte den Entwurf: Ein Detektor darf nur bei Struktur anschlagen, und die Testsuite schickt jetzt eine vollständige Chrome-Anfrage, einschließlich eines Kommentar-Bodys mit select, -- und einem Apostroph, durch die Engine und stellt sicher, dass sie sauber herauskommt.

Byteklassen in einem Durchlauf

Jedes geprüfte Feld wird einmal durchsucht, um festzustellen, welche Byteklassen vorkommen: Anführungszeichen, =, <, Shell-Trennzeichen, %, NUL, Auslöser der Kanonisierung und doppelte Leerzeichen. Jeder Detektor befragt die Klassen, statt erneut zu suchen, und der kanonisierte zweite Durchlauf läuft nur, wenn ein Auslöser gesehen wurde. Die Suche ist ein Zugriff auf eine Tabelle mit 256 Einträgen pro Byte, aus dem WAF-Modul von sibuna-policy. Vier Akkumulatoren halten die OR-Ketten kurz, und nach den beiden Bytepaaren (/* und zwei benachbarte Leerzeichen) wird nur gesucht, wenn noch kein einzelnes Byte die Kanonisierung verlangt hat:

pub(crate) fn scan(text: &[u8]) -> Classes {
    let (chunks, remainder) = text.as_chunks::<8>();
    // Vier Akkumulatoren halten die OR-Ketten kurz, damit die Loads dicht folgen.
    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)];
    }
    // Die Paare zählen nur, solange kein Byte allein die Kanonisierung verlangt hat.
    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 }
}

Detektoren

  • Signaturen. Alle starken Signaturen jeder Kategorie liegen in einem markierten Automaten; ein Treffer ist ein terminales deny mit dem Namen waf:sqli, waf:xss, waf:path-traversal oder waf:rce.
  • SQL-Injection. Ein Wortscanner mit einem Durchlauf schlägt jedes alphanumerische Wort (höchstens sieben Bytes) in der Schlüsselworttabelle nach und prüft bei or / and auf eine Tautologie literal = literal; id=1 or 1=1 ist terminal. Andernfalls ist ein Anführungszeichen-Byte Pflicht, und die Indizien müssen mindestens 4 Punkte erreichen aus: Anführungszeichen (1), bis zu zwei Schlüsselwörter (2), ein Kommentarzeichen (1), ein = (1). admin'-- ist für sich allein terminal. „it's a group order from the shop“ erreicht 3 Punkte und passiert.
  • Cross-Site-Scripting. Erfordert <; schlägt an, wenn ein Tag, das Skript aufnehmen kann, zusammen mit einem Attribut on<event>= an Attributposition vorkommt. onboarding=1 zählt nicht.
  • Command Injection. Erfordert ein Trennzeichen; schlägt an, wenn auf ;, |, &&, $(, einen Backtick oder einen Zeilenumbruch ein bekannter Befehlsname folgt. status ok; done | next passiert.
  • Path Traversal. Signaturen (../, ..%2f, /etc/passwd, id_rsa, ...) sowie NUL und %00.

Strukturelle Header, deren Grammatik legitim Anführungszeichen und Sterne enthält (Accept*, Content-Type, Sec-*, If-*, ...), werden übersprungen; Pfad, Query, User-Agent, die übrigen Header und die ersten 8 KB des Bodys werden geprüft. Felder mit Prozent-Escapes, Pluszeichen, Kommentaröffnern oder zusammenfassbarem Leerraum werden in einen 8-KB-Stack-Puffer kanonisiert und erneut geprüft, sodass 1%27/**/UnIoN/**/SeLeCt und %252e%252e/ auf die rohen Signaturen zusammenfallen.

Kosten

Die Kosten der Prüfung hängen von den Feldern und Bytes ab, die der Engine vorgelegt werden, nicht nur von der Zahl der Anfragen. Das Benchmark-Kapitel berichtet getrennte Fälle für Gate, Shield und einen 8-KB-Body. Die Grenze von 8 KB ist ein Prüflimit, keine Aussage, dass der Rest eines Uploads sicher ist. Ein Eingangsproxy im Forward-Auth-Modus muss die relevanten Anfrageinformationen weitergeben; ausgelassene Bytes kann dieser Prozess nicht prüfen.

Die deklarative Richtlinien-Engine

Eine Regel ist eine Konjunktion optionaler Kriterien (Pfadmuster, User-Agent-Muster, bis zu vier Header, bis zu acht IPv4/IPv6-CIDR-Blöcke, ein JA4-Fingerabdruck oder -Präfix) mit einer Aktion ALLOW, DENY, CHALLENGE oder WEIGH, optionaler Schwierigkeit pro Regel in Arbeitsbits und optionalem Algorithmus sowie einem vorzeichenbehafteten weight. Auswertungsreihenfolge:

  1. Semantische WAF (nur Shield): Ein Verstoß ist ein terminales deny.
  2. Reputations-Trie: deny- oder allow-Präfixe sind terminal.
  3. Regeln der Reihe nach: Der erste terminale Treffer liefert das Ergebnis; WEIGH-Treffer summieren sich.
  4. Bewertung: Negative Summen ergeben allow; Summen \(\geq 40\) ergeben deny; Summen \(\geq 10\) ergeben challenge mit einem zusätzlichen Arbeitsbit je 5 Punkte über der Schwelle, höchstens sechs.
  5. Statische Bypass-Pfade, dann challenge-Urteile des Tries, dann der Bot-Automat.
  6. Standardaktion, challenge, sofern die Richtliniendatei nichts anderes sagt.

Eingebaute Regeln erlauben /.well-known/*, /favicon.ico, /robots.txt und /__sibuna/*, lehnen CF-Worker-Clients und Amazonbot ab und belegen jeden Mozilla-User-Agent mit einer Challenge: Eine Browserzeichenkette lässt sich kostenlos fälschen, sie zuzulassen würde das Gate zur Dekoration machen.

{
  "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 }
  ]
}

Durchgerechnete Ablaufverfolgung: ein kodierter Angriff mit gültiger Sitzung

Betrachten wir GET /search?q=%2527%2520OR%25201%253D1 von einem Client mit gültiger Sitzung. Zuerst trennt der HTTP-Parser Pfad und Query, ohne ihre Bytes zu kopieren. Die lokalen Limits laufen, dann prüft Shield die Anfrage. Das Prozentzeichen markiert das Feld für die Kanonisierung. Ein Dekodierdurchlauf legt %27%20OR%201%3D1 frei; ein zweiter legt ' OR 1=1 frei.

Der Tokenizer sieht nun ein Anführungszeichen, das Schlüsselwort OR und gleiche literale Operanden. Eine Ablehnung ist ein terminales Richtlinienergebnis. Die gültige Sitzung macht daraus keine Erlaubnis: Die Sitzungsprüfung löst nur eine Challenge-Entscheidung auf. Der Speicher-Hook kopiert einen begrenzten Vorfallsdatensatz; SQL läuft später. Der Antwortpfad muss den Engine-Schnappschuss nicht halten, solange eine Verbindung zum Ursprungsserver untätig ist.