Regular Expression Matching using Bit Vector Automata
summary
Presents a new automaton model called NBVA that simulates nondeterministic counter automata by manipulating per-state bit vectors, using rotations, single-bit shifts and a resizable circular n-bit array so per-symbol work is constant-time independent of the repetition bound. Implements the algorithms in Rust as BVA-Scan, uses bit-parallel CPU operations, and evaluates on SNORT, bioinformatics and malware workloads against PCRE, re2 and CA, reporting about 10x speedup on average and matching correctness.
AI-written summary · about
chapters (9)
- 0:00Regex matching with bit vectors
- 2:09Classical regex techniques
- 4:16Counters for bounded repetition
- 7:11From counters to bit vectors
- 9:00Bit vector algorithm
- 12:40BVA-SCAN implementation
- 15:12Benchmarks and results
- 15:53Summary and conclusion
- 16:18Q&A
related talks
14mRegex Matching with Counting-Set Automata
21mEfficient Matching of Regular Expressions with Lookaround Assertions
51mRegular Expressions in C++, Present and Future
16mCertified Decision Procedures for Width-Independent Bitvector Predicates
19mDerivative Based Nonbacktracking Real-World Regex Matching with Backtracking Semantics
37mAll About Regular Expressions
13mInteractive Bit Vector Reasoning using Verified Bitblasting
29mVerified and Efficient Matching of Regular Expressions with Lookaround