Metamorphic Fault Tolerance: An Automated and Systematic Methodology for Fault Tolerance in the Absence of Test Oracle
A system may fail due to an internal bug or a fault in its execution environment. Incorporating fault tolerance strategies enables such system to complete its function despite the failure of some of its parts. Prior to the execution of some fault tolerance strategies, failure detection is needed. Detecting incorrect output, for instance, assumes the existence of an oracle to check the correctness of program outputs given an input. However, in many practical situations, oracle does not exist or is extremely difficult to apply. Such an oracle problem is a major challenge in the context of software testing. In this paper, we propose to apply metamorphic testing, a software testing method that alleviates the oracle problem, into fault tolerance. The proposed technique supports failure detection without the need of oracles.
|
Huai Liu, Iman I. Yusuf, Heinz W. Schmidt, and Tsong Yueh Chen |
RMIT University, Australia; Swinburne University of Technology, Australia |
|
Software Bug Localization with Markov Logic
Software bug localization is the problem of determining buggy statements in a software system. It is a crucial and expensive step in the software debugging process. Interest in it has grown rapidly in recent years, and many approaches have been proposed. However, existing approaches tend to use isolated information to address the problem, and are often ad hoc. In particular, most existing approaches predict the likelihood of a statement being buggy sequentially and separately. This paper proposes a well-founded, integrated solution to the software bug localization problem based on Markov logic. Markov logic combines first-order logic and probabilistic graphical models by attaching weights to first-order formulas, and views them as templates for features of Markov networks. We show how a number of salient program features can be seamlessly combined in Markov logic, and how the resulting joint inference can be solved. We implemented our approach in a debugging system, called MLNDebugger, and evaluated it on 4 small programs. Our initial results demonstrated that our approach achieved higher accuracy than a previous approach.
|
Sai Zhang and Congle Zhang |
University of Washington, USA |
|
Steering Model-Based Oracles to Admit Real Program Behaviors
The oracle—an arbiter of correctness of the system under test (SUT)—is a major component of the testing process. Specifying oracles is particularly challenging for real-time embedded systems, where small changes in time or sensor inputs may cause large differences in behavior. Behavioral models of such systems, often built for analysis and simulation purposes, are naturally appealing for reuse as oracles. However, these models typically provide an idealized view of the system. Even when given the same inputs, the model’s behavior can frequently be at variance with some acceptable behavior of the SUT executing on a real platform. We therefore propose steering the model when used as an oracle, to admit an expanded set of behaviors when judging the SUT’s adherence to its requirements. On detecting a behavioral difference, the model is backtracked and then searched for a new state that satisfies certain constraints and minimizes a dissimilarity metric. The goal is to allow non-deterministic, but bounded, behavior differences while preventing future mismatches, by guiding the oracle—within limits—to match the execution of the SUT. Early experimental results show that steering significantly increases SUT-oracle conformance with minimal masking of real faults and, thus, has significant potential for reducing development costs.
|
Gregory Gay, Sanjai Rayadurgam, and Mats P. E. Heimdahl |
University of Minnesota, USA |
|
Shadow Symbolic Execution for Better Testing of Evolving Software
In this idea paper, we propose a novel way for improving the testing of program changes via symbolic execution. At a high-level, our technique runs two different program versions in the same symbolic execution instance, with the old version effectively shadowing the new one. In this way, the technique can exploit precise dynamic value information to effectively drive execution toward the behaviour that has changed from one version to the next. We discuss the main challenges and opportunities of this approach in terms of pruning and prioritising path exploration, mapping elements across versions, and sharing common symbolic state between versions.
|
Cristian Cadar and Hristina Palikareva |
Imperial College London, UK |
|
Leveraging P2P Networks to Address the Test Scenario Explosion Problem
The behaviour of software is influenced by whatever environment it happens to be deployed in. Achieving a sufficient level of coverage for all deployment scenarios during lab testing is difficult for even the most resources rich organisation. We refer to this as the Test Scenario Explosion Problem and propose the construction of a peer-to-peer network which facilitates the quick creation of large-scale virtual test labs that are representative of a company's customer base. Following an outline of our initial ideas in this regard, a number of open research challenges are discussed.
|
Mark Micallef, Conrad Attard, Andrea Mangion, and Sebastian Attard |
University of Malta, Malta |
|
A Framework to Advise Tests using Tests
Tests generated by different approaches can form a rich body of information about the system under test (SUT), which can then be used to amplify the power of test suites. Diversity in test representations, however, creates an obstacle to extracting and using this information. In this work, we introduce a test advice framework which enables extraction and application of information contained in existing tests to help improve other tests or test generation techniques. Our framework aims to 1) define a simple, yet expressive test case language so that different types of tests can be represented using a unified language, and 2) define an advice extraction function that enables the elicitation and application of the information encoded in a set of test cases. Preliminary results show how test advice can be used to generate amplified test suites with higher code coverage and improved mutants killed scores over the original test suite.
|
Yurong Wang, Suzette Person, Sebastian Elbaum, and Matthew B. Dwyer |
University of Nebraska-Lincoln, USA; NASA Langley Research Center, USA |