Directed Grammar-Based Test Generation

• URL: http://arxiv.org/abs/2508.01472v1
• Date: Sat, 02 Aug 2025 19:43:15 GMT
• Title: Directed Grammar-Based Test Generation
• Abstract summary: This work proposes an automated test generation approach (called FdLoop)<n>FdLoop iteratively learns relevant input properties from existing inputs to drive the generation of goal-specific inputs.<n>We evaluate FdLoop using three (3) well-known input formats (JSON, CSS and JavaScript) and 20 open-source software.
• Score: 2.0948216657769616
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To effectively test complex software, it is important to generate goal-specific inputs, i.e., inputs that achieve a specific testing goal. However, most state-of-the-art test generators are not designed to target specific goals. Notably, grammar-based test generators, which (randomly) produce syntactically valid inputs via an input specification (i.e., grammar) have a low probability of achieving an arbitrary testing goal. This work addresses this challenge by proposing an automated test generation approach (called FdLoop) which iteratively learns relevant input properties from existing inputs to drive the generation of goal-specific inputs. Given a testing goal, FdLoop iteratively selects, evolves and learn the input distribution of goal-specific test inputs via test feedback and a probabilistic grammar. We concretize FdLoop for four testing goals, namely unique code coverage, input-to-code complexity, program failures (exceptions) and long execution time. We evaluate FdLoop using three (3) well-known input formats (JSON, CSS and JavaScript) and 20 open-source software. In most (86%) settings, FdLoop outperforms all five tested baselines namely the baseline grammar-based test generators (random, probabilistic and inverse-probabilistic methods), EvoGFuzz and DynaMosa. FdLoop is (up to) twice (2X) as effective as the best baseline (EvoGFuzz) in inducing erroneous behaviors. In addition, we show that the main components of FdLoop (i.e., input mutator, grammar mutator and test feedbacks) contribute positively to its effectiveness. Finally, our evaluation demonstrates that FdLoop effectively achieves single testing goals (revealing erroneous behaviors, generating complex inputs, or inducing long execution time) and scales to multiple testing goals across varying parameter settings.

Related papers

• DuET: Dual Execution for Test Output Prediction with Generated Code and Pseudocode [56.14374797825548]
  We introduce LLM-based pseudocode execution, which grounds prediction on more error-resilient pseudocode.<n>We propose DuET, a dual-execution framework that combines both approaches by functional majority voting.<n>On LiveCodeBench, DuET achieves the state-of-the-art performance, improving Pass@1 by 13.6 pp.
  arXiv  Detail & Related papers  (2026-04-13T14:18:58Z)
• Scaling Agentic Verifier for Competitive Coding [66.11758166379092]
  Large language models (LLMs) have demonstrated strong coding capabilities but still struggle to solve competitive programming problems correctly in a single attempt.<n>Execution-based re-ranking offers a promising test-time scaling strategy, yet existing methods are constrained by either difficult test case generation or inefficient random input sampling.<n>We propose Agentic Verifier, an execution-based agent that actively reasons about program behaviors and searches for highly discriminative test inputs.
  arXiv  Detail & Related papers  (2026-02-04T06:30:40Z)
• HarnessLLM: Automatic Testing Harness Generation via Reinforcement Learning [30.26598881538489]
  Existing LLM-based automatic test generation methods mainly produce input and expected output pairs.<n>We propose HarnessLLM, a two-stage training pipeline that enables LLMs to write harness code for testing.
  arXiv  Detail & Related papers  (2025-11-02T22:41:15Z)
• DiffTester: Accelerating Unit Test Generation for Diffusion LLMs via Repetitive Pattern [6.901203999358967]
  We present DiffTester, an acceleration framework specifically tailored for dLLMs in Unit Test Generation (UTG)<n>DiffTester adaptively increases the number of tokens produced at each step without compromising the quality of the output.<n>We extend the original TestEval benchmark, which was limited to Python, by introducing additional programming languages including Java and C++.
  arXiv  Detail & Related papers  (2025-09-29T16:04:18Z)
• Combining TSL and LLM to Automate REST API Testing: A Comparative Study [3.8615905456206256]
  RestTSLLM is an approach that uses Test Specification Language (TSL) in conjunction with Large Language Models (LLMs) to automate the generation of test cases for REST APIs.<n>The proposed solution integrates prompt engineering techniques with an automated pipeline to evaluate various LLMs on their ability to generate tests from OpenAPI specifications.<n>The results indicate that the best-performing LLMs consistently produced robust and contextually coherent REST API tests.
  arXiv  Detail & Related papers  (2025-09-05T23:32:35Z)
• LLM-based Unit Test Generation for Dynamically-Typed Programs [16.38145000434927]
  TypeTest is a novel framework that enhances type correctness in test generation through a vector-based Retrieval-Augmented Generation system.<n>In an evaluation on 125 real-world Python modules, TypeTest achieved an average statement coverage of 86.6% and branch coverage of 76.8%, outperforming state-of-theart tools by 5.4% and 9.3%, respectively.
  arXiv  Detail & Related papers  (2025-03-18T08:07:17Z)
• Learning to Generate Unit Tests for Automated Debugging [52.63217175637201]
  Unit tests (UTs) play an instrumental role in assessing code correctness as well as providing feedback to large language models (LLMs)<n>We propose UTGen, which teaches LLMs to generate unit test inputs that reveal errors along with their correct expected outputs.<n>We show that UTGen outperforms other LLM-based baselines by 7.59% based on a metric measuring the presence of both error-revealing UT inputs and correct UT outputs.
  arXiv  Detail & Related papers  (2025-02-03T18:51:43Z)
• Training on the Benchmark Is Not All You Need [52.01920740114261]
  We propose a simple and effective data leakage detection method based on the contents of multiple-choice options.<n>Our method is able to work under gray-box conditions without access to model training data or weights.<n>We evaluate the degree of data leakage of 35 mainstream open-source LLMs on four benchmark datasets.
  arXiv  Detail & Related papers  (2024-09-03T11:09:44Z)
• PROZE: Generating Parameterized Unit Tests Informed by Runtime Data [10.405775369526006]
  A parameterized unit test (PUT) receives a set of inputs as arguments and contains assertions that are expected to hold true for all these inputs. In this paper, we address the problem of finding oracles for PUTs that hold over multiple inputs. We design a system called PROZE, that generates PUTs by identifying developer-written assertions that are valid for more than one test input.
  arXiv  Detail & Related papers  (2024-06-30T17:07:12Z)
• LLM-Powered Test Case Generation for Detecting Bugs in Plausible Programs [37.48856389469826]
  TrickCatcher generates test cases for uncovering bugs in plausible programs.<n>TrickCatcher achieves recall, precision, and F1 scores that are 1.80x, 2.65x, and 1.66x those of the state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-04-16T06:20:06Z)
• Test-Driven Development for Code Generation [0.850206009406913]
  Large Language Models (LLMs) have demonstrated significant capabilities in generating code snippets directly from problem statements. This paper investigates if and how Test-Driven Development (TDD) can be incorporated into AI-assisted code-generation processes.
  arXiv  Detail & Related papers  (2024-02-21T04:10:12Z)
• Test Generation Strategies for Building Failure Models and Explaining Spurious Failures [4.995172162560306]
  Test inputs fail not only when the system under test is faulty but also when the inputs are invalid or unrealistic. We propose to build failure models for inferring interpretable rules on test inputs that cause spurious failures. We show that our proposed surrogate-assisted approach generates failure models with an average accuracy of 83%.
  arXiv  Detail & Related papers  (2023-12-09T18:36:15Z)
• Generative Input: Towards Next-Generation Input Methods Paradigm [49.98958865125018]
  We propose a novel Generative Input paradigm named GeneInput. It uses prompts to handle all input scenarios and other intelligent auxiliary input functions, optimizing the model with user feedback to deliver personalized results. The results demonstrate that we have achieved state-of-the-art performance for the first time in the Full-mode Key-sequence to Characters(FK2C) task.
  arXiv  Detail & Related papers  (2023-11-02T12:01:29Z)
• LeTI: Learning to Generate from Textual Interactions [60.425769582343506]
  We explore LMs' potential to learn from textual interactions (LETI) that not only check their correctness with binary labels but also pinpoint and explain errors in their outputs through textual feedback. Our focus is the code generation task, where the model produces code based on natural language instructions. LETI iteratively fine-tunes the model, using the objective LM, on a concatenation of natural language instructions, LM-generated programs, and textual feedback.
  arXiv  Detail & Related papers  (2023-05-17T15:53:31Z)
• Intergenerational Test Generation for Natural Language Processing Applications [16.63835131985415]
  We propose an automated test generation method for detecting erroneous behaviors of various NLP applications. We implement this method into NLPLego, which is designed to fully exploit the potential of seed sentences. NLPLego successfully detects 1,732, 5301, and 261,879 incorrect behaviors with around 95.7% precision in three tasks.
  arXiv  Detail & Related papers  (2023-02-21T07:57:59Z)
• READIN: A Chinese Multi-Task Benchmark with Realistic and Diverse Input Noises [87.70001456418504]
  We construct READIN: a Chinese multi-task benchmark with REalistic And Diverse Input Noises. READIN contains four diverse tasks and requests annotators to re-enter the original test data with two commonly used Chinese input methods: Pinyin input and speech input. We experiment with a series of strong pretrained language models as well as robust training methods, we find that these models often suffer significant performance drops on READIN.
  arXiv  Detail & Related papers  (2023-02-14T20:14:39Z)
• Interactive Code Generation via Test-Driven User-Intent Formalization [60.90035204567797]
  Large language models (LLMs) produce code from informal natural language (NL) intent. It is hard to define a notion of correctness since natural language can be ambiguous and lacks a formal semantics. We describe a language-agnostic abstract algorithm and a concrete implementation TiCoder.
  arXiv  Detail & Related papers  (2022-08-11T17:41:08Z)
• Synthetic Datasets for Neural Program Synthesis [66.20924952964117]
  We propose a new methodology for controlling and evaluating the bias of synthetic data distributions over both programs and specifications. We demonstrate, using the Karel DSL and a small Calculator DSL, that training deep networks on these distributions leads to improved cross-distribution generalization performance.
  arXiv  Detail & Related papers  (2019-12-27T21:28:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.