idea: optimize regex/substring matching using literal prefix and Aho-Corasick
- Dominant language
- Python
- Stars
- 6.2k
- Forks
- 726
- Avg merge
- 11d 11h
- Merged PRs (30d)
- 7
Description
today we have a bunch of rules that rely on substring features, sometimes many of them, like [compiled-with-rust](https://github.com/mandiant/capa-rules/blob/be59710ad9d283d9e23e9ad6726b549061c3c0cf/compiler/rust/compiled-with-rust.yml). matching these features requires doing a regex match against every string encountered in the program, which we suspect is expensive.
to make this cheaper, we could introduce a filtering pass first:
when encountering a string feature, check the filter first to see if it might possibly match any regexes in any rule. only if that filter passes are the regexes run.
the filter might be implemented as: extract a prefix literal from the regex/substring, and then use Aho-Corasick automaton to check if the literal is present anywhere in the string. this should be very fast, much faster than repeatedly running regex against the string. from wikipedia:
> It is a kind of dictionary-matching [algorithm](https://en.wikipedia.org/wiki/Algorithm) that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all strings simultaneously. The [complexity](https://en.wikipedia.org/wiki/Time_complexity) of the algorithm is linear in the length of the strings plus the length of the searched text plus the number of output matches.
Contributor guide
Assessment
This issue has not been assessed yet.