Automatically `Verifying’ discrete-time complex systems through learning, abstraction and refinement

• Main Authors: WANG, Jingyi, SUN, Jun, QIN, Shengchao, JEGOUREL, Cyrille
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2018
• Subjects: Verification; model learning; abstraction refinement; Cyber-physical system; Computer Engineering; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/4760; https://ink.library.smu.edu.sg/context/sis_research/article/5763/viewcontent/1610.06371.pdf
• Institution: Singapore Management University

Precisely modeling complex systems like cyber-physical systems is challenging, which often render model-based system verification techniques like model checking infeasible. To overcome this challenge, we propose a method called LAR to automatically ‘verify’ such complex systems through a combination of learning, abstraction and refinement from a set of system log traces. We assume that log traces and sampling frequency are adequate to capture ‘enough’ behaviour of the system. Given a safety property and the concrete system log traces as input, LAR automatically learns and refines system models, and produces two kinds of outputs. One is a counterexample with a bounded probability of being spurious. The other is a probabilistic model based on which the given property is ‘verified’. The model can be viewed as a proof obligation, i.e., the property is verified if the model is correct. It can also be used for subsequent system analysis activities like runtime monitoring or model-based testing. Our method has been implemented as a self-contained software toolkit. The evaluation on multiple benchmark systems as well as a real-world water treatment system shows promising results.