Digital Symposium Collection 2000

Minimal Data Upgrading to Prevent Inference and Association Steven Dawson, Sabrina De Capitani di Vimercati, Patrick Lincoln, and Pierangela Samarati   View Paper (PDF)     View Slides (HTML)   Return to Database Theory Sampler Abstract 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 solution of this problem and give an algorithm implementing it which is linear in simple cases, and low-order polynomial (n^2) in the general case. We also analyze a variant of the problem that is NP-hard. References Note: References link to DBLP on the Web. [1] Hassan Aït-Kaci , Robert S. Boyer , Patrick Lincoln , Roger Nasr : Efficient Implementation of Lattice Operations. TOPLAS 11(1) : 115-146(1989) [2] Silvana Castano , Mariagrazia Fugini , Giancarlo Martella , Pierangela Samarati : Database Security. Addison-Wesley & ACM Press 1995, ISBN 0-201-59375-0 Contents [3] Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest : Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8 and 0-07-013143-0 [4] Steven Dawson , Sabrina De Capitani di Vimercati , Pierangela Samarati : Specification and Enforcement of Classification and Inference Constraints. IEEE Symposium on Security and Privacy 1999 : 181-195 [5] ... [6] Deb Dutta Ganguly , Chilukuri K. Mohan , Sanjay Ranka : A Space-and-Time-Efficient Codeing Algorithm for Lattice Computations. TKDE 6(5) : 819-829(1994) [7] ... [8] Sushil Jajodia , Ravi S. Sandhu : Towards a Multilevel Secure Relational Data Model. SIGMOD Conference 1991 : 50-59 [9] ... [10] Teresa F. Lunt , Dorothy E. Denning , Roger R. Schell , Mark Heckman , William R. Shockley : The SeaView Security Model. TSE 16(6) : 593-607(1990) [11] Matthew Morgenstern : Security and Inference in Multilevel Database and Knowledge-Base Systems. SIGMOD Conference 1987 : 357-373 [12] Vaughan R. Pratt , Jerzy Tiuryn : Satisfiability of Inequalities in a Poset. Fundamenta Informaticae 28(1-2) : 165-182(1996) [13] ... [14] Xiaolei Qian , Teresa F. Lunt : A MAC Policy Framework for Multilevel Relational Databases. TKDE 8(1) : 3-15(1996) [15] ... [16] ... [17] Tzong-An Su , Gultekin Özsoyoglu : Controlling FD and MVD Inferences in Multilevel Relational Database Systems. TKDE 3(4) : 474-485(1991) [18] Maurizio Talamo , Paola Vocca : A Data Structure for Lattice Representation. TCS 175(2) : 373-392(1997) [19] Robert Endre Tarjan : Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2) : 146-160(1972) [20] Marianne Winslett , Kenneth Smith , Xiaolei Qian : Formal Query Languages for Secure Relational Databases. TODS 19(4) : 626-662(1994) BIBTEX @inproceedings{DBLP:conf/pods/DawsonVLS99,   author    = {Steven Dawson and                 Sabrina De Capitani di Vimercati and                 Patrick Lincoln and                 Pierangela Samarati},    title     = {Minimal Data Upgrading to Prevent Inference and Association},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {114-125},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM