We present a spectrum-based, sequential software debugging approach coined Sequoia, that greedily selects tests out of a suite of tests to narrow down the set of diagnostic candidates with a minimum number of tests. Sequoia handles multiple faults, that can be intermittent, at polynomial time and space complexity, due to a novel, approximate diagnostic entropy estimation approach, which considers the subset of diagnoses that cover almost all Bayesian posterior probability mass. Synthetic experiments show that Sequoia achieves much better diagnostic uncertainty reduction compared to random test sequencing.Real programs, taken from the Software Infrastructure Repository, confirm Sequoia's better performance, with a test reduction up to 80% compared to random test sequences.

In practically all development processes tests are used to detect the presence of faults. This is not an exception for critical and high-availability systems. However, these systems cannot be taken offline or duplicated for testing in some cases. This makes runtime testing necessary. This paper presents work aimed at optimizing the three main sources of testing cost: preparation, execution and diagnosis. First, preparation cost is optimized by defining a metric of the runtime testability of the system, used to elaborate an implementation plan of preparative work for runtime testing. Second, the interrelated nature of test execution cost and diagnostic cost is highlighted and a new diagnostic test prioritization is introduced.

In practically all development processes, regression tests are used to detect the presence of faults after a modification. If faults are detected, a fault localization algorithm can be used to reduce the manual inspection cost. However, while using test case prioritization to enhance the rate of fault detection of the test suite (e.g., statement coverage), the diagnostic information gain per test is not optimal, which results in needless inspection cost during diagnosis. We present RAPTOR, a test prioritization algorithm for fault localization, based on reducing the similarity between statement execution patterns as the testing progresses. Unlike previous diagnostic prioritization algorithms, RAPTOR does not require false negative information, and is much less complex. Experimental results from the Software Infrastructure Repository's benchmarks show that RAPTOR is the best technique under realistic conditions, with average cost reductions of 40% with respect to the next best technique, with negligible impact on fault detection capability.

SUMMARY During regression testing, test prioritization techniques select test cases that maximize the confidence on the correctness of the system when the resources for quality assurance (QA) are limited. In the event of a test failing, the fault at the root of the failure has to be localized, adding an extra debugging cost that has to be taken into account as well. However, test suites that are prioritized for failure detection can reduce the amount of useful information for fault localization. This deteriorates the quality of the diagnosis provided, making the subsequent debugging phase more expensive, and defeating the purpose of the test cost minimization. In this paper we introduce a new test case prioritization approach that maximizes the improvement of the diagnostic information per test. Our approach minimizes the loss of diagnostic quality in the prioritized test suite. When considering QA cost as a combination of testing cost and debugging cost, on our benchmark set, the results of our test case prioritization approach show reductions of up to 60% of the overall combined cost of testing and debugging, compared with the next best technique. Copyright © 2011 John Wiley & Sons, Ltd.

Test cost minimisation approaches have traditionally been devoted to minimising ``execution costs'', while maximising coverage or reliability. However, in a runtime testing context, the amount of coverage or reliability that can be achieved, in other words, the system's Runtime Testability, is limited by the adverse effects that the interferences of runtime tests have on the system. Supporting runtime testing, therefore, introduces an additional cost in ``preparatory'' activities in software, (e.g., testable components) and in hardware (e.g., more memory), before certain runtime tests can be executed. In this paper we present a low-complexity, cost minimisation algorithm for the optimal selection of preparation activities, based on a near-optimal trade-off between preparation cost and a structure-based measurement of Runtime Testability, coined the Runtime Testability Metric (RTM). We perform a theoretical and empirical validation of RTM, showing that RTM is indeed a valid, and reasonably accurate measurement with ratio scale. We also present empirical data demonstrating the near-optimal performance at a low computational cost of our algorithm.