Description
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.
Potential Impact
Availability
DoS: Resource Consumption (CPU), DoS: Resource Consumption (Memory), DoS: Resource Consumption (Other)
Demonstrative Examples
var test_string = "Bad characters: $@#";
var bad_pattern = /^(\w+\s?)*$/i;
var result = test_string.search(bad_pattern);var test_string = "Bad characters: $@#";
var good_pattern = /^((?=(\w+))\2\s?)*$/i;
var result = test_string.search(good_pattern);Real-World CVE Examples
| CVE ID | Description |
|---|---|
| CVE-2021-32617 | C++ library for image metadata has "quadratic complexity" issue with unnecessarily repetitive parsing each time an invalid character is encountered |
| CVE-2020-10735 | Python has "quadratic complexity" issue when converting string to int with many digits in unexpected bases |
| CVE-2020-5243 | server allows ReDOS with crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking. |
| CVE-2014-1474 | Perl-based email address parser has "quadratic complexity" issue via a string that does not contain a valid address |
| CVE-2003-0244 | CPU consumption via inputs that cause many hash table collisions. |
| CVE-2003-0364 | CPU consumption via inputs that cause many hash table collisions. |
| CVE-2002-1203 | Product performs unnecessary processing before dropping an invalid packet. |
| CVE-2001-1501 | CPU and memory consumption using many wildcards. |
| CVE-2004-2527 | Product 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 i |
| CVE-2006-6931 | Network monitoring system allows remote attackers to cause a denial of service (CPU consumption and detection outage) via crafted network traffic, aka a "backtracking attack." |
| CVE-2006-3380 | Wiki 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. |
| CVE-2006-3379 | Wiki 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. |
| CVE-2005-2506 | OS allows attackers to cause a denial of service (CPU consumption) via crafted Gregorian dates. |
| CVE-2005-1792 | Memory leak by performing actions faster than the software can clear them. |
Related Weaknesses
Taxonomy Mappings
- PLOVER: — Algorithmic Complexity
Frequently Asked Questions
What is CWE-407?
CWE-407 (Inefficient Algorithmic Complexity) is a software weakness identified by MITRE's Common Weakness Enumeration. It is classified as a Class-level weakness. 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 manipulation...
How can CWE-407 be exploited?
Attackers can exploit CWE-407 (Inefficient Algorithmic Complexity) to dos: resource consumption (cpu), dos: resource consumption (memory), dos: resource consumption (other). This weakness is typically introduced during the Architecture and Design, Implementation phase of software development.
How do I prevent CWE-407?
Follow secure coding practices, conduct code reviews, and use automated security testing tools (SAST/DAST) to detect this weakness early in the development lifecycle.
What is the severity of CWE-407?
CWE-407 is classified as a Class-level weakness (High abstraction). It has been observed in 14 real-world CVEs.