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

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-6931
CVE-2006-3380
CVE-2006-3379
CVE-2005-2506
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
+ 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
Back to top