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.
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...
Results confirm that permutation-based MBA obfuscation offers a practical, composite, and resilient defense against symbolic execution, balancing strong protection with lightweight performance overhead.
Mo-Xuan Wang, Hai-Yan Hu, Hao-Hang Qin et al.· Journal of computing and sec...· 0 citations
The refutation gap is closed with a pipeline that synthesizes minimal linear straight-line programs over GF(2), where every decisive UNSAT answer emits a DRAT proof checked by an independent third-party checker.
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.· Proceedings of the ACM on Pr...· 0 citations
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...
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· Proceedings of the ACM on Pr...· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.