טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentKutsy Ekaterina
SubjectA Probabilistic Analysis of Coverage Methods
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Ofer Strichman
Full Thesis textFull thesis text - English Version


Abstract

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.