Aug 2026· Proc. ACM Program. Lang.· Vol 10, pp. 160 - 173· 0 citations· 16 references
Computer Science
TL;DR
A QuickCheck testing method based on generating and shrinking random execution traces based on checking if the first and last terms of a generated trace share the same deterministic normal form that efficiently finds counterexamples and enables fast, robust shrinking.
Abstract
Term rewriting systems are a common tool in automated reasoning and semantics of programming languages, and many practical applications require these systems to be convergent. While automated tools and theory exist to establish convergence, this paper is concerned with a practical method for testing it to quickly find useful counterexamples. Standard property-based testing approaches struggle here: exhaustively computing all normal forms is fundamentally flawed and too slow, while generating random normal forms makes counterexample minimization (shrinking) fragile due to dependencies on earlier generated test data. To solve this, we introduce a QuickCheck testing method based on generating and shrinking random execution traces. By checking if the first and last terms of a generated trace share the same deterministic normal form, we remove the data dependency between generators. This approach yields a property that efficiently finds counterexamples and enables fast, robust shrinking. We demonstrate the effectiveness of this method on various examples, ranging from group theory equations to distributed process calculus.
A reusable, locale-based framework of sloped graphs is developed that defines Infinite Descent at an abstract level, independently of any concrete graph encoding, and formalize tool-facing sufficient criteria, prove their soundness, and certify incompleteness where appropriate via verified counterexamples.
Jamie Wright, L. Cohen, R. Rowe et al.· International Conference on...· 1 citation
This paper provides a formal account of the syntax and semantics of Hedgehog, a popular PBT framework, and proves that Hedgehog→ possesses a compositional distribution semantics, and introduces Hedgehog→, a restricted version of the language based on the arrow calculus, and proves that Hedgehog→ possesses a compositional distribution semantics.
Anthony Vandikas, Kiarash Sotoudeh, Marsha Chechik· Proc. ACM Program. Lang.· 0 citations
Test or prove? These two approaches to software verification have long been presented as opposites. One is dynamic, the other static: A test executes the program, a proof only analyzes the program text. A different perspective is emerging, in which testing and proving are complementary rather than competing techniques for producing software of verified quality. Work performed over the past few years and reviewed here develops this complementarity by taking advantage of "design by contract," as available in Eiffel, and exploiting a feature of modern program-proving tools based on "satisfiability modulo theories" (SMT): counterexample generation. A counterexample is an input combination that makes the program fail. If we are trying to prove a program correct, we hope not to find any. One can, however, apply counterexample generation to incorrect programs, as a tool for automatic test generation. We can also introduce faults into a correct program and turn the counterexamples into an automatically generated regression test suite with full coverage. Additionally, we can use these mechanisms to help produce program fixes for incorrect programs, with a guarantee that the fixes are correct. All three applications, leveraging on the mechanisms of Eiffel and design by contract, hold significant promise to address some of the challenges of program testing, software maintenance, and automatic program repair. Moving past the traditional opposition between tests and proofs, current work on software verification treats them as complementary.
Li Huang, Bertrand Meyer, M. Oriol· Communications of the ACM· 0 citations
A proof checker called Nörgler is introduced that builds upon and extends the established approach pioneered by GDV and supports checking propositional, (untyped and typed) first-order, and higher-order refutations represented in TSTP.
Melanie Taprogge, H. Sariyanto, Alexander Steen· 0 citations
This work presents a deductive verification framework based on a weighted assertion language and an intermediate verification language, whose weight domains are ordered structures with implication and coimplication, which let verification conditions express lower- and upper-bound obligations internally.
Emma Ahrens, Samuel Rode, Philipp Schröer et al.· 0 citations
