Abstract
Malicious users can exploit the correlation among data to infer sensitive information from a series of seemingly innocuous data accesses. Thus, we develop an inference violation detection system to protect sensitive data content. Based on data dependency, database schema and semantic knowledge, we constructed a semantic inference model (SIM) that represents the possible inference channels from any attribute to the pre-assigned sensitive attributes. The SIM is then instantiated to a semantic inference graph (SIG) for query-time inference violation detection. For a single user case, when a user poses a query, the detection system will examine his/her past query log and calculate the probability of inferring sensitive information. The query request will be denied if the inference probability exceeds the pre-specified threshold. For multi-user cases, the users may share their query answers to increase the inference probability. Therefore, we develop a model to evaluate collaborative inference based on the query sequences of collaborators and their task-sensitive collaboration levels. Experimental studies reveal that information authoritativeness and communication fidelity are two key factors that affect the level of achievable collaboration. An example is given to illustrate the use of the proposed technique to prevent multiple collaborative users from deriving sensitive information via inference.
This research is supported by NSF grant number IIS-03113283.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aberer, K., Despotovic, Z.: Managing Trust in a Peer-2-Peer Information System. In: Proceedings of the tenth international conference on Information and knowledge management, Atlanta, Georgia, USA, October 05–10 (2001)
Chavira, M., Allen, D., Darwiche, A.: Exploiting Evidence in Probabilistic Inference. In: Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI), pp. 112–119 (2005)
Chan, H., Darwiche, A.: A Distance Measure for Bounding Probabilistic Belief Change. In: Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI), pp. 539–545. AAAI Press, Menlo Park (2002)
Chan, H., Darwiche, A.: When Do Numbers Really Matter? Journal of Artificial Intelligence Research 17, 265–287 (2002)
Chan, H., Darwiche, A.: Reasoning about bayesian network classifiers. In: Proceedings of the Conference on Uncertainty in Artificial Intelligence, pp. 107–115 (2003)
Chan, H., Darwiche, A.: Sensitivity analysis in Bayesian networks: From single to multiple parameters. In: Proceedings of the Twentieth Conference on Uncertainty in Artificial Intelligence (UAI), Arlington, Virginia, pp. 67–75. AUAI Press (2004)
Cornelli, F., Damiani, E., De Capitani di Vimercati, S., Paraboschi, S., Samarati, P.: Choosing reputable servents in a P2P network. In: Proceedings of the 11th international conference on World Wide Web, Honolulu, Hawaii, USA, May 07–11 (2002)
Chavira, M., Darwiche, A.: Compiling bayesian networks with local structure. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1306–1312 (2005)
Chen, Y., Chu, W.W.: Database Security Protection via Inference Detection. In: Mehrotra, S., Zeng, D.D., Chen, H., Thuraisingham, B., Wang, F.-Y. (eds.) ISI 2006. LNCS, vol. 3975. Springer, Heidelberg (2006)
Chu, W.W., Chen, Q., Hwang, A.Y.: Query Answering via Cooperative Data Inference. Journal of Intelligent Information Systems (JIIS) 3(1), 57–87 (1994)
Chu, W.W., Yang, H., Chiang, K., Minock, M., Chow, G., Larson, C.: CoBase: A Scalable and Extensible Cooperative Information System. Journal of Intelligence Information Systems (JIIS) 6 (1996)
Date, C.J.: An Introduction to Database Systems, 6th edn. Addison-Wesley, Reading (1995)
Darwiche, A.: Recursive conditioning. Arificial Intelligence 126(1-2), 5–41 (2001)
Darwiche, A.: Class notes for CS262A: Reasoning with Partial Beliefs, UCLA (2003)
Duma, C., Shahmehri, N., Caronni, G.: Dynamic trust metrics for peer-to-peer systems. In: Proceedings of the Sixteenth International Workshop on Database and Expert Systems Applications, pp. 776–781 (2005)
Dechter, R.: Bucket elimination: A unifying framework for probabilistic inference. In: Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 211–219 (1996)
Dechter, R.: Bucket elimination: A unifying framework for reasoning. Artificial Intelligence 113, 41–85 (1999)
Delugach, H.S., Hinke, T.H.: Wizard: A Database Inference Analysis and Detection System. IEEE Trans. Knowledge and Data Engeneering 8(1), 56–66 (1996)
Friedman, N., Getoor, L., Koller, D., Pfeffer, A.: Learning Probabilistic Relational Models. In: Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI), Stockholm, Sweden, August 1999, pp. 1300–1307 (1999)
Farkas, C., Jajodia, S.: The Inference Problem: A Survey. SIGKDD Explorations 4(2), 6–11 (2002)
Farkas, C., Toland, T.S., Eastman, C.M.: The Inference Problem and Updates in Relational Databases. In: Proceedings of the 15th IFIP WG11.3 Working Conference on Database and Application Security, pp. 181–194 (2001)
Garvey, T.D., Lunt, T.F., Quain, X., Stickel, M.: Toward a Tool to Detect and Eliminate Inference Problems in the Design of Multilevel Databases. In: Proceedings of the 6th Annual IFIP WG 11.3 Working Conference on Data and Applications Security (1992)
Getoor, L., Taskar, B., Koller, D.: Selectivity Estimation using Probabilistic Relational Models. In: Proceedings of the ACM SIGMOD (Special Interest Group on Management of Data) Conference (2001)
Getoor, L., Friedman, N., Koller, D., Pfeffer, A.: Learning Probabilistic Relational Models. In: Dzeroski, S., Lavrac, N. (eds.) Relational Data Mining. Springer, Heidelberg (2001)
He, J., Chu, W.W., Liu, Z.: Inferring Privacy Information From Social Networks. In: Mehrotra, S., Zeng, D.D., Chen, H., Thuraisingham, B., Wang, F.-Y. (eds.) ISI 2006. LNCS, vol. 3975. Springer, Heidelberg (2006)
Heckerman, D., Mamdani, A., Wellman, M.P.: Real-world applications of Bayesian networks. Communications of the ACM 38(3), 24–68 (1995)
Heckerman, D.: A Tutorial on Learning with Bayesian Networks. Techinical Report, Microsoft Research (1996)
Hinke, T.H., Delugach, H.S.: Aerie: An Inference Modeling and Detection Approach for Databases. In: Proceedings of the 6th Annual IFIP WG 11.3 Working Conference on Data and Applications Security (1992)
Hinke, T.H., Delugach, H.S., Wolf, R.: A Framework for Inference-Directed Data Mining. In: Proceedings of the 10th Annual IFIP WG 11.3 Working Conference on Data and Applications Security (1996)
Jensen, F.V.: An Introduction to Bayesian Networks. Springer, New York (1996)
Jensen, F.V., Lauritzen, S.L., Olesen, K.G.: Bayesian updating in recursive graphical models by local computation. Computational Statistics Quarterly 4, 269–282 (1990)
Kamvar, S.D., Schlosser, M.T., Garcia-Molina, H.: The Eigentrust algorithm for reputation management in P2P networks. In: Proceedings of the 12th international conference on World Wide Web, Budapest, Hungary, May 20–24 (2003)
Kautz, H., Selman, B., Shah, M.: The Hidden Web. AI magazine (1997)
Laskey, K.B.: Sensitivity Analysis for Probability Assessments in Bayesian Networks. IEEE Transactions on Systems, Man and Cybernetics 25, 909–909 (1995)
Lauritzen, S.L., Spiegelhalter, D.J.: Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems (with Discussion). Journal of the Royal Statistical Society, Series B 50(2), 157–224 (1988)
Lee, W., Stolfo, S.J., Chan, P.K., Eskin, E., Fan, W., Miller, M., Hershkop, S., Zhang, J.: Real Time Data Mining-based Intrusion Detection. In: Proceedings of DISCEX II (June 2001)
Marti, S., Garcia-Molina, H.: Taxonomy of trust: Categorizing P2P reputation systems. Computer Networks 50(4), 472–484 (2006)
Page, L., Brin, S.: The anatomy of a large-scale hypertextual web search engine. In: Proceedings of the Seventh International World-Wide Web Conference, Brisbane, Australia (April 1998)
Pearl, J.: Probabilistic Reasoning in Intelligence Systems. Morgan Kaufmann, San Mateo (1988)
Pearl, J.: Bayesian Networks, Causal Inference and Knowledge Discovery. UCLA Cognitive Systems Laboratory, Technical Report (R-281), March. Second Moment (March 1, 2001)
SamIam, Automated Reasoning Group, UCLA, http://reasoning.cs.ucla.edu/samiam/
Shafiq, B., Bertino, E., Ghafoor, A.: Access control management in a distributed environment supporting dynamic collaboration. In: Workshop On Digital Identity Management, Proceedings of the 2005 workshop on Digital identity management (2005)
Thuraisingham, B.M., Ford, W., Collins, M., Keeffe, J.O.: Design and Implementa-tion of a Database Inference Controller. Data Knowl. Eng. 11(3), 271 (1993)
Toland, T.S., Farkas, C., Eastman, C.M.: Dynamic Disclosure Monitor (D2Mon): An Improved Query Processing Solution. In: The Secure Data Management Workshop (2005)
Winsborough, W., Li, N.: Safety in automated trust negotiation. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 147–160 (2004)
Xiong, L., Liu, L.: Peertrust: Supporting reputation-based trust for peer-to-peer electronic communities. IEEE Transactions on Knowledge and Data Engineering 16(7), 843–857 (2004)
Yip, R.W., Levitt, K.N.: Data Level Inference Detection in Database Systems. In: PCSFW: Proceedings of the 11th Computer Security Foundations Workshop (1998)
Yu, T., Winslett, M.: A Unified Scheme for Resource Protection in Automated Trust Negotiation. In: Proceedings of the 2003 IEEE Symposium on Security and Privacy, May 11–14, 2003, p. 110 (2003)
Yu, T., Winslett, M.: Policy migration for sensitive credentials in trust negotiation. In: Proceedings of the 2003 ACM workshop on Privacy in the electronic society, Washington, DC, October 30 (2003)
Zhang, G., Chu, W.W., Meng, F., Kong, G.: Query Formulation from High-Level Concepts for Relational Databases. User Interfaces to Data Intensive Systems (UIDIS) 1999, 64–75 (1994)
Zhang, N.L., Poole, D.: Exploiting Causal Independence in Bayesian Network Inference. Journal of Artificial Intelligence Research 5, 301–328 (1996)
Zhang, N.L., Poole, D.: A simple approach to bayesian network computations. In: Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence (UAI), pp. 171–178 (1994)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Chen, Y., Chu, W.W. (2008). Protection of Database Security Via Collaborative Inference Detection. In: Chen, H., Yang, C.C. (eds) Intelligence and Security Informatics. Studies in Computational Intelligence, vol 135. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69209-6_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-69209-6_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69207-2
Online ISBN: 978-3-540-69209-6
eBook Packages: EngineeringEngineering (R0)