Chipmunk: A Tool for Matching of Regular Expressions

Chipmunk: A Tool for Matching of Regular Expressions

Software

The tool allows efficient matching regular expressions (regexes) with bounded repetition using deterministic automata with registers - counting-sets automata (CsA). The CsA can hold sets of bounded integers and can be manipulated by a limited portfolio of constant-time operations. Our experimental results confirm that deterministic CsAs produced from practical regexes with repetition are indeed vastly smaller than the corresponding DFAs. This prototype matcher based on CsA simulation handles practical regexes with repetition regardless of sizes of counter bounds. It easily copes with regexes with repetition where state-of-the-art matchers struggle.

The tool allows efficient matching regular expressions (regexes) with bounded repetition using deterministic automata with registers - counting-sets automata (CsA). The CsA can hold sets of bounded integers and can be manipulated by a limited portfolio of constant-time operations. Our experimental results confirm that deterministic CsAs produced from practical regexes with repetition are indeed vastly smaller than the corresponding DFAs. This prototype matcher based on CsA simulation handles practical regexes with repetition regardless of sizes of counter bounds. It easily copes with regexes with repetition where state-of-the-art matchers struggle.

regular expressions, pattern matching, security, counting-set automata

regular expressions, pattern matching, security, counting-set automata

Nástroj i dokumentaci lze získat na URL: http://www.fit.vutbr.cz/research/groups/verifit/tools/chipmunk/

K využití výsledku jiným subjektem je vždy nutné nabytí licence

https://www.fit.vut.cz/research/product/685/