mandiant / mandiant/capa

idea: optimize regex/substring matching using literal prefix and Aho-Corasick

Open
#3,073 8 comments 0 reactions 1 assignee Claimed by @corkamig View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.