A common problem for developers is applications exhibiting new bugs after deployment. Many of these bugs can be traced to unexpected network, operating system, and file system differences that cause program executions that were successful in a development environment to fail once deployed. Preventing these bugs is difficult because it is impractical to test an application in every environment. Enter Simulating Environmental Anomalies (SEA), a technique that utilizes evidence of one application's failure in a given environment to generate tests that can be applied to other applications, to see whether they suffer from analogous faults. In SEA, models of unusual properties extracted from interactions between an application, A, and its environment guide simulations of another application, B, running in the anomalous environment. This reveals faults B may experience in this environment without the expense of deployment. By accumulating these anomalies, applications can be tested against an increasing set of problematic conditions. We implemented a tool called CrashSimulator, which uses SEA, and evaluated it against Linux applications selected from coreutils and the Debian popularity contest. Our tests found a total of 63 bugs in 31 applications with effects including hangs, crashes, data loss, and remote denial of service conditions.

Prior work has shown that extremely small code patterns, such as the conditional operator and implicit type conversion, can cause considerable misunderstanding in programmers. Until now, the real world impact of these patterns - known as 'atoms of confusion' - was only speculative. This work uses a corpus of 14 of the most popular and influential open source C and C++ projects to measure the prevalence and significance of these small confusing patterns. Our results show that the 15 known types of confusing micro patterns occur millions of times in programs like the Linux kernel and GCC, appearing on average once every 23 lines. We show there is a strong correlation between these confusing patterns and bug-fix commits as well as a tendency for confusing patterns to be commented. We also explore patterns at the project level showing the rate of security vulnerabilities is higher in projects with more atoms. Finally, we examine real code examples containing these atoms, including ones that were used to find and fix bugs in our corpus. In total this work demonstrates that beyond simple misunderstanding in the lab setting, atoms of confusion are both prevalent - occurring often in real projects, and meaningful - being removed by bug-fix commits at an elevated rate.

This paper presents empirical studies of test effectiveness for Java database applications. We primarily address two research questions: (1) What is the relationship between test set size, coverage criteria, and test effectiveness for Java/JDBC programs? (2) Which adequacy criterion is more suitable for testing Java database applications, statement coverage, branch coverage, or command form coverage? We collected data sets by experimenting on several moderately complex open source database application programs, and performed a series of rigorous and comprehensive statistical analyses. The results show that linear models fit the relationship of size and coverage to effectiveness well and that coverage appears to have greater impact on effectiveness than size. However, surprisingly, command form coverage was not consistently more effective than statement or branch coverage.

Several recent research projects have developed new testing techniques targeted to database application programs, a widely used class of programs with some unique characteristics. Mutation testing, focused on interactions between an application and a database, presents a promising approach to evaluating test adequacy and to evaluating the effectiveness of other test generation and test adequacy criteria. Prior work on database application mutation techniques has focused exclusively on SELECT statements, which extract data without modifying the database state. Extending the techniques to updating statements, INSERT, DELETE, and UPDATE, is challenging because it's necessary to compare the behavior of mutants when executed against the same database state, but each mutant execution changes the database state. This paper presents inferential checking, a new technique for determining whether mutants of an updating statement are killed, without actually executing the mutants. Queries are automatically derived from updating statements and their mutants, characterizing the state change that would occur if the statement were executed. Results of these queries are compared to determine which mutants are killed. The paper presents the technique, its implementation for Java/JDBC applications, and empirical evaluation demonstrating that it is efficient, precise, and useful.

Abstract Database application programs are ubiquitous; hence, good techniques for testing them are needed. Several approaches to testing database applications have been proposed recently, including test generation techniques and adequacy criteria. Tuyaet al.proposed mutation‐based adequacy criteria for database queries and developed a set of mutation operators for Structured Query LanguageSELECTstatements. This paper extends that approach by integrating it with analysis and instrumentation of the application bytecode. The design and implementation of a tool, Java Database Application Mutation Analyser (JDAMA), are described. JDAMA instruments application bytecode so as to compare the results of queries executed by the application under test to the results of mutants of those queries. JDAMA can be used to support mutation testing for Java database applications. A second, potentially more useful application of JDAMA is to support experiments evaluating testing techniques for database applications, in which query mutation is used to seed faults into subject applications. The paper illustrates these uses of JDAMA with experiments comparing two approaches to test generation and experiments evaluating coverage criteria. Copyright © 2011 John Wiley & Sons, Ltd.

Database application programs are ubiquitous, so good techniques for testing them are needed. Recently, several research groups have proposed new approaches to generating tests for database applications and for assessing test data adequacy. This paper describes a mutation testing tool, JDAMA (Java Database Application Mutation Analyzer), for Java programs that interact with a database via the JDBC interface. Our approach extends the mutation testing approach for SQL by Tuya et al, by integrating it with analysis and instrumentation of the application bytecode. JDAMA's use is illustrated through a small study which uses mutation scores to compare two test generation techniques for database applications.

We describe the use of property-based peer trust to provide security in Sleeper, a new energy-efficient service discovery protocol which uses proxied advertisement and discovery to dynamically offload service discovery workload from power-limited devices. Property-based digital certificates have previously been used in trust-negotiation methods. In earlier work we developed a new method for secure and private peer-to-peer trust negotiation using property-based digital certificates and a secure trust negotiation agent. Here we describe how property-based peer trust can be used to secure the Sleeper service discovery protocol

The design of service discovery protocols which limit power consumption of devices has received little consideration but is an important problem because of the growing use of power-limited mobile networked devices. We describe Sleeper, a new discovery protocol which uses proxied advertisement and discovery to dynamically offload service discovery workload from power-limited devices. The advertisement structure supports several modes of service discovery including conventional service advertisements, meta discovery, taxonomic-based discovery, location-based discovery and federated discovery. In addition, Sleeper supports both push and pull modes of advertisement, but unlike other protocols uses service popularity to select push or pull modality. We describe an implementation of the new protocol and provide an analytical model for comparing response time to other push-based service discovery methods.

AGENDA is a tool set for testing relational database applications. An earlier prototype was targeted to applications consisting of a single query and included components for populating a database with data suitable for testing the application, generating inputs to the query, and checking relatively simple aspects of the results of executing the query. This paper describes substantial extensions to AGENDA, allowing it to test transactions with multiple queries and with complex intended behavior. The paper introduces a technique for checking complex properties of the database state transition performed by the transaction under test, as well as an improved input generation heuristic. Results of using AGENDA to test three applications with seeded faults are presented.

Abstract Database systems play an important role in nearly every modern organization, yet relatively little research effort has focused on how to test them. This paper discusses issues arising in testing database systems, presents an approach to testing database applications, and describes AGENDA, a set of tools to facilitate the use of this approach. In testing such applications, the state of the database before and after the user's operation plays an important role, along with the user's input and the system output. A framework for testing database applications is introduced. A complete tool set, based on this framework, has been prototyped. The components of this system are a parsing tool that gathers relevant information from the database schema and application, a tool that populates the database with meaningful data that satisfy database constraints, a tool that generates test cases for the application, a tool that checks the resulting database state after operations are performed by a database application, and a tool that assists the tester in checking the database application's output. The design and implementation of each component of the system are discussed. The prototype described here is limited to applications consisting of a single SQL query. Copyright © 2004 John Wiley & Sons, Ltd.

Database application programs are often designed to be executed concurrently by many users. By grouping related database queries into transactions, DBMS (database management system) can guarantee that each transaction satisfies the well-known ACID properties: atomicity, consistency, isolation, and durability. However, if a database application is decomposed into transactions in an incorrect manner, the application may fail when executed concurrently due to potential offline concurrency problems. This paper presents a dataflow analysis technique for identifying schedules of transaction execution aimed at revealing concurrency faults of this nature, along with techniques for controlling the DBMS or the application so that execution of transaction sequences follows generated schedules. The techniques have been integrated into AGENDA, a tool set for testing relational database application programs. Preliminary empirical evaluation is presented.

Database systems play an important role in nearly every modern organization, yet relatively little research effort has focused on how to test them. This paper discusses issues arising in testing database systems and presents an approach to testing database applications. In testing such applications, the state of the database before and after the user's operation plays an important role, along with the user's input and the system output. A tool for populating the database with meaningful data that satisfy database constraints has been prototyped. Its design and its role in a larger database application testing tool set are discussed.

Many analytical and empirical studies of software testing effectiveness have used the probability that a test set exposes at least one fault as the measure of effectiveness. That measure is useful for evaluating testing techniques when the goal of testing is to gain confidence that the program is free from faults. However, if the goal of testing is to improve the reliability of the program (by discovering and removing those faults that are most likely to cause failures when the software is in the field) then the measure of test effectiveness must distinguish between those faults that are likely to cause failures and those that are unlikely to do so. Delivered reliability was previously introduced as a means of comparing testing techniques in that setting. This paper empirically compares reliability delivered by three testing techniques, branch testing, the all-uses data flow testing criterion, and operational testing. The subject program is a moderate-sized C-program (about 10,000 LOC) produced by professional programmers and containing naturally occurring faults.

This paper describes a new approach to performing data flow testing in the presence of aliasing, and a tool based on this method. The technique is based on the observation that, under certain reasonable assumptions, one can statically determine which variables are aliased whenever control reaches a given program point via a particular path. Furthermore, one can group together paths that behave similarly with respect to aliasing and represent them by regular expressions. The resulting test requirements demand that the test data execute representatives of particular sets of paths between variable definitions and uses. Copyright © 1999 John Wiley & Sons, Ltd.

Regression testing is a commonly used activity whose purpose is to determine whether the modifications made to a software system have introduced new faults. Textual differencing is a new, safe and fairly precise, selective regression testing technique that works by comparing source files from the old and the new version of the program. We have implemented the textual differencing technique in a tool called Pythia. Pythia has been developed primarily through the integration of standard, well known UNIX programs, and is capable of analyzing large software systems written in C. We present results from a case study involving a software system of approximately 11,000 lines of source code written for the European Space Agency. The results provide empirical evidence that textual differencing is very fast and capable of achieving substantial reductions in the size of the regression test suite.

This paper reports on an empirical evaluation of the fault-detecting ability of two white-box software testing techniques: decision coverage (branch testing) and the all-uses data flow testing criterion. Each subject program was tested using a very large number of randomly generated test sets. For each test set, the extent to which it satisfied the given testing criterion was measured and it was determined whether or not the test set detected a program fault. These data were used to explore the relationship between the coverage achieved by test sets and the likelihood that they will detect a fault.Previous experiments of this nature have used relatively small subject programs and/or have used programs with seeded faults. In contrast, the subjects used here were eight versions of an antenna configuration program written for the European Space Agency, each consisting of over 10,000 lines of C code.For each of the subject programs studied, the likelihood of detecting a fault increased sharply as very high coverage levels were reached. Thus, this data supports the belief that these testing techniques can be more effective than random testing. However, the magnitudes of the increases were rather inconsistent and it was difficult to achieve high coverage levels.

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.

The effectiveness of a test data adequacy criterion for a given program and specification is the probability that a test set satisfying the criterion will expose a fault. Experiments were performed to compare the effectiveness of the mutation testing and all-uses test data adequacy criteria at various coverage levels, for randomly generated test sets. Large numbers of test sets were generated and executed, and for each, the proportion of mutants killed or def-use associations covered was measured. This data was used to estimate and compare the effectiveness of the criteria. The results were mixed: at the highest coverage levels considered, mutation was more effective than all-uses for five of the nine subjects, all-uses was more effective than mutation for two subjects, and there was no clear winner for two subjects. However, mutation testing was much more expensive than all-uses. The relationship between coverage and effectiveness for fixed-sized test sets was also explored and was found to be nonlinear and, in many cases, nonmonotonic.

This paper describes a new approach to performing data flow testing on programs that use pointer variables and a tool based on this approach. Our technique is based on the observation that, under certain reasonable assumptions, we can determine which dereferenced pointers are aliased whenever control reaches a given program point via a particular path. Furthermore, we can group together paths which behave similarly and represent them by regular expressions. The resulting test requirements demand that the test data execute representatives of particular sets of paths between variable definitions and uses.

We consider communication structures for event ordering algorithms in distributed environments where information flows only in one direction. Example applications are multilevel security and hierarchically decomposed databases. Although the most general one directional communication structure is a partial order, partial orders do not enjoy the property of being consistently ordered, a formalization of the notion that local ordering decisions are ensured to be globally consistent. Our main result is that the crown free property is necessary and sufficient for a communication structure to be consistently ordered. We discuss the computational complexity of detecting crowns and sketch typical applications.

This article describes a new approach to the unit testing of object-oriented programs, a set of tools based on this approach, and two case studies. In this approach, each test case consists of a tuple of sequences of messages, along with tags indicating whether these sequences should put objects of the class under test into equivalent states and/or return objects that are in equivalent states. Tests are executed by sending the sequences to objects of the class under test, then invoking a user-supplied equivalence-checking mechanism. This approach allows for substantial automation of many aspects of testing, including test case generation, test driver generation, test execution, and test checking. Experimental prototypes of tools for test generation and test execution are described. The test generation tool requires the availability of an algebraic specification of the abstract data type being tested, but the test execution tool can be used when no formal specification is available. Using the test execution tools, case studies involving execution of tens of thousands of test cases, with various sequence lengths, parameters, and combinations of operations were performed. The relationships among likelihood of detecting an error and sequence length, range of parameters, and relative frequency of various operations were investigated for priority queue and sorted-list implementations having subtle errors. In each case, long sequences tended to be more likely to detect the error, provided that the range of parameters was sufficiently large and likelihood of detecting an error tended to increase up to a threshold value as the parameter range increased.

Several relationships between software testing criteria, each induced by a relation between the corresponding multisets of subdomains, are examined. The authors discuss whether for each relation R and each pair of criteria, C/sub 1/ and C/sub 2/, R(C/sub 1/, C/sub 2/) guarantees that C/sub 1/ is better at detecting faults than C/sub 2/ according to various probabilistic measures of fault-detecting ability. It is shown that the fact that C/sub 1/ subsumes C/sub 2/ does not guarantee that C/sub 1/ is better at detecting faults. Relations that strengthen the subsumption relation and that have more bearing on fault-detecting ability are introduced.>

An experiment comparing the effectiveness of the all-uses and all-edges test data adequacy criteria is discussed. The experiment was designed to overcome some of the deficiencies of previous software testing experiments. A large number of test sets was randomly generated for each of nine subject programs with subtle errors. For each test set, the percentages of executable edges and definition-use associations covered were measured, and it was determined whether the test set exposed an error. Hypothesis testing was used to investigate whether all-uses adequate test sets are more likely to expose errors than are all-edges adequate test sets. Logistic regression analysis was used to investigate whether the probability that a test set exposes an error increases as the percentage of definition-use associations or edges covered by it increases. Error exposing ability was shown to be strongly positively correlated to percentage of covered definition-use associations in only four of the nine subjects. Error exposing ability was also shown to be positively correlated to the percentage of covered edges in four different subjects, but the relationship was weaker.>

This paper compares the fault-detecting ability of several software test data adequacy criteria. It has previously been shown that if C/sub 1/ properly covers C/sub 2/, then C/sub 1/ is guaranteed to be better at detecting faults than C/sub 2/, in the following sense: a test suite selected by independent random selection of one test case from each subdomain induced by C/sub 1/ is at least as likely to detect a fault as a test suite similarly selected using C/sub 2/. In contrast, if C/sub 1/ subsumes but does not properly cover C/sub 2/, this is not necessarily the case. These results are used to compare a number of criteria, including several that have been proposed as stronger alternatives to branch testing. We compare the relative fault-detecting ability of data flow testing, mutation testing, and the condition-coverage techniques, to branch testing, showing that most of the criteria examined are guaranteed to be better than branch testing according to two probabilistic measures. We also show that there are criteria that can sometimes be poorer at detecting faults than substantially less expensive criteria.>

The authors extend the definitions of the previously introduced family of data flow testing criteria to apply to programs written in a large subset of Pascal. They then define a family of adequacy criteria called feasible data flow testing criteria, which are derived from the data-flow testing criteria. The feasible data flow testing criteria circumvent the problem of nonapplicability of the data flow testing criteria by requiring the test data to exercise only those definition-use associations which are executable. It is shown that there are significant differences between the relationships among the data flow testing criteria and the relationships among the feasible data flow testing criteria. The authors discuss a generalized notion of the executability of a path through a program unit. A script of a testing session using their data flow testing tool, ASSET, is included.>