On the Effectiveness of Interpreter-Guided Compiler Testing

Several solutions have been proposed to aid in testing and debugging programming language implementations. The main challenges of compiler testing are the automatic generation of test programs and oracles for their validation [5]. Existing work covers black box approaches to test generation using pseudo-random generation [34], grammar-based solutions [26], and program mutations [18]. The most commonly used oracle is differential testing [21], where two different implementations (or configurations) are compared side by side.

Lately, several works have explored the path of program fuzzing and differential testing between different Virtual Machines for the same programming language [7, 6, 13, 35, 24]. Similar approaches have been proposed to test virtual machine optimizations [1, 10, 2].

Recently, graybox approaches have been proposed to increase the efficiency of compiler testing, either guided by coverage [9] or interpreter concolic meta-interpretation[25].

A recent promising approach to compiler testing is guiding test generation with an interpreter [25]. This solution uses concolic execution on the interpreter instruction handlers (i.e., the code implementing each instruction e.g., a bytecode) to identify their different execution paths as sequences of symbolic constraints. Then, the set of concrete values that satisfies a path’s constraints is used to execute the program along that path. The insight is that interpreter paths represent the language implementation semantics, and thus they can be exploited to test the compiler using differential testing.

To illustrate this solution, let us consider the instruction implementing addition in Pharo, a dynamically typed high-level language, illustrated in Figure 1. This operation works on different types and presents four execution paths, as illustrated in Table 1. These four different paths should be semantically equivalent in both the interpreter and compiler, otherwise they show a fault in one of the implementations.

Our experimentation platform is the Pharo Virtual Machine and its Cogit JIT compiler, an industrial-level Virtual Machine [14, 23]. The VM implements a threaded byte-code interpreter and a linear non-optimizing JIT compiler named Cogit [22] that includes polymorphic inline caches [12]. It implements 255 bytecode instructions and 340 native methods, several duplicated in both the interpreter and the JIT compiler.

In their paper, Polito et al. explored a design using concolic testing and differential testing together, focusing on its ability to find interpreter/compiler differences [25]. However, little has been said about the effectiveness and limits of this solution, which would shed light on future improvements and research. In this paper, we explore the following research questions:

RQ1: Effectiveness.

How effective is it to combine Differential Testing with Concolic testing for Interpreter-guided testing?

RQ2: Limits.

What are the limits of using an interpreter as a source of compiler tests?

RQ3: Mutations.

How much can Constraint Mutations improve the effectiveness of compiler testing? Can they be used to explore a major diversity of compiler paths?

The Pharo compiler makes specific optimization decisions that are independent of the interpreter. Since a compiler operates at a lower level, it must deal with particular decisions like the following:

Calling convention.

The compiler defines a calling convention that maximizes the usage of registers depending on the method’s arity. Meanwhile, the interpreter is oblivious to registers and uses a stack.

Frameless methods.

The compiler optimizes code generation when a method does not need a method stack frame (see Figure 2). The interpreter, on the other hand, uses a single strategy and therefore, the concolic runner generates a single test case to execute.

Block closures.

Compiling in the context of a block closure or a method has different behavior because the code layout differs, while the behavior is the same in the interpreter.

Integer encoding.

The interpreter manages integer representations in the same manner. The compiler, on the other hand, covers different types of integer representations that can be encoded differently in machine code. For example, consider the case of shiftable or rotatable immediate values (see Figure 3).

These properties hint to us that simple fuzzing of compiler parameters/configurations could improve over the first three cases. Compiler settings are independent of the tested instruction, and a generic input generation based on the interpreter can’t reach them. However, to cover the different integer encoders, we need to augment the generated tests with domain (compiler)-specific integer variations.

One of the main weaknesses of guiding test generation with single interpreter instructions is that generated tests do not cover programs with many instructions. Thus, code-generation decisions that are guided by a sequence of instructions, such as register allocation (see Figure 4) or literal encoding, are not reachable by single instruction programs. Overcoming this limitation requires a different fuzzing approach generating random instruction sequences.

The classes implementing the Pharo JIT compiler contain responsibilities other than compilation and code generation: e.g., runtime interactions,code garbage collection, trampolines, and polymorphic inline caches. Since these features are activated by compiler-specific behavior, their code is inherently unreachable from the interpreter. For example, generated tests are not capable of covering different machine code GC configurations (see Figure 5). This suggests, on the one hand, that refactoring the compiler code to separate these responsibilities could simplify further analyses. On the other hand, testing these features requires separate tests and fuzzing strategies.

The PharoVM is written in Pharo itself, which allows its simulation as a normal Pharo program. In this mode, the VM supports debugging features that are unavailable in a production environment (see Figure 6). To make this behavior reachable, test execution should be augmented to run in a debugging environment. This raises the question of whether it is meaningful to test the VM’s debugger features.

The compiler backend is engineered as a generic compiler instruction supporting a complete assembly-like intermediate language (CogRTL), which is reusable in different scenarios and compiler frontends. However, not all features from this intermediate language are exercised by our evaluated frontend. This is due to the backend’s language-independent design, which supports functionalities beyond the front end’s requirements. A common example of unused frontend features is the code generation for instructions that are not used by the frontend (see Figure 7).

Recall that each generated test is represented as a collection of logic constraints, defining a single conjunction logic constraint. We then apply a set of mutations generating, for each possible mutation match, a new test mutant. Moreover, we introduce two steps before constraint mutations to limit the explosion of generated cases. Firstly, we perform a cleaning step, keeping only satisfiable paths. Secondly, we perform constraint minimization. Finally, we test the individual mutants and compare them with the original cases. Each mutation is applied independently of other mutants departing from the baseline of cases commented in the previous section.

Generated logic constraints contain redundant constraints and therefore increase the amount of redundant mutants. We first transform each constraint to its Conjunctive normal form (CNF), which allows us to reduce the number of mutation criteria matches. Then, we reduce well-known equivalences to minimize the constraint’s size. Finally, knowing that the logic expression is in CNF, we reduce the size of these constraints by removing redundant ones under the expression’s root, which by definition is an and expression.

Following our third research question, we focus our mutation design on mutations that preserve the semantics of the interpreter while improving compiler code coverage. The key idea is to segment the set of valid inputs into subsets that are more restrictive than the initial one. This allows us to segment the universe of possible values, forcing the constraint solver to generate diverse values. For example, consider Figure 8 illustrates an input set segmented into four different subsets. From this idea, we designed four different mutation operators:

• $\mathrm{■}$

  Subset Segmentation: Mutates each path containing the condition $isInt(x)$ by adding bounds to it. For example, $isInt(x)\wedge x>n$ and $isInt(x)\wedge x\le n$.

• $\mathrm{■}$

  Shiftable Integers: Mutates each path containing the condition $isInt(x)$ by forcing a random value that can be represented as shiftable 16bit integer. For example, $0x00010000$ (65536) and $0x12340000$ (1195376640) can be represented as $0x0001\ll 16$ and $0x1234\ll 16$ respectively, both with a left shift magnitude of 16.

• $\mathrm{■}$

  Commutative: Mutates each path containing commutative operators by reversing the operands.

• $\mathrm{■}$

  Randomness: Mutates each path containing binary operators by adding a same random number to both sides of the operator. For example, form $var(A)\otimes n$ becomes $var(A)+X\otimes n+X$, where $X$ is a random number between the minimum and maximum representable numbers.

Constraint mutations generate a total of 45233 new test cases. Table 3 presents the reached new nodes obtained from these new test cases.

The first column lists the mutators used. The second column shows the number of mutants generated by each mutator, along with a factor indicating how many times that number multiplies the number of base cases. The third column displays the number of newly covered nodes reached by the mutation. Despite the substantial number of mutants generated, the total number of newly reached nodes remains limited, with a maximum of 4 unique nodes discovered across all mutations.

Segmentation and Shiftable produced the highest number of mutants (15,115 and 11,150, respectively), followed by Commutative (10,595). These mutations increased the number of generated test cases by factors of 3.27x, 2.41x, and 2.29x, respectively. However, they all reach the same 4 new method nodes, indicating that their effects may be redundant in terms of reachability. Conversely, BinArithOpRand generated only 210 mutants (+0.45x), and IsNotIntNotEqRand produced 8,163 mutants (+1.76x), yet they reached the same or fewer new nodes (with IsNotIntNotEqRand covering only 2 additional nodes).

Several works evaluate the impact and validity of compiler testing approaches. Most compiler testing techniques use the number of detected compiler bugs [4, 19]. In this work, we decided to approach this problem in a white-box fashion, using code coverage. A similar approach is taken by [11] where they generate random valid compiler inputs using grammars.

When comparing compiler testing effectiveness among different techniques, the baseline convention is to use already-known bugs to prove the fuzzing accuracy. Mettoc [29] proposes to use metamorphic relations to generate equivalent source programs. Similarly, equivalence module inputs compares compilers by removing dead code modulo program inputs from source programs [19]. They establish a set of target configurations finding common compiler bugs using OpenCL benchmarks. Another technique compares Randomized Differential Testing, Different Optimization Levels and Equivalence Modulo Input proposing a new measurement: Correcting Commits [4]. They perform their experiments using CSSmith to generate unknown programs and compare three different techniques. Finally, other work compares submitted bug entries to GCC and LLVM [28].

In this work, we used code coverage as a proxy for fuzzing effectiveness: the insight is that the larger the coverage, the more effective the fuzzer. Several works study in depth the relation between these two properties, although not in compilers.

Böhme et al. show the relation between coverage and bugs mentioning “the best fuzzer at achieving coverage, may not be best at finding bugs” [3]. They study the correlation between coverage and bug finding using branch coverage.

Wolff et al. suggest that fuzzer performance evaluation is usually driven by a specific benchmark and proposes a methodology to quantify the impact of benchmark properties on the performance evaluation [32]. They found that the measured performance depends on the properties of the programs used for benchmarking. Also, they explain how specific evaluation setup leads to a superior ranking of fuzzers in practice.

Klooster et al. study how to adapt fuzzing to be fitted in CI/CD pipelines and what is a reasonable fuzzing duration that is compatible with CI/CD pipelines [16]. They explore the effectiveness of fuzzing testing in CI/CD pipelines, suggesting that continuous fuzzing is beneficial for secure software development processes.

Several limitations have been identified in the past on concolic testing [27]. For example, they list issues managing 64-bit numbers, bitwise operations, and solution generation overhead. Our focus is on understanding its limitations in compiler testing, to improve coverage.

Several solutions propose variants to overcome the limits of concolic testing. Some work proposes the usage of heuristics to reduce false alarms [15]. Other approaches combine concolic testing with random testing until saturation with a fixed bound [20]. When random testing saturates, they switch to Concolic Execution keeping the current program state. Finally, other work propose the use of Symbolic Backward Execution [8]. In particular, they propose Symetric Execution which demonstrates to be efficient in finding targeted inputs.