ABSTRACT
Traditionally, we protect data using policies, such as access control policies and sanitization-based policies. However, current mechanisms for enforcing these policies do not operate over data that takes the form of a directed graph (Braun et al., 2008). Additionally, users can infer sensitive information from the results returned by performing frequent queries over a provenance graph. We are particularly interested in any conclusion formed from premises where the conclusion is formed without any expressed or prior approval from anyone or any organization that controls or processes the premises or information from which the conclusion is formed. We also refer to the process of forming these conclusions from the premises as inference. When the information inferred is something unauthorized for the user to see, we say that we have an instance of the inference problem. This problem is always present in systems that contain both public and private information. The inferred knowledge could depend on data obtained from a knowledge base, or it could depend on some prior knowledge possessed by the user in addition to the information obtained from the knowledge base (Thuraisingham et al., 1993).
