Testing randomized software by means of statistical hypothesis tests

Abstract

Software testing research has mostly focused on deterministic software systems so far. In reality, however, randomized software systems (i.e. software systems with random output) also play an important role, e. g. for simulation purposes. Test evaluation is a real problem in that case. In previous work, statistical hypothesis tests have already been used, but test decisions have not been interpreted. Furthermore, those tests have only been applied if theoretic values on the distribution of program outputs had been available and not in case of golden implementations. In the present paper, we propose a general approach on how to apply statistical hypothesis tests in order to test randomized software systems. We exactly determine the confidence gained through these tests. We show that after passing a statistical hypothesis test, it can be guaranteed that at least the tested characteristics of the system under test are correct with a certain probability and accuracy of the result. Our approach is also applicable in case of golden implementations. Therefore, knowledge about the outputs' distribution is not necessary in that situation, which is a great advantage. Two case studies are described that have been conducted in order to assess the proposed approach. One of the case studies is based on a software system for the simulation of stochastic geometric models (among others) that evolved from the GeoStoch research project and is now used at France Télécom R&D, Paris, in order to calculate costs for communication networks and to plan new network structures.