The inference problem: a survey

Abstract

Access control models protect sensitive data from unauthorized disclosure via direct accesses, however, they fail to prevent indirect accesses. Indirect data disclosure via inference channels occurs when sensitive information can be inferred from non-sensitive data and metadata. Inference channels are often low-bandwidth and complex; nevertheless, detection and removal of inference channels is necessary to guarantee data security. This paper presents a survey of the current and emerging research in data inference control and emphasizes the importance of targeting this so often overlooked problem during database security design.

References

1. Genetic information and the workplace. Technical report, Department of Labor, Department of Health and Human Services, Equal Employment Opportunity Commission Department of Justice, 1998.]]
2. D. Agrawal and C. C. Aggarwal. On the design and quantification of privacy preserving data mining algorithms. In Symposium on Principles of Database Systems, 2001.]]
3. R. Agrawal and R. Srikant. Privacy-preserving data mining. In Proc. of the ACM SIGMOD Conference on Management of Data, pages 439--450. ACM Press, May 2000.]]
4. J. G. Anderson. Clearing the way for physicians' use of clinical information systems. Communications of ACM, 40(8):83--90, August 1997.]]
5. T. Berners-Lee, J. Hendler, and O. Lassila. The semantic web. Scientific American, May 2001.]]
6. E. Bertino, M. Braun, S. Castano, E. Ferrari, and M. Mesiti. A java-based system for XML data protection, 2000.]]
7. E. Bertino, S. Castano, E. Ferrari, and M. Mesiti. Controlled access and dissemination of XML documents. In Workshop on Web Information and Data Management, pages 22--27, 1999.]]
8. J. Biskup and P. A. Bonatti. Controlled query evaluation for known policies by combining lying and refusal. In Foundations of Information and Knowledge Systems, pages 49--66, 2002.]]
9. J. Biskup and H. H. Bruggemann. The personal model of data - towards a privacy oriented information system (extended abstract). In Proc. of the Fifth International Conference of Data Engineering, February 6--10, 1989, Loas Angeles, California, USA, pages 348--355. IEEE Computer Society, 1989.]]
10. P. Bonatti, S. Kraus, and V. S. Subrahmanian. Secure agents. Technical Report CS-TR-4068, 1999.]]
11. P. A. Bonatti, S. Kraus, J. Salinas, and V. S. Subrahmanian. Data-security in heterogeneous agent systems. Lecture Notes in Computer Science, 1435, 1998.]]
12. B. Braithwaite. National health information privacy bill generates heat at SCAMC. Journal of Americal Informatic Association, 3(1):95--96, 1996.]]
13. A. Brodsky, C. Farkas, and S. Jajodia. Secure databases: Constraints, inference channels, and monitoring disclosure. IEEE Trans. Knowledge and Data Eng., 12(6):900--919, November/December 2000.]]
14. J. Broekstra, A. Kampman, and F. van Harmelen. Sesame: An architecture for storing and querying rdf data and schema information, 2001.]]
15. L. Buczkowski. Database inference controller. In D. Spooner and C. Landwehr, editors, Database Security III: Status and Prospects, pages 311--322. North-Holland, Amsterdam, 1990.]]
16. C. Clifton. Using sample size to limit exposure to data mining. Journal of Computer Security, 8(4), 2000.]]
17. C. Clifton and D. Marks. Security and privacy implications of data mining. In Workshop on Data Mining and Knowledge Discovery, number 96--08, pages 15--19, Montreal, Canada, 1996.]]
18. N. R. Council. For the record Protecting electronic health information. Technical report, National Academy of Sciences, 1997.]]
19. E. Damiani, S. D. C. di Vimercati, S. Paraboschi, and P. Samarati. Design and implementation of an access control processor for XML documents. WWW9/Computer Networks, 33(1--6):59--75, 2000.]]
20. S. Dawson, S. D. Capitano, and P. Samarati. Specification and enforcement of classification and inference constraints. In Proc. of the 20th IEEE Symposium on Security and Privacy, May 1999. Oakland.]]
21. S. Dawson, S. D. C. di Vimercati, P. Lincoln, and P. Samarati. Minimal data upgrading to prevent inference and association. In Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia, Pennsylvania, pages 114--125. ACM Press, 1999.]]
22. S. Decker, S. Melnik, F. van Harmelen, D. Fensel, M. C. A. Klein, J. Broekstra, M. Erdmann, and I. Horrocks. The semantic web: The roles of XML and RDF. IEEE Internet Computing, 4(5):63--74, 2000.]]
23. H. Delugach and T. Hinke. Wizard: A database inference analysis and detection system. IEEE Trans. on Knowledge and Data Engineering, 8(1):56--66, 1996.]]
24. G. Denker, J. R. Hobbs, D. Martin, S. Narayanan, and R. J. Waldinger. Accessing information and services on the DAML-enabled web. In SemWeb, 2001.]]
25. D. Denning. Cryptography and Data Security. Addison-Wesley, Mass., 1982.]]
26. D. Denning. Commutative filters for reducing inference threats in multilevel database systems. In Proc. IEEE Symp. on Security and Privacy, pages 134--146, 1985.]]
27. A. Deutch, M. Fernandez, D. Florescu, A. Levy, and D. Suciu. A query language for XML. In Proc. In International Conference on World Wide Web, 1999.]]
28. A. Deutsch, M. Fernandez, D. Florescu, A. Levy, and D. Suciu. A query language for XML. Computer Networks (Amsterdam, Netherlands: 1999), 31(11--16):1155--1169, 1999.]]
29. L. C. J. Dreyer and M. S. Olivier. Dynamic aspect of the infopriv model. In Proc. 9th Database and Expert Systems Applications DEXA 98, pages 340--345. IEEE Computer Society, Los Alamitos, 1998.]]
30. G. Duncan and S. Fienberg. Obtaining information while preserving privacy: a markov perturbation method for tabular data. In Statistical Data Protection, pages 351--362, 1998.]]
31. C. Farkas, S. Fenner, and M. Valtorta. Medical privacy versus data mining. In Proc. Fifth Multiconference on Systemics, Cybernetics and Informatics, pages 194--200, July 2001.]]
32. G. Gardarin and F. Sha. Using conceptual modeling and intelligent agents to integrate semi-structured documents in federated databases. Lecture Notes in Computer Science, 1565:87--99, 1999.]]
33. J. Goguen and J. Meseguer. Unwinding and inference control. In Proc. IEEE Symp. on Security and Privacy, pages 75--86, 1984.]]
34. J. Hale and S. Shenoi. Catalytic inference analysis: Detecting inference threat due to knowledge discovery. In Proc. of the 1997 IEEE Symposium on Security and Privacy, pages 188--199, May 1997. Oakland.]]
35. J. Hale, J. Threet, and S. Shenoi. A practical formalism for imprecise inference control. IFIP Trans. Computer Science And Technology, 60:139--156, 1994.]]
36. T. Hinke. Inference aggregation detection in database management systems. In Proc. IEEE Symp. on Security and Privacy, pages 96--106, 1988.]]
37. T. Hinke, H. Delugach, and R. Wolf. A framework for inference directed data mining. In Proc. 10th IFIP WG11.3 Workshop on Database Security, pages 229--239, 1996.]]
38. T. Hinke, H. S. Delugach, and R. P. Wolf. Protecting databases from inference attacks. Computers and Security, 16(8):687--708, 1997.]]
39. S. Jajodia and C. Meadows. Inference problems in multilevel secure database management systems. In M. Abrams, S. Jajodia, and H. Podell, editors, Information Security: An integrated collection of essays, pages 570--584. IEEE Computer Society Press, Los Alamitos, Calif., 1995.]]
40. A. Karr, J. Lee, A. Sanil, J. Hernandez, S. Karimi, and K. Litwin. Web-based systems that disseminate information from data but protect confidentiality. IEEE Computer, February 2001. http://www.niss.org/dg/technicalreports.html.]]
41. W. Klosgen. Knowledge discovery in databases and data privacy. In IEEE Expert, April 1995.]]
42. M. Kudo and S. Hada. XML document security based on provisional authorization. In Proc. of the 7th ACM Conference on Computer and Communication Security, November 2000.]]
43. Y. Lindell and B. Pinkas. Privacy preserving data mining. Lecture Notes in Computer Science, 1880:36--??, 2000.]]
44. T. Lunt. Current issues in statistical database security. In C. Landwehr and S. Jajodia, editors, Database Security, V: Status and Prospects, IFIP WG 11.3, pages 381--385, 1991.]]
45. D. Marks. Inference in MLS database systems. IEEE Trans. Knowledge and Data Eng., 8(1):46--55, February 1996.]]
46. S. Mazumdar, D. Stemple, and T. Sheard. Resolving the tension between integrity and security using a theorem prover. In Proc. ACM Int'l Conf. Management of Data, pages 233--242, 1988.]]
47. B. N. Meeks. Privacy lost, anytime, anywhere. In Communications of ACM, volume 40/8, pages 11--13, 1997.]]
48. M. Morgenstern. Controlling logical inference in multilevel database systems. In Proc. IEEE Symp. on Security and Privacy, pages 245--255, 1988.]]
49. U. S. G. A. Office. Medical records privacy, access needed for health research, but oversight of privacy protections is limited. Technical report, United States General Accounting Office, Report to Congressional Requesters GAO/HEHS-99-55, 1999.]]
50. D. O'Leary. Knowledge discovery as a threat to database security. In G. Piatetsky-Shapiro and W. Frawley, editors, Knowledge Discovery in Databases, pages 507--516. AAAI Press/The MIT Press, Menlo Park, California, 1991.]]
51. D. O'Leary. Some privacy issues in knowledge discovery: OECD personal privacy guidelines. In IEEE Expert, April 1995.]]
52. D. E. O'Leary. Some privacy issues in knowledge dis covery: Oecd personal privacy guidelines. IEEE Expert/Intelligent Systems and Their Applications, 10(2), April 1995.]]
53. G. Ozsoyoglu and T. Su. On inference control in semantic data models for statistical databases. Journal of Computer and System Sciences, 40(3):405--443, 1990.]]
54. Y. Papakonstantinou and V. Vianu. DTD Inference for Views of XML Data. In Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 35--46, Dallas, Texas, 2000.]]
55. G. Piatetsky-Shapiro. Knowledge discovery in databases vs. personal privacy. In IEEE Expert, April 1995.]]
56. T. C. Rindfleisch. Privacy, information technology, and health care. Communications of ACM, 40(8):93--100, August 1997.]]
57. V. Roth and M. Jalali-Sohi. Concepts and architecture of a security-centric mobile agent server. In ISADS, 2001.]]
58. A. D. Rubin, D. Geer, and M. J. Ranum. WEB Security Sourcebook. John Wiley and Sons, Inc., 1997.]]
59. P. Selfridge. Privacy and knowledge discovery in databases. In IEEE Expert, April 1995.]]
60. G. Smith. Modeling security-relevant data semantics. In Proc. IEEE Symp. Research in Security and Privacy, pages 384--391, 1990.]]
61. P. Stachour and B. Thuraisingham. Design of LDV: A multilevel secure relational database management system. IEEE Trans. Knowledge and Data Eng., 2(2):190--209. June 1990.]]
62. L. D. Stein. Web Security - A Step-by-Step Reference Guide. Addison-Wesley Longman, inc., 1998.]]
63. M. Stickel. Elimination of inference channels by optimal upgrading. In Proc. of the 1994 IEEE Symposium on Research in Security and Privacy, pages 168--174, May 1994. Oakland.]]
64. A. Stoica and C. Farkas. Secure XML views. In Proc. IFIP WG11.3 Working Conference on Database and Application Security, 2002.]]
65. T. Su and G. Ozsoyoglu. Inference in MLS database systems. IEEE Trans. Knowledge and Data Eng., 3(4):474--485, December 1991.]]
66. T. H. Hinke, H. S. Delugach, and A. Chandrasekhar. A fast algorithm for detecting second paths in database inference analysis. Jour. of Computer Security, 3(2,3):147--168, 1995.]]
67. B. Thuraisingham. Security checking in relational database management systems augmented with inference engines. Computers and Security, 6:479--492, 1987.]]
68. B. Thuraisingham. Security issues for data warehousing and data mining. In DBSec, 1996.]]
69. T. C. Ting. Privacy and confidentiality in healthcare delivery information systems. In Proc. of the 12th IEEE Symposium on Computer-Based Medical Systems, 1998.]]
70. G. Wiederhold, M. Bilello, and C. Donahue. Web implementation of a security mediator for medical databases. In T. Y. Lin and S. Qian, editors, Database Security XI Status and Prospent, pages 60--47. Chapman and Hall, 1998.]]
71. G. Wiederhold, M. Bilello, V. Sarathy, and X. L. Qian. Protecting collaboration. In Proceedings of the NISSC 1996 National Information Systems Security Conference, pages 561--569, 1996.]]
72. G. Wiederhold, M. Bilello, V. Sarathy, and X. L. Qian. A security mediator for health care information. In Proceedings of the 1996 AMIA Conference, pages 120--124, 1996.]]
73. R. Yip and K. Levitt. Data level inference detection in database systems. In Proc. of the 11th IEEE Computer Security Foundation Workshop, pages 179--189, 1998. Rockport, MA.]]