Minimal data upgrading to prevent inference and association attacks
Steven L. Dawson, Sabrina De Capitani di Vimercati, Patrick D. Lincoln, Pierangela Samarati · 1999
Despite advances in recent years in the area of mandatory access control in database systems, today's information repositories remain vulnerable to inference and data association attacks that can result in serious information leakage.Such information leakage can be prevented by properly classifying information according to constraints that express relationships among the security levels of data objects.In this paper we address the problem of classifying information by enforcing explicit data classification as well as inference and association constraints.We formulate the problem of determining a classification that ensures satisfaction of the constraints, while at the same time guaranteeing that information will not be unnecessarily overclassified.We present an approach to the s;olution of this problem and give an algorithm implementing it which is linear in simple cases, and low-order polynomial (n") in the general case.We also analyze a variant of the problem that is NP-hard. IntroductionMandatory policies control access to information on the basis of classifications, taken from a partially ordered set, assigned to data objects and subjects requesting access to them.Classifications assigned to information reflect the sensitivity of that information, while classifications assigned to subjects reflect their trustworthiness not to disclose the information they access to subjects not cleared to see it.By controlling read and write operations accordingly -allowing subjects to read information whose classification is dominated by their level #and write information only at a level that dominates theirs -mandatory policies provide a sim-