Intransitive Non-interference by Unfolding

摘要

Non-interference characterises the absence of undesired information flows in a computing system, by asking that actions with higher level of confidentiality do not cause any observable effect at the lower levels. In many concrete applications, this requirement is too strict and the abstract model is enriched with some form of downgrading, namely with the possibility of declassifying information, thus allowing for a controlled form of leakage. This paper focuses on BINI (Bisimilarity-based Intransitive non-interference), a formalisation of non-interference with downgrading in the setting of Petri nets. Generalising some previous works, we provide a caused characterisation of BINI in terms of the unfolding semantics, a true concurrent semantics of Petri nets. Building on this, we design an algorithm for checking BINI on safe Petri nets which relies on the construction of suitable complete prefixes of the unfolding. The algorithm is implemented in a prototype tool and some preliminary tests are quite encouraging as they suggest that the management of downgrading does not cause any significant performance decay.