Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Defining Abstract Semantics for Static Dependence Analysis of Relational Database Applications

  • Conference paper
  • First Online:
Information Systems Security (ICISS 2016)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 10063))

Included in the following conference series:

  • 1118 Accesses

  • 7 Citations

Abstract

Dependence Graph provides the basis for powerful programming tools to address a large number of software engineering activities including security analysis. This paper proposes a semantics-based static dependence analysis framework for relational database applications based on the Abstract Interpretation theory. As database attributes differ from traditional imperative language variables, we define abstract semantics of database applications in relational abstract domain. This allows to identify statically various parts of database information (in abstract form) possibly used or defined by database statements, leading to a more precise dependence analysis. This way the semantics-based dependence computation improves w.r.t. its syntax-based counterpart. We prove the soundness of our proposed approach which guarantees that non-overlapping of the defined-part by one statement and the used-part by another statement in abstract domain always indicates a non-dependency in practice. Furthermore, the abstract semantics as a basis of the proposed framework makes it more powerful to solve undecidable scenario when initial database state is completely unknown.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook
USD 13.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The abstract Domain of Polyhedra Library is available in [2, 19].

References

  1. Ahuja, B.K., Jana, A., Swarnkar, A., Halder, R.: On preventing SQL injection attacks. In: Chaki, R., Cortesi, A., Saeed, K., Chaki, N. (eds.) Advanced Computing and Systems for Security. AISC, vol. 395, pp. 49–64. Springer, Heidelberg (2016). doi:10.1007/978-81-322-2650-5_4

    Chapter  Google Scholar 

  2. Bagnara, R., Hill, P.M., Zaffanella, E.: The ppl: toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems. Technical report Dipartimento di Matematica, Università di Parma, Italy (2006)

    Google Scholar 

  3. Baralis, E., Widom, J.: An algebraic approach to rule analysis in expert database systems (1994)

    Google Scholar 

  4. Chen, L., Minè, A., Cousot, P.: A sound floating-point polyhedra abstract domain. In: Proceeding of the PLS, pp. 3–18 (2008)

    Google Scholar 

  5. Cheney, J., Ahmed, A., Acar, U.A.: Provenance as dependency analysis. In: Proceeding of the ICDPL, pp. 138–152 (2007)

    Google Scholar 

  6. Chernikova, N.V.: Algorithm for discovering the set of all the solutions of a linear programming problem, vol. 8, pp. 282–293 (1968)

    Google Scholar 

  7. Cousot, P.: Web page on abstract interpretation. http://www.di.ens.fr/cousot/AI/

  8. Cousot, P., Cousot, R.: A gentle introduction to formal verification of computer systems by abstract interpretation. NATO Science Series III: Comp. and Syst. Sciences

    Google Scholar 

  9. Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: Proceeding of the POPL 1978, pp. 84–96 (1978)

    Google Scholar 

  10. Ferrante, J., Ottenstein, K.J., Warren, J.D.: The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Sys. 9(3), 319–349 (1978)

    Article  MATH  Google Scholar 

  11. Guerraoui, R., Henzinger, T.A., Singh, V.: Software transactional memory on relaxed memory models. In: Computer Aided Verification, vol. 5643, pp. 321–336 (2009)

    Google Scholar 

  12. Halder, R., Cortesi, A.: Abstract interpretation of database query languages. Comput. Lang. Syst. Struct. 38, 123–157 (2012)

    MATH  Google Scholar 

  13. Halder, R., Cortesi, A.: Abstract program slicing of database query languages. In: Proceeding of the Applied Computing, pp. 838–845. ACM (2013)

    Google Scholar 

  14. Halder, R., Jana, A., Cortesi, A.: Data leakage analysis of the hibernate query language on a propositional formulae domain. Trans. Large-Scale Data- Knowl.-Centered Syst. 23, 23–44 (2016)

    Google Scholar 

  15. Hammer, C.: Experiences with PDG-based IFC. In: Massacci, F., Wallach, D., Zannone, N. (eds.) ESSoS 2010. LNCS, vol. 5965, pp. 44–60. Springer, Heidelberg (2010). doi:10.1007/978-3-642-11747-3_4

    Chapter  Google Scholar 

  16. Horwitz, S., Reps, T., Binkley, D.: Interprocedural slicing using dependence graphs. ACM Trans. PLS 12(1), 26–60 (1990)

    Google Scholar 

  17. Jana, A., Halder, R., Chaki, N., Cortesi, A.: Policy-based slicing of hibernate query language. In: Saeed, K., Homenda, W. (eds.) CISIM 2015. LNCS, vol. 9339, pp. 267–281. Springer, Heidelberg (2015). doi:10.1007/978-3-319-24369-6_22

    Chapter  Google Scholar 

  18. Jana, A., Halder, R., Cortesi, A.: Verification of hibernate query language by abstract interpretation. In: He, X., Gao, X., Zhang, Y., Zhou, Z.-H., Liu, Z.-Y., Fu, B., Hu, F., Zhang, Z. (eds.) IScIDE 2015. LNCS, vol. 9243, pp. 116–128. Springer, Heidelberg (2015). doi:10.1007/978-3-319-23862-3_12

    Chapter  Google Scholar 

  19. Jeannet, B., Miné, A.: Apron: a library of numerical abstract domains for static analysis. In: Bouajjani, A., Maler, O. (eds.) CAV 2009. LNCS, vol. 5643, pp. 661–667. Springer, Heidelberg (2009). doi:10.1007/978-3-642-02658-4_52

    Chapter  Google Scholar 

  20. Johnson, A., Waye, L., Moore, S., Chong, S.: Exploring and enforcing security guarantees via program dependence graphs. In: Proceeding of the 36th ACM SIGPLAN Conference on PLDI, PLDI 2015, pp. 291–302. ACM (2015)

    Google Scholar 

  21. Kelner, J.A., Spielman, D.A.: A randomized polynomial-time simplex algorithm for linear programming. In: Proceeding of the Theory of Computing, pp. 51–60. ACM (2006)

    Google Scholar 

  22. Larsen, L., Harrold, M.J.: Slicing object-oriented software. In: Proceeding of the ICSE, pp. 495–505. IEEE CS (1996)

    Google Scholar 

  23. Levy, A.Y., Sagiv, Y.: Queries independent of updates. In: Proceeding of the VLDB, pp. 171–181 (1993)

    Google Scholar 

  24. Mastroeni, I., Zanardini, D.: Data dependencies and program slicing: from syntax to abstract semantics. In: Proceeding of the Partial Evaluation and Semantics-Based Program Manipulation, pp. 125–134 (2008)

    Google Scholar 

  25. Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. ACM 31(1), 114–127 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  26. Millstein, T., Levy, A., Friedman, M.: Query containment for data integration systems. In: Proceeding of the PDS, pp. 67–75. ACM (2000)

    Google Scholar 

  27. Minè, A.: The octagon abstract domain. Higher Order Symbol. Comput. 19(1), 31–100 (2006). http://www.astreeensfr/

    Article  MATH  Google Scholar 

  28. Nielson, F., Nielson, H.R., Hankin, C.: Principles of Program Analysis. Springer, Heidelberg (1999)

    Book  MATH  Google Scholar 

  29. Ottenstein, K.J., Ottenstein, L.M.: The program dependence graph in a software development environment. ACM SIGPLAN Notices 19(5), 177–184 (1984)

    Article  Google Scholar 

  30. Sabelfeld, A., Myers, A.C.: Language-based information-flow security. IEEE J. SAC 21, 2003 (2003)

    Google Scholar 

  31. Sen, S., Dutta, A., Cortesi, A., Chaki, N.: A new scale for attribute dependency in large database systems. In: Cortesi, A., Chaki, N., Saeed, K., Wierzchoń, S. (eds.) CISIM 2012. LNCS, vol. 7564, pp. 266–277. Springer, Heidelberg (2012). doi:10.1007/978-3-642-33260-9_23

    Chapter  Google Scholar 

  32. Tsahhirov, I., Laud, P.: Application of dependency graphs to security protocol analysis. In: Proceeding of the 3rd Symposium on Trustworthy Global Computing, pp. 294–311, Sophia-Antipolis, France, 5–6 Nov 2007

    Google Scholar 

  33. Willmor, D., Embury, S.M., Shao, J.: Program slicing in the presence of a database state. In: Proceeding of the IEEE ICSM, pp. 448–452 (2004)

    Google Scholar 

Download references

Acknowledgment

This work is partially supported by the ERDF - European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation - COMPETE 2020 Programme within project “POCI-01-0145-FEDER-006961”, and by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia as part of project “UID/EEA/50014/2013”.

Author information

Authors and Affiliations

  1. Indian Institute of Technology Patna, Patna, India

    Angshuman Jana & Raju Halder

  2. HASLab, INESC TEC, Braga, Portugal

    Raju Halder

Authors
  1. Angshuman Jana
    View author publications

    Search author on:PubMed Google Scholar

  2. Raju Halder
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Angshuman Jana .

Editor information

Editors and Affiliations

  1. Colorado State University, Fort Collins, Colorado, USA

    Indrajit Ray

  2. Malaviya National Institute of Technology, Jaipur, India

    Manoj Singh Gaur

  3. University of Padua, Padua, Italy

    Mauro Conti

  4. IIIT Delhi, Delhi, India

    Dheeraj Sanghi

  5. IIT Madras, Madras, India

    V. Kamakoti

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing AG

About this paper

Cite this paper

Jana, A., Halder, R. (2016). Defining Abstract Semantics for Static Dependence Analysis of Relational Database Applications. In: Ray, I., Gaur, M., Conti, M., Sanghi, D., Kamakoti, V. (eds) Information Systems Security. ICISS 2016. Lecture Notes in Computer Science(), vol 10063. Springer, Cham. https://doi.org/10.1007/978-3-319-49806-5_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-49806-5_8

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-49805-8

  • Online ISBN: 978-3-319-49806-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics