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']}] на байте {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 <iostream>
#include <vector>
#include <cmath>
#include <cstring>

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

// ==========================================
// 1. C++ Bloom Filter (L1 Cache-Friendly)
// ==========================================
class FastBloomFilter {
private:
    std::vector<uint8_t> bit_array;
    size_t size_bits;
    size_t num_hashes;

public:
    FastBloomFilter(size_t expected_elements = 50000, float fp_rate = 0.001) {
        size_bits = static_cast<size_t>(-(expected_elements * std::log(fp_rate)) / (std::log(2) * std::log(2)));
        num_hashes = static_cast<size_t>((size_bits / expected_elements) * std::log(2));
        bit_array.resize((size_bits + 7) / 8, 0);
    }

    void add(const uint8_t* data, size_t len) {
        size_t hash = ngx_hash_key((u_char*)data, len);
        for (size_t i = 0; i < num_hashes; ++i) {
            size_t bit_idx = (hash + i * (hash >> 3)) % size_bits;
            bit_array[bit_idx >> 3] |= (1 << (bit_idx & 7));
        }
    }

    bool contains(const uint8_t* data, size_t len) const {
        size_t hash = ngx_hash_key((u_char*)data, len);
        for (size_t i = 0; i < num_hashes; ++i) {
            size_t bit_idx = (hash + i * (hash >> 3)) % size_bits;
            if (!(bit_array[bit_idx >> 3] & (1 << (bit_idx & 7)))) {
                return false;
            }
        }
        return true;
    }
};

// ==========================================
// 2. Ternary Search Tree (TST)
// ==========================================
struct TSTNode {
    uint8_t byte;
    TSTNode* left = nullptr;
    TSTNode* mid = nullptr;
    TSTNode* right = nullptr;
    int rule_id = -1;

    TSTNode(uint8_t b) : byte(b) {}
};

class FlatTrieDPI {
public:
    TSTNode* root = nullptr;

    void insert(const uint8_t* pattern, size_t len, int rule_id) {
        root = _insert(root, pattern, len, 0, rule_id);
    }

    int match(const uint8_t* pattern, size_t len) const {
        TSTNode* curr = root;
        size_t idx = 0;
        while (curr && idx < len) {
            uint8_t b = pattern[idx];
            if (b < curr->byte) {
                curr = curr->left;
            } else if (b > curr->byte) {
                curr = curr->right;
            } else {
                if (idx == len - 1) return curr->rule_id;
                curr = curr->mid;
                idx++;
            }
        }
        return -1;
    }

private:
    TSTNode* _insert(TSTNode* node, const uint8_t* pattern, size_t len, size_t idx, int rule_id) {
        uint8_t b = pattern[idx];
        if (!node) node = new TSTNode(b);

        if (b < node->byte) {
            node->left = _insert(node->left, pattern, len, idx, rule_id);
        } else if (b > node->byte) {
            node->right = _insert(node->right, pattern, len, idx, rule_id);
        } else if (idx < len - 1) {
            node->mid = _insert(node->mid, pattern, len, idx + 1, rule_id);
        } else {
            node->rule_id = rule_id;
        }
        return node;
    }
};

// ==========================================
// 3. Nginx-Regel- und Konfigurationsstruktur
// ==========================================
typedef struct {
    ngx_str_str_t rule; // key: pattern/string, value: rule_id string
} ngx_dpi_rule_entry_t;

typedef struct {
    ngx_flag_t enable;
    ngx_array_t *patterns; //Angriffssignaturen (URI/Query/Body)
    ngx_array_t *user_agents; // Fehlerhafte User-Agent-Signaturen
    FastBloomFilter *bloom;
    FlatTrieDPI *tst;
} ngx_http_dpi_loc_conf_t;

extern ngx_module_t ngx_http_dpi_module;

// Hilfspufferinspektionsfunktion über Bloom-Filter + TST
static int inspect_buffer(FastBloomFilter* bloom, FlatTrieDPI* tst, const uint8_t* payload, size_t payload_len) {
    if (!bloom || !tst || payload_len == 0) return -1;

    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;

            if (!bloom->contains(chunk, len)) {
                continue;
            }

            int rule_id = tst->match(chunk, len);
            if (rule_id != -1) {
                return rule_id;
            }
        }
    }
    return -1;
}

// ==========================================
// 4. ACCESS-Phasenhandler (Haupthandler)
// ==========================================
static ngx_int_t ngx_http_dpi_handler(ngx_http_request_t *r) {
    ngx_http_dpi_loc_conf_t *lcf = (ngx_http_dpi_loc_conf_t*) ngx_http_get_module_loc_conf(r, ngx_http_dpi_module);

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

    // 1. Validierung einer URI / Query String
    if (r->unparsed_uri.len > 0 && r->unparsed_uri.data != NULL) {
        int uri_rule_id = inspect_buffer(lcf->bloom, lcf->tst, r->unparsed_uri.data, r->unparsed_uri.len);
        if (uri_rule_id != -1) {
            ngx_log_error(NGX_LOG_WARN, r->connection->log, 0,
                          "[DPI Module] Threat detected in URI! Rule ID: %d, URI: %V",
                          uri_rule_id, &r->unparsed_uri);
            return NGX_HTTP_FORBIDDEN;
        }
    }

    // 2. Validierung einer User-Agent
    if (r->headers_in.user_agent != NULL && r->headers_in.user_agent->value.len > 0) {
        u_char *ua_data = r->headers_in.user_agent->value.data;
        size_t ua_len = r->headers_in.user_agent->value.len;

        int ua_rule_id = inspect_buffer(lcf->bloom, lcf->tst, ua_data, ua_len);
        if (ua_rule_id != -1) {
            ngx_log_error(NGX_LOG_WARN, r->connection->log, 0,
                          "[DPI Module] Threat detected in User-Agent! Rule ID: %d, UA: %V",
                          ua_rule_id, &r->headers_in.user_agent->value);
            return NGX_HTTP_FORBIDDEN;
        }
    }

    return NGX_DECLINED;
}

// ==========================================
// 5. Nginx-Konfigurationsanweisungen analysieren
// ==========================================
static char *ngx_http_dpi_add_rule(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;

    ngx_dpi_rule_entry_t *entry;
    ngx_array_t **target_array = (cmd->name.data[10] == 'p') ? &lcf->patterns : &lcf->user_agents;

    if (*target_array == NULL) {
        *target_array = ngx_array_create(cf->pool, 10, sizeof(ngx_dpi_rule_entry_t));
        if (*target_array == NULL) return (char*) NGX_CONF_ERROR;
    }

    entry = (ngx_dpi_rule_entry_t*) ngx_array_push(*target_array);
    if (entry == NULL) return (char*) NGX_CONF_ERROR;

    entry->rule.key = value[1];   // Signaturzeichenfolge (z. B. "SELECT * FROM")
    entry->rule.value = value[2]; // Rule ID (Zum Beispiel: "101")

    return NGX_CONF_OK;
}

static void *ngx_http_dpi_create_loc_conf(ngx_conf_t *cf) {
    ngx_http_dpi_loc_conf_t *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->patterns = NULL;
    conf->user_agents = NULL;
    conf->bloom = NULL;
    conf->tst = NULL;

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

    // Wir kombinieren Regelarrays vom übergeordneten Block (server/http) mit dem lokalen Block (location).
    if (conf->patterns == NULL) conf->patterns = prev->patterns;
    if (conf->user_agents == NULL) conf->user_agents = prev->user_agents;

    // Initialisierung der Bloom + TST-Struktur aus den konfigurierten Regeln
    size_t total_rules = (conf->patterns ? conf->patterns->nelts : 0) +
                         (conf->user_agents ? conf->user_agents->nelts : 0);

    if (conf->enable && total_rules > 0) {
        conf->bloom = new FastBloomFilter(total_rules * 10, 0.001);
        conf->tst = new FlatTrieDPI();

        auto compile_array = [&](ngx_array_t* arr) {
            if (!arr) return;
            ngx_dpi_rule_entry_t *entries = (ngx_dpi_rule_entry_t*) arr->elts;
            for (ngx_uint_t i = 0; i < arr->nelts; i++) {
                int rule_id = ngx_atoi(entries[i].rule.value.data, entries[i].rule.value.len);
                if (rule_id == NGX_ERROR) rule_id = 999;

                const uint8_t* pattern = entries[i].rule.key.data;
                size_t len = entries[i].rule.key.len;

                conf->tst->insert(pattern, len, rule_id);
                for (size_t k = 4; k <= len; ++k) {
                    conf->bloom->add(pattern, k);
                }
            }
        };

        compile_array(conf->patterns);
        compile_array(conf->user_agents);
    }

    return NGX_CONF_OK;
}

static ngx_int_t ngx_http_dpi_init(ngx_conf_t *cf) {
    ngx_http_core_main_conf_t *cmcf = (ngx_http_core_main_conf_t*) ngx_http_conf_get_module_main_conf(cf, ngx_http_core_module);
    ngx_http_handler_pt *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;
}

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,
        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_add_rule,
        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_add_rule,
        NGX_HTTP_LOC_CONF_OFFSET,
        0,
        NULL
    },
    ngx_null_command
};

static ngx_http_module_t ngx_http_dpi_module_ctx = {
    NULL, ngx_http_dpi_init, NULL, NULL, NULL, NULL,
    ngx_http_dpi_create_loc_conf, ngx_http_dpi_merge_loc_conf
};

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

2. Konfiguration (config)

Eine Datei namens config im selben Ordner:

ngx_addon_name=ngx_http_dpi_module
NGX_ADDON_SRCS="$NGX_ADDON_SRCS $ngx_addon_dir/ngx_http_dpi_module.cpp"
# Verbindung des C++-Compilers

HTTP_MODULES="$HTTP_MODULES ngx_http_dpi_module"
     

3a. Wie man kompiliert und verbindet

Nginx mit dem Modul erstellen:

./configure --add-module=/path/to/your/dpi_module_folder --with-ld-opt="-lstdc++"
make -j$(nproc)
sudo make install
     

Einrichtung in nginx.conf:

http {
    # 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;

    server {
        listen 80;
        server_name example.com;

        # Aktivieren den DPI-Inspektor für diesen Server.
        dpi_inspect on;

        # Sie können eine spezifische Regel nur für einen bestimmten location hinzufügen
        location /api/ {
            dpi_block_ua "curl/" 301;
            proxy_pass http://127.0.0.1:5000;
        }

        location / {
            proxy_pass http://127.0.0.1:5000;
        }
    }
}
     

3b. Wie man kompiliert und verbindet

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.:

# 1. 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

# 2. Wir konfigurieren die Quellen, indem wir unser Modul als dynamisch angeben (--add-dynamic-module)
./configure --with-compat --add-dynamic-module=/path/to/your/dpi_module_folder --with-ld-opt="-lstdc++"

# 3. Wir kompilieren NUR das Modul (die Ausgabe ist eine .so-Datei).
make modules
     

Die fertige Moduldatei befindet sich im Ordner: objs/ngx_http_dpi_module.so

Verbindung in nginx.conf:

Danach müssen Sie Nginx nie wieder neu kompilieren – legen Sie einfach die .so-Datei in das Nginx-Modulverzeichnis und fügen Sie sie oben in die Hauptkonfigurationsdatei ein.

# Aktivieren Sie das dynamische Modul ganz am Anfang der nginx.conf (vor dem http-Block).
load_module modules/ngx_http_dpi_module.so;

http {
    # 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;

    server {
        listen 80;
        server_name example.com;

        # Aktivieren Sie den DPI-Inspektor für diesen Server.
        dpi_inspect on;

        # Sie können eine spezifische Regel nur für einen bestimmten location hinzufügen.
        location /api/ {
            dpi_block_ua "curl/" 301;
            proxy_pass http://127.0.0.1:5000;
        }

        location / {
            proxy_pass http://127.0.0.1:5000;
        }
    }
}