Source-linked AI summary
PALM: Path-aware LLM-based Test Generation with Comprehension
Yaoxuan Wu, Xiaojie Zhou, Ahmad Humayun, Muhammad Ali Gulzar, Miryung Kim
TL;DR
Symbolic execution can be constrained by the difficulty of modeling library functions, while LLMs may miss subtle paths without systematic enumeration. PALM combines AST-level path enumeration with LLM-guided test generation and an interactive frontend; it reports higher path coverage than LLM baselines and user-study benefits for path comprehension.
Problem
Symbolic execution depends on modeling target and library code as constraints, while LLMs lack systematic path enumeration and can miss subtle cases.
Source: §1 · p. 1Method
Results
35.0% and 24.2% higher path coverage than GPT-4o-mini and GPT-o3-mini, respectively, using the same backend; 12 participants reported improved path-coverage understanding with PALM’s frontend.
Source: §1 · p. 2Takeaways & Limitations
PALM’s frontend helps users understand path coverage and identify which generated tests exercise specific paths.
Source: §1 · p. 2, §7 · p. 10The evaluation uses relatively small Java programs primarily involving standard-library APIs, so results may not generalize to larger projects or other languages.
Source: §5 · p. 10
Abstract
from arXiv · showhide
Symbolic execution is a widely used technique for test generation, offering systematic exploration of program paths through constraint solving. However, it is fundamentally constrained by the capability to model the target code, including library functions, in terms of symbolic constraints and by the capability of underlying constraint solvers. As a result, many paths involving complex features remain unanalyzed or insufficiently modeled. Recent advances in large language models (LLMs) have shown promise in generating diverse and valid test inputs. Yet, LLMs lack mechanisms for systematically enumerating program paths and often fail to cover subtle corner cases. We observe that directly prompting an LLM with the full program leads to missed coverage of interesting paths. In this paper, we present PALM, a test generation system that combines symbolic path enumeration with LLM-assisted test generation. PALM statically enumerates possible paths through AST-level analysis and transforms each into an executable variant with embedded assertions that specify the target path. This avoids the need to translate path constraints into SMT formulas, by instead constructing program variants that the LLM can interpret. Importantly, PALM provides an interactive frontend that visualizes path coverage alongside generated tests, assembling tests based on the specific paths they exercise. A user study with 12 participants demonstrates that PALM's frontend helps users better understand path coverage and identify which paths are actually exercised by PALM-generated tests through verification and visualization of their path profiles.
1 Introduction
Symbolic execution struggles when library functions cannot be modeled by constraint solvers, while LLMs can miss subtle paths without systematic guidance. PALM combines symbolic path enumeration with LLM test generation and an interface for inspecting test–path alignment.
1 Introduction
- Constraint solvers such as Z3 and CVC5 lack built-in support for string operations such as equalsIgnoreCase, unless developers manually supply symbolic models for those library functions.This limits symbolic execution when branch conditions depend on such operations.Source: §1 · p. 1
- LLMs can generate typical tests but may miss subtle paths, such as {"-f","-v"}, when directly prompted with the full program without path guidance.The example path is also difficult for symbolic execution because of unsupported string operations.Source: §1 · p. 1, Figure 1 · p. 2
- PALM enumerates paths through AST-level analysis and creates path-specific program variants with assertions that guide LLM test generation without constraint solving.Each generated test is executed on its corresponding variant to verify that it exercises the target path.Source: §1 · p. 2
- On 124 HumanEval-Java programs, PALM achieved 35.0% and 24.2% higher path coverage than GPT-4o-mini and GPT-o3-mini; refinement added 14.2% over non-iterative GPT-4o-mini.With the same LLM backend, Symbolic PathFinder failed to derive an accurate path constraint in 34.3% of programs because of insufficient modeling of external API calls.Source: §1 · p. 2
- PALM’s interactive frontend visualizes path coverage and lets users inspect whether generated tests exercise intended paths.In a 12-participant study, users reported better understanding of path coverage and ability to identify tests exercising specific paths.Source: §1 · p. 2
2 Tool Overview
PALM pairs a symbolic execution tree with executable path-specific variants and LLM-generated tests. Users can inspect coverage, review path logic, and validate or refine tests that diverge from their selected paths.
2 Tool Overview
- PALM combines symbolic execution with LLMs for Java programs, organizing enumerated paths and their coverage in a symbolic execution tree.The tree represents statements and branch conditions, with paths from root to leaf corresponding to possible executions.Source: §2 · p. 2
2.1 Test generation
- Users provide a program and symbolic execution settings; PALM enumerates paths, constructs variants, and requests path-specific tests.The interface also provides an example selector, generation controls, and editors for prompts and tests.Source: §2.1 · p. 2, Figure 2 · p. 3
2.2 Path understanding with symbolic tree and path variant
- The tree distinguishes branch conditions from statements and marks paths covered, uncovered, or unreachable; selected paths appear as executable variants with assertions encoding branch outcomes.The variants guide LLM test generation and let users interpret path logic, while avoiding SMT translation and manual library-function modeling.Source: §2.2 · p. 3
2.3 Validating and refining generated tests
- PALM checks whether generated inputs follow the selected path and highlights the first assertion where a test diverges.Users can inspect the divergence, edit prompts or tests, and use feedback containing the prior failing test and first diverging assertion to guide another attempt.Source: §2.3 · p. 3, Figure 3 · p. 4
3 Methodology
PALM enumerates paths through AST-level analysis and turns them into executable variants, then uses an LLM to generate and validate path-specific tests. Path extraction preserves path semantics through control-flow expansion, while a symbolic execution tree organizes generation and coverage.
3 Methodology
- PALM enumerates paths from the AST and represents each as an executable program variant, avoiding translation of path semantics into SMT constraints.The variants encode branch outcomes with assertions; a user-defined loop-unrolling bound controls loop expansion.Source: §3 · p. 4, §3.1 · p. 4
3.1 Path Extraction
- Path extraction inlines symbolic callees, renames variables after control-flow expansion, and propagates or folds constants to preserve meaning and simplify variants.Inlining embeds callee behaviors in the caller’s path; simplification can also prune trivially infeasible paths.Source: §3.1 · pp. 4–5
3.2 Path Aware Test Generation with Validation
- PALM organizes path variants in a symbolic tree, prompts an LLM for tests, and runs each test against its variant to verify path exercise.For up to five trials per path, failed assertions can be returned to the LLM as feedback for refinement.Source: §3 · p. 4, §3.2 · p. 6
4 Evaluation
PALM was evaluated on 124 HumanEval-Java programs, comparing path-aware generation with direct LLM generation, Symbolic PathFinder, and a baseline chatbox in a 12-person user study. Results show coverage gains in several settings and stronger participant performance on path-comprehension tasks, while gains from refinement varied by LLM backend.
4.1 Path-aware test generation
- 35.0% higher path coverage with GPT-4o-mini and 24.2% higher path coverage with GPT-o3-mini were achieved by PALM over direct generation using the same backend.With GPT-o3-mini, PALM had 1.7% lower branch coverage and 0.4% lower line coverage than direct generation.Source: §4.1 · p. 7, Table 2 · p. 7
- With GPT-o4-mini, direct generation achieved 8.8% higher path coverage, 1.1% higher branch coverage, and 0.4% higher line coverage than PALM.The authors partly attribute this to PALM’s cap of 50 enumerated paths per program; they describe path-level guidance and visualization as complementary benefits.Source: §4.1 · p. 7
4.2 Test validation and refinement
- Four additional rounds with GPT-4o-mini improved path coverage by 14.2%, branch coverage by 4.2%, and line coverage by 1.4%, with gains plateauing after round five.GPT-o3-mini showed smaller gains across rounds: 0.5% in path coverage, 0.5% in branch coverage, and 0.1% in line coverage.Source: §4.2 · p. 7, Figure 6 · p. 7
4.3 Comparison with Symbolic PathFinder
- Symbolic PathFinder failed to model a complete path in 49 programs (34.3%), while PALM used LLMs to infer constraints without lowering paths to SMT.The example involves unsupported API calls and a symbolic heap object; falling back to concrete execution on split() loses the dependency between txt and parts.Source: §4.3 · pp. 7–8, Table 3 · p. 8
4.4 User study
- PALM users scored 0.92 on Q1 and 1.0 on Q2 and Q3; LLM chatbox users struggled to enumerate paths and match tests to paths.One PALM user miscounted the total paths despite correctly navigating the symbolic tree; chatbox users missed loop cases and one overlooked a data dependency.Source: §4.4 · p. 9, Table 7 · p. 9
- Average task-completion times were similar for PALM and the LLM chatbox: 5.43 versus 5.17 minutes.PALM users reported higher confidence across all three aspects: path enumeration (4.92 vs. 3.00), avoiding redundant tests (4.33 vs. 2.75), and test-path alignment (4.58 vs. 3.17).Source: §4.4 · p. 9, Figure 8 · p. 9
- Participants said PALM helped them identify covered and missing paths, align tests with execution paths, and reduce redundant testing effort.The study used a counterbalanced within-subject design with 12 participants familiar with Java and prior LLM use.Source: §4.4 · pp. 8–9
5 Threats to Validity
PALM’s evaluation has validity boundaries related to comparison cost, benchmark scope, measurement choices, and study size. These constrain how broadly its coverage and user-study findings can be interpreted.
5 Threats to Validity
- PALM’s comparison with direct LLM prompting is not budget-equivalent, so coverage gains may partly reflect more generation and validation opportunities.The evaluation does not include an ablation that equalizes LLM budgets.Source: §5 · p. 9
- SPF does not synthesize executable unit tests from satisfying assignments, especially for arrays or heap-allocated objects, so its HumanEval-Java path coverage is not reported.Instead, the study reports whether programs yield at least one SMT-formatted path constraint as a coarse applicability indicator.Source: §5 · pp. 9–10
- HumanEval-Java contains relatively small Java programs that primarily use standard-library APIs, limiting representation of larger projects and richer dependencies or behaviors.The implementation targets Java, and HumanEval benchmarks may be subject to training-data contamination that could inflate absolute LLM-based performance.Source: §5 · p. 10
- Branch-based path coverage misses data-flow behavior without distinct branch outcomes and may under-represent symbolic execution’s boundary-value generation within a branch.The user-study tasks may differ from end-to-end tool use, and test readability, naturalness, and bug-finding capability are not comprehensively measured.Source: §5 · p. 10
- The user study’s 12 participants limit statistical power, while stochastic generation leaves residual variance despite repeated runs and aggregate summaries.These factors limit the strength of quantitative claims.Source: §5 · p. 10
6 Related Work
Related work addresses symbolic execution’s modeling challenges, LLM-based test generation, and systems combining LLMs with symbolic reasoning. PALM is positioned around explicit path enumeration, executable path-specific variants, and visual inspection of path-level behavior.
6 Related Work
- Prior symbolic execution systems use concolic execution or API abstractions to address external functions, but these approaches can under-approximate path constraints or require specialized models.DART and CUTE execute external functions concretely; KLEE, AEG, and Cloud9 provide abstractions for selected APIs and environments.Source: §6 · p. 10
- Unlike mature symbolic executors that explore exception-, implicit-check-, or scheduling-induced paths, PALM enumerates explicit branch outcomes and avoids translating path constraints into SMT formulas.PALM therefore does not require SMT-level symbolic abstractions for external functions.Source: §6 · p. 10
- LLM test-generation work enriches prompts or uses analysis-driven feedback, while IntUT guides generation with test intentions rather than specific control-flow paths [30] [26] [18] [28] [31].Examples include focal-method context, API documentation, slicing, and feedback from ineffective attempts.Source: §6 · p. 10
- Hybrid systems use LLMs for SMT translation or constraint satisfaction, branch-condition prompting, or fuzzing, while AutoEXE has limited transparency into exercised paths [27] [25] [20] [19].PALM instead enumerates paths and constructs executable assertion-instrumented variants for validated, iterative generation and visual inspection of missing or redundant tests.Source: §6 · p. 10
7 Conclusion
PALM combines symbolic path enumeration with LLM-guided test generation using executable, assertion-embedded variants. Its interface provides visibility into path coverage and test behavior, and study participants reported greater confidence in reasoning about generated tests.
7 Conclusion
- PALM combines symbolic path enumeration with LLM-guided generation, using executable path-specific variants with embedded assertions to guide inputs and bypass symbolic modeling of invoked APIs.This design also enables precise alignment between tests and paths.Source: §7 · p. 10
- PALM’s interactive frontend provides visibility into path coverage and test behavior, helping users detect missing or redundant tests..Source: §7 · p. 10
- User-study participants reported higher confidence in assessing test comprehensiveness, distinguishing missing or redundant tests, and understanding which inputs exercise a specific path..Source: §7 · p. 10