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.7)  

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

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
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
Externally Mined
Modifications
Modification DateModifierOrganizationSource
2008-07-01CigitalExternal
updated Time_of_Introduction
2008-09-08MITREInternal
updated Common_Consequences, Relationships, Other_Notes, Taxonomy_Mappings
2009-07-27MITREInternal
updated Functional_Areas, Other_Notes
2009-10-29MITREInternal
updated Common_Consequences
2009-12-28MITREInternal
updated Applicable_Platforms, Likelihood_of_Exploit
2011-06-01MITREInternal
updated Common_Consequences
2012-05-11MITREInternal
updated Observed_Examples, Relationships
Page Last Updated: June 23, 2014