Michael Emmi
ABSTRACT
We describe an algorithm for automatic test input generation for database applications. Given a program in an imperative language that interacts with a database through API calls, our algorithm generates both input data for the program as well as suitable database records to systematically explore all paths of the program, including those paths whose execution depend on data returned by database queries. Our algorithm is based on concolic execution, where the program is run with concrete inputs and simultaneously also with symbolic inputs for both program variables as well as the database state. The symbolic constraints generated along a path enable us to derive new input values and new database records that can cause execution to hit uncovered paths. Simultaneously, the concrete execution helps to retain precision in the symbolic computations by allowing dynamic values to be used in the symbolic executor. This allows our algorithm, for example, to identify concrete SQL queries made by the program, even if these queries are built dynamically.
The contributions of this paper are the following. We develop an algorithm that can track symbolic constraints across language boundaries and use those constraints in conjunction with a novel constraint solver to generate both program inputs and database state. We propose a constraint solver that can solve symbolic constraints consisting of both linear arithmetic constraints over variables as well as string constraints (string equality, disequality, as well as membership in regular languages). Finally, we provide an evaluation of the algorithm on a Java implementation of MediaWiki, a popular wiki package that interacts with a database back-end.
- J. R. Büchi and S. Senger. Definability in the existential theory of concatenation and undecidable extensions of this theory. Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, 22, 1987.Google Scholar
- M. J. S. Cabal and J. Tuya. Using an SQL coverage measurement for testing database applications. In SIGSOFT FSE, 2004.Google Scholar
- C. Cadar and D. R. Engler. Execution generated test cases: How to make systems code crash itself. In SPIN, 2005. Google ScholarDigital Library
- M. Chan and S. -C. Cheung. Testing database applications with SQL semantics. In CODAS, 1999.Google Scholar
- D. Chays, S. Dan, P. G. Frankl, F. I. Vokolos, and E. J. Weber. A framework for testing database applications. In ISSTA, 2000. Google ScholarDigital Library
- D. Chays, Y. Deng, P. G. Frankl, S. Dan, F. I. Vokolos, and E. J. Weyuker. AGENDA: a test generator for relational database applications. Technical Report TR-CIS-2002-04, Polytechnic University, 2002. http://cis.poly.edu/tr/tr-cis-2002-04.shtml.Google Scholar
- A. S. Christensen, A. Møller, and M. I. Schwartzbach. Precise analysis of string expressions. In SAS 03: Static Analysis Symposium, volume 2694 of LNCS, pages 1--18. Springer-Verlag, 2003.Google ScholarCross Ref
- D. Detlefs, G. Nelson, and J. B. Saxe. Simplify: a theorem prover for program checking. J. ACM, 52(3), 2005. Google ScholarDigital Library
- V. Diekert. Makanin's algorithm. In Algebraic Combinatorics on Words, volume 90 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002.Google Scholar
- J. -C. Filliâtre, S. Owre, H. Rueß, and N. Shankar. ICS: Integrated canonizer and solver. In CAV, 2001. Google ScholarDigital Library
- P. Godefroid, N. Klarlund, and K. Sen. DART: directed automated random testing. In PLDI, 2005. Google ScholarDigital Library
- C. Gould, Z. Su, and P. T. Devanbu. JDBC checker: A static analysis tool for SQL/JDBC applications. In ICSE, 2004. Google ScholarDigital Library
- C. Gould, Z. Su, and P. T. Devanbu. Static checking of dynamically generated queries in database applications. In ICSE, 2004. Google ScholarDigital Library
- W. G. J. Halfond and A. Orso. Command-form coverage for testing database applications. In ASE, 2006. Google ScholarDigital Library
- W. G. J. Halfond, A. Orso, and P. Manolios. Using positive tainting and syntax-aware evaluation to counter SQL injection attacks. In SIGSOFT FSE, 2006. Google ScholarDigital Library
- G. M. Kapfhammer and M. L. Soffa. A family of test adequacy criteria for database-driven applications. In ESEC / SIGSOFT FSE, 2003. Google ScholarDigital Library
- D. Kozen. Lower bounds for natural proof systems. In FOCS, 1977.Google ScholarDigital Library
- lp solve. http://groups.yahoo.com/group/lp_solve/.Google Scholar
- MediaWiki. http://www.mediawiki.org/wiki/MediaWiki.Google Scholar
- A. Neufeld, G. Moerkotte, and P. C. Lockemann. Generating consistent test data for a variable set of general consistency constraints. VLDB J., 2(2), 1993. Google ScholarDigital Library
- T. J. Parr and R. W. Quong. ANTLR: A predicated- LL (k) parser generator. Softw., Pract. Exper., 25(7), 1995. Google ScholarDigital Library
- MS SQL Server 2000 SELECT statement grammar. http://www.antlr.org/grammar/1062280680642/MS_SQL_SELECT.html.Google Scholar
- K. Sen and G. Agha. CUTE and jCUTE: Concolic unit testing and explicit path model-checking tools. In CAV, 2006. Google ScholarDigital Library
- K. Sen, D. Marinov, and G. Agha. CUTE: a concolic unit testing engine for C. In ESEC/SIGSOFT FSE, 2005. Google ScholarDigital Library
- A. Stump, C. W. Barrett, and D. L. Dill. CVC: A cooperating validity checker. In CAV, 2002. Google ScholarDigital Library
- Z. Su and G. Wassermann. The essence of command injection attacks in web applications. In POPL, 2006. Google ScholarDigital Library
- R. E. Tarjan. Efficiency of a good but not linear set union algorithm. J. ACM, 22(2), 1975. Google ScholarDigital Library
- J. D. Ullman, H. Garcia-Molina, and J. Widom. Database Systems: The Complete Book. Prentice Hall PTR, Upper Saddle River, NJ, USA, 2001. Google ScholarDigital Library
- R. Vallée-Rai, P. Co, E. Gagnon, L. J. Hendren, P. Lam, and V. Sundaresan. Soot - a Java bytecode optimization framework. In CASCON, 1999.Google ScholarDigital Library
- W. Visser, C. S. Pasareanu, and S. Khurshid. Test input generation with Java PathFinder. In ISSTA, 2004. Google ScholarDigital Library
- T. Xie, D. Marinov, W. Schulte, and D. Notkin. Symstra: A framework for generating object-oriented unit tests using symbolic execution. In TACAS, 2005. Google ScholarDigital Library
- J. Zhang, C. Xu, and S. -C. Cheung. Automatic generation of database instances for white-box testing. In COMPSAC, 2001. Google ScholarDigital Library
Index Terms
- Dynamic test input generation for database applications
Recommendations
Guided test generation for database applications via synthesized database interactions
Testing database applications typically requires the generation of tests consisting of both program inputs and database states. Recently, a testing technique called Dynamic Symbolic Execution (DSE) has been proposed to reduce manual effort in test ...
Test input generation for database programs using relational constraints
DBTest '12: Proceedings of the Fifth International Workshop on Testing Database SystemsDatabases are ubiquitous in software and testing of programs manipulating databases is thus essential to enhance the reliability of software. In this paper, we describe a clean and unified approach to automatically generate test inputs for such database ...
SynConSMutate: Concolic Testing of Database Applications via Synthetic Data Guided by SQL Mutants
ITNG '13: Proceedings of the 2013 10th International Conference on Information Technology: New GenerationsTesting techniques for database applications typically include generation of database states (synthetic data) along with automatic generation of test cases. The quality of such test cases is evaluated on the basis of structural coverage of the host ...
Comments