Dynamic test input generation for database applications
Published 9 July 2007
Michael Emmi, Rupak Majumdar, Koushik Sen
Citations198
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
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 is developed and a constraints solver is proposed that can solve symbolic constraints consisting of both linear arithmetic constraints over variables as well as string constraints.
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.
Keywords
Computer Science
ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS
1,784 Citations1985Arto Salomaa
CUTE
1,653 Citations2005Koushik Sen, Darko Marinov +1 more
A method to represent and track constraints that capture the behavior of a symbolic execution of a unit with memory graphs as inputs is developed and an efficient constraint solver is proposed to facilitate incremental generation of such test inputs.
DART
1,501 Citations2005Patrice Godefroid, Nils Klarlund +1 more
DART is a new tool for automatically testing software that combines three main techniques, automated extraction of the interface of a program with its external environment using static source-code parsing, and dynamic analysis of how the program behaves under random testing and automatic generation of new test inputs to direct systematically the execution along alternative program paths.
Database Systems: The Complete Book
1,274 Citations2001Héctor García-Molina, Jeffrey D. Ullman +1 more
This introduction to database systems offers a readable comprehensive approach with engaging, real-world examples, and users will learn how to successfully plan a database application before building it.
Soot
939 Citations2010Raja Vallée-Rai, Phong Co +4 more
Soot, a framework for optimizing Java* bytecode, is implemented in Java and supports three intermediate representations for representing Java bytecode: Baf, a streamlined representation of bytecode which is simple to manipulate; Jimple, a typed 3-address intermediate representation suitable for optimization; and Grimp, an aggregated version of Jimple suitable for decompilation.
Journal of the ACMSimplify: a theorem prover for program checking
781 Citations2005David Detlefs, Greg Nelson +1 more
The article describes two techniques, error context reporting and error localization, for helping the user to determine the reason that a false conjecture is false, and includes detailed performance figures on conjectures derived from realistic program-checking problems.
Software Practice and ExperienceANTLR: A predicated‐<i>LL</i>(<i>k</i>) parser generator
610 Citations1995T. J. Parr, Russell W. Quong
ANTLR is introduced, a public‐domain parser generator that combines the flexibility of hand‐coded parsing with the convenience of a parser generator, which is a component of PCCTS.
The essence of command injection attacks in web applications
518 Citations2006Zhendong Su, Gary Wassermann
This paper presents the first formal definition of command injection attacks in the context of web applications, and gives a sound and complete algorithm for preventing them based on context-free grammars and compiler parsing techniques.
Test input generation with java PathFinder
500 Citations2004Willem Visser, Corina S. Păsăreanu +1 more
The main contribution of this work is to show how efficient white-box test input generation can be done for code manipulating complex data, taking into account complex method preconditions.
Lower bounds for natural proof systems
439 Citations1977Dexter Kozen
A lower space bound of n/log(n) is shown for the proof system for the PTIME complete theory and a lower length bound of 2cn/log('n'): length of polynomial space for the PSPACE complete theory.
Lecture notes in computer scienceCUTE and jCUTE: Concolic Unit Testing and Explicit Path Model-Checking Tools
391 Citations2006Koushik Sen, Gul Agha
CUTE is a tool to systematically and automatically test sequential C programs (including pointers) and concurrent Java programs and introduces a race-flipping technique to efficiently test and model check concurrent programs with data inputs.
Lecture notes in computer scienceSymstra: A Framework for Generating Object-Oriented Unit Tests Using Symbolic Execution
281 Citations2005Tao Xie, Darko Marinov +2 more
Experimental results show that Symstra generates unit tests that achieve higher branch coverage faster than the existing test-generation techniques based on concrete method arguments.
Lecture notes in computer scienceExecution Generated Test Cases: How to Make Systems Code Crash Itself
248 Citations2005Cristian Cadar, Dawson Engler
This paper presents a technique that uses code to automatically generate its own test cases at run time by using a combination of symbolic and concrete execution.
Using positive tainting and syntax-aware evaluation to counter SQL injection attacks
210 Citations2006William G. J. Halfond, Alessandro Orso +1 more
A new, highly automated approach for protecting existing Web applications against SQL injection, based on the novel idea of positive tainting and the concept of syntax-aware evaluation is proposed.
Lecture notes in computer sciencePrecise Analysis of String Expressions
202 Citations2003Aske Simon Christensen, Anders Møller +1 more
Lecture notes in computer scienceCVC: A Cooperating Validity Checker
199 Citations2002Aaron Stump, Clark Barrett +1 more
The CVC ("Cooperating Validity Checker") decision procedure is described, which implements a framework for combining subsidiary decision procedures for certain logical theories into a decision procedure for the theories' union.
Static checking of dynamically generated queries in database applications
173 Citations2004Carl Gould, Zhendong Su +1 more
Lecture notes in computer scienceICS: Integrated Canonizer and Solver?
133 Citations2001Jean-Christophe Filliâtre, Sam Owre +2 more
Decision procedures are at the core of many industrial-strength verification systems such as ACL2, PVS, or STeP but many existing decision procedures lack an appropriate API for managing contexts and efficiently switching between contexts.
A family of test adequacy criteria for database-driven applications
111 Citations2003Gregory M. Kapfhammer, Mary Lou Soffa
A family of test adequacy criteria that can be used to assess the quality of test suites for database-driven applications is proposed and a unique representation of a database- driven application is developed that facilitates the enumeration of database interaction associations.
JDBC checker: a static analysis tool for SQL/JDBC applications
111 Citations2004Carl Gould, Zhendong Su +1 more
A framework for testing database applications
108 Citations2000David Chays, Saikat Dan +3 more
This paper discusses issues arising in testing database systems and presents an approach to testing database applications, and a tool for populating the database with meaningful data that satisfy database constraints has been prototyped.
Using an SQL coverage measurement for testing database applications
71 Citations2004María José Suárez‐Cabal, Javier Tuya
A measurement of the coverage of SQL queries and the tool that automates it is presented and it is shown how database test data may be revised and changed using this measurement by means of completing or deleting information to achieve the highest possible value of coverage of queries that have access to the database.
Automatic generation of database instances for white-box testing
60 Citations2002Jian Zhang, Xu Chen +1 more
This paper studies the generation of database instances that respect the semantics of SQL statements embedded in a database application program and describes a supporting tool which generates a set of constraints.
Testing Database Applications with SQL Semantics.
55 Citations1999Man Yee Chan, Shing-Chi Cheung
This paper proposes to complement white box techniques with the inclusion of the SQL semantics and transforms the embedded SQL statements to procedures in some general-purpose programming language and thereby generate test cases using conventional white box testing techniques.
Command-Form Coverage for Testing Database Applications
54 Citations2006William G. J. Halfond, Alessandro Orso
A new test adequacy criterion is introduced that is based on coverage of the database commands generated by an application and specifically focuses on the application-database interactions.
The VLDB JournalGenerating consistent test data: Restricting the search space by a generator formula
42 Citations1993Andrea Neufeld, Guido Moerkotte +1 more
A new two-step approach is proposed that operationalizes the generator formula by translating it into a sequence of operators, and then executes it to construct the test database and introduces two powerful operators: the generation operator and the test-and-repair operator.