Consistency and repair for XML write-access control policies | The VLDB Journal Skip to main content
Springer Nature Link
Log in

Consistency and repair for XML write-access control policies

  • Regular Paper
  • Published:
The VLDB Journal Aims and scope Submit manuscript

Abstract

XML access control policies involving updates may contain security flaws, here called inconsistencies, in which a forbidden operation may be simulated by performing a sequence of allowed operations. This article investigates the problem of deciding whether a policy is consistent, and if not, how its inconsistencies can be repaired. We consider total and partial policies expressed in terms of annotated schemas defining which operations are allowed or denied for the XML trees that are instances of the schema. We show that consistency is decidable in PTIME for such policies and that consistent partial policies can be extended to unique least-privilege consistent total policies. We also consider repair problems based on deleting privileges to restore consistency, show that finding minimal repairs is NP-complete, and give heuristics for finding repairs. Finally, we experimentally evaluate these algorithms in comparison with an exact approach based on answer-set programming.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Arenas, M., Bertossi, L., Chomicki, J.: Consistent Query Answers in Inconsistent Databases, pp. 68–79. PODS, ACM Press, London (1999)

  2. Bertossi L., Bravo L., Franconi E., Lopatenko A.: The complexity and approximation of fixing numerical attributes in databases under integrity constraints. Inf. Syst. 33, 407–434 (2008)

    Article  Google Scholar 

  3. Bex G.J., Neven F., Schwentick T., Vansummeren S.: Inference of concise regular expressions and DTDs. ACM Trans. Database Syst. 35, 11:1–11:47 (2010)

    Article  Google Scholar 

  4. Boneva, I., Caron, A.C., Groz, B., Roos, Y., Tison, S., Staworko, S.: View Update Translation for XML. In: ICDT, pp 42–53 (2011)

  5. Bravo, L., Cheney, J., Fundulaki, I.: Repairing Inconsistent XML Write-access Control Policies. DBPL, no. 4797 in LNCS, pp. 98–112. Springer, Vienna (2007)

  6. Bravo, L., Cheney, J., Fundulaki, I.: ACCOn: Checking Consistency of XML Write-access Control Policies. EDBT (demonstration), pp. 715–719 (2008)

  7. Cautis B., Abiteboul S., Milo T.: Reasoning about XML update constraints. J. Comput. Syst. Sci. 75(6), 336–358 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chvatal V.: A Greedy Heuristic for the set covering problem. Math. Oper. Res. 4, 233–235 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  9. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms. MIT Press/McGraw-Hill, Cambridge (2001)

    MATH  Google Scholar 

  10. De Capitani di Vimercati, S., Foresti, S., Paraboschi, S., Samarati, P.: Access control models for XML. In: Gertz, M., Jajodia, S. (eds.) Handbook of Database Security, pp. 27–53. Springer, USA (2008)

  11. Fan, W., Chan, C.Y., Garofalakis, M.: Secure XML Querying with Security Views, pp. 587–598. ACM SIGMOD, London (2004)

  12. Floyd R.: Algorithm 97: Shortest path. Commun. ACM 5(6), 345 (1962)

    Article  Google Scholar 

  13. Fundulaki, I., Maneth, S.: Formalizing XML Access Control for Update Operations. SACMAT, pp. 169–174. ACM, London (2007)

  14. Harmar, A., Hills, R., Rosser, E., Jones, M., Buneman, O., Dunbar, D., Greenhill, S., Hale, V., Sharman, J., et al: IUPHAR-DB: the IUPHAR database of G protein-coupled receptors and ion channels. Nucleic Acids Res 37:D680–D685 (2009)

    Google Scholar 

  15. Jacquemard, F., Rusinowitch, M.: Rewrite-based Verification of XML Updates. PPDP, pp. 119–130. ACM, London (2010)

  16. Jiang M., Fu A.W.C: Integration and efficient lookup of compressed XML accessibility maps. IEEE Trans. Knowl. Data Eng. 17(7), 939–953 (2005)

    Article  Google Scholar 

  17. Koromilas, L., Chinis, G., Fundulaki, I., Ioannidis, S.: Controlling access to XML documents over XML native and relational databases. In: Secure Data Management, Lecture Notes in Computer Science, vol 5776, pp. 122–141. Springer, Berlin (2009)

  18. Kuper, G., Massacci, F., Rassadko, N.: Generalized XML Security Views. SACMAT, pp. 77–84. ACM, London (2005)

  19. Leone N., Pfeifer G., Faber W., Eiter T., Gottlob G., Koch C., Mateis C., Perri S., Scarcello F.: The DLV system for knowledge representation and reasoning. ACM Trans. Comp. Logic 7(3), 499–562 (2006)

    Article  Google Scholar 

  20. Lim, C.H., Park, S., Son, S.H.: Access control of XML documents considering update operations. In: ACM Workshop on XML Security pp. 49–59 (2003)

  21. Luo B., Lee D., Lee W.C., Liu P.: QFilter: rewriting insecure XML queries to secure ones using nondeterministic finite automata. VLDB J. 20, 397–415 (2011)

    Article  Google Scholar 

  22. Martens W., Neven F., Schwentick T., Bex G.J.: Expressiveness and complexity of XML schema. ACM Trans. Database Syst. 31(3), 770–813 (2006)

    Article  Google Scholar 

  23. Moore N.: Computational complexity of the problem of tree generation under fine-grained access control policies. Inf. Comput. 209(3), 548–567 (2011)

    Article  MATH  Google Scholar 

  24. Murata M., Tozawa A., Kudo M., Hada S.: XML access control using static analysis. ACM TISSEC 9(3), 290–331 (2006)

    Article  Google Scholar 

  25. Papadimitriou C.: Computational Complexity. Addison- Wesley, Reading (1994)

    MATH  Google Scholar 

  26. Robie, J., Chamberlin, D., Dyck, M., Florescu, D., Melton, J., Simeon, J.: XQuery Update Facility 1.0. http://www.w3.org/TR/xquery-update-10/, W3C Recommendation (2011)

  27. Saltzer J., Schroeder M.: The protection of information in computer systems. Proc. IEEE 63(9), 1278–1308 (1975)

    Article  Google Scholar 

  28. Schmidt, A., Waas, F., Kersten, M., Carey, M.J., Manolescu, I., Busse, R.: XMark: A Benchmark for XML Data Management. VLDB, pp. 974–985 (2002)

  29. Stoica, A., Farkas, C.: Secure XML Views. In: IFIP WG 11.3, vol. 256. Kluwer, Dordrecht (2002)

  30. Yannakakis, M.: Node-and Edge-deletion NP-complete Problems. STOC, pp 253–264. ACM Press, New york (1978)

  31. Yannakakis M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297–309 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  32. Yu T., Srivastava D., Lakshmanan L.V.S., Jagadish H.V.: A compressed accessibility map for XML. ACM Trans. Database Syst. 29(2), 363–402 (2004)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universidad de Concepción, Concepción, Chile

    Loreto Bravo & Ricardo Segovia

  2. University of Edinburgh, Edinburgh, UK

    James Cheney

  3. ICS-FORTH, Crete, Greece

    Irini Fundulaki

Authors
  1. Loreto Bravo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. James Cheney
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Irini Fundulaki
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ricardo Segovia
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Loreto Bravo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bravo, L., Cheney, J., Fundulaki, I. et al. Consistency and repair for XML write-access control policies. The VLDB Journal 21, 843–867 (2012). https://doi.org/10.1007/s00778-012-0273-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00778-012-0273-y

Keywords

Search

Navigation