An algorithm in a product has an inefficient worst-case computational complexity that may be detrimental to system performance and can be triggered by an attacker, typically using crafted manipulations that ensure that the worst case is being reached.
View on MITREThe typical consequence is CPU consumption, but memory consumption and consumption of other resources can also occur.
No mitigation information available for this CWE.
No detection method information available for this CWE.
This example attempts to check if an input string is a "sentence" [REF-1164].
The regular expression has a vulnerable backtracking clause inside (\w+\s?)*$ which can be triggered to cause a Denial of Service by processing particular phrases. To fix the backtracking problem, backtracking is removed with the ?= portion of the expression which changes it to a lookahead and the \2 which prevents the backtracking. The modified example is:
This example attempts to check if an input string is a "sentence" [REF-1164].
The regular expression has a vulnerable backtracking clause inside (\w+\s?)*$ which can be triggered to cause a Denial of Service by processing particular phrases. To fix the backtracking problem, backtracking is removed with the ?= portion of the expression which changes it to a lookahead and the \2 which prevents the backtracking. The modified example is:
C++ library for image metadata has "quadratic complexity" issue with unnecessarily repetitive parsing each time an invalid character is encountered
View DetailsPython has "quadratic complexity" issue when converting string to int with many digits in unexpected bases
View Detailsserver allows ReDOS with crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking.
View DetailsPerl-based email address parser has "quadratic complexity" issue via a string that does not contain a valid address
View DetailsProduct allows attackers to cause multiple copies of a program to be loaded more quickly than the program can detect that other copies are running, then exit. This type of error should probably have its own category, where teardown takes more time than initialization.
View DetailsNetwork monitoring system allows remote attackers to cause a denial of service (CPU consumption and detection outage) via crafted network traffic, aka a "backtracking attack."
View DetailsWiki allows remote attackers to cause a denial of service (CPU consumption) by performing a diff between large, crafted pages that trigger the worst case algorithmic complexity.
View DetailsWiki allows remote attackers to cause a denial of service (CPU consumption) by performing a diff between large, crafted pages that trigger the worst case algorithmic complexity.
View DetailsOS allows attackers to cause a denial of service (CPU consumption) via crafted Gregorian dates.
View DetailsCWE-407: Inefficient Algorithmic Complexity is a Common Weakness Enumeration (CWE) entry maintained by MITRE. An algorithm in a product has an inefficient worst-case computational complexity that may be detrimental to system performance and can be triggered by an attacker, typically using crafted manipulations that ensure that the worst case is being reached.
If exploited, CWE-407 (Inefficient Algorithmic Complexity) it can compromise Availability, leading to outcomes such as DoS: Resource Consumption (CPU), DoS: Resource Consumption (Memory) and DoS: Resource Consumption (Other).
CWE-407 commonly affects Not Language-Specific. Note that weaknesses are often language-agnostic patterns, so secure coding practices apply broadly.
MITRE documents real CVEs mapped to CWE-407, including CVE-2021-32617, CVE-2020-10735, CVE-2020-5243, CVE-2014-1474 and CVE-2003-0244. You can look up the full details of each CVE, including CVSS scores and remediation guidance, on our CVE Lookup tool.
A CWE (Common Weakness Enumeration) like CWE-407 describes a category of software weakness — the underlying flaw type. A CVE (Common Vulnerabilities and Exposures) identifies a specific, real-world vulnerability in a particular product. In short, a CWE is the kind of mistake, and a CVE is an instance of that mistake being found in software.