M.Sc Student | Kutsy Ekaterina |
---|---|

Subject | A Probabilistic Analysis of Coverage Methods |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Ofer Strichman |

Full Thesis text |

Testing of hardware and software frequently cost more than the development of the product itself. As a result there is a constant effort, both in the industry and in the academia, to make this process as efficient as possible. Automatic test generators are tools that generate test vectors that are run on the tested program / hardware, and the outputs are then compared to some predefined specification. The simplest type of automatic test generation is generating random input vectors. There are various analytic results showing the effectiveness of such testing, assuming a uniform distribution of the tests. However, uniformly generated tests are not the only way tests are generated in the industry.

Hardware testing
is typically done by modeling the environment of the
tested component with a set of constraints. Every solution to this
set of constraints is a test, and hence such constraints-based test
generators produce a large number of solutions. A typical scenario
is that of beginning the testing process by defining a *coverage model*, which is a partition of the
sampling space to *coverage goals* according to
the developer's knowledge of the expected
functionality of the tested product. Then, using a constraint solver, various constraints are added in
order to *direct *the constraint
solver to goals that were not yet covered. Another
possible scenario is that random sampling is combined with such
directed sampling in various ways. Directed sampling has a cost,
since a more constrained model is many times harder to solve.
There is therefore a trade-off between cheaper sampling
- achieved by generating random samples - and directed sampling that have a higher probability of covering the
predefined goals. In this thesis we examine
four testing models, each of which makes different
assumptions about the error distribution, the testing
environment, the associated costs, and the possible testing strategies.
In each such model we compute the probability to find an error,
assuming it exists, or the expected cost until achieving full coverage
of the goals.

The aim is to achieve the best testing results - maximal probability to find an error or/and minimal testing cost. For this we estimate different measures of testing quality under different sampling strategies and show what strategy leads to the best result. In case we can not find an optimal strategy, we show what strategy is preferable in a given model.