Dimiter Vladimirov Milushev

Reasoning About Hyperproperties Dimiter Vladimirov Milushev

The importance of security and reliability of software systems makes formal methods of paramount significance as they can be used to guarantee that a system satisfies a particular security policy. Hyperproperties are an abstract formalization of the security policies, however they lack a generic verification methodology. This thesis makes progress towards such a verification methodology. We first introduce the classes of holistic hyperproperties, which are difficult to reason about. To simplify the reasoning about these, we propose their related incremental variants. We also introduce a framework for reasoning about incremental and holistic hyperproperties based on a technique called coinduction. In addition, we propose a generic verification methodology for incremental hyperproperties based on representing the process of policy checking intuitively as playing a game. This also enables the use of off-the-shelf tools for verification of the respective security policies. The proposed incremental hyperproperties have not only an interesting security application, but also their own theoretical significance, as they are new, more general than the currently known coinductive predicates.