A Learning-Based Framework for Automatic Parameterized Verification
Yongjian Li, Jialun Cao, Jun Pang · 2019
Parameterized verification is shown to be a complicated and undecidable problem. The challenge of parameterized verification lies in how to construct appropriate invariants. Designing algorithms to find such invariants automatically has become an active research area since the last decade. With the advent of some recent works, automatically finding invariants has become possible, but most of these invariants are unreadable, making them difficult to be understood by protocol designers and researchers. Therefore, we propose an automatic framework that learns a set of readable and simple invariants to support in protocol design. It takes advantage of association rule learning, and combines the learning algorithm with parameterized verification. It is noteworthy that the gap between machine learning algorithms and parameterized verification seems to be huge, as they rely on statistical learning and symbolic reasoning, respectively. Our framework, however, builds a bridge through association rules and invariants, making their combination possible. Besides, we also propose an invariant-guided strengthening paradigm, providing an innovative perspective to existing abstraction-strengthening methods. Our framework has been successfully applied to several benchmarks, including an industrial-scale protocol FLASH.