Inefficient Algorithmic Complexity

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.


The following examples help to illustrate the nature of this weakness and describe methods or techniques which can be used to mitigate the risk.

Note that the examples here are by no means exhaustive and any given weakness may have many subtle varieties, each of which may require different detection methods or runtime controls.

Example One

This example attempts to check if an input string is a "sentence" [REF-1164].

var test_string = "Bad characters: $@#";
var bad_pattern  = /^(\w+\s?)*$/i;
var result =;

The regular expression has a vulnerable backtracking clause inside (\w+\s?)*$ which can be triggered to cause a Denial of Service by processing particular phrases.

To fix the backtracking problem, backtracking is removed with the ?= portion of the expression which changes it to a lookahead and the \2 which prevents the backtracking. The modified example is:

var test_string = "Bad characters: $@#";
var good_pattern  = /^((?=(\w+))\2\s?)*$/i;
var result =;

Note that [REF-1164] has a more thorough (and lengthy) explanation of everything going on within the RegEx.

See Also

Comprehensive Categorization: Resource Lifecycle Management

Weaknesses in this category are related to resource lifecycle management.

CISQ Quality Measures - Maintainability

Weaknesses in this category are related to the CISQ Quality Measures for Maintainability. Presence of these weaknesses could reduce the maintainability of the software.

SFP Secondary Cluster: Design

This category identifies Software Fault Patterns (SFPs) within the Design cluster.

Comprehensive CWE Dictionary

This view (slice) covers all the elements in CWE.

Weaknesses for Simplified Mapping of Published Vulnerabilities

CWE entries in this view (graph) may be used to categorize potential weaknesses within sources that handle public, third-party vulnerability information, such as the N...

CWE Cross-section

This view contains a selection of weaknesses that represent the variety of weaknesses that are captured in CWE, at a level of abstraction that is likely to be useful t...

Common Weakness Enumeration content on this website is copyright of The MITRE Corporation unless otherwise specified. Use of the Common Weakness Enumeration and the associated references on this website are subject to the Terms of Use as specified by The MITRE Corporation.