UC-based Approximate Incremental Reachability

In recent years, formal verification technology has received more and more attention, and it plays an important role in ensuring the safety and correctness of systems in safety-critical areas. As a branch of formal verification with a high degree of automation, model checking has a very broad development prospect. This study analyzes and proposes a new model checking technique, which can effectively check transition systems, including bug-finding and safety proof. Different from existing model checking algorithms, the proposed method, Unsatisfiable Core (UC)-based Approximate Incremental Reachability (UAIR), mainly utilizes the UC to solve a series of candidate safety invariants until the final invariant is generated, so as to realize safety proof and bug-finding. In symbolic model checking based on the SAT solver, this study uses the UC obtained by the satisfiability solver to construct the candidate safety invariant, and if the transition system itself is safe, the obtained initial invariant is only an approximation of the safety invariant. Then, while checking the safety, the study incrementally improves the candidate safety invariant until it finds a true invariant that proves the system is safe; if the system is unsafe, the method can finally find a counterexample to prove the system is unsafe. The brand new method exploits UCs for safety model checking and achieves good results. It is known that there is no absolute best method in the field of model checking. Although the proposed method cannot surpass the current mature methods such as IC3 and complement Approximate Reachability (CAR), in terms of the number of solvable benchmarks, the method in this paper can solve three cases that other mature methods are unable to solve. It is believed that the method can be a valuable addition to the model checking toolset.