CS Paper Radar

Formalizing the Omega Test in Dafny

Ariadna Brănici-Faraon, Ştefan Ciobâcă, Diana-Elena Gratie

cs.LO cs.PLcs.SC ·submitted 2026-09-28 10:58 UTC · v1
published

Abstract

We present a formalization in Dafny of the Omega Test, an algorithm used to decide the satisfiability of a system of inequalities. The implementation defines executable representations for rational numbers, linear expressions, inequalities, equalities, divisibility constraints, and systems of constraints, together with their semantic interpretation through valuations. We fully specify and verify the implementation in Dafny. We describe the lessons learned and how the formalization process led to new insights into the algorithm.

Comment
In Proceedings FROM 2026, arXiv:2609.30324
Journal ref
EPTCS 452, 2026, pp. 67-81
DOI
10.4204/EPTCS.452.5

Closest papers

Nearest neighbours by meaning across the whole index.

The Formalization of two Computational Models in Dafny

cs.LO cs.FLcs.PL ·2026-09-28 ·Ştefan Ciobâc\b{a}, Diana-Elena Gratie, Dragoş-Irinel Rotariu
publishedtheory similarity 0.61
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

We describe the formalization in Dafny of two computational models, Turing Machines and the Lambda Calculus. We present several application of the formalizations: machine proofs of termination for Turing machines, Dafny proofs for Church encodings, and a mechanized proof of the Church-Rosser theorem.

0.41

DSpec2Test: Specification-Driven Test Generation in Dafny

cs.SE ·2026-08-31 ·Sofia Vieira Pinto, Álvaro F. Silva, João Pascoal Faria, Alexandra Mendes
top venue similarity 0.60
Abstract

Verification-aware languages, such as Dafny, integrate logical constructs into code and enable automatic verification of program correctness. However, tests remain helpful in scenarios that verification alone does not address (e.g., to support test-driven development). Existing Dafny test generation tools are implementation-based, limiting their applicability in this context. We present DSpec2Test, a specification-driven test generation tool for Dafny that automatically derives tests from formal specifications, without considering implementation details. Our tool extends Dafny's generate-tests command with a new blackbox mode based on Disjunctive Normal Form (DNF) equivalence class partitioning and optional Boundary Value Analysis (BVA). DSpec2Test relies on the Z3 SMT solver to synthesize inputs and expected outputs that meet the specification-derived constraints. We evaluate DSpec2Test on programs from DafnyBench mutated using MutDafny and compare it against Dafny's existing implementation-driven Block mode. DSpec2Test achieves a 93.9% mutation kill rate on a dataset of 131 mutants, outperforming Block's 82.4%, and uniquely killing 17 mutants. These results suggest that specification-driven testing is an effective and complementary approach for testing Dafny programs.

0.51

ProofPulse: Interactive Proof Coverage Analysis for Dafny

cs.SE ·2026-08-31 ·Álvaro F. Silva, Ruben Martins, Alexandra Mendes
top venuebenchmark similarity 0.57
Abstract

Deductive verification ensures that an implementation satisfies its specification, but successful verification does not guarantee the quality of the specification. As such, weak specifications and redundant invariants may create overconfidence in ``verified'' code. We present \proofpulse, a tool for Dafny that diagnoses specification quality using a three-valued proof coverage model. By analyzing proof dependencies, ProofPulse distinguishes between elements that contribute to specification intent, those used only for auxiliary checks, and those irrelevant to any proof obligation. Evaluated against an oracle of 252 programs from the dafny-synthesis benchmark, ProofPulse provides a high-precision signal for specification weaknesses, particularly unnecessary preconditions and vacuous proofs. With unsat-core minimization, ProofPulse achieves perfect precision for precondition classification and reduces false positives across all evaluated categories. These results show that proof coverage is a practical complement to verification. Although it cannot fully capture semantic intent, it can reveal weak proof coupling in programs that otherwise appear fully verified. Just as a pulse check distinguishes vitality from the mere absence of symptoms, ProofPulse exposes weaknesses in proofs that technically verify successfully but still suffer from inadequate or redundant code and specifications.

0.46

DafnyCert: Certifying Specification Strength in Dafny

cs.SE ·2026-11-11 ·Álvaro Silva, Isabel Amaral, Ruben Martins, Alexandra Mendes
similarity 0.57
Abstract

Formally verifying a method with Dafny guarantees correctness relative to its specification. However, a specification may be too permissive, allowing multiple outputs for the same input, even when the implementation produces only one. In this paper, we propose checkable certificates that provide independently verifiable evidence of whether a specification is weak or strong. A certificate of weakness contains an alternative implementation that verifies against the original specification, together with a witness input on which the original and alternative implementations produce different results. A certificate of strength is produced by constructing a harness around the original method such that successfully verifying the harness guarantees that the specification allows at most one possible output for any given input. We present DafnyCert, a tool that automatically produces these certificates. Strength is established by constructing and verifying the harness. Weakness is demonstrated by using the MutDafny mutation tool to find mutants that verify against the original specification, and by using the Hypothesis property-based testing framework to generate inputs that produce different outputs for the original program and the mutant. The resulting mutant and witness form a recheckable certificate of weakness. On a dataset of 3,910 verified Dafny methods from Dafny-Synthesis and VeriEquivBench, DafnyCert automatically certifies 3,570 methods (91.3%). We also provide certificates for the remaining 340 methods. To our knowledge, this is the first dataset in which every specification is backed by a checkable certificate of strength or weakness. These labels disagree with the benchmarks' original labels for 16.3% of the methods. These findings highlight the importance of supporting specification strength labels with independently checkable evidence.

0.25

More Powerful Constant Value Checking with SMT Solving

cs.PL ·2026-10-04 ·Jonas Mittnacht, Florian Lanzinger
similarity 0.55
Abstract

Pluggable type systems extend the basic type system of a programming language by introducing additional type hierarchies to specify more complex properties and dependencies between variables. We consider the Constant Value Checker, a pluggable type checker for Java implemented using the Checker Framework, which provides various pluggable type systems and corresponding checkers. The Constant Value Checker lets users specify restrictions on the values a primitive integer or boolean variable can hold using a set or range of constant values. However, the current implementation of the Value Checker makes use of a limited set of syntactic typing rules that, in practice, often fail to verify well-typedness of more complex code. In this paper, we introduce an extension to the Checker Framework using Satisfiability Modulo Theories (SMT) solvers to address these limitations by creating corresponding first-order logic formulas for expressions whose type checks fail with the current syntactic typing rules and determining their well-typedness based on the satisfiability of these formulas. Furthermore, we introduce new dependent types for specifying allowed values with expressions that can depend on other variables in the program.

0.22

Idealizing Useful Fictions in Omega Grounded Arithmetic

cs.LO math.LOcs.PL ·2026-08-18 ·Bryan Ford
theory similarity 0.55
Abstract

Grounded arithmetic is a family of formal systems for reasoning about computation in which a statement may be asserted only when a terminating computation backs it; the logics are paracomplete - for a sentence whose backing computation never settles, neither the sentence nor its negation is derivable, so paradoxes like the Liar are harmless rather than explosive. The reflective member of the family, RGA, can quantify over its own computations, but cannot certify that its own unbounded searches have definite yes-or-no answers. This paper studies what happens when that openness is closed by exactly one rule - ATI, the $ω$-grounded universal: if every numeric instance of a universal sentence is certified decided, the universal is certified decided. The resulting system, OGA, shares RGA's syntax and rules symbol-for-symbol otherwise, and every consequence is developed as a machine-checked theorem. Decidedness certificates become abundant - every totality question about a computable function is certified to have an answer, whether or not anyone can produce it - and this is exactly the provable separation between the two systems. OGA is complete for its own semantics; certified-but-unresolved sentences receive values built from the system's own open questions. Provability remains recursively enumerable, with a primitive-recursive certificate checker, while $ω$-truth deliberately is not. Within that asymmetry, incompleteness takes a new form. The Gödel sentence is classified, unconditionally, as a genuine fiction: neither provable nor refutable, yet valued, and carrying a computable pedigree recording exactly what adopting it as an axiom commits one to. The adoption is itself a theorem suite: extending OGA by any finite stock of true fictions is consistent, and independently certified adoptions can never collide.

0.26

LLM-Assisted Verification in Dafny

cs.LO cs.AIcs.SE ·2026-11-12 ·Wieger Wesselink, Kees Huizing, Huub van de Wetering
theory similarity 0.55
Abstract · 16 pages (excluding references), 20 pages including references; 1 figure, 2 tables. Submitted to FSEN 2027

Formal verification of complex algorithms requires expertise in program specification, invariant construction, mathematical proof, and the management of automated theorem provers. Although large language models (LLMs) can generate program code and proof fragments, reliably developing complete machine-checked verifications remains challenging: it requires an iterative process of constructing and validating specifications and invariants, building proofs, diagnosing solver failures, and optimizing verification performance. This paper presents a systematic ten-step workflow for LLM-assisted verification of scientific algorithms using the Dafny verification system. The workflow integrates algorithm formalization, contract development, empirical invariant validation, proof construction, bottleneck profiling, and resource-driven proof optimization. We applied the workflow using Antrhopic's Claude Opus 5 and Opus 5.5 models, combining LLM-driven development with automated testing and verification feedback, while retaining human oversight for correctness-critical decisions and strategic interventions. We evaluate the approach on 37 complex algorithms from graph theory and labelled transition systems. Notably, we verified the Hopfcroft-Tarjan triconnectivity test, demonstrating that even highly challenging algorithmic verification tasks can be carried out through a structured LLM-assisted workflow. Many of our machine-checked verifications were obtained within hours to a few days of interactive development. Our results suggest that LLM-assisted workflows can shift the role of the human verifier from detailed proof construction toward supervision, specification review, and strategic guidance.

0.46

Further simulations between tropical and linear programming

cs.CC math.OC ·2026-11-18 ·Edward A. Hirsch, Dmitrii Sluch
theory similarity 0.54
Abstract

Propositional proof systems that apply various kinds of cuts to linear inequalities (such as Cutting Planes [CCT87] and Lift&Project [BCC93,Pud99,Das05]) or operate with disjunctions of linear inequalities (such as Res(CP) [Kra98] and Res(LP) [HK06]) have been in the focus of research for the past 30 years. Recently, tropical proof systems were introduced [AGH25]; they resemble the latter systems but differ from them in important respects. The relations between the traditional systems and the new tropical systems have remained largely unknown, and exponential lower bounds for tropical systems were limited to non-CNF examples. In this paper we prove several new polynomial simulations between these systems. To this end, we introduce Thr-Res (Threshold Resolution), a new natural daglike proof system operating on threshold conditions over the Boolean literals: lines asserting that at least s literals of a given multiset are true. Its main difference from CP is that the rounding rule (without it CP is incomplete) is replaced by a weaker rule that allows one to perform "resolution" steps with linear combinations beyond Boolean clauses; also, in its addition rules, Thr-Res resembles input resolution [Cha70]: a derived line is combined with an input clause or an axiom, whereas CP can add up any two derived lines. By varying the maximum value of s, one obtains systems ranging in strength from Resolution to MP-NSR, the static tropical (min-plus) proof system introduced in [AGH25]. As a consequence, we prove that MP-NSR is polynomially simulated by CP and L&P (even by their unary versions), which automatically yields exponential lower bounds on the size of MP-NSR proofs for formulas in CNF. We complement it with simulations in the converse direction: binary daglike MP-PCR (a dynamic version of MP-NSR) polynomially simulates L&P; it also polynomially simulates CP when division axioms are added.

0.38