Inefficient Regular Expression Complexity

crmne/ruby_llm at commit fa6f279847d6d7027814539d9c0dfc3bbdfd2a83 contains a polynomial-time regular expression denial-of-service condition in RubyLLM::Utils.underscore on Ruby 3.1.x. A very long crafted class, agent, or tool name can cause excessive CPU consumption and a denial of service.Show less

CyberChef is a web app for encryption, encoding, compression, and data analysis. Prior to 11.3.0, CyberChef's pretty-recipe parser in src/core/Utils.mjs can exhaust client-side CPU when a malformed #recipe= URL fragment containing a large number of unmatched quote characters reaches Utils.parseRecipeConfig(). The function synchronously applies a complex global regular expression that may perform heavy backtracking before rejecting the input, causing the victim's browser tab to freeze during startup for seconds or longer. No code execution, data exfiltration, or privilege escalation occurs. This issue is fixed in version 11.3.0.Show less

Hono is a Web application framework that provides support for any JavaScript runtime. Prior to 4.12.34, the built-in CORS middleware, hono/cors, is vulnerable to a regular expression denial of service (ReDoS). During a preflight OPTIONS request, the middleware parses the attacker-controlled Access-Control-Request-Headers header using a whitespace-tolerant regular expression whose backtracking makes its running time quadratic in the input length. Because the header value is bounded only by the deployment's maximum HTTP header size, a single preflight carrying a long run of whitespace can consume seconds of CPU and block request processing. On runtimes that share one execution thread across requests, this stalls concurrent requests as well, and repeated requests can render the service unresponsive. This affects the default configuration, since the vulnerable path is reached whenever cors() is used with an unset or empty allowHeaders. Applications that set a non-empty allowHeaders are not affected. This issue is fixed in version 4.12.34.Show less

SvelteKit is a framework for rapidly developing robust, performant web applications using Svelte. Prior to 2.70.2, the content negotiation header parser used by SvelteKit's request handling (for headers such as Accept) uses a regular expression vulnerable to quadratic backtracking, so a maliciously crafted header value can cause excessive CPU consumption and degrade or deny service. Version 2.70.2 fixes the issue.Show less

pymdown-extensions is a collection of extensions for the Python Markdown library. In versions up to and including 11.0, four inline processors (caret, tilde, betterem, and magiclink) use regular expressions whose content groups can partition a run of delimiter characters in exponentially many ways, causing catastrophic backtracking. As a result, a single untrusted Markdown line under 50 bytes rendered with markdown.markdown() in each extension's default configuration drives the rendering thread into unbounded CPU usage that grows exponentially with input length, enabling an unauthenticated remote attacker who can submit Markdown to cause denial of service. The exposure is concrete for web applications that render user-supplied Markdown (comments, wikis, issue bodies, live preview), including any app using pymdownx.extra which bundles the vulnerable betterem default, as well as hosted docs/CI systems that build untrusted Markdown. The issue has been fixed in version 11.0.1.Show less

Inefficient Regular Expression Complexity vulnerability in the CSS scrubber in rrrene html_sanitize_ex allows an unauthenticated remote attacker to exhaust server CPU via a long CSS declaration in sanitized HTML. The declaration regex in HtmlSanitizeEx.Scrubber.CSS.scrub/1 matches the property name with an unbounded greedy [-\w]+ followed by a mandatory :, so a long run of word characters not followed by a colon makes the engine give back one character at a time and retry the colon at every start offset. The work is quadratic in the length of the run, and no length cap is applied to the CSS handed to the scrubber. An 80 KB <style> body costs roughly 2.4 seconds of scheduler time, so a few concurrent requests saturate the BEAM scheduler pool and make the application unresponsive. The impact is CPU exhaustion only. Nothing is read, modified or disclosed. This issue affects html_sanitize_ex: from 0.3.1 before 1.4.5 and from 1.5.0-rc.0 before 1.5.3.Show less

In OpenStack Swift through 2.38.0, the proxy server Accept header parser contains a regular expression vulnerable to catastrophic backtracking (ReDoS). The "qdtext" pattern (?:[^"]|\\.)* allows an unauthenticated remote attacker to send a crafted Accept header that causes exponential CPU consumption in the proxy worker. A payload of 32 backslash-character pairs exceeds 30 seconds of CPU time. No authentication is required. Repeated requests can exhaust all proxy worker threads, resulting in a complete denial of service.Show less

Open WebUI is an extensible, feature-rich, and user-friendly self-hosted AI platform. From 0.9.6 until 0.11.0, the built-in knowledge search path in backend/open_webui/tools/knowledge_fs.py and backend/open_webui/tools/builtin.py let a chat participant choose a pattern used to grep knowledge files. Patterns containing regex metacharacters were compiled with Python's backtracking re engine and run against every line of every reachable file with no time limit, so a crafted pattern such as (x|x)*y and one matching uploaded file line can pin one CPU core and block the event loop. This causes availability impact for every other user of the affected worker. This issue is fixed in 0.11.0.Show less

Open WebUI is an extensible, feature-rich, and user-friendly self-hosted AI platform. From 0.9.0 until 0.11.0, automation recurrence parsing in backend/open_webui/utils/automations.py anchored minutely and hourly rules at a fixed date of 2000-01-01 and then walked forward one interval at a time to find the next run. A single FREQ=MINUTELY rule enumerates roughly a quarter-century of occurrences synchronously on the event loop that also serves scheduler, HTTP, and WebSocket traffic, and the scheduler recomputes the next run for every claimed row on each poll. This causes availability impact for every other user of the instance. This issue is fixed in 0.11.0.Show less

A Regular Expression Denial of Service (ReDoS) vulnerability exists in Apache Superset versions 1.5.0 through 5.0.0. The vulnerability is located in the sql_parse.py component, specifically within the SQL_REGEX used for parsing SQL statements in the sqlparse library integration. The affected regular expression contains overlapping disjunctions that share a common outer quantifier. An authenticated attacker can exploit this by sending a maliciously crafted input string (specifically a long sequence of backslashes or similar characters) to endpoints that process SQL queries This issue affects Apache Superset: before 6.0.0. Users are recommended to upgrade to version 6.0.0, which fixes the issue.  Workarounds: ● WAF Rules: Implement Web Application Firewall (WAF) rules to detect and block requests containing excessively long sequences of backslashes or suspicious repeated patterns in the queries.extras.where parameter. ● Rate Limiting: Ensure strict rate limiting is applied to the /api/v1/chart/data endpoint to reduce the impact of potential attacks.Show less

Date::Manip versions through 7.00 for Perl allow CPU exhaustion via quadratic backtracking in the unanchored time substitution in _parse_time. _parse_time removes a time from anywhere in the string with the unanchored substitution `s/$timerx/ /`, where $timerx is an auto-generated alternation of time patterns reached through a leading `(?:$atrx|^|\s+)`. The engine therefore retries the match at every position of an interior whitespace run: at each start position the leading `\s+` consumes the rest of the run greedily, the time alternation fails because the run holds no digits, and the engine backtracks a space at a time across the run before advancing the start position, which is quadratic in the length of the run. No time need be present in the string for this to happen, only a long run of whitespace, and the parse time rises about fourfold for each doubling of the run: a few kilobytes of whitespace costs seconds of CPU per parse and tens of kilobytes costs minutes. Any caller that passes an untrusted string of unbounded length to ParseDate(), Date::Manip::Date->parse() or ->parse_time() can be made to spend unbounded CPU in a single parse, a denial of service.Show less

HAPI FHIR is a complete implementation of the HL7 FHIR standard for healthcare interoperability in Java. Prior to 6.9.9 and 6.9.4.2, all implementations of FHIRPathEngine accept arbitrary FHIRPath expressions and evaluate them without input validation, and the FHIRPath functions matches(), matchesFull(), and replaceMatches() pass user-controlled regular expressions to Java's Pattern.compile() and String.replaceAll() through an incomplete timeout utility. An attacker can send a resource containing an evil regex pattern that causes catastrophic backtracking, exhausting CPU resources and causing denial of service in the FHIR Validator HTTP endpoint and affected org.hl7.fhir.* modules. This issue is fixed in versions 6.9.9 and 6.9.4.2.Show less

JSONata is a JSON query and transformation language. Prior to 2.2.0 and 1.8.9, malicious non-matching inputs to the $toMillis function can cause superlinear backtracking in the ISO-8601 validation regex, leading to denial of service in applications that evaluate user-provided JSONata expressions. This issue is fixed in version 2.2.0 and 1.8.9.Show less

HTTP::Date versions before 6.08 for Perl allow CPU exhaustion via polynomial regex backtracking in parse_date. parse_date() matches the date string against a chain of alternative regexes, and str2time() delegates to it. Several of these patterns place unbounded quantifiers next to each other before a trailing `\s*$` anchor. A valid date prefix followed by a long interior run of digits, letters, or whitespace and a single trailing byte that defeats the final match forces the engine to repartition the run, giving polynomial (about quadratic) backtracking. A header value of a few tens of kilobytes runs for tens of seconds of CPU. HTTP::Date parses timestamps such as HTTP `Date`, `Expires`, and `Last-Modified` headers, which commonly originate from untrusted sources. Any caller that passes an untrusted date header to str2time() or parse_date() can be driven to consume unbounded CPU, a denial of service.Show less

Grav before 2.0.4 contains a regular expression denial of service (ReDoS) vulnerability in the regex_replace filter and function, which are allowlisted in the Twig content sandbox. When Twig processing in page content is enabled (security.twig_content.process_enabled: true, disabled by default), an authenticated page editor can supply a catastrophically backtracking PCRE pattern that is passed directly to PHP's preg_replace(), causing unbounded CPU consumption and denial of service to the web server process.Show less

HAPI FHIR is a complete implementation of the HL7 FHIR standard for healthcare interoperability in Java. Prior to 6.9.7, the FHIRPathEngine implementation passes user-controlled regular expressions from matches(), matchesFull(), and replaceMatches() to Java regex operations without effective timeouts, allowing catastrophic backtracking and denial of service. This issue is fixed in version 6.9.7.Show less

Soup Sieve is a CSS selector library designed to be used with Beautiful Soup 4. Prior to 2.8.4, the CSS selector parser in soupsieve contains a regular expression vulnerable to catastrophic backtracking when processing an attribute selector with an unterminated quoted value in soupsieve/css_parser.py, allowing an attacker who can supply untrusted CSS selector strings to soupsieve.compile() or Beautiful Soup .select() / .select_one() to cause CPU exhaustion and denial of service. This issue is fixed in version 2.8.4.Show less

linkify-it is a links recognition library with full Unicode support. Prior to 5.0.1, LinkifyIt.prototype.match, the package's primary public API, has O(N²) algorithmic complexity for inputs containing many fuzzy links or emails because the JavaScript-level scan loop re-slices input and re-runs unanchored regex searches on progressively shorter tails. Any service that synchronously renders untrusted Markdown with linkify:true on a request hot path can inherit a worker-process denial of service triggerable by a tens-of-KB request body. This issue is fixed in version 5.0.1.Show less

UAParser.js is a JavaScript library to detect browsers, operating systems, CPUs, and devices from user-agent data. From 2.0.1 until 2.0.10, a regular expression denial-of-service vulnerability exists when using the Client Hints API. By sending a crafted Sec-CH-UA-Model header to an application that calls UAParser(headers).withClientHints(), an attacker can cause excessive CPU time due to catastrophic backtracking in the device regex because Client Hints values are copied without the UA_MAX_LENGTH limit used for User-Agent values. This issue is fixed in version 2.0.10.Show less

Symfony is a PHP framework for web and console applications and a set of reusable PHP components. Prior to 5.4.52, 6.4.40, 7.4.12, and 8.0.12, Symfony\Component\Yaml\Parser::cleanup() used regular expressions with overlapping quantifiers for YAML directive, comment, and document marker cleanup, allowing crafted input to make parsing hang for an arbitrarily long time. This issue is fixed in versions 5.4.52, 6.4.40, 7.4.12, and 8.0.12.Show less