Skip to main content
SpringerLink
Log in

Static Analysis of String Values

  • Conference paper
Formal Methods and Software Engineering (ICFEM 2011)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 6991))

Included in the following conference series:

Abstract

In this paper we propose a unifying approach for the static analysis of string values based on abstract interpretation, and we present several abstract domains that track different types of information. In this way, the analysis can be tuned at different levels of precision and efficiency, and it can address specific properties.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as 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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Christensen, A., Moller, A., Schwartzbach, M.: Precise analysis of string expressions. In: Cousot, R. (ed.) SAS 2003. LNCS, vol. 2694, pp. 1–18. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  2. Cortesi, A., Zanioli, M.: Widening and narrowing operators for abstract interpretation. Computer Languages, Systems and Structures 37(1), 24–42 (2011)

    Article  MATH  Google Scholar 

  3. Costantini, G.: Abstract domains for static analysis of strings. Master’s thesis, Ca’ Foscari University of Venice (2010)

    Google Scholar 

  4. Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: POPL 1977. ACM, New York (1977)

    Google Scholar 

  5. Cousot, P., Cousot, R.: Systematic design of program analysis frameworks. In: POPL 1979. ACM, New York (1979)

    Google Scholar 

  6. Cousot, P., Cousot, R., Feret, J., Mauborgne, L., Miné, A., Monniaux, D., Rival, X.: The ASTREÉ analyzer. In: Sagiv, M. (ed.) ESOP 2005. LNCS, vol. 3444, pp. 21–30. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  7. Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: Proceedings of POPL 1978. ACM Press, New York (1978)

    Google Scholar 

  8. Doh, K., Kim, H., Schmidt, D.: Abstract parsing: Static analysis of dynamically generated string output using LR-parsing technology. In: Palsberg, J., Su, Z. (eds.) SAS 2009. LNCS, vol. 5673, pp. 256–272. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  9. Ferrara, P.: Static type analysis of pattern matching by abstract interpretation. In: Hatcliff, J., Zucca, E. (eds.) FMOODS 2010. LNCS, vol. 6117, pp. 186–200. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  10. Gould, C., Su, Z., Devanbu, P.: Static checking of dynamically generated queries in database applications. In: Proceedings of ICSE 2004, pp. 645–654. IEEE Computer Society, Los Alamitos (2004)

    Google Scholar 

  11. Granger, P.: Static analysis of linear congruence equalities among variables of a program. In: Abramsky, S. (ed.) CAAP 1991 and TAPSOFT 1991. LNCS, vol. 493, pp. 169–192. Springer, Heidelberg (1991)

    Google Scholar 

  12. Gulwani, S.: Automating string processing in spreadsheets using input-output examples. In: Proceedings of POPL 2011. ACM, New York (2011)

    Google Scholar 

  13. Hooimeijer, P., Veanes, M.: An evaluation of automata algorithms for string analysis. In: Jhala, R., Schmidt, D. (eds.) VMCAI 2011. LNCS, vol. 6538, pp. 248–262. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  14. Hosoya, H., Pierce, B.: Xduce: A statically typed xml processing language. ACM Trans. Internet Technol. 3(2), 117–148 (2003)

    Article  Google Scholar 

  15. Janssens, G., Bruynooghe, M.: Deriving description of possible values of program variables by means of abstract interpretation. Journal of Logic Programming 13(2-3), 205–258 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  16. Kim, S.-W., Choe, K.-M.: String analysis as an abstract interpretation. In: Jhala, R., Schmidt, D. (eds.) VMCAI 2011. LNCS, vol. 6538, pp. 294–308. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  17. Logozzo, F., Fähndrich, M.: Pentagons: A weakly relational domain for the efficient validation of array accesses. In: Proceedings of SAC 2008. ACM Press, New York (2008)

    Google Scholar 

  18. Minamide, Y.: Static approximation of dynamically generated web pages. In: Proceedings of WWW 2005, pp. 432–441. ACM, New York (2005)

    Google Scholar 

  19. Miné, A.: The octagon abstract domain. Higher-Order and Symbolic Computation (2006)

    Google Scholar 

  20. Halder, R., Cortesi, A.: Obfuscation-based analysis of sql injection attacks. In: IEEE (ed.) Proceedings of ISCC 2010 (2010)

    Google Scholar 

  21. Tabuchi, N., Sumii, E., Yonezawa, A.: Regular expression types for strings in a text processing language. Electr. Notes Theor. Comput. Sci. 75 (2002)

    Google Scholar 

  22. Thiemann, P.: Grammar-based analysis of string expressions. In: Proceedings of TLDI 2005, pp. 59–70. ACM, New York (2005)

    Google Scholar 

  23. van Hentenryck, P., Cortesi, A., Le Charlier, B.: Type analysis of prolog using type graphs. Journal of Logic Programming 22(3), 179–208 (1995)

    Article  MATH  Google Scholar 

  24. Yu, F., Bultan, T., Cova, M., Ibarra, O.: Symbolic string verification: An automata-based approach. In: Havelund, K., Majumdar, R. (eds.) SPIN 2008. LNCS, vol. 5156, pp. 306–324. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University Ca’ Foscari of Venice, Italy

    Giulia Costantini & Agostino Cortesi

  2. ETH Zurich, Switzerland

    Pietro Ferrara

Authors
  1. Giulia Costantini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pietro Ferrara
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Agostino Cortesi
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Computing, Teesside University, UK

    Shengchao Qin

  2. LMAM and Department of Informatics, School of Mathematical Sciences,, Peking University, China

    Zongyan Qiu

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Costantini, G., Ferrara, P., Cortesi, A. (2011). Static Analysis of String Values. In: Qin, S., Qiu, Z. (eds) Formal Methods and Software Engineering. ICFEM 2011. Lecture Notes in Computer Science, vol 6991. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24559-6_34

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-24559-6_34

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-24558-9

  • Online ISBN: 978-3-642-24559-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation