Inefficient Algorithmic Complexity

Description

Inefficient Algorithmic Complexity is a vulnerability that occurs when 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. Also known as "Quadratic Complexity" when the algorithm scales as O(n²), these weaknesses allow attackers to cause denial of service by providing inputs that trigger worst-case algorithmic behavior.

Risk

Inefficient algorithmic complexity enables attackers to cause denial of service with carefully crafted inputs. Regular expressions with catastrophic backtracking (ReDoS) can consume exponential CPU time. Sorting algorithms that degrade to O(n²) with specific inputs can freeze applications. Hash table implementations that use weak hash functions can be forced into O(n) lookup time through hash collision attacks. String processing functions may have hidden quadratic complexity. These attacks are dangerous because they exploit fundamental algorithmic properties and can be triggered with relatively small, valid-looking inputs.

Solution

Choose algorithms with good worst-case complexity guarantees. Avoid regular expressions with nested quantifiers that can cause catastrophic backtracking. Use atomic groups or possessive quantifiers in regex patterns. Implement timeouts for potentially long-running operations. Use randomized algorithms (like randomized quicksort) to prevent worst-case triggering. Apply input validation and size limits before processing. Consider using linear-time alternatives where possible. Profile and test with adversarial inputs during development.

Common Consequences

Impact	Details
Availability	Scope: Availability DoS: Resource Consumption (CPU) - Primary consequence is excessive CPU usage.
Availability	Scope: Availability DoS: Resource Consumption (Memory) - Some algorithmic attacks also consume excessive memory.

Example Code

Vulnerable Code

// Vulnerable: ReDoS - Regular expression with catastrophic backtracking
function vulnerableValidate(input) {
    // Vulnerable: Nested quantifiers cause exponential backtracking
    // Input like "aaaaaaaaaaaaaaaaaaaaaaaaaaaaX" takes exponential time
    const pattern = /^(\w+\s?)*$/;
    return pattern.test(input);
}

// Vulnerable: Another common ReDoS pattern
function vulnerableEmailCheck(email) {
    // Vulnerable: Overlapping alternatives with quantifiers
    const pattern = /^([a-zA-Z0-9]+)*@([a-zA-Z0-9]+\.)+[a-zA-Z]+$/;
    return pattern.test(email);
}

# Vulnerable: Quadratic string concatenation
def vulnerable_build_string(items):
    result = ""
    for item in items:
        # Vulnerable: String concatenation is O(n) per operation
        # Total complexity is O(n²)
        result += str(item) + ","
    return result

# Vulnerable: Quadratic list operations
def vulnerable_remove_duplicates(items):
    result = []
    for item in items:
        if item not in result:  # O(n) lookup
            result.append(item)
    # Total complexity: O(n²)
    return result

# Vulnerable: Nested loops
def vulnerable_find_pairs(list1, list2):
    pairs = []
    for item1 in list1:
        for item2 in list2:
            # O(n * m) even when not necessary
            if item1 == item2:
                pairs.append((item1, item2))
    return pairs

// Vulnerable: Inefficient sorting with predictable worst case
public class VulnerableSorter {

    // Vulnerable: Basic quicksort with first element as pivot
    // Sorted or nearly-sorted input causes O(n²) behavior
    public void vulnerableQuicksort(int[] arr, int low, int high) {
        if (low < high) {
            // Vulnerable: Always picks first element as pivot
            int pivot = arr[low];  // Worst case for sorted input
            int i = low, j = high;

            while (i < j) {
                while (arr[i] <= pivot && i < high) i++;
                while (arr[j] > pivot) j--;
                if (i < j) swap(arr, i, j);
            }
            swap(arr, low, j);

            vulnerableQuicksort(arr, low, j - 1);
            vulnerableQuicksort(arr, j + 1, high);
        }
    }
}

Fixed Code

// Fixed: Use atomic groups or possessive quantifiers
function secureValidate(input) {
    // Fixed: Add length limit first
    if (input.length > 1000) {
        return false;
    }

    // Fixed: Use possessive quantifier equivalent (atomic group)
    // Or use a simpler pattern that doesn't backtrack
    const pattern = /^[\w\s]+$/;  // Simpler, no nested quantifiers
    return pattern.test(input);
}

// Fixed: Use timeout for regex operations
async function secureValidateWithTimeout(input, pattern, timeoutMs = 100) {
    return new Promise((resolve) => {
        const timeout = setTimeout(() => resolve(false), timeoutMs);

        try {
            const result = pattern.test(input);
            clearTimeout(timeout);
            resolve(result);
        } catch (e) {
            clearTimeout(timeout);
            resolve(false);
        }
    });
}

// Fixed: Simpler email validation
function secureEmailCheck(email) {
    if (email.length > 254) return false;

    // Fixed: Simple pattern without nested quantifiers
    const pattern = /^[^\s@]+@[^\s@]+\.[^\s@]+$/;
    return pattern.test(email);
}

# Fixed: Use list/generator for efficient string building
def secure_build_string(items):
    # Fixed: O(n) complexity using join
    return ",".join(str(item) for item in items)

# Fixed: Use set for O(1) lookups
def secure_remove_duplicates(items):
    seen = set()
    result = []
    for item in items:
        if item not in seen:  # O(1) lookup
            seen.add(item)
            result.append(item)
    # Total complexity: O(n)
    return result

# Alternative: Use dict.fromkeys() for order-preserving dedup
def secure_remove_duplicates_v2(items):
    return list(dict.fromkeys(items))

# Fixed: Use set intersection for finding common elements
def secure_find_pairs(list1, list2):
    # Fixed: O(n + m) using set operations
    set2 = set(list2)
    return [(item, item) for item in list1 if item in set2]

// Fixed: Randomized quicksort with median-of-three
import java.util.Random;

public class SecureSorter {
    private Random random = new Random();

    // Fixed: Use randomized pivot selection
    public void secureQuicksort(int[] arr, int low, int high) {
        if (low < high) {
            // Fixed: Random pivot prevents worst-case exploitation
            int pivotIndex = low + random.nextInt(high - low + 1);
            swap(arr, pivotIndex, high);  // Move pivot to end

            int pivot = arr[high];
            int i = low - 1;

            for (int j = low; j < high; j++) {
                if (arr[j] <= pivot) {
                    i++;
                    swap(arr, i, j);
                }
            }
            swap(arr, i + 1, high);

            int pi = i + 1;
            secureQuicksort(arr, low, pi - 1);
            secureQuicksort(arr, pi + 1, high);
        }
    }

    // Alternative: Use median-of-three pivot selection
    private int medianOfThree(int[] arr, int low, int high) {
        int mid = low + (high - low) / 2;

        if (arr[low] > arr[mid]) swap(arr, low, mid);
        if (arr[low] > arr[high]) swap(arr, low, high);
        if (arr[mid] > arr[high]) swap(arr, mid, high);

        return mid;  // Median is now at mid
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

---

CVE Examples

• CVE-2020-10735 — Python string-to-int conversion with unexpectedly high digit counts causes CPU exhaustion.
• CVE-2020-5243 — ReDoS attacks via crafted User-Agent strings.
• CVE-2014-1474 — Perl email parser with quadratic complexity issues.
• CVE-2003-0244 — Hash table collision-based CPU attacks in Linux routing cache.

---

References

1. MITRE Corporation. "CWE-407: Inefficient Algorithmic Complexity." https://cwe.mitre.org/data/definitions/407.html
2. OWASP. "Regular expression Denial of Service - ReDoS." https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS