Algorithms: Complexity & Security

This post is a glossary entry on the security-relevant aspects of algorithms – including key points and exam questions.

In a Nutshell

It’s not just about “reasonably fast”: For robust systems, worst-case analysis is crucial. Pathological inputs can otherwise lead to DoS (Algorithmic Complexity Attacks).

Concise Technical Description

Algorithms are often evaluated by runtime and memory requirements (Big-O/Θ/Ω). In security-critical contexts, what matters is:

• Worst-case behavior
• Input validation
• Resource limits (timeouts, memory bounds)

Typical examples:

• Hash-DoS (artificial collisions)
• Regex-DoS (catastrophic backtracking)
• Unbounded recursion (StackOverflow)

Exam-Relevant Key Points

• Make worst-case robust
• Time/memory limits
• Defensive programming for inputs
• Monitoring/rate limiting/backpressure

Typical Exam Questions (with Brief Answers)

1. Why is worst-case analysis important? Because attackers/errors can force “bad” inputs.
2. What is Hash-DoS? Collisions make hash tables extremely slow.
3. What is Regex-DoS? Certain regex+input combinations lead to extremely long runtimes.

Further Information

1. https://owasp.org/