CWE

Common Weakness Enumeration

A Community-Developed List of Software Weakness Types

CWE/SANS Top 25 Most Dangerous Software Errors
Home > CWE List > CWE- Individual Dictionary Definition (3.0)  
ID

CWE-407: Algorithmic Complexity

Weakness ID: 407
Abstraction: Base
Structure: Simple
Status: Incomplete
Presentation Filter:
+ 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.
+ Relationships

The table(s) below shows the weaknesses and high level categories that are related to this weakness. These relationships are defined as ChildOf, ParentOf, MemberOf and give insight to similar items that may exist at higher and lower levels of abstraction. In addition, relationships such as PeerOf and CanAlsoBe are defined to show similar weaknesses that the user may want to explore.

+ Relevant to the view "Research Concepts" (CWE-1000)
+ Relevant to the view "Weaknesses for Simplified Mapping of Published Vulnerabilities" (CWE-1003)
+ Relevant to the view "Development Concepts" (CWE-699)
+ Modes Of Introduction

The different Modes of Introduction provide information about how and when this weakness may be introduced. The Phase identifies a point in the software life cycle at which introduction may occur, while the Note provides a typical scenario related to introduction during the given phase.

PhaseNote
Architecture and Design
Implementation
+ Applicable Platforms
The listings below show possible areas for which the given weakness could appear. These may be for specific named Languages, Operating Systems, Architectures, Paradigms, Technologies, or a class of such platforms. The platform is listed along with how frequently the given weakness appears for that instance.

Languages

(Language-Independent classes): (Undetermined Prevalence)

+ Common Consequences

The table below specifies different individual consequences associated with the weakness. The Scope identifies the application security area that is violated, while the Impact describes the negative technical impact that arises if an adversary succeeds in exploiting this weakness. The Likelihood provides information about how likely the specific consequence is expected to be seen relative to the other consequences in the list. For example, there may be high likelihood that a weakness will be exploited to achieve a certain impact, but a low likelihood that it will be exploited to achieve a different impact.

ScopeImpactLikelihood
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
+ 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.
+ Functional Areas
  • Cryptography
+ Memberships
This MemberOf Relationships table shows additional CWE Categories and Views that reference this weakness as a member. This information is often useful in understanding where a weakness fits within the context of external information sources.
NatureTypeIDName
MemberOfViewView884CWE Cross-section
MemberOfCategoryCategory977SFP Secondary Cluster: Design
+ Taxonomy Mappings
Mapped Taxonomy NameNode IDFitMapped Node Name
PLOVERAlgorithmic Complexity
+ References
[REF-395] Crosby and Wallach. "Algorithmic Complexity Attacks". <http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/index.html>.
+ Content History
Submissions
Submission DateSubmitterOrganizationSource
PLOVER
Modifications
Modification DateModifierOrganizationSource
2008-07-01Eric DalciCigital
updated Time_of_Introduction
2008-09-08CWE Content TeamMITRE
updated Common_Consequences, Relationships, Other_Notes, Taxonomy_Mappings
2009-07-27CWE Content TeamMITRE
updated Functional_Areas, Other_Notes
2009-10-29CWE Content TeamMITRE
updated Common_Consequences
2009-12-28CWE Content TeamMITRE
updated Applicable_Platforms, Likelihood_of_Exploit
2011-06-01CWE Content TeamMITRE
updated Common_Consequences
2012-05-11CWE Content TeamMITRE
updated Observed_Examples, Relationships
2014-07-30CWE Content TeamMITRE
updated Relationships
2015-12-07CWE Content TeamMITRE
updated Relationships
2017-11-08CWE Content TeamMITRE
updated Likelihood_of_Exploit

More information is available — Please select a different filter.
Page Last Updated: November 14, 2017