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: Dharun Anandayuvaraj (PhD student) Charles Sale (Undergraduate)

Representative Publications

  • 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.

  • 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 ExpressionsDavis, Michael, Coghlan, Servant, and Lee. ESEC/FSE 2019.

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

  • Testing Regex Generalizability And Its Implications: A Large-Scale Many-Language Measurement StudyDavis, 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.
       

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