Source-linked AI summary
SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities
Theofilos Petsios, Jason Zhao, Angelos D. Keromytis, Suman Jana
TL;DR
Algorithmic complexity vulnerabilities are difficult to detect across domains because existing approaches depend on manual, implementation-specific rules. SlowFuzz uses resource-usage-guided evolutionary search to find worst-case inputs automatically, achieving more than 100% improvement over code-coverage-guided generation while exposing vulnerabilities in diverse applications.
Problem
Algorithmic complexity vulnerabilities create large worst-case versus average-case resource differences, while existing detection relies on difficult-to-scale domain- and implementation-specific analysis.
Method
SlowFuzz instruments a binary and uses evolutionary search to mutate and retain inputs that maximize resource utilization without domain-specific rules.
Results
SlowFuzz achieves more than 100% improvement over code-coverage-guided input generation and detects vulnerabilities across diverse real-world applications.
Takeaways & Limitations
Customized evolutionary search is a promising direction for automated detection of algorithmic complexity and other resource-exhaustion vulnerabilities.
Takeaways & Limitations
SlowFuzz’s instruction guidance uses coarse, imprecise 8-bit edge-access counters, so observed instruction totals are not monotonically increasing.
Abstract
from arXiv · showhide
Algorithmic complexity vulnerabilities occur when the worst-case time/space complexity of an application is significantly higher than the respective average case for particular user-controlled inputs. When such conditions are met, an attacker can launch Denial-of-Service attacks against a vulnerable application by providing inputs that trigger the worst-case behavior. Such attacks have been known to have serious effects on production systems, take down entire websites, or lead to bypasses of Web Application Firewalls. Unfortunately, existing detection mechanisms for algorithmic complexity vulnerabilities are domain-specific and often require significant manual effort. In this paper, we design, implement, and evaluate SlowFuzz, a domain-independent framework for automatically finding algorithmic complexity vulnerabilities. SlowFuzz automatically finds inputs that trigger worst-case algorithmic behavior in the tested binary. SlowFuzz uses resource-usage-guided evolutionary search techniques to automatically find inputs that maximize computational resource utilization for a given application.
1 INTRODUCTION
Algorithmic complexity vulnerabilities arise when user-controlled inputs produce much worse time or space usage than average cases, enabling denial-of-service attacks. SlowFuzz addresses the difficulty of detecting them across domains by using automated, resource-guided evolutionary testing.
- Algorithmic complexity vulnerabilities stem from large worst-case versus average-case differences in application or data-structure complexity.
- Crafted inputs can trigger worst-case behavior and enable denial-of-service attacks, including through regular expressions, hash tables, and quicksort.Quicksort can have O(nlogn) average-case complexity and O(n^2) worst-case complexity.
- Domain-independent detection is difficult because manual analysis does not scale, implementation details alter complexity, and constant factors matter in execution time.
- Existing detection mechanisms rely on brittle, domain-specific rules that require substantial expertise and maintenance as software changes.
- SlowFuzz automatically searches for inputs maximizing resource utilization through a domain-independent evolutionary approach without manual guidance or domain-specific rules.The fitness objective can include instruction count and memory usage.
- SlowFuzz achieves more than 100% improvement over code-coverage-guided generation and finds vulnerabilities across diverse real-world applications.Evaluated domains include bzip2, PCRE, and PHP hash tables.
2 OVERVIEW
SlowFuzz frames worst-case-input discovery as resource-usage optimization under gray-box access, then uses evolutionary mutation and selection to approach expensive executions without domain-specific rules.
- SlowFuzz detects candidate vulnerabilities by finding large resource-utilization variations among inputs of a given size, rather than estimating asymptotic complexity.It can use executed instructions or CPU usage as resource measures.
- The approach assumes gray-box access to instrument the application binary and collect fine-grained resource-usage information across runs.
- SlowFuzz does not know domain-specific rules or pivot-selection semantics, yet seeks inputs triggering worst-case behavior in the tested implementation.
- Evolutionary search starts from seed inputs, mutates corpus members, ranks them by resource usage, and retains high-ranked inputs for later generations.
- For first-element-pivot quicksort, sorted arrays trigger quadratic behavior, so mutations that increase executed statements are selected for further mutation.In the example, executes 37 LOC, while executes 52 LOC.
3 METHODOLOGY
SlowFuzz’s methodology combines evolutionary corpus management with resource-based fitness and specialized mutations to seek inputs that maximize execution cost.
- SlowFuzz’s evolutionary engine repeatedly selects, mutates, executes, scores, and retains inputs that exhibit high resource usage.
- Coverage-based fitness is poorly suited because it does not capture loop iterations that drive repeated execution and resource consumption.
- The fitness function ranks inputs by total executed instructions, monitored at basic-block granularity, so higher counts represent slower executions.
- SlowFuzz supports mutations that add, remove, modify, reorder, cross over, or dictionary-replace input bytes.
- Mutation priority scores operations by how often they increase instruction counts, balancing exploration and exploitation through ϵ, whose default value is 0.5.
4 IMPLEMENTATION
SlowFuzz extends libFuzzer with instrumentation and an analysis engine that executes the target in-process while refining an active corpus of inputs.
- The prototype is built on libFuzzer and consists of 550 lines of C++ modifications compiled with Clang v4.0.
- SlowFuzz executes in the same address space as the tested application and instruments it to expose resource-usage metrics such as executed instructions.
- The analysis engine controls executions and maintains an active input corpus that it refines during testing.
5 EVALUATION
SlowFuzz was evaluated on sorting algorithms, real-world quicksort implementations, regular expressions, hash tables, and bzip2, using resource-guided evolutionary search to expose worst-case behavior. Across these settings, it triggered substantial slowdowns and complexity vulnerabilities, outperforming coverage-guided or random baselines where comparisons were reported.
- Sorting: On real-world quicksort implementations, SlowFuzz produced slowdowns from 8.7% to 3.34x, while coverage-based fuzzing never exceeded 5%.The implementations were NetBSD, GNU, OpenBSD, and Apple quicksort.
- Sorting: SlowFuzz generated sorting inputs achieving 84.97% and 83.74% of theoretical worst-case performance for insertion sort and quicksort, respectively, without algorithm-internal information.The experiments used 64-byte inputs and averaged 100 runs.
- Regular Expressions: SlowFuzz generated regular expressions with super-linear and exponential matching complexity, with average rates of 12.33% and 2.29%, respectively.With 90% probability, it generated at least 2 super-linear regexes and 31 slowdown-inducing regexes; the probability of at least one exponential regex was 45.45%.
- Hash Tables: For PHP hash tables, SlowFuzz reached 31.25% of the theoretical worst-case after approximately 40 hours on one CPU without hash-function details.Coverage-based fuzzing produced no input with more than 8 collisions, whereas SlowFuzz’s evolutionary guidance increased slowdowns monotonically.
- ZIP Utilities: For bzip2, SlowFuzz found a 300x decompression slowdown and a two-byte mutation that caused BZ2_bzDecompress to be called 4845 times instead of once.The input size remained unchanged after the mutation; coverage-based fuzzing achieved at most a 23.7% slowdown.
- Fitness Function: SlowFuzz’s resource-usage fitness function and mutation schemes outperformed code-coverage-guided evolutionary search by more than 100%.The comparison evaluates resource-use-guided search against coverage-guided search for finding complexity-triggering inputs.
6 DISCUSSION
SlowFuzz’s evolutionary search can be extended beyond algorithmic complexity vulnerabilities, while prototype implementation choices constrain efficiency and resource-usage measurement precision.
- Future directions: Evolutionary fuzzing strategies can be adapted to find algorithmic complexity vulnerabilities and other resource-exhaustion attacks.Potential targets include battery draining and filling memory or hard disks.
- Future directions: Integrating static analysis could reduce SlowFuzz’s mutation search space and improve performance.Taint tracking, loop analysis, and runtime flow profiles could identify promising mutation locations.
- Prototype limitations: SlowFuzz’s prototype tracks CFG-edge access counts through SanitizerCoverage, but its bucket limit reduces resource-usage accuracy.Edges accessed more than 128 times share a bucket regardless of their actual counts.
- Prototype characteristics: SlowFuzz execution is dominated by the tested function, which occupies less than 0.02 seconds of native-binary execution.
- Prototype limitations: The prototype’s imprecise edge counts are an implementation artifact rather than a fundamental SlowFuzz limitation.More precise alternatives include custom callbacks, hardware counters, or per-unit perf tracking.
7 RELATED WORK
Prior work addresses complexity attacks, analyst-guided detection, and generic performance profiling, but these approaches differ from SlowFuzz’s automated vulnerability-focused search.
- Complexity attacks: Prior complexity attacks targeted hash tables, kernel name lookup, Snort inspection, and Aho-Corasick matching, often with specialized attack knowledge or defenses.
- Complexity-vulnerability detection: Analyst-driven Java exploration combines static and dynamic analysis but requires humans to select analyzed regions and define binary inputs.
- Performance bugs: A genetic-algorithm profiler explores Web-application input combinations for performance bottlenecks rather than detecting algorithmic complexity vulnerabilities.
8 CONCLUSION
SlowFuzz is presented as an evolutionary-search framework that finds worst-case algorithmic behavior across several real-world application classes without regular-expression semantic knowledge.
- Conclusion: SlowFuzz is described as the first evolutionary-search-based framework targeting algorithmic complexity vulnerabilities.
- Conclusion: SlowFuzz generated inputs matching theoretical worst-case complexity in known algorithms and triggered vulnerabilities in every examined application.
- Conclusion: Its inputs caused more than 300-times slowdown in bzip2, high hash-table collision counts, and exponential regular-expression matching.
- Conclusion: The regular-expression results required no knowledge of regular-expression semantics.
A WAF REGEXES
This appendix presents regular expressions associated with the slowdowns shown in Figure 7, including patterns for matching text and HTML-like tags.
- WAF regexes: Figure 7’s slowdowns correspond to specific regular expressions listed in this appendix.
- WAF regexes: One listed pattern uses case-insensitive matching and repeated alternatives involving characters, whitespace, and numeric character encodings.
- WAF regexes: Other listed patterns enumerate HTML-like tags and search for VML frame markup with a source attribute.