FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
On Generating A Variety of Unsafe Counterexamples for Linear Dynamical Systems

Authors: Manish Goyal and Parasara Sridhar Duggirala

Paper Information

Title:On Generating A Variety of Unsafe Counterexamples for Linear Dynamical Systems
Authors:Manish Goyal and Parasara Sridhar Duggirala
Proceedings:ADHS Full papers
Editor: Alessandro Abate
Keywords:aaa, bbb, ccc
Abstract:

ABSTRACT. Counterexamples encountered in formal verification are typically used as evidence for violation of specification. They also play a crucial role in CEGAR based techniques, where the counterexample guides the refinements to be performed on the abstractions. While several scalable techniques for verification have been developed for safety verification of hybrid systems, less attention has been paid to extracting the various types of counterexamples for safety violations. Since these systems are infinite state systems, the number of counterexamples for safety violations are potentially infinite and hence searching for the right counterexample becomes a challenging task. In this paper, we present a technique for providing various types of counterexamples for a safety violation of the linear dynamical system. More specifically, we develop algorithms to extract the longest counterexample — the execution that stays in the unsafe set for most time, and deepest counterexample — the execution that ventures the most into the unsafe set in a specific direction provided by the user.

Pages:6
Talk:Jul 12 11:15 (Session 73A: Reachability and safety analysis)
Paper: