Ineffiziente CPU-Berechnung

Beschreibung

Ineffiziente CPU-Berechnung tritt auf, wenn ein Produkt CPU-Berechnungen mit Algorithmen durchführt, die nicht so effizient sind, wie sie für die Bedürfnisse des Entwicklers sein könnten - die Berechnungen können weiter optimiert werden. Dies umfasst die Verwendung von Algorithmen mit schlechter Zeitkomplexität, redundante Berechnungen, fehlende Zwischenspeicherung berechneter Ergebnisse, Verwendung ineffizienter Datenstrukturen und unnötige Iterationen. Wenn Angreifer die Menge oder Art der durchgeführten Berechnungen beeinflussen können, können ineffiziente Algorithmen zu Denial-of-Service-Bedingungen führen.

Risiko

Ineffiziente CPU-Berechnung hat Sicherheitsauswirkungen. Algorithmen mit schlechter Worst-Case-Komplexität können für DoS ausgenutzt werden. Ressourcenerschöpfungsangriffe werden effektiver. Legitimen Benutzern kann der Dienst aufgrund langsamer Verarbeitung verweigert werden. Zeitbasierte Angriffe können aufgrund messbarer Verzögerungen einfacher sein. Die Systemskalierbarkeit ist reduziert, was kapazitätsbasierte Angriffe erleichtert. Gemeinsame Ressourcen können durch teure Berechnungen monopolisiert werden. Kostenerhöhungen in Cloud-Umgebungen aufgrund von CPU-Nutzung. Echtzeitsysteme können Deadlines verpassen.

Lösung

Wählen Sie Algorithmen mit angemessener Zeitkomplexität für den Anwendungsfall. Analysieren Sie die Worst-Case-Komplexität, nicht nur den Durchschnitt. Implementieren Sie Caching für teure wiederholte Berechnungen. Verwenden Sie effiziente Datenstrukturen (Hash-Maps vs. lineare Suche). Vermeiden Sie redundante Berechnungen. Setzen Sie Berechnungslimits und Timeouts. Überwachen und profilieren Sie CPU-intensive Operationen. Implementieren Sie Circuit Breaker für teure Operationen. Erwägen Sie Lazy Evaluation wo angemessen. Verwenden Sie Memoization für rekursive Berechnungen.

Häufige Auswirkungen

Auswirkung	Details
Verfügbarkeit	Bereich: Verfügbarkeit DoS: Ressourcenverbrauch (CPU) - Suboptimale Algorithmen können die Produktleistung merklich verschlechtern. Wenn Angreifer Berechnungsmengen manipulieren können, schafft dies Denial-of-Service-Schwachstellenbedingungen.

Beispielcode

Verwundbarer Code

// Verwundbar: Ineffiziente String-Verkettung in Schleife

public class InefficiencyExamples {

    // O(n²) String-Verkettung - erstellt neuen String bei jeder Iteration
    public String buildReport(List<String> items) {
        String result = "";  // Unveränderlich - ineffizient

        for (String item : items) {
            result = result + item + "\n";  // Erstellt jedes Mal neuen String
        }

        return result;
    }

    // O(n²) List-Contains-Prüfung
    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;  // Gesamt: O(n³)!
    }

    // Wiederholte teure Berechnung
    public double processData(List<Double> values) {
        double result = 0;

        for (Double value : values) {
            // calculateFactor ist teuer aber gibt gleichen Wert für gleiche Eingabe zurück
            double factor = calculateExpensiveFactor(value);
            double factor2 = calculateExpensiveFactor(value);  // Redundant!
            result += value * factor * factor2;
        }

        return result;
    }

    // Lineare Suche statt Hash-Lookup
    public User findUser(List<User> users, String username) {
        // O(n) für jede Suche
        for (User user : users) {
            if (user.getUsername().equals(username)) {
                return user;
            }
        }
        return null;
    }

    // Fibonacci ohne Memoization - O(2^n)
    public long fibonacci(int n) {
        if (n <= 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);  // Exponentielle Zeit!
    }
}

# Verwundbar: Python mit ineffizienten Berechnungen

import re

class InefficiencyExamples:

    # Ineffiziente Regex-Kompilierung in Schleife
    def find_patterns(self, text, patterns):
        results = []
        for pattern in patterns:
            # Kompiliert Regex bei jeder Iteration!
            matches = re.findall(pattern, text)
            results.extend(matches)
        return results

    # O(n²) Membership-Test mit Liste
    def remove_duplicates(self, items):
        result = []
        for item in items:
            if item not in result:  # O(n) für Liste
                result.append(item)
        return result

    # Ineffiziente verschachtelte Schleifen
    def find_pairs_with_sum(self, numbers, target):
        pairs = []
        for i in range(len(numbers)):
            for j in range(len(numbers)):  # Sollte bei i+1 starten
                if i != j and numbers[i] + numbers[j] == target:
                    pairs.append((numbers[i], numbers[j]))
        return pairs  # Gibt Duplikate zurück und O(n²)

    # Wiederholte Datenbankabfragen in Schleife (N+1 Problem)
    def get_order_details(self, orders):
        details = []
        for order in orders:
            # Datenbankabfrage für jede Bestellung!
            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 Primzahlprüfung - O(n)
    def is_prime(self, n):
        if n < 2:
            return False
        for i in range(2, n):  # Sollte nur bis sqrt(n) gehen
            if n % i == 0:
                return False
        return True

    # Sortierung in jeder Iteration
    def get_top_items(self, items, n, count):
        results = []
        for _ in range(count):
            sorted_items = sorted(items)  # Sortiert gesamte Liste jedes Mal!
            results.append(sorted_items[-n:])
        return results

// Verwundbar: C mit ineffizienten Algorithmen

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

// Naive String-Suche - O(n*m)
int find_substring(const char *text, const char *pattern) {
    int text_len = strlen(text);     // Einmal aufgerufen, 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;  // Könnte KMP oder Boyer-Moore für O(n+m) verwenden
}

// 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;
            }
        }
    }
    // Sollte Quicksort/Mergesort für O(n log n) verwenden
}

// Wiederholte strlen-Aufrufe
void process_string(char *str) {
    for (int i = 0; i < strlen(str); i++) {  // strlen bei jeder Iteration aufgerufen!
        process_char(str[i]);
    }
}

// Kopie in Schleife erstellen
void process_items(Item *items, int count) {
    for (int i = 0; i < count; i++) {
        Item *copy = malloc(sizeof(Item));  // Allokation in Schleife
        memcpy(copy, &items[i], sizeof(Item));
        process_item(copy);
        free(copy);  // Könnte einzelnen Puffer wiederverwenden
    }
}

Lösung

// Behoben: Effiziente Algorithmen und Datenstrukturen

public class EfficientExamples {

    // O(n) String-Erstellung mit 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) Duplikatfindung mit 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 und check
                duplicates.add(item);
            }
        }

        return duplicates;
    }

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

        for (Double value : values) {
            // Teure Berechnung cachen
            double factor = factorCache.computeIfAbsent(value,
                this::calculateExpensiveFactor);
            result += value * factor * factor;
        }

        return result;
    }

    // O(1) Lookup mit 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 mit 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)
        );
    }

    // Oder iterativ - O(n) Zeit, O(1) Speicher
    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;
    }
}

# Behoben: Python mit effizienten Algorithmen

import re
from functools import lru_cache
from collections import defaultdict

class EfficientExamples:

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

    # Vorkompilierte Regex
    def find_patterns(self, text, patterns):
        results = []
        for pattern in patterns:
            # Einmal kompilieren und cachen
            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) mit Set
    def remove_duplicates(self, items):
        seen = set()
        result = []
        for item in items:
            if item not in seen:  # O(1) für Set
                seen.add(item)
                result.append(item)
        return result

    # Oder einfach:
    def remove_duplicates_simple(self, items):
        return list(dict.fromkeys(items))  # Erhält Reihenfolge

    # Effiziente Paarfindung mit 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) statt O(n²)

    # Batch-Datenbankabfragen (N+1 vermeiden)
    def get_order_details(self, orders):
        # Alle IDs sammeln
        customer_ids = [o.customer_id for o in orders]
        order_ids = [o.id for o in orders]

        # Einzelne Batch-Abfragen
        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
        )

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

        # Details aus indizierten Daten erstellen
        return [{
            'order': order,
            'customer': customer_map.get(order.customer_id),
            'items': items_map.get(order.id, [])
        } for order in orders]

    # Effiziente Primzahlprüfung - O(sqrt(n))
    def is_prime(self, n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False

        # Nur ungerade Zahlen bis sqrt(n) prüfen
        i = 3
        while i * i <= n:
            if n % i == 0:
                return False
            i += 2

        return True

    # Einmal sortieren, mehrfach zugreifen
    def get_top_items(self, items, n, count):
        sorted_items = sorted(items)  # Einmal sortieren
        top_n = sorted_items[-n:]     # Top N einmal holen

        # Gleiches Ergebnis für alle Counts zurückgeben
        return [top_n for _ in range(count)]

    # Oder Heap für Top-N-Findung verwenden - O(n log k) statt O(n log n)
    def get_top_n(self, items, n):
        import heapq
        return heapq.nlargest(n, items)

// Behoben: C mit effizienten Algorithmen

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

// strlen-Ergebnis cachen
void process_string(char *str) {
    int len = strlen(str);  // Einmal berechnen
    for (int i = 0; i < len; i++) {
        process_char(str[i]);
    }
}

// Puffer wiederverwenden
void process_items(Item *items, int count) {
    Item *buffer = malloc(sizeof(Item));  // Einmal allokieren

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

    free(buffer);  // Einmal freigeben
}

// Quicksort statt Bubble Sort - O(n log n) Durchschnitt
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;
}

// Effiziente Primzahlprüfung - 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-Beispiele

Diese CWE ist ein beitragender Faktor bei Angriffen auf algorithmische Komplexität und Denial-of-Service-Schwachstellen. Beispiele sind ReDoS (Regular Expression Denial of Service) und Hash-Kollisionsangriffe.

---

Verwandte CWEs

• CWE-405: Asymmetrischer Ressourcenverbrauch (übergeordnet)
• CWE-1046: Erstellung von unveränderlichem Text durch String-Verkettung (untergeordnet)
• CWE-1049: Übermäßige Datenabfrageoperationen (untergeordnet)
• CWE-1067: Übermäßige Ausführung sequentieller Suchen (untergeordnet)
• CWE-407: Ineffiziente algorithmische Komplexität (verwandt)

---

Referenzen

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