Skip to main content
Erschienen in:
Buchtitelbild

2017 | OriginalPaper | Buchkapitel

Exact Detection of Information Leakage: Decidability and Complexity

verfasst von : Rada Chirkova, Ting Yu

Erschienen in: Transactions on Large-Scale Data- and Knowledge-Centered Systems XXXII

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Elaborate security policies often require organizations to restrict user data access in a fine-grained manner, instead of traditional table- or column-level access control. Not surprisingly, managing fine-grained access control in software is rather challenging. In particular, if access is not configured carefully, information leakage may happen: Users may infer sensitive information through the data explicitly accessible to them.
In this paper we formalize this information-leakage problem, by modeling sensitive information as answers to “secret queries,” and by modeling access-control rules as views. We focus on the scenario where sensitive information can be deterministically derived by adversaries. We review a natural data-exchange based inference model for detecting information leakage, and show its capabilities and limitation. We then introduce and formally study a new inference model, view-verified data exchange, that overcomes the limitation for the query language under consideration. Our formal study provides correctness and complexity results for the proposed inference model in the context of queries belonging to a frequent realistic query type and common types of integrity constraints on the data.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Weakly acyclic dependencies [7] are sets of tuple- and equality-generating integrity constraints (tgds and egds, respectively) that commonly occur in practice and have nice formal properties.
 
2
The intuition is that tuple patterns occuring over S constrain tuple patterns over T.
 
3
We omit from \(\varSigma ^{(\mathcal{M}\varSigma )}\) the dependencies, of the form \(\phi ({\bar{X}},{\bar{Y}}) \rightarrow true\), for the case where \(k_V = 0\) and MV[V] \(\ne \) \(\emptyset \). By the results in this section, adding these dependencies to \(\varSigma ^{(\mathcal{M}\varSigma )}\) would not change any chase results.
 
4
Besides the egds and tgds of Sect. 3.1, chase on each path in \(\mathcal T\) may use MV-induced implication constraints. However, the only role of the latter constraints is to obtain the instance \(\epsilon \) and thus to terminate the respective path in \(\mathcal T\).
 
5
It is easy to verify that if a homomorphism \(\mu \) specified by (i)-(ii) does not exist, then \(\bar{t}\) cannot be a certain answer to Q w.r.t. \(\mathcal{M}\varSigma \).
 
Literatur
1.
Zurück zum Zitat Abiteboul, S., Duschka, O.: Complexity of answering queries using materialized views. In: Proceedings of ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 254–263 (1998) Abiteboul, S., Duschka, O.: Complexity of answering queries using materialized views. In: Proceedings of ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 254–263 (1998)
2.
Zurück zum Zitat Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)MATH Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)MATH
3.
Zurück zum Zitat Agrawal, R., Bayardo Jr., R.J., Faloutsos, C., Kiernan, J., Rantzau, R., Srikant, R.: Auditing compliance with a hippocratic database. In: Proceedings of Very Large Data Bases (VLDB) Conference, pp. 516–527 (2004) Agrawal, R., Bayardo Jr., R.J., Faloutsos, C., Kiernan, J., Rantzau, R., Srikant, R.: Auditing compliance with a hippocratic database. In: Proceedings of Very Large Data Bases (VLDB) Conference, pp. 516–527 (2004)
4.
Zurück zum Zitat Alborzi, F., Chirkova, R., Yu, T.: Exact detection of information leakage in database access control. In: Madria, S., Hara, T. (eds.) DaWaK 2015. LNCS, vol. 9263, pp. 403–415. Springer, Cham (2015). doi:10.1007/978-3-319-22729-0_31 CrossRef Alborzi, F., Chirkova, R., Yu, T.: Exact detection of information leakage in database access control. In: Madria, S., Hara, T. (eds.) DaWaK 2015. LNCS, vol. 9263, pp. 403–415. Springer, Cham (2015). doi:10.​1007/​978-3-319-22729-0_​31 CrossRef
5.
Zurück zum Zitat Al-Shaer, E., Hamed, H., Boutaba, R., Hasan, M.: Conflict classification and analysis of distributed firewall policies. IEEE J. Sel. Areas Commun. 23(10), 2069–2084 (2005)CrossRef Al-Shaer, E., Hamed, H., Boutaba, R., Hasan, M.: Conflict classification and analysis of distributed firewall policies. IEEE J. Sel. Areas Commun. 23(10), 2069–2084 (2005)CrossRef
6.
Zurück zum Zitat Ammann, P., Sandhu, R.S.: Safety analysis for the extended schematic protection model. In: Proceedings of IEEE Symposium on Security and Privacy, pp. 87–97 (1991) Ammann, P., Sandhu, R.S.: Safety analysis for the extended schematic protection model. In: Proceedings of IEEE Symposium on Security and Privacy, pp. 87–97 (1991)
7.
Zurück zum Zitat Barcelo, P.: Logical foundations of relational data exchange. SIGMOD Rec. 38(1), 49–58 (2009)CrossRef Barcelo, P.: Logical foundations of relational data exchange. SIGMOD Rec. 38(1), 49–58 (2009)CrossRef
8.
Zurück zum Zitat Bertino, E., Ghinita, G., Kamra, A.: Access control for databases: concepts and systems. Found. Trends Databases 3(1–2), 1–148 (2011)MATH Bertino, E., Ghinita, G., Kamra, A.: Access control for databases: concepts and systems. Found. Trends Databases 3(1–2), 1–148 (2011)MATH
9.
Zurück zum Zitat Biskup, J., Bonatti, P.A.: Controlled query evaluation for known policies by combining lying and refusal. Ann. Math. Artif. Intell. 40(1–2), 37–62 (2004)MathSciNetCrossRefMATH Biskup, J., Bonatti, P.A.: Controlled query evaluation for known policies by combining lying and refusal. Ann. Math. Artif. Intell. 40(1–2), 37–62 (2004)MathSciNetCrossRefMATH
10.
Zurück zum Zitat Bond, R., See, K.Y.-K., Wong, C.K.M., Chan, Y.-K.H.: Understanding DB2 9 Security. IBM Press, Indianapolis (2006) Bond, R., See, K.Y.-K., Wong, C.K.M., Chan, Y.-K.H.: Understanding DB2 9 Security. IBM Press, Indianapolis (2006)
11.
Zurück zum Zitat Brodsky, A., Farkas, C., Jajodia, S.: Secure databases: constraints, inference channels, and monitoring disclosures. IEEE Trans. Knowl. Data Eng. 12(6), 900–919 (2000)CrossRef Brodsky, A., Farkas, C., Jajodia, S.: Secure databases: constraints, inference channels, and monitoring disclosures. IEEE Trans. Knowl. Data Eng. 12(6), 900–919 (2000)CrossRef
12.
Zurück zum Zitat Chandra, A., Merlin, P.: Optimal implementation of conjunctive queries in relational data bases. In: Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC), pp. 77–90 (1977) Chandra, A., Merlin, P.: Optimal implementation of conjunctive queries in relational data bases. In: Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC), pp. 77–90 (1977)
13.
Zurück zum Zitat Chen, B.-C., Kifer, D., LeFevre, K., Machanavajjhala, A.: Privacy-preserving data publishing. Found. Trends Databases 2(1–2), 1–167 (2009)CrossRef Chen, B.-C., Kifer, D., LeFevre, K., Machanavajjhala, A.: Privacy-preserving data publishing. Found. Trends Databases 2(1–2), 1–167 (2009)CrossRef
14.
Zurück zum Zitat Deutsch, A.: XML query reformulation over mixed and redundant storage. Ph.D. thesis, University of Pennsylvania (2002) Deutsch, A.: XML query reformulation over mixed and redundant storage. Ph.D. thesis, University of Pennsylvania (2002)
15.
Zurück zum Zitat Deutsch, A., Nash, A., Remmel, J.: The chase revisited. In: Proceedings of ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 149–158 (2008) Deutsch, A., Nash, A., Remmel, J.: The chase revisited. In: Proceedings of ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 149–158 (2008)
16.
Zurück zum Zitat Deutsch, A., Tannen, V.: Optimization properties for classes of conjunctive regular path queries. In: Ghelli, G., Grahne, G. (eds.) DBPL 2001. LNCS, vol. 2397, pp. 21–39. Springer, Heidelberg (2002). doi:10.1007/3-540-46093-4_2 CrossRef Deutsch, A., Tannen, V.: Optimization properties for classes of conjunctive regular path queries. In: Ghelli, G., Grahne, G. (eds.) DBPL 2001. LNCS, vol. 2397, pp. 21–39. Springer, Heidelberg (2002). doi:10.​1007/​3-540-46093-4_​2 CrossRef
17.
Zurück zum Zitat Domingo-Ferrer, J.: Inference Control in Statistical Databases: From Theory to Practice. Springer, Heidelberg (2002)CrossRefMATH Domingo-Ferrer, J.: Inference Control in Statistical Databases: From Theory to Practice. Springer, Heidelberg (2002)CrossRefMATH
18.
Zurück zum Zitat Fagin, R., Kolaitis, P., Miller, R., Popa, L.: Data exchange: semantics and query answering. Theor. Comput. Sci. 336(1), 89–124 (2005)MathSciNetCrossRefMATH Fagin, R., Kolaitis, P., Miller, R., Popa, L.: Data exchange: semantics and query answering. Theor. Comput. Sci. 336(1), 89–124 (2005)MathSciNetCrossRefMATH
19.
Zurück zum Zitat Fuxman, A., Kolaitis, P.G., Miller, R.J., Tan, W.-C.: Peer data exchange. ACM Trans. Database Syst. 31(4), 1454–1498 (2006)CrossRef Fuxman, A., Kolaitis, P.G., Miller, R.J., Tan, W.-C.: Peer data exchange. ACM Trans. Database Syst. 31(4), 1454–1498 (2006)CrossRef
20.
Zurück zum Zitat Harrison, M.A., Ruzzo, W.L., Ullman, J.D.: Protection in operating systems. Commun. ACM 19, 461–471 (1976)CrossRefMATH Harrison, M.A., Ruzzo, W.L., Ullman, J.D.: Protection in operating systems. Commun. ACM 19, 461–471 (1976)CrossRefMATH
21.
Zurück zum Zitat Kabra, G., Ramamurthy, R., Sudarshan, S.: Redundancy and information leakage in finite-grained access control. In: Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 133–144 (2006) Kabra, G., Ramamurthy, R., Sudarshan, S.: Redundancy and information leakage in finite-grained access control. In: Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 133–144 (2006)
22.
Zurück zum Zitat Kaushik, R., Ramamurthy, R.: Efficient auditing for complex SQL queries. In: Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 697–708 (2011) Kaushik, R., Ramamurthy, R.: Efficient auditing for complex SQL queries. In: Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 697–708 (2011)
23.
Zurück zum Zitat Li, N., Winsborough, W.H., Mitchell, J.C.: Beyond proof-of-compliance: safety and availability analysis in trust management. In: Proceedings of IEEE Symposium on Security and Privacy, pp. 123–139 (2003) Li, N., Winsborough, W.H., Mitchell, J.C.: Beyond proof-of-compliance: safety and availability analysis in trust management. In: Proceedings of IEEE Symposium on Security and Privacy, pp. 123–139 (2003)
24.
Zurück zum Zitat Miklau, G., Suciu, D.: A formal analysis of information disclosure in data exchange. J. Comput. Syst. Sci. 73(3), 507–534 (2007)MathSciNetCrossRefMATH Miklau, G., Suciu, D.: A formal analysis of information disclosure in data exchange. J. Comput. Syst. Sci. 73(3), 507–534 (2007)MathSciNetCrossRefMATH
25.
Zurück zum Zitat Motwani, R., Nabar, S., Thomas, D.: Auditing SQL queries. In: Proceedings of IEEE International Conference on Data Engineering (ICDE), pp. 287–296 (2008) Motwani, R., Nabar, S., Thomas, D.: Auditing SQL queries. In: Proceedings of IEEE International Conference on Data Engineering (ICDE), pp. 287–296 (2008)
26.
Zurück zum Zitat The Virtual Private Database in Oracle9iR2. An Oracle White Paper (2002) The Virtual Private Database in Oracle9iR2. An Oracle White Paper (2002)
27.
Zurück zum Zitat Stoffel, K., Studer, T.: Provable data privacy. In: Andersen, K.V., Debenham, J., Wagner, R. (eds.) DEXA 2005. LNCS, vol. 3588, pp. 324–332. Springer, Heidelberg (2005). doi:10.1007/11546924_32 CrossRef Stoffel, K., Studer, T.: Provable data privacy. In: Andersen, K.V., Debenham, J., Wagner, R. (eds.) DEXA 2005. LNCS, vol. 3588, pp. 324–332. Springer, Heidelberg (2005). doi:10.​1007/​11546924_​32 CrossRef
28.
Zurück zum Zitat Zhang, X., Ozsoyoglu, M.: Implication and referential constraints: a new formal reasoning. IEEE Trans. Knowl. Data Eng. 9(6), 894–910 (1997)CrossRef Zhang, X., Ozsoyoglu, M.: Implication and referential constraints: a new formal reasoning. IEEE Trans. Knowl. Data Eng. 9(6), 894–910 (1997)CrossRef
29.
Metadaten
Titel
Exact Detection of Information Leakage: Decidability and Complexity
verfasst von
Rada Chirkova
Ting Yu
Copyright-Jahr
2017
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-55608-5_1