On Testing Non-Testable Programs

1982/11/01 by E. J. Weyuker, Elaine J. Weyuker · 605 citations
Computer Science · #Computer science #Mechanism (biology) #Oracle #Physics #Programming language #Software Reliability and Analysis Research #Software Testing and Debugging Techniques #Teaching and Learning Programming

paper · pdf · doi:10.1093/comjnl/25.4.465

published in The Computer Journal 25(4), 465-470 (Oxford University Press)

openalex publication_date 1982/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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 non-testable if either an oracle does not exist or the tester must expend some 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.

Cited by

• The Café in Amsterdam: When the Incumbent Becomes the Oracle
• LLM-Based Invariant Testing for Software Functional Bugs
• A Survey on Metamorphic Testing
• The Oracle Problem in Software Testing: A Survey
• A Frozen 12B Beats Frontier Models on Verified Work: 100% Accuracy, 0 Tokens, Bit-Exact, Forever
• Metamorphic Testing for Clinical ML Models: A Framework Proposal and Pilot Study
• How Do Practitioners Build SE Agents? Insights from a Mixed-Methods Study
• Testing Scientific Software: A Systematic Literature Review
• A survey on software testability
• Input Relation Prompting for Metamorphic Testing on Query-Based Systems
• STADS: Software Testing as Species Discovery
• Excision Score: Evaluating Edits with Surgical Precision
• Software Mutational Robustness
• Trustworthy Artificial Intelligence: A Review
• Predicting Metamorphic Relation for Matrix Calculation Programs
• Searching publications on software testing
• A software engineering perspective on engineering machine learning systems: State of the art and challenges
• Metamorphic Testing: Testing the Untestable
• Isolating Noisy Labelled Test Cases in Human-in-the-Loop Oracle Learning
• Prioritizing documentation effort: Can we do better?
• Quality Assurance of Bioinformatics Software: A Case Study of Testing a Biomedical Text Processing Tool Using Metamorphic Testing
• HOMRS: High Order Metamorphic Relations Selector for Deep Neural Networks
• Just-in-Time Catching Test Generation at Meta
• Basic concepts and taxonomy of dependable and secure computing
• Identifying implementation bugs in machine learning based image classifiers using metamorphic testing
• How to test bioinformatics software? [europepmc]
• Towards testing big data analytics software: the essential role of metamorphic testing. [europepmc]
• A metamorphic testing approach for event sequences. [europepmc]
• A Formal and Quantifiable Log Analysis Framework for Test Driving of Autonomous Vehicles. [europepmc]
• Expectation management in AI: A framework for understanding stakeholder trust and acceptance of artificial intelligence systems. [europepmc]

Related

• The Oracle Problem in Software Testing: A Survey
• Test Oracle Automation in the era of LLMs
• Mind the Gap: The Difference Between Coverage and Mutation Score Can Guide Testing Efforts
• An Empirical Study on Failed Error Propagation in Java Programs with Real Faults
• Insight Into SEER