Eliminating Regex-based Denial of Service

Principal Investigator: Jamie Davis

Regexes are implemented with exponential worst-case time complexity. When used for input processing, slow regexes comprise a denial of service vector. Researchers have reported that thousands of major websites are vulnerable. This project is investigating how best to discover and eliminate these vulnerabilities. We conduct empirical work to measure vulnerability incidence in practice. We propose novel algorithms with provable security guarantees. We are exploring their adoption in production-grade regex engines.

Personnel

Other PIs: Dongyoon Lee (Stony Brook University)

Students: Berk Cakar (PhD student) Charles Sale (MSc student)

Representative Publications

• Testing Regex Generalizability And Its Implications: A Large-Scale Many-Language Measurement Study. Davis, Moyer, Kazerouni, and Lee. ASE 2019.

• Improving Developers’ Understanding of Regex Denial of Service Tools through Anti-Patterns and Fix Strategies.
  Hassan, Aamir, Lee, Davis, and Servant.
  Proceedings of the 44th IEEE Symposium on Security and Privacy (IEEE S&P) 2023.

• Exploiting Input Sanitization for Regex Denial of Service. Barlas, Du, and Davis. ICSE 2022.

• Testing Regex Generalizability And Its Implications: A Large-Scale Many-Language Measurement Study. Davis, Moyer, Kazerouni, and Lee. ASE 2019.

• Testing Regex Generalizability And Its Implications: A Large-Scale Many-Language Measurement Study. Davis, Moyer, Kazerouni, and Lee. ASE 2019.A Sense of Time for JavaScript and Node.js: First-Class Timeouts as a Cure for Event Handler Poisoning.
  Davis, Williamson, and Lee.
  USENIX Security 2018.
     

• Regexes are Hard: Decision-making, Difficulties, and Risks in Programming Regular Expressions. Michael, Donohue, Davis, Lee, and Servant. ASE 2019.

• Using Selective Memoization to Defeat Regular Expression Denial of Service (ReDoS). Davis, Servant, and Lee. IEEE S&P 2021.
  

• Why Aren’t Regular Expressions a Lingua Franca? An Empirical Study on the Re-use and Portability of Regular Expressions. Davis, Michael, Coghlan, Servant, and Lee. ESEC/FSE 2019.

• SoK: A Literature and Engineering Review of Regular Expression Denial of Service.
  Bhuiyan, Cakar, Burmane, Davis, and Staicu.
  arXiv 2024.

Keywords: application-level vulnerabilities, denial of service, regular expressions, Web security