Software that has been well tested and analyzed may fail unpredictably when a certain combination of conditions occurs. In bounded exhaustive testing (BET) all combinations are tested on reduced versions of a problem/application with the idea that bugs associated with combinations for full versions of a program may also show up when combinations are tested for the reduced version. In previous work, a class oriented JUnit framework approach to BET was introduced, along with the idea of a BET test pattern. In this paper we considered the application of BET to system testing, using an extension of the FIT (framework for integrated testing) framework called SuperFIT. This approach is described along with a simple example of the application of a SuperFIT test generation tool.

Traditional white and black box testing methods are effective in revealing many kinds of defects, but the more elusive bugs slip past them. Model-based testing incorporates additional application concepts in the selection of tests, which may provide more refined bug detection, but does not go far enough. Test selection patterns identify defect-oriented contexts in a program. They also identify suggested tests for risks associated with a specified context. A context and its risks is a kind of conceptual trap designed to corner a bug. The suggested tests will find the bug if it has been caught in the trap.

Coverage is often used to determine when unit modules have been sufficiently tested. It is difficult to apply the same approach to whole systems. An additional problem is that coverage has no obvious reliability interpretation. A form of coverage called statistical coverage is described that solves some of the problems of systems level coverage and which also has a reliability interpretation. Statistical coverage is based on ideas from statistical testing. Statistical testing is reviewed and new results are introduced that are needed for statistical coverage, and which can also be applied to statistical testing.

In confidence-based reliability measurement, we determine that we are at least C confident that the probability of a program failing is less than or equal to a bound B. The basic results of this approach are reviewed and several additional results are introduced, including the adaptive sampling theorem which shows how confidence can be computed when faults are corrected as they appear in the testing process. Another result shows how to carry out testing in parallel. Some of the problems of statistical testing are discussed and an alternative method for establishing reliability called statistical coverage is introduced. At the cost of making reliability estimates that are relative to a fault model, statistical coverage eliminates the need for output validation during reliability estimation and allows the incorporation of non-statistical testing results into the statistical reliability estimation process. Statistical testing and statistical coverage are compared, and their relationship with traditional reliability growth modeling approaches is briefly discussed.

Software maintenance has been recognized as the most important phase of the software life cycle. Reverse engineering is an approach to help the maintainers in maintaining code which is poorly documented and understood, by recapturing information that was used to design and build a system. A new class of CASE tools, called reverse-engineering tools has emerged to help developers maintain and enhance existing source code basics. Some work has been done describing the derivation of specifications from code but has been impractical for real world code and unsuitable for a procedural language such as COBOL. The paper is a study of an approach to reverse engineering of functional specifications, called FACET (Function And Context Extraction Technique). The problems of generating a specification from a complex, large data processing program are discussed and three necessary strategies for overcoming these problems called modularization, abstraction and selection are surveyed. The basic tools needed to implement a FACET system are described as well as the design of a FACET prototype.

A temporal event analysis approach to program understanding is described. Program understanding is viewed as a sequence of episodes in which the programmer concludes that an informal event occurs that corresponds to some part of the code. This can be viewed as accepting that the code is an adequate definition of the meaning of the informal event. Often, such a definition is contingent upon working hypotheses that describe other informal program properties that should be verified in order to confirm the validity of the understanding process. Verification of working hypotheses may depend on the formulation of additional definitions or working hypotheses. The understanding process can be assisted through the use of a documentation language for describing events and hypotheses, and a hypothesis verification tool. The paper describes a temporal event language in which hypotheses are formulated in terms of expected event sequences. A hypothesis verification tool was built, and experimentation was carried out on a set of programs. The tool was found to be very useful in understanding the detailed, control oriented aspects of a program. Program faults were discovered in every program that was analyzed, indicating that it facilitates a deep level of understanding.

A measure of software dependability called trustability is described. A program p has trustability T if we are at least T confident that p is free of faults. Trustability measurement depends on detectability. The detectability of a method is the probability that it will detect faults, when there are faults present. Detectability research can be used to characterize conditions under which one testing and analysis method is more effective than another. Several detectability results that were only previously described informally, and illustrated by example, are proved. Several new detectability results are also proved. The trustability model characterizes the kind of information that is needed to justify a given level of trustability. When the required information is available, the trustability approach can be used to determine strategies in which methods are combined for maximum effectiveness. It can be used to determine the minimum amount of resources needed to guarantee a required degree of trustability, and the maximum trustability that is achievable with a given amount of resources. Theorems proving several optimization results are given. Applications of the trustability model are discussed. Methods for the derivation of detectability factors, the relationship between trustability and operational reliability, and the relationship between the software development process and trustability are described.

A measure of software dependability called trustability is described. A program p has trustability T if we are at least T confident that p is free of faults. Trustability measurement depends on detectability. The detectability of a method is the conditional probability that it will detect faults. The trustability model characterizes the kind of information needed to justify a given level of trustability. When the required information is available, the trustability approach can be used to determine strategies in which methods are combined for maximum effectiveness. It can be used to determine the minimum amount of resources needed to guarantee a required degree of trustability, and the maximum trustability that is achievable with a given amount of resources.>

No abstract available.

Formal verification of program properties may be infeasible or impractical, and informal analysis may be sufficient. Informal analysis involves the informal acceptance, by inspection, of the validity of program properties or steps in an analysis. Informal analysis may also involve abstraction. Abstraction can be used to eliminate details and concentrate on more general properties. Abstraction will result in informal analysis if it includes the use of undefined properties. A systematic, informal method for analysis called QDA (Quick Defect Analysis) is described. QDA is a comments analysis process based on facts and hypotheses. Facts are used to create an abstract program model, and hypotheses are selected, nonobvious program properties which are identified as needing verification. Hypotheses are proved from the facts that define an abstraction. QDA is hypothesis-driven in the sense that only those parts of an abstraction that are needed to prove hypotheses are created. The QDA approach was applied to a previously well tested operational flight program (OFP). The QDA method and the results of the OFP experiment are presented. The problems of incomplete or unsound informal analysis are analyzed, the relationship of QDA to other analysis methods is discussed, and suggested improvements to the QDA method are described.>

Reverse engineering abstractions are considered. Three kinds of abstractions are identified: problem domain, structural, and logical. Problem domain abstractions correspond to concepts from a program's application area. Structural abstractions are used to eliminate implementation details and redundant information. Logical abstractions are properties that can be logically derived from code. A method for generating functional specifications is described, which incorporates the abstraction techniques. It has been applied to a variety of COBOL programs and been found to generate natural abstract program descriptions. The authors describe work in progress, including the construction of an analysis tool that will be used to help verify the approach and to assess its complexity and computational requirements.>

Abstract It is argued that the goal in verification and validation is not correctness, but the detection of the occurrence of errors in the program construction process. Different methods, such as proofs and testing, should not be viewed as competing techniques, but as complementary methods used to detect different kinds of error. Proofs, for example, are appropriate for the detection of logical errors made during algorithm design, but are not appropriate for detecting detailed programming errors. Testing is useful for detecting other kinds of error. Mutation testing, for example, can be used to detect “typographical errors”, such as the use of the wrong arithmetic operator. Functional static analysis can be used to detect decomposition errors in which a programmer working on one part of a system makes a false assumption about the properties of objects that are established in some other part of the system. A brief summary of different methods is given, along with a description of the kind of error classes for which they are appropriate. An integrated approach to verification and validation is suggested in which, error classes are characterized, and methods, identified as being particularly appropriate for such classes, are combined.

Software validation is treated as the problem of detecting errors that programmers make during the software development process. This includes fault detection, in which the focus is on techniques for detecting the occurrence of local errors that result in well-defined classes of program statement faults. It also includes detecting other kinds of errors, such as decomposition errors. The main focus of the work is on a decomposition-error analysis technique called comments analysis. In this technique, errors are detected by analyzing special classes of program comments. Comments analysis has been applied to a variety of systems, including a data-processing program and an avionics real-time program. The use of comments analysis for sequential and concurrent systems is discussed, and the basic features of comments analysis tools are summarized. The relationship of comments analysis to other techniques, such as event sequence analysis, is discussed, and the differences between it and earlier work are explained.>

No abstract available.

An integrated approach to testing is described which includes both static and dynamic analysis methods and which is based on theoretical results that prove both its effectiveness and efficiency. Programs are viewed as consisting of collections of functions that are joined together using elementary functional forms or complex functional structures. Functional testing is identified as the input-output analysis of functional forms. Classes of faults are defined for these forms, and results are presented which prove the fault-revealing effectiveness of well defined sets of tests. Functional analysis is identified as the analysis of the sequences of operators, functions, and data type transformations which occur in functional structures. Theoretical results are presented which prove that it is only necessary to look at interfaces between pairs of operators and data type transformations in order to detect the presence of operator or data type sequencing errors. The results depend on the definition of normal forms for operator and data type sequencing diagrams.

One-dimensional design methods focus on one way of looking at data and control relationships in a design. Structured design concentrates on top-down, or vertical relationships. Data flow diagrams concentrate on horizontal relationships, in which the output from one computation flows to the next computation to be done. Two-dimensional design allows the simultaneous consideration of both the functional abstraction of vertical designs and the complex data sharing of horizontal designs through the use of functional and environmental models. The basic defects of one-dimensional approaches are described, followed by a description of a two-dimensional method. The method includes guidelines for transforming a one-dimensional design to a two-dimensional design.

Different approaches to the generation of test data are described. Error-based approaches depend on the definition of classes of commonly occurring program errors. They generate tests which are specifically designed to determine if particular classes of errors occur in a program. An error-based method called weak mutation testing is described. In this method, tests are constructed which are guaranteed to force program statements which contain certain classes of errors to act incorrectly during the execution of the program over those tests. The method is systematic, and a tool can be built to help the user apply the method. It is extensible in the sense that it can be extended to cover additional classes of errors. Its relationship to other software testing methods is discussed. Examples are included.

Error analysis involves the examination of a collection of programs whose errors are known. Each error is analyzed and validation techniques which would discover the error are identified. The errors that were present in version five of a package of Fortran scientific subroutines and then later corrected in version six were analyzed. An integrated collection of static and dynamic analysis methods would have discovered the errors in version five before its release. An integrated approach to validation and the effectiveness of individual methods are discussed.

An approach to functional testing is described in which the design of a program is viewed as an integrated collection of functions. The selection of test data depends on the functions used in the design and on the value spaces over which the functions are defined. The basic ideas in the method were developed during the study of a collection of scientific programs containing errors. The method was the most reliable testing technique for discovering the errors. It was found to be significantly more reliable than structural testing. The two techniques are compared and their relative advantages and limitations are discussed.

An approach to functional testing is described in which the design of a program is viewed as an integrated collection of functions. The selection of test data depends on the functions used in the design and on the value spaces over which the functions are defined. The basic ideas in the method were developed during the study of a collection of scientific programs containing errors. The method was the most reliable testing technique for discovering the errors. It was found to be significantly more reliable than structured testing. The two techniques are compared and their relative advantages and limitations are discussed.

Abstract The effectiveness in discovering errors of symbolic evaluation and of testing sad static program analysis are studied. The three techniques are applied to a diverse collection of programs and the results compared. Symbolic evaluation is used to carry out symbolic testing and to generate symbolic systems of path predicates. The use of the predicates for automated test data selection is analysed. Several conventional types of program testing strategies are evaluated. The strategies include branch testing, structured testing and testing on input values having special properties. The static source analysis techniques that are studied include anomaly analysis and interface analysis. Examples are included which describe typical situations in which one technique is reliable but another unreliable. The effectiveness of symbolic testing is compared with testing on actual data and with the use of an integrated methodology that includes both testing and static source analysis. Situations in which symbolic testing is difficult to apply or not effective are discussed. Different ways in which symbolic evaluation can be used for generating test data are described. Those ways for which it is most effective are isolated. The paper concludes with a discussion of the most effective uses to which symbolic evaluation can he put in an integrated system which contains all three of the validation techniques that are studied.

The basic features of the DISSECT symbolic testing tool are described. Usage procedures are outlined and the special advantages of the tool are summarized. Cost estimates for using the tool are provided and the results of experiments to determine its effectiveness are included. The background and history of the development of the tool are outlined. The availability of the tool is described and a listing of reference materials is included.

Two approaches to the study of program testing are described. One approach is theoretical and the other empirical. In the theoretical approach situations are characterized in which it is possible to use testing to formally prove the correctness of programs or the correctness of properties of programs. In the empirical approach statistics are collected which record the frequency with which different testing strategies reveal the errors in a collection of programs. A summary of the results of two research projects which investigated these approaches are presented. The differences between the two approaches are discussed and their relative advantages and disadvantages are compared.

Symbolic testing and a symbolic evaluation system called DISSECT are described. The principle features of DISSECT are outlined. The results of two classes of experiments in the use of symbolic evaluadon are summarized. Several classes of program errors are defined and the reliability of symbolic testing in finding bugs is related to the classes of errors. The relationship of symbolic evaluation systems like DISSECT to classes of program errors and to other kinds of program testing and program analysis tools is also discussed. Desirable improvements in DISSECT, whose importance was revealed by the experiments, are mentioned.

A set of test data T for a program P is reliable if it reveals that P contains an error whenever P is incorrect. If a set of tests T is reliable and P produces the correct output for each element of T then P is a correct program. Test data generation strategies are procedures for generating sets of test data. A testing strategy is reliable for a program P if it produces a reliable set of test data for P. It is proved that an effective testing strategy which is reliable for all programs cannot be constructed. A description of the path analysis testing strategy is presented. In the path analysis strategy data are generated which cause different paths in a program to be executed. A method for analyzing the reliability of path testing is introduced. The method is used to characterize certain classes of programs and program errors for which the path analysis strategy is reliable. Examples of published incorrect programs are included.

A methodology for generating program test data is described. The methodology is a model of the test data generation process and can be used to characterize the basic problems of test data generation. It is well defined and can be used to build an automatic test data generation system.

The concept of a "solution plan" is used to characterize the structure of interactive systems in which the user guides the solution process. A formalism for describing and analyzing solution plan structures is presented. The formalism can be used to define the role of the user in an interactive system. The solution plan approach to interaction is particularly applicable to problems which have an obvious graphical representation. An interactive graphics system for solving a class of routing problems is described. Suggestions for the application of the approach to other problems are included.

A program is described which can be used to determine if an irregular two-dimensional object can be moved from one point to another point inside a complicated two-dimensional structure (the two-dimensional sofa problem). The representation of the program in terms of a problem network and an associated search procedure is used to indicate the desirability of a generalised programming schema.

Many applications of CPM and PERT techniques involve the laborious procedure of drawing and redrawing “networks” or “flow charts”. The utility of a computer program that would automatically draw these flow charts is apparent. To be useful, PERT diagrams must be easy to read. In this program, events and activities that form a subnetwork are grouped together and the proximity of any two subnetworks reflects their interdependence. Events and activities in one subnetwork are not separated by the elements of another subnetwork. The horizontal axis of the diagram is a critical path along which the events may be time-scaled.