Design and implementation of an Evolutionary Fuzzer for assembly program

This thesis describes the design and implementation of Byron, an extensible, self-adaptive, general-purpose Evolutionary Fuzzer, capable of fuzzing complex test-program in assembly language. Evolutionary Algorithm (EA) principles and techniques were first described by John H. Holland in the 1960s; in 1990 John Koza described Genetic Programming, a new approach that differs in the type of representation, using trees, and in the application area. From these roots arise various alternative representations of GP, Linear Genetic Programming (LGP), Cartesian Genetic Programming (CGP), and Graph Genetic Programming (GGP); the last one, which is used in Byron implementation. The tool represents the genotypes as Directed Acyclic Graphs (DAGs), which allow the evolution of the graph without going through an intermediate encoding, but directly manipulating the graphs. Byron, through the use of multiple genetic operators and a self-adaptation mechanism, is able to perform fuzzing of programs written in assembly language; this is due to its framework that allows the encoding of candidate solutions employing typed Directed Multi-Graphs, characterized by the possibility of having multiple edges that connect the same couple of vertices. Moreover, this graph encoding features two edge types, “Framework” or “Link”, that are bound by the type of vertices they connect. Experiments show the applicability and performance of this tool on the RISC-V Instruction Set Architecture, with results that can be extended to any general programs written in assembly language.