Many interesting program properties like determinism or information flow security are hyperproperties, that is, they relate multiple executions of the same program. Hyperproperties can be verified using relational logics, but these logics require dedicated tool support and are difficult to automate. Alternatively, constructions such as self-composition represent multiple executions of a program by one product program, thereby reducing hyperproperties of the original program to trace properties of the product. However, existing constructions do not fully support procedure specifications, for instance, to derive the determinism of a caller from the determinism of a callee, making verification non-modular. We present modular product programs, a novel kind of product program that permits hyperproperties in procedure specifications and, thus, can reason about calls modularly. We provide a general formalization of our product construction and prove it sound and complete. We demonstrate its expressiveness by applying it to information flow security with advanced features such as declassification and termination-sensitivity. Modular product programs can be verified using off-the-shelf verifiers; we have implemented our approach for both secure information flow and general hyperproperties using the Viper verification infrastructure. Our evaluation demonstrates that modular product programs can be used to prove hyperproperties for challenging examples in reasonable time. separately and using only the specifications of other procedures. Modularity is vital for scalability and to verify libraries without knowing all of their clients. Fully modular reasoning about hyperproperties thus requires the ability to formulate relational specifications, which relate different executions of a procedure, and to apply those specifications where the procedure is called. As an example, the statement if (x) then {y:=x} else {y:= call f(x)} can be proved to be deterministic if f's relational specification guarantees that its result deterministically depends on its input. Relational program logics [10, 39, 41] allow directly proving general hyperproperties. However, automating relational logics is difficult and requires building dedicated tools. Alternatively, self-composition [8] and product programs [6, 7] reduce a hyperproperty to an ordinary trace property, thus making it possible to use off-the-shelf program verifiers for proving hyperproperties. Both approaches construct a new program that combines the behaviors of multiple runs of the original program. However, by the nature of their construction, neither approach supports modular verification based on relational specifications: Procedure calls in the original program will be duplicated, which means that there is no single program point at which a relational specification can be applied. For the aforementioned example, self-composition yields the following program: if (x) then {y:=x} else {y:= call f(x)}; if (x ′ ) then {y ′ :=x ′ } else {y ′ := call f(x ′ )} Determinism can now be verified by proving the trace property that identical values for x and x ′ in the initial state imply identical values for y and y ′ in the final state. However, such a proof cannot make use of a relational specification for procedure f (expressing that f is deterministic). Such a specification relates several executions of f, whereas each call in the self-composition belongs to a single execution. Instead, verification requires a precise functional specification of f, which exactly determines its result value in terms of the input. Verifying such precise functional specifications increases the verification effort and is at odds with data abstraction (for instance, a collection might not want to promise the exact iteration order); inferring them is beyond the state of the art for most procedures [40] . Existing product programs allow aligning or combining some statements and can thereby lift this requirement in some cases, but this requires manual effort during the construction, depends on the used specifications, and does not solve the problem in general. Some techniques for proving equivalence between different programs use product constructions that enable using relational specifications between different functions. However, they cannot exploit the inherent advantages resulting from combining a program with itself as opposed to an arbitrary other program [22, 25] . In this paper, we present modular product programs, a novel kind of product programs that allows modular reasoning about hyperproperties. Modular product programs enable proving k-safety hyperproperties, i.e., hyperproperties that relate finite prefixes of k execution traces, for arbitrary values of k [12]. We achieve this via a transformation that, unlike existing products, does not duplicate loops or procedure calls, meaning that for any loop or call in the original program, there is exactly one statement in the k-product at which a relational specification can be applied. Like existing product programs, modular products can be reasoned about using off-the-shelf program verifiers. We demonstrate the expressiveness of modular product programs by applying them to prove secure information flow, which can be expressed as a 2-safety hyperproperty. We show how modular products enable proving traditional non-interference using natural and concise information flow ACM
REF propose a modular product program construction that permits hyperproperties in procedure specifications.
Modular Product Programs
ESOP
Computer Science