Tên: 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.

Thông tin chung

Các cách xuất hiện

Architecture and Design
Implementation

Nền tảng áp dụng

Ngôn ngữ

Lớp: Not Language-Specific (Undetermined)

Hậu quả phổ biến

Phạm vi	Tác động	Khả năng xảy ra
Availability	DoS: Resource Consumption (CPU), DoS: Resource Consumption (Memory), DoS: Resource Consumption (Other) Ghi chú: The typical consequence is CPU consumption, but memory consumption and consumption of other resources can also occur.

Ví dụ đã quan sát

Tài liệu tham khảo	Mô tả
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.

Phương pháp phát hiện

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.)
Hiệu quả : High

Ghi chú ánh xạ lỗ hổng

Lý do : This CWE entry is a Class and might have Base-level children that would be more appropriate
Bình luận : Examine children of this entry to see if there is a better fit

Tài liệu tham khảo

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

Gửi

Tên	Tổ chức	Ngày	Ngày phát hành	Version
PLOVER		2006-07-19 +00:00	2006-07-19 +00:00	Draft 3

Sửa đổi

Tên	Tổ chức	Ngày	Bình luận
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

Chi tiết CWE-407

CWE-407