William Blair (Boston University), Andrea Mambretti (Northeastern University), Sajjad Arshad (Northeastern University), Michael Weissbacher (Northeastern University), William Robertson (Northeastern University), Engin Kirda (Northeastern University), Manuel Egele (Boston University)
Fifteen billion devices run Java and many of them are
connected to the Internet. As this ecosystem continues to grow,
it remains an important task to discover the unknown security
threats these devices face. Fuzz testing repeatedly runs software
on random inputs in order to trigger unexpected program
behaviors, such as crashes or timeouts, and has historically re-
vealed serious security vulnerabilities. Contemporary fuzz testing
techniques focus on identifying memory corruption vulnerabilities
that allow adversaries to achieve remote code execution. Mean-
while, algorithmic complexity (AC) vulnerabilities, which are a
common attack vector for denial-of-service attacks, remain an
understudied threat.
In this paper, we present HotFuzz, a framework for automatically
discovering AC vulnerabilities in Java libraries. HotFuzz uses
micro-fuzzing, a genetic algorithm that evolves arbitrary Java
objects in order to trigger the worst-case performance for a
method under test. We define Small Recursive Instantiation (SRI)
which provides seed inputs to micro-fuzzing represented as Java
objects. After micro-fuzzing, HotFuzz synthesizes test cases that
triggered AC vulnerabilities into Java programs and monitors
their execution in order to reproduce vulnerabilities outside the
analysis framework. HotFuzz outputs those programs that exhibit
high CPU utilization as witnesses for AC vulnerabilities in a Java
library.
We evaluate HotFuzz over the Java Runtime Environment (JRE),
the 100 most popular Java libraries on Maven, and challenges
contained in the DARPA Space and Time Analysis for Cyber-
Security (STAC) program. We compare the effectiveness of using
seed inputs derived using SRI against using empty values. In this
evaluation, we verified known AC vulnerabilities, discovered pre-
viously unknown AC vulnerabilities that we responsibly reported
to vendors, and received confirmation from both IBM and Oracle.
Our results demonstrate micro-fuzzing finds AC vulnerabilities
in real-world software, and that micro-fuzzing with SRI derived
seed inputs complements using empty seed inputs.