Connecting test coverage to software dependability

It is widely felt that software quality, in the form of reliability or "trustworthiness, " can be demonstrated by the successful completion of testing that "covers" the software. However, this intuition has little experimental or theoretical support. This paper considers why the intuition is so powerful and yet misleading. Formal definitions of software "dependability " are suggested, along with new approaches for measuring this analog of trustworthiness. 1. The idea of test coverage From the beginning of computer programming, clever people have looked for clever ways to catch the mistakes that too easily enter even the best programs. The essential ideas are ones of systematic coverage, judging the quality of a test by how well it explores the nooks and crannies of program or specification. The ideas of functional coverage, based on the specification, and control coverage, based on the program’s control structure, are the most popular. They have been repeatedly reinvented and captured in testing tools. Control coverage is intuitively appealing because software defects appear as textually located faults along the path of execution, giving rise to failures. Functional coverage is even more basic—function-based trials put the software through its paces. Although these coverage ideas have appeared in the technical literature for more than 20 years, their penetration in practice is surprisingly shallow. The idea of mutation coverage [Hamlet77, DeMillo78, Howden82], in which the computational structure of a program is exercised, is not so obvious as control coverage. Mutation remains a research technique rather than one exploited in practice, partly because it is computationally expensive, but probably more because it is harder for people to use than is control coverage. Mutation is a double-edged sword: it appears that mutation-adequate tests are difficult to "fool " in the sense of detecting more faults than other kinds of structural coverage; but at the same time, th