Path-oriented random testing
A. Gotlieb, M. Petit
Abstract: Test campaigns usually require only a restricted subset of paths
in a program to be thoroughly tested. As random testing (RT) offers interesting fault-detection
capacities at low cost, we face the problem of building a sequence of random test data that execute only
a subset of paths in a program. We address this problem with an original technique based on backward
symbolic execution and constraint propagation to generate random test data based on an uniform
distribution. Our approach derives path conditions and computes an over-approximation
of thier associated subdomain to find such a uniform sequence. The challenging problem consists
in building efficiently a path-oriented random test data generator by minimizing the number of rejets
within the generated random sequence. Our first experimental resluts, conducted over a few academic
expaples, clearly show a dramatic improvement of our approach over classical random testing.
An ongoing work on statistical
structural testing via probabilistic concurrent constraint programming
M. Petit, A. Gotlieb
Abstract: The use of a model to describe and test the expected behavior of a
program is a well-proved software testing technique. Statistical
structural testing aims at building a model from which an input
probability distribution can be derived that maximizes the
coverage of some structural criteria by a random test data
generator. Our approach consists in converting statistical
structural testing into a Probabilistic Concurrent Constraint
Programming (PCCP) problem in order 1) to exploit the high
declarativity of the probabilistic choice operators of this
paradigm and 2) to benefit from its automated constraint solving
capacity. This paper reports on an ongoing work to implement PCCP
and exploit it to solve instances of statistical structural
testing problems. Application to testing Java Card applets is
discussed.
Raisonner et filtrer avec un choix probabiliste partiellement connu
M. Petit, A. Gotlieb
Résumé : La Programmation Concurrente par Contraintes Probabilistes (PCCP) étend la Programmation
Concurrente par Contraintes (CCP) par l'ajout d'un opérateur de choix probabiliste. Cet opérateur permet d'introduire
de l'aléa dans l'exécution d'un processus de CCP. Dans cet article, les fonctionnalités de cet opérateur sont étendues
afin de raisonner avec un choix probabiliste partiellement connu. Pour cela, nous définissons l'opérateur de choix probabiliste
comme un nouveau combinateur de contraintes et lui associons un algorithme de filtrage. Cet algorithme de filtrage permet, la plupart
du temps, d'accélérer la propagation de contraintes. L'implantation sous la forme d'une nouvelle librairie d'opérateurs de
choix probabilistes pour SICStus Prolog ainsi qu'une validation expérimentale est présentée.
Probabilistic choice operators
as global constraints : application to statistical software testing
M. Petit, A. Gotlieb
Poster published in LNCS 3132 -- Proc. of the
20th International Conference on Logic Programming (ICLP'2004), Saint-Malo, France,
6th to 10th September, 2004
Probabilistic Choice Operators as Constraint Combinators: application to the statistical
structural testing problem
M. Petit, A. Gotlieb
Abstract: Probabilistic Concurrent Constraint Programming (PCCP) extends concurrent constraint languages by providing probabilistic choice operators.
These operators have proved to be useful in implementing randomized algorithms as well as stochastic processes.
In this paper, we present an instance of PCCP where probabilistic choice operators are modelled with constraint
combinators. This modeling allow us to deal with a new kind of problems where the
probabilistic choice is only partially known.
An implementation under the form of a library of SICStus Prolog is in progress.
The major practical application of our work is the statistical structural testing problem in software testing.
Constraint-Based Reasoning on Probabilistic Choice Operators.
M. Petit, A. Gotlieb
Abstract:Probabilistic Concurrent Constraint Programming (PCCP) extends concurrent constraint languages with a probabilistic choice operator. This operator has proved to be useful in implementing randomized algorithms as well as stochastic processes.
In this report, we present a filtering algorithm dedicated to the probabilistic choice operator which permits to address new kind of applications where probabilistic choices are partially known. This filtering algorithm helps to deduce information on the possible values of the probabilistic choice without requiring its full valuation. An implementation under the form of a library of SICStus Prolog is presented.