Problem
daemon/scanner.c uses a linear scan: for each pattern in the database, it slides byte-by-byte across the target buffer. Complexity is O(n * m * p) where n = buffer size, m = pattern length, p = pattern count.
Current signature count (~5 rules in signatures/default.sigs) makes this irrelevant. But if the signature database grows to hundreds or thousands of rules (realistic for a production anti-cheat), scan time scales linearly with rule count per periodic check cycle.
Proposal
Replace with Aho-Corasick automaton:
- Build the automaton once at signature load time
- Single pass over the buffer matches all patterns simultaneously: O(n + matches)
- Wildcard bytes (
??) need special handling — either expand to multiple patterns or use a hybrid approach (AC for fixed prefixes, linear verify for wildcard positions)
Constraints
- Must preserve existing
owl_sig_db API (init, add, scan)
- 17 scanner tests must still pass
- No external library dependency (embed or implement)
Acceptance
make -C tests test_scanner && ./tests/test_scanner — 17/17 pass- Benchmark: scan time independent of pattern count for fixed buffer size
Problem
daemon/scanner.cuses a linear scan: for each pattern in the database, it slides byte-by-byte across the target buffer. Complexity is O(n * m * p) where n = buffer size, m = pattern length, p = pattern count.Current signature count (~5 rules in
signatures/default.sigs) makes this irrelevant. But if the signature database grows to hundreds or thousands of rules (realistic for a production anti-cheat), scan time scales linearly with rule count per periodic check cycle.Proposal
Replace with Aho-Corasick automaton:
??) need special handling — either expand to multiple patterns or use a hybrid approach (AC for fixed prefixes, linear verify for wildcard positions)Constraints
owl_sig_dbAPI (init, add, scan)Acceptance
make -C tests test_scanner && ./tests/test_scanner— 17/17 pass