Specification and counterexample generation for cyber-physical systems

Cyber-Physical Systems (CPS) are complex systems that integrate information control devices with physical resources, which can be automatically and formalized verified by model checking according to the expected requirements in the formal specification. The counterexamples in model checking are witnesses to the violation of the specification properties of the system and can provide important diagnostic information for debugging, controlling, and synthesizing CPS. Designing a rational specification language for CPS and generating effective counterexamples allows security vulnerabilities to be detected and addressed early in the system development. However, CPS involve frequent interactions between cyber and physical systems and often operate in unreliable environments, which poses new challenges for comprehensive modeling and designing specification languages for CPSs with discrete, continuous, time, probabilistic, and concurrent behaviors. Moreover, finding the smallest counterexample of CPS with probabilistic behavior in the shortest possible time has been identified as a Non-Deterministic Polynomial-complete (NP-complete) problem. Although a number of heuristics have been devised to address this challenge, the accuracy and efficiency of the solved counterexamples need to be improved due to the difficulty in determining the heuristic functions. We first provide a comprehensive model for CPS by introducing the Hybrid Probabilistic Time Labeled Transition System (HPTLTS). Subsequently, we design a specification language HPTLTS Temporal Logic (HPTLTS-TL) that can describe the properties of CPS. In addition, we propose an optimization algorithm CACO-A, which combines the Ant Colony Optimization (ACO) algorithm and the A-algorithm to efficiently generate the counterexample of CPS, which is represented as the diagnostic subgraph. Finally, we discuss a typical CPS example to demonstrate the feasibility of our approach.