CWE

Common Weakness Enumeration

A Community-Developed Dictionary of Software Weakness Types

Common Weakness Scoring System
Common Weakness Risk Analysis Framework
Home > CWE List > CWE- Individual Dictionary Definition (2.8)  

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
CPU consumption via inputs that cause many hash table collisions.
CPU consumption via inputs that cause many hash table collisions.
Product performs unnecessary processing before dropping an invalid packet.
CPU and memory consumption using many wildcards.
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.
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."
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.
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.
OS allows attackers to cause a denial of service (CPU consumption) via crafted Gregorian dates.
Memory 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
ChildOfCategoryCategory977SFP Secondary Cluster: Design
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
2014-07-30CWE Content TeamMITREInternal
updated Relationships
Page Last Updated: July 30, 2014