Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2017 | OriginalPaper | Chapter

Exact Detection of Information Leakage: Decidability and Complexity

Authors : Rada Chirkova, Ting Yu

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

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
next chapter Binary Shapelet Transform for Multiclass Time Series Classification
Footnotes
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 \).
 
Literature
1.
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.
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)MATH
3.
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.
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.
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.
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.
Barcelo, P.: Logical foundations of relational data exchange. SIGMOD Rec. 38(1), 49–58 (2009)CrossRef
8.
Bertino, E., Ghinita, G., Kamra, A.: Access control for databases: concepts and systems. Found. Trends Databases 3(1–2), 1–148 (2011)MATH
9.
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.
Bond, R., See, K.Y.-K., Wong, C.K.M., Chan, Y.-K.H.: Understanding DB2 9 Security. IBM Press, Indianapolis (2006)
11.
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.
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.
Chen, B.-C., Kifer, D., LeFevre, K., Machanavajjhala, A.: Privacy-preserving data publishing. Found. Trends Databases 2(1–2), 1–167 (2009)CrossRef
14.
Deutsch, A.: XML query reformulation over mixed and redundant storage. Ph.D. thesis, University of Pennsylvania (2002)
15.
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.
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.
Domingo-Ferrer, J.: Inference Control in Statistical Databases: From Theory to Practice. Springer, Heidelberg (2002)CrossRefMATH
18.
Fagin, R., Kolaitis, P., Miller, R., Popa, L.: Data exchange: semantics and query answering. Theor. Comput. Sci. 336(1), 89–124 (2005)MathSciNetCrossRefMATH
19.
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.
Harrison, M.A., Ruzzo, W.L., Ullman, J.D.: Protection in operating systems. Commun. ACM 19, 461–471 (1976)CrossRefMATH
21.
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.
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.
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.
25.
Motwani, R., Nabar, S., Thomas, D.: Auditing SQL queries. In: Proceedings of IEEE International Conference on Data Engineering (ICDE), pp. 287–296 (2008)
26.
The Virtual Private Database in Oracle9iR2. An Oracle White Paper (2002)
27.
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.
Zhang, X., Ozsoyoglu, M.: Implication and referential constraints: a new formal reasoning. IEEE Trans. Knowl. Data Eng. 9(6), 894–910 (1997)CrossRef
29.
Metadata
Title
Exact Detection of Information Leakage: Decidability and Complexity
Authors
Rada Chirkova
Ting Yu
Copyright Year
2017
Publisher
Springer Berlin Heidelberg
Book
Transactions on Large-Scale Data- and Knowledge-Centered Systems XXXII

Print ISBN: 978-3-662-55607-8

Electronic ISBN: 978-3-662-55608-5

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-662-55608-5_1

Premium Partner

    Image Credits