A framework for inference control in incomplete logic databases

Abstract

Security in information systems aims at various, possibly conflicting goals, two of which are availablility and confidentiality. On the one hand, as much information as possible should be provided to the user. On the other hand, certain information may be confidential and must not be disclosed. In this context, inferences are a major problem: The user might combine a priori knowledge and public information gained from the answers in order to infer secret information. Controlled Query Evaluation (CQE) is a dynamic, policy-driven mechanism for the enforcement of confidentiality in information systems, namely by the distortion of certain answers, by means of either lying or refusal. CQE prevents harmful inferences, and tries to provide the best possible availability while still preserving confidentiality. In this thesis, we present a framework for Controlled Query Evaluation in incomplete logic databases. In the first part of the thesis, we consider CQE from a declarative point of view. We present three different types of confidentiality policy languages with different simplicity and expressibility – propositional potential secrets, confidentiality targets, and epistemic potential secrets – and show how they relate to each other. We also give a formal, declarative definition of the requirements for a method protecting these types of policies. As it turns out, epistemic potential secrets are the most expressive policies of the three types studied, so we concentrate on these policies in the second part of the thesis. In that second part, we show how to operationally enforce confidentiality policies based on epistemic potential secrets. We first present an abstract framework in which two parameters are left open: 1. Does the user know the elements of the confidentiality policy? 2. Do we allow only refusal, only lying, or both distortion methods? For five of the six resulting cases, we present instantiations of the framework and prove the confidentiality according to the declarative definition from the first part of the thesis. For the remaining case (combined lying and refusal under unknown policies), we show that no suitable enforcement method can be constructed using the naive heuristics. Finally, we compare the enforcement methods to those constructed for complete databases in earlier work, and we discuss the properties of our algorithms when relaxing the assumptions about the user’s computational abilities.

Security in information systems aims at various, possibly conflicting goals, two of which are availablility and confidentiality. On the one hand, as much information as possible should be provided to the user. On the other hand, certain information may be confidential and must not be disclosed. In this context, inferences are a major problem: The user might combine a priori knowledge and public information gained from the answers in order to infer secret information. Controlled Query Evaluation (CQE) is a dynamic, policy-driven mechanism for the enforcement of confidentiality in information systems, namely by the distortion of certain answers, by means of either lying or refusal. CQE prevents harmful inferences, and tries to provide the best possible availability while still preserving confidentiality. In this thesis, we present a framework for Controlled Query Evaluation in incomplete logic databases. In the first part of the thesis, we consider CQE from a declarative point of view. We present three different types of confidentiality policy languages with different simplicity and expressibility – propositional potential secrets, confidentiality targets, and epistemic potential secrets – and show how they relate to each other. We also give a formal, declarative definition of the requirements for a method protecting these types of policies. As it turns out, epistemic potential secrets are the most expressive policies of the three types studied, so we concentrate on these policies in the second part of the thesis. In that second part, we show how to operationally enforce confidentiality policies based on epistemic potential secrets. We first present an abstract framework in which two parameters are left open: 1. Does the user know the elements of the confidentiality policy? 2. Do we allow only refusal, only lying, or both distortion methods? For five of the six resulting cases, we present instantiations of the framework and prove the confidentiality according to the declarative definition from the first part of the thesis. For the remaining case (combined lying and refusal under unknown policies), we show that no suitable enforcement method can be constructed using the naive heuristics. Finally, we compare the enforcement methods to those constructed for complete databases in earlier work, and we discuss the properties of our algorithms when relaxing the assumptions about the user’s computational abilities.