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.
Methodology
The researchers developed a four-stage workflow to identify and verify vulnerabilities in live web services:
- Regex Collection: The team crawled 1,000 popular domains for HTML
patternattributes and analyzed 475 API domains via OpenAPI specifications. - Static Analysis: Using tools like
vuln-regex-detector, they identified "super-linear" regexes—those exhibiting worst-case time complexity. - 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.
- 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