Lune

ASE2024Top-tier venue

Constraint-Based Test Oracles for Program Analyzers

Markus Fleischmann, David Kaindlstorfer, Anastasia Isychev, Valentin Wüstholz, Maria Christakis

Abstract

Program analyzers implement complex algorithms and, as any software, can contain bugs. Bugs in their implementation may lead to analyzers being imprecise and failing to verify safe programs, i.e., programs with no reachable error locations; or worse, analyzer bugs may lead to reporting unsound results by verifying unsafe programs, i.e., programs with reachable error locations. In this paper, we propose a method to detect such bugs by generating constraint-based test oracles for analyzers. We re-purpose and extend Fuzzle, a tool for benchmarking fuzzers, in a tool called Minotaur. Minotaur generates C programs from SMT constraints, and based on the satisfiability of the constraints, derives whether the generated programs are safe or unsafe. For instance, for an unsafe program, an analyzer under test contains a soundness issue if it proves it safe. Using Minotaur, we found 30 unique soundness and precision issues in 11 well-known analyzers that reason about reachability properties.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

3 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • On the unusual effectiveness of type-aware operator mutations for testing SMT solvers cites Validating SMT solvers via semantic fusion
  • On the unusual effectiveness of type-aware operator mutations for testing SMT solvers cites Detecting critical bugs in SMT solvers using blackbox mutational fuzzing
  • Fuzzing Processing Pipelines for Zero-Knowledge Circuits cites GrayC: Greybox Fuzzing of Compilers and Analysers for C
  • Fuzzing Processing Pipelines for Zero-Knowledge Circuits cites On the unusual effectiveness of type-aware operator mutations for testing SMT solvers
  • Fuzzing Processing Pipelines for Zero-Knowledge Circuits cites Validating SMT solvers via semantic fusion
  • Fuzzing Processing Pipelines for Zero-Knowledge Circuits cites Generative type-aware mutation for testing SMT solvers
  • Fuzzing Processing Pipelines for Zero-Knowledge Circuits cites Detecting critical bugs in SMT solvers using blackbox mutational fuzzing
  • Cost-Effective Testing of MPC Compilers cites GrayC: Greybox Fuzzing of Compilers and Analysers for C
  • Cost-Effective Testing of MPC Compilers cites On the unusual effectiveness of type-aware operator mutations for testing SMT solvers
  • Cost-Effective Testing of MPC Compilers cites Validating SMT solvers via semantic fusion
  • Cost-Effective Testing of MPC Compilers cites Generative type-aware mutation for testing SMT solvers
  • Cost-Effective Testing of MPC Compilers cites Fuzzing Processing Pipelines for Zero-Knowledge Circuits
  • Cost-Effective Testing of MPC Compilers cites Detecting critical bugs in SMT solvers using blackbox mutational fuzzing
  • Testing Static Taint Analyzers with Equivalence Modulo Taint cites GrayC: Greybox Fuzzing of Compilers and Analysers for C
  • Testing Static Taint Analyzers with Equivalence Modulo Taint cites On the unusual effectiveness of type-aware operator mutations for testing SMT solvers
  • Testing Static Taint Analyzers with Equivalence Modulo Taint cites Validating SMT solvers via semantic fusion
  • Testing Static Taint Analyzers with Equivalence Modulo Taint cites Generative type-aware mutation for testing SMT solvers
  • Testing Static Taint Analyzers with Equivalence Modulo Taint cites Fuzzing Processing Pipelines for Zero-Knowledge Circuits
  • Testing Static Taint Analyzers with Equivalence Modulo Taint cites Detecting critical bugs in SMT solvers using blackbox mutational fuzzing
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. Fuzzing Processing Pipelines for Zero-Knowledge CircuitsChristoph Hochrainer, Anastasia Isychev, Valentin Wüstholz, Maria ChristakisCCS 2025 · 1 citation
  2. Cost-Effective Testing of MPC CompilersSebastian Watzinger, Valentin Wüstholz, Deepak Garg, Maria ChristakisFSE 2026
  3. Testing Static Taint Analyzers with Equivalence Modulo TaintMaria Christakis, Anastasia Isychev, Samuel Pilz, Florian Tesarek et al.ISSTA 2026

Builds on13

  1. Validating SMT solvers via semantic fusionDominik Winterer, Chengyu Zhang, Zhendong SuPLDI 2020 · 80 citations
  2. On the unusual effectiveness of type-aware operator mutations for testing SMT solversDominik Winterer, Chengyu Zhang, Zhendong SuOOPSLA 2020 · 55 citations
  3. GrayC: Greybox Fuzzing of Compilers and Analysers for CKarine Even-Mendoza, Arindam Sharma, Alastair F. Donaldson, Cristian CadarISSTA 2023 · 52 citations
  4. Detecting critical bugs in SMT solvers using blackbox mutational fuzzingMuhammad Numair Mansur, Maria Christakis, Valentin Wüstholz, Fuyuan ZhangFSE 2020 · 51 citations
  5. Generative type-aware mutation for testing SMT solversJiwon Park, Dominik Winterer, Chengyu Zhang, Zhendong SuOOPSLA 2021 · 31 citations

Related papers

  1. Fuzzle: Making a Puzzle for FuzzersHaeun Lee, Soomin Kim, Sang Kil ChaASE 2022 · 13 citations
  2. Interrogation Testing of Program Analyzers for Soundness and Precision IssuesDavid Kaindlstorfer, Anastasia Isychev, Valentin Wüstholz, Maria ChristakisASE 2024 · 2 citations
  3. Automatically testing string solversAlexandra Bugariu, Peter MüllerICSE 2020 · 28 citations
  4. Finding and Understanding Defects in Static Analyzers by Constructing Automated OraclesWeigang He, Peng Di, Mengli Ming, Chengyu Zhang et al.FSE 2024 · 6 citations
  5. SMT2Test: From SMT Formulas to Effective Test CasesChengyu Zhang, Zhendong SuOOPSLA 2024 · 5 citations
Dusk over the sea between two cliffs drawn in fine vertical lines