GadgetCA: A Tool for Generating of ReDoS Attacks

  1. News
  2. About
  3. Source Code
  4. Conference Papers
  5. Benchmarks
  6. Contact
  7. Related Papers
  8. Acknowledgement

News

February, 2022:The paper about GadgetCA has been accepted to appear at USENIX Security'22.


About

The tool allows to generate ReDoS attacks for automata-based matchers. It is the first generator capable of attacking the automata-based matchers using bounded repetition. It is based on counting-set automata (CsA) which are small and can be constructed faster than deterministic counting automata (DFA).

This is a common research with Microsoft Research (Margus Veanes).



Source Code

https://pajda.fit.vutbr.cz/ituronova/countingautomata-generator


Conference Papers

1.
TURONOVA, L.; HOLIK, L.; HOMOLIAK, I.; LENGAL, O.; VOJNAR, T.; VEANES, M. Counting in Regexes Considered Harmful: Exposing ReDoS Vulnerability of Nonbacktracking Matchers. Proceedings of USENIX Security, 2022.


Benchmarks

The regexes used for this experiment were selected:

1.
from the database of over 500,000 real-world regexes coming from an Internet-wide analysis of regexes collected from over 190,000 software projects from here;
2.
from databases of regexes used by network intrusion detection systems (NIDSes), in particular, Snort, Bro, Sagan, and, moreover, the academic papers;
3.
the RegExLib database of regexes from here; and
4.
industrial regexes originally used for security purposes from here.


The original set of files can be retrieved from repository here.

Contact

If you have further questions, do not hesitate to contact authors:

[1]
HOLIK, L.; LENGAL, O.; TURONOVA, L.; VOJNAR, T.; SAARIKIVI, O.; VEANES, M. Succinct Determinisation of Counting Automata via Sphere Construction. In In Proc. of 17th Asian Symposium on Programming Languages and Systems - APLAS'19. Lecture Notes in Computer Science. Berlin Heidelberg: Springer Verlag, 2019. p. 468-489. ISSN: 0302-9743.
[2]
TURONOVA, L., HOLIK, L.; LENGAL, O.; VOJNAR, T.; VEANES, M. Regex Matching with Counting-Set Automata. Proceedings of the ACM on Programming Languages, 2020, vol. 4, no. 11, p. 1-30. ISSN: 2475-1421.

Acknowledgements

This work is supported by ERC CZ project LL1908, the Czech Science Foundation project 20-07487S, and FIT BUT internal project FIT-S-20-6427.