Browse Prior Art Database

ON TESTING NONTESTABLE PROGRAMS

IP.com Disclosure Number: IPCOM000128177D
Original Publication Date: 1980-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 7 page(s) / 31K

Publishing Venue

Software Patent Institute

Related People

ELAINE J. WEYUKER: AUTHOR [+3]

Abstract

A frequently invoked assumption in program testing is that there is an oracle (i.e., the tester or an external .mechanism can accurately decide whether or not the output produced by a program is correct.) A program is nontestable if either an oracle does not exist or the tester must expend same extraordinary amount of time to determine whether or not the output is correct. The reasonableness of the oracle assumption is examined and the conclusion is reached that in many cases this is not a realistic assumption. The consequences of assuming the availability of an oracle are examined and alternatives investigated.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ON TESTING NONTESTABLE PROGRAMS

BY ELAINE J. WEYUKER

OCTOBER 1980 REPORT N0. OZS k

ABSTRACT

A frequently invoked assumption in program testing is that there is an oracle (i.e., the tester or an external .mechanism can accurately decide whether or not the output produced by a program is correct.) A program is nontestable if either an oracle does not exist or the tester must expend same extraordinary amount of time to determine whether or not the output is correct. The reasonableness of the oracle assumption is examined and the conclusion is reached that in many cases this is not a realistic assumption. The consequences of assuming the availability of an oracle are examined and alternatives investigated.

1. INTRODUCTION

' It is widely accepted that the fundamental limitation of using program testing techniques to determine the correctness of a program is the inability to extrapolate from the correctness of results for a proper subset of the input domain to the program's correctness for all elements of the domain. In particular, for any proper subset of the domain there are infinitely many programs which produce the correct output on those elements, but produce an incorrect output for some other domain element. Nonetheless we routinely test programs to increase our confidence in their correctness, and a great deal of research is currently being devoted to improving the effectiveness of program testing. These efforts fall into three primary categories:

1) The development of a sound ,theoretical basis for testing, 2) Devising and improving testing methodologies, particularly mechanizable ones,

3) The definition of accurate measures of and criteria for test data thoroughness. Almost all of the research on software testing therefore focuses on the development and analysis of input data. In particular there is an underlying assumption that once this phase is complete, the remaining tasks are straightforward. This . consists of running the program on the selected data, producing output which is then examined to determine the program's correctness on the test data. That this last phase of output examination is indeed routine is frequently expressed as the oracle assumption. This states that the tester is able to determine whether or not the output produced on the test data is correct. The mechanism which checks this correctness is known as p an oracle. (See for example [131 or [51.) Intuitively, it does not seem unreasonable to require that the tester be able to determine the correct answer in~some "reasonable" amount of time while expending some "reasonable" amount of effort. Therefore if either of the following two conditions occurr, a program should be considered nontestable.

1) There does not exist an oracle. 2) It is theoretically possible, but practically too difficult to determine the correct output. The term nontestable is used since if one cannot decide whether

New Yor...