Contents 2 Figures 4 Abstract 5 Chapter 1 Introduction 7 1.1 Testing and Debugging 7 1.2 Concurrent Programs 8 1.2.1 Repeat Execution and Nondeterministic Behavior 10 1.2.2 Probe Effect 12 1.3 Difficulties of Testing Concurrent Programs 12 1.3 Reachability Testing 13 1.3.1 Problems When Dealing with Busy-Waiting Loops 14 1.4 Organization of Thesis 15 Chapter 2 Reachability Testing and Busy-Waiting Loops 16 2.1 Terminologies used in Reachability Testing 16 2.2 Taxonomy of Busy-Waiting Loops 17 2.2.1 Deadlock 18 2.2.2 Livelock 19 2.3 Inside Reachability Testing 20 2.3.1 An Example 20 2.4 Problems When Reachability Testing Dealing with Loops 21 Chapter 3 Spontaneous Locating of Infinite Loops 23 3.1 Target Model 23 3.1.1 Structure of Loop Statements 23 3.1.2 Abstract of the Algorithms 24 3.2 A New Monitor Protocol of Reachability Testing 24 3.2.1 Details of Implementation 24 3.2.2 Example 1 26 3.2.3 Example 2 27 3.2.4 Example 3 28 3.2.5 Example 4 29 3.2.6 Example 5 30 3.3 Dependency Graph 31 Chapter 4 Prune away Unnecessary Analysis in Reachability Testing for Analysis Livelock 33 4.1 RV Derivation of Reachability Testing 33 4.2 Improvement of RV Derivation 34 4.4 An Example 36 Chapter 5 Conclusion and Future Works 39 5.1 Future Work 39 Bibliography 40