HotFuzz: Discovering Algorithmic Denial-of-Service Vulnerabilities

A detailed exploration of algorithmic complexity bugs and insight into distributed micro-fuzzing methods. The study uncovers vulnerabilities through guided micro-fuzzing approaches, emphasizing the importance of AC bug detection and fuzz testing techniques such as seed inputs, fuzz observations, and test case synthesis, presenting a comprehensive analysis of issues related to computing performance and security.

• Algorithmic Complexity
• Micro-Fuzzing
• Vulnerabilities
• Fuzz Testing
• Security

decimus Follow

Uploaded on Jul 19, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. HotFuzz Discovering Algorithmic Denial-of-Service Vulnerabilities through Guided Micro-Fuzzing William Blair Boston University Andrea Mambretti Northeastern University Sajjad Arshad Northeastern University Michael Weissbacher Northeastern University William Robertson Northeastern University Engin Kirda Manuel Egele Boston University Northeastern University 1

2. 1988 2

3. 2020 Fuzz Testing Seed Inputs 1% Covered 2% Covered Crashing Inputs Program Under Test Fuzzer (AFL, LibFuzzer) 3

4. Algorithmic Complexity (AC) Bugs We observed computing the total price of your cart can take 4 months! Check Out 4

5. HotFuzz Distributed Micro-Fuzzing Input Output Synthesis and Validation Message Broker EyeVM OpenJDK AC Witnesses ?Fuzz Observations K8S 5

6. Distributed Micro-Fuzzing Input Output Synthesis and Validation Message Broker HotFuzz Micro-Fuzzing EyeVM OpenJDK AC Witnesses ?Fuzz class A { public method(B b, C c); } Observations K8S Micro-Fuzzing AC Sanitization a, b, c = TestHarness(method) Threshold ? a A Runtime(a.method(b, c)) ? b B Runtime(x.method(y, z)) > ? c C a.method(b, c) 6

7. Distributed Micro-Fuzzing Input Output Synthesis and Validation Message Broker Micro-Fuzzing EyeVM OpenJDK AC Witnesses ?Fuzz Observations K8S (a, b, c) (a , b , c ) (a , b , c ) A.method(B, C) Method Under Test n 1 Population Generations Genetic Algorithm Cross-Over Mutation 7

8. Distributed Micro-Fuzzing Input Output Synthesis and Validation Message Broker Instantiating Seed Inputs EyeVM OpenJDK AC Witnesses ?Fuzz Observations K8S Small Recursive Instantiation (SRI) Identity Value Instantiation (IVI) ? = 0 ? new D(int) new A(D, E) a.method(b, c) 8

9. Distributed Micro-Fuzzing Input Output Synthesis and Validation Message Broker Synthesizing Test Cases EyeVM OpenJDK AC Witnesses new D(10) new E( a ) ?Fuzz Observations K8S new A(D, E) new B(179) new C(-1) a.method(b, c) public static void main(String argv[]){ 9 }

10. Distributed Micro-Fuzzing Input Output Synthesis and Validation Message Broker Micro-Fuzzing Evaluation EyeVM OpenJDK AC Witnesses ?Fuzz Observations K8S Library No. AC Bugs Detected AC Bugs Confirmed Methods Covered Throughput Methods Both IVI SRI Both IVI SRI Both IVI SRI IVI SRI 91,632 6 8 13 5 8 13 23,818 2,780 1,439 4,389,675 3,092,866 JRE 67,494 34 6 15 5 0 0 8,064 847 1,162 3,608,741 3,172,502 STAC 239,777 46 38 56 46 38 56 66,987 2,622 1,770 5,906,687 5,591,106 Maven 10

11. AC Vulnerability in the JRE If an adversary can influence the value of s or t, they can trigger DoS. import java.math.BigDecimal; BigDecimal x = new BigDecimal(s); BigDecimal y = new BigDecimal(t); x.add(y); Computing new BigDecimal( 1E2147483647 )).add( 1E0 ); Takes at least an hour to complete on every major implementation of the JVM! 11

12. Impact of BigDecimal Findings Affects all widely used JVM implementations Disclosed our findings to 3 vendors IBM J9 Proof of Concept (PoC) terminates after running for 4 months Issued us a CVE for our findings Oracle OpenJDK PoC runs in an hour Credited us in a Security-in-Depth Issue Google Android PoC takes over 24 hours to run Stated the issue falls outside their definition of DoS vulnerabilities 12

13. Summary Introduced Micro-Fuzzing Presented HotFuzz Prototype implementation of micro-fuzzing for Java libraries Automatically detects AC bugs Introduced strategies for generating seed inputs for micro-fuzzing IVI Identity Value Instantiation SRI Small Recursive Instantiation Micro-fuzzing detected 158 AC bugs in our evaluation artifacts Showed how an AC bug in production code can trigger DoS 13

14. Thank you! 14