Usage-Based Test-Case Prioritization

Statistical testing proposes to generate test cases based on a usage model represented by a Discrete Time Markov Chain (DTMC). This usage model represents the usage scenarios of the software as well as their probability. This allows one to determine the relative importance of execution scenarios (with respect to other). This project explores the possibility of using statistical testing to sample and prioritize products of an SPL. The basic idea is to focus on "most probable" (respectively "less probable" products), i.e. products that are able to execute highly probable (respectively. improbable) traces of the DTMC. Since black box usage scenarios may not relate directly to features, we propose to use a compact representation of SPL behavior, Featured Transition Systems (FTSs) to determine which traces are legal with respect to the SPL and associate related products. In fact, we construct another FTS, which maps to the selected traces. This FTS represent the behavior of the set of products of interest and is amenable to various testing and verification techniques.

In our approach, we consider three models: a FD d to represent the features and their constraints, an FTS fts over d and a usage model represented by a DTMC dtmc whose states, actions, and transitions are subset of their counterpart in fts.

Statistical Prioritization Approach Overview

The first step is to extract traces from the DTMC according to desired parameters provided by the tester. Generated finite traces from the DTMC may be illegal: behavior that cannot be executed any valid product of the SPL. The set of generated finite traces has to be filtered using the FTS by running them on it. Practically, we will build a second FTS' which will represent only the behavior of the SPL appearing in the finite traces generated from the DTMC.

At the end of step 2, we have an FTS' and a set of finite traces in this FTS'. This set of finite traces (coming from the DTMC) covers all the valid behaviors of the FTS'. It is thus possible to order them according to their probability to happen. This probability corresponds to the the cumulated individual probabilities of the transitions fired when executing the finite trace in the DTMC.

The set of products able of executing a trace t may be calculated from the FTS' (and its associated FD). Each valid finite trace t is associated to the set of products prod(t,fts') that can actually execute t with a probability Pr(t). Product priortization may be done by classifying the finite traces according to their probability to be executed, giving t-behaviourally equivalent classes of products for each finite trace t.


Examples of FTS statistical prioritization may be found here: Soda vending machine, Learning and online collaborative work application (Claroline).