A shallow embedding of HyperCTL*

Markus N. Rabe, Peter Lammich, and Andrei Popescu

We formalize HyperCTL*, a temporal logic for expressing security properties. We first define a shallow embedding of HyperCTL*, within which we prove inductive and coinductive rules for the operators. Then we show that a HyperCTL* formula captures Goguen-Meseguer noninterference, a landmark information flow property. We also define a deep embedding and connect it to the shallow embedding by a denotational semantics, for which we prove sanity w.r.t. dependence on the free variables. Finally, we show that under some finiteness assumptions about the model, noninterference is given by a (finitary) syntactic formula.

Archive of Formal Proofs (AFP).

BSD Licence. The file and the proof script can be found here

(pdf) (bib)