Towards Effective Performance Fuzzing

Fuzzing is a process that generates a large number of inputs to provide to a program with the intent to identify bugs. These inputs are generated by a fuzzer following some set of rules. Fuzzers typically focus on correctness bugs, however, also of importance are bugs that lead to poor performance. For example, bugs that cause a large number of hash collision can significantly reduce the performance of hash tables from amortized O(1) to O(n). This is a security vulnerability as the reduced performance can lead to loss of availability in applications. Examples of this type of vulnerability has occurred in the implementation of Python.

Importance

Performance fuzzers typically use a metric called path length (the number of basic blocks executed). This work identified that this is an issue because path length does not always correlate with the amount of time a program will execute for. This can occur when operations within a basic block cost a different number of CPU cycles to execute.

Secondly, performance fuzzers limit the search space for inputs. This is a necessary trade-off between time spent executing inputs and the size of the search space explored. However, this work found that default limits on input size and timeouts was overly limiting, meaning that potentially interesting inputs were not explored.

Perspectives

Understanding what metrics to use and what are good default parameters to set are hard choices. Different users will have different requirements, so different configurations will benefit them. However, it is important that appropriate metrics are used and that an appropriate search space is explored before conclusions are drawn. This work is an initial step to improving the state of performance fuzzing.

Presentation