A Novel Counterexample-Guided Inductive Synthesis Framework for Barrier Certificate Generation
Mi Ding, Kaipeng Lin, Lin Wang, Zuohua Ding · 2022
Barrier certificate is a powerful and practical approach of safety verification for hybrid systems. In this paper, we propose a novel Counterexample-Guided Inductive Synthesis (CEGIS) procedure for synthesizing neural barrier certificates. The CEGIS procedure is structured as an inductive loop where a learner and a verifier interact to synthesize barrier certificates. The learner trains candidate barrier certificates expressed as feedforward neural networks with polynomial activations, and the verifier employs computer algebra techniques to either ensure the validity of the trained candidate barrier certificate or produce informative counterexamples, which can effectively reduce the number of CEGIS iterations. We implement the CEGIS tool and evaluate its performance over a set of benchmarks. The experimental results demonstrate the effectiveness and efficiency of our approach.