A Topological Model for Applications in Fuzzing

Abstract

In this thesis, we introduce a topological model of dependencies motivated by applications in fuzzing. The model we define in Chapter 2 is framed within the language of finite topological spaces, partially ordered sets and simplicial complexes. In Chapter 3, we extend the theory to address situations where information is evolving dynamically and probabilistically, borrowing ideas from the general framework of persistence theory and Topological Data Analysis. In Chapter 4, we define algorithms to compute the relevant quantities and provide coarse bounds on their time complexity.

Our model is applied to two problems in the fuzzing literature. Firstly, we reformulate the challenges of coverage-based grey-box fuzzing in Chapter 5 as a question about dependency relationships. We define a high-level schematic for the alteration of the popular afl algorithm and perform a case study that supports the use of our conceptual framework. Our second application is the analysis of call-stacks generated by a fuzzing campaign in Chapter 6. We examine the characteristics of a large data-set of call-stacks and use our model to define a recovery scheme they have obscured or incomplete information. Show more