Case study — Lucene index & ClamAV signature

TL;DR: ClamAV phải đối chiếu file người dùng tải về với hơn 8 triệu chữ ký virus — nếu dùng KMP chạy từng chữ ký, mỗi file cần hàng triệu lần duyệt. Aho-Corasick xây automaton một lần từ toàn bộ chữ ký, duyệt file một lần duy nhất và phát hiện mọi chữ ký khớp. Lucene giải quyết bài toán khác nhưng liên quan: với hàng triệu document, tra cứu term cần cấu trúc nhanh hơn hash table — FST (Finite State Transducer) nén toàn bộ term dictionary vào bộ nhớ cho O(|term|) lookup. Hai hệ thống dùng hai cấu trúc khác nhau vì bài toán khác nhau: ClamAV cần quét đồng thời nhiều pattern cố định, Lucene cần lookup nhanh trong tập term khổng lồ.

Aho-Corasick — quét đồng thời hơn 8 triệu chữ ký trong một lần đọc file

FST + inverted index — lookup term nhanh trong tập document khổng lồ

Phần A — ClamAV: Aho-Corasick cho multi-signature scanning

1. Vấn đề: 8 triệu chữ ký, mỗi file quét trong millisecond

ClamAV (Clam AntiVirus) là antivirus mã nguồn mở được dùng rộng rãi trong mail server và gateway. Cơ sở dữ liệu chữ ký virus của ClamAV chứa hơn 8 triệu signature (thực tế 2024-2025 đã vượt 10 triệu) — mỗi signature là một chuỗi byte đặc trưng xuất hiện trong file nhiễm virus.

Khi một file được tải qua mail server, ClamAV phải kiểm tra xem file đó có chứa bất kỳ signature nào không. Bài toán: tìm đồng thời nhiều pattern trong một text.

Phương án naive: chạy KMP cho từng signature → O(|file| × 8,000,000). Với file 1 MB và 8 triệu signature, đây là 8 × 10¹² phép so sánh — không thể thực hiện trong thời gian thực.

ClamAV thực tế phối hợp nhiều matcher — Aho-Corasick cho chữ ký đa mẫu (trọng tâm bài này), Boyer-Moore cho chữ ký đơn, hash table cho exact-match toàn file, và PCRE cho chữ ký dạng regex. Phần lõi quét đa mẫu — Aho-Corasick — giải bài toán bằng cách xây một automaton duy nhất từ toàn bộ tập signature, sau đó duyệt file một lần duy nhất:

• Build phase — O(tổng độ dài các signature): xây trie từ tất cả pattern, sau đó tính failure link cho mỗi node (giống lps của KMP nhưng trên cây).
• Search phase — O(|file| + số lần khớp): duyệt file một lần, automaton tự chuyển trạng thái theo từng byte đọc được.

2. Cấu trúc Aho-Corasick — trie + failure link

Cho tập pattern {"he", "she", "his", "hers"}:

graph TD
    ROOT["root (0)"] -- "h" --> H["h (1)"]
    ROOT -- "s" --> S["s (5)"]
    H -- "e" --> HE["he (2) *"]
    H -- "i" --> HI["hi (3)"]
    HE -- "r" --> HER["her (7)"]
    HER -- "s" --> HERS["hers (8) *"]
    HI -- "s" --> HIS["his (4) *"]
    S -- "h" --> SH["sh (6)"]
    SH -- "e" --> SHE["she (9) *"]

Node có dấu * là node chấp nhận (output node) — khi automaton đến đây, một pattern đã được tìm thấy.

Failure link — tương tự failure function của KMP — chỉ đến node dài nhất là suffix của đường dẫn đến node hiện tại mà đồng thời cũng là prefix trong trie. Ví dụ: failure link của node she (path s-h-e) trỏ đến node he (path h-e) vì "he" là suffix dài nhất của "she" có trong trie.

function buildAhoCorasick(patterns):
    -- Bước 1: xây trie từ tất cả pattern
    root <- newNode()
    for each pattern P trong patterns:
        node <- root
        for each char c trong P:
            if node không có child c:
                node.children[c] <- newNode()
            node <- node.children[c]
        node.isOutput <- true
        node.outputPatterns.add(P)

    -- Bước 2: tính failure link bằng BFS
    Queue Q <- []
    for each child v của root:
        v.failure <- root
        Q.enqueue(v)

    while Q không rỗng:
        u <- Q.dequeue()
        for each (char c, child v) của u:
            -- failure của v = state đạt được khi follow failure link của u và đọc c
            f <- u.failure
            while f != root và f không có child c:
                f <- f.failure
            v.failure <- f.children[c] nếu có, không thì root
            -- Output link: kế thừa output từ failure chain
            v.outputLink <- v.failure nếu v.failure.isOutput, không thì v.failure.outputLink
            Q.enqueue(v)

// Time build: O(tổng_m × |alphabet|)  Space: O(tổng_m × |alphabet|)

3. Search phase — một lần duyệt file

function ahoCorasickSearch(text, root):
    results <- []
    state <- root

    for i from 0 to text.length - 1:
        c <- text[i]
        -- Chuyển trạng thái: follow failure link cho đến khi tìm được transition hợp lệ
        while state != root và state không có child c:
            state <- state.failure
        if state có child c:
            state <- state.children[c]
        -- Thu thập output: node hiện tại và toàn bộ output link chain
        node <- state
        while node != null:
            if node.isOutput:
                for each pattern P trong node.outputPatterns:
                    results.append((i - P.length + 1, P))
            node <- node.outputLink

    return results
// Time: O(n + tổng_m + k)  -- k = tổng số lần khớp

4. ClamAV mở rộng Aho-Corasick cho byte signature

Signature virus trong ClamAV không phải chuỗi ASCII đơn giản — chúng là chuỗi hex byte với wildcard và range:

-- Ví dụ ClamAV signature (dạng đơn giản):
-- "4D5A{10-80}50450000" nghĩa là:
--   4D 5A (MZ header của PE file)
--   rồi 10 đến 80 byte bất kỳ
--   rồi 50 45 00 00 (PE signature)

ClamAV xử lý bằng cách tách signature thành các segment cố định (phần không có wildcard), xây Aho-Corasick trên các segment, rồi khi tìm thấy segment, kiểm tra thêm điều kiện wildcard và vị trí tương đối.

graph LR
    FILE["File<br/>cần quét"] -- "1 lần duyệt" --> AC["Automaton<br/>Aho-Corasick<br/>(8M+ signature)"]
    AC -- "match segment?" --> VERIFY["Verify wildcard\n+ offset"]
    VERIFY -- "confirmed" --> ALERT["Báo virus tìm thấy"]
    VERIFY -- "spurious" --> CONT["Tiếp tục"]

So sánh trực tiếp:

Phần B — Lucene: FST cho term dictionary

5. Vấn đề: term dictionary của search engine

Apache Lucene là thư viện search engine nền tảng của Elasticsearch, Solr và nhiều công cụ tìm kiếm khác. Lucene index hoạt động theo mô hình inverted index: với mỗi term (từ), lưu danh sách document chứa term đó (posting list).

Để tìm kiếm term "algorithm" trong index chứa 100 triệu document:

1. Tra term dictionary để tìm term "algorithm" và lấy offset của posting list.
2. Đọc posting list — danh sách document ID chứa term.

Term dictionary của Lucene chứa hàng chục triệu term phân biệt. Cần cấu trúc cho phép:

• Tra cứu chính xác (exact match) nhanh.
• Prefix search (tất cả term bắt đầu bằng "algo...").
• Tốn ít RAM (dictionary nằm on-disk, một phần được memory-map).

6. FST — Finite State Transducer cho term dictionary

Lucene dùng FST (Finite State Transducer) — một dạng automaton đặc biệt có thể vừa nhận diện chuỗi vừa map chuỗi sang giá trị. FST là trie được nén tối đa: các state được merge khi chúng có cùng "suffix behaviour".

Ví dụ trie naïve của {"mop", "moth", "pop", "star", "stop", "top"} có 18 node (kể cả root). FST nén xuống còn 10 state bằng cách nhận ra "mop", "pop", "top" có cùng suffix "op" và "stop" cũng kết thúc bằng "op" — các nhánh chia sẻ state S2 và S3.

graph LR
    S0["(0)"] -- "m" --> S1["(1)"]
    S0 -- "p" --> S1
    S0 -- "t" --> S1
    S0 -- "s" --> S6["(6)"]
    S1 -- "o" --> S2["(2)"]
    S2 -- "p" --> S3["(3) *"]
    S2 -- "t" --> S4["(4)"]
    S4 -- "h" --> S5["(5) *"]
    S6 -- "t" --> S7["(7)"]
    S7 -- "a" --> S8["(8)"]
    S8 -- "r" --> S9["(9) *"]
    S7 -- "o" --> S2

Trong FST thực tế của Lucene, mỗi transition cũng mang một "output" (giá trị tích luỹ) — đường đi từ state đầu đến state chấp nhận cho biết offset của posting list trong file .tim (term index).

Tại sao không dùng hash table? Hash table cho O(1) exact lookup nhưng:

• Không hỗ trợ prefix search (tất cả term bắt đầu bằng "algo...").
• Không hỗ trợ range query (tất cả term giữa "aab" và "aaz").
• Tốn nhiều bộ nhớ hơn FST đáng kể (hash table phải lưu cả key string, còn FST chia sẻ prefix/suffix nên nén rất chặt).

FST với 100 triệu term chỉ chiếm cỡ 150-200 MB RAM — đủ nhỏ để memory-map hoặc giữ trong heap, lookup O(|term|) với constant nhỏ, mà vẫn hỗ trợ prefix/range query.

7. Posting list — bên dưới term dictionary

Khi đã tra được term trong FST, Lucene đọc posting list — danh sách (docID, tf, positions[]) trong file .doc:

term "algorithm" → posting list:
  doc 42:  tf=3, positions=[12, 47, 103]
  doc 157: tf=1, positions=[8]
  doc 891: tf=5, positions=[1, 4, 7, 11, 23]
  ...

Lucene nén posting list bằng delta encoding (lưu hiệu docID thay vì docID tuyệt đối, vì delta thường nhỏ) + VByte encoding (số nguyên nhỏ dùng ít byte hơn).

Chi tiết về inverted index, scoring (TF-IDF, BM25), và ranking sẽ được đào sâu trong Module 6 — Search engine. Module này chỉ chú trọng phần term lookup.

Vì sao chọn thuật toán nào

graph TD
    Q0["Bài toán string matching"] --> Q1{"Pattern cố định,\ntext thay đổi?"}
    Q1 -- "Có" --> Q2{"Số pattern?"}
    Q2 -- "1 pattern" --> KMP2["KMP — O(n+m)\ntất định, không spurious hit"]
    Q2 -- "Nhiều pattern\n(triệu)" --> AC2["Aho-Corasick — O(n+tổng_m+k)\nClamAV, IDS"]
    Q1 -- "Text cố định,\ntruy vấn thay đổi" --> Q3{"Cần prefix/range\nhay exact only?"}
    Q3 -- "Exact only" --> HT["Hash table — O(1) average"]
    Q3 -- "Prefix + range" --> FST2["FST/Trie — O(|term|)\nLucene, DNS"]
    Q1 -- "Cả hai thay đổi,\ncần fuzzy" --> Q4["Lucene BM25 scoring\n(Module 6)"]

Liên hệ các bài khác

• KMP: failure function là nền tảng trực tiếp của Aho-Corasick — failure link trên trie chính là lps đa mẫu. Đọc KMP trước khi đọc phần ClamAV sẽ giúp phần failure link dễ hiểu hơn nhiều.
• Aho-Corasick: bài concept đầy đủ về cấu trúc trie + failure link + output link. Case study này là ứng dụng thực tế của bài đó.
• Rabin-Karp: khi số pattern thay đổi liên tục (không cố định), Aho-Corasick không phù hợp vì phải rebuild — Rabin-Karp multi-pattern hoặc Bloom filter phù hợp hơn.
• Module 6 — Search engine (sắp ra): inverted index đầy đủ, BM25 scoring, shard và replica trong Elasticsearch — xây trực tiếp trên FST term dictionary giới thiệu ở đây.

Tự kiểm tra

Bài tiếp theo: Module 2 — Tổng kết & cheat sheet