Exploiting Input Sanitization for Regex Denial of Service

Efe Barlas, Xin Du, James C. Davis

Abstract

Regular Expression Denial of Service (ReDoS) occurs when a regex engine takes excessive time to process a specially crafted input string. While typically requiring "white-box" code access to detect, this paper presents a black-box methodology based on the Consistent Sanitization Assumption: the idea that client-side validation rules mirror server-side logic. By analyzing regexes exposed in HTML and API specifications, we identified and confirmed ReDoS vulnerabilities in major services like Microsoft and Amazon.

The ReDoS Challenge in Web Services

ReDoS is a known threat that has caused major outages at platforms like Stack Overflow and Cloudflare. However, identifying these vulnerabilities from the outside is challenging. This research addresses whether web services inadvertently hand attackers the "blueprints" for ReDoS by publishing their sanitization logic to the client to improve usability.

A sign-in form demonstrating how regexes are exposed in HTML attributes and JavaScript for client-side validation.

Methodology

The researchers developed a four-stage workflow to identify and verify vulnerabilities in live web services:

The research methodology workflow, covering regex collection, analysis, probing, and disclosure.
  1. Regex Collection: The team crawled 1,000 popular domains for HTML pattern attributes and analyzed 475 API domains via OpenAPI specifications.
  2. Static Analysis: Using tools like vuln-regex-detector, they identified "super-linear" regexes—those exhibiting worst-case time complexity.
  3. Ethical Probing: They performed "treatment vs. control" experiments by sending "probe" strings (designed to trigger backtracking) and "control" strings to the service and measuring response time deviations.
  4. Responsible Disclosure: Confirmed vulnerabilities were reported to vendors, and a dataset of 1,850 unique sanitization regexes was released to the research community.

Key Insights: The API/HTML Divide

A critical discovery was that traditional HTML forms are relatively safe, often reusing simple, well-vetted regexes. In contrast, API specifications are a "minefield," containing a vast variety of complex, custom regexes. Furthermore, API code-generation tools like swagger-codegen often produce server-side code that defaults to unsafe, backtracking regex engines, effectively "baking in" ReDoS risks for developers.

Results and Real-World Impact

The study found that 355 services publish regexes, with 17 publishing demonstrably unsafe ones. Black-box probing confirmed ReDoS vulnerabilities in 6 major domains (15 subdomains). Following disclosure, both Microsoft and Amazon Web Services patched their services. Additionally, the authors contributed a patch to the ajv library, a major Node.js validation tool, allowing developers to opt into the safe re2 engine.

Limitations

The methodology is limited to regexes exposed to the client; "hidden" regexes in deep business logic remain invisible. Additionally, ethical constraints limited probes to a 5-second response time increase, likely under-reporting the true severity of some vulnerabilities.

Summary updated

BibTeX
@inproceedings{barlas2022exploiting,
  author = {Efe Barlas and Xin Du and James C. Davis},
  title = {{Exploiting Input Sanitization for Regex Denial of Service}},
  booktitle = {ICSE},
  year = {2022},
  url = {https://openreview.net/forum?id=oCPxaFErcQCy},
}
Figure