Bounded Model Checking for Hyperproperties
This addresses the verification of complex system properties like security and concurrency for researchers and practitioners in formal methods, representing a novel extension rather than an incremental improvement.
The paper tackles the problem of verifying hyperproperties, which relate multiple computation traces, by introducing the first bounded model checking algorithm for HyperLTL, reducing it to QBF solving and implementing it in a tool called HyperQube, with successful and efficient model checking reported on various case studies including security and concurrency.
Hyperproperties are properties of systems that relate multiple computation traces, including security and concurrency properties. This paper introduces a bounded model checking (BMC) algorithm for hyperproperties expressed in HyperLTL, which - to the best of our knowledge - is the first such algorithm. Just as the classic BMC technique for LTL primarily aims at finding bugs, our approach also targets identifying counterexamples. BMC for LTL is reduced to SAT solving, because LTL describes a property via inspecting individual traces. HyperLTL allows explicit and simultaneous quantification over traces and describes properties that involves multiple traces and, hence, our BMC approach naturally reduces to QBF solving. We report on successful and efficient model checking, implemented in a tool called HyperQube, of a rich set of experiments on a variety of case studies, including security, concurrent data structures, path planning for robots, and testing.