Inefficient Algorithmic Complexity
This vulnerability occurs when a software component uses an algorithm with poor worst-case performance. An attacker can exploit this by providing specially crafted input that forces the algorithm into its slowest possible execution path, leading to severe performance degradation or denial of service.
At its core, this issue is about predictable resource exhaustion. Common examples include using algorithms with quadratic (O(n²)) or exponential complexity for tasks that handle user-controlled data size, like inefficient sorting or search algorithms on large, attacker-supplied inputs. When exploited, this can cause excessive CPU consumption, memory usage, or runtime delays, crippling the application's availability. Developers can mitigate this by selecting algorithms with consistent, efficient complexity (like O(n log n) for sorting) and implementing safeguards. These include setting hard limits on input size, using timeouts for operations, and switching to more performant algorithms or data structures when processing thresholds are crossed. Always profile code with worst-case input scenarios during testing.
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.
ID : DX-158
This example attempts to check if an input string is a "sentence" [REF-1164].Code Example:
var test_string = "Bad characters: $@#"; var bad_pattern = /^(\w+\s?)*$/i; var result = test_string.search(bad_pattern);
Code Example:
var test_string = "Bad characters: $@#"; var good_pattern = /^((?=(\w+))\2\s?)*$/i; var result = test_string.search(good_pattern);
Low
Quadratic Complexity
Used when the algorithmic complexity is related to the square of the number of inputs (N^2)- Cryptography
- PLOVER