Efficient monitoring of hyperproperties using prefix trees

Hyperproperties, such as non-interference and observational determinism, relate multiple computation traces with each other and are thus not monitorable by tools that consider computations in isolation. We present the monitoring approach implemented in the latest version of \(\text {RVHyper}\), a runtime verification tool for hyperproperties. The input to the tool are specifications given in the temporal logic \(\text {HyperLTL}\), which extends linear-time temporal logic (LTL) with trace quantifiers and trace variables. \(\text {RVHyper}\) processes execution traces sequentially until a violation of the specification is detected. In this case, a counterexample, in the form of a set of traces, is returned. \(\text {RVHyper}\) employs a range of optimizations: a preprocessing analysis of the specification and a procedure that minimizes the traces that need to be stored during the monitoring process. In this article, we introduce a novel trace storage technique that arranges the traces in a tree-like structure to exploit partially equal traces. We evaluate \(\text {RVHyper}\) on existing benchmarks on secure information flow control, error correcting codes, and symmetry in hardware designs. As an example application outside of security, we show how \(\text {RVHyper}\) can be used to detect spurious dependencies in hardware designs.

     

Synthesis from hyperproperties

We study the reactive synthesis problem for hyperproperties given as formulas of the temporal logic HyperLTL. Hyperproperties generalize trace properties, i.e., sets of traces, to sets of sets of traces. Typical examples are information-flow policies like noninterference, which stipulate that no sensitive data must leak into the public domain. Such properties cannot be expressed in standard linear or branching-time temporal logics like LTL, CTL, or $$\hbox {CTL}^*$$. Furthermore, HyperLTL subsumes many classical extensions of the LTL realizability problem, including realizability under incomplete information, distributed synthesis, and fault-tolerant synthesis. We show that, while the synthesis problem is undecidable for full HyperLTL, it remains decidable for the $$\exists ^*$$, $$\exists ^*\forall ^1$$, and the $${{ linear }}\;\forall ^*$$ fragments. Beyond these fragments, the synthesis problem immediately becomes undecidable. For universal HyperLTL, we present a semi-decision procedure that constructs implementations and counterexamples up to a given bound. We report encouraging experimental results obtained with a prototype implementation on example specifications with hyperproperties like symmetric responses, secrecy, and information flow.     

The first reactive synthesis competition (SYNTCOMP 2014)

International Journal on Software Tools for Technology Transfer - We introduce the reactive synthesis competition (SYNTCOMP), a long-term effort intended to stimulate and guide advances in the...