FAiLGen: Calibrating LLM for Failing Test Generation with Monte Carlo Tree Search

Abstract

Failing test generation is an important yet challenging task in software engineering. It involves searching a vast space to identify fault-triggering test inputs and the oracles that assert these faulty executions. Several approaches have been proposed for generating failing tests. Specifically, given a program-under-test (PUT) and its requirements, these approaches leverage large language models (LLMs) to generate alternative implementations of the PUT that comply with the requirements, followed by differential testing between the PUT and the alternative implementations. Failing tests can be constructed by adopting the inconsistency-revealing inputs as the test inputs and treating the outputs returned by the alternative implementations as expected outputs. As alternative implementations may also contain faults and thus return incorrect outputs, current methods rely on either output consistency across alternative implementations or pre-constructed test cases for validation. However, the former is susceptible to LLM training biases or stochasticity, while the latter can be impractical due to the scarcity or unavailability of pre-constructed test cases in real-world scenarios. To address existing works’ limitations, we employ LLM as an alternative oracle for output validation, and calibrate its reasoning steps to reduce its susceptibility to LLM training biases or stochasticity. One critical challenge is that the calibration process inherently requires correct input-output pairs for the output validation task as ground-truth for reference when validating/calibrating LLMs’ reasoning, yet correct input-outputs (i.e., passing tests) are often scarce or unavailable in real-world scenarios. To address this challenge, our insight is that outputs consistently returned by both the PUT and all alternative implementations have a high probability of being the correct outputs of the PUT, as the PUT and alternative implementations are generated by independent agents (i.e., human developers and LLMs). Based on this insight, we propose FAiLGen, a novel approach that calibrates LLM’s reasoning for failing tests generation via a representative reasoning calibration paradigm, Monte Carlo Tree Search. We evaluate FAiLGen on 100 subjects from CodeForces and 100 subjects from SWE-Bench-Live. Our evaluation results show that FAiLGen achieves a recall of 58.1%, which is 62.4% higher than that of the best baseline (35.8%). Meanwhile, FAiLGen attains a precision of 75.2%, favorably compared to the best baseline (61.1%).