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.

Primary

Quadratic Complexity
Used when the algorithmic complexity is related to the square of the number of inputs (N^2)

Architecture and Design

Implementation

Low

Availability
DoS: Resource Consumption (CPU)
DoS: Resource Consumption (Memory)
DoS: Resource Consumption (Other)
The typical consequence is CPU consumption, but memory consumption and consumption of other resources can also occur.

This example attempts to check if an input string is a "sentence" [REF-1164].

var test_string = "Bad characters: $@#";
var bad_pattern = /^(\w+\s?)*$/i;
var result = test_string.search(bad_pattern);

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:

var test_string = "Bad characters: $@#";
var good_pattern = /^((?=(\w+))\2\s?)*$/i;
var result = test_string.search(good_pattern);

Note that [REF-1164] has a more thorough (and lengthy) explanation of everything going on within the RegEx.

CVE-2021-32617
C++ library for image metadata has "quadratic complexity" issue with unnecessarily repetitive parsing each time an invalid character is encountered
https://www.cve.org/CVERecord?id=CVE-2021-32617

CVE-2020-10735
Python has "quadratic complexity" issue when converting string to int with many digits in unexpected bases
https://www.cve.org/CVERecord?id=CVE-2020-10735

CVE-2020-5243
server allows ReDOS with crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking.
https://www.cve.org/CVERecord?id=CVE-2020-5243

CVE-2014-1474
Perl-based email address parser has "quadratic complexity" issue via a string that does not contain a valid address
https://www.cve.org/CVERecord?id=CVE-2014-1474

CVE-2003-0244
CPU consumption via inputs that cause many hash table collisions.
https://www.cve.org/CVERecord?id=CVE-2003-0244

CVE-2003-0364
CPU consumption via inputs that cause many hash table collisions.
https://www.cve.org/CVERecord?id=CVE-2003-0364

CVE-2002-1203
Product performs unnecessary processing before dropping an invalid packet.
https://www.cve.org/CVERecord?id=CVE-2002-1203

CVE-2001-1501
CPU and memory consumption using many wildcards.
https://www.cve.org/CVERecord?id=CVE-2001-1501

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 its own category, where teardown takes more time than initialization.
https://www.cve.org/CVERecord?id=CVE-2004-2527

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."
https://www.cve.org/CVERecord?id=CVE-2006-6931

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.
https://www.cve.org/CVERecord?id=CVE-2006-3380

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.
https://www.cve.org/CVERecord?id=CVE-2006-3379

CVE-2005-2506
OS allows attackers to cause a denial of service (CPU consumption) via crafted Gregorian dates.
https://www.cve.org/CVERecord?id=CVE-2005-2506

CVE-2005-1792
Memory leak by performing actions faster than the software can clear them.
https://www.cve.org/CVERecord?id=CVE-2005-1792

Cryptography

Algorithmic Complexity

Allowed-with-Review
This CWE entry is a Class and might have Base-level children that would be more appropriate
Examine children of this entry to see if there is a better fit

PLOVER
2006-07-19
Draft 3
2006-07-19

Eric Dalci
Cigital
2008-07-01
updated Time_of_Introduction

CWE Content Team
MITRE
2008-09-08
updated Common_Consequences, Relationships, Other_Notes, Taxonomy_Mappings

CWE Content Team
MITRE
2009-07-27
updated Functional_Areas, Other_Notes

CWE Content Team
MITRE
2009-10-29
updated Common_Consequences

CWE Content Team
MITRE
2009-12-28
updated Applicable_Platforms, Likelihood_of_Exploit

CWE Content Team
MITRE
2011-06-01
updated Common_Consequences

CWE Content Team
MITRE
2012-05-11
updated Observed_Examples, Relationships

CWE Content Team
MITRE
2014-07-30
updated Relationships

CWE Content Team
MITRE
2015-12-07
updated Relationships

CWE Content Team
MITRE
2017-11-08
updated Likelihood_of_Exploit

CWE Content Team
MITRE
2019-06-20
updated Name, Relationships, Type

CWE Content Team
MITRE
2020-02-24
updated Relationships

CWE Content Team
MITRE
2020-08-20
updated Relationships

CWE Content Team
MITRE
2021-03-15
updated References, Relationships

CWE Content Team
MITRE
2021-07-20
updated References

CWE Content Team
MITRE
2022-10-13
updated Alternate_Terms, Observed_Examples, Relationships

CWE Content Team
MITRE
2023-01-31
updated Demonstrative_Examples, Observed_Examples, References

CWE Content Team
MITRE
2023-04-27
updated Relationships

CWE Content Team
MITRE
2023-06-29
updated Mapping_Notes

CWE Content Team
MITRE
2025-12-11
4.19
2025-12-11
updated Weakness_Ordinalities

Algorithmic Complexity