My Explorations Into Deep Learning: How to apply DeepLearning to Fuzzing: Playing Chess vs Fuzzing

To continue exploring the connections between Deep Learning and Fuzzing, here we will identify the similarities between DL and Fuzzing.

1. Given limited time and computing resources: you have to choose the best option to take. Identify as many alternative options as possible.

2. Study your opponents: understanding the applications, understanding its different inputs, understanding the distributions of the inputs vs output and its variations. Visualization should help here.

3. Brute force techniques is very tempting, or even probabilistic + brute force, but still, brute force is primitive. Instead of brute force, another way is the actor-critics algorithm [5]. Or perhaps like reinforcement learning. The "actor" is the fuzzer that will try to generate the input for the application to be fuzzed. The "critics" here is the analyzer that will examine the application state - how many crashes, how much have been covered, how much memory used etc.

4. With ref to (2) above, programming have many pattern: eg how to use locks to share resources usage concurrently etc. And so in fuzzing, you have to take advantage of this pattern: how to break it? what if it is not properly implemented? So here is where visualization can help: if the process of fuzzing can be visualized, how the input is distributed, how it is generated, how the output depends on the input etc.

5. End-game database - this is good for brute force, but it is not good for intuitive game play. So in fuzzing, the corpus database may not be useful: the larger it is, the more time it takes to walk the database and contribute additional items to the database, vs a more intuitive fuzzing that generate the inputs and fuzzed it immediately.

6. Many times generation of inputs to fuzzing is the key problem: how to generate the inputs so as to discover new bugs. The input pattern will vary from API to APIs, applications to applications. Sometimes there is a pattern to discover, sometimes patterns are very complex to uncover - which means near to totally random inputs is needed to uncover these bugs. Patterns in the applications which can be used for feedback / learning / critics are coverage data, crash dump, instabilities of applications, memory usage instability, CPU consumption patterns etc. Identifying the patterns of the progress of these variables and its changes can also be used as pattern feedback.

7. Expanding on (6) every input will generate a trace of coverage data as output [12,13,14,15,16]. Among the state of art tool for coverage-based fuzzing right now is AFL [16]. So if the coverage can be combined with more data like program state, memory consumption rate, proximity to previous known crash dump (by comparing the stack trace proximity) it is possible to modify the input in a way to nudge the output towards maximizing the coverage, or memory consumption, or proximity to previous bug stack trace etc - assuming that the transitioning is a continuous change.

In conclusion, DeepLearning, and Reinforcement Learning offers a lot more opportunities in the area of fuzzing, which is sometimes very much dependent on luck, and many times difficult to get the input right, as is a exponentially explosive in combination possibilities.

References:

My Explorations Into Deep Learning

Dec 16, 2017

How to apply DeepLearning to Fuzzing: Playing Chess vs Fuzzing

No comments: