Detection of security vulnerabilities in XML-based systems with fuzz testing using different mutation strategies

Fuzz tests are known as a set of automated processes used to detect crashes and security vulnerabilities in software systems. In general, fuzz tests are divided into three; black box tests, white box tests and gray box tests. In terms of the generation of input data used to initiate fuzz tests, fuzz tests are divided into two; one is grammar-based and the other one is mutation-based. While the grammar-based fuzzing generates inputs from a specification and takes complex structured inputs, mutation-based fuzzing generates inputs by modifying well-formed seed files and abstract syntax trees randomly. There are fuzzing approaches working grammar or mutation based, but there are not enough case studies comparing their crash detection capabilities. To add to the body of empirical evidence in this area, this case study compares gray-box fuzzing with different mutation strategies to evaluate their effectiveness in three aspects: fault detection effectiveness, fault detection performance and types of faults detected. Also we investigate the affects of different seed generation techniques to fuzzing effectiveness. We perform the fuzzing executions on three Systems Under Test (SUT); XML parsers, Libxml2, Apache Xerces and Expat. To execute fuzzing, we use the well-known fuzzers AFL (American Fuzzy Lop) and Superion which have different mutation strategies. We carry out the investigations for finding the affects of seed generation to fuzzing by leveraging publicly-available seeds and the PCSG (Probabilistic Context Sensitive Grammar) based seeds. In terms of fault detection effectiveness and performance, we measure the number of crashes, and the number of corpus files generated. With respect to mutation strategies used, our results demonstrate that the bit/byte-level mutation strategy detects more crashes than tree-level mutation strategy. According to the fuzzing results, PCSG-based seeds help detect higher number of crashes than publicly-available ones. In terms of corpus file generation, while there is less corpus generated for PCSG based seeds compared to publicly-selected ones, bit/byte level mutations result in more corpus when compared to tree level mutation. Empirical results show that crash detection capabilities of fuzzing differ significantly based on the mutation strategy it uses. Fuzzing is an effective and popular technique for finding crashes and vulnerabilities in an automated way. The system is tested with the continuous and random test cases generated by another program. At the same time, the system is monitored to expose any defects while processing this input. Therefore, input generation is important for the fuzzing process since every fuzzer should automatically generate test cases to be run on the execution engine. There are two fundamental forms to create input and test scenarios in fuzz tests: mutation- and grammar-based input generation. While the first is aware of input format, the latter is not. The former includes transformations on a reference input, while the latter employs system specification. Mutation-based fuzzers mainly lack coverage and are less effective, with inputs that are different from what is expected. In mutation-based approaches, the modification on the input is performed at the bit/byte level. These methods randomly flips, deletes or copies some bits to generate new files. However, random bitflips are not likely to produce valid files for applications processing complex file formats. Therefore, mutation-based fuzzing is not well suited for programs that handle highly structured inputs (e.g. XML, JavaScript). Those types of programs take and process inputs in three basic stages; syntax parsing, semantic checking, and application execution. Most malformed inputs produced by mutation-based fuzz tests fail at syntax parsing and are therefore rejected at an early stage of processing. Grammar-based fuzz tests generate entries according to a well-defined specification, such as input models or context-free grammar that determine the format and integrity constraints of data pieces. In contrary to mutation-based approaches, grammar-based approaches pass the syntax parsing stage in fuzz tests more easily. But most of the test cases produced by this method usually do not pass the semantic check. However, systematic generation of semantically valid test cases is often a highly expensive and difficult problem to solve. This is also a widely known issue for developing an intelligent fuzz testing tool which is aware of both syntactic and semantic features of the program. So, only a small fraction of the input produced in grammar-based fuzz tests can reach the application execution stage, where deep errors are hidden; therefore, most of the application code cannot be accessed and most of the crash inducing cases cannot be exposed. In order to overcome this issue, there are some approaches that work based on the PCSG (Probabilistic Context Sensitive Grammar). Those approaches use a large number of examples to automatically extract knowledge of grammar and semantic rules and then generate seeds that are expected to trigger crash inducing cases. It is claimed that since these smart seeds can pass the semantic parsing stage easily and reach out the application execution phase, it gains more chance to trigger the unknown bugs and crashes hidden in the tested application. For this reason, there is a growing need to show the effectiveness of the smart seeds generated in terms of a learning algorithm that they can outperform in terms of finding crashes compared to publicly-available seed files. In this paper, we address this need by making exhaustive comparison between these two types of seed files in terms of performing fuzzing executions for XML parsers that take highly structured inputs. Throughout this study, we use two main fuzzers, namely AFL and Superion, for the fuzzing executions. AFL is the state-of-the art gray-box fuzzer which functions based on CGF (Coverage Guided Fuzzing) principles. Superion uses a grammar-aware trimming strategy to trim test inputs at the tree level by using the abstract syntax trees (ASTs) of those parsed inputs. Whereas mutations in AFL are grammar-blind and works in bit/byte level, mutations in Superion are grammar-aware and functioning in tree level. It is also claimed that grammar-blind mutation strategies in AFL hinder the effectiveness and efficiency. On the other hand, Superion is well-suited for complex-structured input files meaning that it can produce valid inputs for fuzzing. In this sense, there is also need to compare between the bit/byte- and tree-level mutations to find out how they perform for generated and publicly available seed files. From this angle, our case study also involves comparing different types of mutation strategies and their effects on their crash detection capabilities. In addition to input generation methods and mutation strategies, another metric in fuzzing is code coverage. It is related with how far the fuzzing execution can reach out different parts of the tested program. Fuzzing tools need a helping function to evaluate the quality of the new input and guide the generation of this input. This helping function can be basically code coverage. In this context, there are some studies to guide gray-box fuzzing with mutation testing as a helping function. According to their study, mutation testing has shown to be an alternative to code coverage while generating effective corpus input files, meaning that a test corpus can be evaluated on its ability to detect artificially injected faults. Also the study uses the mutation score as a metric for evaluating fuzzing quality. This study for the gray-box fuzzing approaches is conducted based on the principles of case-study research. The nature of our case study is both "exploratory" and "improving" in that our objective is to find out what happened (in the process of developing the fuzz testing approach), to seek new insights, and to generate ideas and hypotheses for follow-up improvements (on the fuzz test approach) and research (the "exploratory" aspect). Furthermore, the study has "improving" aspects since we wanted to improve test effectiveness and efficiency of the "studied phenomenon".