Tue 18 Jan 2022 15:35 - 16:05 at Salon I - Static Analysis and Hybrid Systems Chair(s): Yoni Zohar

Due to the tangling of discrete and continuous behavior and the compositional state space explosion, bounded model checking (BMC) of compositional linear hybrid automata (CLHA) is a very challenging task. In this paper, we propose a mixed semantics guided layered method to handle this problem in a divide-and-conquer manner. Specifically, we first enumerate candidate compositional paths in the discrete layer of CLHA through the classical step semantics. Then, we remove all stutter transitions in the candidate paths to cover all interleaving cases, and check the reachability of the generalized paths in the continuous level through the shallow semantics. We only handle one shallow compositional path at a time, so that the memory usage in the checking can be well controlled. Besides, we propose two optimization methods to tailor infeasible paths to further improve the efficiency of our approach. We implement these techniques into an LHA reachability checker called BACH. The experimental results show that our method outperforms state-of-the-art tools significantly in the aspects of efficiency and scalability.

Tue 18 Jan

Displayed time zone: Eastern Time (US & Canada) change

15:05 - 16:05
Static Analysis and Hybrid SystemsVMCAI at Salon I
Chair(s): Yoni Zohar Bar Ilan University
15:05
30m
Paper
Fast Three-Valued Abstract Bit-Vector ArithmeticInPerson
VMCAI
Jan Onderka Czech Technical University in Prague, Stefan Ratschan The Czech Academy of Sciences
15:35
30m
Paper
Mixed Semantics Guided Layered Bounded Reachability Analysis of Compositional Linear Hybrid AutomataRemote
VMCAI
Yuming Wu Nanjing University, Lei Bu Nanjing University, Jiawan Wang Nanjing University, Xinyue Ren Nanjing University, Wen Xiong Nanjing University, Xuandong Li Nanjing University