Class weakness

Incomplete

CWE-407: Inefficient Algorithmic Complexity

Also known as: Quadratic Complexity

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.

Recorded CVEs

With this primary weakness

KEVs

In the CISA KEV catalog

Low

Likelihood of exploit

Per MITRE

Class

Abstraction

MITRE classification

Overview

CWE-407 (Inefficient Algorithmic Complexity) is a class-level software weakness catalogued by MITRE in the Common Weakness Enumeration (CWE). It describes a recurring type of mistake that can lead to exploitable security vulnerabilities.

Illustrative examples

Real CVEs that MITRE cites as examples of this weakness.

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 its own category, where teardown takes more time than initialization.
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.

CWE-407: Inefficient Algorithmic Complexity

Overview

Real-world CVEs

Common consequences

How it happens

When it is introduced

Code examples

Illustrative examples

Terminology & mappings

Alternate terms

Mapped taxonomies

Frequently asked questions

What is CWE-407?

What CVEs are caused by CWE-407?

What are the consequences of CWE-407?

Is CWE-407 actively exploited?

References

Stay ahead of CWE-407

Overview

Real-world CVEs

Common consequences

How it happens

When it is introduced

Code examples

Illustrative examples

Related weaknesses

Parent

Child

Terminology & mappings

Alternate terms

Mapped taxonomies

Frequently asked questions

What is CWE-407?

What CVEs are caused by CWE-407?

What are the consequences of CWE-407?

Is CWE-407 actively exploited?

References

Stay ahead of CWE-407