# IRFuzzer: Specialized Fuzzing for LLVM Backend Code Generation

Yuyang Rong  Advanced Micro Devices, Inc. and UC DavisDavisCAUSA
<EMAIL_ADDRESS>,  Zhanghan Yu  UC DavisDavisCAUSA<EMAIL_ADDRESS>,
Zhenkai Weng  UC DavisDavisCAUSA<EMAIL_ADDRESS>,  Stephen Neuendorffer
Advanced Micro Devices, Inc.San JoseCAUSA<EMAIL_ADDRESS>and
Hao Chen  UC DavisDavisCAUSA<EMAIL_ADDRESS>
(2024)

###### Abstract.

Modern compilers, such as LLVM, are complex pieces of software. Due to their
complexity, manual testing is unlikely to suffice, yet formal verification is
difficult to scale. End-to-end fuzzing can be used, but it has difficulties in
achieving high coverage of some components of LLVM.

In this paper, we implement IRFuzzer to investigate the effectiveness of
specialized fuzzing of the LLVM compiler backend. We focus on two approaches
to improve the fuzzer: guaranteed input validity using constrained mutations
and improved feedback quality. The mutator in IRFuzzer is capable of
generating a wide range of LLVM IR inputs, including structured control flow,
vector types, and function definitions. The system instruments coding patterns
in the compiler to monitor the execution status of instruction selection. The
instrumentation not only provides a new coverage feedback called matcher table
coverage, but also provides an architecture specific guidance to the mutator.

We show that IRFuzzer is more effective than existing fuzzers by fuzzing on 29
mature LLVM backend targets. In the process, we reported 74 confirmed new bugs
in LLVM upstream, out of which 49 have been fixed, five have been back ported
to LLVM 15, showing that specialized fuzzing provides useful and actionable
insights to LLVM developers.

fuzzing, LLVM, software analysis

††booktitle: Proceedings of the 32nd ACM Symposium on the Foundations of
Software Engineering (FSE ’24), November 15–19, 2024, Porto de Galinhas,
Brazil††copyright: acmcopyright††journalyear: 2024††doi: XXXXXXX.XXXXXXX††ccs:
Software and its engineering Compilers††ccs: Security and privacy Software
security engineering

##  1\. Introduction

Modern compilers, such as LLVM (lattner2004llvm, 1), are complex software. For
example, LLVM consists of over seven million lines of C/C++ code contributed
by more than $2500\text{\,}$developers111https://github.com/llvm/llvm-project.
Given the size of this codebase and its importance in the computing ecosystem,
an effective and scalable verification method is critical. Despite extensive
regression testing and wide usage, latent bugs remain and their impact on
users can be quite significant given the widespread distribution and long
lifetimes of compilers.

To reduce latent bugs, various techniques have been used to automate the
verification of compilers, such as partial model checking (lopes2021alive2,
2), fuzzing (LibAFL, 3, 4, 5), and differential testing (emi, 6, 7). Although
end-to-end formal verification of compilers has been applied (Jourdan-
LBLP-2015, 8, 9), these techniques have not yet scaled to practical compilers
such as LLVM, which support a wide range of architectures, programming
languages, and use models, including just-in-time compilation and link-time
optimization.

In the specific case of LLVM, another factor making verification difficult is
that the interface between the compiler optimization and machine code
generation is widely used but not completely specified. As a result, it can be
difficult for backend developers to understand whether they have completely
implemented the wide range of possible inputs. In addition, backends often
differ greatly in their relative code maturity, including some targets that
are relatively mature and other targets for new devices that are in active
development.

We find that the state-of-the-art fuzzers failed to find new bugs of a
compiler backend for various reasons. General-purpose fuzzing techniques, such
as AFL++ (AFLplusplus, 10), often do not consider input validity and struggle
to explore control paths in the compiler backend since most binary strings are
invalid compiler inputs. In order to test the compiler backend more
effectively, we aim to generate LLVM Intermediate Representation (LLVM IR)
that complies with the language reference. LLVM includes llvm-opt-fuzzer and
llvm-isel-fuzzer that generates valid IR for middle end and backend fuzzing,
respectively (LLVMFuzzing, 11). Both of them are based on the library
FuzzMutate (FuzzMutate, 12) for valid IR mutation. However, FuzzMutate can’t
construct complex control flow, and it only generates a few instructions with
scalar types. On the other hand, end-to-end fuzzing tools, such as CSmith
(CSmith, 4) and GrayC (GreyC, 13), test the whole pipeline of the compiler,
but they cannot to efficiently explore control paths in the compiler backend.
CSmith does not take any feedback from the compiler, which contributes to its
ineffectiveness. A more fundamental reason is that front-end parser and
middle-end optimizations may limit the set of features seen by the compiler
backend. High level languages like C may not exercise all backend features in
LLVM. Therefore, even if GrayC used branch coverage feedback from libFuzzer
(serebryany2016continuous, 14), it missed many backend bugs introduced before
LLVM 12, which were found by us. As a result, when a new language, such as
Rust, is introduced, new backend bugs may still arise (rustbug, 15).

Generating valid IR is challenging with three major difficulties. In order to
generate a complex control flow graph (CFG), we have to maintain all data
dependencies to avoid use-before-definition situations. A valid CFG can be
easily invalidated by a jump, as shown in Figure 2. This challenge does not
exist in C generation if one does not generate goto statements. Besides,
modelling the instructions missing in FuzzMutate isn’t trivial. We must make
sure that the types of the operands in each IR instruction match, but
enumerating the large numbers of natively supported vector types is
infeasible. Finally, it is difficult to model intrinsic functions for all
architectures, as intrinsics are often poorly documented and vary from
architecture to architecture.

We also observe that AFL++’s feedback mechanism performed poorly when testing
the backend. It uses branch coverage as feedback, which runs into severe
branch collision problems when fuzzing large code bases such as LLVM. Naively
increasing the branch counting table size introduces huge overhead (8418631,
16). A more fundamental reason is that much code generation logic in the LLVM
backend is implemented using table-driven state machines. A matcher table
encapsulates all possible states as a constant byte array, meaning that branch
counting can’t observe this logic during fuzzing. The fuzzer needs a better
feedback on whether the seed is interesting or not. If the seed is not
interesting, the feedback should also inform the mutator what type of input is
more desired.

Figure 1.  Overview of IRFuzzer. Green shaded components are the contributions
of this paper, orange shaded components are AFL++, and blue shaded components
are from LLVM. We first create a LLVM IR mutator that guarantees the
correctness of the generated input ( Section 3.1). We introduce a new coverage
metric to keep track of the backend code generation while providing a mutation
guide to the mutation module ( Section 3.2).

BB1BB2BB3

(a) Original CFG

BB1BB2BB3

(b) Naive mutation by random edge insertion

Figure 2.  An example showing that naive mutation of CFG may break domination
relations. 2(a) shows the original CFG. If we randomly insert an edge shown in
2(b), BB2 won’t dominate BB3 after mutation, and any value in BB3 referencing
BB2 becomes invalid.

To address these issues, we design a specialized fuzzer, IRFuzzer, for fuzzing
the LLVM compiler backend. Figure 1 shows the overall structure of IRFuzzer.
We first design a mutator that generates valid IR (Section 3.1). We maintain
the correctness of CFG during mutation. We also use a descriptive language to
list the requirements of each instruction type. This approach ensures that
inputs to the compiler backend are always valid, increasing the efficiency of
fuzzing. Our work expands the FuzzMutate to include aspects where compiler
backends often have special handling, including multiple basic blocks with
complex control flow, function calls, intrinsic functions, and vector types.
Using IRFuzzer, we are able to generate a wider range of instructions and
explore control paths in the compiler backends more efficiently.

Then, we introduce a new coverage metric (Section 3.2) by instrumenting the
table-driven state machines in LLVM, enabling the design space to be more
efficiently explored. New entries that are covered in the matcher table means
new features are executed. Working together with branch coverage, they can
provide a better feedback on whether a seed is interesting or not.
Furthermore, the matcher table has all information about the instructions and
intrinsics in one architecture. As a result, we use the matcher table to
determine which instructions and intrinsics haven’t been fuzzed. We design a
feedback loop from the matcher table coverage to our mutator. IRFuzzer will
periodically generate a coverage report containing the states that haven’t
been executed. The report will be sent to the mutator to guide future
mutations, enabling IRFuzzer to test on different backends with no prior
knowledge of the architecture.

We evaluate IRFuzzer on 29 mature backend architectures in LLVM (Section 5).
Our results show that IRFuzzer is more effective than the state-of-the-art
fuzzers such as AFL++ and GrayC. IRFuzzer generated inputs code with better
edge coverage and matcher table coverage on 28 LLVM backends. Leveraging these
techniques, we were able to find and report 74 confirmed, new bugs in LLVM, 49
of which have been fixed, five have been back ported to LLVM 15. This
demonstrates the high impact on improving the correctness of LLVM backend
targets.

This paper uses LLVM to demonstrate the importance of having a specialized
fuzzer for the compiler backend. Since modern compilers have similar
intermediate representations, we expect that our approach can be easily
applied to other compilers without requiring heavy engineering efforts. We
made the following contributions:

  * •

We have designed and implemented IRFuzzer. To the best of our knowledge,
IRFuzzer is the first backend fuzzer that uses coverage feedback to guide IR
mutation.

  * •

We compared IRFuzzer with other state-of-the-art fuzzers on LLVM upstream and
found it to be the most effective on matcher table coverage metric.

  * •

We carefully analyzed and categorized the bugs we found during our testing. In
total, we discovered 74 confirmed new bugs in LLVM, 49 of them have already
been fixed, five have been back ported to LLVM 15.

##  2\. Background

###  2.1. LLVM

LLVM (lattner2004llvm, 1) is a mature compiler framework consisting of many
components that can be targeted to different architectures. At its core lies
the LLVM Intermediate Representation (LLVM IR), which serves as a target-
independent abstraction separating the concerns of high-level programming
languages from the low-level details of particular architectures. LLVM can be
roughly partitioned into three layers as shown in Figure 4: A frontend, such
as clang, translates programming languages to LLVM IR, including lexer,
parser, AST transformation, etc. The middle-end, called opt, processes LLVM IR
and performs common target-independent optimizations. The backend, called llc,
converts LLVM IR to a target-specific machine code representation and
eventually emits binary or assembly code for the target architecture. The LLVM
backend supports multiple target architectures through a plug-in abstraction,
and the code to support a target architecture typically involves the
implementation of API functions to describe common aspects along with target
specific code to implement more unusual concepts.

Figure 3.  LLVM can be roughly partitioned into three components, frontend,
middle end, and backend.

Figure 4.  AFL can be modelled as a four-stage loop that tests the executable
repeatedly.

The LLVM IR describes a static single-assignment (SSA) form (SSA, 17), with a
fixed set of instructions. Instructions are strongly typed, and the type of
each value must match between its definition and all uses. A wide range of
types are supported, including integers with arbitrary bit width up to
$65\,536\text{\,}\mathrm{,}$ floating point values, pointers, vectors, and
other aggregate types. As with most high-level languages, LLVM IR allows the
definition of functions, and the control flow between functions is implemented
using the call instruction. Architecture specific intrinsic have no
corresponding IR instructions, but are represented as function calls at IR
level.

Control flow within a function in LLVM IR is represented using basic blocks
and branch instructions. Special PHI instructions allow instructions in a
basic block to refer to values defined in other basic blocks. Therefore, PHI
instructions must respect control flow constraints and may only refer to
values defined in predecessor blocks. This domination constraint
(prosser1959applications, 18) means that techniques used in high-level
language generation cannot be easily adapted to LLVM IR.

The process of instruction selection in the LLVM backend replaces target-
independent LLVM IR instructions with target-specific machine code
instructions. LLVM provides two different frameworks to implement instruction
selection that may be leveraged by the target backend plug-in. SelectionDAG
(SelectionDAG, 19) is the more mature instruction selection framework and is
leveraged by all targets. In SelectionDAG, the code in each basic block is
converted into a directed acyclic graph (DAG) representing the data dependency
between instructions, and instruction selection is performed on the DAG. Since
SelectionDAG processes each basic block independently, it can miss
opportunities for optimization across basic blocks. GlobalIsel (GlobalIsel,
20) is a newer framework that is only leveraged by some targets. GlobalIsel
preserves the basic block structure within a function during instruction
selection, enabling more optimization opportunities.

⬇

1void SelectCodeCommon(SDNode *N, char *MatcherTable) {

2 bool Result;

3 while (true) {

4 switch (MatcherTable[Idx++]){

5 case OPC_CheckOpcode: {

6 uint16_t Opc = MatcherTable[Idx++];

7 Opc |= (unsigned short) MatcherTable[Idx++] << 8;

8 Result = (Opc == N->getOpcode()); }

9 case OPC_CheckPredicate: ...

10 ...

11 }

12}}

Listing 1:  SelectionDAG in LLVM that consumes a matcher table to do
instruction selection.

Both frameworks use patterns to describe rewrite rules applied during
instruction selection. Some patterns are relatively simple and replace a
single LLVM IR instruction with a single machine instruction. More complicated
patterns may replace multiple LLVM IR instructions, or generate multiple
machine instructions. Patterns may also include complex predicates to limit
their applicability only to specific situations. For example, a pattern may
only apply when a particular operand is a constant, or a certain hardware
feature is enabled.

Most patterns are described declaratively in an LLVM-specific language called
TableGen (TableGen, 21). In order to optimize the application of patterns,
TableGen translates individual patterns into a state-machine representation
implemented as a large byte array in C++ known as the matcher table. During
compilation, the state machine in the matcher table is executed on each IR
instruction and determines the correct pattern (if any) to apply. 1 is a C++
code snippet used to evaluate the matcher table in SelectionDAG. SDNode is a
data structure that represents an IR instruction. The while loop iteratively
reads a command from the matcher table based on the current state, represented
by the idx variable, evaluates the command, and selects the next state that
will be evaluated. For example, Opc_CheckOpcode will check if the opcode of a
given SDNode representing an instruction in the SelectionDAG graph matches a
particular opcode. The Result will be used in future iterations, depending on
the next entry in the matcher table. Evaluation of the matcher table continues
until a single pattern is selected, or a state is reached where no patterns
can apply.

Note that all patterns are evaluated using the same set of conditional
branches in the switch statement in 1. As a result, control flow coverage in
the code is a poor indicator of whether all patterns have been exercised.

###  2.2. Coverage guided fuzzing

American Fuzzy Lop (AFL) (AFL, 22) is a widely used open source fuzzing
framework that implements a form of coverage-guided fuzzing, Figure 4 shows an
overview of AFL. Rather than simply generate arbitrary inputs to a program
under test (PUT), AFL instruments the PUT with the ability to track control-
flow coverage. When a particular program input results in increased code
coverage, AFL stores this input in a seed cache for future use. When
generating new random program inputs, AFL prefers to select previous inputs
from the seed cache and further mutate them, rather than generating completely
random input. Using this strategy, AFL and coverage-guided fuzzing tools are
able to more quickly explore all different control-flow paths of the PUT, when
compared to black-box fuzzing techniques without instrumentation.

Many variations of coverage guided fuzzing have been developed, with the goal
of finding bugs more efficiently by exploring a wider range of program
behaviors with future executions of the PUT (10.1145/3512345, 23). There are
studies on the impact of different feedback algorithms (241986, 24, 25, 26).
Different methods are proposed to prioritize seeds to improve the performance
of fuzzing. (aflfast, 27, 28, 29). Some fuzzers also target on triggering
specific bugs (251544, 30, 31, 32). More advanced mutation strategies also
show better fuzzing performance compared with random mutation (redqueen, 33,
34, 35, 36, 37). Many improvements of have been implemented in AFL++
(AFLplusplus, 10), making it a good framework for further development.

LLVM also introduces its own coverage guided fuzzing framework libFuzzer
(serebryany2016continuous, 14), coupled with FuzzMutate (FuzzMutate, 12), it
can be used to fuzz LLVM backend. However, FuzzMutate only generates a limited
type of code and is not under active development. Still, the framework
provides us with helpful insights into how should we mutate LLVM IR.

###  2.3. Challenges in Compiler Fuzzing

We believe that compilers represent a particularly challenging area to apply
fuzzing, due to the size and complexity of the PUT involved. First, the input
program has to be semantically meaningful. With program context, many
structured fuzzing techniques (8811923, 38, 39) based on context-free grammar
cannot be directly applied. For example, generating an IR instruction
depending on a value that hasn’t been defined yet may cause the module
verifier to abort. While high-level languages use notions like scope or
lifetime to notate whether a value can be used, LLVM IR does not have that. We
can only reason the lifetimes of values in basic blocks by static analysis.
For two blocks $A$ and $B$, only when $A$ must be executed before $B$, or $A$
dominates $B$, can $B$ directly reference values in $A$. However, when
changing control flows, it is very easy to break that domination relation. For
example, in 2(b), by adding an edge to the CFG we may invalidate the whole
module and be rejected. We have to carefully maintain the CFG so that if a $A$
dominates $B$, the relation remains the same after the control flow mutation.

In addition, we have to make sure the input has the correct syntax. LLVM IR is
a strongly typed language with numerous types, including vector types and
struct types, making it infeasible to explicitly enumerate types of legal
operations. This challenge doesn’t exist in some high-level programming
language generation tasks like C (CSmith, 4, 5) and JavaScript
(aschermann2019nautilus, 39, 40, 41, 42). What’s worse, each architecture can
implement its customized LLVM IR instructions called intrinsic functions. The
internal definition of intrinsic are often poorly documented, as the
implementation details are often proprietary. These constraints make it hard
to enumerate and model all of them without architecture specific knowledge.

LLVM IR implements an SSA representation of code, which only allows each
variable to be assigned once. Consequently, it is very easy to reason if a
variable is used at static time. If an IR instruction is not used, it is a
dead code and the compiler erases it. Therefore, we wish our generated
instructions to rely not only on constants but also other instructions.

Finally, machine instructions do not correlate with instruction selection’s
control flow, rendering traditional code coverage ineffective. When compiling
LLVM IR to binary executable, both backend algorithms (SelectionDAG and
GlobalIsel) use a table-driven method. Architecture developers will write code
generation patterns in TableGen. These patterns will be compiled by LLVM into
a static table known as a matcher table. The matcher table contains both data
and control instructions for the pattern. At runtime, a while loop will
consume this table. Thus, different instructions may be generated using the
same control flow with different data.

##  3\. Design

⬇

1define i64 @f(i32 %I, <4 x i32> %V) {

2Entry: %ret_p = alloc i64, 1

3 %ret = load i64, ptr %ret_p

4 ret i64 %ret

5}

Listing 2:  A piece of LLVM IR program generated by function
generation(Section 3.1.1). The function returns a 64 bit integer, so we
allocate a stack memory and load from it to return. We will fill the memory
later.

⬇

1define i64 @f(i32 %I, <4 x i32> %V) {

2EntrySrc:

3 %ret_p = alloc i64, 1

4 switch i32 %I, label %sCFG_Default [

5 i32 1, label %sCFG_1

6 i32 42, label %sCFG_42

7 ]

8sCFG_Default: br label %EntrySink

9sCFG_1: br label %EntrySink

10sCFG_42: br label %EntrySink

11EntrySink:

12 %ret = load i64, ptr %ret_p

13 ret i64 %ret

14}

Listing 3:  The program after mutation from 2. Line 4 to 10 are introduced by
sCFG insertion(Section 3.1.2). We insert sCFG by splitting the Entry block
into two and generate a switch instruction.

⬇

1declare i64 @llvm.smax.i64(i64, i64)

2

3define i64 @f(i32 %I, <4 x i32> %V) {

4EntrySrc:

5 %ret_p = alloc i64, 1

6 switch i32 %I, label %sCFG_Default [

7 i32 1, label %sCFG_1

8 i32 42, label %sCFG_42

9 ]

10sCFG_Default:

11 %I64 = zext i32 %I, i64

12 br label %EntrySink

13sCFG_1:

14 %I1 = add i32 %I, 1

15 %J64 = call @f(i32 %I1, <4 x i32> %V)

16 br label %EntrySink

17sCFG_42:

18 %M = call @llvm.smax.i64(i64 0, i64 1)

19 br label %EntrySink

20EntrySink:

21 %PHI = phi i64 [%I64, %sCFG_Default],

22 [%J64, %sCFG_1],

23 [%M, %sCFG_42]

24 store i64 %PHI, %ret_p

25 %ret = load i64, ptr %ret_p

26 ret i64 %ret

27}

Listing 4:  The program after mutation from 3. Instruction insertion(Section
3.1.3) generated line 11, 15, 18, and 21. The placeholder memory is also used
by %PHI to avoid undefined behavior (Line 24).

Figure 5.  An example of how IRFuzzer mutates a module using different
strategies.

To overcome those challenges in Section 2.3, we design IRFuzzer with two new
components. Figure 1 shows the new components of IRFuzzer. During mutation, we
first generate a function if there isn’t one (Section 3.1.1). Then we change
the control flow graph (CFG) to create more control flows (Section 3.1.2).
Finally, we generate new IR instructions and mutate them (Section 3.1.3).
Figure 9 shows an example of the mutation process using these mutation
strategies. After mutation, we create a new method to measure the coverage of
the program (Section 3.2).

###  3.1. LLVM IR mutation

In order to generate a wide variety of input while avoiding invalid inputs, we
adopt a mutation-based strategy. This strategy starts with small valid seed
inputs and modifies the seed inputs in ways that should also generate valid
inputs. By randomly selecting between a number of small, well-defined
mutations, we expect to eventually generate a broad class of valid inputs
while avoiding invalid inputs. Figure 9 shows an overview of our design. We
first generate an empty function is non is present ( 2). Then, we mutate the
control flow by sCFG insertion ( 3). Finally, we modify or insert instructions
in basic blocks ( 4).

####  3.1.1. Function generation

The LLVM backend has a significant amount of target-specific code related to
function calls. As a result, it is important to generate a wide range of
function definitions and function calls with different arguments and return
types.

IRFuzzer implements a mutation strategy capable of generating new function
definitions with arbitrary arguments and return types. One important
constraint is that the return type of the function signature matches the type
of each return instruction in the function definition. To ensure this, the
function generation strategy also synthesizes a load instruction of an
appropriate type as the operand for a return instruction. Although the value
returned from the load may be uninitialized, later mutations may store values
to the memory, validating the return value.

IRFuzzer also implements a mutation strategy to generate new call instructions
which refer to specific function declarations. The mutator is free to select
any declared function and will generate compatible arguments and return values
for the call, as with any other primitive instruction. Intrinsic functions are
target specific operations that correspond to complicated machine
instructions, and generating them will increase the code we can test. Yet they
are treated as functions at middle-end. In particular, this mutation strategy
will also select intrinsic functions to call.

####  3.1.2. Control flow graph mutation

BB1BB2source…sCFGBB2sinkBB3 Figure 6.  Examples of a successful CFG mutations
by sCFG insertion on Figure 2. We break BB2 into two halves. No matter how
complicated sCFG is, the domination relations are unchanged.

Another area where target-specific code in the LLVM backend differs relates to
control flow. Many machine code optimizations, such as jump threading,
restructure control flow. In addition, certain compiler optimizations may
select specific jump instructions, but this optimization can only be performed
after instruction selection when code size and alignment are known. For
instance, a common compiler optimization is to first select jump instructions
into a “short” form with a limited offset range and then only later replace
the short form with a “long” jump instruction if a larger offset is required.
Control flow optimization can also affect register lifetimes, exercising
target-specific code for spilling and restoring values from the stack.

IRFuzzer implements a structured approach to generating control flow.
Inserting and removing arbitrary branches in the code can greatly change
dominator constraints between basic blocks. For example, in 2(b), mutated from
2(a), BB2 no longer dominates $BB3$ after mutation. If any value in $BB3$
refers $BB2$, the module is invalid after mutation. We implement an elegant
approach that uses sub-control flow graph, or sCFG, shown in Figure 6. Instead
of changing edges, we split a block and insert sCFG inside.

A sCFG is a CFG with a single source entry block and a single sink exit block
that will be placed inside a larger CFG. Within the sCFG, we allow the
synthesis of an arbitrary control flow graph. However, every control flow edge
starting in the sCFG must be contained within the sCFG, except for source
edges, sink edges, and return instructions. With this restriction, we can
insert sCFG into a program without breaking the dominator constraint by
randomly selecting a block and splitting it into two. The first part is source
and the second sink. After block splitting, we generate random sCFG starting
from source and ending with sink.

The sCFG can be constructed with three main control schemas: branch, switch,
and return, corresponding to different terminators of the basic block. We
start with only one basic block and randomly select the terminator of the
block. If the return schema is selected and the function requires a return
type, we pick any value available that matches the return type of the
function. If a branch or switch is selected as the terminator, we will find a
previously generated non-constant value as a condition. If no such values can
be found, we will allocate a stack memory as a placeholder. The branch can go
to one of three places: sink, self-loop or return. If we generate a self-loop,
we will also update all the PHI nodes in the block to include a new value.

Finally, all terminators will be generated when we are mutating CFG. Note that
our instruction generation strategies will not mutate terminators in order to
protect the integrity of the CFG.

####  3.1.3. Instruction modeling and generation

A key aspect of the LLVM backend is to convert the wide range of LLVM IR types
to the (usually small) set of types natively implemented by each target
architecture. Therefore, to exercise all features of code generation, it is
necessary to generate IR instructions with as many data types as possible.
However, many IR instructions only operate on a restricted set of data types,
and FuzzMutate only modelled scalar types, which is trivial and limited. In
order to model these restrictions for vector types, we categorize instructions
as shown in Table 1. These definitions are reflected in the code as
declarative declarations expressing both restrictions on the types of operands
and constraints between the types of different operands. For example, the
anyIntOrVecInt constraint restricts the valid types for a particular operand
to be any integer type or vector of integer type. The matchFirstOperand
constraint restricts the type of operand to be the same as the type of the
first operand.

Table 1.  Instruction modeling for IR instructions.

Operation type | Opcode |  | Argument descriptions
---|---|---|---
Unary operation | fneg | : | anyFloatPointOrVectorFloatPoint
Binary operations |  add, sub, mul, (s$|$u)(div$|$rem) | : | anyIntOrVecInt | sameAsFirst |
fadd, fsub, fmul, fdiv, frem | : | anyFPOrVecFP | sameAsFirst |
Bitwise operations | shl, lshr, ashr, and, or, xor | : | anyIntOrVecInt | sameAsFirst |
Vector operations | extractelement | : | anyVector | anyInt |
insertelement | : | anyVector | matchScalarOfFirst | anyInt
shufflevector | : | anyVector | matchLengthOfFirst | VecOfConstI32
Aggregate operations | extractvalue | : | anyAggregateOrArray | anyConstInt |
insertvalue | : | anyAggregateOrArray | matchScalarOfFirst | anyConstInt
Memory operation | getelementptr | : | anySized | pointerOfFirst | anyInt
Casting operations | trunc | : | anyNonBoolIntOrVecInt | anyIntOrVecIntWithLowerPrecision |
zext, sext | : | anyIntOrVecInt | anyIntOrVecIntWithHigherPrecision |
fptrunc | : | anyNonHalfFPOrVecFP | andFPOrVecFPWHigherPrecision |
fptoui, fptosi | : | anyFPOrVecFP | matchLengthOfFirstWithInt |
uitofp, sitofp | : | anyIntOrVecInt | matchLengthOfFirstWithFP |
ptrtoint | : | anyPtrOrVecPtr | matchLengthOfFirstWithInt |
ptrtoint | : | anyIntOrVecInt | matchLengthOfFirstWithPtr |
bitcast | : | anyType | anyTypeWithSameBitWidth |
Other operations | icmp | : | anyIntOrVecInt | sameAsFirst |
fcmp | : | anyFPOrVecFP | sameAsFirst |
select | : | anyBoolOrVecBool | matchLengthOfFirst | sameAsSecond

When generating a new instruction, we first randomly select an opcode and use
the declarations to randomly select values that exist in the code with a
compatible type. If no value exists with a compatible type, then the mutator
will create a new operation with a compatible type. For numerical types, the
new operation could generate a random constant, undef, or poison.

In addition, a small number of operations are not modeled declaratively. For
instance, store and load memory operations are structured differently enough
from other operations that modeling them is not necessary. Some other
instructions have constraints which are too complex to be simply handled in
the declarative framework, and we resort to custom generators. For instance,
instructions representing PHI nodes must be created with a number of operands
equal to the number of predecessor blocks and must occur at the start of their
basic block. Similarly, call instructions are handled manually too, since we
must select a function declaration and find values that exactly match the
operand types of the declaration.

To ensure that values are defined before they are used, the mutator searches
for values defined in the following locations: global variable, function
argument, values in dominators, and values defined by previous instructions in
the same basic block. If no value with a compatible type exists, the mutator
will attempt to generate a load from a compatible pointer, if one exists.
Lastly, if a value with a compatible pointer type exists, the mutator will
fall back to either creating a new global variable, a new constant value, or a
load from a stack memory location.

In some cases, the mutator may create IR instructions that define values which
are never used. Since such dead code is likely to be removed by the compiler
before instruction selection, the mutator will attempt to create a use for
such values. One possibility is to store dead values to stack memory or a
global variable. Alternatively, if there are instructions after the
definition, or the current block dominates other blocks, the mutator may
select an instruction with a compatible operand to replace.

When generating instructions, it is possible that the mutator allocated new
stack memory as placeholders. In order to avoid undefined behavior, the
mutator will again attempt to replace loads from these placeholders with other
values of compatible type. If no such value exists, then the mutator will
store a value into the placeholder location.

We don’t model intrinsic functions, as they vary from architecture to
architecture, potentially consuming a lot of time with little outcome.
Instead, we rely on the feedback from matcher table coverage (Section 3.2.2).
Matcher table coverage report contains a list of intrinsics that haven’t been
generated in the form of function definitions. Then, the mutator will randomly
generate call instructions to intrinsic from this report.

###  3.2. Matcher table feedback

####  3.2.1. Matcher table instrumentation

Machine instruction generation does not correspond to compiler control flow.
Different instructions can be generated by the same control flow due to the
matcher table. Consequently, many patterns may not be generated yet even if
edge coverage is high. To overcome this, we track the usage of the matcher
table.

Similar to edge coverage, we allocate a table when the compiler starts in
order to track the coverage of the matcher table. Every time an entry in the
matcher table is accessed, we will record that access in our table as well.

Table 2.  Matcher table size in all architectures in LLVM on commit 860e439f.
Since GlobalIsel is a new CodeGen framework introduced in 2015, only eight
architectures have implemented it.

Architecture | SelectionDAG | GlobalIsel | Architecture | SelectionDAG | GlobalIsel
---|---|---|---|---|---
AArch64 | $489\,789$ | $278\,233$ | Mips | $54\,044$ | $60\,449$
AMDGPU | $493\,556$ | $338\,444$ | NVPTX | $186\,134$ | -
ARC | $1998$ | - | PowerPC | $190\,304$ | $83\,201$
ARM | $201\,172$ | $130\,029$ | RISCV | $2\,191\,899$ | $190\,009$
AVR | $2973$ | - | Sparc | $6607$ | -
BPF | $3586$ | - | SystemZ | $53\,271$ | -
CSKY | $19\,076$ | - | VE | $71\,577$ | -
Hexagon | $178\,277$ | - | WASM | $25\,991$ | -
Lanai | $2337$ | - | X86 | $680\,916$ | $61\,488$
M68k | $18\,850$ | $2388$ | XCore | $3854$ | -
MSP430 | $9103$ | - |  |  |

Natively tracking the number of accesses like edge coverage is a huge memory
overhead. The second and fifth column of Table 2 show the size of the matcher
table in different architectures. The matcher tables for mainstream
architectures like X86 and AArch64 have several hundred thousand entries,
RISCV even has about two million entries. Natively assigning a counter to each
entry like AFL++ will cost hundreds of KB of runtime memory, which will lower
the fuzzing throughput (241986, 24).

Unlike control flow where the edge’s execution count represents different
program semantics, a matcher table entry being accessed multiple times only
means the same pattern is triggered multiple times. Therefore, we only track
whether an entry is accessed or not, i.e., we use a boolean to track each
entry. During instrumentation, we pack eight booleans into a byte to save
space. If the table size is not a multiple of eight, we pad extra booleans.

During fuzzing, to access an entry in the matcher table, the fuzzer can
calculate the offset of the entry’s corresponding boolean using its index.
After execution, the instrumented compiler will report a matcher table
coverage back to the fuzzer. The fuzzer will use edge coverage and matcher
table coverage together. If either table shows new coverage, we will consider
the input as new.

####  3.2.2. IR mutation feedback

While the matcher table can help filter out not interesting seeds, it also
contains knowledge whether an instruction or intrinsic is generated or not. We
wish to pass that feedback to the mutator, so it can generate more diverse
inputs. However, decoding the meaning of each entry in the matcher table is
non-trivial, as LLVM hides this information when preparing the matcher table.

We first modify TableGen to dump a look-up table specifying the correspondence
of matcher table entries and machine instruction patterns. The pattern reveals
the condition on a specific instruction or intrinsic being generated.

Prior to fuzzing, we dump this look-up table for each architecture. During
fuzzing, we will decode the matcher table coverage using the look-up table to
determine which instructions haven’t been generated yet. For instructions that
haven’t been generated, we model the condition of it; for intrinsic, we model
the intrinsic as an LLVM IR function definition. Finally, we compile this
information into a report and send back to the mutator to increase the chance
of them been generated. This feedback is done every ten minutes, so we can
provide a meaningful feedback while minimizing the runtime overhead.

##  4\. Implementation

Our implementation is based on prior work FuzzMutate(FuzzMutate, 12) and AFL++
(AFLplusplus, 10). FuzzMutate introduced a naive mutator with around
$1000\text{\,}\mathrm{l}$ines of code. We add more mutation strategies for
function calls, control flow graph mutation, and arbitrary data types. The
mutator described in Section 3.1 consists of approximately
$2000\text{\,}\mathrm{n}$ew lines of C++ code, which has been contributed to
the upstream LLVM’s repository, augmenting the existing mutator strategies.

We implement our matcher table coverage described in Section 3.2.1. The
implementation combines a compiler plugin to measure the size of each matcher
table and insert appropriate instrumentation, along with a small runtime
library to allocate and track the coverage information. It is implemented in
around $1000\text{\,}\mathrm{l}$ines of C and C++.

We modify TableGen to dump a look-up table for each matcher table described in
Section 3.2.2. Our decode and feedback report code is implemented in around
$1000\text{\,}\mathrm{l}$ine of C++. IRFuzzer is anonymously published
(IrfuzzerArtifact, 43), and we plan to open-source IRFuzzer once the paper is
accepted.

##  5\. Evaluation

In order to understand how IRFuzzer helps to test LLVM code generation, we
implement IRFuzzer and evaluate it. In the rest of this section, we will fuzz
LLVM with different settings and tools to gain some insights to these research
questions.

  * •

RQ1: How does IRFuzzer compare with state-of-the-art backend fuzzers?

  * •

RQ2: How does IRFuzzer compare with end-to-end fuzzers like CSmith and GrayC?

  * •

RQ3: Does mutator and feedback individually contribute to IRFuzzer?

  * •

RQ4: Can IRFuzzer help find new bugs in LLVM?

  * •

RQ5: What are the insights we can gain from the bugs we found?

The upstream LLVM repository (commit 860e439f) currently supports 21
architectures listed in Table 2, excluding experimental ones. We only test on
mature architectures that have a matcher table size larger than 25 000. In
addition, each architecture may provide different features that can be enabled
on different hardware. For simplicity, we select the backend of some popular
microchips, which has a predefined set of features. These backends are widely
used from user product to server applications, justifying the variety of our
choice. All architectures we tested are under active development. As a result,
we select 29 target CPUs 222“Target CPU” is used in LLVM to label a backend
corresponding to a microchip. It can also refer to GPU or other DSP. across 12
architectures.

We use two baseline fuzzers: AFL++ with no modification and AFL++ whose
mutation module replaced with FuzzMutate. We will refer to it as FuzzMutate
thereafter. All fuzzers used AFL++’s default scheduling. For fairness, we
collect the seeds generated by each fuzzer and measure their branch table
coverage and matcher table coverage. Branch coverage is reported by AFL++
using classical instrumentation and a default 64 KB table. Matcher table
coverage is calculated as the entries accessed divided by matcher table size
listed in Table 2.

We prepare two versions of IRFuzzer. The one labelled IRF has all designs
described in Section 3. On the other hand, we strip all the feedback mechanism
described in Section 3.2 and label it IRFbare. When comparing with FuzzMutate,
IRFbare’s performance will tell us how our mutator is doing, while comparing
with IRF can reveal the contribution of the feedback mechanism.

Each fuzzer process was dedicated to a single processor core on an x86_64
server with two 20-core CPUs and 692 GB of memory. Each fuzzing process lasted
for one day to allow adequate exploration (10.1145/3243734.3243804, 44). In
addition, each experiment was repeated five times and the results were
averaged to reduce random effects. To demonstrate IRFuzzer’s ability to mutate
IR modules and to provide a fair comparison with AFL++, each fuzzer process
was initialized with 92 seed. The seeds are randomly selected from LLVM’s unit
testing, and they are smaller than 256 bytes to increase the throughput. The
seeds are anonymously published in the artifact (IrfuzzerArtifact, 43).

###  5.1. Baseline comparison

To evaluate our strategy, we compare with two baseline implementations: AFL++
and the upstream LLVM implementation of FuzzMutate. Unmodified AFL++ lacks an
LLVM IR-aware mutator, and hence we expect it to often generate invalid inputs
that fail to meet the syntactic and semantic constraints of LLVM IR. On the
other hand, FuzzMutate has a limited LLVM IR-aware mutator.

Table 3.  Branch table coverage and matcher table coverage on 29 target CPUs
across 12 targets in SelectionDAG. Statistics are the arithmetic mean over
five trials. Bold entries are the best among baseline fuzzers. FM means AFL++
coupled with FuzzMutate, IRF means IRFuzzer

Arch | Target CPU | Branch coverage | Matcher table coverage
---|---|---|---
Seeds | AFL++ | FM | IRF | IRFbare | Seeds | AFL++ | FM | IRF | IRFbare
AArch64 | apple-a16 | 59.8$\mathrm{\char 37\relax}$ | 87.1$\mathrm{\char 37\relax}$ | 82.9$\mathrm{\char 37\relax}$ | 94.7$\mathrm{\char 37\relax}$ | 93.9$\mathrm{\char 37\relax}$ | 0.7$\mathrm{\char 37\relax}$ | 1.6$\mathrm{\char 37\relax}$ | 2.6$\mathrm{\char 37\relax}$ | 8.2$\mathrm{\char 37\relax}$ | 7.3$\mathrm{\char 37\relax}$
apple-m2 | 59.8$\mathrm{\char 37\relax}$ | 86.9$\mathrm{\char 37\relax}$ | 83.3$\mathrm{\char 37\relax}$ | 94.8$\mathrm{\char 37\relax}$ | 93.6$\mathrm{\char 37\relax}$ | 0.7$\mathrm{\char 37\relax}$ | 1.6$\mathrm{\char 37\relax}$ | 2.6$\mathrm{\char 37\relax}$ | 8.2$\mathrm{\char 37\relax}$ | 7.2$\mathrm{\char 37\relax}$
cortex-a715 | 60.0$\mathrm{\char 37\relax}$ | 87.7$\mathrm{\char 37\relax}$ | 83.2$\mathrm{\char 37\relax}$ | 94.0$\mathrm{\char 37\relax}$ | 93.6$\mathrm{\char 37\relax}$ | 0.7$\mathrm{\char 37\relax}$ | 1.7$\mathrm{\char 37\relax}$ | 2.6$\mathrm{\char 37\relax}$ | 9.4$\mathrm{\char 37\relax}$ | 7.2$\mathrm{\char 37\relax}$
cortex-r82 | 60.1$\mathrm{\char 37\relax}$ | 87.0$\mathrm{\char 37\relax}$ | 82.9$\mathrm{\char 37\relax}$ | 93.9$\mathrm{\char 37\relax}$ | 93.6$\mathrm{\char 37\relax}$ | 0.7$\mathrm{\char 37\relax}$ | 1.6$\mathrm{\char 37\relax}$ | 2.6$\mathrm{\char 37\relax}$ | 7.6$\mathrm{\char 37\relax}$ | 7.2$\mathrm{\char 37\relax}$
cortex-x3 | 60.0$\mathrm{\char 37\relax}$ | 93.3$\mathrm{\char 37\relax}$ | 85.2$\mathrm{\char 37\relax}$ | 94.1$\mathrm{\char 37\relax}$ | 94.5$\mathrm{\char 37\relax}$ | 0.7$\mathrm{\char 37\relax}$ | 7.1$\mathrm{\char 37\relax}$ | 2.7$\mathrm{\char 37\relax}$ | 9.1$\mathrm{\char 37\relax}$ | 7.6$\mathrm{\char 37\relax}$
exynos-m5 | 60.3$\mathrm{\char 37\relax}$ | 87.4$\mathrm{\char 37\relax}$ | 83.2$\mathrm{\char 37\relax}$ | 93.9$\mathrm{\char 37\relax}$ | 94.5$\mathrm{\char 37\relax}$ | 0.7$\mathrm{\char 37\relax}$ | 1.7$\mathrm{\char 37\relax}$ | 2.6$\mathrm{\char 37\relax}$ | 7.8$\mathrm{\char 37\relax}$ | 7.5$\mathrm{\char 37\relax}$
tsv110 | 60.0$\mathrm{\char 37\relax}$ | 87.3$\mathrm{\char 37\relax}$ | 82.9$\mathrm{\char 37\relax}$ | 93.2$\mathrm{\char 37\relax}$ | 94.1$\mathrm{\char 37\relax}$ | 0.7$\mathrm{\char 37\relax}$ | 1.6$\mathrm{\char 37\relax}$ | 2.6$\mathrm{\char 37\relax}$ | 7.5$\mathrm{\char 37\relax}$ | 7.3$\mathrm{\char 37\relax}$
AMDGPU | gfx1036 | 70.8$\mathrm{\char 37\relax}$ | 90.0$\mathrm{\char 37\relax}$ | 89.1$\mathrm{\char 37\relax}$ | 96.9$\mathrm{\char 37\relax}$ | 96.7$\mathrm{\char 37\relax}$ | 0.9$\mathrm{\char 37\relax}$ | 2.1$\mathrm{\char 37\relax}$ | 2.7$\mathrm{\char 37\relax}$ | 4.9$\mathrm{\char 37\relax}$ | 4.5$\mathrm{\char 37\relax}$
gfx1100 | 71.2$\mathrm{\char 37\relax}$ | 89.7$\mathrm{\char 37\relax}$ | 89.9$\mathrm{\char 37\relax}$ | 97.0$\mathrm{\char 37\relax}$ | 96.3$\mathrm{\char 37\relax}$ | 1.0$\mathrm{\char 37\relax}$ | 2.1$\mathrm{\char 37\relax}$ | 2.9$\mathrm{\char 37\relax}$ | 4.9$\mathrm{\char 37\relax}$ | 4.5$\mathrm{\char 37\relax}$
ARM | generic | 55.5$\mathrm{\char 37\relax}$ | 87.9$\mathrm{\char 37\relax}$ | 82.5$\mathrm{\char 37\relax}$ | 88.6$\mathrm{\char 37\relax}$ | 88.4$\mathrm{\char 37\relax}$ | 1.7$\mathrm{\char 37\relax}$ | 4.3$\mathrm{\char 37\relax}$ | 4.3$\mathrm{\char 37\relax}$ | 5.2$\mathrm{\char 37\relax}$ | 5.1$\mathrm{\char 37\relax}$
Hexagon | hexagonv71t | 64.8$\mathrm{\char 37\relax}$ | 88.0$\mathrm{\char 37\relax}$ | 86.0$\mathrm{\char 37\relax}$ | 93.6$\mathrm{\char 37\relax}$ | 93.2$\mathrm{\char 37\relax}$ | 1.7$\mathrm{\char 37\relax}$ | 6.6$\mathrm{\char 37\relax}$ | 17.0$\mathrm{\char 37\relax}$ | 30.6$\mathrm{\char 37\relax}$ | 21.0$\mathrm{\char 37\relax}$
hexagonv73 | 64.9$\mathrm{\char 37\relax}$ | 89.5$\mathrm{\char 37\relax}$ | 85.7$\mathrm{\char 37\relax}$ | 94.4$\mathrm{\char 37\relax}$ | 93.4$\mathrm{\char 37\relax}$ | 1.7$\mathrm{\char 37\relax}$ | 7.3$\mathrm{\char 37\relax}$ | 17.4$\mathrm{\char 37\relax}$ | 32.2$\mathrm{\char 37\relax}$ | 21.1$\mathrm{\char 37\relax}$
Mips | mips64r6 | 52.5$\mathrm{\char 37\relax}$ | 81.0$\mathrm{\char 37\relax}$ | 72.7$\mathrm{\char 37\relax}$ | 85.9$\mathrm{\char 37\relax}$ | 84.5$\mathrm{\char 37\relax}$ | 3.8$\mathrm{\char 37\relax}$ | 10.0$\mathrm{\char 37\relax}$ | 15.3$\mathrm{\char 37\relax}$ | 17.8$\mathrm{\char 37\relax}$ | 16.6$\mathrm{\char 37\relax}$
NVPTX | sm_90 | 46.6$\mathrm{\char 37\relax}$ | 77.5$\mathrm{\char 37\relax}$ | 77.5$\mathrm{\char 37\relax}$ | 87.0$\mathrm{\char 37\relax}$ | 84.5$\mathrm{\char 37\relax}$ | 1.7$\mathrm{\char 37\relax}$ | 3.1$\mathrm{\char 37\relax}$ | 4.7$\mathrm{\char 37\relax}$ | 26.5$\mathrm{\char 37\relax}$ | 6.2$\mathrm{\char 37\relax}$
PowerPC | pwr9 | 60.3$\mathrm{\char 37\relax}$ | 87.3$\mathrm{\char 37\relax}$ | 86.9$\mathrm{\char 37\relax}$ | 94.5$\mathrm{\char 37\relax}$ | 94.1$\mathrm{\char 37\relax}$ | 1.2$\mathrm{\char 37\relax}$ | 3.6$\mathrm{\char 37\relax}$ | 7.1$\mathrm{\char 37\relax}$ | 19.6$\mathrm{\char 37\relax}$ | 15.9$\mathrm{\char 37\relax}$
RISCV | rocket-rv64 | 53.7$\mathrm{\char 37\relax}$ | 83.0$\mathrm{\char 37\relax}$ | 76.6$\mathrm{\char 37\relax}$ | 86.4$\mathrm{\char 37\relax}$ | 87.4$\mathrm{\char 37\relax}$ | 1.2$\mathrm{\text{\textperthousand}}$ | 2.0$\mathrm{\text{\textperthousand}}$ | 2.2$\mathrm{\text{\textperthousand}}$ | 2.2$\mathrm{\text{\textperthousand}}$ | 2.3$\mathrm{\text{\textperthousand}}$
sifive-u74 | 54.5$\mathrm{\char 37\relax}$ | 83.1$\mathrm{\char 37\relax}$ | 75.9$\mathrm{\char 37\relax}$ | 86.7$\mathrm{\char 37\relax}$ | 86.6$\mathrm{\char 37\relax}$ | 1.4$\mathrm{\text{\textperthousand}}$ | 2.4$\mathrm{\text{\textperthousand}}$ | 2.9$\mathrm{\text{\textperthousand}}$ | 3.0$\mathrm{\text{\textperthousand}}$ | 3.0$\mathrm{\text{\textperthousand}}$
sifive-x280 | 55.0$\mathrm{\char 37\relax}$ | 84.1$\mathrm{\char 37\relax}$ | 75.7$\mathrm{\char 37\relax}$ | 88.6$\mathrm{\char 37\relax}$ | 89.7$\mathrm{\char 37\relax}$ | 1.4$\mathrm{\text{\textperthousand}}$ | 2.7$\mathrm{\text{\textperthousand}}$ | 3.1$\mathrm{\text{\textperthousand}}$ | 30.6$\mathrm{\text{\textperthousand}}$ | 31.5$\mathrm{\text{\textperthousand}}$
SystemZ | z15 | 55.3$\mathrm{\char 37\relax}$ | 84.0$\mathrm{\char 37\relax}$ | 81.5$\mathrm{\char 37\relax}$ | 89.9$\mathrm{\char 37\relax}$ | 91.0$\mathrm{\char 37\relax}$ | 5.2$\mathrm{\char 37\relax}$ | 13.7$\mathrm{\char 37\relax}$ | 27.1$\mathrm{\char 37\relax}$ | 43.8$\mathrm{\char 37\relax}$ | 38.7$\mathrm{\char 37\relax}$
z16 | 55.3$\mathrm{\char 37\relax}$ | 83.7$\mathrm{\char 37\relax}$ | 81.8$\mathrm{\char 37\relax}$ | 89.8$\mathrm{\char 37\relax}$ | 89.7$\mathrm{\char 37\relax}$ | 5.2$\mathrm{\char 37\relax}$ | 14.1$\mathrm{\char 37\relax}$ | 26.5$\mathrm{\char 37\relax}$ | 43.9$\mathrm{\char 37\relax}$ | 37.6$\mathrm{\char 37\relax}$
VE | generic | 49.0$\mathrm{\char 37\relax}$ | 80.4$\mathrm{\char 37\relax}$ | 70.2$\mathrm{\char 37\relax}$ | 84.4$\mathrm{\char 37\relax}$ | 83.1$\mathrm{\char 37\relax}$ | 3.5$\mathrm{\char 37\relax}$ | 8.1$\mathrm{\char 37\relax}$ | 11.4$\mathrm{\char 37\relax}$ | 14.0$\mathrm{\char 37\relax}$ | 12.6$\mathrm{\char 37\relax}$
WASM | bleeding-edge | 46.8$\mathrm{\char 37\relax}$ | 84.7$\mathrm{\char 37\relax}$ | 70.5$\mathrm{\char 37\relax}$ | 82.9$\mathrm{\char 37\relax}$ | 83.2$\mathrm{\char 37\relax}$ | 4.1$\mathrm{\char 37\relax}$ | 36.9$\mathrm{\char 37\relax}$ | 10.9$\mathrm{\char 37\relax}$ | 37.6$\mathrm{\char 37\relax}$ | 35.9$\mathrm{\char 37\relax}$
generic | 46.6$\mathrm{\char 37\relax}$ | 80.2$\mathrm{\char 37\relax}$ | 69.7$\mathrm{\char 37\relax}$ | 80.6$\mathrm{\char 37\relax}$ | 81.9$\mathrm{\char 37\relax}$ | 4.1$\mathrm{\char 37\relax}$ | 11.8$\mathrm{\char 37\relax}$ | 10.6$\mathrm{\char 37\relax}$ | 11.7$\mathrm{\char 37\relax}$ | 11.8$\mathrm{\char 37\relax}$
X86 | alderlake | 61.2$\mathrm{\char 37\relax}$ | 88.0$\mathrm{\char 37\relax}$ | 84.6$\mathrm{\char 37\relax}$ | 94.7$\mathrm{\char 37\relax}$ | 93.7$\mathrm{\char 37\relax}$ | 0.7$\mathrm{\char 37\relax}$ | 1.8$\mathrm{\char 37\relax}$ | 3.1$\mathrm{\char 37\relax}$ | 8.0$\mathrm{\char 37\relax}$ | 6.2$\mathrm{\char 37\relax}$
emeraldrapids | 60.5$\mathrm{\char 37\relax}$ | 93.4$\mathrm{\char 37\relax}$ | 84.4$\mathrm{\char 37\relax}$ | 93.7$\mathrm{\char 37\relax}$ | 93.5$\mathrm{\char 37\relax}$ | 0.6$\mathrm{\char 37\relax}$ | 12.5$\mathrm{\char 37\relax}$ | 3.2$\mathrm{\char 37\relax}$ | 13.9$\mathrm{\char 37\relax}$ | 12.4$\mathrm{\char 37\relax}$
raptorlake | 61.2$\mathrm{\char 37\relax}$ | 93.5$\mathrm{\char 37\relax}$ | 85.8$\mathrm{\char 37\relax}$ | 94.5$\mathrm{\char 37\relax}$ | 93.7$\mathrm{\char 37\relax}$ | 0.7$\mathrm{\char 37\relax}$ | 6.2$\mathrm{\char 37\relax}$ | 3.3$\mathrm{\char 37\relax}$ | 8.0$\mathrm{\char 37\relax}$ | 6.2$\mathrm{\char 37\relax}$
sapphirerapids | 60.5$\mathrm{\char 37\relax}$ | 88.4$\mathrm{\char 37\relax}$ | 85.4$\mathrm{\char 37\relax}$ | 93.7$\mathrm{\char 37\relax}$ | 93.2$\mathrm{\char 37\relax}$ | 0.6$\mathrm{\char 37\relax}$ | 1.8$\mathrm{\char 37\relax}$ | 3.3$\mathrm{\char 37\relax}$ | 14.0$\mathrm{\char 37\relax}$ | 12.2$\mathrm{\char 37\relax}$
znver3 | 61.8$\mathrm{\char 37\relax}$ | 86.6$\mathrm{\char 37\relax}$ | 84.0$\mathrm{\char 37\relax}$ | 93.8$\mathrm{\char 37\relax}$ | 94.3$\mathrm{\char 37\relax}$ | 0.7$\mathrm{\char 37\relax}$ | 1.6$\mathrm{\char 37\relax}$ | 3.0$\mathrm{\char 37\relax}$ | 7.7$\mathrm{\char 37\relax}$ | 6.5$\mathrm{\char 37\relax}$
znver4 | 61.0$\mathrm{\char 37\relax}$ | 87.6$\mathrm{\char 37\relax}$ | 84.0$\mathrm{\char 37\relax}$ | 93.7$\mathrm{\char 37\relax}$ | 94.2$\mathrm{\char 37\relax}$ | 0.7$\mathrm{\char 37\relax}$ | 1.8$\mathrm{\char 37\relax}$ | 3.2$\mathrm{\char 37\relax}$ | 13.2$\mathrm{\char 37\relax}$ | 12.6$\mathrm{\char 37\relax}$

The result can be found in Table 3. The 3rd and 8th column shows the coverage
brought by initial seeds. Bold numbers are the best statistical significance
($p<0.05$) when compared with other baseline fuzzers using Mann Whitney U
Test.

Overall, we see AFL++ performed poorly for the purpose of testing LLVM
compiler backends. In most backends, it cannot increase much matcher table
coverage due to its lack of support for structured input; IRFuzzer covered
more branches than AFL++ on 28 target CPUs. The output generated by AFL++ did
not provide significant coverage of instruction selection patterns, as
measured by the low matcher table coverage.

Both FuzzMutate and IRFuzzer reached high code coverages. FuzzMutate reached
more than 75% except for generic-la64, mips64r6, generic VE, and generic
WebAssembly. On the other hand, IRFuzzer performed better, achieving over 80%
branch coverage for all target CPUs.

It is not sufficient to only compare branch coverage (8418631, 16). More
significantly, IRFuzzer reached number one in matcher table coverage on all
CPUs, indicating significantly better coverage of instruction selection
patterns.

We observe that in generic WebAssembly, IRFuzzer shows no significance
compared with other fuzzers. After investigation, we find that generic
WebAssembly disabled many features, limiting the maximum reachable matcher
table to 11.8%. This does not show that IRFuzzer is less effective on
WebAssembly, as we can see that IRFuzzer still rank number one in the
bleeding-edge version.

In summary, IRFuzzer achieved higher branch coverage and matcher table
coverage on 28 out of 29 target CPUs. To answer RQ1, IRFuzzer is better at
coverage when fuzzing LLVM code generation compared with state-of-the-art
fuzzers.

###  5.2. Comparison with end-to-end fuzzers

In order to better understand the benefits of targeted fuzzing compared to
end-to-end fuzzing, we also compare IRFuzzer with CSmith (CSmith, 4) and GrayC
(GreyC, 13). Unlike IRFuzzer, end-to-end fuzzers generates C code, which must
be processed by the compiler frontend and middle-end before reaching the
backend. As a result, they exercise the entire compilation pipeline, rather
than focusing on just the backend. Note that although CSmith generates random,
syntactically correct C code, it does not implement any instrumentation and
lacks feedback from executions to guide the generation process. While GrayC
relies on branch coverage feedback, it does not have feedback that is
customized for backends of the compilers. Besides, to test end-to-end fuzzers,
we have to cross compile C to different architectures. Cross compilation
itself is difficult, as we have to set up the proper tool chain for it.
Therefore, we test on three most widely used architectures using generic
backend.

CSmith generates C files with no initial seed. To make comparison fair, we
also run IRFuzzer with no initial seed, since IRFuzzer is capable of
generating LLVM IR from scratch. GrayC relies on deprecated APIs in LLVM 12
and can’t instrument the latest LLVM, thus we download the artifact provided
by GrayC (GrayCArtifact, 45). The artifact consists of $715\,147\text{\,}$C
programs across ten trials. We run CSmith for 24 hours and repeat eight times,
generating a total of $506\,971\text{\,}$C programs.

We cross compile these C programs to different architectures. After
compilation, we measure the resulting control-flow and matcher table coverage
in the compiler backend, using the same instrumentation as IRFuzzer. llc
default optimization to O2, therefore we only test O2 and O3, as O0 and O1 are
often subsets of O2. The results are shown in 4(b).

Table 4.  Average branch table coverage and matcher table coverage of CSmith
(CS), GrayC, and IRFuzzer (IRF). O2 to O3 stands for different optimization
levels. Bold entries are the winners.

(a) O2 Arch | Branch table coverage | Matcher table coverage
---|---|---
CS | GrayC | IRF | CS | GrayC | IRF
AArch64 |  $94.8$% |  $96.1$% |  $93.3$% |  $5.2$% |  $6.9$% |  $7.9$%
ARM |  $90.7$% |  $92.3$% |  $87.2$% |  $4.5$% |  $4.5$% |  $5.1$%
X86 |  $94.8$% |  $96.1$% |  $91.9$% |  $3.5$% |  $4.2$% |  $4.7$%

(b) O3 Arch | Branch table coverage | Matcher table coverage
---|---|---
CS | GrayC | IRF | CS | GrayC | IRF
AArch64 |  $95.3$% |  $96.2$% |  $92.6$% |  $5.4$% |  $6.9$% |  $7.7$%
ARM |  $91.1$% |  $92.5$% |  $86.1$% |  $4.5$% |  $4.5$% |  $4.9$%
X86 |  $94.9$% |  $96.2$% |  $91.5$% |  $3.5$% |  $4.2$% |  $4.6$%

IRFuzzer achieved higher matcher table coverage on all architectures and all
optimizations. Even with branch coverage feedback, GrayC is not able to
generate C inputs with more matcher table coverage, further demonstrating the
necessity for specialized backend fuzzing. We looked into the code generated
by end-to-end fuzzers and found the reason for the coverage differences. The
inferiority of matcher table coverage of end-to-end fuzzers was largely
related to a lack of coverage of vector data types. Vector instructions can
only be generated when the frontend and middle-end decide a vector instruction
will speed up a particular piece of code, which turns out to be rather
unlikely for random C programs. However, since IRFuzzer operates on IR
instructions, it can generate vector operations without relying on the
frontend or middle-end of the compiler.

On the other hand, CSmith and GrayC achieved higher branch coverage. After
investigation, we find that the size of generated files contributed to the
difference. IRFuzzer generates bit code less than 10 KB to achieve higher
throughput. Seeds generated by CSmith average to more than 40 KB after we
compiled them to bit code. This means that many backend edges are executed
more times, which would increase branch coverage in AFL’s design. This does
not show IRFuzzer’s inferiority. IRFuzzer can reach fair coverage in much
smaller inputs, showing the efficiency of specialized backend fuzzing.

Our evaluation answers RQ2, IRFuzzer achieved higher matcher table coverage
than state-of-the-art end-to-end fuzzers. This shows that backend testing
should not solely rely on end-to-end fuzzing, and that specialized fuzzing can
improve matcher table coverage significantly.

###  5.3. Individual contributions

We are interested to know how each component helps IRFuzzer. Therefore, we
strip all feedbacks in IRFuzzer to get IRFuzzerbare. Comparison of fuzzing
results can be found in Table 3.

Comparing IRFuzzerbare with FuzzMutate, we find that IRFuzzerbare always reach
higher branch coverage and matcher table coverage. This means that our mutator
is able to generate more diverse input than FuzzMutate. Although FuzzMutate is
also a structured mutator, it lacks many advanced features we designed in
Section 3.1. Sifive-x280 best demonstrates this improvement: on sifive-x280,
IRFuzzerbare can cover 31.5$\mathrm{\text{\textperthousand}}$ of the matcher
table, while FuzzMutate only reached 3.1$\mathrm{\text{\textperthousand}}$.

On the other hand, when comparing the last two columns of Table 3, we find
that IRFuzzer is able to cover more matcher table in 26 out of 29 target CPUs
compared with IRFuzzerbare. IRFuzzer didn’t show superiority on three target
CPUs (rocket-rv64, sifive-x280, generic WebAssembly) mainly because both
fuzzers reached coverage ceilings allowed by that target CPU. However, we find
that sometimes IRFuzzer has less branch coverage. We find the contribution of
feedback mechanism is double-sided. The newly introduced matcher table
coverage and feedback to mutator lowered the throughput, affecting the overall
branch coverage. On the other hand, the feedback is valuable in generating
more diverse inputs, contributing to higher matcher table coverage. For
example, in NVPTX, IRFuzzer achieved 26.5% matcher table thanks to our
feedback when IRFuzzerbare only covered 6.2%. Since our end goal is to test
the code generation part of the backend, we believe this tradeoff is
acceptable. We can answer RQ3 confidently that both mutator and feedback
design contributed to improve the matcher table coverage.

###  5.4. Bug categories and analysis

We collect all crashes found in Section 5.1 and Section 5.2. We also fuzzed
other architectures with no features to extend our scope. Since GlobalIsel
also uses matcher table design, we can apply IRFuzzer on it with little
modification. We also fuzzed GlobalIsel for AArch64, Mips, and X86.

In the process, we found hundreds of crashes in the LLVM compiler. Even though
these crashes all have unique stack traces, it doesn’t necessarily mean they
are different bugs. Some crashes have different paths but have the same root
cause. Therefore, we manually analyzed all of them and report the ones we
believe are bugs. In this section, we only report the bugs that have been
confirmed. In total, IRFuzzer found 74 confirmed bugs. We manually verified
that these bugs are found by IRFuzzer only and published the details
anonymously (IrfuzzerArtifact, 43).

These bugs are distributed in different places in LLVM codebase. 7(a) shows
the distribution of these bugs across LLVM. CodeGen is the library shared
between architectures, meaning that a bug in CodeGen may affect all
architectures. We are surprised to find that CodeGen and some widely adopted
architectures have more bugs than we expected. This indicates that LLVM
backend still needs more specialized fuzzing to be more fail-safe.

To better study these bugs, we categorize them into six categories: hang,
memory errors, assertion failures, logic errors, missing patterns, and other
bugs. Hang, memory errors and assertion failures are the most severe ones as
they have a direct impact on end users. Missing patterns means a certain
machine instruction is permitted by the hardware specification, but no
matching instruction selection pattern exists. Logic error and missing
patterns won’t immediately affect the user, but may generate ineffective or
even wrong machine instructions. 7(b) shows the number of bugs in each
category. Most bugs are assertion errors or missing patterns. They arise from
developers’ false assumption that some properties holds true during
compilation, while our fuzzer proved otherwise.

X86AArch64CodeGenNVPTXAMDGPUHexagonWASMRISCVARMBPFVEXCorePowerPC$0$$5$$10$$15$$7$$3$$2$$7$$3$$2$$1$$7$$10$$9$$1$$4$$5$$6$$3$$1$$1$$1$$1$#
of bugsConfirmedFixed

(a) Bugs categorized by locations. CodeGen refers to the code shared by all
architectures, thus bugs in it can potentially affect all architectures.

AssertionPatternLogicMemoryHangOther$0$$10$$20$$5$$8$$5$$3$$3$$1$$17$$12$$8$$6$$3$$3$#
of bugsConfirmedFixed

(b) Bugs categorized by causes. Most of the severe bugs are compiler hangs,
memory errors, and assertion failures.

Figure 7.  Distributions of bugs found by IRFuzzer. IRFuzzer has found 74 new
bugs, 49 have been fixed.

We are working closely with the LLVM community to fix the bugs. 49 have been
fixed, five of which are back ported to LLVM 15 as security patches. It’s
surprising that, despite heavy fuzzing, all fixed bugs are introduced before
LLVM 15, which is released more than a year before paper submission. This
demonstrates that specialized fuzzing for compiler backend is necessary, and
it provides actionable insight to developers.

We can answer RQ4 now. We found six compiler hangs, nine memory errors, and 22
assertion failures. We also found 13 logic errors and 20 missing patterns in
the matcher table. In total, we found 74 new bugs, 49 have been fixed, five
have been back ported to LLVM 15 as security patches.

###  5.5. Bugs case study

####  5.5.1. Compiler hang

LLVM may execute multiple optimizations repeatedly until a fixed point is
reached. However, this strategy can result in an infinite loop if not applied
carefully, such as when one optimization undoes the effects of a previous
optimization. Four of six hangs we found are caused by this problem.

BB1BB2BB3BB4BB5x == 3x == 2x == 2x == 3

(a) Original CFG

BB1BB2BB3BB4BB5x == 2 || x == 3x == 2x == 3

(b) Optimized CFG

Figure 8.  A piece of code we generated, simplified to CFG only. Two
optimization passes are involved in this compiler hang.
TurnSwitchRangeIntoICmp will transform 8(a) into 8(b).
FoldValueComparisonIntoPredecessors will undo the transformation, causing an
infinite loop.

For example, Figure 8 shows a simplified CFG corresponding to the code
generated by IRFuzzer. This CFG will cause a compiler hang due to the
interaction between two optimization passes. BB2 in 8(a) consists of a switch
statement with two self loop edges. The TurnSwitchRangeIntoICmp optimization
attempts to rewrite the condition as a branch predicate because x == 2 || x ==
3 can be optimized using bit operations, rewriting 8(a) into 8(b). However,
the FoldValueComparisonIntoPredecessors optimization converts this code back
into a switch statement to reduce the number of comparison operations, turning
the CFG back to 8(a). As a result, a fixed point is never reached, creating an
infinite loop.

This bug is hard to trigger since the bug can only be triggered when the
switch in 8(b) has exactly two destinations (BB2 and BB3), and the switch
conditions are consecutive, enabling the TurnSwitchRangeIntoICmp optimization.
This combination is unlikely to be created during manual testing, and can only
happen through the interaction of two largely unrelated pieces of code. Yet,
we are able to discover this catastrophic combination through our CFG mutation
strategy in a time frame amenable to run fuzzing on every nightly build with
little human intervention.

In this case, we answer RQ5 by advising the developers to carefully read code
that may modify the same location before they push out a new optimization that
changes the code.

####  5.5.2. Memory error

LLVM often hides memory management from the developers so they don’t have to
manually manage it. Still, we found five memory errors: one null pointer
dereference, two double frees and two out of bounds (OOB) accesses. After
inspection, we determined that both double free bugs were indirectly caused by
OOB accesses, which didn’t result in crash immediately. All four OOB accesses
are caused by developers using constants from the program under compilation
without validation. In these cases, an OOB access or undefined behavior in the
program being compiled were able to crash the compiler itself.

As an example, we consider a case involving vector types, shown in 5. LLVM
natively supports to enable SIMD optimizations. The insertelement IR
instruction instruction inserts a value into a vector at a specified index. If
the given index is out of the bounds, the behavior is undefined. The compiler
can leverage this to remove the insertelement instruction.

⬇

1bool CombinerHelper::matchCombineInsertVecElts(...){

2 while (...) {

3+ if (IntImm >= NumElts || IntImm < 0)

4- if (IntImm >= NumElts)

5 return false;

6 if (!MatchInfo[IntImm])

7 MatchInfo[IntImm] = TmpReg;

8 CurrInst = TmpInst;

9 ...

10 }

11}

Listing 5:  A snippet of code in AArch64 where the index (IntImm) is not
sanitized before usage. This diff is our patch to fix this bug.

⬇

1bool IRTranslator::translateExtractElement(

2 const User &U,

3 MachineIRBuilder &MIRBuilder) {

4 Register Idx;

5 const LLT VecIdxTy = LLT::scalar(PreferredVecIdxWidth);

6 Idx = MIRBuilder

7- .buildSExtOrTrunc(VecIdxTy, Idx)

8+ .buildZExtOrTrunc(VecIdxTy, Idx)

9 .getReg(0);

10 ...

11}

Listing 6:  A snippet of code in LLVM where index of a vector is treated as
signed value. This diff is our patch to fix this bug.

Figure 9.  Two bugs we found in LLVM code base. Both of them will lead to
compiler crash and have been fixed.

In most cases, LLVM’s module verifier checks for invalid indices, and will
reject any negative indices before compilation. As a result, developers may
implicitly assume that indices in this code are always non-negative. However,
the module verifier does allow undef as a valid index. Undef in LLVM
represents a value is can be anything, and is represented as an index IntImm
of $-1$ at this point in the code, resulting in an OOB access at line 7.

This example shows that our IR instruction mutation method is better than
high-level language generation, since undef is not a primitive high-level
language construct and will only be introduced through other optimizations. By
generating LLVM IR directly, we have more control over instruction operands
and can directly generate values like undef. To answer RQ5, we recommend
developers to be careful about uncommon values like undef and poison, which
may appear during compilation.

####  5.5.3. Logic error

Logic error usually starts with unclear documentation or undocumented
assumptions. Middle-end and backend are developed by different programmers,
who may interpret ambiguous documentations differently.

For example, 6 shows a bug we found in the LLVM backend. When translating the
IR instruction extractelement, the index is extended as a signed integer. The
code translates constants like char 255 into -1. This bug generates incorrect
machine instructions and affects the LLVM backend for seven architectures.

The bug was introduced in LLVM nine years ago and was never noticed for
several reasons. First, it is less common for compiler frontends to generate
vector operations, as we have seen in Section 5.2, and even more rare to use
an index that is large enough to wrap around to a negative integer. However,
more importantly, we discovered that the documentation was ambiguous with
respect to the desired behavior. The documentations indicated that “The index
may be a variable of any integer type” without giving more details on how it
should be interpreted. Therefore, when this bug was introduced nine years ago,
it was actually compliant with the incomplete documentation at the time. This
exemplifies how complex software interfaces can be incompletely specified,
which further justifies our specialized fuzzing. In this case, we have fixed
the bug and updated the documentation to reflect the intended interpretation
of the index as an unsigned integer. To answer RQ5, we encourage developers of
LLVM to communicate more on the documentations. Review and update
documentations with the development of the code would be a good practice.

##  6\. Related work

Prior work has focused on compiler testing (10.1145/3363562, 46, 47, 48). One
popular approach is to generate inputs for compilers to compile.
Purdom(purdom1972sentence, 49) generates program based on context free
grammar. Superion(8811923, 38) and Nautilus(aschermann2019nautilus, 39) also
relies on context free grammar for fuzzing. However, context free grammar
based methods cannot generate semantically meaningful programs. These efforts
are effective in testing frontend parsers, but cannot reach the backends
effectively.

While many fuzzers are testing the frontend of the compiler using grammar
based method (zeller2019fuzzing, 50), some work also tests the correctness of
middle-end (lopes2021alive2, 2, 51, 52, 53). To the best of our knowledge,
IRFuzzer is the first one to verify the compiler backend using an architecture
independent method.

Some work does end-to-end tests using high-level programming languages.
CSmith(CSmith, 4), YARPGen(10.1145/3428264, 5), and Grayc (GreyC, 13) generate
C and C++ programs. AI has also been used for program generate for the purpose
of compiler testing (DeepFuzz, 54, 55, 56). However, end-to-end testing
implies that there is a need to create a generator for every language, like
JavaScript (9152648, 40, 41), Rust (rust, 57), and Java (java1, 58, 59, 60).
POLYGLOT(POLYGLOT, 61) introduced a language-free IR and mutator based on it.
Most fuzzers have no feedback from the compiler. Even though Grayc (GreyC, 13)
introduced branch coverage feedback, it was unable to trigger backend bugs due
to language limitations and compiler optimizations discussed in Section 5.5.3.
Instead of directly generating a program, Equivalence Modulo Inputs (emi, 6,
62) mutates an existing C program to preserve its semantics. Therefore, the
program before and after mutation should have the same behavior. Combining
CSmith and EMI, Lidbury et al. mutate program to test OpenCL compiler
(Lidbury, 63). However, the language limits these work, since the generator
cannot help when the language frontend cannot exercise a feature in the
compiler.

Formal verification is another valuable part of compiler verification
(10.1145/966221.966235, 64). Verasco (Jourdan-LBLP-2015, 8) is a formally
verified C analyzer. CompCert (10.1145/1538788.1538814, 65) is a compiler for
a subset of C that is formally verified. There is work that verifies other
languages, like Rust (10.1145/3360573, 66) and Lustre (Bourke-BDLPR-2017, 9).
However, formal verification cannot scale to large compilers like LLVM,
therefore it has a limited impact in the community.

There is also work on intermediate representation generation. FuzzMutate
directly generates LLVM IR(FuzzMutate, 12). However, FuzzMutate has no
feedback unless combined with fuzzers like AFL++(AFLplusplus, 10) or
libFuzzer(serebryany2016continuous, 14). Some work focus on testing of a
specific compiler (10.1145/3597926.3598053, 67, 68). Tzer focuses on IR
mutation in the context of a tensor compiler (10.1145/3527317, 68). However,
Tzer relies on LLVM’s Coverage Sanitizer that only tracks code coverage.
Similar to IRFuzzer’s approach, ClassMing directly mutates on Java byte
code(8811957, 69). Neither Tzer nor ClassMing designed a feedback method that
can apply to LLVM’s scenarios.

##  7\. Conclusion

In this paper, we propose IRFuzzer, a fuzzer specializing in fuzzing LLVM
instruction selection. To generate inputs that are semantically and
syntactically correct, we first identify the challenges in IR generation that
don’t exist in high-level language generation. We create a mutator that
maintains semantic correctness by splitting a block and inserting a sCFG in
between. Then, we make sure that the IR instruction we inserted is
syntactically correct using a descriptive language to model all IR
instructions. Therefore, the IR program we generated can always be compiled by
the backend. We also propose a new coverage metric to better monitor the
fuzzing status to keep track of the program behavior. IRFuzzer also decodes
this coverage table for mutation guidance.

Our evaluation shows that IRFuzzer outperforms existing backend and end-to-end
state-of-the-art fuzzers. IRFuzzer achieved higher matcher table coverage in
all LLVM backend architectures. Specialized fuzzing is required for
specialized tools, and IRFuzzer is efficient enough to be used within the
context of a regular development process.

Using IRFuzzer, we have identified 74 bugs in upstream LLVM code that have
been confirmed by developers. 49 of these bugs have been fixed, showing that
these bugs provide useful insight to LLVM developers. These findings indicate
that there are fertile opportunities for specialized fuzzing despite popular
end-to-end compiler testing. We demonstrated that IRFuzzer is effective in
finding bugs in LLVM backend.

## References

  * (1) C. Lattner and V. Adve  “LLVM: a compilation framework for lifelong program analysis & transformation”  In _International Symposium on Code Generation and Optimization, 2004. CGO 2004._ , 2004, pp. 75–86  DOI: 10.1109/CGO.2004.1281665
  * (2) Nuno P. Lopes et al.  “Alive2: Bounded Translation Validation for LLVM”  In _Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation_ , PLDI 2021  Virtual, Canada: Association for Computing Machinery, 2021, pp. 65–79  DOI: 10.1145/3453483.3454030
  * (3) Andrea Fioraldi, Dominik Christian Maier, Dongjia Zhang and Davide Balzarotti  “LibAFL: A Framework to Build Modular and Reusable Fuzzers”  In _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security_ , CCS ’22  Los Angeles, CA, USA: Association for Computing Machinery, 2022, pp. 1051–1065  DOI: 10.1145/3548606.3560602
  * (4) Xuejun Yang, Yang Chen, Eric Eide and John Regehr  “Finding and Understanding Bugs in C Compilers”  In _Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation_ , PLDI ’11  San Jose, California, USA: Association for Computing Machinery, 2011, pp. 283–294  DOI: 10.1145/1993498.1993532
  * (5) Vsevolod Livinskii, Dmitry Babokin and John Regehr  “Random Testing for C and C++ Compilers with YARPGen”  In _Proc. ACM Program. Lang._ 4.OOPSLA Association for Computing Machinery, 2020  DOI: 10.1145/3428264
  * (6) Vu Le, Mehrdad Afshari and Zhendong Su  “Compiler Validation via Equivalence modulo Inputs”  In _Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation_ , PLDI ’14  Edinburgh, United Kingdom: Association for Computing Machinery, 2014, pp. 216–226  DOI: 10.1145/2594291.2594334
  * (7) Qirun Zhang, Chengnian Sun and Zhendong Su  “Skeletal Program Enumeration for Rigorous Compiler Testing”  In _Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation_ , PLDI 2017  Barcelona, Spain: Association for Computing Machinery, 2017, pp. 347–361  DOI: 10.1145/3062341.3062379
  * (8) Jacques-Henri Jourdan et al.  “A Formally-Verified C Static Analyzer”  In _POPL 2015: 42nd symposium Principles of Programming Languages_ ACM Press, 2015, pp. 247–259  URL: http://xavierleroy.org/publi/verasco-popl2015.pdf
  * (9) Timothy Bourke et al.  “A formally verified compiler for Lustre”  In _PLDI 2017: Programming Language Design and Implementation_ ACM Press, 2017, pp. 586–601  URL: http://xavierleroy.org/publi/velus-pldi17.pdf
  * (10) Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt and Marc Heuse  “AFL++ : Combining Incremental Steps of Fuzzing Research”  In _14th USENIX Workshop on Offensive Technologies (WOOT 20)_ USENIX Association, 2020  URL: https://www.usenix.org/conference/woot20/presentation/fioraldi
  * (11) “Fuzzing LLVM libraries and tools” Accessed: 2023-09-22, https://llvm.org/docs/FuzzingLLVM.html
  * (12) Justin Bogner  “Adventures in Fuzzing Instruction Selection”, https://llvm.org/devmtg/2017-03/assets/slides/adventures_in_fuzzing_instruction_selection.pdf, 2017
  * (13) Karine Even-Mendoza, Arindam Sharma, Alastair F. Donaldson and Cristian Cadar  “GrayC: Greybox Fuzzing of Compilers and Analysers for C”  In _Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis_ , ISSTA 2023  Seattle, WA, USA: Association for Computing Machinery, 2023, pp. 1219–1231  DOI: 10.1145/3597926.3598130
  * (14) Kosta Serebryany  “Continuous fuzzing with libfuzzer and addresssanitizer”  In _2016 IEEE Cybersecurity Development (SecDev)_ , 2016, pp. 157–157  IEEE
  * (15) Seo Sanghyeon  “Rust triggers LLVM ARM backend bug” [Online; accessed 21-Mar-2023], https://github.com/rust-lang/rust/issues/9117, 2013
  * (16) Shuitao Gan et al.  “CollAFL: Path Sensitive Fuzzing”  In _2018 IEEE Symposium on Security and Privacy (SP)_ , 2018, pp. 679–696  DOI: 10.1109/SP.2018.00040
  * (17) B.. Rosen, M.. Wegman and F.. Zadeck  “Global Value Numbers and Redundant Computations”  In _Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages_ , POPL ’88  San Diego, California, USA: Association for Computing Machinery, 1988, pp. 12–27  DOI: 10.1145/73560.73562
  * (18) Reese T Prosser  “Applications of boolean matrices to the analysis of flow diagrams”  In _Papers presented at the December 1-3, 1959, eastern joint IRE-AIEE-ACM computer conference_ , 1959, pp. 133–138
  * (19) “The LLVM Target-Independent Code Generator” Accessed: 2023-09-22, https://llvm.org/docs/CodeGenerator.html
  * (20) “GlobalIsel” Accessed: 2023-09-22, https://llvm.org/docs/GlobalISel/index.html
  * (21) “TableGen Overview” Accessed: 2023-09-22, https://llvm.org/docs/TableGen/
  * (22) “American fuzzy lop”  URL: http://lcamtuf.coredump.cx/afl/
  * (23) Xiaogang Zhu, Sheng Wen, Seyit Camtepe and Yang Xiang  “Fuzzing: A Survey for Roadmap”  In _ACM Comput. Surv._ 54.11s Association for Computing Machinery, 2022  DOI: 10.1145/3512345
  * (24) Jinghan Wang et al.  “Be Sensitive and Collaborative: Analyzing Impact of Coverage Metrics in Greybox Fuzzing”  In _22nd International Symposium on Research in Attacks, Intrusions and Defenses (RAID 2019)_ USENIX Association, 2019, pp. 1–15  URL: https://www.usenix.org/conference/raid2019/presentation/wang
  * (25) Jinghan Wang, Chengyu Song and Heng Yin  “Reinforcement Learning-based Hierarchical Seed Scheduling for Greybox Fuzzing”  In _2021 Network and Distributed System Security Symposium_ DOI: 10.14722/ndss.2021.24486
  * (26) Cornelius Aschermann, Sergej Schumilo, Ali Abbasi and Thorsten Holz  “Ijon: Exploring Deep State Spaces via Fuzzing”  In _2020 IEEE Symposium on Security and Privacy (SP)_ , 2020, pp. 1597–1612  DOI: 10.1109/SP40000.2020.00117
  * (27) M. Böhme, V. Pham and A. Roychoudhury  “Coverage-Based Greybox Fuzzing as Markov Chain”  In _IEEE Transactions on Software Engineering_ 45.5, 2019, pp. 489–506  DOI: 10.1109/TSE.2017.2785841
  * (28) Chenyang Lyu et al.  “MOPT: Optimized Mutation Scheduling for Fuzzers”  In _28th USENIX Security Symposium (USENIX Security 19)_ USENIX Association, 2019, pp. 1949–1966  URL: https://www.usenix.org/conference/usenixsecurity19/presentation/lyu
  * (29) Dongdong She, Abhishek Shah and Suman Jana  “Effective Seed Scheduling for Fuzzing with Graph Centrality Analysis”  In _43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022_ IEEE, 2022, pp. 2194–2211  DOI: 10.1109/SP46214.2022.9833761
  * (30) Sebastian Österlund, Kaveh Razavi, Herbert Bos and Cristiano Giuffrida  “ParmeSan: Sanitizer-guided Greybox Fuzzing”  In _29th USENIX Security Symposium (USENIX Security 20)_ USENIX Association, 2020, pp. 2289–2306  URL: https://www.usenix.org/conference/usenixsecurity20/presentation/osterlund
  * (31) Yuyang Rong, Peng Chen and Hao Chen  “Int egrity: Finding Integer Errors by Targeted Fuzzing”  In _Security and Privacy in Communication Networks: 16th EAI International Conference, SecureComm 2020, Washington, DC, USA, October 21-23, 2020, Proceedings, Part I 16_ , 2020, pp. 360–380  Springer
  * (32) Dae R. Jeong et al.  “Razzer: Finding Kernel Race Bugs through Fuzzing”  In _2019 IEEE Symposium on Security and Privacy (SP)_ , 2019, pp. 754–768  DOI: 10.1109/SP.2019.00017
  * (33) Cornelius Aschermann et al.  “REDQUEEN: Fuzzing with Input-to-State Correspondence.”  In _NDSS_ 19, 2019, pp. 1–15
  * (34) Dongdong She et al.  “NEUZZ: Efficient fuzzing with neural program smoothing”  In _2019 IEEE Symposium on Security and Privacy (SP)_ , 2019, pp. 803–817  IEEE
  * (35) Peng Chen and Hao Chen  “Angora: Efficient Fuzzing by Principled Search”  In _2018 IEEE Symposium on Security and Privacy (SP)_ , 2018, pp. 711–725  DOI: 10.1109/SP.2018.00046
  * (36) Mingyuan Wu et al.  “One Fuzzing Strategy to Rule Them All”  In _Proceedings of the 44th International Conference on Software Engineering_ , ICSE ’22  Pittsburgh, Pennsylvania: Association for Computing Machinery, 2022, pp. 1634–1645  DOI: 10.1145/3510003.3510174
  * (37) Yuyang Rong, Chibin Zhang, Jianzhong Liu and Hao Chen  “Valkyrie: Improving Fuzzing Performance Through Deterministic Techniques”  In _22nd IEEE International Conference on Software Quality, Reliability and Security, QRS 2022, Guangzhou, China, December 5-9, 2022_ IEEE, 2022, pp. 628–639  DOI: 10.1109/QRS57517.2022.00069
  * (38) Junjie Wang, Bihuan Chen, Lei Wei and Yang Liu  “Superion: Grammar-Aware Greybox Fuzzing”  In _2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)_ , 2019, pp. 724–735  DOI: 10.1109/ICSE.2019.00081
  * (39) Cornelius Aschermann et al.  “NAUTILUS: Fishing for Deep Bugs with Grammars.”  In _NDSS_ , 2019
  * (40) Soyeon Park et al.  “Fuzzing JavaScript Engines with Aspect-preserving Mutation”  In _2020 IEEE Symposium on Security and Privacy (SP)_ , 2020, pp. 1629–1642  DOI: 10.1109/SP40000.2020.00067
  * (41) Samuel Groß  “Fuzzil: Coverage guided fuzzing for javascript engines”  In _Department of Informatics, Karlsruhe Institute of Technology_ , 2018
  * (42) Junjie Wang et al.  “FuzzJIT: Oracle-Enhanced Fuzzing for JavaScript Engine JIT Compiler”  In _32nd USENIX Security Symposium, USENIX Security 2023, Anaheim, CA, USA, August 9-11, 2023_ USENIX Association, 2023  URL: https://www.usenix.org/conference/usenixsecurity23/presentation/wang-junjie
  * (43) Anonymous  “IRFuzzer artifacts”  Zenodo, 2023  DOI: 10.5281/zenodo.8388301
  * (44) George Klees et al.  “Evaluating Fuzz Testing”  In _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ , CCS ’18  Toronto, Canada: Association for Computing Machinery, 2018, pp. 2123–2138  DOI: 10.1145/3243734.3243804
  * (45) Karine Even-Mendoza, Arindam Sharma, Alastair F. Donaldson and Cristian Cadar  “Artifact of GrayC: Greybox Fuzzing of Compilers and Analysers for C” GitHub Repository of GrayC: https://github.com /srg-imperial/GrayC/tree/main/ISSTA-2023-AE.  Zenodo, 2023  DOI: 10.5281/zenodo.7978251
  * (46) Junjie Chen et al.  “A Survey of Compiler Testing”  In _ACM Comput. Surv._ 53.1 Association for Computing Machinery, 2020  DOI: 10.1145/3363562
  * (47) Haoyang Ma  “A Survey of Modern Compiler Fuzzing”, 2023  arXiv:2306.06884 [cs.SE]
  * (48) Michaël Marcozzi, Qiyi Tang, Alastair F. Donaldson and Cristian Cadar  “Compiler Fuzzing: How Much Does It Matter?”  In _Proc. ACM Program. Lang._ 3.OOPSLA Association for Computing Machinery, 2019  DOI: 10.1145/3360581
  * (49) Paul Purdom  “A sentence generator for testing parsers”  In _BIT Numerical Mathematics_ 12.3 Springer, 1972, pp. 366–375
  * (50) Andreas Zeller et al.  “The fuzzing book”  CISPA+ Saarland University, 2019
  * (51) William Mansky and Elsa Gunter  “A framework for formal verification of compiler optimizations”  In _Interactive Theorem Proving: First International Conference, ITP 2010, Edinburgh, UK, July 11-14, 2010. Proceedings 1_ , 2010, pp. 371–386  Springer
  * (52) Vsevolod Livinskii, Dmitry Babokin and John Regehr  “Fuzzing Loop Optimizations in Compilers for C++ and Data-Parallel Languages”  In _Proc. ACM Program. Lang._ 7.PLDI Association for Computing Machinery, 2023  DOI: 10.1145/3591295
  * (53) Nuno P. Lopes, David Menendez, Santosh Nagarakatte and John Regehr  “Practical Verification of Peephole Optimizations with Alive”  In _Commun. ACM_ 61.2 Association for Computing Machinery, 2018, pp. 84–91  DOI: 10.1145/3166064
  * (54) Xiao Liu, Xiaoting Li, Rupesh Prajapati and Dinghao Wu  “DeepFuzz: Automatic Generation of Syntax Valid C Programs for Fuzz Testing”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 33.01, 2019, pp. 1044–1051  DOI: 10.1609/aaai.v33i01.33011044
  * (55) Yinlin Deng et al.  “Large Language Models are Zero-Shot Fuzzers: Fuzzing Deep-Learning Libraries via Large Language Models”  In _Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis_ , 2023, pp. 423–435
  * (56) Chunqiu Steven Xia et al.  “Universal Fuzzing via Large Language Models”, 2023  arXiv:2308.04748 [cs.SE]
  * (57) Kyle Dewey, Jared Roesch and Ben Hardekopf  “Fuzzing the Rust Typechecker Using CLP (T)”  In _2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE)_ , 2015, pp. 482–493  DOI: 10.1109/ASE.2015.65
  * (58) Yuting Chen et al.  “Coverage-Directed Differential Testing of JVM Implementations”  In _Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation_ , PLDI ’16  Santa Barbara, CA, USA: Association for Computing Machinery, 2016, pp. 85–99  DOI: 10.1145/2908080.2908095
  * (59) Emin Gün Sirer and Brian N. Bershad  “Using Production Grammars in Software Testing”  In _Proceedings of the 2nd Conference on Domain-Specific Languages_ , DSL ’99  Austin, Texas, USA: Association for Computing Machinery, 2000, pp. 1–13  DOI: 10.1145/331960.331965
  * (60) Mingyuan Wu et al.  “JITfuzz: Coverage-Guided Fuzzing for JVM Just-in-Time Compilers”  In _Proceedings of the 45th International Conference on Software Engineering_ , ICSE ’23  Melbourne, Victoria, Australia: IEEE Press, 2023, pp. 56–68  DOI: 10.1109/ICSE48619.2023.00017
  * (61) Yongheng Chen et al.  “One Engine to Fuzz ’em All: Generic Language Processor Testing with Semantic Validation”  In _2021 IEEE Symposium on Security and Privacy (SP)_ , 2021, pp. 642–658  DOI: 10.1109/SP40001.2021.00071
  * (62) Vu Le, Chengnian Sun and Zhendong Su  “Finding Deep Compiler Bugs via Guided Stochastic Program Mutation”  In _Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications_ , OOPSLA 2015  Pittsburgh, PA, USA: Association for Computing Machinery, 2015, pp. 386–399  DOI: 10.1145/2814270.2814319
  * (63) Christopher Lidbury, Andrei Lascu, Nathan Chong and Alastair F. Donaldson  “Many-Core Compiler Fuzzing”  In _Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation_ , PLDI ’15  Portland, OR, USA: Association for Computing Machinery, 2015, pp. 65–76  DOI: 10.1145/2737924.2737986
  * (64) Maulik A. Dave  “Compiler Verification: A Bibliography”  In _SIGSOFT Softw. Eng. Notes_ 28.6 Association for Computing Machinery, 2003, pp. 2  DOI: 10.1145/966221.966235
  * (65) Xavier Leroy  “Formal Verification of a Realistic Compiler”  In _Commun. ACM_ 52.7 Association for Computing Machinery, 2009, pp. 107–115  DOI: 10.1145/1538788.1538814
  * (66) Vytautas Astrauskas, Peter Müller, Federico Poli and Alexander J. Summers  “Leveraging Rust Types for Modular Specification and Verification”  In _Proc. ACM Program. Lang._ 3.OOPSLA Association for Computing Machinery, 2019  DOI: 10.1145/3360573
  * (67) Haoyang Ma et al.  “Fuzzing Deep Learning Compilers with HirGen”  In _Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis_ , ISSTA 2023  Seattle, WA, USA: Association for Computing Machinery, 2023, pp. 248–260  DOI: 10.1145/3597926.3598053
  * (68) Jiawei Liu et al.  “Coverage-Guided Tensor Compiler Fuzzing with Joint IR-Pass Mutation”  In _Proc. ACM Program. Lang._ 6.OOPSLA1 Association for Computing Machinery, 2022  DOI: 10.1145/3527317
  * (69) Yuting Chen, Ting Su and Zhendong Su  “Deep Differential Testing of JVM Implementations”  In _2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)_ , 2019, pp. 1257–1268  DOI: 10.1109/ICSE.2019.00127