Potential vulnerabilities of some Snort regexes

[Asiri Rathnayake <asiri.rathnayake () gmail com>]

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

------------------------------------------------------------------------------
Master Java SE, Java EE, Eclipse, Spring, Hibernate, JavaScript, jQuery
and much more. Keep your Java skills current with LearnJavaNow -
200+ hours of step-by-step video tutorials by Java experts.
SALE $49.99 this month only -- learn more at:
http://p.sf.net/sfu/learnmore_122612

_______________________________________________
Snort-devel mailing list
Snort-devel () lists sourceforge net
https://lists.sourceforge.net/lists/listinfo/snort-devel
Archive:
http://sourceforge.net/mailarchive/forum.php?forum_name=snort-devel

Please visit http://blog.snort.org for the latest news about Snort!