Abstract.

Differential testing can be an effective way to find bugs in software systems with multiple implementations that conform to the same specification, like compilers, network protocol parsers, or language runtimes. Specifications for such systems are often standardized in natural language documents, like Instruction Set Architecture (ISA) specifications or IETF RFC’s. Large Language Models (LLMs) have demonstrated potential in both generating tests and handling large volumes of natural language text, making them well-suited for analyzing artifacts like specification documents, bug reports, and code implementations. In this work, we leverage natural language and code artifacts to guide LLMs to generate targeted tests that highlight meaningful behavioral differences between implementations, including those corresponding to bugs. We introduce \tool, a framework for generating differential tests with LLMs using prompt chaining. We demonstrate \tool’s efficacy on two different (extensively tested) systems, eBPF runtimes and Wasm validators. Using \tool, we generated 1901 differentiating tests, uncovering at least four distinct and confirmed bugs in eBPF, including a kernel memory leak, inconsistent behavior in jump instructions, undefined behavior when using the stack pointer, and tests with infinite loops that hang the verifier in ebpf-for-windows. We also found 299 differentiating tests in Wasm validators pointing to two confirmed and fixed bugs.

1. Introduction

Differential testing is an approach for automatically generating potentially bug-finding tests for applications that correspond to multiple implementations of the same functionality (McKeeman, 1998). The key idea is to test two or more different systems (or two different versions of the same system) that should behave the same way under the same conditions on the same inputs. If their output behavior differs, it is likely that at least one of the implementations is incorrect.

Differential testing has shown significant success especially in testing language implementations, such as uncovering bugs in C compilers (Yang et al., 2011a; Le et al., 2014) or browser engines, for example revealing inconsistencies in JavaScript interpreters and JIT compilers (Bernhard et al., 2022). It also can be useful for testing cross-platform consistency (i.e., the same system across different configurations or operating systems) (Fazzini and Orso, 2017) or versions (as in regression testing) (Godefroid et al., 2020).

Generating tests that specifically target differences between two versions of a program is especially challenging, as it involves simultaneously searching the vast input space of two programs to find rare inputs that trigger often subtle discrepancies (McKeeman, 1998). Existing approaches to find such tests limit the possible search space by borrowing techniques from symbolic execution (Rutledge and Orso, 2022), guided semantic aware program generation (Kapus and Cadar, 2017), type aware mutations (Jay and Miller, 2018), and code coverage optimizations (Chen et al., 2016). While some approaches leverage semantic and syntactic properties of the code or use information from static analysis tools, they are significantly limited in their ability to harness the wealth of information available from natural language artifacts.

Large Language Models (LLMs) excel at extracting and understanding information from large amounts of natural language text, enabling a wide variety of tasks such as program comprehension, bug localization, and software testing. Recent research has shown significant promise in leveraging LLMs to enhance various testing techniques. For instance, LLMs have been used to generate more effective mutations in mutation testing (Deng et al., 2023), to create higher-quality unit tests (Rao et al., 2023; Alshahwan et al., 2024; Li et al., 2023b; Liu et al., 2024), and to improve fuzzing methods by producing diverse and targeted inputs (Xia et al., 2024).

In this work, we propose a differential testing technique that leverages natural language and code artifacts describing the software systems under test to inform and prompt an LLM to produce effective, and targeted, differential tests. The extracted information describes the system specification, its source code implementation, and historical bug information.

We realize this intuition in \tool, a general approach to differential testing of multiple systems implemented with respect to a documented specification, and with functionality that can be decomposed into testable units. \toolis well-suited for testing systems that correspond to, or integrally include, language compilers, runtimes, and verification systems, like network protocol parsers or JVM or EVM or web browsers. This is the predominant domain for differential testing applications in research (Li and Su, 2023; Chen et al., 2023; Song et al., 2022) and practice (Hicks, [n. d.]). Such systems are typically associated with comprehensive language specification documentation, like the Instruction Set Architecture (ISA) specification associated with eBPF (D. Thaler, 2024), or the WebAssembly (Wasm) language specification (Group, 2024). Moreover, testing these types of systems can be naturally decomposed into testing language instructions or subsets thereof.

We demonstrate \toolon various implementations of Wasm and eBPF runtimes, which both have rich evolving natural language artifacts that \toolcan leverage, and are widely used in practice. Both runtimes vary in domain, the type of contextual information that our approach must extract from the natural language artifacts, and the format and language of the tests to be generated (see Section 4), demonstrating the generalizability of \tool.

Using \tool, we found 299 differentiating tests across four different implementations of Wasm validators. Upon manual analysis, we found that these point to at least two bugs which includes a type mismatch and cast of out-of-bounds. These bugs were reported to the maintainers of Wasm and have now been fixed. We also generated 1901 differentiating tests, that helped discover at least four distinct bugs across three different implementations of eBPF runtimes. These include a kernel memory leak, inconsistent behavior in jump instructions, undefined behavior when using the stack pointer, and tests with infinite loops that hang the verifier in ebpf-for-windows. These bugs were confirmed by the contributors of eBPF and issues have been filed for them.

In summary, we make the following contributions:

• •

  We release \tool, the first differential test generation framework that uses natural language specifications and code artifacts to generate tests.

• •

  We demonstrate the generalizability of the framework by evaluating it on two real-world systems, eBPF and Wasm.

• •

  We expand the existing test suites for both eBPF and Wasm, and contribute to open source.

• •

  We find bugs in the implementations of both eBPF and Wasm runtimes, which have been reported to the maintainers of the projects. The Wasm bugs have been fixed since we reported them.

2. Illustrative Example

This section presents an example illustrating how \tooluses natural language specifications and code artifacts to generate tests for eBPF. First, given a natural language specification document , \toolextracts a list of instructions in the underlying language, along with the corresponding constraints for each instruction. For example, constraints extracted for the RSH instruction include:

1. (1)

   The RSH instruction performs a right shift operation. The destination register (dst) is shifted right by the number of bits specified in the source operand (src or imm).

2. (2)

   The source operand can come from either the src register (if the source bit in the opcode is set to X) or the immediate value (if the source bit in the opcode is set to K).

3. (3)

   For ALU: {RSH, K, ALU} means d⁢s⁢t=(u⁢32)⁢(d⁢s⁢t>>i⁢m⁢m)𝑑𝑠𝑡𝑢32much-greater-than𝑑𝑠𝑡𝑖𝑚𝑚dst=(u32)(dst>>imm)italic_d italic_s italic_t = ( italic_u 32 ) ( italic_d italic_s italic_t > > italic_i italic_m italic_m ) and {RSH, X, ALU} means d⁢s⁢t=(u⁢32)⁢(d⁢s⁢t>>s⁢r⁢c)𝑑𝑠𝑡𝑢32much-greater-than𝑑𝑠𝑡𝑠𝑟𝑐dst=(u32)(dst>>src)italic_d italic_s italic_t = ( italic_u 32 ) ( italic_d italic_s italic_t > > italic_s italic_r italic_c ).

Next, for each considered instruction \toolextracts the implementation of that instruction from each of the two codebases corresponding to the systems under test. For example, \toolextracts an implementation of RSH from the source code for eBPF in linux ARM 32, a subset of which includes:

1

2

3case BPF_ALU | BPF_RSH | BPF_X:

4 case BPF_ALU64 | BPF_RSH | BPF_X:

5 switch (BPF_SRC(code)) {

6 case BPF_X:

7 emit_a32_alu_r64(is64,dst,src,ctx,BPF_OP(code));

8 break;

9 case BPF_K:

10 if (unlikely(imm > 31))

11 return -EINVAL;

12

Listing 1: RSH source code extracted from the bpf implementation from linux arm 32 implementation

Given two code snippets, \toolthen reasons about the implementation differences, such as “Checking of Immediate Value: The first implementation checks if the immediate value is greater than 31 or 63 for 32-bit and 64-bit operations respectively. The second implementation does not perform this check.”

\tool

additionally looks at historical bugs to generate a set of bug classes to guide test generation. For example, “Shift Operation Bug: These bugs occur when the JIT compiler incorrectly handles shift operations, especially when the shift amount is zero. Incorrect shift operations can lead to unexpected results, or in worst cases, hang the kernel.”

Using all extracted context, \toolfirst generates a set of test descriptions that detail what the test should check for. This along with a set of hand written guidelines that provides instructions on what makes a valid test, is then used to generate the test code. Here is an example of the test description along with the corresponding test code generated by \tool.

1

2

3

4-- asm

5mov %r0, 0x12345678

6rsh %r0, 0

7exit

8-- result

90x12345678

Listing 2: Generated test code

Interestingly, there was a historical bug in the linux implementation of BPF. The issue titled “arm, bpf: Fix bugs with ALU64 RSH, ARSH BPF_K shift by 0” describes how “The current arm BPF JIT does not correctly compile RSH or ARSH when the immediate shift amount is 0…” The test generated by \toolwould have caught this issue, preemptively.

7. Related Work

Testing eBPF. There exists a large body of work on improving eBPF verifiers and JIT compilers through fuzzing (Hung and Amiri Sani, 2024; Vyukov and Konovalov, 2015; iovisor, 2015a; Li et al., 2023a), state embeddings (Sun and Su, 2024), or rewriting the verifier with proof-carrying code (Nelson et al., 2020; Vishwanathan et al., 2023; Jin et al., 2024), including using abstract interpretation to prove various functional and safety properties (Gershuni et al., 2019). However, as existing eBPF ecosystems continue to grow in complexity and novel runtimes are added (Nelson et al., 2020; bpfwindows), concerns regarding correctness remain. Despite extensive testing and verification efforts, kernel bugs introduced by the verifier and JIT, as well as exploits leveraging unsafe extensions that pass the verifier but violate other safety properties, are constantly reported (Jia et al., 2023).

Kernel fuzzing techniques like LKL-fuzzer (Mohamed et al., 2023), BRF (Hung and Amiri Sani, 2024), or BVF (Sun et al., 2024b), generate eBPF programs that passthe verifier to find correctness bugs, using structured program generation to enforce the eBPF ISA grammar. \toolinstead relies on LLMs to infer the grammar and generate valid bytecode from the specification document and example tests, overcoming common limitations of generation-based fuzzing techniques, namely that they do not evolve with the program semantics, and they have restricted generation ability. Closer to our work is Kgent (Zheng et al., 2024), which uses LLM agents to generate valid eBPF programs grounded in formal specifications generated from natural language documentation. While we also seek to leverage informal natural language specifications, we focus on generating executable tests with the purpose of identifying differential behavior.

Testing Wasm. There has been work to further the correctness guaranteed by the Wasm spec through mechanization via a custom DSL (Youn et al., 2024). Naturally, bugs still exist due to gaps in testing, diversity in use cases, variation in implementation, etc., and have been studied (Waseem et al., 2024; Romano et al., 2022). Tools to find such bugs use static and dynamic analysis (Lehmann and Pradel, 2019; Lehmann et al., 2023; Titzer et al., 2024; Rodrigues and Barreiros, 2022; Breitfelder et al., 2023; He et al., 2023), compiler fuzzing (was, 2024b; Hai et al., 2022; Zhang et al., 2024) and binary fuzzing (Haßler and Maier, 2022; Lehmann et al., 2021; Zhao et al., 2024). Some fuzzers have been developed to target the behavior in a specific domain such as smart contracts (Chen et al., 2022).

Efforts to use differential testing for Wasm have taken several forms (such as using a stack-directed binary generator (Perényi and Midtgaard, 2020)), none of which (as far as we are aware) use LLMs or leverage natural language. DITWO (Liu et al., 2023) leveraged differential testing to uncover missed Wasm optimization opportunities. WADIFF (Zhou et al., 2023), the first differential testing framework for Wasm, generated test cases for each operator and then fuzzed them. Wasmaker (Cao et al., 2024) performs similarly, but can generate more complex binaries.

Testing with LLMs Neural test generation techniques have been developed to address limitations and challenges of traditional testing techniques, for example, improving coverage of the input space and readability of the generated tests. Several works rely on LLMs to improve unit test generation techniques, by leveraging build  (Alshahwan et al., 2024) and code coverage information (Pizzorno and Berger, 2024; Lemieux et al., 2023), using multi-step prompting with AST-based context retrieval (Ryan et al., 2024), and training models on aligned code and tests to improve generated test validity (Rao et al., 2023).

Fuzzing techniques, like TitanFuzz (Deng et al., 2023) which uses LLMs to generate and mutate human-like code to test deep learning library APIs, have also been used to improve the coverage and quality of fuzzing inputs. Fuzz4All (Xia et al., 2024) aims to address the limitations of traditional compiler fuzzers by leveraging LLMs as an input generation and mutation engine. Fuzz4All relies on a set of user provided documentation, example code, or formal specifications for each component under test. It then uses autoprompting techniques to summarize these artifacts and iteratively mutate generated inputs. Our approach leverages similar inputs, however \tooldoes not require users to manually extract relevant sections of documentation and other artifacts for the component under test. Instead, \toolautomatically extracts relevant specifications for each instruction from the given document. This is to ensure higher level specifications, which can be at scattered across a document, are not missed, improving the validity of the generated inputs. While TitanFuzz and Fuzz4All generate input programs for a single system, \toolgenerates test inputs that differentiate two given programs, does not require a user defined oracle, and uses prompt chaining to incorporate evolving differential information, such as difference in code implementations and historic bugs, to guide test generation. The target-section baseline we use closely resembles the Fuzz4All approach. Closest to our work is Mokav (Etemadi et al., 2024), an LLM-guided differential testing technique. Mokav uses execution based feedback to prompt models to generate difference exposing tests between two versions of a python program. Similar to our work, Mokav generates natural language descriptions of each versions of the program, however, unlike our approach it does so independently, without prompting the model to explicitly look for differences. While Mokav targets differential testing, it does not consider other sources of natural language artifacts to guide test generation. Other approaches, such as AID (Liu et al., 2024) and a Differential Prompting framework introduced by Li et al. (Li et al., 2023b), leverage buggy versions of code to generate fault-localizing tests that expose differences between a buggy and fixed version. In contrast, \tooldirectly generates differentiating tests without access to a known buggy version of the code.