MAB-BMC: A Formal Verification Enhancer by Harnessing Multiple BMC Engines Together
Open Access
- 13 August 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Design Automation of Electronic Systems
- Vol. 29 (5) , 1-37
Abstract
In recent times, Bounded Model Checking (BMC) engines have gained wide prominence in formal verification. Different BMC engines exist, differing in their optimization, representations and solving mechanisms used to represent and navigate the underlying state transition of the given design to be verified. The objective of this article is to examine if combinations of BMC engines can help to combine their strengths. We propose an approach that can create a sequencing of BMC engines that can reach better depth in formal verification, as opposed to executing them alone for a specified time. Our approach uses machine learning, specifically, the Multi-Armed Bandit paradigm of reinforcement learning, to predict the best-performing BMC engine for a given unrolling depth of the underlying circuit design. We evaluate our approach on a set of benchmark designs from the Hardware Model Checking Competition (HWMCC) benchmarks and show that it outperforms the state-of-the-art BMC engines in terms of the depth reached or time taken to deduce a property violation. The synthesized BMC engine sequences reach better depths than HWMCC results and the state-of-the-art technique, super_deep, for more than 80% of the cases. It also outperforms single engine runs for more than 92% of the cases where a property violation is not found within a given time duration. For designs where property violations are found within the given time duration, the synthesized sequences found the property violation in a lesser time than HWMCC for all the designs and outperformed both super_deep and single engine runs for more than 87% of the designs.Keywords
Funding Information
- Semiconductor Research Corporation (2022-IR-3164)
This publication has 17 references indexed in Scilit:
- Construction of Verifier Combinations Based on Off-the-Shelf Verifiers2022
- Algorithm selection for software validation based on graph kernelsAutomated Software Engineering, 2020
- Author Correction: SciPy 1.0: fundamental algorithms for scientific computing in PythonNature Methods, 2020
- PeSCo: Predicting Sequential Combinations of Verifiers2019
- ABC: An Academic Industrial-Strength Verification Tool2010
- An Incremental Algorithm to Check Satisfiability for Bounded Model CheckingElectronic Notes in Theoretical Computer Science, 2005
- Scalable Automated Verification via Expert-System Guided Transformations2004
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- Tuning SAT Checkers for Bounded Model CheckingLecture Notes in Computer Science, 2000
- Model checking1997