Software Fuzzing: What, Why, What next?

Shachee M
6 min readSep 20, 2021

--

Software development is a manual process and, more often than not, is the work of one or more developers with varied expertise and experiences. The process of constant writing and re-writing of software with human involvement leads to the introduction of vulnerabilities in the code. Although modern software development practices emphasise strict review processes to ensure correctness and remove inadequacies from released pieces of software, these vulnerabilities invariably creep in. Reasons for this include the sheer size of the applications, inter-connected components sourced from multiple development environments and strict timelines that the developers operate on.

“Vulnerabilities exist in all types of software. Several versions of the Microsoft Windows operating system were open to the WannaCry attack. For instance, the popular open-source web browser Firefox has had more than 100 vulnerabilities identified in its code each year since 2009. Fifteen different vulnerabilities have been identified in Microsoft Internet Explorer browser variants since the start of 2017.”[1]

RFC 2828 defines a vulnerability as a flaw or weakness in a system’s design, implementation, or operation and management that could be exploited to violate the system’s security policy[2].

Once a vulnerability is identified, an adversary can exploit it to gain control of the application environment and perform tasks that the benign application never intended to. For example, they can elevate user privileges, create network connections to transfer sensitive information, create backdoors or stealthily monitor the system for launching an attack in the future. Thus vulnerability detection and fixing is an essential and continuous process in an application’s lifetime.

Fuzzing Process [3]

Fundamentally, fuzzing involves generating random input samples and feeding them to the application. Hoping that one such random input would take a path with some vulnerability and trigger it making the application misbehave or crash.

Conventionally, fuzzing is an automated process of looking for software bugs in an application. The random data generation involves creating permutations of an initial seed fed into the program as user input. Multiple techniques have emerged in the last three decades that perform focused and formalised testing to generate reproducible sequences. Sophisticated tools have also been proposed that use genetic algorithms to link input to observed application behaviour.

Categorising Fuzzing techniques

On a broader level, fuzzing tools (fuzzers) can be classified according to their dependence on visibility into the target application source(SUT). There are three categories: Black box, grey box and white box fuzzing. White box fuzzers assume complete access to the source of the target. They thus can modify the input data to steer the application into parts that have not been previously traversed. Grey box fuzzers do not have access to the target source. Still, they can perform program analysis to gain insight into the application. Black box fuzzers operate with no knowledge about the source and can only observe the final program output (or crash).

On another front, fuzzers can also be classified based on the search strategies adopted to explore the target application. A fuzzer could either perform directed fuzzing or coverage-based fuzzing. While directed fuzzing has information about target paths within the application that need to be tested, coverage guided fuzzers try to cover as many control paths as possible.

Security community in recent years has come up with several fuzzers; From the user’s perspective, some characteristics should be weighed upon before deciding to use one.

  1. Target vulnerabilities. On the one hand, a fuzzer could be used to focus on excavating a pre-identified set of vulnerabilities. In contrast, a generic fuzzer would look for any deviation from the expected behaviour. While the latter case would essentially encompass the vulnerabilities identified in the former, the high time and resource requirements for the generic fuzzers often outweigh its benefits.
  2. Input Model: Generating a valid set of input data is one of the most important features of a fuzzer. The generation process requires understanding the target application and structuring the input with a set of constraints in mind. The data generation process is more time consuming, and thus fuzzers may or may not use input modelling.
  3. Mutation: Mutation is the process of generating the next set of input from the current ones. The valid input is mutated predictably and fed into the application. One such mutation could be flipping the least significant bit in the current valid input.
  4. Guidance: The input samples generated by the fuzzer must be guided under application and coverage specific constraints. Behaviour-specific guidance would aim towards exploring more vulnerabilities. At the same time, an anomaly-specific one attempts to maximise path coverage in the application.
  5. Monitoring: The definition of anomalous behaviour differs among fuzzers. While some might consider a crashing/misbehaving application anomalous, some perform fine-grained monitoring into register values and instruction pointers. An advanced attacker might prevent crashing the application while carefully steering the application in malicious ways[4].
  6. Fuzzing completion: According to the goal of the fuzzing process, the fuzzer might terminate after identifying a minimum number of vulnerabilities (or the search space exhausts). While in case of coverage-guided fuzzing, when the set proportion of application paths are successfully executed.

As mentioned, choosing which fuzzing technique/strategy to use requires a deep introspection into the problem/application under consideration. We here briefly discuss three popular fuzzers followed by a table indicating the differences in design under the aspects detailed previously.

American Fuzzy Lop (AFL)[5] is one of the most popular coverage-guided fuzzers. AFL uses mutation to generate new input data and aims to explore previously uncovered paths. AFL also employs a unique feedback mechanism that utilises the behaviour of the previous run to guide the following input. Every run of the application identifies the set of edges explored. The input is considered interesting only if it traverses an edge not previously traversed.

Radamsa[6] is a blackbox fuzzer and does not require even the type and format of input to generate input samples. It can be complemented with analysis techniques to trim down the space in which the input samples are generated. Radamsa does not support any feedback or behavioural monitoring of the application, thus requires additional user-defined scripts to guide the input generation. This is the main difference between AFL and Radamsa.

SMARTEST-SWE[7] is dedicated to exposing a well-known vulnerability called buffer overflow. A buffer overflow vulnerability presents the ability to overwrite control data in the application stack. They essentially enable the attacker to perform arbitrary code execution, which is one of the most severe attacks. A static code analysis phase accompanies test data generation, and genetic algorithms are used for the iterative regeneration of new data samples.

The table[8] summarises the differences among the three fuzzers:

Conclusion
Fuzzing has become an essential component of the software testing process lately. The main reasons include the ease of setting the testbed, a variety of design options to choose from as per requirement, and the ability to unearth software vulnerabilities that are difficult to catch during the review process. Although it is not a new area, there are several open problems. Researchers are working towards optimising the input generation process, making more robust feedback loops, reducing the time taken for fuzzing and using fuzzing to newer domains like hardware.

References

[1] What Are Software Vulnerabilities, and Why Are There So Many of Them? https://www.scientificamerican.com/article/what-are-software-vulnerabilities-and-why-are-there-so-many-of-them/

[2] Internet Security Glossary https://datatracker.ietf.org/doc/html/rfc2828

[3] Fuzzing: a survey https://cybersecurity.springeropen.com/articles/10.1186/s42400-018-0002-y

[4] The Geometry of Innocent Flesh on the Bone: Return-into-libc without Function Calls (on the x86) https://hovav.net/ucsd/papers/s07.html

[5] American Fuzzy Lop https://github.com/google/AFL

[6] Radamsa https://gitlab.com/akihe/radamsa

[7] Constraint-based Testing for Buffer Overflows www11.informatik.uni-erlangen.de/Forschung/Publikationen/DECSoS2018Smart.pdf

[8] Comparative Evaluation of Security Fuzzing Approaches http://www11.informatik.uni-erlangen.de/Forschung/Publikationen/DECSoS2019Smart.pdf

--

--