[Forgot Password]
Login  Register Subscribe

23631

 
 

115084

 
 

97147

 
 

909

 
 

78730

 
 

109

Paid content will be excluded from the download.


Download | Alert*
CWE
view XML

Algorithmic Complexity

ID: 407Date: (C)2012-05-14   (M)2017-11-15
Type: weaknessStatus: INCOMPLETE
Abstraction Type: Base





Description

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.

Likelihood of Exploit: Low to Medium

Applicable Platforms
Language Class: Language-independent

Time Of Introduction

  • Architecture and Design
  • Implementation

Common Consequences

ScopeTechnical ImpactNotes
Availability
 
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.
 

Detection Methods
None

Potential Mitigations
None

Relationships

Related CWETypeViewChain
CWE-407 ChildOf CWE-907 Category CWE-888  

Demonstrative Examples
None

Observed Examples

  1. CVE-2003-0244 : CPU consumption via inputs that cause many hash table collisions.
  2. CVE-2003-0364 : CPU consumption via inputs that cause many hash table collisions.
  3. CVE-2002-1203 : Product performs unnecessary processing before dropping an invalid packet.
  4. CVE-2001-1501 : CPU and memory consumption using many wildcards.
  5. 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.
  6. 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."
  7. 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.
  8. 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.
  9. CVE-2005-2506 : OS allows attackers to cause a denial of service (CPU consumption) via crafted Gregorian dates.
  10. CVE-2005-1792 : Memory leak by performing actions faster than the software can clear them.

For more examples, refer to CVE relations in the bottom box.

White Box Definitions
None

Black Box Definitions
None

Taxynomy Mappings

TaxynomyIdNameFit
PLOVER  Algorithmic Complexity
 
 

References:

  1. Crosby Wallach .Algorithmic Complexity Attacks.

© 2013 SecPod Technologies