Search

Test case prioritization is used in regression testing to schedule the execution order of test cases so as to expose faults earlier in testing. Over the past few years, many test case prioritization techniques have been proposed in the literature. Most of these techniques require data on dynamic execution in the form of code coverage information for test cases. However, the collection of dynamic code coverage information on test cases has several associated drawbacks including cost increases and reduction in prioritization precision. In this paper, we propose an approach to prioritizing test cases in the absence of coverage information that operates on Java programs tested under the JUnit framework—an increasingly popular class of systems. Our approach, JUnit test case Prioritization Techniques operating in the Absence of coverage information (JUPTA), analyzes the static call graphs of JUnit test cases and the program under test to estimate the ability of each test case to achieve code coverage, and then schedules the order of these test cases based on those estimates. To evaluate the effectiveness of JUPTA, we conducted an empirical study on 19 versions of four Java programs ranging from 2K-80K lines of code, and compared several variants of JUPTA with three control techniques, and several other existing dynamic coverage-based test case prioritization techniques, assessing the abilities of the techniques to increase the rate of fault detection of test suites. Our results show that the test suites constructed by JUPTA are more effective than those in random and untreated test orders in terms of fault-detection effectiveness. Although the test suites constructed by dynamic coverage-based techniques retain fault-detection effectiveness advantages, the fault-detection effectiveness of the test suites constructed by JUPTA is close to that of the test suites constructed by those techniques, and the fault-detection effectiveness of the test suites constructed by some of JUPTA's variants is better than that of the test suites constructed by several of those techniques. [ABSTRACT FROM AUTHOR]

Dynamic software updating (DSU) systems patch programs on the fly without incurring downtime. To avoid failures due to the updating process itself, many DSU systems employ timing restrictions. However, timing restrictions are theoretically imperfect, and their practical effectiveness is an open question. This paper presents the first significant empirical evaluation of three popular timing restrictions: activeness safety (AS), which prevents updates to active functions, con-freeness safety (CFS), which only allows modifications to active functions when doing so is provably type-safe, and manual identification of the event-handling loops during which an update may occur. We evaluated these timing restrictions using a series of DSU patches to three programs: OpenSSH, vsftpd, and ngIRCd. We systematically applied updates at each distinct update point reached during execution of a suite of system tests for these programs to determine which updates pass and which fail. We found that all three timing restrictions prevented most failures, but only manual identification allowed none. Further, although CFS and AS allowed many more update points, manual identification still supported updates with minimal delay. Finally, we found that manual identification required the least developer effort. Overall, we conclude that manual identification is most effective. [ABSTRACT FROM AUTHOR]

Debugging often involves 1) finding the point of failure (the first statement that produces bad output) and 2) finding and fixing the actual bug. Print statements and debugger break points can help with step 1. Slicing the program back from values used at the point of failure can help with step 2. However, neither approach is ideal: Debuggers and print statements can be clumsy and timeconsuming and backward slices can be almost as large as the original program. This paper addresses both problems. We present callstack-sensitive slicing, which reduces slice sizes by leveraging the series of calls active when a program fails. We also show how slice intersections may further reduce slice sizes. We then describe a set of tools that identifies points of failure for programs that produce bad output. Finally, we apply our point-of-failure tools to a suite of buggy programs and evaluate callstack-sensitive slicing and slice intersection as applied to debugging. Callstack-sensitive slicing is very effective: On average, a callstack-sensitive slice is about 0.31 time the size of the corresponding full slice, down to just 0.06 time in the best case. Slice intersection is less impressive, on average, but may sometimes prove useful in practice. [ABSTRACT FROM AUTHOR]

Test-Driven Development (TDD) is based on formalizing a piece of functionality as a test, implementing the functionality such that the test passes, and iterating the process. This paper describes a controlled experiment for evaluating an important aspect of TDD: In TDD, programmers write functional tests before the corresponding implementation code. The experiment was conducted with undergraduate students. While the experiment group applied a test-first strategy, the control group applied a more conventional development technique, writing tests after the implementation. Both groups followed an incremental process, adding new features one at a time and regression testing them. We found that test-first students on average wrote more tests and, in turn, students who wrote more tests tended to be more productive. We also observed that the minimum quality increased linearly with the number of programmer tests, independent of the development strategy employed. [ABSTRACT FROM AUTHOR]

In this paper, we present a compiler testing technique that closes the gap between existing compiler implementations and correct compilers. Using formal specifications of procedure-calling conventions, we have built a target-sensitive test suite generator that builds test cases for a specific aspect of compiler code generators: the procedure-calling sequence generator. By exercising compilers with these specification-derived target-specific test suites, our automated testing tool has exposed bugs in every compiler tested on the MIPS and one compiler on the SPARC. These compilers include some that have been in heavy use for many years. Once a fault has been detected, the system can often suggest the nature of the problem. The testing system is an invaluable tool for detecting, isolating, and correcting faults in today's compilers. [ABSTRACT FROM AUTHOR]

The decision about when to release a software product commercially is not a question of when the software has attained some objectively justifiable degree of correctness. It is, rather, a question of whether the software achieves a reasonable balance among engineering objectives, market demand, customer requirements, and marketing directives of the software organization. In this paper, we present a rigorous framework for addressing this important decision. Conjugate distributions from statistical decision theory provide an attractive means of modeling the cost and rate of bugs given information acquired during software testing, as well as prior information provided by software engineers about the fidelity of the software before testing begins. In contrast to methods such as [1] and [15] the stopping analysis presented here yields a computationally simple rule for deciding when to release a commercial software product based on information revealed to engineers during software testing-complicated numerical procedures are not needed. Our method has the added benefits that it is sequential: It measures explicitly the costs of customer dissatisfaction associated with bugs as well as the costs of declining market position while the testing process continues; and it incorporates a practical framework for costcriticality assessment that makes sense to professional software developers. A probabilistic model of catastrophic bugs provides another useful way of characterizing and measuring the software's expected performance after commercial release. Taken together, these tools provide a software organization with a clearer basis for making decisions about when to release a commercial software software product. [ABSTRACT FROM AUTHOR]

Embedded assertions have been recognized as a potentially powerful tool for automatic runtime detection of software faults during debugging, testing, maintenance and even production versions of software systems. Yet despite the richness of the notations and the maturity of the techniques and tools that have been developed for programming with assertions, assertions are a development tool that has seen little widespread use in practice. The main reasons seem to be that (1) previous assertion processing tools did not integrate easily with existing programming environments, and (2) it is not well understood what kinds of assertions are most effective at detecting software faults. This paper describes experience using an assertion processing tool that was built to address the concerns of ease-of-use and effectiveness. The tool is called APP, an Annotation PreProcessor for C programs developed in UNIX-based development environments. APP has been used in the development of a variety of software systems over the past five years. Based on this experience, the paper presents a classification of the assertions that were most effective at detecting faults. While the assertions that are described guard against many common kinds of faults and errors, the very commonness of such faults demonstrates the need for an explicit, high-level, automatically checkable specification of required behavior. It is hoped that the classification presented in this paper will prove to be a useful first step in developing a method of programming with assertions. [ABSTRACT FROM AUTHOR]

Statistical testing of software establishes a basis for statistical inference about a software system's expected field quality. This paper describes a method for statistical testing based on a Markov chain model of software usage. The significance of the Markov chain is twofold. First, it allows test input sequences to be generated from multiple probability distributions, making it more general than many existing techniques. Analytical results associated with Markov chains facilitate informative analysis of the sequences before they are generated, indicating how the test is likely to unfold. Second, the test input sequences generated from the chain and applied to the software are themselves a stochastic model and are used to create a second Markov chain to encapsulate the history of the test, including any observed failure information. The influence of the failures is assessed through analytical computations on this chain. We also derive a stopping criterion for the testing process based on a comparison of the sequence generating properties of the two chains. [ABSTRACT FROM AUTHOR]

A theory of fault-based program testing is defined and explained. Testing is fault-based when it seeks to demonstrate that prescribed faults are not in a program. It is assumed here that a program can only be incorrect in a limited fashion specified by associating alternate expressions with program expressions. Classes of alternate expressions can be infinite. Substitution of an alternate expression for a program expression yields an alternate program that is potentially correct. The goal of fault-based testing is to produce a test set that differentiates the program from each of its alternates. A particular form of fault-based testing based on symbolic execution is presented. In symbolic testing program expressions are replaced by symbolic alternatives that represent classes of alternate expressions. The output from the system is an expression in terms of the input and the symbolic alternative. Equating this with the output from the original program yields a propagation equation whose solutions determine those alternatives which are not differentiated by this test. Since an alternative set can be infinite, it is possible that no finite test differentiates the program from all its alternates. Circumstances are described as to when this is decidable. [ABSTRACT FROM AUTHOR]

A new test for detecting the nonrandomness of finite bi- nary strings is proposed. This test, based on an evaluation of the power spectrum of a finite string, extends and quantifies a similar test proposed by Jason Gait [1] in 1977. As an empirical measure of the sensitivity of our test, it was com- pared with a chi-square test for uniformity of distribution, which also measures nonrandomness. This comparison was performed by applying each of these tests to binary strings produced, using short-round versions of the DES in output-feedback mode. By varying the number of DES rounds from 1 to 16, it was possible to gradually vary the degree of randomness of the resulting strings. The degree of randomness of the DES, including the 15 short-round versions, was also assessed. Only ensembles generated by one and two round versions were rejected as random. [ABSTRACT FROM AUTHOR]

When a new computer software package is developed, a testing procedure is often put into effect to eliminate the faults, or bugs, in the package. One common procedure is th try the package on a set of well-known problems to try to see if any errors result. This goes for some fixed time with all detected errors being noted. Then the testing stops and the package is carefully checked to determine the r specific bugs that were responsible for the observed errors, and the package is then altered to remove these bugs. A problem of great importance is the estimation of the error rate of this revised software package. To model the above, we suppose that initially the package contains m, an unknown number of bugs which cause errors to occur in accordance with independent Poisson process having unknown rates λi, i = 1, …, m. We suppose that the package is to be run for t time units and that each error is, independently, detected with some known probability p. At the end of this time, a careful check of the package is made to determine the specific bugs that caused the detected errors (that is, a debugging takes place). These bugs are then removed and the problem of interest is to determine the error rate for the revised package. In this paper, we show how to estimate this quantity under a variety of assumptions as to what is learned when the debugging occurs. [ABSTRACT FROM AUTHOR]

In this paper we introduce two classes of program testing strategies that consist of specifying a set of required elements for the program and then covering those elements with appropriate test inputs. In general, a required element has a structural and a functional component and is covered by a test case if the test case causes the features specified in the structural component to be executed under the conditions specified in the functional component. Data flow analysis is used to specify the structural component and data flow interactions are used as a basis for developing the functional component. The strategies are illustrated with examples and some experimental evaluations of their effectiveness are presented. [ABSTRACT FROM AUTHOR]

-c_A systematic approach to test data design is presented based on both practical translation of theory and organization of professional lore. The approach is organized around five domains and achieving coverage (exercise) of them by the test data. The domains are processing functions, input, output, interaction among functions, and the code itself. Checklists are used to generate data for processing functions. Separate checklists have been constructed for eight common business data processing functions such as editing, updating, sorting, and reporting. Checklists or specific concrete directions also exist for input, output, interaction, and code coverage. Two global heuristics concerning all test data are also used. A limited discussion on documenting test input data, expected results, and actual results is included. Use, applicability, and possible expansions are covered briefly. Introduction of the method has similar difficulties to those experienced when introducing any disciplined technique into an area where discipline was previously lacking. The approach is felt to be easily modifiable and usable for types of systems other than the traditional business data processing ones for which it was originally developed. [ABSTRACT FROM AUTHOR]

This paper explores the testing complexity of several classes of programs, where the testing complexity is measured in terms of the number of test data required for demonstrating program correctness by testing. It is shown that even for very restrictive classes of programs, none of the commonly used test criteria, namely, having every statement, branch, and path executed at least once, is nearly sufficient to guarantee absence of errors. Based on the study of testing complexity, this paper proposes two new test criteria, one for testing a path and the other for testing a program. These new criteria suggest how to select test data to obtain confidence in program correctness beyond the requirement of having each statement, branch, or path tested at least once. [ABSTRACT FROM AUTHOR]

There are a number of practical difficulties in performing a path testing strategy for computer programs. One problem is in deciding which paths, out of a possible infinity, to use as test cases. A hierarchy of structural test metrics is suggested to direct the choice and to monitor the coverage of test paths. Another problem is that many of the chosen paths may be infeasible in the sense that no test data can ever execute them. Experience with the use of "allegations" to circumvent this problem and prevent the static generation of many infeasible paths is reported. [ABSTRACT FROM AUTHOR]

A hardware failure analysis technique adapted to software yielded three rules for generating test cases sensitive to code errors. These rules, and a procedure for generating these cases, are given with examples. Areas for further study are recommended. [ABSTRACT FROM AUTHOR]

This paper presents a testing strategy designed to detect errors in the control flow of a computer program, and the conditions under which this strategy is reliable are given and characterized. The control flow statements in a computer program partition the input space into a set of mutually exclusive domains, each of which corresponds to a particular program path and consists of input data points which cause that path to be executed. The testing strategy generates test points to examine the boundaries of a domain to detect whether a domain error has occurred, as either one or more of these boundaries will have shifted or else the corresponding predicate relational operator has changed. If test points can be chosen within ∈ of each boundary, under the appropriate assumptions, the strategy is shown to be reliable in detecting domain errors of magnitude greater than ∈. Moreover, the number of test points required to test each domain grows only linearly with both the dimensionality of the input space and the number of predicates along the path being tested. [ABSTRACT FROM AUTHOR]

In this paper various path cover problems, arising in program testing, are discussed. Dilworth's theorem for acyclic digraphs is generalized. Two methods for finding a minimum set of paths (minimum path cover) that covers the vertices (or the edges) of a digraph are given. To model interactions among code segments, the notions of required pairs and required paths are introduced. It is shown that finding a minimum path cover for a set of required pairs is NP-hard. An efficient algorithm is given for finding a minimum path cover for a set of required paths. Other constrained path problems are considered and their complexities are discussed. [ABSTRACT FROM AUTHOR]

This paper describes ASSIST-V, a software tool designed for use in the teaching of operating systems, file management, and ma- chine architecture courses. ASSIST-V is a program that provides an environment for the implementation, testing, and evaluation of systems software for the IBM 360 series machines. This capability is achieved by simulating all relevant aspects of the machine's architecture. In particular, ASSIST-V simulates interrupts, I/O channels, and I/O devices, as well as all IBM 360 machine instructions. In addition, ASSIST-V provides extensive debugging and statistics-gathering aids. [ABSTRACT FROM AUTHOR]

Two approaches to the study of program testing arc 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. [ABSTRACT FROM AUTHOR]

We propose a method of testing the correctness of control structures that can be modeled by a finite-state machine. Test results derived from the design are evaluated against the specification. No "executable" prototype is required. The method is based on a result in automata theory and can be applied to software testing. Its error- detecting capability is compared with that of other approaches. Application experience is summarized. [ABSTRACT FROM AUTHOR]

Randomized testing is an effective method for testing software units. The thoroughness of randomized unit testing varies widely according to the settings of certain parameters, such as the relative frequencies with which methods are called. In this paper, we describe Nighthawk, a system which uses a genetic algorithm (GA) to find parameters for randomized unit testing that optimize test coverage. Designing GAs is somewhat of a black art. We therefore use a feature subset selection (FSS) tool to assess the size and content of the representations within the GA. Using that tool, we can reduce the size of the representation substantially while still achieving most of the coverage found using the full representation. Our reduced GA achieves almost the same results as the full system, but in only 10 percent of the time. These results suggest that FSS could significantly optimize metaheuristic search-based software engineering tools. [ABSTRACT FROM AUTHOR]

We present an integrated method for program proving, testing, and debugging. Using the concept of metamorphic relations, we select necessary properties for target programs. For programs where global symbolic evaluation can be conducted and the constraint expressions involved can be solved, we can either prove that these necessary conditions for program correctness are satisfied or identify all inputs that violate the conditions. For other programs, our method can be converted into a symbolic-testing approach. Our method extrapolates from the correctness of a program for tested inputs to the correctness of the program for related untested inputs. The method supports automatic debugging through the identification of constraint expressions that reveal failures. [ABSTRACT FROM AUTHOR]