Summary Testing of concurrent programmes is difficult since the scheduling nondeterminism requires one to test a huge number of different thread interleavings. Moreover, repeated test executions that are performed in the same environment will typically examine similar interleavings only. One possible way how to deal with this problem is to use the noise injection approach, which influences the scheduling by injecting various kinds of noise (delays, context switches, etc) into the common thread behaviour. However, for noise injection to be efficient, one has to choose suitable noise injection heuristics from among the many existing ones as well as to suitably choose values of their various parameters, which is not easy. In this paper, we propose a novel way how to deal with the problem of choosing suitable noise injection heuristics and suitable values of their parameters (as well as suitable values of parameters of the programmes being tested themselves). Here, by suitable, we mean such settings that maximize chances of meeting a given testing goal (such as, eg, maximizing coverage of rare behaviours and thus maximizing chances to find rarely occurring concurrency‐related bugs). Our approach is, in particular, based on using data mining in the context of noise‐based testing to get more insight about the importance of the different heuristics in a particular testing context as well as to improve fully automated noise‐based testing (in combination with both random as well as genetically optimized noise setting).

Summary Testing of concurrent software written in programming languages like Java and C/C++ is a highly challenging task owing to the many possible interactions among threads. A simple, cheap, and effective approach that addresses this challenge is testing with noise injection , which influences the scheduling so that different interleavings of concurrent actions are witnessed. In this paper, multiple results achieved recently in the area of noise‐injection‐based testing by the authors are presented in a unified and extended way. In particular, various concurrency coverage metrics are presented first. Then, multiple heuristics for solving the noise placement problem (i.e. where and when to generate noise) as well as the noise seeding problem (i.e. how to generate the noise) are introduced and experimentally evaluated. In addition, several new heuristics are proposed and included into the evaluation too. Recommendations on how to set up noise‐based testing for particular scenarios are then given. Finally, a novel use of the genetic algorithm for finding suitable combinations of the many parameters of tests and noise techniques is presented. Copyright © 2014 John Wiley & Sons, Ltd.

Large systems generate immense quantities of code coverage data. A user faced with the task of analyzing this data, for example, to decide on test areas to improve, faces a 'needle in a haystack' problem.

Combinatorial testing is a specification based sampling technique that provides a systematic way to select combinations of program inputs or features for testing. It has been applied over the years to test input data, configurations, web forms, protocols, graphical user interfaces and for testing software product lines. This tutorial introduces the fundamentals of combinatorial testing, including both practical and theoretical foundations, to provide a comprehensive introduction that is relevant to both test practitioners and software engineering researchers. The tutorial will present an overview of Combinatorial Test Design (CTD) and describe some state of the art research advances and domains where CTD has been applied. It will present the theoretical underpinnings of CTD and explain a few algorithmic techniques used to generate CTD samples, as well as describe recent work on practical extensions to these algorithms that allow for a broader use of CTD. A session devoted to modeling test problems using CTD will follow, with attendees obtaining hands-on experience using several realistic problems.

Many service-oriented systems are not well equipped to guarantee that service time is optimized. We have specifically examined two industrial systems which implement service-oriented architectures in real, field environments. We discovered that both were not engineered to properly address surges in service request rate. In the absence of an integral solution, it is difficult and costly to (re-) engineer such a solution in the field. The challenge faced by this study was to deliver a low cost solution, without re-engineering the target systems. This paper introduces such a generic solution. The solution slows-down some components to deliver improvement in request service time. It was implemented, tested, and successfully applied to two industrial systems with no need to modify their logic or architecture. Experiments with those systems exhibited significant improvement in performance. These results have validated our solution and its industrial applicability across systems and environments.

Code coverage is a common aid in the testing process. It is generally used for marking the source code segments that were executed and, more importantly, those that were not executed.

We describe a version of review/inspection called selective homeworkless review. In these reviews, moderators are taught how to select artifacts for review and review methodologies with little or no preparation. Many review and inspection methodologies are known in the literature and used in industry with very good results. The main issue we faced was not how to tune an existing inspection methodology, but rather how to get people to seriously and continuously inspect their artifacts. With the shrinking of the release cycle, people try to avoid front-loaded methodologies such as reviews, which seem to waste time early on. This is true both at the organizational level, where the overall cost is considered and at the day-to-day level, where time for preparation needs to be found. Because the reasons for rejecting existing inspection techniques were more organizational than technical, the way our methodology overcomes these objections is as central to the paper as the selective homeworkless review methodology itself. We introduced selective homeworkless reviews three years ago. We now have convincing evidence that this methodology can be introduced even in organizations that are resistant to formal inspections, leading to significant improvements in quality.

PADTAD brings together researchers from academia and researchers and practitioners from industry to promote the development of techniques and tools that aid in testing, analysis, and debugging of multi-threaded/parallel/distributed software.

Concurrent computer programs are fast becoming prevalent in many critical applications. Unfortunately, these programs are especially difficult to test and debug. Recently, it has been suggested that injecting random timing noise into many points within a program can assist in eliciting bugs within the program. Upon eliciting the bug, it is necessary to identify a minimal set of points that indicate the source of the bug to the programmer. In this paper, we pose this problem as an active feature selection problem. We propose an algorithm called the iterative group sampling algorithm that iteratively samples a lower dimensional projection of the program space and identifies candidate relevant points. We analyze the convergence properties of this algorithm. We test the proposed algorithm on several real-world programs and show its superior performance. Finally, we show the algorithms' performance on a large concurrent program.

As concurrent and distributive applications are becoming more common and debugging such applications is very difficult, practical tools for automatic debugging of concurrent applications are in demand. In previous work, we applied automatic debugging to noise-based testing of concurrent programs. The idea of noise-based testing is to increase the probability of observing the bugs by adding, using instrumentation, timing to the execution of the program. The technique of finding a small subset of points that causes the bug to manifest can be used as an automatic debugging technique. Previously, we showed that Delta Debugging can be used to pinpoint the bug location on some small programs.In the work reported in this paper, we create and evaluate two algorithms for automatically pinpointing program locations that are in the vicinity of the bugs on a number of industrial programs. We discovered that the Delta Debugging algorithms do not scale due to the non-monotonic nature of the concurrent debugging problem. Instead we decided to try a machine learning feature selection algorithm. The idea is to consider each instrumentation point as a feature, execute the program many times with different instrumentations, and correlate the features (instrumentation points) with the executions in which the bug was revealed. This idea works very well when the bug is very hard to reveal using instrumentation, correlating to the case when a very specific timing window is needed to reveal the bug. However, in the more common case, when the bugs are easy to find using instrumentation points ranked high by the feature selection algorithm is not high enough. We show that for these cases, the important value is not the absolute value of the evaluation of the feature but the derivative of that value along the program execution path.As a number of groups expressed interest in this research, we built an open infrastructure for automatic debugging algorithms for concurrent applications, based on noise injection based concurrent testing using instrumentation. The infrastructure is described in this paper.

Abstract The primary difficulty with testing concurrent programs is their non‐determinism, where two executions with the same input can yield different results due to a changed thread schedule (also known as interleaving). This problem is aggravated by the fact that most thread schedulers are almost deterministic, and generate the same interleavings over and over for a given testing environment. The traditional approach to testing concurrent programs is to identify and examine the race conditions. A different solution involves noise‐making, which generates different interleavings at runtime, for example, using embedded sleep statements. This paper proposes a totally different technique for generating a rich set of interleavings. In this approach, operations on shared variables are tracked. Every time a shared variable is read, the value to be read is selected from the set of values that were held by this variable during the program execution. The algorithm identifies those values that the variable could hold in some interleaving consistent with the past observed events. Within this subset, the value choice can be random, biased‐random, based on coverage, etc. The problem of identifying read values that are consistent with the past observations is far from simple, since past decisions on value selection affect future ones. Our solution is computationally intensive and, therefore, impractical as is. However, insights gained from this solution lead to new heuristics for noise‐making. Copyright © 2006 John Wiley & Sons, Ltd.

Abstract Multi‐threaded code is becoming very common, both on the server side, and very recently for personal computers as well. Consequently, looking for intermittent bugs is a problem that is receiving more and more attention. As there is no silver bullet, research focuses on a variety of partial solutions. We outline a road map for combining the research within the different disciplines of testing multi‐threaded programs and for evaluating the quality of this research. We have three main goals. First, to create a benchmark that can be used to evaluate different solutions. Second, to create a framework with open application programming interfaces that enables the combination of techniques in the multi‐threading domain. Third, to create a focus for the research in this area around which a community of people who try to solve similar problems with different techniques can congregate. We have started creating such a benchmark and describe the lessons learned in the process. The framework will enable technology developers, for example, developers of race detection algorithms, to concentrate on their components and use other ready made components (e.g. an instrumentor) to create a testing solution. Copyright © 2006 John Wiley & Sons, Ltd.

Testing and Debugging (PADTAD

A noise maker is a tool that seeds a concurrent program with conditional synchronization primitives, such as yield(), for the purpose of increasing the likelihood that a bug manifest itself. We introduce a novel fault model that classifies locations as "good", "neutral", or "bad," based on the effect of a thread switch at the location. Using the model, we explore the terms under which an efficient search for real-life concurrent bugs can be conducted. We accordingly justify the use of probabilistic algorithms for this search and gain a deeper insight of the work done so far on noise- making. We validate our approach by experimenting with a set of programs taken from publicly available multi-threaded benchmarks. Our empirical evidence demonstrates that real-life behavior is similar to one derived from the model.

Coverage analysis is used to monitor the quality of the verification process. Reports provided by coverage tools' help users identify areas in the design that have not been adequately tested. Because of their sheer size, the analysis of large coverage models can be an intimidating and time-consuming task. This paper presents several techniques for coverage analysis. These techniques range from highly interactive and dynamic analysis that allows users to focus on certain aspects or areas of interest in the coverage model to fully automated coverage analysis, which identifies uncovered or lightly covered areas. The proposed techniques provide additional means for extracting relevant, useful information, thereby improving the quality of the coverage analysis. A number of examples show how the proposed method improved the verification of actual designs

Coverage analysis is a useful testing technology. However, some coverage models are more acceptable to the industry than others. In the field of testing multi-threaded applications, there is a need for a coverage model that can be used to evaluate tests for concurrent completeness and to find new testing requirements. We present a new coverage model: synchronization coverage. This model is simple to understand and the action items generated by each uncovered task are clear to testers and developers. We propose that synchronization coverage could, and should, become one of the more commonly used coverage models.

Random test generators are often used to create regression suites on-the-fly. Regression suites are commonly generated by choosing several specifications and generating a number of tests from each one, without reasoning which specification should be used and how many tests should be generated from each specification. This paper describes a technique for building high quality random regression suites. The proposed technique uses information about the probability of each test specification covering each coverage task. This probability is used, in turn, to determine which test specifications should be included in the regression suite and how many tests should be generated from each specification. Experimental results show that this practical technique can be used to improve the quality, and reduce the cost, of regression suites. Moreover, it enables better informed decisions regarding the size and distribution of the regression suites, and the risk involved.

Summary form only given. In previous work, we introduced the alternative pasts algorithm that delays the assignment of values to variables until their usage. Whenever a variable is used, the algorithm chooses one of its past values that is consistent with some possible execution. The alternative pasts algorithm can be seen as belonging to a class of algorithms that shadow the execution and choose at any point to modify the values of some of the variables. We build on this work and extend it in two directions. First we show a more powerful shadowing algorithm that can delay not only writes but also reads and other kinds of instructions, at most until a relevant control decision is taken, which is the longest possible delay for algorithms of this class. We prove that this algorithm inherits the ability of the alternative pasts algorithm to generate significantly different interleavings, which are guaranteed to execute differently. In addition, we show a new use for the two algorithms, namely alternative replay. Unlike regular replay, where the execution of the program is reproduced, alternative replay is an execution that did not happen before but could have happened. For example, if a bug did not materialize, alternative replay can be used to show the user alternative execution in which the impact of the bug can be observed.

Summary form only given. Testing multithreaded, concurrent, or distributed programs is acknowledged to be a very difficult task. We decided to create a benchmark of programs containing documented multithreaded bugs that can be used in the development of testing tool for the domain. In order to augment the benchmark with a sizable number of programs, we assigned students in a software testing class to write buggy multithreaded Java programs and document the bugs. This paper documents this experiment. We explain the task that was given to the students, go over the bugs that they put into the programs both intentionally and unintentionally, and show our findings. We believe this part of the benchmark shows typical programming practices, including bugs, of novice programmers. In grading the assignments, we used our technologies to look for undocumented bugs. In addition to finding many undocumented bugs, which was not surprising given that writing correct multithreaded code is difficult, we also found a number of bugs in our tools. We think this is a good indication of the expected utility of the benchmark for multithreaded testing tool creators.

Abstract Finding bugs due to race conditions in multi‐threaded programs is difficult, mainly because there are many possible interleavings, any of which may contain a fault. In this work we present a methodology for testing multi‐threaded programs which has minimal impact on the user and is likely to find interleaving bugs. Our method reruns existing tests in order to detect synchronization faults. We find that a single test executed a number of times in a controlled environment may be as effective in finding synchronization faults as many different tests. A great deal of resources are saved since tests are very expensive to write and maintain. We observe that simply rerunning tests, without ensuring in some way that the interleaving will change, yields almost no benefits. We implement the methodology in our test generation tool—ConTest. ConTest combines the replay algorithm, which is essential for debugging, with our interleaving test generation heuristics. ConTest also contains an instrumentation engine, a coverage analyzer, and a race detector (not finished yet) that enhance bug detection capabilities. The greatest advantage of ConTest, besides finding bugs of course, is its minimal effect on the user. When ConTest is combined into the test harness, the user may not even be aware that ConTest is being used. Copyright © 2003 John Wiley & Sons, Ltd.

One of the main goals of coverage tools is to provide the user with informative presentation of coverage information. Specifically, information on large, cohesive sets of uncovered tasks with common properties is very useful. This paper describes methods for discovering and reporting large uncovered spaces (holes) for crossproduct functional coverage models. Hole analysis is a presentation method for coverage data that is both succinct and informative. Using case studies, we show how hole analysis was used to detect large uncovered spaces and improve the quality of verification.

Test generation and simulation tools have input stimuli that can direct them to cover specific events. However, the cost of completely covering a verification plan is still very high. While coverage analysis tools can find events that have not been covered, they do not provide an automated covering method. This paper presents the first implementation of a generation framework that uses feedback from coverage analysis to direct microarchitecture simulation. This framework uses a coverage analysis tool to find events that have not been simulated and then utilizes information about the design to determine which directives should be given to the simulation environment. This paper describes, in detail, the system and its operation process, an experiment that uses the system, and the results of the experiment. This system was shown to reduce the machine time and person time required to cover the test plan. Implications of this work suggest the types of verification plans appropriate for the utilization of this system and the further experiments and developments required.

In this paper, we demonstrate a method for generation of assembler test programs that systematically probe the micro architecture of a PowerPC superscalar processor.We show innovations such as ways to make small models for large designs, predict, with cycle accuracy the movement of instructions through the pipes (taking into account stalls and dependencies) and generation of test programs such that each reaches a new micro architectural state.We compare our method to the established practice of massive random generation and show that the quality of our tests, as measured by transition coverage, is much higher.The main contribution of this paper is not in theory, as the theory has been discussed in previous papers, but in describing how to translate this theory into practice in a practical way, a task that was far from trivial.

This paper describes a new coverage methodology developed at IBM's Haifa Research Lab. The main idea behind the methodology is a separation of the coverage model definition from the coverage analysis tool. This enables the user to define the coverage models that best fit the points of significance in the design, and still have the benefits of a coverage tool. To support this methodology, we developed a new coverage measurement tool called Comet. The tool is currently used in many domains, such as system verification and micro-architecture verification, and in many types of designs ranging from systems, to microprocessors, and ASICs.

Testing is one of the biggest problems of the software industry. Coverage is the main technique for showing that the testing has been thorough. Coverage can be used to find a good regression suite, i.e. a set of tests that is run on the application after sofware or data changes in order to check that no new bugs were introduced. This paper is about the experience gained in IBM Haifa Research Lab (HRL) in creating regression suites and minimizing their size, while maintaining high quality as measured in coverage. The problem we solve, while similar to the one addressed in the literature, has a key difference; the compaction algorithm is implemented online due to the large number of tests processed. We compare strategies for implementing online set-cover. The trade-offs are between the solution quality (as expressed by the size of the cover), the size of the intermediate sets and the computational resources. We show that it is possible to start discarding tests very early without getting a significantly larger final set.