Orax: A Feedback-Driven Framework for Efficiently Solving Satisfiability Modulo Theories and Oracles
Open Access
- 9 April 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (OOPSLA1) , 676-703
Abstract
Recent advancements in Satisfiability Modulo Theory (SMT) solving have significantly improved formula-driven techniques for verification, testing, repair, and synthesis. However, addressing open programs that lack formal specifications, such as those relying on third-party libraries, remains a challenge. The problem of Satisfiability Modulo Theories and Oracles (SMTO) has emerged as a critical issue where oracles, representing components with observable behavior but unknown implementation, hinder SMT solver from reasoning. Existing approaches like Delphi and Saadhak struggle to effectively combine sufficient oracle mapping information that is crucial for feasible solution construction with the reasoning capabilities of the SMT solver, leading to inefficient solving of SMTO problems. In this work, we propose a novel solving framework for SMTO problems, Orax, which establishes an oracle mapping information feedback loop between the SMT solver and the oracle handler. In Orax, the SMT solver analyzes the deficiency in oracle mapping information it has and feeds this back to the oracle handler. The oracle handler then provides the most suitable additional oracle mapping information back to the SMT solver. Orax employs a dual-clustering strategy to select the initial oracle mapping information provided to the SMT solver and a relaxation-based method to analyze the deficiency in the oracle mapping information the SMT solver knows. Experimental results on the benchmark suite demonstrate that Orax outperforms existing methods, solving 118.37% and 13.83% more benchmarks than Delphi and Saadhak, respectively. In terms of efficiency, Orax achieves a PAR-2 score of 1.39, significantly exceeding Delphi’s score of 669.13 and Saadhak’s score of 173.31.Keywords
Funding Information
- Beijing Natural Science Foundation (L243010)
This publication has 47 references indexed in Scilit:
- Local Search For Satisfiability Modulo Integer Arithmetic TheoriesACM Transactions on Computational Logic, 2023
- Reinforcement Learning-based Hierarchical Seed Scheduling for Greybox Fuzzing2021
- Automated program repairCommunications of the ACM, 2019
- Satisfiability Modulo Theories2018
- A Unifying View on SMT-Based Software VerificationJournal of Automated Reasoning, 2017
- Synergistic effects of polymer and bentonite clay on rheology and thermal stability of foam fluid developed for hydraulic fracturingAsia-Pacific Journal of Chemical Engineering, 2017
- Local search for Boolean Satisfiability with configuration checking and subscoreArtificial Intelligence, 2013
- Symbolic execution for software testingCommunications of the ACM, 2013
- Program sketchingInternational Journal on Software Tools for Technology Transfer, 2012
- Satisfiability modulo theoriesCommunications of the ACM, 2011