Universal safeness of test allocation strategies for partition testing

Given a specification, a partition testing strategy is said to be safe for a program if it is not less probable of detecting at least one failure than random testing, and universally safe, if it is safe for every program. The proportional sampling strategy (PSS) has previously been proved to be universally safe. This paper extends previous results by proving that PSS is actually the only universally safe test allocation strategy for partition testing, thereby settling an open problem in the search for universally safe strategies. Despite this, we show that a close approximation to PSS may still be safe for most programs. We also discuss the practical implications of this result.