Abstract

Bugs exist in hardware, such as CPU. Unlike software bugs, these hardware bugs need to be detected before deployment. Previous fuzzing work in CPU bug detection has several disadvantages, e.g., the length of RTL input instructions keeps growing, and longer inputs are ineffective for fuzzing.

In this paper, we propose Instiller (Instruction Distiller), an RTL fuzzer based on ant colony optimization (ACO). First, to keep the input instruction length short and efficient in fuzzing, it distills input instructions with a variant of ACO (VACO). Next, related work cannot simulate realistic interruptions well in fuzzing, and Instiller solves the problem of inserting interruptions and exceptions in generating the inputs. Third, to further improve the fuzzing performance of Instiller, we propose hardware-based seed selection and mutation strategies.

We implement a prototype and conduct extensive experiments against state-of-the-art fuzzing work in real-world target CPU cores. In experiments, Instiller has 29.4% more coverage than DiFuzzRTL. In addition, 17.0% more mismatches are detected by Instiller. With the VACO algorithm, Instiller generates 79.3% shorter input instructions than DiFuzzRTL, demonstrating its effectiveness in distilling the input instructions. In addition, the distillation leads to a 6.7% increase in execution speed on average.

I Introduction

CPU bugs are notorious. Besides the well-known Meltdown and Spectre [1], numerous bugs are reported, including the Pentium FDIV bug [2], Broadwell MCE bug [3], and Ryzen segfault bug [4]. All of them can cost the manufacturers millions or billions of dollars in mitigating and repairing the bugs.

Before CPU deployment, the circuits and RTL (register transition level) designs should be thoroughly verified. In software deployment, bugs can be avoided with timely patches. However, in the development of CPU, once deployed, it is nearly impracticable to remove the impact of hardware vulnerabilities. For example, the mitigation of Meltdown and Spectre only focuses on part of the mainstream products, due to the challenging balance among the mitigation itself, performance impact, and implementation complexity [5].

Previous work has made some attempts to detect CPU bugs [6, 7], both in static and dynamic techniques. Among them, verifying CPU with fuzz testing [8] is one of the most promising approaches [9, 10]. However, there are still several drawbacks to these techniques, and they extend to the following challenges.

Challenge 1: growing input length. The basic structure of the input instructions of the CPU consists of an instruction sequence. Interruptions and exceptions can be inserted to simulate the real-world execution of the CPU. Starting from a simple instruction, as the fuzzing process goes on, the length of input tends to increase. The speed of fuzz testing is the key to its success [11, 12, 13, 14, 15, 16]. Longer input instructions are catastrophic to the execution speed of fuzzing since longer inputs will spend more CPU cycles. More importantly, according to our analysis in the evaluation in Section V-C, coverage does not increase proportionally to input length. Therefore, we should come up with solutions to shorten the input instructions and improve the fuzzing efficiency.

Challenge 2: realistic interruption and exception handling. Interruptions and exceptions are common in the execution of the CPU. Simulating them in testing CPU can cover the corner cases of CPU verification. Previous fuzzing work mentioned considering interruptions in the design [10], but the approach is relatively simple. Exceptions are not simulated, and multiple interruptions and exceptions and their priorities are also not included. Missing these situations cannot simulate the real-world CPU execution and cannot cover all the CPU states.

Challenge 3: fuzzing techniques related to hardware. Fuzzing techniques are initially designed for testing software. Many customized approaches in fuzzing, such as program transformation [17] and process tracing [18], are also tailored for software programs. Especially in the critical steps of fuzzing, such as seed selection and mutation, previous fuzzing work did not combine fuzzing with hardware features well. For example, [10] did not consider seed selection when fuzzing the CPU. Not using hardware-related techniques cannot improve the fuzzing performance in testing CPU RTL.

To address the above challenges, we propose the following techniques.

Input instruction distillation based on a variant of ant colony optimization. To save the CPU cycles and improve fuzzing performance, we need to distill the inputs and shorten the input instruction length. The basic idea of input instruction distillation is to construct a subset of the original input set, which is shorter in length and can maintain the original coverage. Ant colony optimization (ACO) is one of the latest techniques for approximate optimization [19]. The algorithm simulates the routine of an ant colony to search for the shortest path to the target city. We use the idea of ACO to distill input instructions. We model the length of input instructions as the number of ants and the RTL circuits as cities. The algorithm can output the best input instruction and length for the current status, which finishes the task of input instruction distillation. Moreover, we make some changes to the classic ACO and propose a variant of ACO (VACO) to fit the RTL fuzzing scenario.

Simulating realistic interruption and exception handling. First, we include exceptions in fuzzing the CPU, which is not proposed in previous work [10]. Next, we integrate more than one interruption and exception to test the CPU, aiming to simulate the real-world execution scenario of the CPU more comprehensively. Besides, we consider the priorities of different interruptions and exceptions, which can thoroughly fuzz the CPU. The above techniques can better simulate real-world interruption and exception handling than previous work.

Hardware-related seed selection and mutation. We propose new seed selection and mutation strategies in fuzzing the CPU. In seed selection, not only basic fuzzing heuristics are taken into consideration, but also hardware heuristics, e.g., special instructions and registers. For mutation, we propose strategies closely related to hardware, such as insertion or deletion based on the input instruction length. The seed selection and mutation strategies combine fuzzing with hardware characteristics, and they overcome the drawbacks of previous tools.

We implement a prototype Instiller (Instruction Distiller) and conduct extensive evaluation against state-of-the-art fuzzing work. In general, the results show the effectiveness of our proposed techniques. Our tool increases coverage by 29.4%. For input instruction distillation, the length of Instiller is 79.3% shorter than DiFuzzRTL. For vulnerability discovery, Instiller finds 17.0% more mismatches in the targets. In addition, the input instruction distillation leads to a 6.7% increase in execution speed on average.

In conclusion, we make the following contributions to this paper:

• •

  We propose an input instruction distillation technique, which is based on a variant of ant colony optimization. The distillation can make the inputs shorter and more effective.

• •

  We enable our fuzzer to handle multiple interruptions and exceptions. The priorities of them are also considered. These techniques can simulate realistic interruption and exception handling well.

• •

  We propose hardware-based seed selection and mutation strategies. We use hardware-related heuristics and mutation operations to improve fuzzing performance in the situation of RTL fuzzing.

• •

  We implement a prototype named Instiller and conduct extensive experiments. The results show that our tool outperforms previous work and demonstrate the effectiveness of our proposed approaches.