Oct 2026· Proceedings of the ACM on Programming Languages· Vol 10, pp. 1849 - 1877· 1 citation· 55 references
Software Testing and Debugging Techniques
TL;DR
A lightweight form of constraint solving and propagation that enables randomized testing of programs with complex preconditions is obtained, and a generator DSL whose monadic semantics are parametric over abstract domains is formalized.
Abstract
Property-based testing of C programs can be automated by synthesizing random input generators from separation-logic specifications. Existing work in this space, such as the Bennet testing tool, uses randomized backtracking search, generating random values and checking them against constraints, backtracking on failure. Although this approach performs well on simple recursive heap structures, it struggles as constraints grow more complex, particularly when they involve pointer arithmetic—as, for example, in the many forms of specialized storage allocators that arise in low-level systems software. Existing work uses targeted optimizations and heuristics to satisfy specific classes of constraints, but this requires continual expansion as new special cases arise, resulting in complex tools. We reframe generation as the iterative refinement of abstract domain elements, where sampling a concrete value is the final refinement. By applying abstract interpretation at runtime to obtain an abstract element, we obtain a lightweight form of constraint solving and propagation that enables randomized testing of programs with complex preconditions. We identify three strategies for applying abstract interpretation: (1) speculative refinement, refining abstract elements before sampling based on immediately following constraints, (2) corrective refinement, calculating “desired” abstract elements from information gleaned from failed constraints, and (3) cascading propagation, propagating information from failures to components of compound expressions. We formalize these ideas in a generator DSL whose monadic semantics are parametric over abstract domains. We implement this DSL in a new tool called Lucas and evaluate it on sixteen workloads: the six original case studies from the Bennet paper, six position-independent data structures, and four free-list allocators. Comparing configurations with and without refinement, we find that refinement finds bugs in all four allocators and in two of the position-independent data structures that Bennet-style random backtracking fails to find.
STARS is presented, a novel test assertion generation technique that combines the benefits of static program analysis and LLM-based synthesis and goes beyond what an LLM alone could realistically guess based on the test prefix and focal method, and they naturally fit the given test case.
Jia-Lun Cao, Hao-Yu Wang, Hao-Ran Yan et al.· Proceedings of the ACM on So...· 0 citations
Automatically generating high-coverage unit tests for complex Java methods remains a formidable challenge, particularly when execution paths are guarded by intricate control-flow nesting and cross-class state dependencies. Existing LLM-based approaches predominantly follow a goal-driven paradigm, relying on unguided co...
Rui-Guo Yu, Rui-Qi Dong, Xi Xiao et al.· Proceedings of the ACM on So...· 0 citations
Concolic execution systematically explores program paths by solving symbolic constraints, but in object-oriented software its practical effectiveness is often limited by heap constraints over objects and heap structure, such as nullness, aliasing, runtime types, and field reachability. These constraints form a systemat...
Shao-Ran Xia, Le-Yi Cheng, Cai-Hua Dong et al.· Proceedings of the 41st IEEE...· 0 citations
EasyProver is presented, a Lean proving system built from recursive agents with isolated contexts, asynchronous search, parallel tactic probing, and an elastic elaboration service, and Aegis is introduced, which converts competitive programming problems into much harder verification tasks over real implementations.
Debargha Ganguly, Divya Raghunathan, Dejan Jovanovic et al.· 0 citations
What's new in research at Microsoft? Host Anson Ho explores the latest, including AI-powered universal translation, a breakthrough in a 31-year-old mathematics challenge, and advances making AI coding agents faster and more efficient. The post Microsoft Research Focus – Edition #98 appeared first on Microsoft Research.
AI agents can generate code at a scale that’s hard for humans to review line-by-line. PDD Kit helps ensure the code is doing what the developer intended by creating formal specifications and testing against them. It converts developer intent into a Verus specification, proves AI-generated code meets it for every input, and uses tests where proofs aren't practical. Developers review intent, not every line. The post Formally verifying agent-written full-stack web apps with PDD Kit appeared first o…