Approximating Non-interference and Erasure in Rewriting Logic

Non-interference is a semantic program property that assigns confidentiality levels to data objects and prevents illicit information flows to occur from high to low security levels. Erasure is a way of strengthening confidentiality by upgrading data confidentiality levels, up to the extreme of demanding the removal of secret data from the system. In this paper, we propose a certification technique for confidentiality of complete Java classes that includes non-interference and erasure policies. This technique is based on rewriting logic, which is a very general logical and semantic framework that is efficiently implemented in the high-level programming language Maude. In order to achieve a finite state transition system, we develop an abstract Java semantics which correctly approximates non-interference and erasure. The analysis produces certificates that are independently checkable, and are small enough to be used in practice. We have implemented our methodology and developed some experiments that demonstrate the feasibility of our approach.