# Formal Methods in Security Vassena, Nemati, Künnemann

## News

### SysV: notes on confidentiality preserving refinement

Written: 15.12.2020 10:10
Modified: 15.12.2020 10:24
Written By: Hamed Nemati

Some notes on confidentiality preserving refinement stated in the following theorem:

$\text{Theorem:&space;we&space;say}&space;\mathit{T_{impl}\&space;\mathcal{P}\!-\!refine\&space;T_{spec}}&space;\text{&space;if&space;}&space;T_{spec}&space;\lesssim&space;T_{impl}&space;\text{&space;and&space;all&space;behaviours&space;of&space;}&space;T_{impl}&space;\text{&space;are&space;possible&space;behaviours&space;of&space;}&space;T_{spec}.$

where   $T_{spec}&space;\lesssim&space;T_{impl}$  means "T_impl simulates T_spec" and it is define as follows:

$\forall&space;s_1&space;\lesssim&space;s'_1&space;\text{&space;and&space;}&space;\alpha&space;\in&space;\mathcal{P}&space;\text{&space;if&space;}&space;s_1&space;\in&space;\alpha&space;\text{&space;then&space;}&space;s'_1&space;\in&space;\alpha&space;\text{&space;and&space;for&space;all&space;}&space;s_2&space;\text{&space;and&space;}&space;a&space;\in&space;\mathbb{A}&space;\text{&space;such&space;that&space;}&space;s_1&space;\xrightarrow[]{a}&space;s_2&space;\text{&space;then&space;there&space;exists&space;}&space;s'_2&space;\text{&space;such&space;that&space;}&space;s'_1&space;\xrightarrow[]{a}&space;s'_2&space;\text{&space;and&space;}&space;s_2&space;\lesssim&space;s'_2.$

Regarding the simulation relation used in the confidentiality preserving refinement part of the lecture, please note the direction of the simulation property, that is "T_impl simulates T_spec". This is in opposite direction of the simulation property we normally use to prove the functional correctness of systems. The specific direction that we used here guarantees that all permitted behaviour of the systems (modeled by the specification) are also behaviour of the implementation model.

Moreover, to rule out the problem stated in slide 39 (slide 44 in lecture notes) we used an additional constraint (stated as "all behaviours of T_impl are possible behaviors of T_spec" in the final Theorem) to make sure that there cannot be an implementation trace for which there is no corresponding specification trace. Please note that, in the supplementary paper this constraint is denoted as  $Tr(T_{impl})&space;\subseteq&space;Tr(T_{spec})$ .

These two conditions together help us to prove the theorem above and thus conclude that implementation does not leak more secret than the specification.

In the simulation relation definition the condition "if s_1 \in \alpha then s'_1 \in \alpha" guarantees that initial states of the two transitions are related by the property \alpha