This weakness occurs when software uses an algorithm that consumes disproportionate CPU, memory, or time relative to the size of its input. An attacker can…
This weakness occurs when software uses an algorithm that consumes disproportionate CPU, memory, or time relative to the size of its input. An attacker can craft specially designed input to trigger extreme resource consumption, causing the application to slow down, become unresponsive, or crash — a condition known as a denial-of-service (DoS) attack. The flaw is not a logic error; it's a performance design problem that becomes exploitable under adversarial conditions.
Inefficient algorithmic complexity typically arises when developers choose algorithms without considering worst-case behavior or fail to validate input size before processing. Common patterns include nested loops over user-supplied collections, recursive algorithms without depth limits, or operations that scale exponentially with input length. For example, a search function that iterates through every element for every element (O(n²) complexity) may work fine on small datasets but becomes unusable when an attacker submits a large input. Similarly, algorithms that perform expensive operations (regex matching, sorting, hashing) on unbounded user input can be exploited to exhaust server resources.
The root cause is often a mismatch between the algorithm's theoretical complexity and the practical constraints of the deployment environment. Developers may not anticipate that input size could grow beyond typical use cases, or they may underestimate the cost of operations performed per input element.
Resource exhaustion can render an application unavailable to legitimate users. A web server processing inefficient queries may consume all CPU or memory, causing timeouts and service degradation. In multi-tenant environments, a single attacker's crafted input can impact other users. Depending on the context, this can lead to financial loss (cloud infrastructure overages), reputational damage, or violation of service-level agreements. In some cases, the attack may cascade — for instance, a slow database query triggered by inefficient code can lock resources and block other operations.
def search_items(items, query):
results = []
for item in items:
for char in query:
if char in item:
results.append(item)
break
return results
# Called with user input
user_items = request.args.get('items', '').split(',')
user_query = request.args.get('query', '')
search_items(user_items, user_query)Why it's vulnerable:
The nested loop structure is O(n × m), where n is the number of items and m is the query length. An attacker can submit thousands of items and a long query string to force quadratic iterations, consuming CPU and causing timeouts.
def search_items(items, query):
# Limit input size and use efficient lookup
MAX_ITEMS = 1000
MAX_QUERY_LEN = 100
if len(items) > MAX_ITEMS or len(query) > MAX_QUERY_LEN:
raise ValueError("Input exceeds size limits")
query_chars = set(query) # O(m) preprocessing
results = [item for item in items if any(c in query_chars for c in item)]
return resultsfunction filter_records($records, $pattern) {
$results = array();
foreach ($records as $record) {
foreach (str_split($pattern) as $char) {
if (strpos($record, $char) !== false) {
$results[] = $record;
break;
}
}
}
return $results;
}
$user_records = explode(',', $_GET['records']);
$user_pattern = $_GET['pattern'];
filter_records($user_records, $user_pattern);Why it's vulnerable:
Nested loops over user-supplied arrays and strings create O(n × m) complexity. A large records parameter combined with a long pattern can exhaust CPU time.
function filter_records($records, $pattern) {
$MAX_RECORDS = 1000;
$MAX_PATTERN_LEN = 100;
if (count($records) > $MAX_RECORDS || strlen($pattern) > $MAX_PATTERN_LEN) {
throw new Exception("Input exceeds size limits");
}
$pattern_chars = array_flip(str_split($pattern));
$results = array_filter($records, function($record) use ($pattern_chars) {
foreach (str_split($record) as $char) {
if (isset($pattern_chars[$char])) {
return true;
}
}
return false;
});
return $results;
}Watch for unexplained CPU spikes or memory exhaustion correlated with specific requests or parameters. Check application logs for requests with unusually large input values (long query strings, many array elements, large file uploads) followed by timeout errors or slow response times. Monitor for repeated requests with similar patterns, which may indicate an attacker probing for algorithmic weaknesses.
