CWE

Common Weakness Enumeration

A Community-Developed Dictionary of Software Weakness Types

CWE/SANS Top 25 Most Dangerous Software Errors Common Weakness Scoring System
Common Weakness Risk Analysis Framework
Home > CWE List > CWE- Individual Dictionary Definition (2.6)  

Presentation Filter:

CWE-407: Algorithmic Complexity

 
Algorithmic Complexity
Weakness ID: 407 (Weakness Base)Status: Incomplete
+ Description

Description Summary

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.
+ Time of Introduction
  • Architecture and Design
  • Implementation
+ Applicable Platforms

Languages

Language-independent

+ Common Consequences
ScopeEffect
Availability

Technical Impact: 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.

+ Likelihood of Exploit

Low to Medium

+ Observed Examples
ReferenceDescription
CVE-2003-0244CPU consumption via inputs that cause many hash table collisions.
CVE-2003-0364CPU consumption via inputs that cause many hash table collisions.
CVE-2002-1203Product performs unnecessary processing before dropping an invalid packet.
CVE-2001-1501CPU and memory consumption using many wildcards.
CVE-2004-2527Product 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-6931Network 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-3380Wiki 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-3379Wiki 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-2506OS allows attackers to cause a denial of service (CPU consumption) via crafted Gregorian dates.
CVE-2005-1792Memory leak by performing actions faster than the software can clear them.
+ Relationships
NatureTypeIDNameView(s) this relationship pertains toView(s)
ChildOfWeakness ClassWeakness Class405Asymmetric Resource Consumption (Amplification)
Development Concepts (primary)699
Research Concepts (primary)1000
ChildOfCategoryCategory907SFP Cluster: Other
Software Fault Pattern (SFP) Clusters (primary)888
MemberOfViewView884CWE Cross-section
CWE Cross-section (primary)884
+ Functional Areas
  • Cryptography
+ Taxonomy Mappings
Mapped Taxonomy NameNode IDFitMapped Node Name
PLOVERAlgorithmic Complexity
+ References
Crosby and Wallach. "Algorithmic Complexity Attacks". <http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/index.html>.
+ Content History
Submissions
Submission DateSubmitterOrganizationSource
PLOVERExternally Mined
Modifications
Modification DateModifierOrganizationSource
2008-07-01Eric DalciCigitalExternal
updated Time_of_Introduction
2008-09-08CWE Content TeamMITREInternal
updated Common_Consequences, Relationships, Other_Notes, Taxonomy_Mappings
2009-07-27CWE Content TeamMITREInternal
updated Functional_Areas, Other_Notes
2009-10-29CWE Content TeamMITREInternal
updated Common_Consequences
2009-12-28CWE Content TeamMITREInternal
updated Applicable_Platforms, Likelihood_of_Exploit
2011-06-01CWE Content TeamMITREInternal
updated Common_Consequences
2012-05-11CWE Content TeamMITREInternal
updated Observed_Examples, Relationships
Page Last Updated: February 18, 2014