Oct 2026· Proceedings of the ACM on Software Engineering· Vol 3, pp. 3043 - 3061· 0 citations· 4 references
TL;DR
RecurIC3, a framework that alleviates redundant exploration due to the lack of a cross-level memory mechanism via structural reuse, is proposed and results suggest that structural reuse can substantially accelerate IC3.
Abstract
IC3/PDR has become a widely adopted technique for safety model checking due to its high efficiency. Despite its success, the algorithm often suffers from redundant exploration due to the lack of a cross-level memory mechanism. This results in the repetitive discovery of highly similar CTIs (Counterexamples to Induction), forcing the solver to waste computational effort traversing overlapping blocking chains. We propose RecurIC3, a framework that alleviates this bottleneck via structural reuse. RecurIC3 maintains a Bad State Tree (G_bad) that persistently records CTIs together with their level-aligned predecessor–successor links along blocking chains, turning the blocking phase into a history-aware process. To reduce solver calls, RecurIC3 first retrieves and rechecks lightweight candidates from G_bad and falls back to solver queries only when reuse is exhausted. This approach can significantly reduce the search space, thereby enhancing the verification efficiency of IC3. We implemented RecurIC3 in the state-of-the-art model checker Kind2 and evaluated it on the official benchmark suite. On instances where reuse is triggered, RecurIC3 reduces the number of explored tree nodes by 27%, achieves a 1.42× cumulative speedup, and solves 16 additional instances (13 Safe and 3 Unsafe) within the same timeout. These results suggest that structural reuse can substantially accelerate IC3.
Test-time reasoning systems often respond to failure by restarting or revising the latest step, even when an earlier decision caused the error. We introduce CORE, a search controller that requests a certified conflict core from a verifier, backjumps to the latest decision in that core, and caches the conflict to avoid...
Si-Yu Song, Rui-Peng Xu, Jia Lin et al.· arXiv.org· 0 citations
This work identifies two recurring proof barriers in self-composed IFV: implementation complexity, where proof-hard datapath logic dominates even though the property needs only a compact boundary relation, and relational inductive complexity, where the proof depends on cross-copy public-control facts that the backend p...
LLM-generated, verifier-checked semantic hints can serve as a practical complement to conventional word-level PDR, demonstrating notable speedups and timeout avoidance on hard cases.
Guangyu Hu, Ming-Kai Miao, Zhi-Yuan Yan et al.· arXiv.org· 1 citation
Formal theorem proving increasingly combines learned semantic guidance with verified symbolic execution. The quality of the symbolic search substrate therefore determines how much useful mathematical structure can be accumulated, reused, and exposed under a finite inference budget. We introduce ViaLean, a Lean4 prover...
This paper proposes CAST, a systematic testing framework designed to evaluate the compositional safety of LLMs in the domain of malicious code, and demonstrates that CAST systematically exposes severe safety violations in strongly aligned models that resist conventional red-teaming.
Lu Yan, Zhuo Zhang, Xiang-Zhe Xu et al.· Proceedings of the ACM on So...· 0 citations
Borrow checking is a central mechanism for Rust to ensure temporal memory safety. Its correctness is based on the intuition that the Aliasing XOR Mutability discipline guarantees that programs without borrow errors inherently could not access invalid references (i.e., pointers). However, existing work on formalizing bo...