Inefficient CPU Computation

Description

Inefficient CPU Computation occurs when a product performs CPU computations using algorithms that are not as efficient as they could be for the needs of the developer - the computations can be optimized further. This includes using algorithms with poor time complexity, performing redundant calculations, not caching computed results, using inefficient data structures, and making unnecessary iterations. When attackers can influence the amount or type of computation performed, inefficient algorithms can lead to denial-of-service conditions.

Risk

Inefficient CPU computation has security implications. Algorithms with poor worst-case complexity can be exploited for DoS. Resource exhaustion attacks become more effective. Legitimate users may be denied service due to slow processing. Time-based attacks may be easier due to measurable delays. System scalability is reduced, making capacity-based attacks easier. Shared resources may be monopolized by expensive computations. Cost increases in cloud environments due to CPU usage. Real-time systems may miss deadlines.

Solution

Choose algorithms with appropriate time complexity for the use case. Analyze worst-case complexity, not just average case. Implement caching for expensive repeated computations. Use efficient data structures (hash maps vs. linear search). Avoid redundant calculations. Set computation limits and timeouts. Monitor and profile CPU-intensive operations. Implement circuit breakers for expensive operations. Consider lazy evaluation where appropriate. Use memoization for recursive computations.

Common Consequences

Impact	Details
Availability	Scope: Availability DoS: Resource Consumption (CPU) - Suboptimal algorithms can degrade product performance noticeably. When attackers can manipulate computation amounts, this creates denial-of-service vulnerability conditions.

Example Code

Vulnerable Code

// Vulnerable: Inefficient string concatenation in loop

public class InefficiencyExamples {

    // O(n²) string concatenation - creates new String each iteration
    public String buildReport(List<String> items) {
        String result = "";  // Immutable - inefficient

        for (String item : items) {
            result = result + item + "\n";  // Creates new String each time
        }

        return result;
    }

    // O(n²) list contains check
    public List<String> findDuplicates(List<String> items) {
        List<String> duplicates = new ArrayList<>();

        for (int i = 0; i < items.size(); i++) {
            for (int j = i + 1; j < items.size(); j++) {
                if (items.get(i).equals(items.get(j))) {
                    if (!duplicates.contains(items.get(i))) {  // O(n) contains
                        duplicates.add(items.get(i));
                    }
                }
            }
        }

        return duplicates;  // Total: O(n³)!
    }

    // Repeated expensive computation
    public double processData(List<Double> values) {
        double result = 0;

        for (Double value : values) {
            // calculateFactor is expensive but returns same value for same input
            double factor = calculateExpensiveFactor(value);
            double factor2 = calculateExpensiveFactor(value);  // Redundant!
            result += value * factor * factor2;
        }

        return result;
    }

    // Linear search instead of hash lookup
    public User findUser(List<User> users, String username) {
        // O(n) for each lookup
        for (User user : users) {
            if (user.getUsername().equals(username)) {
                return user;
            }
        }
        return null;
    }

    // Fibonacci without memoization - O(2^n)
    public long fibonacci(int n) {
        if (n <= 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);  // Exponential time!
    }
}

# Vulnerable: Python with inefficient computations

import re

class InefficiencyExamples:

    # Inefficient regex compilation in loop
    def find_patterns(self, text, patterns):
        results = []
        for pattern in patterns:
            # Compiles regex every iteration!
            matches = re.findall(pattern, text)
            results.extend(matches)
        return results

    # O(n²) membership test with list
    def remove_duplicates(self, items):
        result = []
        for item in items:
            if item not in result:  # O(n) for list
                result.append(item)
        return result

    # Inefficient nested loops
    def find_pairs_with_sum(self, numbers, target):
        pairs = []
        for i in range(len(numbers)):
            for j in range(len(numbers)):  # Should start from i+1
                if i != j and numbers[i] + numbers[j] == target:
                    pairs.append((numbers[i], numbers[j]))
        return pairs  # Returns duplicates and O(n²)

    # Repeated database queries in loop (N+1 problem)
    def get_order_details(self, orders):
        details = []
        for order in orders:
            # Database query for each order!
            customer = db.query(f"SELECT * FROM customers WHERE id = {order.customer_id}")
            items = db.query(f"SELECT * FROM items WHERE order_id = {order.id}")
            details.append({
                'order': order,
                'customer': customer,
                'items': items
            })
        return details

    # Naive prime checking - O(n)
    def is_prime(self, n):
        if n < 2:
            return False
        for i in range(2, n):  # Should only go to sqrt(n)
            if n % i == 0:
                return False
        return True

    # Sorting in each iteration
    def get_top_items(self, items, n, count):
        results = []
        for _ in range(count):
            sorted_items = sorted(items)  # Sorts entire list each time!
            results.append(sorted_items[-n:])
        return results

// Vulnerable: C with inefficient algorithms

#include <string.h>
#include <stdlib.h>

// Naive string search - O(n*m)
int find_substring(const char *text, const char *pattern) {
    int text_len = strlen(text);     // Called once, OK
    int pattern_len = strlen(pattern);

    for (int i = 0; i <= text_len - pattern_len; i++) {
        int j;
        for (j = 0; j < pattern_len; j++) {
            if (text[i + j] != pattern[j]) {
                break;
            }
        }
        if (j == pattern_len) {
            return i;
        }
    }
    return -1;  // Could use KMP or Boyer-Moore for O(n+m)
}

// Bubble sort - O(n²)
void sort_array(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    // Should use quicksort/mergesort for O(n log n)
}

// Repeated strlen calls
void process_string(char *str) {
    for (int i = 0; i < strlen(str); i++) {  // strlen called every iteration!
        process_char(str[i]);
    }
}

// Creating copy in loop
void process_items(Item *items, int count) {
    for (int i = 0; i < count; i++) {
        Item *copy = malloc(sizeof(Item));  // Allocation in loop
        memcpy(copy, &items[i], sizeof(Item));
        process_item(copy);
        free(copy);  // Could reuse single buffer
    }
}

Fixed Code

// Fixed: Efficient algorithms and data structures

public class EfficientExamples {

    // O(n) string building with StringBuilder
    public String buildReport(List<String> items) {
        StringBuilder result = new StringBuilder();

        for (String item : items) {
            result.append(item).append("\n");
        }

        return result.toString();
    }

    // O(n) duplicate finding with HashSet
    public Set<String> findDuplicates(List<String> items) {
        Set<String> seen = new HashSet<>();
        Set<String> duplicates = new HashSet<>();

        for (String item : items) {
            if (!seen.add(item)) {  // O(1) add and check
                duplicates.add(item);
            }
        }

        return duplicates;
    }

    // Cached computation
    public double processData(List<Double> values) {
        Map<Double, Double> factorCache = new HashMap<>();
        double result = 0;

        for (Double value : values) {
            // Cache expensive computation
            double factor = factorCache.computeIfAbsent(value,
                this::calculateExpensiveFactor);
            result += value * factor * factor;
        }

        return result;
    }

    // O(1) lookup with HashMap
    private Map<String, User> userIndex;

    public void buildUserIndex(List<User> users) {
        userIndex = users.stream()
            .collect(Collectors.toMap(User::getUsername, u -> u));
    }

    public User findUser(String username) {
        return userIndex.get(username);  // O(1)
    }

    // Fibonacci with memoization - O(n)
    private Map<Integer, Long> fibCache = new HashMap<>();

    public long fibonacci(int n) {
        if (n <= 1) return n;

        return fibCache.computeIfAbsent(n, k ->
            fibonacci(k - 1) + fibonacci(k - 2)
        );
    }

    // Or iterative - O(n) time, O(1) space
    public long fibonacciIterative(int n) {
        if (n <= 1) return n;

        long prev = 0, curr = 1;
        for (int i = 2; i <= n; i++) {
            long next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

# Fixed: Python with efficient algorithms

import re
from functools import lru_cache
from collections import defaultdict

class EfficientExamples:

    def __init__(self):
        self._compiled_patterns = {}

    # Pre-compiled regex
    def find_patterns(self, text, patterns):
        results = []
        for pattern in patterns:
            # Compile once and cache
            if pattern not in self._compiled_patterns:
                self._compiled_patterns[pattern] = re.compile(pattern)
            compiled = self._compiled_patterns[pattern]
            matches = compiled.findall(text)
            results.extend(matches)
        return results

    # O(n) with set
    def remove_duplicates(self, items):
        seen = set()
        result = []
        for item in items:
            if item not in seen:  # O(1) for set
                seen.add(item)
                result.append(item)
        return result

    # Or simply:
    def remove_duplicates_simple(self, items):
        return list(dict.fromkeys(items))  # Preserves order

    # Efficient pair finding with hash map
    def find_pairs_with_sum(self, numbers, target):
        seen = {}
        pairs = set()

        for num in numbers:
            complement = target - num
            if complement in seen:
                pair = tuple(sorted([num, complement]))
                pairs.add(pair)
            seen[num] = True

        return list(pairs)  # O(n) instead of O(n²)

    # Batch database queries (avoid N+1)
    def get_order_details(self, orders):
        # Get all IDs
        customer_ids = [o.customer_id for o in orders]
        order_ids = [o.id for o in orders]

        # Single batch queries
        customers = db.query(
            "SELECT * FROM customers WHERE id IN :ids",
            ids=customer_ids
        )
        items = db.query(
            "SELECT * FROM items WHERE order_id IN :ids",
            ids=order_ids
        )

        # Index results
        customer_map = {c.id: c for c in customers}
        items_map = defaultdict(list)
        for item in items:
            items_map[item.order_id].append(item)

        # Build details from indexed data
        return [{
            'order': order,
            'customer': customer_map.get(order.customer_id),
            'items': items_map.get(order.id, [])
        } for order in orders]

    # Efficient prime checking - O(sqrt(n))
    def is_prime(self, n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False

        # Only check odd numbers up to sqrt(n)
        i = 3
        while i * i <= n:
            if n % i == 0:
                return False
            i += 2

        return True

    # Sort once, access many times
    def get_top_items(self, items, n, count):
        sorted_items = sorted(items)  # Sort once
        top_n = sorted_items[-n:]     # Get top N once

        # Return same result for all counts
        return [top_n for _ in range(count)]

    # Or use heap for finding top N - O(n log k) instead of O(n log n)
    def get_top_n(self, items, n):
        import heapq
        return heapq.nlargest(n, items)

// Fixed: C with efficient algorithms

#include <string.h>
#include <stdlib.h>
#include <math.h>

// Cache strlen result
void process_string(char *str) {
    int len = strlen(str);  // Calculate once
    for (int i = 0; i < len; i++) {
        process_char(str[i]);
    }
}

// Reuse buffer
void process_items(Item *items, int count) {
    Item *buffer = malloc(sizeof(Item));  // Allocate once

    for (int i = 0; i < count; i++) {
        memcpy(buffer, &items[i], sizeof(Item));
        process_item(buffer);
    }

    free(buffer);  // Free once
}

// Quicksort instead of bubble sort - O(n log n) average
void quicksort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quicksort(arr, low, pivot - 1);
        quicksort(arr, pivot + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

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

    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

// Efficient prime check - O(sqrt(n))
int is_prime(int n) {
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;

    int limit = (int)sqrt(n);
    for (int i = 3; i <= limit; i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

---

CVE Examples

This CWE is a contributing factor in algorithmic complexity attacks and denial-of-service vulnerabilities. Examples include ReDoS (Regular Expression Denial of Service) and hash collision attacks.

---

Related CWEs

• CWE-405: Asymmetric Resource Consumption (parent)
• CWE-1046: Creation of Immutable Text Using String Concatenation (child)
• CWE-1049: Excessive Data Query Operations (child)
• CWE-1067: Excessive Execution of Sequential Searches (child)
• CWE-407: Inefficient Algorithmic Complexity (related)

---

References

1. MITRE Corporation. "CWE-1176: Inefficient CPU Computation." https://cwe.mitre.org/data/definitions/1176.html
2. "Introduction to Algorithms" by Cormen et al.
3. Big-O Cheat Sheet: https://www.bigocheatsheet.com/