1. Hocheffizienter Tokenizer

$$\sum _{k=0}^{n-1}{3}^k=\frac{3^n-1}{2}$$

Dies ist die mathematische Grundlage des ternären Zahlensystems (Basis 3) und ternärer Bäume (Tries). Im Kontext der Tokenisierung und Textkomprimierung findet dieses Prinzip in zwei leistungsstarken Architekturen Anwendung:

1. Ternärer Suchbaum (Ternary Search Tree / TST) — Ultraschnelle Tokensuche

Wenn ein Tokenizer den Eingabetext in Tokens zerlegt, muss er sofort nach Wort-/Teilwortübereinstimmungen in einem Wörterbuch suchen.

In regulären Suchbäumen hat jeder Knoten 2 Zweige (<, >). Wenn wir 3 Zweige hinzufügen (<, =, >):

• Kleiner als (<): Gehe nach links, wenn das aktuelle Textzeichen kleiner ist als das Zeichen im Knoten
• Gleichheitszeichen (=): Gehe nach unten (zum nächsten Präfixsymbol).
• Größer als (>): Gehe nach rechts, wenn das Symbol größer als ist.

Was hat die progressive Summe $\frac{3^n-1}{2}$ damit zu tun?

Dies ist die maximale Anzahl von Knoten in einem idealen, vollständig verbundenen ternären Baum der Tiefe n.:

• Auf Stufe 0: 1 Knote (3⁰)
• Auf Stufe 1: 3 Knote (3¹)
• Auf Stufe 2: 9 Knote (3²)

Die Summe aller Knoten bis zur Tiefe n ist genau gleich $\frac{3^n-1}{2}$ .

Was bringt uns das?!

Sie können im Voraus ein flaches Array (Flat Array/Buffer) für den Tokenizer-Baum allokieren. Wenn Sie die maximale Tokenlänge n kennen, allokieren Sie genau $\frac{3^n-1}{2}$ Elemente im Speicher ohne dynamische Speicherzuweisungen. Die Adresse eines jeden Knotens wird mithilfe der Indexierungsformel in O(1)-Zeit berechnet, ganz ohne pointers/Zeiger!

2. Ternäre Token-Kodierung (Ternary Token ID / Base-3 Encodings)

Die meisten Tokenizer (BPE, WordPiece) verwenden Zweierpotenzen (Bitoperationen: 2ⁿ). Wenn Sie jedoch über begrenzten Speicher verfügen oder einen Low-Level-Tokenizer für spezialisierte Chips entwickeln (z. B. FPGAs oder neuromorphe Prozessoren, die mit ternärer Logik arbeiten –1, 0, 1 / 0, 1, 2):

Jede Symbolfolge wird in eine Zahl im 3-zahlensystem umgewandelt:

Token ID = c₀ * 3⁰ + c₁ * 3¹ + c₂ * 3² + ... + c_n-1 * 3^n-1

Summe der Progression $\frac{3^n-1}{2}$ bestimmt die obere Grenze (den Offset) für Token der Länge n:

• Tokens der Länge 1 belegen IDs von 0 bis 2.
• Token der Länge 2 belegen die IDs von 3 bis 11 (insgesamt 3² = 9 Stück, und der endgültige Bereich entspricht genau der Summe von $\frac{3^n-1}{2}$ = 4, unter Berücksichtigung der Offsets).

Wenn Sie einen Eingabestrom von Zeichen mit einer Token-ID abgleichen müssen, ohne die Funktion aufzurufen hashtable / dict:

def get_ternary_offset(depth):
    """
    Berechnet den Startindex in einem flachen Array für Token der Länge 'depth'.
    Verwendet die Formel für die Summe einer geometrischen Folge: (3^n - 1) / 2
    """
    return (3**depth - 1) // 2

# Beispiel: Konvertiere ein 3-stelliges Präfix (aus dem Alphabet {0, 1, 2}) in eine exakte ID in einem Array in O(1).
def encode_prefix_to_id(chars):
    # chars - ist eine Liste von Ziffern [c0, c1, c2], wobei jede Ziffer im Bereich (0, 1, 2) liegt.
    length = len(chars)
    offset = get_ternary_offset(length)

    # Wir berechnen den Wert in Base-3
    base3_val = sum(c * (3**i) for i, c in enumerate(chars))

    return offset + base3_val

# Länge 0 -> Offset 0
# Länge 1 -> Offset 1
# Länge 2 -> Offset 4
# Länge 3 -> Offset 13
              

Zusammenfassung:

• Vorberechnung der Speichergröße (Flache Trie-Datenstruktur) ohne dynamische Speicherzuweisung malloc/new.
• Sofortige Berechnung von Offsets in Token-Dictionaries mit Präfixgruppierung nach Länge.
• Aufbau eines Ternary Search Tree (TST), der Token schneller sucht als Hashtabellen ohne Kollisionen.

2. Sehr schnell – aber es wird noch schneller werden!!!

Die Kombination aus Bloom-Filter und ternärem Suchbaum (TST) erzeugt einen leistungsstarken hybriden Tokenizer: Der Bloom-Filter eliminiert sofort 100% der Präfixe und Teilwörter, die offensichtlich nicht im Wörterbuch vorhanden sind, und bewahrt den Prozessor so vor Cache-Fehlern (L1/L2 Cache-Fehlern) beim Durchlaufen des Baums.

Die Bedeutung ist einfach: Wenn der Bloom-Filter NEIN sagt, führen wir in TST nicht einmal Zeiger-/Array-Durchläufe durch.

Architektur: Bloom Filter + TST

1. Bloom Filter:

• Ein kleiner Bitsatz im RAM, der vollständig in den L1/L2-Cache der CPU passt.
• Nimmt eine Teilzeichenkette (oder ein Präfix) entgegen und gibt Folgendes zurück: 0 (Definitiv nicht im Wörterbuch) oder 1 (Möglicherweise).

2. TST (Präziser Baum):

• Wird nur aufgerufen, wenn der Bloom-Filter 1 zurückgibt.
• Führt eine exakte Suche nach einem Token oder der längsten Übereinstimmung durch (Longest Prefix Match).

Für maximale Geschwindigkeit erstellen wir ein einfaches, aber schnelles BitSet mit mehreren Hashfunktionen (mittels mmh3 oder einer schnellen Bitmaske) und verknüpfen es mit einem ternären Baum:

import math

class FastBloomFilter:
    def __init__(self, expected_elements: int, false_positive_rate: float = 0.01):
        # Automatische Berechnung der Bitarraygröße (m) und der Anzahl der Hashwerte (k)
        self.size = int(- (expected_elements * math.log(false_positive_rate)) / (math.log(2) ** 2))
        self.k = int((self.size / expected_elements) * math.log(2))
        self.bit_array = [0] * self.size

    def _hashes(self, string: str):
        # Schnelle Hashes durch Shift-Generierung (in C++ ist dies üblicherweise murmurhash3 / xxHash)
        h = hash(string)
        for i in range(self.k):
            # Hier können Sie natürlich "%" verwenden, aber um es noch schneller zu machen: https://pypi.org/project/divisibility-library/ (pip install divisibility-library)
            yield (h + i * (h >> 3)) % self.size

    def add(self, string: str):
        for bit_index in self._hashes(string):
            self.bit_array[bit_index] = 1

    def __contains__(self, string: str) -> bool:
        # Eine falsche Antwort stellt sicher, dass das Element DEFINITIV NICHT EXISTIERT.
        return all(self.bit_array[bit_index] for bit_index in self._hashes(string))


class TSTNode:
    def __init__(self, char: str):
        self.char = char
        self.left = None
        self.mid = None
        self.right = None
        self.token_id = None  # None, wenn es sich um ein Zwischenpräfix und nicht um das Ende eines Tokens handelt


class AcceleratedTSTTokenizer:
    def __init__(self, expected_tokens: int = 50000):
        self.root = None
        # Front-End-Bloom-Filter
        self.bloom = FastBloomFilter(expected_elements=expected_tokens, false_positive_rate=0.01)

    def insert(self, token: str, token_id: int):
        # 1. Wir registrieren das Token selbst und ALLE seine Präfixe im Bloom-Filter.
        for i in range(1, len(token) + 1):
            self.bloom.add(token[:i])

        # 2. Einfügen eines Tokens in den ternären Suchbaum
        def _insert(node, char_idx):
            char = token[char_idx]
            if node is None:
                node = TSTNode(char)

            if char < node.char:
                node.left = _insert(node.left, char_idx)
            elif char > node.char:
                node.right = _insert(node.right, char_idx)
            elif char_idx < len(token) - 1:
                node.mid = _insert(node.mid, char_idx + 1)
            else:
                node.token_id = token_id
            return node

        self.root = _insert(self.root, 0)

    def lookup(self, word: str) -> int:
        """
        Sofortige Token-Suche mit Bloom-Filter-Pruning.
        """
        # Zuerst überprüfen wir den Bloom-Filter: Wenn er auf „False“ steht, gehen wir gar nicht erst zu TST!
        if word not in self.bloom:
            return None  # Instant Reject! (O(k) ohne Dereferenzierung von TST-Zeigern)

        # Wenn der Bloom-Filter grünes Licht gibt, führen wir eine eigentliche Suche in TST durch.
        curr = self.root
        idx = 0
        while curr and idx < len(word):
            char = word[idx]
            if char < curr.char:
                curr = curr.left
            elif char > curr.char:
                curr = curr.right
            else:
                if idx == len(word) - 1:
                    return curr.token_id
                curr = curr.mid
                idx += 1
        return None
              

Wie wird es beschleunigt Greedy Tokenization (Max Match)

Bei der Tokenisierung von Text (zum Beispiel mit dem gierigen Maximal-Munch-Algorithmus) versucht der Tokenizer ständig, das längste Token zu erraten: Er nimmt 10 Zeichen, schlägt sie im Wörterbuch nach und reduziert sie gegebenenfalls auf 9, 8, 7 usw.

Ohne Bloom ist er gezwungen, für jede falsche Länge dutzende Sprünge über TST-Knoten hinweg zu machen.:

Bloom-freie Tests: Text "supercali..." --> Suche in TST --> sprünge im Gedächtnis (Cache Misses) --> Fail

Mit Bloom-Filter:

• supercalifragilistic in Bloom? --> NO (0 Nanosekunden, sofortiger Ausfall!)
• supercalifragilist in Bloom? --> NO (0 Nanosekunden!)
• ...
• super in Bloom? --> YES --> Für die genaue Identifizierung gehen wir zu TST.

Abschließende CPU-Optimierung (Hardware-Level)

Um in der Produktion mit C++ maximale Geschwindigkeit zu erreichen

• SIMD-Befehle für Bloom-Filter: Die Überprüfung von k Hashes erfolgt in einem AVX2 / AVX-512-Befehl, da alle Bitmasken parallel in CPU-Registern verarbeitet werden.
• Flat Bloom + Flat TST: Der Bloom-Filter passt in eine einzelne zusammenhängende Bytefolge (64 Byte Cache-Zeile).
• Ergebnis: 90–95% der falschen Verzweigungen werden entfernt, bevor der CPU-Speicherbus auch nur eine einzige Anfrage außerhalb des L1-Caches stellt.

4. Anwendungsgebiete

Dieser hybride Tokenizer (Bloom-Filter + ternärer Suchbaum / Base-3 Offset Trie) eignet sich ideal für Aufgaben, bei denen minimale Latenz, Einsparung des L1/L2-CPU-Caches und ein Speicherbedarf von null entscheidend sind.

Hier sind die wichtigsten Bereiche, in denen diese Architektur gegenüber herkömmlichen Hashtabellen und BPE-Tokenisierern in Python Vorteile bietet:

1. High-Frequency Inference auf CPU (Edge AI und lokale LLM)

Wenn ein lokales Sprachmodell oder ein Einbettungsdienst auf Server-CPUs ohne GPU ausgeführt wird (z. B. Inferenz auf Intel AMX/AVX-512- oder ARM-Chips):

• Das Problem mit regulären Tokenizern: Maximal Munch (BPE) führt dazu, dass der Prozessor regelmäßig im RAM herumspringt (DRAM Cache Misses), wodurch die Anzahl der Token pro Sekunde reduziert wird.
• Lösung: Der Bloom-Filter entfernt ungültige Präfixzweige direkt im L1-Cache der CPU (da das Bit-Array winzig ist und in 32–64 KB passt), und ein flacher TST-Baum mit mathematischer Indizierung $\frac{3^n-1}{2}$ ermöglicht einen Übergang zur Token-ID in O(1) ohne Entpacken von Zeigern.

2. High-Throughput Webserver und API-Gateways (WAF / Reverse Proxies)

In stark ausgelasteten Backends (Nginx, C++ Gateway)

• Tokenisierung eingehender Anfragen: Zur schnellen Erkennung von Spam, SQL-Injections, XSS-Mustern oder zur Echtzeit-Protokollanalyse.
• Warum hier: Bloom Filter durchbricht sofort 99% des normalen Datenverkehrs („dieses gefährliche Token ist definitiv nicht vorhanden“), ohne den Haupt-TST-Index überhaupt zu laden.

3. Eingebettete Systeme und IoT (Embedded / Microcontrollers)

Auf Geräten mit extrem begrenztem Arbeitsspeicher (16 MB - 512 MB):

• Die Forme $\frac{3^n-1}{2}$ ermöglicht es Ihnen, einen statischen Speicherpuffer (Flat Array) bereits bei der Kompilierung zu allokieren, ohne dynamische Allokation (malloc/new) zu verwenden, was aufgrund der Speicherfragmentierung im IoT gefährlich ist.
• Durch das Fehlen von Hashtabellen mit Kollisionen wird eine maximale Leistungsverschlechterung vermieden (Worst-case time complexity).

4. Computernetzwerk und DPI (Deep Packet Inspection)

Bei der Verarbeitung von Netzwerkverkehr auf Paketebene:

• Suche nach Schlüsselwörtern/Headern in einem binären Datenstrom von Netzwerkpaketen.
• SIMD-beschleunigter Bloom-Filter (über AVX/NEON geprüft) plus TST ermöglichen das Filtern von Gigabit-Datenströmen ohne Paketverlust.

5. Suchmaschinen und Datenbanken (In-Memory Search)

Bei der Volltextsuche (Lucene, Meilisearch) und Compilern:

• Autovervollständigung (Trie-Suche): Ermöglicht das Durchsuchen von Wörterbüchern nach Millionen von Begriffen in Nanosekunden und das Herausfiltern von Optionen, die nicht in der Datenbank enthalten sind.
• Lexikalische Analyse (Lexer): In Compilern und Interpretern von Programmiersprachen zur schnellen Tokenisierung von Quellcode in Schlüssel und Bezeichner.

Dieser Ansatz ist erforderlich, wenn ein herkömmlicher Tokenizer durch die Speicherbandbreite eingeschränkt ist. Während Standard-TikToken- oder Tokenizer beim Parsen von Millionen von Textströmen durch Cache-Fehler Zeit verschwenden, reduziert die Bloom+TST-Struktur die CPU-Arbeit auf sofortige Bitoperationen.

5. DPI (Deep Packet Inspection)

In Netzwerksystemen (DPDK, eBPF, Nginx) arbeitet DPI mit einem durchgängigen binären Paketstrom (z. B. HTTP/DNS/TLS-Verkehr) und muss Signaturen (bösartige URLs, blockierte Domains, SQLi-Angriffe) in Nanosekunden identifizieren.

Unser DPI scannt das Netzwerkpaket mit einem Fenster variabler Länge:

• Der Bloom-Filter verwirft sofort 99% der sauberen Batches direkt im CPU L1-Cache (NO = „Das Paket ist sauber, wir leiten es weiter“).
• Flat TST ist nur dann aktiviert, wenn Bloom die Signatur/Angriffs-ID in O(1) findet.

import math
import time

# ==========================================
# 1. Ultraschneller Bloom-Filter für DPI
# ==========================================
class FastBloomFilter:
    def __init__(self, expected_elements: int = 10000, fp_rate: float = 0.001):
        self.size = int(-(expected_elements * math.log(fp_rate)) / (math.log(2) ** 2))
        self.k = int((self.size / expected_elements) * math.log(2))
        self.bit_array = bytearray((self.size + 7) // 8)  # Bytebasierte Bitmap (L1-Cache-freundlich)

    def _get_bits(self, data: bytes):
        # In der Produktion von C++ werden hier AVX2/AVX-512 + xxHash/MurmurHash3 verwendet. (Siehe den Artikel: https://bogatyrev.de/quantization.html)
        h = hash(data)
        for i in range(self.k):
            bit_idx = (h + i * (h >> 3)) % self.size
            yield bit_idx >> 3, 1 << (bit_idx & 7)

    def add(self, data: bytes):
        for byte_idx, bit_mask in self._get_bits(data):
            self.bit_array[byte_idx] |= bit_mask

    def __contains__(self, data: bytes) -> bool:
        for byte_idx, bit_mask in self._get_bits(data):
            if not (self.bit_array[byte_idx] & bit_mask):
                return False  # Instant Reject (Es gibt DEFINITIV KEINE bösartige Signatur)
        return True


# ==========================================
# 2. Ternärer Suchbaum (TST) für präzise ID-Signaturen
# ==========================================
class TSTNode:
    __slots__ = ('byte', 'left', 'mid', 'right', 'rule_id')  # __slots__ spart RAM und beschleunigt den Zugriff

    def __init__(self, byte: int):
        self.byte = byte
        self.left = None
        self.mid = None
        self.right = None
        self.rule_id = None  # Blockierungsregel-ID (falls dies das Ende der Signatur ist)


class FlatTrieDPI:
    def __init__(self):
        self.root = None

    def insert(self, pattern: bytes, rule_id: int):
        def _insert(node, idx):
            b = pattern[idx]
            if node is None:
                node = TSTNode(b)

            if b < node.byte:
                node.left = _insert(node.left, idx)
            elif b > node.byte:
                node.right = _insert(node.right, idx)
            elif idx < len(pattern) - 1:
                node.mid = _insert(node.mid, idx + 1)
            else:
                node.rule_id = rule_id
            return node

        self.root = _insert(self.root, 0)

    def match(self, pattern: bytes) -> int:
        curr = self.root
        idx = 0
        while curr and idx < len(pattern):
            b = pattern[idx]
            if b < curr.byte:
                curr = curr.left
            elif b > curr.byte:
                curr = curr.right
            else:
                if idx == len(pattern) - 1:
                    return curr.rule_id
                curr = curr.mid
                idx += 1
        return None


# ==========================================
# 3. Einheitliche DPI-Engine (Bloom + TST Tokenizer)
# ==========================================
class DPIScanner:
    def __init__(self, min_pattern_len=4, max_pattern_len=16):
        self.bloom = FastBloomFilter(expected_elements=50000, fp_rate=0.001)
        self.tst = FlatTrieDPI()
        self.min_len = min_pattern_len
        self.max_len = max_pattern_len
        self.rules_map = {}

    def add_rule(self, rule_id: int, pattern: str, description: str):
        pattern_bytes = pattern.encode('utf-8')
        self.rules_map[rule_id] = description

        # 1. Заносим в TST
        self.tst.insert(pattern_bytes, rule_id)

        # 2. Регистрируем в Bloom Filter сам паттерн и все его под-префиксы
        for i in range(self.min_len, len(pattern_bytes) + 1):
            self.bloom.add(pattern_bytes[:i])

    def inspect_packet(self, packet_payload: bytes):
        """
        Durchsucht die Nutzdaten des Pakets mit einem gleitenden Fenster.
        """
        payload_len = len(packet_payload)

        # Gleitfenster-Scanning von Paketbytes
        for i in range(payload_len):
            # Wir prüfen Teilstrings unterschiedlicher Länge (von min_len bis max_len).
            for length in range(self.min_len, min(self.max_len, payload_len - i) + 1):
                chunk = packet_payload[i : i + length]

                # SCHRITT 1: Bloom-Filterprüfung (Unterdrückt 99,9% des legitimen Datenverkehrs in ca. 2-5 ns)
                if chunk not in self.bloom:
                    continue  # Wir lassen es aus, wir schauen es uns in TST nicht einmal an!

                # SCHRITT 2: Wenn Bloom „Wahr“ zurückgibt, prüfen Sie in TST auf eine exakte Übereinstimmung.
                rule_id = self.tst.match(chunk)
                if rule_id is not None:
                    return {
                        "action": "DROP",
                        "rule_id": rule_id,
                        "rule_name": self.rules_map[rule_id],
                        "offset": i,
                        "matched_bytes": chunk
                    }

        return {"action": "FORWARD"}


# ==========================================
# 4. Testen der DPI-Engine
# ==========================================
if __name__ == "__main__":
    scanner = DPIScanner(min_pattern_len=4, max_pattern_len=32)

    # Laden der Signaturregelbasis (WAF / Firewall-Regeln)
    scanner.add_rule(101, "SELECT * FROM", "SQL Injection Attempt")
    scanner.add_rule(102, "<script>", "XSS Attack")
    scanner.add_rule(103, "malware.com", "Blacklisted Domain Request")
    scanner.add_rule(104, "etc/passwd", "Path Traversal Attack")

    # Simulieren eines eingehenden HTTP-Netzwerkpakets
    clean_packet = b"GET /index.html HTTP/1.1\r\nHost: example.com\r\nUser-Agent: Mozilla/5.0\r\n\r\n"
    malicious_packet = b"POST /login HTTP/1.1\r\nHost: example.com\r\n\r\nuser=admin' UNION SELECT * FROM users--"

    print("--- 1. Scannen eines normalen Pakets ---")
    res1 = scanner.inspect_packet(clean_packet)
    print(f"Ergebnis: {res1['action']}")

    print("\n--- 2. Angriffsscan ---")
    start = time.perf_counter_ns()
    res2 = scanner.inspect_packet(malicious_packet)
    end = time.perf_counter_ns()

    print(f"Ergebnis: {res2['action']}")
    if res2['action'] == "DROP":
        print(f"Bedrohung erkannt: [{res2['rule_name']}] auf Byte {res2['offset']}")
        print(f"Zeit: {(end - start) / 1000:.2f} µs")
                    

6. Und nun mit großem Respekt vor Igor Sysoev erstellen wir einen DPI im Nginx.

Bei Nginx befindet sich der ngx_buf_t Netzwerkpuffer bereits im L1/L2-Cache, sodass unser Bloom Filter + TST Hybrid mit maximaler Geschwindigkeit arbeitet und bösartige HTTP-Anfragen in der NGX_HTTP_ACCESS_PHASE-Phase verwirft, bevor sie den Upstream/Backend (Gunicorn, Flask, FastAPI) erreichen.

1. Der Modulquellcode (ngx_http_dpi_module.cpp) beinhaltet die gleichzeitige DPI-Prüfung sowohl der URI/Query-String als auch des User-Agent-Headers.

#include <vector>
#include <string>
#include <memory>
#include <cstring>
#include <cstdint>

extern "C" {
    #include <ngx_config.h>
    #include <ngx_core.h>
    #include <ngx_http.h>
}

/* ============================================================================
 * 1. Algorithmus: Bloom Filter (zur schnellen O(1)-Filterung von reinem Datenverkehr)
 * ============================================================================ */
class BloomFilter {
private:
    std::vector<bool> bitset;
    size_t size;

    uint32_t hash1(const char* str, size_t len) const {
        uint32_t hash = 5381;
        for (size_t i = 0; i < len; ++i) {
            hash = ((hash << 5) + hash) + static_cast<unsigned char>(tolower(str[i]));
        }
        return hash;
    }

    uint32_t hash2(const char* str, size_t len) const {
        uint32_t hash = 0;
        for (size_t i = 0; i < len; ++i) {
            hash = static_cast<unsigned char>(tolower(str[i])) + (hash << 6) + (hash << 16) - hash;
        }
        return hash;
    }

public:
    BloomFilter(size_t bits = 8192) : size(bits) {
        bitset.resize(bits, false);
    }

    void add(const std::string& key) {
        if (key.empty()) return;
        bitset[hash1(key.c_str(), key.length()) % size] = true;
        bitset[hash2(key.c_str(), key.length()) % size] = true;
    }

    bool contains_ngram(const char* str, size_t len) const {
        if (len == 0) return false;
        bool h1 = bitset[hash1(str, len) % size];
        bool h2 = bitset[hash2(str, len) % size];
        return h1 && h2;
    }
};

/* ============================================================================
 * 2. Algorithmus: Ternary Search Tree (TST) für präzise Mustersuche
 * ============================================================================ */
struct TSTNode {
    char splitchar;
    ngx_uint_t rule_id;
    std::shared_ptr<TSTNode> left;
    std::shared_ptr<TSTNode> mid;
    std::shared_ptr<TSTNode> right;

    TSTNode(char ch) : splitchar(ch), rule_id(0), left(nullptr), mid(nullptr), right(nullptr) {}
};

class TSTree {
private:
    std::shared_ptr<TSTNode> root;

    std::shared_ptr<TSTNode> insert(std::shared_ptr<TSTNode> node, const char* s, ngx_uint_t rule_id) {
        char ch = tolower(*s);
        if (node == nullptr) {
            node = std::make_shared<TSTNode>(ch);
        }

        if (ch < node->splitchar) {
            node->left = insert(node->left, s, rule_id);
        } else if (ch > node->splitchar) {
            node->right = insert(node->right, s, rule_id);
        } else {
            if (*(s + 1) != '\0') {
                node->mid = insert(node->mid, s + 1, rule_id);
            } else {
                node->rule_id = rule_id;
            }
        }
        return node;
    }

public:
    TSTree() : root(nullptr) {}

    void add_pattern(const std::string& pattern, ngx_uint_t rule_id) {
        if (!pattern.empty()) {
            root = insert(root, pattern.c_str(), rule_id);
        }
    }

    /* Finden einer genauen Präfix-/Teilzeichenfolge-Übereinstimmung in TST */
    ngx_uint_t search_substring(const char* text, size_t text_len) const {
        if (!root || text_len == 0) return 0;

        for (size_t i = 0; i < text_len; ++i) {
            std::shared_ptr<TSTNode> curr = root;
            size_t j = i;

            while (curr && j < text_len) {
                char ch = tolower(text[j]);
                if (ch < curr->splitchar) {
                    curr = curr->left;
                } else if (ch > curr->splitchar) {
                    curr = curr->right;
                } else {
                    if (curr->rule_id != 0) {
                        return curr->rule_id; /* Signaturübereinstimmung gefunden! */
                    }
                    curr = curr->mid;
                    j++;
                }
            }
        }
        return 0;
    }
};

/* ============================================================================
 * 3. Konfigurationsstruktur des Nginx-Moduls
 * ============================================================================ */
typedef struct {
    ngx_flag_t    enable;
    BloomFilter  *bf;
    TSTree       *tst_uri;
    TSTree       *tst_ua;
    size_t        min_ngram_len;
} ngx_http_dpi_loc_conf_t;

/* Nginx-Funktionsprototypen */
static ngx_int_t ngx_http_dpi_handler(ngx_http_request_t *r);
static ngx_int_t ngx_http_dpi_init(ngx_conf_t *cf);
static void *ngx_http_dpi_create_loc_conf(ngx_conf_t *cf);
static char *ngx_http_dpi_merge_loc_conf(ngx_conf_t *cf, void *parent, void *child);
static char *ngx_http_dpi_block_pattern(ngx_conf_t *cf, ngx_command_t *cmd, void *conf);
static char *ngx_http_dpi_block_ua(ngx_conf_t *cf, ngx_command_t *cmd, void *conf);

/* Modulanweisungen */
static ngx_command_t ngx_http_dpi_commands[] = {

    { ngx_string("dpi_inspect"),
      NGX_HTTP_MAIN_CONF|NGX_HTTP_SRV_CONF|NGX_HTTP_LOC_CONF|NGX_CONF_FLAG,
      ngx_conf_set_flag_slot,
      NGX_HTTP_LOC_CONF_OFFSET,
      offsetof(ngx_http_dpi_loc_conf_t, enable),
      NULL },

    { ngx_string("dpi_block_pattern"),
      NGX_HTTP_MAIN_CONF|NGX_HTTP_SRV_CONF|NGX_HTTP_LOC_CONF|NGX_CONF_TAKE2,
      ngx_http_dpi_block_pattern,
      NGX_HTTP_LOC_CONF_OFFSET,
      0,
      NULL },

    { ngx_string("dpi_block_ua"),
      NGX_HTTP_MAIN_CONF|NGX_HTTP_SRV_CONF|NGX_HTTP_LOC_CONF|NGX_CONF_TAKE2,
      ngx_http_dpi_block_ua,
      NGX_HTTP_LOC_CONF_OFFSET,
      0,
      NULL },

    ngx_null_command
};

static ngx_http_module_t ngx_http_dpi_module_ctx = {
    NULL,                          /* preconfiguration */
    ngx_http_dpi_init,             /* postconfiguration */
    NULL,                          /* create main configuration */
    NULL,                          /* init main configuration */
    NULL,                          /* create server configuration */
    NULL,                          /* merge server configuration */
    ngx_http_dpi_create_loc_conf,  /* create location configuration */
    ngx_http_dpi_merge_loc_conf    /* merge location configuration */
};

ngx_module_t ngx_http_dpi_module = {
    NGX_MODULE_V1,
    &ngx_http_dpi_module_ctx,
    ngx_http_dpi_commands,
    NGX_HTTP_MODULE,
    NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    NGX_MODULE_V1_PADDING
};

/* Initialisierung der Konfigurationsstruktur */
static void *
ngx_http_dpi_create_loc_conf(ngx_conf_t *cf)
{
    ngx_http_dpi_loc_conf_t *conf;

    conf = (ngx_http_dpi_loc_conf_t *)ngx_pcalloc(cf->pool, sizeof(ngx_http_dpi_loc_conf_t));
    if (conf == NULL) {
        return NULL;
    }

    conf->enable = NGX_CONF_UNSET;
    conf->bf = new BloomFilter();
    conf->tst_uri = new TSTree();
    conf->tst_ua = new TSTree();
    conf->min_ngram_len = 3;

    return conf;
}

static char *
ngx_http_dpi_merge_loc_conf(ngx_conf_t *cf, void *parent, void *child)
{
    ngx_http_dpi_loc_conf_t *prev = (ngx_http_dpi_loc_conf_t *)parent;
    ngx_http_dpi_loc_conf_t *conf = (ngx_http_dpi_loc_conf_t *)child;

    ngx_conf_merge_value(conf->enable, prev->enable, 0);

    return NGX_CONF_OK;
}

/* Regeln zu BloomFilter und TSTree (URI) hinzufügen */
static char *
ngx_http_dpi_block_pattern(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
{
    ngx_http_dpi_loc_conf_t *lcf = (ngx_http_dpi_loc_conf_t *)conf;
    ngx_str_t               *value = (ngx_str_t *) cf->args->elts;

    std::string pattern((char *)value[1].data, value[1].len);
    ngx_uint_t rule_id = ngx_atoi(value[2].data, value[2].len);

    if (rule_id == (ngx_uint_t) NGX_ERROR) {
        return (char *) "invalid rule ID";
    }

    /* Zur vorläufigen Prüfung 3 Gramm zum Bloom Filter hinzufügen */
    for (size_t i = 0; i + lcf->min_ngram_len <= pattern.length(); ++i) {
        lcf->bf->add(pattern.substr(i, lcf->min_ngram_len));
    }

    /* Das gesamte Muster zu TST hinzufügen */
    lcf->tst_uri->add_pattern(pattern, rule_id);

    return NGX_CONF_OK;
}

/* Hinzufügen von Regeln zu BloomFilter und TSTree (User-Agent) */
static char *
ngx_http_dpi_block_ua(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
{
    ngx_http_dpi_loc_conf_t *lcf = (ngx_http_dpi_loc_conf_t *)conf;
    ngx_str_t               *value = (ngx_str_t *) cf->args->elts;

    std::string pattern((char *)value[1].data, value[1].len);
    ngx_uint_t rule_id = ngx_atoi(value[2].data, value[2].len);

    if (rule_id == (ngx_uint_t) NGX_ERROR) {
        return (char *) "invalid rule ID";
    }

    for (size_t i = 0; i + lcf->min_ngram_len <= pattern.length(); ++i) {
        lcf->bf->add(pattern.substr(i, lcf->min_ngram_len));
    }

    lcf->tst_ua->add_pattern(pattern, rule_id);

    return NGX_CONF_OK;
}

/* Registrierung in ACCESS_PHASE */
static ngx_int_t
ngx_http_dpi_init(ngx_conf_t *cf)
{
    ngx_http_handler_pt        *h;
    ngx_http_core_main_conf_t  *cmcf;

    cmcf = (ngx_http_core_main_conf_t *)ngx_http_conf_get_module_main_conf(cf, ngx_http_core_module);

    h = (ngx_http_handler_pt *)ngx_array_push(&cmcf->phases[NGX_HTTP_ACCESS_PHASE].handlers);
    if (h == NULL) {
        return NGX_ERROR;
    }

    *h = ngx_http_dpi_handler;

    return NGX_OK;
}

/* ============================================================================
 * 4. Inspektionscontroller (Bloom Filter Fast-Path -> TST-Suche)
 * ============================================================================ */
static ngx_int_t
ngx_http_dpi_handler(ngx_http_request_t *r)
{
    ngx_http_dpi_loc_conf_t *lcf;
    lcf = (ngx_http_dpi_loc_conf_t *)ngx_http_get_module_loc_conf(r, ngx_http_dpi_module);

    if (lcf == NULL || !lcf->enable) {
        return NGX_DECLINED;
    }

    /* --- URI-PRÜFUNG --- */
    if (r->unparsed_uri.len >= lcf->min_ngram_len) {
        const char* uri_str = (char*) r->unparsed_uri.data;
        size_t uri_len = r->unparsed_uri.len;
        bool possible_threat = false;

        /* PHASE 1: Bloom-Filter – Schnelle N-Gramm-Prüfung */
        for (size_t i = 0; i + lcf->min_ngram_len <= uri_len; ++i) {
            if (lcf->bf->contains_ngram(uri_str + i, lcf->min_ngram_len)) {
                possible_threat = true;
                break;
            }
        }

        /* PHASE 2: Wenn Bloom Filter verdächtig ist -> TST ausführen */
        if (possible_threat) {
            ngx_uint_t matched_rule = lcf->tst_uri->search_substring(uri_str, uri_len);
            if (matched_rule != 0) {
                ngx_log_error(NGX_LOG_WARN, r->connection->log, 0,
                              "[DPI Module] Threat detected in URI via Bloom+TST! Rule ID: %ui, URI: \"%V\"",
                              matched_rule, &r->unparsed_uri);
                return NGX_HTTP_FORBIDDEN;
            }
        }
    }

    /* --- BENUTZER-AGENT-PRÜFUNG --- */
    if (r->headers_in.user_agent != NULL && r->headers_in.user_agent->value.len >= lcf->min_ngram_len) {
        const char* ua_str = (char*) r->headers_in.user_agent->value.data;
        size_t ua_len = r->headers_in.user_agent->value.len;
        bool possible_threat = false;

        for (size_t i = 0; i + lcf->min_ngram_len <= ua_len; ++i) {
            if (lcf->bf->contains_ngram(ua_str + i, lcf->min_ngram_len)) {
                possible_threat = true;
                break;
            }
        }

        if (possible_threat) {
            ngx_uint_t matched_rule = lcf->tst_ua->search_substring(ua_str, ua_len);
            if (matched_rule != 0) {
                ngx_log_error(NGX_LOG_WARN, r->connection->log, 0,
                              "[DPI Module] Threat detected in User-Agent via Bloom+TST! Rule ID: %ui, UA: \"%V\"",
                              matched_rule, &r->headers_in.user_agent->value);
                return NGX_HTTP_FORBIDDEN;
            }
        }
    }

    return NGX_DECLINED;
}

2. config - im selben Verzeichnis

ngx_addon_name=ngx_http_dpi_module

if test -n "$ngx_module_link"; then
    # Dynamischer Build von Nginx (1.9.11+)
    ngx_module_type=HTTP
    ngx_module_name=ngx_http_dpi_module
    ngx_module_srcs="$ngx_addon_dir/ngx_http_dpi_module.cpp"

    # Linker-Flags für die C++-Bibliothek
    ngx_module_libs="-lstdc++"

    # Hinzufügen eines C++11-Flags NUR für den C++/g++-Compiler
    NGX_ADDON_DEPS="$NGX_ADDON_DEPS"

    . auto/module

    # Einrichten einer Flag-Variable speziell für unser .cpp-Objekt
    ngx_cc_opt="$ngx_cc_opt -std=c++11"
else
    # Statischer Aufbau
    HTTP_MODULES="$HTTP_MODULES ngx_http_dpi_module"
    NGX_ADDON_SRCS="$NGX_ADDON_SRCS $ngx_addon_dir/ngx_http_dpi_module.cpp"
    CORE_LIBS="$CORE_LIBS -lstdc++"
fi

3. Dank der integrierten Unterstützung für dynamische Module in Nginx (load_module) können Sie das DPI-Modul direkt über eine dynamische Bibliothek (.so) einbinden, ohne den gesamten Nginx-Server neu zu kompilieren. Sie müssen nicht den gesamten Nginx-Quellcode herunterladen und `make install` ausführen. Es genügt, den Quellcode für die auf Ihrem System installierte Nginx-Version zu verwenden und nur das Modul mit `make modules` zu kompilieren.

# Laden Sie den Quellcode für Ihre spezifische Nginx-Version herunter (z. B. 1.24.0).
wget http://nginx.org/download/nginx-1.24.0.tar.gz
tar -zxvf nginx-1.24.0.tar.gz
cd nginx-1.24.0

4. Wir konfigurieren die Quellen, indem wir unser Modul als dynamisch angeben (--add-dynamic-module)

/path/to/your/dpi_module_folder - durch deinen Pfad ersetzen!!!

./configure --with-compat --add-dynamic-module=/path/to/your/dpi_module_folder --with-ld-opt="-lstdc++"

5. Wir kompilieren NUR das Modul (die Ausgabe ist eine .so-Datei).

make modules

6. Kopieren Sie die gesammelte .so

# Erstellen Sie einen Ordner, falls dieser noch nicht vorhanden ist
# sudo mkdir -p /usr/lib/nginx/modules
sudo cp objs/ngx_http_dpi_module.so /usr/lib/nginx/modules/

7. Erstellen Sie eine Konfigurationsdatei in den modules-available

sudo vi /etc/nginx/modules-available/50-mod-http-dpi.conf
# Fügen Sie eine Zeile ein, die den absoluten Pfad zu .so angibt:
load_module modules/ngx_http_dpi_module.so;

8. Symlink, damit Nginx das Modul beim Start aufruft:

sudo ln -s /etc/nginx/modules-available/50-mod-http-dpi.conf /etc/nginx/modules-enabled/

9. Überprüfen Sie Ihre Konfiguration:

# Syntaxprüfung (stellen Sie sicher, dass das Modul fehlerfrei geladen wurde)
sudo nginx -t

10. Öffnen Sie Ihre Nginx-Testkonfiguration (z. B. /etc/nginx/sites-available/default) und fügen Sie das Modul und die Validierungsregeln hinzu.

server {
    listen       80;
    server_name  127.0.0.1;
    location / {
        # DPI
        dpi_inspect on;
        # Gemeinsame Angriffssignaturen für alle Hosts
        dpi_block_pattern "SELECT * FROM" 101;
        dpi_block_pattern "<script>"       102;
        dpi_block_pattern "etc/passwd"     103;
        dpi_block_pattern "UNION SELECT"   104;
        # Häufig verwendete verbotene User-Agents
        dpi_block_ua "sqlmap"          201;
        dpi_block_ua "nikto"           202;
        dpi_block_ua "nmap"            203;
        dpi_block_ua "python-requests" 204;

            # Als nächstes kommt Ihr Skript
            include proxy_params;
            proxy_pass http://127.0.0.1:5000;
    }
}

11. Überprüfen Sie die Konfiguration und starten Sie Nginx neu:

# Syntaxprüfung (stellen Sie sicher, dass das Modul fehlerfrei geladen wurde)
sudo nginx -t
# Starten Sie Nginx neu
sudo systemctl reload nginx
# sudo /etc/init.d/nginx restart

12. Berechtigte Anfrage (sollte 200 OK zurückgeben):

curl -i http://localhost/

13. Anfrage mit Signatur im URI (sollte 403 Forbidden zurückgeben):

curl -i "http://localhost/static/etc/passwd"

14. Anfrage mit böswilligem User-Agent (sollte 403 Forbidden zurückgeben):

curl -i -A "sqlmap/1.5-stable" http://localhost/

Liebe Leserinnen und Leser, ich freue mich sehr über Ihr Interesse an meinem Blog.

Die Antwort auf Ihre Frage: „Warum funktioniert /?q=SELECT%20*%20FROM nicht?“

Antwort

• Gleitfenster: Die Funktion inspect_buffer untersucht den eingehenden Datenverkehr in Blöcken (Fenstern) fester Länge von 4 bis 16 Bytes.
• Signatur länger als Fenster: Wenn Ihre Signatur oder Abfragezeichenfolge länger als 16 Zeichen ist, kann der Algorithmus sie nicht vollständig in einem Schritt erfassen.
• Die Parameterzeichenkette ist sogar noch länger: Die Abfrage ?q=SELECT%20*%20FROM ist 21 Byte lang und überschreitet damit das Limit deutlich. Selbst wenn die Signatur selbst kürzer wäre, verschiebt das Präfix ?q= die Bytes, und das vollständige Fragment passt nicht in das aktuelle Scanfenster.

Eine unserer Hauptaufgaben besteht darin, dass die Geschwindigkeit der Ausführung von Anfragen an nginx nicht beeinträchtigt wird, da, wie ich oben bereits schrieb, alles direkt im Prozessor verarbeitet wird und mir gesagt wurde, dass die Geschwindigkeit im Nanosekundenbereich liegt.

Schauen Sie sich das Programm genau an:

 static int inspect_buffer(FastBloomFilter* bloom, FlatTrieDPI* tst, const uint8_t* payload, size_t payload_len) {
    size_t min_len = 4;
    size_t max_len = 16;

    for (size_t i = 0; i < payload_len; ++i) {
        for (size_t len = min_len; len <= max_len && (i + len) <= payload_len; ++len) {
            const uint8_t* chunk = payload + i;
            ...

size_t max_len = 16; - Natürlich kann man den Wert auf 32 erhöhen, ABER was passiert dann?

• Erhöhte CPU-Last: Der Algorithmus prüft Text mithilfe eines gleitenden Fensters. Eine Erhöhung der Fensterlänge von 16 auf 32 erhöht die Anzahl der Kombinationen (Teilstrings unterschiedlicher Länge von 4 bis 32) für jeden Textabschnitt erheblich. Das Modul muss daher mehr Iterationen in seinen Prüfschleifen durchführen.
• Bei längeren Mustern fügt der Bloom-Filter deutlich mehr Teilzeichenketten hinzu (alle möglichen Präfixe und Abschnitte mit einer Länge von 4 bis 32 Zeichen). Dadurch wird die Bitmap des Filters schneller gefüllt, was die Rate falsch positiver Ergebnisse leicht erhöhen kann. Bei den aktuellen Wahrscheinlichkeitseinstellungen ist dies jedoch nicht kritisch.

Empfehlung

Wenn Sie mit langen Mustern arbeiten möchten:

Wenn Sie `max_len` erhöhen, vermeiden Sie unnötig hohe Werte (z. B. `max_len = 256` für kurze Anfragen). Am besten setzen Sie `max_len` auf die tatsächliche maximale Länge Ihrer längsten Signaturen (z. B. 32 oder 48), um ein ausgewogenes Verhältnis zwischen Sicherheit und Nginx-Performance zu erzielen.

Wenn Sie Geschwindigkeit und Stabilität wünschen:

Halten Sie Ihre Muster einfach kürzer, das ist bei DPI durchaus möglich. Behalten Sie Ihre access.log-Datei im Auge und erstellen Sie gute Muster.

if ($request_uri ~* "\?") {
        return 403;
}

if ($args) {
        return 403;
}