Why Programs Fail (eBook)

Front Cover 1
Title Page 4
Copyright Page 5
Table of Contents 6
Foreword 16
Preface 18
Chapter 1. How Failures Come to Be 26
1.1 My Program Does Not Work! 26
1.2 From Defects to Failures 27
1.3 Lost in Time and Space 30
1.4 From Failures to Fixes 33
1.4.1 Track the Problem 33
1.4.2 Reproduce the Failure 34
1.4.3 Automate and Simplify the Test Case 34
1.4.4 Find Possible Infection Origins 34
1.4.5 Focus on the Most Likely Origins 37
1.4.6 Isolate the Origin of the Infection 37
1.4.7 Correct the Defect 38
1.5 Automated Debugging Techniques 39
1.6 Bugs, Faults, or Defects? 43
1.7 Concepts 44
How to debug a program 45
1.8 Tools 45
1.9 Further Reading 46
Exercises 47
Chapter 2. Tracking Problems 50
2.1 Oh! All These Problems 50
2.2 Reporting Problems 51
2.2.1 Problem Facts 51
2.2.2 Product Facts 53
2.2.3 Querying Facts Automatically 54
2.3 Managing Problems 56
2.4 Classifying Problems 57
2.4.1 Severity 58
2.4.2 Priority 58
2.4.3 Identifier 58
2.4.4 Comments 59
2.4.5 Notification 59
2.5 Processing Problems 59
2.6 Managing Problem Tracking 61
2.7 Requirements as Problems 62
2.8 Managing Duplicates 64
2.9 Relating Problems and Fixes 65
2.10 Relating Problems and Tests 68
2.11 Concepts 69
How to obtain the relevant problem information 69
How to write an effective problem report 69
How to organize the debugging process 69
How to track requirements 69
How to keep problem tracking simple 69
How to restore released versions 70
How to separate fixes and features 70
How to relate problems and fixes 70
How to relate problems and tests, make a problem report obsolete 70
2.12 Tools 70
2.13 Further Reading 71
Exercises 71
Chapter 3. Making Programs Fail 74
3.1 Testing for Debugging 74
3.2 Controlling the Program 75
3.3 Testing at the Presentation Layer 78
3.3.1 Low-Level Interaction 78
3.3.2 System-Level Interaction 80
3.3.3 Higher-Level Interaction 80
3.3.4 Assessing Test Results 81
3.4 Testing at the Functionality Layer 82
3.5 Testing at the Unit Layer 84
3.6 Isolating Units 88
3.7 Designing for Debugging 91
3.8 Preventing Unknown Problems 94
3.9 Concepts 95
How to test for debugging 95
How to automate program execution 96
How to test at the presentation layer 96
How to test at the functionality layer 96
How to test at the unit layer 96
How to isolate a unit 96
How to design for debugging 96
How to prevent unknown problems 96
3.10 Tools 97
3.11 Further Reading 97
Exercises 98
Chapter 4. Reproducing Problems 100
4.1 The First Task in Debugging 100
4.2 Reproducing the Problem Environment 101
4.3 Reproducing Program Execution 103
4.3.1 Reproducing Data 105
4.3.2 Reproducing User Interaction 105
4.3.3 Reproducing Communications 107
4.3.4 Reproducing Time 108
4.3.5 Reproducing Randomness 108
4.3.6 Reproducing Operating Environments 109
4.3.7 Reproducing Schedules 111
4.3.8 Physical Influences 113
4.3.9 Effects of Debugging Tools 114
4.4 Reproducing System Interaction 115
4.5 Focusing on Units 116
4.5.1 Setting Up a Control Layer 117
4.5.2 A Control Example 117
4.5.3 Mock Objects 120
4.5.4 Controlling More Unit Interaction 122
4.6 Reproducing Crashes 122
4.7 Concepts 126
How to reproduce the problem 126
How to reproduce the problem environment 126
How to reproduce the problem execution 126
How to reproduce unit behavior 126
How to Mock objects 126
How to reproduce a crash 126
4.8 Tools 126
4.9 Further Reading 127
Exercises 127
Chapter 5. Simplifying Problems 130
5.1 Simplifying the Problem 130
5.2 The Gecko BugAThon 131
5.3 Manual Simplification 134
5.4 Automatic Simplification 135
5.5 A Simplification Algorithm 137
5.6 Simplifying User Interaction 142
5.7 Random Input Simplified 143
5.8 Simplifying Faster 144
5.8.1 Caching 144
5.8.2 Stop Early 145
5.8.3 Syntactic Simplification 145
5.8.4 Isolate Differences, Not Circumstances 146
5.9 Concepts 148
How to simplify a test case 148
How to automate simplification 148
How to speed up automatic simplification 148
5.10 Tools 148
5.11 Further Reading 148
Exercises 149
Chapter 6. Scientific Debugging 154
6.1 How to Become a Debugging Guru 154
6.2 The Scientific Method 155
6.3 Applying the Scientific Method 157
6.3.1 Debugging sample—Preparation 157
6.3.2 Debugging sample—Hypothesis 1 157
6.3.3 Debugging sample—Hypothesis 2 158
6.3.4 Debugging sample—Hypothesis 3 158
6.3.5 Debugging sample—Hypothesis 4 158
6.4 Explicit Debugging 159
6.5 Keeping a Logbook 160
6.6 Debugging Quick-and-Dirty 161
6.7 Algorithmic Debugging 162
6.8 Deriving a Hypothesis 165
6.8.1 The Description of the Problem 165
6.8.2 The Program Code 165
6.8.3 The Failing Run 165
6.8.4 Alternate Runs 166
6.8.5 Earlier Hypotheses 166
6.9 Reasoning about Programs 167
6.10 Concepts 169
How to isolate a failure cause 169
How to understand the problem at hand 169
How to avoid endless debugging sessions 169
How to locate an error in a functional or logical program 169
How to debug quick-and-dirty 169
How to derive a hypothesis 169
How to reason about programs 169
6.11 Further Reading 169
Exercises 170
Chapter 7. Deducing Errors 172
7.1 Isolating Value Origins 172
7.2 Understanding Control Flow 173
7.3 Tracking Dependences 177
7.3.1 Effects of Statements 177
7.3.2 Affected Statements 178
7.3.3 Statement Dependences 179
7.3.4 Following Dependences 181
7.3.5 Leveraging Dependences 181
7.4 Slicing Programs 182
7.4.1 Forward Slices 182
7.4.2 Backward Slices 183
7.4.3 Slice Operations 183
7.4.4 Leveraging Slices 185
7.4.5 Executable Slices 185
7.5 Deducing Code Smells 186
7.5.1 Reading Uninitialized Variables 186
7.5.2 Unused Values 187
7.5.3 Unreachable Code 187
7.6 Limits of Static Analysis 191
7.7 Concepts 195
How to isolate value origins 195
How to slice a program 195
7.8 Tools 195
7.9 Further Reading 196
Exercises 196
Chapter 8. Observing Facts 200
8.1 Observing State 200
8.2 Logging Execution 201
8.2.1 Logging Functions 202
8.2.2 Logging Frameworks 205
8.2.3 Logging with Aspects 207
8.2.4 Logging at the Binary Level 211
8.3 Using Debuggers 213
8.3.1 A Debugging Session 214
8.3.2 Controlling Execution 217
8.3.3 Postmortem Debugging 217
8.3.4 Logging Data 218
8.3.5 Invoking Functions 219
8.3.6 Fix and Continue 219
8.3.7 Embedded Debuggers 219
8.3.8 Debugger Caveats 220
8.4 Querying Events 221
8.4.1 Watchpoints 221
8.4.2 Uniform Event Queries 222
8.5 Hooking into the Interpreter 224
8.6 Visualizing State 225
8.7 Concepts 227
How to observe state 228
How to encapsulate and reuse debugging code 228
How to observe the final state of a crashing program 228
How to automate observation 228
8.8 Tools 228
8.9 Further Reading 229
Exercises 229
Chapter 9. Tracking Origins 236
9.1 Reasoning Backward 236
9.2 Exploring Execution History 236
9.3 Dynamic Slicing 238
9.4 Leveraging Origins 241
9.5 Tracking Down Infections 244
9.6 Concepts 245
How to explore execution history 245
How to isolate value origins for a specific run 245
How to track down an infection 245
9.7 Tools 246
9.8 Further Reading 246
Exercises 246
Chapter 10. Asserting Expectations 248
10.1 Automating Observation 248
10.2 Basic Assertions 249
10.3 Asserting Invariants 251
10.4 Asserting Correctness 254
10.5 Assertions as Specifications 257
10.6 From Assertions to Verification 258
10.7 Reference Runs 260
10.8 System Assertions 263
10.8.1 Validating the Heap with MALLOC_CHECK_ 264
10.8.2 Avoiding Buffer Overflows with ELECTRICFENCE 264
10.8.3 Detecting Memory Errors with VALGRIND 265
10.8.4 Language Extensions 266
10.9 Checking Production Code 267
10.10 Concepts 269
How to automate observation 269
How to use assertions 270
How to check a program against a reference program 270
How to check memory integrity 270
How to prevent memory errors in a low-level language 270
10.11 Tools 270
10.12 Further Reading 271
Exercises 272
Chapter 11. Detecting Anomalies 278
11.1 Capturing Normal Behavior 278
11.2 Comparing Coverage 279
11.3 Statistical Debugging 284
11.4 Collecting Data in the Field 285
11.5 Dynamic Invariants 287
11.6 Invariants On-the-Fly 290
11.7 From Anomalies to Defects 291
11.8 Concepts 292
How to determine abnormal behavior 292
How to summarize behavior 292
How to detect anomalies 292
How to compare coverage 292
How to sample return values 292
How to collect data from the field 292
How to determine invariants 292
11.9 Tools 293
11.10 Further Reading 293
Exercises 294
Chapter 12. Causes and Effects 296
12.1 Causes and Alternate Worlds 296
12.2 Verifying Causes 297
12.3 Causality in Practice 298
12.4 Finding Actual Causes 300
12.5 Narrowing Down Causes 301
12.6 A Narrowing Example 302
12.7 The Common Context 302
12.8 Causes in Debugging 303
12.9 Concepts 304
How to show causality 304
How to find a cause 304
How to find an actual cause 304
12.10 Further Reading 304
Exercises 305
Chapter 13. Isolating Failure Causes 308
13.1 Isolating Causes Automatically 308
13.2 Isolating versus Simplifying 309
13.3 An Isolation Algorithm 311
13.4 Implementing Isolation 313
13.5 Isolating Failure-Inducing Input 315
13.6 Isolating Failure-Inducing Schedules 316
13.7 Isolating Failure-Inducing Changes 318
13.8 Problems and Limitations 324
13.9 Concepts 326
How to isolate a failure cause in the input 326
How to isolate a failure cause in the thread schedule 326
How to isolate a failure-inducing code change 326
13.10 Tools 326
13.11 Further Reading 326
Exercises 327
Chapter 14. Isolating Cause–Effect Chains 330
14.1 Useless Causes 330
14.2 Capturing Program States 332
14.3 Comparing Program States 336
14.4 Isolating Relevant Program States 337
14.5 Isolating Cause–Effect Chains 341
14.6 Isolating Failure-Inducing Code 345
14.7 Issues and Risks 349
14.8 Concepts 351
How to understand how a failure cause propagates through the program run 351
How to capture program states 351
How to compare program states 351
How to isolate failure-inducing program states 351
How to find the code that causes the failure 351
How to narrow down the defect along a cause–effect chain 351
14.9 Tools 351
14.10 Further Reading 352
Exercises 352
Chapter 15. Fixing the Defect 354
15.1 Locating the Defect 354
15.2 Focusing on the Most Likely Errors 355
15.3 Validating the Defect 357
15.3.1 Does the Error Cause the Failure? 358
15.3.2 Is the Cause Really an Error? 358
15.3.3 Think Before You Code 360
15.4 Correcting the Defect 360
15.4.1 Does the Failure No Longer Occur? 361
15.4.2 Did the Correction Introduce New Problems? 361
15.4.3 Was the Same Mistake Made Elsewhere? 362
15.4.4 Did I Do My Homework? 363
15.5 Workarounds 363
15.6 Concepts 364
How to isolate the infection chain 364
How to find the most likely origins 364
How to correct the defect 364
How to ensure your correction is successful 364
How to avoid introducing new problems 364
15.7 Further Reading 365
Exercises 365
Chapter 16. Learning from Mistakes 368
16.1 Where the Defects Are 368
16.2 Mining the Past 369
16.3 Where Defects Come From 371
16.4 Errors during Specification 372
16.4.1 What You Can Do 372
16.4.2 What You Should Focus On 373
16.5 Errors during Programming 374
16.5.1 What You Can Do 374
16.5.2 What You Should Focus On 375
16.6 Errors during Quality Assurance 376
16.6.1 What You Can Do 377
16.6.2 What You Should Focus On 378
16.7 Predicting Problems 378
16.7.1 Predicting Errors from Imports 379
16.7.2 Predicting Errors from Change Frequency 380
16.7.3 A Cache for Bugs 380
16.7.4 Recommendation Systems 381
16.7.5 A Word of Warning 381
16.8 Fixing the Process 382
16.9 Concepts 384
How to learn from mistakes 384
How to map defects to components 384
How to reduce the risk of errors in specification 384
How to reduce the risk of errors in the code 384
How to reduce the risk of errors in quality assurance 384
How to allocate quality-assurance resources wisely 384
16.10 Further Reading 384
Exercises 385
Appendix. Formal Definitions 388
A.1 Delta Debugging 388
A.1.1 Configurations 388
A.1.2 Passing and Failing Run 388
A.1.3 Tests 388
A.1.4 Minimality 389
A.1.5 Simplifying 389
A.1.6 Differences 389
A.1.7 Isolating 390
A.2 Memory Graphs 390
A.2.1 Formal Structure 390
A.2.2 Unfolding Data Structures 392
A.2.3 Matching Vertices and Edges 393
A.2.4 Computing the Common Subgraph 393
A.2.5 Computing Graph Differences 394
A.2.6 Applying Partial State Changes 396
A.2.7 Capturing C State 397
A.3 Cause–Effect Chains 399
Glossary 402
Bibliography 406
Index 416