Database Inference Problem

Csilla Farkas

Alexander Brodsky

Sushil Jajodia

Tyrone Toland

Caroline Eastman

Most of the existing works on data secrecy are focused on developing mandatory and discretionary accesses control models. While these models do protect sensitive information from direct data accesses, indirect secrecy violations via inference channels may occur. The detection and removal of existing inference channels are necessary to provide secure database systems.

We study the database inference problem in multilevel secure relational, semi-structured, and numeric databases.  We also consider the effect of updates on the inference problem. 

Future extensions of the current results include the development of models addressing collaborative attacker.  Currently each user is monitored and inferences are generated only on his/her history files.  Also, I’m planning to evaluate the inference problem from the perspective of privacy and fairness.  Disclosing seemingly unimportant or non-sensitive information may give advantage to an adversary.  In particular, it may play an important role in interactive negotiation and trust management. 

Publications:

1.       C. Farkas, “The Inference Problem in Databases,” Ph.D. Dissertation, Information Technology, George Mason University, 2000. (PS file)

2.       A. Brodsky, C. Farkas, S. Jajodia, “Secure Databases: Constraints, Inference Channels and Monitoring Disclosures,” IEEE Trans. on Knowledge and Data Engineering, 12(6): 900-919, 2000.  (PDF file)

3.       C. Farkas and S. Jajodia “The Inference Problem: A Survey,” SIGKDD Explorations, 4(2): 6-11, 2002. (PDF file)

4.       C. Farkas, A. Brodsky, and S. Jajodia, “Unauthorized Inferences in Semi-Structured Databases,” original submission 2003, 2nd  revision submitted to Information Sciences in June 2005.

5.       T. S. Toland, C. Farkas, C. M. Eastman, “Database Updates and the Inference Problem,” original submission to the Data and Knowledge Engineering Journal, original submission 2004; 1st revision will be submitted in August 2005.

6.       A. Brodsky, C. Farkas, D. Wijesekera, S. X. Wang, “Constraints, Inference Channels and Secure Databases,” Proc. Sixth International Conference on Principles and Practice of Constraint Programming, 98-113, 2000. (Acceptance ratio 31 %) (PS file)

7.       C. Farkas, T. Toland, C. Eastman, “The Inference Problem and Updates in Relational Databases,” Proc. 15th IFIP WG11.3 Working Conference on Database and Application Security, 181-194, 2001. (Acceptance ratio 50%) (PDF file)

8.       Toland, C. Farkas, and C. Eastman, “Dynamic Disclosure Monitor (D2Mon): An Improved Query Processing Solution,” Accepted to the Secure Data Management Workshop, in connection with VLDB, 2005, to appear. (Acceptance ratio 50%) (PDF file)