Scaling BDD-based timed verification with simulation reduction

• Main Authors: NGUYEN, Truong Khanh, TAN, Tian Huat, SUN, Jun, LI, Jiaying, LIU, Yang, CHEN, Manman, DONG, Jin Song
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2016
• Subjects: Programming Languages and Compilers; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/4944; https://ink.library.smu.edu.sg/context/sis_research/article/5947/viewcontent/scaling_bdd.pdf
• Institution: Singapore Management University

Digitization is a technique that has been widely used in real-time model checking. With the assumption of digital clocks, symbolic model checking techniques (like those based on BDDs) can be applied for real-time systems. The problem of model checking real-time systems based on digitization is that the number of tick transitions increases rapidly with the increment of clock upper bounds. In this paper, we propose to improve BDD-based verification for real-time systems using simulation reduction. We show that simulation reduction allows us to verify timed automata with large clock upper bounds and to converge faster to the fixpoint. The presented approach is applied to reachability and LTL verification for real-time systems. Finally, we compare our approach with existing tools such as Rabbit, Uppaal, and CTAV and show that our approach outperforms them and achieves a significant speedup.