Project topics and materials
Get Complete Project Material File(s) Now! »
Automatic Analysis and Improved Software Resilience
We define in Section 3.1.1 two exceptions contracts applicable to try-catch blocks. We then describe an algorithm (see Section 3.1.2) and formal predicates (see Section 3.1.3) to verify those contracts according to a test suite. Finally we present the concept of catch stretching, a technique to improve the resilience of software applications against exceptions (see Sec-tion 3.1.4). The insight behind our approach is that we can use test suites as an oracle for the resilience capabilities against unanticipated errors.
Source Independence Contract
Motivation When a harmful exception occurs during testing or production, a developer has two possibilities. One way is to avoid the exception to be thrown by fixing its root cause (e.g. by inserting a not null check to avoid a null pointer exception). The other way is to write a try block surrounding the code that throws the exception. The catch block ending the try block defines the recovery mechanism to be applied when this exception occurs. The catch block responsibility is to recover from the particular encountered exception. By construction, the same recovery would be applied if another exception of the same type occurs within the scope of the try block at a different location.
This motivates the source-independence contract: the normal recovery behavior of the catch block must work for the foreseen exceptions; but beyond that, it should also work for exceptions that have not been encountered but may arise in a near future. We define a novel exception contract, that we called “source-independence” as follows:
Definition A try-catch is source-independent if the catch block proceeds equivalently, what-ever the source of the caught exception is in the try block. For now, we loosely define “proceeds equivalently”: if the system is still in error, it means that the error kind is the same; if the system has recovered, it means that the available func-tionalities are the same. Section 3.1.3 gives a formal definition. For example, Listing 3.1 shows a try-catch that satisfies the source-independence contract. If a value is missing in the application, and exception is thrown and the method returns a default value “missing property ». The code of the catch block (only one return statement) clearly does not depend on the application state. The exception can be thrown by any of the 3 statements in the try, and the result will still be the same.
On the contrary, Listing 3.2 shows a try-catch that violates the source-independence con-tract. Indeed, the result of the catch process depends on the value of isCacheActivated. If the first statement fails (throws an exception), the variable isCacheActivated is false, then an exception is thrown. If the first statement passes but the second one fails, isCacheActivated can be true, then the value missing property is returned. The result of the execution of the catch depends on the state of the program when the catch begins (here it depends on the value of the isCacheActivated variable). In case of failure, a developer cannot know if she will have to work with a default return value or with an exception. This catch is indeed source-dependent. Discussion How can it happen that developers write source-dependent catch blocks? Developers discover some exception risks at the first run-time occurrence of an exception at a particular location. In this case, the developer adds a try-catch block and puts the ex-ception raising code in the try body. Often, the try body contains more code than the prob-lematic statement in order to avoid variable scope and initialization problems. However, while implementing the catch block, the developer still assumes that the exception can only be thrown by the problematic statement, and refers to variables that were set in previous statements in the try block. In other words, the catch block is dependent on the application state at the problematic statement. If the exception comes from the problematic statement, the catch block works, if not, it fails to provide the expected recovery behavior. We will present a formal definition of this contract and an algorithm to verify it in Section 3.1.3. We will show that both source-independent and source-dependent catch blocks exist in practice in Section 3.2.
Pure Resilience Contract
Motivation In general, when an error occurs, it is more desirable to recover from this error than to stop or crash. A good recovery consists in returning the expected result despite the error and in continuing the program execution. One way to obtain the expected result under error is to be able to do the same task in a way that, for the same input, does not lead to an error but to the expected result. Such an alternative is sometimes called “plan B”. In terms of exception, recovering from an exception with a plan B means that the corresponding catch contains the code of this plan B. The “plan B » performed by the catch is an alternative to the “plan A » which is implemented in the try block. Hence, the contract of the try-catch block (and not only the catch or only the try) is to correctly perform a task T under consideration whether or not an exception occurs. We refer to this contract as the “pure resilience » contract. A “pure resilience” contract applies to try-catch blocks. We define it as follows: Definition A try-catch is purely resilient if the system state is equivalent at the end of the try-catch execution whether or not an exception occurs in the try block.
By system state equivalence, we mean that the effects of the plan A on the system are similar to those of plan B from a given observation perspective. If the observation perspec-tive is a returned value, the value from plan A is semantically equivalent to the value of plan B (e.g. satisfies an “equals” predicate method in Java).
For example, Listing 3.3 shows a purely resilient try-catch where a value is required, the program tries to access this value in the cache. If the program does not find this value, it retrieves it from a file. Usages There are different use cases of purely resilient try-catch blocks. We have pre-sented in Listing 3.3 the use case of caching for pure resilience. One can use purely resilient try-catch blocks for performance reasons: a catch block can be a functionally equivalent yet slower alternative. The efficient and more risky implementation of the try block is tried first, and in case of an exception, the catch block takes over to produce a correct result. Option-ality is another reason for pure resilience. Whether or not an exception occurs during the execution of an optional feature in a try block, the program state is valid and allows the execution to proceed normally after the execution of the try-block.
Discussion The difference between source-independence and pure resilience is as fol-lows. Source-independence means that under error the try-catch has always the same ob-servable behavior. In contrast, pure resilience means that in nominal mode and under error the try-catch block has always the same observable behavior. This shows that pure-resilience subsumes source-independence: by construction, purely resilient catch blocks are source-independent. The “pure resilience » contract is a loose translation of the concept of recovery block [82] in mainstream programming languages. We will present a formal definition of this contract and an algorithm to verify it in Section 3.1.3. Although the “pure resilience » contract is strong, we will show in Section 3.2 that we observe purely resilient try-catch blocks in reality, without any dedicated search: the dataset under consideration has been set up independently of this concern.
We presented the source independence and pure resilience contracts. Note that these contracts are not meant to be mandatory. The try-catch blocks can satisfy one, both, or none. We only argue that satisfying them is better from the viewpoint of resilience.
Output of Short-circuit Testing
The output of our short-circuit testing algorithm is a matrix M which represents the result of each test case under injection (for each try-catch). M is a matrix of boolean values where each row represents a try-catch block, and each column represents a test case. A cell in the matrix indicates whether the test case passes with exception injection in the corresponding try-catch. This matrix is used to evaluate the exception contract predicates described next in Sec-tion 3.1.3. Short-circuit testing is performed with source code transformations. Monitoring and fault injection code is added to the application under analysis. Listing 3.4 illustrates how this is implemented. The injected code is able to throw an exception in a context dependent manner. The injector is driven by an exception injection controller at runtime.
Resilience Predicates
We now describe four predicates that are evaluated on each row of the matrix to assess whether: the try-catch is source-independent (contract satisfaction), the try-catch is source-dependent (contract violation), the try-catch is purely-resilient (contract satisfaction), the try-catch is not purely-resilient (contract violation). As hinted here, there is no one single predicate p for which contract[x] = p[x] and :contract[x] = :p[x]. For both contracts, there are some cases where the short-circuit testing procedure yields not enough data to decide whether the contract is satisfied or violated. The principle of the excluded third (principium tertii exclusi) does not apply in our case.
Table of contents :
1 Introduction
1.1 Context
1.2 Thesis Contribution
1.3 Outline
1.4 Publications
2 State of the art
2.1 Definitions
2.1.1 Exception
2.1.2 Resilience
2.1.3 Specifications and Test Suites
2.2 Exception Handling
2.2.1 Static Analysis
2.2.2 Dynamic Analysis
2.2.3 Using Fault Injection
2.3 Debugging and Understanding
2.3.1 General Debugging
2.3.2 Exception Debugging
2.3.3 Fault Detection and Localization
2.4 Bug Fixing and Tolerance
2.4.1 Bug Fixing
2.4.2 Bug Tolerance
2.5 Resilience
2.6 Proposed Improvements on Exception Handling
2.7 Summary
3 Analyzing and Improving Software Resilience against Unanticipated Exceptions
3.1 Automatic Analysis and Improved Software Resilience
3.1.1 Definition of Two Contracts for Exception Handling
3.1.2 The Short-circuit Testing Algorithm
3.1.3 Resilience Predicates
3.1.4 Improving Software Resilience with Catch Stretching
3.2 Empirical Evaluation
3.2.1 Dataset
3.2.2 Relevance of Contracts
3.2.3 Catch Stretching
3.2.4 Summary
3.3 Discussion
3.3.1 Injected Exceptions
3.3.2 Relevance of Exception Contracts for Single-Statement Try Blocks
3.3.3 Try Scope Decrease
3.3.4 Threats to Validity
3.3.5 Fault Injection
3.4 Conclusion
4 Improving Dynamic Analysis with Automatic Test Suite Refactoring
4.1 Background and Motivation
4.1.1 Pitfall of Repairing Real-World Bugs
4.1.2 Automatic Software Repair with Nopol
4.1.3 Real-World Example: Apache Commons Math
4.2 Test Suite Refactoring
4.2.1 Basic Concepts
4.2.2 B-Refactoring – A Test Suite Refactoring Approach
4.2.3 Implementation
4.3 Empirical Study on Test Suite Refactoring
4.3.1 Projects
4.3.2 Empirical Observation on Test Case Purity
4.3.3 Empirical Measurement of Refactoring Quality
4.3.4 Mutation-based Validation for Refactored Test Suites
4.4 Improving Dynamic Analysis Using Test Suite Refactoring
4.4.1 Test Suite Refactoring for Automatically Repairing Three Bugs
4.4.2 Test Suite Refactoring for Exception Contract Analysis
4.5 Threats to Validity
4.6 Discussion
4.7 Conclusion
5 Casper: Debugging Null Dereferences with Ghosts and Causality Traces
5.1 Null Debugging Approach
5.1.1 Null Dereference Causality Trace
5.1.2 Null Ghosts
5.1.3 Casper’s Transformations
5.1.4 Semantics Preservation
5.1.5 Implementation
5.2 Empirical Evaluation
5.2.1 Dataset
5.2.2 Methodology
5.2.3 Results
5.2.4 Causality Trace and Patch
5.2.5 Threats to Validity
5.3 Conclusion
6 NpeFix: Tolerating Null Dereference at Runtime with Test Suite Validation
6.1 Concepts
6.1.1 Detecting Null Dereference Bugs
6.1.2 Tolerating
6.1.3 Viability
6.2 Methodology
6.2.1 Detection
6.2.2 Tolerance
6.3 Evaluation
6.3.1 Dataset
6.3.2 Overall Efficiency
6.3.3 Replacement Efficiency
6.3.4 Skipping Efficiency
6.4 Discussion
6.4.1 Limitations
6.4.2 False Positive Cases
6.4.3 Typing
6.4.4 Value Creation or Reuse
6.5 Conclusion
7 Conclusion
7.1 Summary
7.2 Perspectives
7.2.1 Study of Exception Errors
7.2.2 Repair
7.2.3 Resilience
Bibliography
