Ineffiziente algorithmische Komplexität
Beschreibung
Ineffiziente algorithmische Komplexität ist eine Schwachstelle, die auftritt, wenn ein Algorithmus in einem Produkt eine ineffiziente Worst-Case-Rechenkomplexität hat, die für die Systemleistung nachteilig sein kann und von einem Angreifer ausgelöst werden kann, typischerweise durch gezielte Manipulationen, die sicherstellen, dass der Worst Case erreicht wird. Auch bekannt als "Quadratische Komplexität" wenn der Algorithmus als O(n²) skaliert, ermöglichen diese Schwächen Angreifern, Denial-of-Service zu verursachen, indem sie Eingaben bereitstellen, die algorithmisches Worst-Case-Verhalten auslösen.
Risiko
Ineffiziente algorithmische Komplexität ermöglicht es Angreifern, mit sorgfältig konstruierten Eingaben Denial-of-Service zu verursachen. Reguläre Ausdrücke mit katastrophalem Backtracking (ReDoS) können exponentielle CPU-Zeit verbrauchen. Sortieralgorithmen, die mit bestimmten Eingaben zu O(n²) degradieren, können Anwendungen einfrieren. Hash-Tabellen-Implementierungen, die schwache Hash-Funktionen verwenden, können durch Hash-Kollisionsangriffe zu O(n) Lookup-Zeit gezwungen werden. String-Verarbeitungsfunktionen können versteckte quadratische Komplexität haben. Diese Angriffe sind gefährlich, weil sie fundamentale algorithmische Eigenschaften ausnutzen und mit relativ kleinen, gültig aussehenden Eingaben ausgelöst werden können.
Lösung
Wählen Sie Algorithmen mit guten Worst-Case-Komplexitätsgarantien. Vermeiden Sie reguläre Ausdrücke mit verschachtelten Quantifizierern, die katastrophales Backtracking verursachen können. Verwenden Sie atomare Gruppen oder possessive Quantifizierer in Regex-Mustern. Implementieren Sie Timeouts für potenziell lang laufende Operationen. Verwenden Sie randomisierte Algorithmen (wie randomisierter Quicksort), um Worst-Case-Auslösung zu verhindern. Wenden Sie Eingabevalidierung und Größenlimits vor der Verarbeitung an. Erwägen Sie wo möglich lineare Alternativen. Profilieren und testen Sie während der Entwicklung mit adversarialen Eingaben.
Häufige Auswirkungen
| Auswirkung | Details |
|---|---|
| Verfügbarkeit | Umfang: Verfügbarkeit DoS: Ressourcenverbrauch (CPU) - Primäre Konsequenz ist übermäßiger CPU-Verbrauch. |
| Verfügbarkeit | Umfang: Verfügbarkeit DoS: Ressourcenverbrauch (Speicher) - Einige algorithmische Angriffe verbrauchen auch übermäßigen Speicher. |
Beispielcode
Anfälliger Code
// Anfällig: ReDoS - Regulärer Ausdruck mit katastrophalem Backtracking
function vulnerableValidate(input) {
// Anfällig: Verschachtelte Quantifizierer verursachen exponentielles Backtracking
// Eingabe wie "aaaaaaaaaaaaaaaaaaaaaaaaaaaaX" benötigt exponentielle Zeit
const pattern = /^(\w+\s?)*$/;
return pattern.test(input);
}
// Anfällig: Ein weiteres häufiges ReDoS-Muster
function vulnerableEmailCheck(email) {
// Anfällig: Überlappende Alternativen mit Quantifizierern
const pattern = /^([a-zA-Z0-9]+)*@([a-zA-Z0-9]+\.)+[a-zA-Z]+$/;
return pattern.test(email);
}
# Anfällig: Quadratische String-Konkatenation
def vulnerable_build_string(items):
result = ""
for item in items:
# Anfällig: String-Konkatenation ist O(n) pro Operation
# Gesamtkomplexität ist O(n²)
result += str(item) + ","
return result
# Anfällig: Quadratische Listenoperationen
def vulnerable_remove_duplicates(items):
result = []
for item in items:
if item not in result: # O(n) Lookup
result.append(item)
# Gesamtkomplexität: O(n²)
return result
# Anfällig: Verschachtelte Schleifen
def vulnerable_find_pairs(list1, list2):
pairs = []
for item1 in list1:
for item2 in list2:
# O(n * m) selbst wenn nicht notwendig
if item1 == item2:
pairs.append((item1, item2))
return pairs
// Anfällig: Ineffiziente Sortierung mit vorhersagbarem Worst Case
public class VulnerableSorter {
// Anfällig: Einfacher Quicksort mit erstem Element als Pivot
// Sortierte oder nahezu sortierte Eingabe verursacht O(n²) Verhalten
public void vulnerableQuicksort(int[] arr, int low, int high) {
if (low < high) {
// Anfällig: Nimmt immer erstes Element als Pivot
int pivot = arr[low]; // Worst Case für sortierte Eingabe
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);
}
}
}
Korrigierter Code
// Korrigiert: Atomare Gruppen oder possessive Quantifizierer verwenden
function secureValidate(input) {
// Korrigiert: Zuerst Längenlimit hinzufügen
if (input.length > 1000) {
return false;
}
// Korrigiert: Possessiven Quantifizierer-Äquivalent (atomare Gruppe) verwenden
// Oder einfacheres Muster verwenden, das nicht zurückverfolgt
const pattern = /^[\w\s]+$/; // Einfacher, keine verschachtelten Quantifizierer
return pattern.test(input);
}
// Korrigiert: Timeout für Regex-Operationen verwenden
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);
}
});
}
// Korrigiert: Einfachere E-Mail-Validierung
function secureEmailCheck(email) {
if (email.length > 254) return false;
// Korrigiert: Einfaches Muster ohne verschachtelte Quantifizierer
const pattern = /^[^\s@]+@[^\s@]+\.[^\s@]+$/;
return pattern.test(email);
}
# Korrigiert: Liste/Generator für effiziente String-Erstellung verwenden
def secure_build_string(items):
# Korrigiert: O(n) Komplexität mit join
return ",".join(str(item) for item in items)
# Korrigiert: Set für O(1) Lookups verwenden
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)
# Gesamtkomplexität: O(n)
return result
# Alternative: dict.fromkeys() für reihenfolgeerhaltende Deduplizierung
def secure_remove_duplicates_v2(items):
return list(dict.fromkeys(items))
# Korrigiert: Set-Intersection für gemeinsame Elemente verwenden
def secure_find_pairs(list1, list2):
# Korrigiert: O(n + m) mit Set-Operationen
set2 = set(list2)
return [(item, item) for item in list1 if item in set2]
// Korrigiert: Randomisierter Quicksort mit Median-of-Three
import java.util.Random;
public class SecureSorter {
private Random random = new Random();
// Korrigiert: Randomisierte Pivot-Auswahl verwenden
public void secureQuicksort(int[] arr, int low, int high) {
if (low < high) {
// Korrigiert: Zufälliger Pivot verhindert Worst-Case-Ausnutzung
int pivotIndex = low + random.nextInt(high - low + 1);
swap(arr, pivotIndex, high); // Pivot ans Ende verschieben
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: Median-of-Three Pivot-Auswahl verwenden
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 ist jetzt bei mid
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
CVE-Beispiele
- CVE-2020-10735 — Python String-zu-Int-Konvertierung mit unerwartet hohen Ziffernzahlen verursacht CPU-Erschöpfung.
- CVE-2020-5243 — ReDoS-Angriffe über manipulierte User-Agent-Strings.
- CVE-2014-1474 — Perl E-Mail-Parser mit quadratischen Komplexitätsproblemen.
- CVE-2003-0244 — Hash-Tabellen-Kollisionsbasierte CPU-Angriffe im Linux-Routing-Cache.
Referenzen
- MITRE Corporation. "CWE-407: Inefficient Algorithmic Complexity." https://cwe.mitre.org/data/definitions/407.html
- OWASP. "Regular expression Denial of Service - ReDoS." https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS