Case study: Lucene index và ClamAV signature

TL;DR: Ba hệ thống, ba bài toán khác nhau nên ba lựa chọn khác nhau. ClamAV phải đối chiếu file với rất nhiều chữ ký virus, nên dựng một automaton Aho-Corasick và đọc file một lần thay vì chạy KMP từng chữ ký. GNU grep tìm một chuỗi trong file lớn bằng họ Boyer-Moore: so từ phải sang trái và nhảy cóc, nên phần lớn byte không bao giờ bị đọc. Lucene cần tra term trong từ điển khổng lồ, kể cả theo tiền tố, nên dùng FST (finite state transducer, một dạng trie nén) trong index của nó. Câu hỏi chọn nằm ở: bao nhiêu pattern, cố định hay đổi liên tục, có cần tìm theo tiền tố không.

Aho-Corasick, quét đồng thời nhiều chữ ký trong một lần đọc file

FST + inverted index, tra term nhanh trong tập document lớn

Phần A: ClamAV quét nhiều chữ ký thế nào?

1. Vấn đề: một file, rất nhiều chữ ký

ClamAV (Clam AntiVirus) là antivirus mã nguồn mở, hay chạy trong mail server và gateway. Cơ sở dữ liệu của nó gồm nhiều loại chữ ký: băm của cả file, và chữ ký theo nội dung (body-based) là những chuỗi byte đặc trưng của file nhiễm. Tài liệu ClamAV không công bố một con số tổng, nên bài này lấy 8 triệu chữ ký làm ví dụ minh hoạ để tính toán, không phải số đo. Cơ sở chữ ký đủ lớn để quét từng chữ ký một lượt trên mỗi file là không khả thi.

Phương án naive là chạy KMP cho từng chữ ký, tốn O(|file| × số chữ ký): với file 1 MB và 8 triệu chữ ký giả định, khoảng 8 × 10¹² phép so sánh.

Mã nguồn libclamav cho thấy ClamAV không dùng một thuật toán duy nhất. matcher-ac.c là bộ khớp Aho-Corasick: hàm cli_ac_addpatt thêm từng chữ ký vào trie, cli_ac_buildtrie (qua ac_maketrans) tính failure link bằng duyệt theo tầng, cli_ac_scanbuff đi trên trie theo từng byte. matcher-bm.c là một bộ khớp kiểu Boyer-Moore nhiều pattern, dùng bảng nhảy trên khối 3 byte và từ chối chữ ký ngắn hơn 3 byte. Ý của Aho-Corasick (đã học ở bài 05) là gom toàn bộ chữ ký vào một automaton rồi duyệt file đúng một lần: build tốn O(tổng độ dài chữ ký) một lần khi nạp database, quét tốn O(|file| + số lần khớp).

Hình là cấu trúc đó trên bốn pattern nhỏ; phần build và quét giống pseudocode ở bài 05.

2. Chữ ký có wildcard: cắt đoạn rồi kiểm lại khoảng cách

Chữ ký ClamAV không chỉ là chuỗi cố định. Chúng là chuỗi hex có wildcard và khoảng cách:

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

Trong matcher-ac.c, một chữ ký như vậy được xử lý như chữ ký nhiều phần (partial signature): trie chỉ khoá trên đoạn cố định, và khi một đoạn khớp, cli_ac_scanbuff kiểm tra thêm đoạn trước đó đã khớp chưa, với giới hạn khoảng cách mindist và maxdist giữa hai đoạn.

Automaton không hiểu wildcard và cũng không cần hiểu: nó chỉ trả về vị trí các đoạn cố định. Phần {10-80} được kiểm sau, trên vài vị trí tìm được chứ không phải trên cả file.

Thử ngẫmmột chữ ký mới có 5 đoạn cố định xen kẽ thay vì 2. Bước kiểm khoảng cách sau khi automaton báo vị trí có còn rẻ như minh hoạ ở trên không?