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 revealed serious security vulnerabilities. Contemporary fuzz testing techniques focus on identifying memory corruption vulnerabilities that allow adversaries to achieve remote code execution. Meanwhile, 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 previously 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.

View More Papers

CDN Judo: Breaking the CDN DoS Protection with Itself

Run Guo (Tsinghua University), Weizhong Li (Tsinghua University), Baojun Liu (Tsinghua University), Shuang Hao (University of Texas at Dallas), Jia Zhang (Tsinghua University), Haixin Duan (Tsinghua University), Kaiwen Sheng (Tsinghua University), Jianjun Chen (ICSI), Ying Liu (Tsinghua University)

Read More

Poseidon: Mitigating Volumetric DDoS Attacks with Programmable Switches

Menghao Zhang (Tsinghua University), Guanyu Li (Tsinghua University), Shicheng Wang (Tsinghua University), Chang Liu (Tsinghua University), Ang Chen (Rice University), Hongxin Hu (Clemson University), Guofei Gu (Texas A&M University), Qi Li (Tsinghua University), Mingwei Xu (Tsinghua University), Jianping Wu (Tsinghua University)

Read More

Carnus: Exploring the Privacy Threats of Browser Extension Fingerprinting

Soroush Karami (University of Illinois at Chicago), Panagiotis Ilia (University of Illinois at Chicago), Konstantinos Solomos (University of Illinois at Chicago), Jason Polakis (University of Illinois at Chicago)

Read More

Bobtail: Improved Blockchain Security with Low-Variance Mining

George Bissias (University of Massachusetts Amherst), Brian N. Levine (University of Massachusetts Amherst)

Read More