National Cyber Warfare Foundation (NCWF)login

yinyang for stress-testing SMT solvers with mutated formulas


0 user ratings
2026-11-13 03:28:30
milo
Red Team (CNA)
"yinyang

yinyang is a Python fuzzing framework that mutates seed SMT-LIB 2 formulas to find correctness and crash bugs in SMT solvers like Z3 and CVC4, intended for researchers and authorized solver developers.








Tooltestsmt/yinyang — a fuzzing framework that generates mutant SMT formulas to stress-test SMT solvers
CategoryFuzzing / automated testing of formal-reasoning software
Primary UseRobustifying SMT solvers by fuzzing them with mutants of seed SMT-LIB 2 benchmarks, collecting bug triggers under ./bugs
Safe UseIntended for solver developers, QA engineers, and academic researchers testing software they own or are authorized to assess; no third-party systems are targeted
Telemetry NotePurely offline local testing; it leaves bug-trigger files on disk and produces solver crashes — defenders would only observe it as ordinary high-volume local process activity

Satisfiability modulo theories (SMT) solvers sit quietly underneath an enormous amount of modern security tooling: symbolic execution engines, program verification frameworks, constraint-based test generators, and even configuration analysis all lean on solvers like Z3, CVC4, and CVC5 to answer queries correctly. That dependency makes solver correctness a security property in itself — a wrong answer or a crash inside a solver propagates directly into whatever analysis was built on top of it. testsmt/yinyang is a Python framework that addresses this problem head-on by fuzzing SMT solvers with mutated formulas, and its track record is compelling: the README reports over 1,500 bugs found in Z3 and CVC4, the two solvers it names as state of the art.


The core idea is mutation-based fuzzing applied to the SMT-LIB 2 input language rather than to binary formats or network protocols. You provide a corpus of seed SMT formulas, and yinyang generates mutants of those formulas to stress-test whatever solver you point it at. Because the inputs are text constraints in a well-defined logic, the mutations can exercise deep semantic corners of a solver — rewrite rules, theory combination, quantifier handling — rather than just parser edges. The project's topics list (cvc4, cvc5, fuzzing, smt, smt-lib, smt-solver, testing, z3) makes clear that the primary targets are the mainstream SMT solvers supporting the standard SMT-LIB 2 format.


Installation follows the standard pip3 install yinyang path for a stable release, which is the first of the two invocation examples worth noting. For the development version, the README gives a git clone https://github.com/testsmt/yinyang.git followed by pip3 install antlr4-python3-runtime==4.9.2 ffg. That pinned antlr4-python3-runtime dependency is a revealing architectural detail: yinyang parses SMT-LIB input into a proper syntax tree rather than doing naive byte-level mutation, which is exactly what you want if your mutants are to remain syntactically valid enough to reach interesting solver logic. The README also suggests adding yinyang/bin to your PATH for convenient execution.


The documented workflow has three stages, and the first is corpus acquisition. A helper script, ./scripts/SMT-LIB-clone.sh QF_LIA QF_BV, downloads benchmark sets for the named logics from the SMT-LIB release hosted on Zenodo; run without arguments it simply lists available logics, and it requires curl, tar, and zstd on the host. Alternatively you can pull benchmarks directly from the SMT-LIB website or supply your own corpus. The logics named in the example — QF_LIA (quantifier-free linear integer arithmetic) and QF_BV (quantifier-free bitvectors) — are sensible starting points because bitvector reasoning in particular underpins much of the binary-analysis tooling that security engineers care about.


Stage two is obtaining and building at least two SMT solvers that speak SMT-LIB 2, which the README explicitly requires — two or more, not one. This is the strongest hint at how yinyang decides whether a mutant has exposed a bug: with multiple solvers evaluating the same formula, divergent answers (one says sat, another says unsat, or one crashes while another succeeds) are a sound signal that something is wrong in at least one implementation. The solvers don't need identical internal behavior for this to work; they only need to agree on the semantics of the standard input language.


The third stage is the run itself, and the README's example is the second invocation worth quoting: typefuzz "z3 model_validate=true;cvc4 --check-models -m -i -q" benchmarks. Note that the solver invocations are themselves configured for self-checking — model_validate=true for Z3 and --check-models for CVC4 — so the solvers are asked to validate their own models in addition to being cross-checked against each other. That layered oracle design (self-validation plus differential comparison) is a pragmatic pattern that any fuzzer author working on complex analytical software can learn from.


Operationally, yinyang defaults to randomly selecting formulas from ./benchmarks and generating 300 mutants per seed formula. When a bug is found, the triggering input is stored under ./bugs, giving you a reproducible artifact to attach to a solver issue tracker. The loop is infinite by design, terminated manually with CTRL+C, which fits the typical overnight-fuzzing cadence of solver development teams. The typefuzz entry point name suggests the framework is organized around type-aware or logic-aware fuzzing strategies rather than a single monolithic mutator, though the README keeps the details in its hosted documentation at yinyang.readthedocs.io.


From a maturity standpoint, the repository signals seriousness: continuous-integration badges, dedicated hosted documentation, an MIT license, roughly 201 stars, and institutional recognition including a Google Open Source Peer Bonus and an Amazon Research Award. The project also maintains a website with bug statistics and talk videos, which is the kind of paper-trail you want when evaluating whether a research tool is production-usable. The maintainers explicitly invite feedback and offer help adapting yinyang to custom solvers, so teams building in-house constraint engines are within the tool's intended audience.


In an authorized workflow, the tool sits squarely in the software-assurance category: you fuzz solvers you develop or maintain, in your own lab environment, and file the resulting triggers upstream. There is nothing here that touches third-party systems — the entire pipeline is local files, local solver binaries, and a benchmark corpus. For defenders, the relevance is indirect but real: if your organization ships products that embed an SMT solver, running yinyang against the pinned solver version during CI or release hardening is a cheap way to catch correctness regressions before they become logic bugs in your own product.


The telemetry footprint is correspondingly benign: no network callbacks, no reporting home, just file I/O against ./benchmarks and ./bugs plus repeated local solver process spawns. If anything, the observable signature is high CPU utilization from thousands of short-lived solver processes, which is exactly what you'd expect from any local fuzzing harness. Combined with the clean dependency story and documented build, this makes yinyang a low-risk addition to a testing infrastructure.


For practitioners evaluating it against alternatives, the key differentiator is the SMT-specific mutation design versus generic grammar fuzzers like fuzzingbook-style grammar approaches or naive text mutators. By working at the level of the SMT-LIB 2 AST — evidenced by the antlr4 runtime dependency — and pairing structural mutation with a differential oracle, yinyang reaches solver internals that format-agnostic fuzzers rarely touch. Anyone whose security tooling depends on solver correctness, from symbolic-execution engine maintainers to formal verification teams, will find it a well-documented, focused, and institutionally backed instrument for exactly that problem.



Official project repository for testsmt/yinyang.

Download Tool

Educational analysis for authorized security professionals. Use only in controlled, authorized environments.






Source: OffensiveSec
Source Link: https://www.offsecblog.com/2026/11/yinyang-for-stress-testing-smt-solvers.html


Comments
new comment
Nobody has commented yet. Will you be the first?
 
Forum
Red Team (CNA)



Copyright 2012 through 2026 - National Cyber Warfare Foundation - All rights reserved worldwide.