이름: 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.

일반 정보

취약점 도입 방식

Architecture and Design
Implementation

적용 가능한 플랫폼

언어

클래스: Not Language-Specific (Undetermined)

일반적인 결과

범위	영향	가능성
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.

관찰된 예시

참고 자료	설명
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.

탐지 방법

Automated Static Analysis

Automated static analysis, commonly referred to as Static Application Security Testing (SAST), can find some instances of this weakness by analyzing source code (or binary/compiled code) without having to execute it. Typically, this is done by building a model of data flow and control flow, then searching for potentially-vulnerable patterns that connect "sources" (origins of input) with "sinks" (destinations where the data interacts with external components, a lower layer such as the OS, etc.)
효과성 : High

취약점 매핑 메모

근거 : 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

참고 자료

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

REF-1534

Automated Technical Debt Measure, Version 2
OMG.
https://www.omg.org/spec/ATDM2/1.0/PDF

제출

이름	조직	날짜	출시일	Version
PLOVER		2006-07-19 +00:00	2006-07-19 +00:00	Draft 3

수정 사항

이름	조직	날짜	댓글
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
CWE Content Team	MITRE	2025-12-11 +00:00	updated Weakness_Ordinalities
CWE Content Team	MITRE	2026-10-28 +00:00	updated Detection_Factors, References

CWE-407 상세 정보

CWE-407