INTRODUCTION${N}$-VERSION DIVERSE SYSTEMSTHEORETICAL FOUNDATIONS OF ${M}$-mp TESTINGA framework for ${M}$-mp testingAsymptotic behaviour of ${M}$-mp testingInput domain partitioningAN ${M}$-mp EXPERIMENTBackground and motivationSelecting the applicationPhases of the experimentModel program designModel-program implementationGenerating C++ codeCalibrating the model programBack-to-back testingTest data selectionSetting up the test execution environmentExecuting the programsDisagreements analysisEXPERIMENTAL RESULTS AND INTERPRETATIONObserved and estimated costsCore functionality cost analysisFull functionality cost analysisTest adequacy comparisonSUMMARY AND CONCLUSIONSRepeatability of the experimentWider applicability of ${{M}}$-mp testingRELATED WORKSOFTWARE—PRACTICE AND EXPERIENCESoftw. Pract. Exper. 2001; 31:1211–1236 (DOI: 10.1002/spe.409)Software testing using modelprogramsL. I. Manolache and D. G. Kourie∗,†Department of Computer Science, University of Pretoria, Pretoria 0002, South AfricaSUMMARYA strategy described as ‘testing using M model programs’ (abbreviated to ‘M -mp testing’) is investigatedas a practical alternative to software testing based on manual outcome prediction. A model programimplements suitably selected parts of the functional specification of the software to be tested. The M-mptesting strategy requires that M (M ≥ 1) model programs as well as the program under test, P , shouldbe independently developed. P and the M model programs are then subjected to the same test data.Difference analysis is conducted on the outputs and appropriate corrective action is taken. P and theM model programs jointly constitute an approximate test oracle. Both M-mp testing and manual outcomeprediction are subject to the possibility of correlated failure. In general, the suitability of M -mp testingin a given context will depend on whether building and maintaining model programs is likely to be morecost effective than manually pre-calculating P ’s expected outcomes for given test data. In many contexts,M-mp testing could also facilitate the attainment of higher test adequacy levels than would be possible withmanual outcome prediction.A rigorous experiment in an industrial context is described in which M -mp testing (with M = 1) was usedto test algorithmically complex scheduling software. In this case, M -mp testing turned out to be significantlymore cost effective than testing based on manual outcome prediction. Copyright 2001 John Wiley & Sons,Ltd.KEY WORDS: test oracle; N-version programming; back-to-back testing; comparison testing; M-mp testingINTRODUCTIONOne of the most difficult tasks in software testing is to assess the correctness of the outcomes ofa program that is subjected to particular test inputs. The problem of establishing an appropriatemechanism to adjudicate on whether or not an outcome is correct, somewhat neglected in testing theory,is referred to as ‘the oracle problem’ [1,2]. Hamlet [1] points out that: ‘Testing theory, being concernedwith the choice of tests and testing methods, usually ignores the oracle problem. It is typically assumed∗Correspondence to: D. G. Kourie, Department of Computer Science, University of Pretoria, Pretoria 0002, South Africa.†E-mail: [email protected]  2001 John Wiley & Sons, Ltd.Received 19 June 2000Revised 5 February 2001 and 25 June 2001Accepted 25 June 20011212 L. I. MANOLACHE AND D. G. KOURIEFigure 1. Global view of the test process.that an oracle exists, and the theoretician then glibly talks about success and failure, while in practicethere is no oracle but imperfect human judgment.’A test oracle is a means of determining whether a program passed or failed a test‡. The test processcan be depicted as in Figure1 [3]. P denotes the program to be tested and a test strategy determinesthe set of test data to be used. In order to obtain a test result for a given test in this set, P ’s output hasto be compared to the oracle’s output.The simplest conceptual form of an oracle is the comparison of actual and expected programoutcomes. For a small number of simple test inputs, it might be feasible to work out the expectedoutputs manually. However, thorough testing in a practical context usually requires rather complex andlarge test-datasets. Therefore, as emphasized in the testing literature, manual outcome prediction mightbe time consuming and error prone (e.g. Beizer [4], Richardson et al.[5], Peters and Parnas [6,7]).The research community has addressed the oracle problem especially in relation to formal methods.Stocks and Carrington [8] discuss the generation of oracle templates from formal specifications.Richardson et al.[5] propose an approach to deriving and using specification-based oracles in thetesting process. Peters and Parnas [6,7] developed a test-oracle generator that produces a softwareoracle from relational program documentation. Unfortunately, formal methods have not been widelyadopted in industry yet. A major obstacle seems to be the lack of compelling evidence of theireffectiveness for industrial-size applications [9]. Specification-based oracles might be the answer forthe future, but in the meantime the industry needs better approaches to the oracle problem than manualoutcome prediction. Both Weyuker [10] and Beizer [4] suggest several practical alternatives. Oneof them is to build a pseudo-oracle in the form of a detailed prototype or a dual program that iscapable of providing the expected outputs. The approach examined here is similar and is based onN-version diversity, a principle that is applied especially in the well-known software fault-toleranttechnique known as N-version programming. To highlight its similarity with N -version programming,the approach advocated below is called ‘testing using M model programs’ or, in short, ‘M-mp testing’.The next section surveys research into N-version diverse systems that has inspired and guidedthe proposal for M-mp testing. It is followed by a section outlining theoretical issues relating to‡Some authors adopt a stricter definition and regard an oracle as a means for ‘predicting’ the correct program outcomes.Copyright  2001 John Wiley & Sons, Ltd. Softw. Pract. Exper. 2001; 31:1211–1236SOFTWARE TESTING USING MODEL PROGRAMS 1213M-mp testing. Next described is the execution of an industrial experiment to investigate whetherM-mp testing is likely to be more cost effective than testing based on manual