A Symbolic Execution Algorithm for Constraint-Based Testing of Database Programs

Research output: Working paper

76 Downloads (Pure)

Abstract

In so-called constraint-based testing, symbolic execution is a common technique used as a part of the process to generate test data for imperative programs. Databases are ubiquitous in software and testing of programs manipulating databases is thus essential to enhance the reliability of software. This work proposes and evaluates experimentally a symbolic execution algorithm for constraint-based testing of database programs. First, we describe SimpleDB, a formal language which o ers a minimal and well-de ned syntax and semantics, to model common interaction scenarios between programs and databases. Secondly, we detail the proposed algorithm for symbolic execution of SimpleDB models. This algorithm considers a SimpleDB program as a sequence of operations over a set of relational variables, modeling both the database tables and the program variables. By integrating this relational model of the program with classical static symbolic execution, the algorithm can generate a set of path constraints for any nite path to test in the control ow graph of the program. Solutions of these constraints are test inputs for the program, including an initial content for the database. When the program is executed with respect to these inputs, it is guaranteed to follow the path with respect to which the constraints were generated. Finally, the algorithm is evaluated experimentally using representative SimpleDB models.
Original languageEnglish
Publication statusPublished - 6 Dec 2012

Fingerprint

Testing
Formal languages
Semantics

Cite this

@techreport{3c9e711d90444d88981af71e7337ab65,
title = "A Symbolic Execution Algorithm for Constraint-Based Testing of Database Programs",
abstract = "In so-called constraint-based testing, symbolic execution is a common technique used as a part of the process to generate test data for imperative programs. Databases are ubiquitous in software and testing of programs manipulating databases is thus essential to enhance the reliability of software. This work proposes and evaluates experimentally a symbolic execution algorithm for constraint-based testing of database programs. First, we describe SimpleDB, a formal language which o ers a minimal and well-de ned syntax and semantics, to model common interaction scenarios between programs and databases. Secondly, we detail the proposed algorithm for symbolic execution of SimpleDB models. This algorithm considers a SimpleDB program as a sequence of operations over a set of relational variables, modeling both the database tables and the program variables. By integrating this relational model of the program with classical static symbolic execution, the algorithm can generate a set of path constraints for any nite path to test in the control ow graph of the program. Solutions of these constraints are test inputs for the program, including an initial content for the database. When the program is executed with respect to these inputs, it is guaranteed to follow the path with respect to which the constraints were generated. Finally, the algorithm is evaluated experimentally using representative SimpleDB models.",
author = "Micha{\"e}l Marcozzi and Wim Vanhoof and Jean-Luc Hainaut",
year = "2012",
month = "12",
day = "6",
language = "English",
type = "WorkingPaper",

}

TY - UNPB

T1 - A Symbolic Execution Algorithm for Constraint-Based Testing of Database Programs

AU - Marcozzi, Michaël

AU - Vanhoof, Wim

AU - Hainaut, Jean-Luc

PY - 2012/12/6

Y1 - 2012/12/6

N2 - In so-called constraint-based testing, symbolic execution is a common technique used as a part of the process to generate test data for imperative programs. Databases are ubiquitous in software and testing of programs manipulating databases is thus essential to enhance the reliability of software. This work proposes and evaluates experimentally a symbolic execution algorithm for constraint-based testing of database programs. First, we describe SimpleDB, a formal language which o ers a minimal and well-de ned syntax and semantics, to model common interaction scenarios between programs and databases. Secondly, we detail the proposed algorithm for symbolic execution of SimpleDB models. This algorithm considers a SimpleDB program as a sequence of operations over a set of relational variables, modeling both the database tables and the program variables. By integrating this relational model of the program with classical static symbolic execution, the algorithm can generate a set of path constraints for any nite path to test in the control ow graph of the program. Solutions of these constraints are test inputs for the program, including an initial content for the database. When the program is executed with respect to these inputs, it is guaranteed to follow the path with respect to which the constraints were generated. Finally, the algorithm is evaluated experimentally using representative SimpleDB models.

AB - In so-called constraint-based testing, symbolic execution is a common technique used as a part of the process to generate test data for imperative programs. Databases are ubiquitous in software and testing of programs manipulating databases is thus essential to enhance the reliability of software. This work proposes and evaluates experimentally a symbolic execution algorithm for constraint-based testing of database programs. First, we describe SimpleDB, a formal language which o ers a minimal and well-de ned syntax and semantics, to model common interaction scenarios between programs and databases. Secondly, we detail the proposed algorithm for symbolic execution of SimpleDB models. This algorithm considers a SimpleDB program as a sequence of operations over a set of relational variables, modeling both the database tables and the program variables. By integrating this relational model of the program with classical static symbolic execution, the algorithm can generate a set of path constraints for any nite path to test in the control ow graph of the program. Solutions of these constraints are test inputs for the program, including an initial content for the database. When the program is executed with respect to these inputs, it is guaranteed to follow the path with respect to which the constraints were generated. Finally, the algorithm is evaluated experimentally using representative SimpleDB models.

M3 - Working paper

BT - A Symbolic Execution Algorithm for Constraint-Based Testing of Database Programs

ER -