Skip to content

Efficient Branch-and-Bound Testing and Verification of zkVMs

Sep 2026 · arXiv.org · Vol abs/2609.15020 · 0 citations · 36 references
Computer Science

TL;DR

ZEBRA is a fully automated verification and bug-detection framework that reduces zkVM verification to a solution-set cardinality problem over a canonical trace space, where redundancies such as null-row padding and non-deterministic permutations are eliminated prior to counting.

Abstract

Zero-knowledge virtual machines (zkVMs) enable verifiable execution of general-purpose programs by translating virtual machine semantics into algebraic constraints over execution traces. The correctness of these constraints is critical: a single incorrect constraint can admit forged proofs (under-constrained) or reject valid executions (over-constrained). Existing approaches do not provide meaningful guarantees at production scale: fuzzers and unit tests often miss bugs, SMT solvers struggle with the size and nonlinearity of constraints, and theorem provers require substantial manual effort. We present ZEBRA, a fully automated verification and bug-detection framework: for a given program and input, the constraint must admit exactly one valid execution trace - no more and no fewer. This reduces zkVM verification to a solution-set cardinality problem over a canonical trace space, where redundancies such as null-row padding and non-deterministic permutations are eliminated prior to counting. To compute cardinality tractably, ZEBRA lifts analysis from finite-field witnesses to an integer interval lattice, exploiting a structural sparsity property of zkVM constraints: across 5 real-world zkVMs, constraints utilize only 14.0% of their theoretical connectivity capacity on average. This sparsity enables tight interval propagation with limited approximation error. ZEBRA performs a parallel branch-and-bound search that either produces a concrete counter-example or certifies the absence of violations within a bounded region. We evaluate ZEBRA on five real-world zkVMs. ZEBRA discovers 11 zero-day bugs; 6 have already been independently confirmed and 3 have been fixed by developers. Compared to SMT-based verification, ZEBRA is 51.5x faster, verifies 16.5 percentage point more instances, and its range verification provides up to 63x efficiency gain over repeated single-input verification.

View source

Similar papers

Checking Leakage Witnesses versus Certifying Bounded Non-Leakage

When a language-model audit finds no leak, what is needed to certify non-leakage? We study guarantees over a declared prompt domain under an executable leakage criterion and decoding rule. For general bounded polynomial-time evaluators, a supplied leaking execution is polynomial-time checkable, while leak existence is...

Chao Feng, Burkhard Stiller · 0 citations
Open access Oct 2026

LLM-Assisted Unsatisfiability Proofs for Satisfiability Modulo Theories, Oracles, and Natural Language

NLUnsat is presented, an SMT solver capable of producing proofs of unsatisfiability for first-order theories that include closed-box function calls, and an extension of the SMT-LIB language is introduced that operates over this extended syntax to find unsatisfiability proofs on SMT-LIB formulas with closed-box function...

Gourav Takhar, S. Lahiri, P. Kalita et al. · 0 citations
#artificial intelligence Preprint Sep 2026

SOVER: Formal Certification of Optimization Reformulations via LLM-Assisted SMT Verification

SOVER, an LLM-assisted SMT framework that separates semantic mapping from formal certification, is introduced, and Z3 checks domain cross-feasibility and global objective-order preservation for mixed-integer linear formulations, while dReal provides tolerance-aware feasibility/range and $\epsilon$-argmin checks for con...

Swapnil Bhattacharyya, Mayank Baranwal · 0 citations
#software testing Open access Oct 2026

Random Testing via Runtime Abstract Interpretation

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.

Zain K. Aamer, Benjamin C. Pierce · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.