Unifying theories distil common features of programming languages and design methods by means of algebraic operators and their laws. Several practical concerns---e.g., improvement of a program, conformance of code with design, correctness with respect to specified requirements---are subsumed by the beautiful notion that programs and designs are special forms of specification and their relationships are instances of logical implication between specifications. Mathematical development of this idea has been very successful but limited to an impoverished notion of specification: trace properties. Some mathematically precise properties of programs---dubbed hyperproperties---refer to traces collectively. For example, confidentiality involves knowledge of possible traces. This article reports on both obvious and surprising results about lifting algebras of programming to hyperproperties, especially in connection with loops, and suggests directions for further research. The main results are: the first compositional semantics of imperative programs with loops, at the hyper level, and a proof that this semantics is the same as the direct image of a standard semantics, for subset closed hyperproperties.
Non-compositionality for sequence and conditional seems difficult to reconcile with proofs by induction on program structure. It also results in anomalies, e.g., the formulation in Assaf means that in case @math is a loop, the semantics of @math is different from the semantics of @math . The obscurity is rectified when the semantics is restricted to subset closed sets, as spelled out in detail in an unpublished note @cite_9 , confirming remarks by Pasqua and Mastroeni @cite_18 elaborated in @cite_29 and in the thesis of Pasqua.
@cite_9 @cite_29 @cite_18
2889050595 2734853177
Hyperproperties are quickly becoming very popular in the context of systems security, due to their expressive power. They differ from classic trace properties since they are represented by sets of sets of executions instead of sets of executions. This allows us, for instance, to capture information flow security specifications, which cannot be expressed as trace properties, namely as predicates over single executions. In this work, we reason about how it is possible to move standard abstract interpretation-based static analysis methods, designed for trace properties, towards the verification of hyperproperties. In particular, we focus on the verification of bounded subset-closed hyperproperties which are easier to verify than generic hyperproperties. It turns out that a lot of interesting specifications (e.g., Non-Interference) lie in this category. Hyperproperties are becoming the, de facto, standard for reasoning about systems executions. They differ from classical trace properties since they are represented by sets of sets of executions instead of sets of executions. In this paper, we extend and lift the hierarchy of semantics developed in 2002 by P. Cousot in order to cope with verification of hyperproperties. In the standard hierarchy, semantics at different levels of abstraction are related with each other by abstract interpretation. In the same spirit, we propose an hyperhierarchy of semantics adding a new, more concrete, hyper level. The semantics defined at this hyper level are suitable for hyperproperties verification. Furthermore, all the semantics in the hyperhierarchy (the standard and the hyper ones) are still related by abstract interpretation.