We present a foundational theory of software system reliability based on components. The theory describes how component developers can design and test their components to produce measurements that are later used by system designers to calculate composite system reliability, without implementation and test of the system being designed. The theory describes how to make component measurements that are independent of operational profiles, and how to incorporate the overall system-level operational profile into the system reliability calculations. In principle, the theory resolves the central problem of assessing a component, which is: a component developer cannot know how the component will be used and so cannot certify it for an arbitrary use; but if the component buyer must certify each component before using it, component based development loses much of its appeal. This dilemma is resolved if the component developer does the certification and provides the results in such a way that the component buyer can factor in the usage information later without repeating the certification. Our theory addresses the basic technical problems inherent in certifying components to be released for later use in an arbitrary system. Most component research has been directed at functional specification of software components; our theory addresses the other equally important side of the coin: component quality.

Subdomains of a program's input space are a concept around which ideas about testing can be organized. This paper considers the questions, ``What are the best subdomains for:

We propose checking the execution of an abstract data type's imperative implementation against its algebraic specification. An explicit mapping from implementation states to abstract values is added to the imperative code. The form of specification allows mechanical checking of desirable properties such as consistency and completeness, particularly when operations are added incrementally to the data type. During unit testing, the specification serves as a test oracle. Any variance between computed and specified values is automatically detected. When the module is made part of some application, the checking can he removed, or may remain in place for further validating the implementation. The specification, executed by rewriting, can be thought of as itself an implementation with maximum design diversity, and the validation as a form of multiversion-programming comparison.

It is conventional to start research papers on software engineering, particularly on testing and software quality, with a statement of how important software has become in the world, and the potential dangers of using it when those who construct it really don't know what they are doing. The author then goes on to show that his or her theory/method/insights/tools will make the world safe (or safer, if the author is modest) by providing the understanding that is lacking. ISSTA authors (I among them) have started many of their papers in just this way, but speaking for myself, these statements are window dressing --- they disguise my real concern. Long before software was any part of the workaday world, before there was any "software problem" or even much software, I was interested in program analysis because programs are arguably the most intriguing mathematical objects people create. I have happily pursued the study of programs for over 30 years.I wrote my first program (in ALGOL 58) in 1962 --- it failed to properly calculate a table of values of the error integral, being somewhat off in the third significant figure. (I remember the failure, and the debugging, poring over a decimal memory dump. But I can't recall the fault.) It took me until the mid-1960s to recognize that programs per se were much more interesting than their applications: I stumbled on Maurice Halstead's book [4] on self-compiling NELIAC compilers. Here was magical stuff: the master program defining a language, and itself written in that language! In my application to the University of Washington, I explained that I wanted to study computers "for themselves, not as they are used." Paul Klee, the topologist who was saddled with the task of replying to mathematics grad students that year, wrote back to assure me that "we've got a computer around here somewhere, and by the time you arrive I'm sure I can locate it." It was an IBM 7090, complete with IBSYS and FORTRAN, and who could have asked for software more in need of analysis?There were standards of respectability for a PhD dissertation even in those days, so I took up recursive function theory and the program-equivalence problem. Its application to testing is that we would like to know if the program under test differs from its functional specification --- that is, can it fail? Any understanding of programs through testing (a mechanical process) must come up against the program-equivalence problem: we cannot hope to gain full understanding, because to do so would be to solve the unsolvable problem. My dissertation was an exploration of the additional information (beyond the purely functional) needed to make the program-equivalence problem solvable [5]. What brought me to the first ISSTA in 1978 was Bill Howden's 1976 paper "Reliability of the path analysis strategy" [6].

No abstract available.

There are two main goals in testing software: (1) to achieve adequate quality (debug testing), where the objective is to probe the software for defects so that these can be removed, and (2) to assess existing quality (operational testing), where the objective is to gain confidence that the software is reliable. Debug methods tend to ignore random selection of test data from an operational profile, while for operational methods this selection is all-important. Debug methods are thought to be good at uncovering defects so that these can be repaired, but having done so they do not provide a technically defensible assessment of the reliability that results. On the other hand, operational methods provide accurate assessment, but may not be as useful for achieving reliability. This paper examines the relationship between the two testing goals, using a probabilistic analysis. We define simple models of programs and their testing, and try to answer the question of how to attain program reliability: is it better to test by probing for defects as in debug testing, or to assess reliability directly as in operational testing? Testing methods are compared in a model where program failures are detected and the software changed to eliminate them. The "better" method delivers higher reliability after all test failures have been eliminated. Special cases are exhibited in which each kind of testing is superior. An analysis of the distribution of the delivered reliability indicates that even simple models have unusual statistical properties, suggesting caution in interpreting theoretical comparisons.

Testing methods are compared in a model where program failures are detected and the software changed to eliminate them.The question considered is whether it is better to use tests that seek out failures ("debug testing") or to simulate usage and find failures along the way ("operational testing'')."Better" is measured by the delivered reliability obtained after all test failures have been eliminated.This comparison extends previous work, where the measure was the probability of detecting a failure.The theoretical treatment of the paper is probabilistic and analytical.Revealing special cases are exhibited in which each kind of testing is superior.

In assessing the quality of software, we would like to make engineering judgements similar to those based on statistical quality control. Ideally, we want to support statements like: "The confidence that this program's result at X is correct is p," where X is a particular vector of inputs, and confidence p is obtained from measurements of the software (perhaps involving X). For the theory to be useful, it must be feasible to predict values of p near 1 for many programs, for most values of X.Blum's theory of self-checking/correcting programs has exactly the right character, but it applies to only a few unusual problems. Conventional software reliability theory is widely applicable, but it yields only confidence in a failure intensity, and the measurements required to support a correctness-like failure intensity (say 10-9/demand) are infeasible. Voas's sensitivity theory remedies these problems of reliability theory, but his model is too simple to be very plausible. In this paper we combine these ideas: reliability, sensitivity, and self-checking, to obtain new results on "dependability," plausible predictions of software quality.

Abstract Testing tools are software analyzers that use information from particular executions of a program as well as information about a specification and the program text itself. Research prototypes of such tools are essential to investigate the ideas they embody. Often, hand calculation is so tedious and error‐prone that an investigator cannot obtain any intuition about his or her ideas without an implementation to aid in experiments. Traditionally, such tools have been implemented in conventional high‐level languages (e.g., C, Pascal), a process that takes more time than a prototype should. The technology of compiler generators and logic programming, applied to the idea of self‐instrumenting programs, drastically shortens the prototype cycle. This paper describes a general method for implementing prototype tools, gives examples of several old and new testing techniques fitted into the method, and discusses the ease with which such prototypes may be changed.

Testing is potentially the best grounded part of software engineering, since it deals with the well defined situation of a fixed program and a test (a finite collection of input values). However, the fundamental theory of program testing is in disarray. Part of the reason is a confusion of the goals of testing---what makes a test (or testing method) good. I argue that testing's primary goal should be to measure the dependability of tested software. In support of this goal, a plausible theory of dependability is needed to suggest and prove results about what test methods should be used, and under what circumstances. Although the outlines of dependability theory are not yet clear, it is possible to identify some of the fundamental questions and problems that must be attacked, and to suggest promising approaches and research methods. Perhaps the hardest step in this research is admitting that we do not already have the answers.

Most of the effort that goes into improving the quality of software paradoxically does not lead to quantitative, measurable quality. Software developers and quality-assurance organizations spend a great deal of effort preventing, detecting, and removing “defects”—parts of software responsible for operational failure. But software quality can be measured only by statistical parameters like hazard rate and mean time to failure, measures whose connection with defects and with the development process is little understood.

Theoretical models are used to study partition testing in the abstract and to describe the circumstances under which it should perform well at failure detection. Partition testing is shown to be more valuable when the partitions are narrowly based on expected failures and there is a good chance that failures occur. It is concluded that for gaining confidence from successful tests, partition testing as usually practiced has little value.>

An introductory computer science course is developed, much as calculus is a basic course for mathematics and the physical sciences, concerned primarily with theoretical foundations and methodology rather than apprenticeship through applications. In this work, the principles taught in the course are described and an example illustrating them is given.>

Because large-scale software development is a struggle against internal program complexity, the modules into which programs are divided play a central role in software engineering. A module encapsulating a data type allows the programmer to ignore both the details of its operations, and of its value representations. It is a primary strength of program proving that as modules divide a program, making it easier to understand, so do they divide its proof. Each module can be verified in isolation, then its internal details ignored in a proof of its use. This paper describes proofs of module abstractions based on functional semantics, and contrasts this with the Alphard formalism based on Hoare logic.

A compiler-based system DAISTS that combines a data-abstraction implementation language (derived from the SIMULA class) with specification by algebraic axioms is described.The compiler, presented with two independent syntactic objects in the axioms and implementing code, compiles a "program" that consists of the former as test driver for the latter.Data points, in the form of expressions using the abstract functions and constant values, are fed to this program to determine if the implementation and axioms agree.Along the way, structural testing measures can be applied to both code and axioms to evaluate the test data.Although a successful test does not conclusively demonstrate the consistency of axioms and code, in practice the tests are seldom successful, revealing errors.The advantage over conventional programming systems is threefold:(1) The presence of the axioms eliminates the need for a test oracle; only inputs need be supplied.(2) Testing is automated: a user writes axioms, implementation, and test points; the system writes the test drivers.(3) The results of tests are often surprising and helpful because it is difficult to get away with "trivial" tests: what is not significant for the code is liable to be a severe test of the axioms, and vice versa.

Abstract Package programs allow people who are not computer experts to use the power of machine computation for specialized purposes. Because the designers of scientific packages are more often experts in their scientific field than in computing, they may ignore issues of transportability and ease‐of‐use until too late, and produce a package that is difficult to use, and difficult to move to a different computer. In this paper we suggest some techniques to aid the scientific package designer. We suggest a kernel of routines that interface to the peculiar operating system of each machine, providing sophisticated but standard operating system services. This kernel makes the operating system of each computer appear identical and does not pose a difficult implementation problem. Above this interface all code can be machine‐independent, without sacrificing power and ease of use on any machine. We also suggest some novel organizations of processing routines designed to make the system easy to alter and extend. Complete independence of modules encourages centralization of tasks, which is both efficient and essential for easy extension. With this organization, the vast preponderance of package code can be written in machine‐independent ANSI FORTRAN. We suggest the use of a preprocessor like RATFOR to make this more pleasant. The paper closes with an application to an image‐processing package, in which a major problem is the flexible sequencing of processing routines.

A theory of program testing is presented, based on the idea of "reliable test set." Intuitively, a test is reliable if it exposes all errors that any test could find. To obtain a practical theory, two alterations of this idea are suggested: (1) strengthen the form of specification in the test, (2) restrict the kind of errors that the test must expose. Both of these changes have a natural application to program maintenance.

The techniques of compiler optimisation can be applied to aid a programmer in writing a program which cannot be improved by these techniques. A finite, representative set of test data can be useful in this process. This paper presents the theoretical basis for the (nonconstructive) existence of test sets which serve as maximally effective standins for an unlimited number of input possibilities. It is argued that although the time required by a compiler to fully exercise a program on a set of data may be large, the corresponding improvement in the reliability of the program may also be large if the set meets the given theoretical requirements.

if finite input-output specifications are added to the syntax of programs, these specifications can be verified at compile time. Programs which carry adequate tests with them in this way should be resistant to maintenance errors. If the specifications are independent of program details they are easy to give, and unlikely to contain errors in common with the program. Furthermore, certain finite specifications are maximal in that they exercise the control and expression structure of a program as well as any tests can.

Abstract A complex executive may be written as a core of minimum size, plus processes indistinguishable from those run by normal system users except for heavily circumscribed special privileges. Such an executive defines its virtual machine in a recursive fashion, since the processes abide by rules they help to enforce, and is ‘user‐like’ because most executive processing takes places in the protected, user mode. The advantages of such an executive are compactness because of lack of duplication of user and executive routines, good documentation because the user‐process interface is well defined and stable and, most important, excellent protection of the system from the executive itself, which utilizes all of the hardware protection available whenever possible. Situations most appropriate for the user‐like technique are described, and a series of detailed examples is given to show its application to a multiprogramming executive's memory allocation service.

A programming language may be viewed as an acceptable numbering of the partial recursive functions, with “semantics” the mapping from programs onto the functions computed [1]. (In this view, syntax receives little attention, although it is best to consider it as a characteristic function of a recursive set of indices instead of allowing all natural numbers. Such a view is natural for the usual arithmetizations, and eliminates some possible confusions, for example in interpreting the recursion theorem for pairs of numberings.) The virtue of functional semantics is that the semantic range is a machine-independent class. The abstract view in which details of the semantic mapping are ignored, in which the function assigned to a program is “the one it computes,” with the enumeration and s-m-n theorems assumed to compensate for the lost detail, has found only a restricted application to programning-language problems. Computational complexity, in the successful abstraction by Blum [2], is an attempt to provide more semantic structure without introducing a tenacious machine-dependence. The Blum measures are not themselves suitable as a semantic range. Two programs may have the same measure function, yet compute wildly different functions in widly different ways; other programs, intuitively very similar, may have wildly different measure functions [3]. A composite semantics of a function computed and a measure function is much like the approach suggested here: using formal computation functions as the semantic range.