CWE-407 Detail

CWE-407

Name

Inefficient Algorithmic Complexity

Likelihood

Low

Status

Incomplete

Published

2006-07-19
00h00 +00:00

Modified

2023-06-29
00h00 +00:00

Official links

CWE Mitre.org

Notifications for a CWE

Stay informed of any changes for a specific CWE.

Notifications manage

List of Notifications

Notifications for a CWE

Stay informed of any changes for a specific CWE.

Parameters

You can specify a title that will be retrieved in the alerts that will be sent out.

Specify the CWE ID you wish to monitor.

Planning

Month

Next run calculation

Day

Weekday

Hour

Minute

Creation date

Last execution

Next execution

Functionality requiring a connection

This feature, which allows you to receive alerts, is only active when you are logged into your account.

Name: Inefficient Algorithmic 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.

General Informations

Modes Of Introduction

Architecture and Design
Implementation

Applicable Platforms

Language

Class: Not Language-Specific (Undetermined)

Common Consequences

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

Observed Examples

References	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 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.

Vulnerability Mapping Notes

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

References

REF-395

Algorithmic Complexity Attacks
Scott A. Crosby, Dan S. Wallach.
https://www.usenix.org/legacy/events/sec03/tech/full_papers/crosby/crosby.pdf

REF-1164

Catastrophic backtracking
Ilya Kantor.
https://javascript.info/regexp-catastrophic-backtracking

Submission

Name	Organization	Date	Date release	Version
PLOVER		2006-07-19 +00:00	2006-07-19 +00:00	Draft 3

Modifications

Name	Organization	Date	Comment
Eric Dalci	Cigital	2008-07-01 +00:00	updated Time_of_Introduction
CWE Content Team	MITRE	2008-09-08 +00:00	updated Common_Consequences, Relationships, Other_Notes, Taxonomy_Mappings
CWE Content Team	MITRE	2009-07-27 +00:00	updated Functional_Areas, Other_Notes
CWE Content Team	MITRE	2009-10-29 +00:00	updated Common_Consequences
CWE Content Team	MITRE	2009-12-28 +00:00	updated Applicable_Platforms, Likelihood_of_Exploit
CWE Content Team	MITRE	2011-06-01 +00:00	updated Common_Consequences
CWE Content Team	MITRE	2012-05-11 +00:00	updated Observed_Examples, Relationships
CWE Content Team	MITRE	2014-07-30 +00:00	updated Relationships
CWE Content Team	MITRE	2015-12-07 +00:00	updated Relationships
CWE Content Team	MITRE	2017-11-08 +00:00	updated Likelihood_of_Exploit
CWE Content Team	MITRE	2019-06-20 +00:00	updated Name, Relationships, Type
CWE Content Team	MITRE	2020-02-24 +00:00	updated Relationships
CWE Content Team	MITRE	2020-08-20 +00:00	updated Relationships
CWE Content Team	MITRE	2021-03-15 +00:00	updated References, Relationships
CWE Content Team	MITRE	2021-07-20 +00:00	updated References
CWE Content Team	MITRE	2022-10-13 +00:00	updated Alternate_Terms, Observed_Examples, Relationships
CWE Content Team	MITRE	2023-01-31 +00:00	updated Demonstrative_Examples, Observed_Examples, References
CWE Content Team	MITRE	2023-04-27 +00:00	updated Relationships
CWE Content Team	MITRE	2023-06-29 +00:00	updated Mapping_Notes