Pseudo-oracles for non-testable programs

ABSTRACT

The most commonly used method of validating a program is by testing. The programmer typically runs the program on some test cases, and if and when they run correctly, the program is considered to be correct. We know that many difficult problems are associated with testing. One such problem is that it is a fundamental part of the testing process to require the ability to infer properties of a program by observing the program's behavior on selected inputs. The most common property that one hopes to infer through testing is correctness. But unless the program is run on the entire input domain, there are infinitely many programs which produce the correct output on the selected inputs, but produce incorrect output for some other element of the domain.

REFERENCES

• 1: Avizienis, A. and L. Chen. On the Implementation of N-Version Programming for Software Fault-Tolerance during Program Execution, Proceedings of COMPSAC Conference, 1977, 149-155.
• 2: DeMillo, R. A., R. J. Lipton, and F. G. Sayward. Hints on Test Data Selection: Help for the Practicing Programmer, Computer, Vol. 11, No. 4, April 1978, 34-41.
• 3: Horning, J. J., H. C. Lauer, P. M. Melliar-Smith, and B. Randell. A Program Structure for Error Detection and Recovery, in Lecture Notes in Computer Science, Vol. 16, Springer, 1974, 177-193.
• 4: Howden, W.E. and P. Eichhorst. Proving Properties of Programs from Program Traces, in Tutorial: Software Testing Validation Techniques, eds. E. Miller and W.E. Howden, IEEE Computer Society, 1978, 46-50.
• 5: J. C. Huang, An Approach to Program Testing, ACM Computing Surveys (CSUR), v.7 n.3, p.113-128, Sept. 1975 [doi>10.1145/356651.356652]
• 6: Robert Kowalski, Logic for problem-solving, North-Holland Publishing Co., Amsterdam, The Netherlands, 1986
• 7: Glenford J. Myers, Art of Software Testing, John Wiley & Sons, Inc., New York, NY, 1979
• 8: Panzl, D. J. Experience with Automatic Program Testing, Proceedings Trends and Applications 1981, National Bureau of Standards, May 1981.
• 9: Randell, B. System Structure for Software Fault Tolerance, IEEE Trans. Software Eng., Vol. SE-1, June 1975, 220-232.
• 10: J. T. Schwartz, Automatic data structure choice in a language of very high level, Communications of the ACM, v.18 n.12, p.722-728, Dec. 1975 [doi>10.1145/361227.361235]
• 11: Weyuker, E.J. The Oracle Assumption of Program Testing, Proc. of the 13th Hawaii International Conf. on System Sciences, Hawaii, Jan. 1980.
• 12: Weyuker, E. J. On Testing Nontestable Programs, Dept. of Computer Science Report No. 025, New York University, New York, October 1980.
• 13: White, L. J., E. I. Cohen, and B. Chandrasekaran. A Domain Strategy for Computer Program Testing, Comp. And Info. Sci. Res. Center Tech. Report, The Ohio State University, Columbus, Ohio, Aug. 1978.
• 14: Woodward, M. R., D. Hedley, and M. A. Hennell. Experience with Path Analysis and Testing Programs, IEEE Trans. Software Eng., Vol. SE-6, May 1980, pp. 247-257.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

          Nouns: ORACLE

General Terms:
Management, Verification