Empirical evaluation of pareto efficient multi-objective regression test case prioritisation

Abstract

The aim of test case prioritisation is to determine an order-ing of test cases that maximises the likelihood of early fault revelation. Previous prioritisation techniques have tended to be single objective, for which the additional greedy algo-rithm is the current state-of-the-art. Unlike test suite min-imisation, multi objective test case prioritisation has not been thoroughly evaluated. This paper presents an exten-sive empirical study of the effectiveness of multi objective test case prioritisation, evaluating it on multiple versions of five widely-used benchmark programs and a much larger real world system of over 1 million lines of code. The paper also presents a lossless coverage compaction algorithm that dra-matically scales the performance of all algorithms studied by between 2 and 4 orders of magnitude, making prioritisation practical for even very demanding problems.