Algorithmen: Komplexität & Sicherheit
Dieser Beitrag ist eine Begriffserklärung zur sicherheitsrelevanten Seite von Algorithmen – inklusive Merkpunkten und Prüfungsfragen.
In a Nutshell
Nicht nur „durchschnittlich schnell“ zählt: Für robuste Systeme ist die Worst-Case-Analyse entscheidend. Pathologische Eingaben können sonst zu DoS führen (Algorithmic Complexity Attacks).
Kompakte Fachbeschreibung
Algorithmen werden oft nach Laufzeit und Speicherbedarf bewertet (Big-O/Θ/Ω). In sicherheitskritischen Kontexten ist entscheidend:
- Worst-Case-Verhalten
- Eingabevalidierung
- Ressourcenlimits (Timeouts, Speichergrenzen)
Typische Beispiele:
- Hash-DoS (künstliche Kollisionen)
- Regex-DoS (katastrophales Backtracking)
- ungebremste Rekursion (StackOverflow)
Prüfungsrelevante Stichpunkte
- Worst-Case robust machen
- Zeit-/Speicherlimits
- Defensive Programmierung bei Eingaben
- Monitoring/Rate Limiting/Backpressure
Typische Prüfungsfragen (mit Kurzantwort)
- Warum ist Worst-Case-Analyse wichtig? Weil Angreifer/Fehler „schlechte“ Inputs erzwingen können.
- Was ist Hash-DoS? Kollisionen machen Hash-Tabellen extrem langsam.
- Was ist Regex-DoS? Bestimmte Regex+Input führen zu extrem langen Laufzeiten.