Ember-IO: Effective Firmware Fuzzing with Model-Free Memory Mapped IO

Attempting to re-host and fuzz monolithic binaries creates a search space problem because of the need to provide fuzzing inputs to a large number of peripheral registers to reach new code or program state. The millions of possible values for each register read and potentially thousands of register reads through a program’s execution renders it difficult to effectively mutate inputs to reach new code. Hence, recent approaches for automating re-hosting, P²IM (p2im, ) and µEmu (uEmu, ), attempt to reduce this search space by providing categorisations of registers. Data registers are sourced from the fuzzing input, while the other categories of registers are provided with fixed values or treated as memory–these non-data categorised register accesses are effectively excluded from the input search space. This presents a new problem when miscategorisations occur as techniques developed rely on approximate heuristics to generate such models. Further, by removing the register from the fuzzable space, exploration can be limited if valid values are not presented. One example consequence occurs when fixed status values prevent the execution of error handlers. In contrast to explicitly modelling peripheral register types, the most recent method, Fuzzware (fuzzware, ), directly reduces the search space. Fuzzware utilizes symbolic execution to determine the bits within a register that can influence firmware control flow to allow it to precisely model the necessary bits in the register to fuzz.

We propose an effective and simpler alternative to the search space problem. We focus on improving the fuzzer’s ability to generate values likely to progress execution (overcome hurdles in firmware initialisation and reaching deep code paths) and avoid time consumed on mutating inputs that are functionally equivalent to other fuzz test cases. We briefly describe observations leading to the key techniques we propose, below.

1. (1)

   We observed very high path counts on firmware with existing fuzzing frameworks; this is despite the relatively small program size or block counts. The disparity is due to existing coverage instrumentation methods failing to represent code-coverage when applied to monolithic firmware. Thus, a fuzzer’s input generation method informed by code coverage feedback expends unnecessary effort searching the large input-space without making progress to explore hitherto unseen code. Notably, existing works (binaryonly_instrumentation, ; collafl, ; fullspeedfuzz, ; tortoisefuzz, ; aflsensitive, ) in the desktop application space have provided evidence of the importance of providing high-quality instrumentation for coverage guided fuzzers. Therefore, we propose a new code coverage instrumentation technique to allow for more accurate identification of truly unique paths we refer to as Functionally Equivalent Coverage InstRuMentation (FERMCov). Our approach is motivated by the insight that control flow through an embedded program is often interrupted by hardware triggered events, behaviour not typical in desktop applications. Therefore, we propose separating the coverage instrumentation for interrupt control flow from the rest of the firmware control flow.

2. (2)

   Recent studies (p2im, ; uEmu, ) have identified the need for certain registers to repeatedly report specific values in order to execute firmware correctly and chosen to fix register values (use immutable inputs). But, fixing the values of registers effectively over restricts the search-space and can prevent testing of error handlers; importantly, error handlers were identified as a common source of bugs (ifizz, ; fifuzz, ). Expounding upon this insight we propose the peripheral input playback technique to: i) exploit the knowledge that many peripheral registers often repeatedly return the same value under typical execution conditions; and ii) benefit from mutated inputs to overcome restrictions on triggering of error handlers.

Through our efforts, we make the following contributions in this study:

• •

  We introduce functionally equivalent coverage instrumentation (FERMCov) and peripheral input playback (PIP) techniques to improve the performance of monolithic firmware fuzzers by facilitating a more effective search through the input-space to make progress—overcoming hurdles imposed by MMIO accesses and reaching deep code paths. The techniques we propose provide a different approach to current model based methods and can be understood as addressing the problems arising from the large input search space created by the diverse and large number of memory mapped peripherals in firmware fuzzing.

• •

  We implement our techniques in Ember-IO—a highly effective fuzzing framework realised in AFL++-QEMU that simplifies re-hosting based fuzzing of monolithic firmware whilst providing a new, model-free approach for fuzzing.

• •

  We demonstrate the techniques we propose are generalizable and highly effective in experiments with a diverse set of 21 real-world binaries as a benchmark, and comparisons with the existing state-of-the-art re-hosting method for monolithic firmware—Fuzzware. When compared to Fuzzware, Ember-IO provided up to 255% improvement in blocks covered, and discovered 6 bugs in the real-world firmware not previously uncovered by existing embedded device firmware fuzzers.

We open source¹¹1GitHub Repo: https://github.com/Ember-IO/Ember-IO-Fuzzing Ember-IO, the experimental datasets, and bug analysis to support reproducibility, further improvements and advance the field of firmware fuzzing.

Embedded systems running on microcontrollers often do not rely on a typical operating system, instead executing a single monolithic program that manages the hardware initialisation, peripheral access, the desired functionality and, in some cases, a minimalistic system to manage tasks.

Control:

Used to configure the peripheral device. An example of this is the baud rate of a serial port.

Status:

Used to identify the current state of the peripheral. Bits within a status register may represent whether the peripheral has received new data, or certain errors occurred in the peripheral’s operation.

Data:

Source or sink of data received or sent by the peripheral. Registers such as these may contain the last reading by an ADC (analog to digital converter), or the byte to be written to a serial port.

While it is common for a register to be used as a single type, in some cases, different bits within a single register may serve different purposes, representing different types. Accesses to memory mapped IO is easily identifiable, as architectures can define designated regions specifically for this purpose. For example, ARM Cortex-M devices reserve the region from 0x40000000 to 0x5FFFFFFF (cortexm4_manual, ) for peripherals. Registers of each type are scattered throughout this region, with adjacent registers being associated by peripheral rather than type.

Peripherals may also interact with the MCU using DMA. When interacting using DMA, the peripheral uses a DMA controller to write directly to the memory of the MCU. The data will be present in memory prior to the firmware reading it. This is more common for higher bandwidth peripherals.

An additional form of input to embedded systems is hardware interrupts. While they do not provide data, they signal an event has occurred. This causes the processor to jump to an interrupt handler, where the signal is then processed, and the processor returns to the code being executed prior to the interrupt.

In order to fuzz firmware effectively, suitable inputs must be provided from all peripherals used in the loaded firmware to pass initialisation checks. Furthermore, appropriate status register values must be provided to allow continued inputs from data registers. These factors present a uniquely challenging setting for rapid test automation of embedded system firmware.

Fuzzers typically take a sample input and progressively mutate this input to trigger different functionality within the program under test. Many fuzzers use knowledge of the code covered in each test to guide the fuzzer to new sections of code. Interesting cases that trigger a new code path are saved to a queue to undergo further mutation. One way in which the code coverage can be tracked is through running the binary inside of an emulator. As the emulator processes each new basic block of instructions, it records this in a map. After executing an input, the fuzzer can analyze this map to determine if there are new entries in the map indicating that new code has been reached.

Popular fuzzers such as AFL (afl, ) keep track of the edges visited during program execution to build this map. An edge is a pair consisting of an origin and destination program counter, representing a jump from one block to another. Any test case containing a previously unseen edge will be considered interesting and added as a new path. Test cases that significantly increase the number of times an edge is hit in an execution are also saved for further fuzzing.

Testing a register to infer the readiness of a peripheral device to accept or deliver new data is a very common occurrence during firmware execution. For example, according to an STM32 reference manual (stm32_reference, ), a USART status register includes bits on whether the line is idle, read data is pending, the transmit buffer is empty, the last transfer is complete, and bits representing different errors. Often, such register values need to be repeatedly set to deliver data to the firmware to execute code that consumes the data. Hence, the desire is to primarily generate inputs that mimic typical use cases where data is available and no errors are reported to reach new or deeper code blocks.

Consider the simplified example shown in Listing 1. To continue providing input to the firmware to execute code that processes the data, without repeatedly calling an error handler, the peripheral must have the RX_NOT_EMPTY bit set, with each of the error bits unset. While generating a single input that matches this pattern is trivial, repeatedly generating values following this pattern given the wide search space represented by all the possible register values is challenging. Consequently, it is more likely for a fuzzer to generate inputs to repeatedly trigger the Error_Handler than those that result in the firmware receiving data (i.e executing USART.Read()). Thus, repeating an appropriate register value is necessary to provide deep code exploration.

While the problem above demonstrates the need to repeat values to continue to provide new input to the firmware, it can also be necessary to succeed in the initialisation phase. Consider Listing 2 that highlights an initialisation challenge encountered in the Drone firmware tested in our evaluation. This function waits for the peripheral to report it has finished transmitting a byte, then returns OK. If the correct bit is not set prior to a timeout, or no acknowledgement was reported by the peripheral, an error is returned. While setting a single bit is enough to overcome any returned errors, this function is called dozens of times during initialisation. Even a single reported failure during initialisation causes the firmware to abort. Thus, repeatedly reporting the I2C_TXEMPTY bit as set is necessary to allow fuzzing of the full firmware.

We recognize that prior work has also established the benefits associated with repeating values for reads to the same register. For control registers, P²IM returns the last value written by the firmware, and µEmu does the same for Tier 0 registers. Additionally, a fixed constant value is returned for status registers in P²IM and Tier 1 registers in µEmu.

However, we observe some cases where constantly repeating values is not desirable. Consider Listing 3 showing an excerpt of code from the serial controller for a CNC firmware (cnc_snippet, ). To proceed through a call to the serial_reset_read_buffer function, the serial status register must report that no bytes are available to be read in the uart_tstc function. However, the uart_tstc function is queried to check for received data. Hence, to both initialise and take input from the serial port, status registers must have the ability to change, even at the same point (or program counter) in the firmware. In addition to the ability to trigger error handlers, cases such as this motivates allowing the fuzzer to manipulate the values in status registers.

Based on the observation that repeated values are often needed to reach deep code paths, and the knowledge that generating many of these values is time consuming, we propose a method to define and inject value repetitions for a register.

In contrast to strictly employing the fuzzer generated input stream for register values, we use parts of the input stream to define a repetition scheme that influences the register behaviour.

The repetition scheme is defined based on subsections of the fuzz input, hence, random mutations by the fuzzer can still control the number of repetitions of a register value to be arbitrarily large or small, provided the fuzzer generated input continues to improve coverage. Importantly, our approach allows for repeating of values as often as determined by the fuzzer without eliminating the potential to mutate values. Our approach aims to simplify the fuzzer’s process of generating repeating sequences for a register, but does not prevent any possible sequences of values from being generated.

This allows the sequence of status register values necessary to make progress through the code described in Listing 3. Additionally, by allowing the fuzzer to define repetitions of a register, valid values for the status registers in Listing 1 and 2 only need to be solved once. Repetitions allow later accesses to continue to retrieve valid values, reducing the amount of fuzzer generated data required to overcome these hurdles which addresses the search space problem.

The number of paths identified by existing fuzzing frameworks is large compared to the size of the program. We observed path counts several times the block count reached in the program. This indicates that a large number of unique edges between different blocks have been reached. Given that function calls to predefined functions represent a single edge, and branch instructions have two potential edges, depending on whether the branch is taken or not, the excess of identified paths suggests coverage information is uninformative and is being influenced by other aspects of the framework.

One of the aspects unique to embedded software is the dependence on hardware interrupts. Hardware interrupts trigger an interrupt handler—generally a small piece of code that updates the state to influence later executions when the state is checked—then returns to the point in the program prior to the interrupt being triggered. The exact point in the program where the interrupt is triggered is not usually important; as the state modified by an interrupt is only checked periodically. Triggering the interrupt anywhere in this period will lead to the same outcome. Existing approaches such as P²IM, µEmu and Fuzzware (fuzzware, ) periodically trigger interrupts in a round robin approach after a number of basic blocks have been executed. The point in the program where the interrupt is triggered can be influenced by the input, as the input affects the path taken, and by extension, the number of blocks executed before reaching a point in the program. Hence, the fuzzer will consider each unique point for triggering an interrupt a new interesting path, as it contains a new edge.

Figure 4 illustrates an example with three potential pairs of edges caused by triggering an interrupt at varying points within a function to illustrate the problem. Depending on which of the three blocks within this function the interrupt is triggered at, a distinct new pair of edges will be created. For example, triggering an interrupt at results in an edge from Program Block 1 to Interrupt Handler Start, and a returning edge from Interrupt Handler End back to Program Block 1. Similarly, interrupts can be triggered at points nd with their corresponding edges now being present in the coverage information reported to the fuzzer. Consequently, it is feasible for three paths to be considered unique by the fuzzer, corresponding to the exact moment the interrupt is triggered. Given that the vast majority of blocks do not read the system state and will not be directly influenced by the interrupt, these paths are all functionally equivalent.

We expect this problem to be most prevalent when loops are executed. In the case where the input defines the number of iterations of the loop, every value could potentially be considered a unique path, even if no new code is covered, as the point after the loop that the next interrupt occurs will change. In the case where the loop is a fixed number of iterations, by taking or not taking branches within the loop, the number of blocks executed in each iteration can be varied by the input, potentially leading to the same outcome.

A consequence of the uninformative coverage is poor scheduling of inputs (queue entries), as there are significantly more inputs to schedule, many of which are very similar or functionally equivalent. Hence, time consumed applying mutations to these inputs is wasted if an equivalent entry has already been thoroughly explored.

We propose changing the code coverage instrumentation employed by the emulator during fuzzing to remove functionally equivalent queue entries. FERMCov separates the coverage instrumentation for interrupt control flow from the rest of the firmware control flow. The edges from both interrupt and non-interrupt coverage are then aggregated to a single coverage map. As a result, the context of an interrupt is obscured from the fuzzer’s perspective. The coverage instrumentation technique prevents otherwise uninteresting inputs from being saved by the fuzzer. In the case where triggering the interrupt influences the system state, we expect that new code blocks would be executed, the corresponding edges would then ensure that the new path is saved and added to the queue. However, removing excess paths, we can more efficiently focus on paths that trigger new, deeper code.

We implement the technique we refer to as peripheral input playback within the MMIO manager of our framework (Figure 5). We assign our own functions for handling reads and writes to the peripheral memory regions. Within these memory operation handlers, we implement the value repetition scheme described in Algorithm 1. Prior to a register being read, a small value from the fuzzer generated input stream is read; we employ a two-bit value in our implementation. If this two-bit value is equal to 3 (REPEAT_CONST), instead of responding with the next value in the input buffer, the previous value from this register is retrieved from the peripheral memory store and returned. The previous value represents either the value returned on the last read, or the value last written by the firmware—whichever was more recent. We aim to minimise the number of bits used for this purpose to reduce overhead. However, we do not want to excessively force repetition. The two-bit value comparison is trivially solvable by the fuzzer, and allows triggering only in the minority of cases, preventing excessive repetition.

Given a random input test case, we expect this playback to be triggered on one in four register accesses when this implementation is used. We maintain a list of all registers encountered in the current test case, representing periph_memory_store in the given algorithm. In the case where a repetition is requested on the first access, we assume an initialisation value of 0. To maintain byte alignment on the input stream, and improve spatial locality of related bits, we read 32 bits from the input stream rather than 2 bits when determining if the value should be replayed. These 32 bits are used for the next 16 reads of that register. The improved spatial locality has a unique impact when considered in combination with the types of mutations a fuzzer can make. One mutation type in AFL based fuzzers is to replace an existing value with one of a set of predefined interesting values. Amongst these values are 0 and -1. When interpreted as binary data, the 32-bit value 0 would introduce no repetition and -1 would result in all of these reads playing back the previous value. For a firmware that repeatedly polls a 32-bit register for an appropriate value, only 8 bytes are required to report the correct value 16 times (4 bytes for the value, and 4 bytes for repetition information). Without this technique, 64 bytes of valid fuzzing input would have to be determined to overcome the same obstacle.

Our implementation of FERMCov modifies the existing code-coverage instrumentation in AFL++’s QEMU mode based on the CPU state. As shown in Algorithm 2, any jumps to an interrupt handler have the last_int_block variable set to null during the previously executed program block. Therefore, from the perspective of the fuzzer, all jumps to an interrupt handler are seen as from the same location. The return jump when exiting the interrupt handler is entirely excluded from the coverage map. By keeping the value of last_program_block untouched during the interrupt, continuity of the observed non-interrupt edges can be maintained.

We determine the interrupt state by probing QEMU’s emulated Nested Vectored Interrupt Controller (NVIC). This implementation does not require any comparison between different paths in order to remove functionally equivalent paths, instead relying on the coverage map checks already present at the end of each executed test case, minimising processing overhead.

To address a couple of firmware specific problems, we make some additional extensions to our implementation. The first of these problems is the use of power saving features. Firmware may put the CPU to sleep, and wait for a hardware interrupt to occur before proceeding. In emulators such as QEMU that implement these instructions, this can be problematic. Our interrupt manager is based on the design used in P²IM (p2im, ), that periodically triggers interrupts based on the number of blocks executed by the emulator. But if the CPU is sleeping, no further blocks will be executed, thus no interrupt will be triggered to wake the CPU. We extend the interrupt manager to trigger an interrupt when the CPU enters sleep mode.

Additionally, we observed some firmware with extremely long initialisation routines, far exceeding the time in the main program loop. To ensure performance is not compromised in this case, we allow the fuzzer to operate with multiple forkservers operating at varied depths in the firmware under test. A random forkserver is chosen before each execution, allowing some tests to run from after the initialisation stage is complete.

To verify the usefulness of the techniques we explore, we take a sample of existing firmware from previous works and introduce one technique at a time to measure the improvement in block coverage. We selected the Drone and 3D printer firmware based on past performance in existing firmware fuzzing frameworks (p2im, ; uEmu, ; fuzzware, ). The Drone binary provided some of the highest coverage in each of the existing frameworks, while the 3D Printer binary consistently performed poorly. By extension, we expect the peripheral accesses within these firmware to represent a mix between types already well recognised and dealt with in previous fuzzing approaches, and those that pose a challenge to these approaches.

The configurations are as set out as described at the beginning of Section 4. The Baseline represents fuzzing campaigns found with our AFL++ QEMU mode modified to allow embedded system fuzzing, without additional techniques applied. Next, we introduce our peripheral input playback technique. Subsequently, we combine peripheral input playback with FERMCov. Each test run was executed for 24 hours. Five runs were completed for each test.

We consider the existing state-of-the-art emulation based embedded fuzzing framework Fuzzware (fuzzware, ) for our comparison. Five trials are performed for each firmware, which are executed for 24 hours as in previous works. Our tests were conducted using an AMD Threadripper 3990X and 256GB of RAM. We employed the suite of binaries used to compare coverage in µEmu (uEmu, ) and Fuzzware (fuzzware, ) to generate our experimental results.

In addition to running Fuzzware (fuzzware, ) as released with default settings, we extend Fuzzware with our FERMCov technique to remove functionally equivalent paths. We do not implement peripheral input playback as it conflicts with Fuzzware’s techniques, which only populates a subset of the bits in each register depending on the model for that register and program counter (PC) pair.

For the firmware that interacts with a DMA enabled peripheral, we manually configured the DMA related registers as passthrough following Fuzzware. The XML Parser binary required the disabling of interrupts in the emulator, as configured by prior works. All other firmware was successfully run without modification to the firmware or manual configuration of peripherals.