Static checking of dynamically generated queries in database applications

ABSTRACT

Many data-intensive applications dynamically construct queries in response to client requests and execute them. Java servlets, for example, can create strings that represent SQL queries and then send the queries, using JDBC, to a database server for execution. The servlet programmer enjoys static checking via Java's strong type system. However, the Java type system does little to check for possible errors in the dynamically generated SQL query strings. Thus, a type error in a generated selection query (e.g., comparing a string attribute with an integer) can result in an SQL runtime exception. Currently, such defects must be rooted out through careful testing, or (worse) might be found by customers at runtime. In this article, we present a sound, static program analysis technique to verify that dynamically generated query strings do not contain type errors. We describe our analysis technique and provide soundness results for our static analysis algorithm. We also describe the details of a prototype tool based on the algorithm and present several illustrative defects found in senior software-engineering student-team projects, online tutorial examples, and a real-world purchase order system written by one of the authors.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Roberto M. Amadio , Luca Cardelli, Subtyping recursive types, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.104-118, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99600]
• 3: Andersen, L. 1994. Program analysis and specialization for the C programming language. Ph.D. thesis, DIKU, University of Copenhagen. DIKU report 94/19.
• 4: Claus Braband , Anders Møller , Michael Schwartzbach, Static validation of dynamically generated HTML, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.38-45, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379657]
• 5: Claus Brabrand , Anders Møller , Michael I. Schwartzbach, The <bigwig> project, ACM Transactions on Internet Technology (TOIT), v.2 n.2, p.79-114, May 2002 [doi>10.1145/514183.514184]
• 6: Choi, T.-H., Lee, O., Kim, H., and Doh, K.-G. 2006. A practical string analyzer by the widening approach. In Proceedings of the 4th Asian Symposium on Programming Languages and Systems (APLAS 2006) (Sydney, Australia). Springer-Verlag, New York, 374--388.
• 7: Christensen, A., M&oslah;ller, A., and Schwartzbach, M. 2003. Precise analysis of string expressions. In Proceedings of the 10th International Static Analysis Symposium (San Diego, CA). Springer-Verlag, New York, 1--18.
• 8: Cook, W. R., and Ibrahim, A. H. 2005. Programming languages & databases: What's the problem?? url: http://www.cs.utexas.edu/~wcook/Drafts/2005/PLDBProblem.pdf.
• 9: William R. Cook , Siddhartha Rai, Safe query objects: statically typed objects as remotely executable queries, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062488]
• 10: Guyot, J. 1998. BNF index of SQL for Oracle 7. Available at http://cui.unige.ch/db-research/Enseignement/analyseinfo/SQL7/.
• 11: William G. J. Halfond , Alessandro Orso, Combining static analysis and runtime monitoring to counter SQL-injection attacks, Proceedings of the third international workshop on Dynamic analysis, p.1-7, May 17-17, 2005, St. Louis, Missouri
• 12: Nevin Heintze , Olivier Tardieu, Ultra-fast aliasing analysis using CLA: a million lines of C code in a second, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.254-263, June 2001, Snowbird, Utah, United States
• 13: John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, 2nd edition, ACM SIGACT News, v.32 n.1, March 2001 [doi>10.1145/568438.568455]
• 14: JBoss. 2006. Hibernate. url: http://www.hibernate.org/.
• 15: John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
• 16: Gregory M. Kapfhammer , Mary Lou Soffa, A family of test adequacy criteria for database-driven applications, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 17: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 18: Eugene Kohlbecker , Daniel P. Friedman , Matthias Felleisen , Bruce Duba, Hygienic macro expansion, Proceedings of the 1986 ACM conference on LISP and functional programming, p.151-161, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319859]
• 19: David Melski , Thomas Reps, Interconvertbility of set constraints and context-free language reachability, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.74-89, June 12-13, 1997, Amsterdam, The Netherlands
• 20: Microsoft. 2004. ADO.NET. url: http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnanchor/html/adonetanchor.asp.
• 21: Microsoft. 2005. LINQ Project. url: http://msdn.microsoft.com/netframework/future/linq/.
• 22: Oracle. 2006. Oracle TopLink. url: http://www.oracle.com/technology/products/ias/toplink/index.html.
• 23: Thomas Reps , Susan Horwitz , Mooly Sagiv, Precise interprocedural dataflow analysis via graph reachability, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-61, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199462]
• 24: Anders Sandholm , Michael I. Schwartzbach, A type system for dynamic Web documents, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.290-301, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325733]
• 25: O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
• 26: SQLJ. 1997. See http://www.sqlj.org.
• 27: Zhendong Su , Manuel Fähndrich , Alexander Aiken, Projection merging: reducing redundancies in inclusion constraint graphs, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.81-95, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325706]
• 28: David Jordan , Craig Russell, Java Data Objects, O'Reilly Media, Inc., 2003
• 29: Walid Taha , Tim Sheard, Multi-stage programming with explicit annotations, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.203-217, June 12-13, 1997, Amsterdam, The Netherlands
• 30: Raja Vallée-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , Vijay Sundaresan, Soot - a Java bytecode optimization framework, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 08-11, 1999, Mississauga, Ontario, Canada
• 31: Viega, J., and McGraw, G. 2001. Building Secure Software: How to Avoid Security Problems the Right Way. Addison Wesley, Boston, MA.
• 32: Wassermann, G., and Su, Z. 2004. An analysis framework for security in Web applications. In Proceedings of the 3rd FSE Workshop on the Specification and Verification of Component Based Systems (SAVCBS 2004) (Newport Beach, CA). ACM, New York, 70--78.
• 33: Daniel Weise , Roger Crew, Programmable syntax macros, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.156-165, June 21-25, 1993, Albuquerque, New Mexico, United States
• 34: Yellin, D. 1993. Speeding up dynamic transitive closure for bounded degree graphs. Acta Inf. 30, 4 (July), 369--384.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Reliability

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Validation; Formal methods
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

General Terms:
Algorithms, Languages, Reliability, Verification

Keywords:
JDBC, Static checking, context-free language reachability, database queries