[Snort-devel] Potential vulnerabilities of some Snort regexes

Asiri Rathnayake asiri.rathnayake at ...2499...
Wed Jan 16 09:29:37 EST 2013


Dear All,

I'm a PhD student from the University of Birmingham, UK. Me and my
supervisor are conducting research around the topics of string pattern
matching and parsing [1].

We recently developed a static analysis for detecting exponential runtime
vulnerabilities of (backtracking) regular expression matchers; the analysis
and the implementation is described in [2] (paper under review). As part of
the work, we executed our analyzer on the Snort PCRE regex set (after
extracting them from the rule files), and we found several exponential
runtime vulnerabilities in some of these expressions. The linked file
"snort_sample.txt" [3] details a sample of these vulnerabilities, for an
example, one entry reads:

=[2318]=
- Regex: /^SITE\s*(\w+\s*)+\x7c/smi
- Parse: Ok
- Kleene count: 6
+ Analysis: Completed
+ Vulnerable: Yes
  + Kleene: (\w+\s*)+
    - Prefix: SITE9
    - Pumpable: zz
    - Suffix: (The empty string)

This means that for the regular expression /^SITE\s*(\w+\s*)+\x7c/smi, an
attack string can be formed in the following manner:

SITE9zzzzzzzzzzzzzzzzzzzzzz... (many copies of "zz")

Usually, for prefix "w", pumpable "x" and suffix "z", the attack string is
formed by repeating the pumpable string "x" many times, as in:

wxxxxxxxxxxxxxxxxxxxxx...xxxxxz

The paper argues that the runtime of a backtracking regular expression
matcher would be exponential in the number of copies of "x". The full
analysis of Snort regexes is given in the linked file "snort.log" [4].

While we're confident about the analysis, we're not familiar with the Snort
internal workings; thus we do not know how many of these vulnerabilities
are actually exploitable. We thought of writing to you and getting your
opinion about the quality of the results reported.

The source code for the analyzer (written in OCaml) along with test data
sets and results can be found at [5] (also linked from the paper).

Any comments would be appreciated.

Best regards,

- Asiri

[1] http://www.cs.bham.ac.uk/~hxt/research/parsing-regular-expressions.shtml

[2] http://arxiv.org/abs/1301.0849

[3] https://dl.dropbox.com/u/12212624/RXXR/Results/snort_sample.txt

[4] https://dl.dropbox.com/u/12212624/RXXR/Results/snort.log

[5] http://www.cs.bham.ac.uk/~hxt/research/rxxr.shtml
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.snort.org/pipermail/snort-devel/attachments/20130116/2c35cf03/attachment.html>


More information about the Snort-devel mailing list