RXXR2 regular expression static analyzer

RXXR2 is a refined version of the earlier analysis RXXR presented in our NSS 2013 paper, and supersedes it.

Theoretical background

The analysis and the correctness of RXXR2 are presented in this paper: Static Analysis for Regular Expression Exponential Runtime via Substructural Logics

Downloading the code

The source code for the analyser is available from this page. The download link is at the bottom, below the legal text.

Building requires: ocamllex, ocamlyacc, ocamlc. Execute the build script:

./build.sh

This should produce an executable named scan.bin inside the source directory.

Testing

File mode:

./scan.bin -i <input_file>

Each line on the file is interpreted as a pattern of the form /REGEX/MODS. Empty lines and lines beginning with a # symbol are ignored. Most common pattern syntaxes are supported (Java, PCRE etc.).

Interractive mode:

./scan.bin

Then enter patterns into the terminal (NOTE:- in this mode, the analyser performs an exhaustive search).

Test data

The snort data set is available here.

The regexlib data set is available here.