PaperlayerView exact revision on arXiv

Source-linked AI summary

Advancing Code Coverage: Incorporating Program Analysis with Large Language Models

Chen Yang, Junjie Chen, Bin Lin, Ziqi Wang, Jianyi Zhou

arXiv:2404.04966v2cs.SE

TL;DR

Automated test generators still struggle with branches requiring complex objects or inter-procedural reasoning. TELPA combines program analysis with counter-example-guided LLM prompting; evaluations report higher branch coverage than state-of-the-art SBST and LLM-based techniques.

  • Problem

    Existing test-generation techniques struggle with branches requiring complex object construction or understanding inter-procedural dependencies.

    Source: §1 · pp. 1–2

  • Method

    TELPA combines analyses of real object-construction scenarios and branch dependencies with counter-example sampling and coverage-based feedback to guide LLM test generation.

    Source: §1 · p. 3, §3 · p. 6

  • Results

    TELPA significantly outperforms state-of-the-art SBST and LLM-based techniques across 27 open-source Python projects, four open-source Java projects, and three internal Java projects.

    Source: §8 · p. 28

  • Takeaways & Limitations

    TELPA improves test-generation performance by using program analysis to help LLMs construct complex objects and understand code semantics, with counter-examples and coverage feedback guiding generation.

    Source: §8 · p. 28

    The study did not investigate bug-detection effectiveness because TELPA focuses on branch coverage rather than generating assertions.

    Source: §4.7 · p. 23

Abstract

from arXiv · show

Automatic test generation plays a critical role in software quality assurance. While the recent advances in Search-Based Software Testing (SBST) and Large Language Models (LLMs) have shown promise in generating useful tests, these techniques still struggle to cover certain branches. Reaching these hard-to-cover branches usually requires constructing complex objects and resolving intricate inter-procedural dependencies in branch conditions, which poses significant challenges for existing test generation techniques. In this work, we propose TELPA, a novel technique aimed at addressing these challenges. Its key insight lies in extracting real usage scenarios of the target method under test to learn how to construct complex objects and extracting methods entailing inter-procedural dependencies with hard-to-cover branches to learn the semantics of branch constraints. To enhance efficiency and effectiveness, TELPA identifies a set of ineffective tests as counter-examples for LLMs and employs a feedback-based process to iteratively refine these counter-examples. Then, TELPA integrates program analysis results and counter-examples into the prompt, guiding LLMs to gain deeper understandings of the semantics of the target method and generate diverse tests that can reach the hard-to-cover branches. Our experimental results on 27 open-source Python projects demonstrate that TELPA significantly outperforms the state-of-the-art SBST and LLM-based techniques, achieving an average improvement of 31.39% and 22.22% in terms of branch coverage.

1 INTRODUCTION

TELPA targets hard-to-cover branches that require complex object construction or understanding inter-procedural dependencies. It combines program analysis and feedback-guided LLM prompting, and outperforms the compared tools in branch coverage.

1 INTRODUCTION

  • Hard-to-cover branches may require constructing objects with specific attributes or resolving dependencies across a sequence of method calls.Existing LLM techniques may leave such branches for costly manual test design.Source: §1 · pp. 2–3
  • Object construction analysis traces real invocation paths into the target method, while branch dependency analysis supplies the code of methods invoked by branch conditions in call order.These analyses help LLMs learn how objects are constructed and how dependent methods affect branch outcomes.Source: §1 · p. 3
  • TELPA samples diverse ineffective tests as counter-examples and updates them using recent coverage results in a feedback-based generation process.TELPA is intended to activate after a lightweight tool such as Pynguin fails to increase coverage within a specified timeframe.Source: §1 · p. 3
  • TELPA achieves 34.10%, 25.93%, and 21.10% higher branch coverage than Pynguin, CODAMOSA, and CHATTESTER, respectively, under the same testing time budget.The evaluation covered 27 open-source Python projects.Source: §1 · p. 3
  • The ablation study attributes contributions to object construction analysis, branch dependency analysis, counter-example sampling, and coverage-based feedback.The contribution summary links these components to object construction, inter-procedural dependencies, and test-generation efficiency and effectiveness.Source: §1 · pp. 3–4

2 MOTIVATING EXAMPLE

The examples illustrate two barriers to automated branch coverage: constructing a complex object with required attributes and understanding inter-procedural dependencies. TELPA uses program analysis to provide LLMs with usage scenarios and relevant branch context.

2 MOTIVATING EXAMPLE

  • All three evaluated tools fail to reach the example branch unless an Array is constructed with an items value that is a tuple or list of Field objects.The example uses a 20-minute testing budget.Source: §2 · p. 4
  • In the second example, the branch condition depends on is_magic, which is defined elsewhere and may invoke further methods.Pynguin, CODAMOSA, and CHATTESTER do not make the condition true.Source: §2 · p. 5
  • The benchmark contains 6,559 branches, of which 3,979 (60.7%) are classified as hard-to-cover; the cited Defects4J benchmark contains 9,391 branches, of which 5,494 (58.5%) are classified likewise.The Python benchmark consists of 486 modules from 27 projects.Source: §2 · p. 5
  • The authors attribute existing tools’ difficulties to oversimplified object construction, limited recursive analysis of dependencies, and imprecise LLM context.TELPA applies object construction and branch dependency analysis to supply relevant information to LLMs.Source: §2 · p. 5

3 APPROACH

TELPA targets hard-to-cover branches by combining program-analysis-derived context with sampled counter-examples in an iterative LLM test-generation process. It uses existing test-generation tools first, then applies analyses selectively to help generate tests for uncovered branches.

3 APPROACH

  • TELPA uses existing test-generation tools first, then analyzes methods with uncovered branches and prompts an LLM using analysis results and counter-examples to generate new tests.Generated tests and their coverage are added to the existing pool for later iterations.Source: §3 · p. 6, §3.1 · p. 6, §3.4 · pp. 10–11

3.2 Method-Invocation Analyses

  • It processes methods in ascending order of coverage and supplies methods retrieved by invocation analysis rather than the whole module as LLM context.This ordering prioritizes methods with lower coverage, while restricting context is intended to reduce irrelevant code and computational burden.Source: §3.2 · p. 7

3.2.1 Object Construction Analysis.

  • Object construction analysis extracts invocation sequences ending at the target method to capture real usage scenarios and how its argument objects are constructed.TELPA builds a call graph and extracts paths terminating at the target method; it retains only the shortest path from each entry point.Source: §3.2.1 · pp. 7–8

3.2.2 Branch Dependency Analysis.

  • Branch dependency analysis recursively retrieves methods that may affect branch outcomes by tracing condition variables through relevant assignments.TELPA applies this analysis to methods with intricate inter-procedural dependencies, object construction analysis to methods with complex objects, and both when both challenges occur.Source: §3.2.2 · pp. 8–9

3.3 Counter-Examples Sampling

  • For each invocation sequence, TELPA selects a small set of existing tests that collectively cover the target method’s already-covered branches, using highest coverage and then incremental coverage.The selected tests serve as counter-examples for that sequence’s later generation prompt.Source: §3.3 · p. 9

3.4 Feedback-based Test Generation Process with LLMs

  • TELPA constructs method context from a selected invocation sequence and associated dependency methods, then prompts the LLM with that context and the sequence’s counter-examples to generate divergent tests.It begins with the target method itself as the sequence when available, then tries unused sequences if needed; new tests are executed and added to the pool.Source: §3.4 · pp. 10–11

4 EVALUATION

The evaluation poses five questions covering coverage, component contributions, preceding tools and LLM choices, test correctness, and generalizability. It evaluates TELPA on Python projects and adapts it to Java for the generalizability question.

4.1.1 Implementation of TELPA.

  • TELPA’s Python implementation uses PyCG call graphs and coverage.py, while its Java adaptation uses JavaParser, JUnit, and JaCoCo.The Python evaluation uses Phind-CodeLlama-34B-v2 by default; the Java version uses EvoSuite for preceding test generation.Source: §4.1.1 · pp. 11–12

4.1.2 Baselines for RQ1 and RQ4.

  • The comparisons use Pynguin and CODAMOSA as preceding tools, and compare TELPA’s prompting with CHATTESTER’s prompting under a shared LLM and corresponding workflows.The study replaces CHATTESTER’s original ChatGPT model with Phind-CodeLlama-34B-v2 for comparison.Source: §4.1.1 · p. 11, §4.1.2 · pp. 12–13

4.1.3 Variants for RQ2.

  • Seven TELPA ablations remove object construction analysis, branch dependency analysis, counter-example guidance, feedback, path filtering, or functionality summarization, or replace coverage-based counter-example selection with random selection.The variants are evaluated with both Pynguin-based and CODAMOSA-based preceding tools.Source: §4.1.3 · p. 13

4.1.4 Variants for RQ3.

  • The RQ3 variants test TELPA without a preceding tool, with the smaller DeepSeek-Coder-6.7B-instruct model, and with GPT-4.The GPT-4 variant is Pynguin-based because of API cost.Source: §4.1.4 · pp. 13–14

4.1.5 Baseline for RQ5.

  • For Java generalizability, TELPA is adapted as an EvoSuite-based variant and compared with EvoSuite.Source: §4.1.5 · p. 14

4.1.6 Benchmark, Metrics, and Environment.

  • The Python benchmark contains 486 modules from 27 projects, while the Java benchmark covers four Defects4J projects; both evaluations measure branch and line coverage.Each Python module and technique receives 20 minutes, including TELPA’s component costs, and experiments are repeated 20 times with average final results reported.Source: §4.1.6 · pp. 14–15

4.2 RQ1: Effectiveness of TELPA

TELPA improves coverage over Pynguin and CODAMOSA and reaches hard-to-cover branches that other methods miss. Its coverage continues to rise after the preceding tools begin to plateau.

4.2 RQ1: Effectiveness of TELPA

  • Pynguin and CODAMOSA plateau early while TELPA continues gaining coverage and surpasses both within the 10-minute budget.The trend is shown in Figure 8; TELPA coverage continues to increase over the 20-minute period, more slowly after the first 10 minutes.Source: §4.2 · pp. 16–17, Figure 8 · p. 16
  • 34.10% and 25.93% are TELPA’s average branch-coverage improvements over Pynguin and CODAMOSA, respectively, across projects.TELPA also improves average line coverage by 16.72% over Pynguin and 9.32% over CODAMOSA.Source: §4.2 · p. 17
  • 39.53% and 35.23% are TELPA’s hard-to-cover branch coverage with Pynguin and CODAMOSA as preceding tools, versus 31.62% and 20.58% for those baselines.The reported improvements are 25.02% over Pynguin and 71.18% over CODAMOSA.Source: Table 2 · p. 16, §4.2 · p. 17
  • TELPA_p improves average branch coverage over CHATTESTER by 20.19%, while TELPA_c improves coverage on hard-to-cover branches by 21.06%; both significantly outperform CHATTESTER, with all p-values below 0.05.Source: §4.2 · p. 18
  • TELPA covers nearly all hard-to-cover branches found by other techniques and a significant number of unique hard-to-cover branches.Figure 9 shows overlap in branches covered by the different techniques.Source: §4.2 · p. 18

4.3 RQ2: Contribution of Each Component in TELPA

TELPA’s components each contribute to its effectiveness, and the full system significantly outperforms its variants. Filtering invocation sequences and selecting diverse counter-examples are among the supported design choices.

4.3 RQ2: Contribution of Each Component in TELPA

  • TELPA_p and TELPA_c outperform their corresponding variants in average branch and line coverage, with statistically significant differences across projects.All paired Wilcoxon p-values are below 0.05.Source: §4.3 · p. 18, Table 3 · p. 19
  • TELPAnpf performs worst because unfiltered invocation sequences can be too long and complex for LLMs to comprehend effectively.The results support sequence filtering and avoiding irrelevant or insufficient prompt context.Source: §4.3 · pp. 19–20
  • Coverage-based counter-example sampling outperforms random sampling, while random counter-examples still outperform using none.TELPA_p improves average branch coverage over TELPA_p rce by 9.01%, and TELPA_c improves over TELPA_c rce by 11.76%; summarizing functionality beforehand also improves effectiveness.Source: §4.3 · p. 20

4.4 RQ3: TELPA’s Effectiveness with Different Configurations

TELPA’s results depend on its configuration: using an existing generator before invoking the LLM balances effectiveness and efficiency, while performance remains strong with a smaller LLM. GPT-4 results were similar on a 100-method sample.

4.4 RQ3: TELPA’s Effectiveness with Different Configurations

  • Starting TELPA from scratch improves branch coverage over CODAMOSA and Pynguin by 3.70% and 10.56%, but the gains are limited under the same time budget.LLM test generation takes more time, and using it on easy-to-cover branches limits time available for hard-to-cover branches.Source: §4.4 · p. 20
  • Among 603 methods uncovered by CODAMOSA and Pynguin, TELPA improves coverage for 259; on these methods, TELPA_c averages 21.86% branch coverage and TELPA_p 17.14%.Their average line coverage is 39.99% and 43.80%, respectively.Source: §4.4 · p. 20

4.5 RQ4: Correctness of Unit Tests Generated by TELPA

TELPA-generated tests are syntactically valid but have lower execution pass rates than search-based tests. The authors relate this trade-off to the complexity of tests targeting hard-to-cover branches.

4.5 RQ4: Correctness of Unit Tests Generated by TELPA

  • All evaluated techniques achieve 100% syntax correctness, but TELPA and CHATTESTER have lower execution pass rates than Pynguin.CODAMOSA’s pass rates are comparable to Pynguin because Pynguin generates most of its tests.Source: §4.5 · p. 21
  • TELPA’s lower execution pass rates than CHATTESTER accompany coverage of 21.00% and 21.06% more hard-to-cover branches for TELPA_p and TELPA_c, respectively.The paper attributes the more challenging execution to complex object construction and inter-procedural dependencies in the targeted branches.Source: §4.5 · p. 22
  • AssertionError (32.0%) and AttributeError (33.5%) are the predominant TELPA test errors.The paper associates these errors with harder-to-predict assertions and objects that are not properly constructed or initialized.Source: §4.5 · p. 22

4.6 RQ5: Generalizability of TELPA

TELPA improves coverage over EvoSuite on Java, especially for hard-to-cover branches, and also outperforms CHATTESTER on three industrial projects. The authors discuss parameter, benchmark, randomness, and evaluation-metric limitations.

4.6 RQ5: Generalizability of TELPA

  • 9.32% on all branches and 29.60% on hard-to-cover branches: TELPA improves average branch coverage over EvoSuite on Java projects.The authors note that EvoSuite’s advanced static analysis may diminish TELPA’s gains on all branches, while complex dependencies and object construction remain challenging for EvoSuite.Source: §4.6 · pp. 22–23, Table 8 · p. 23
  • TELPA consistently improves coverage over EvoSuite, including on hard-to-cover branches, supporting generalizability to statically typed Java.The authors describe the Java comparison as helping mitigate the threat posed by evaluating primarily on dynamically typed Python.Source: §4.6 · p. 23, §4.7 · p. 24

4.7 Threats to Validity

  • The evaluation uses a two-minute switch timeframe, LLM temperature 0, and a 20-minute testing budget per module; effects of other settings remain future work.The authors also report an average static-analysis overhead of 1.5 seconds per module, performed offline.Source: §4.7 · p. 23
  • The study did not evaluate bug-detection effectiveness because revealing bugs requires proper assertions, which TELPA does not generate.The authors plan to use more metrics to evaluate generated tests more sufficiently.Source: §4.7 · pp. 23–24
  • On three industrial Java projects, TELPA improves average branch coverage from 52.75% to 69.71% and line coverage from 59.43% to 72.71% over CHATTESTER.The authors present these results as evidence of generalizability independent of potential leakage from open-source training data.Source: §4.7 · p. 24, Table 9 · p. 24
  • Across 20 runs, TELPA’s standard deviation was 1.8%, and the Kruskal–Wallis H test found no significant differences across runs (p > 0.05).The authors say these results indicate stable performance and mitigate the randomness threat to some extent.Source: §4.7 · p. 24

5 CASE STUDY

The case studies show how TELPA uses program analysis to supply construction and dependency context for branches that baseline generators struggle to cover.

5 CASE STUDY

  • For the schema case, baseline tools either generate invalid inputs or omit required dataclass metadata, while TELPA generates a test with the metadata needed to cover the target branch.The target branch checks whether metadata.get(mm_field) is not None.Source: §5 · pp. 25–26
  • TELPA traces process_schema → build_schema → schema and extracts the dynamic construction logic that instantiates cls with the required metadata.That usage context is incorporated into the prompt through object construction analysis.Source: §5 · p. 25
  • The cases illustrate TELPA’s use of inter-procedural dependencies and complex object-construction logic to generate tests for hard-to-cover branches.The section introduces two cases targeting those challenges.Source: §5 · pp. 25–26

6 DISCUSSION

TELPA can still miss hard-to-cover branches because of LLM hallucinations, while its prompt-focused approach can be combined with other prompting methods. The discussion also identifies assertion-quality and file-scope limitations.

6 DISCUSSION

  • LLM hallucinations remain a reason TELPA cannot reach all hard-to-cover branches within the testing budget.Generated tests may use nonexistent parameters when invoking methods.Source: §6 · p. 26
  • TELPA’s prompt-content improvements are orthogonal to chain-of-thought and post-processing methods, so the authors suggest combining them may further improve coverage.The discussion names SCoT, CCoT, and self-repairing as examples of those methods.Source: §6 · pp. 26–27
  • TELPA focuses on branch coverage rather than assertion generation, and assertion quality varies; the authors plan to refine assertions and evaluate bug detection and mutation scores.Assertions reveal bugs only when tests cover buggy code.Source: §6 · p. 27
  • TELPA analyzes invocation sequences only in the file hosting the target method, which can miss usage scenarios when that method is primarily used elsewhere.The authors describe this scope as a trade-off between comprehensiveness and computational efficiency.Source: §6 · p. 27

7 RELATED WORK

Related work spans search-based, symbolic-execution, and deep-learning test generation. TELPA differs by using program analysis to enrich prompts for hard-to-cover branches and can incorporate other techniques.

7 RELATED WORK

  • Search-based techniques such as Pynguin use heuristic search to mutate tests for coverage, while symbolic-execution approaches target path conditions and rare execution conditions.The cited work also includes object-construction graphs and string literals from human-written tests as enhancements to search-based testing.Source: §7 · p. 27
  • Symbolic execution struggles with complex data types and objects, limiting its ability to address TELPA’s target challenges.The cited approaches combine symbolic execution with search, optimization, or reachability analysis.Source: §7 · pp. 27–28
  • TELPA uses program analysis to enrich prompts for hard-to-cover branches, and the authors say earlier techniques can serve as preceding generators or be incorporated into TELPA.The paper describes this integration as compatible with its prompting approach.Source: §7 · p. 28
  • Deep-learning test-generation work includes trained models and LLM prompting systems, with CODAMOSA and CHATTESTER among the techniques evaluated in this study.Examples include models trained on method-test data and methods that repair invalid generated tests.Source: §7 · p. 28
  • Unlike prior empirical evaluations of LLM test generation, TELPA proposes a program-analysis-assisted technique rather than only evaluating prompting information or generated suites.The cited studies include a survey and evaluations of API information, ChatGPT versus EvoSuite, and open-source LLMs.Source: §7 · p. 28

8 CONCLUSION

TELPA combines program analysis with LLM test generation to address branches involving complex objects and inter-procedural dependencies. Experiments span open-source and internal Java projects and open-source Python projects.

8 CONCLUSION

  • TELPA significantly outperforms state-of-the-art SBST and LLM-based techniques across 27 open-source Python projects, four open-source Java projects, and three internal Java projects.Source: §8 · p. 28
  • TELPA uses program analysis to help LLMs construct complex objects and understand code semantics, alongside counter-example sampling and coverage-based feedback.Source: §8 · p. 28
  • The authors released TELPA’s implementation and experimental data for replication and practical use.Source: §8 · p. 28
Loading 2404.04966v2…