Why Programs Fail: A Guide to Systematic Debugging

Title page......Page 6
Copyright page......Page 7
About the Author......Page 9
Contents......Page 10
Foreword......Page 20
How This Book Came to be Written......Page 22
What This Book Is and What It Is Not......Page 23
Overview of Content......Page 24
Supplements, Resources, and Web Extensions......Page 27
Advice for Readers......Page 28
Acknowledgments......Page 29
1.1 My Program Does Not Work!......Page 30
1.2 From Defects to Failures......Page 32
1.3 Lost in Time and Space......Page 35
1.4 From Failures to Fixes......Page 39
1.5 Automated Debugging Techniques......Page 44
1.6 Bugs, Faults, or Defects?......Page 48
1.7 Concepts......Page 50
1.9 Further Reading......Page 52
1.10 Exercises......Page 53
2.1 Oh! All These Problems......Page 56
2.2 Reporting Problems......Page 57
2.3 Managing Problems......Page 61
2.4.1 Severity......Page 63
2.5 Processing Problems......Page 64
2.6 Managing Problem Tracking......Page 67
2.7 Requirements as Problems......Page 68
2.8 Managing Duplicates......Page 69
2.9 Relating Problems and Fixes......Page 71
2.10 Relating Problems and Tests......Page 73
2.11 Concepts......Page 75
ISSUETRACKER......Page 77
GFORGE......Page 78
2.14 Exercises......Page 79
3.1 Testing for Debugging......Page 82
3.2 Controlling the Program......Page 84
3.3.1 Low-level Interaction......Page 87
3.3.2 System-level Interaction......Page 89
3.3.3 Higher-level Interaction......Page 90
3.3.4 Assessing Test Results......Page 91
3.4 Testing at the Functionality Layer......Page 92
3.5 Testing at the Unit Layer......Page 95
3.6 Isolating Units......Page 100
3.7 Designing for Debugging......Page 103
3.8 Preventing Unknown Problems......Page 106
3.9 Concepts......Page 108
JUNIT......Page 109
FAUmachine......Page 110
3.11 Further Reading......Page 111
3.12 Exercises......Page 112
4.1 The First Task in Debugging......Page 114
4.2 Reproducing the Problem Environment......Page 115
4.3 Reproducing Program Execution......Page 118
4.3.1 Reproducing Data......Page 120
4.3.2 Reproducing User Interaction......Page 121
4.3.3 Reproducing Communications......Page 123
4.3.4 Reproducing Time......Page 124
4.3.6 Reproducing Operating Environments......Page 125
4.3.7 Reproducing Schedules......Page 128
4.3.8 Physical Influences......Page 130
4.3.9 Effects of Debugging Tools......Page 131
4.4 Reproducing System Interaction......Page 133
4.5.1 Setting Up a Control Layer......Page 134
4.5.2 A Control Example......Page 135
4.5.3 Mock Objects......Page 138
4.6 Concepts......Page 141
4.8 Further Reading......Page 143
4.9 Exercises......Page 144
5.1 Simplifying the Problem......Page 146
5.2 The Gecko BugAThon......Page 147
5.3 Manual Simplification......Page 150
5.4 Automatic Simplification......Page 152
5.5 A Simplification Algorithm......Page 154
5.6 Simplifying User Interaction......Page 161
5.7 Random Input Simplified......Page 162
5.8.2 Stop Early......Page 163
5.8.3 Syntactic Simplification......Page 164
5.8.4 Isolate Differences, Not Circumstances......Page 166
5.9 Concepts......Page 167
5.11 Further Reading......Page 168
5.12 Exercises......Page 169
6.1 How to Become a Debugging Guru......Page 174
6.2 The Scientific Method......Page 175
6.3 Applying the Scientific Method......Page 176
6.3.2 Debugging sample—Hypothesis 1......Page 178
6.3.5 Debugging sample—Hypothesis 4......Page 179
6.4 Explicit Debugging......Page 180
6.5 Keeping a Logbook......Page 182
6.6 Debugging Quick-and-Dirty......Page 183
6.7 Algorithmic Debugging......Page 184
6.8 Deriving a Hypothesis......Page 187
6.9 Reasoning About Programs......Page 190
6.10 Concepts......Page 192
6.11 Further Reading......Page 193
6.12 Exercises......Page 194
7.1 Isolating Value Origins......Page 196
7.2 Understanding Control Flow......Page 197
7.3.1 Effects of Statements......Page 201
7.3.2 Affected Statements......Page 203
7.3.3 Statement Dependences......Page 204
7.3.5 Leveraging Dependences......Page 206
7.4 Slicing Programs......Page 207
7.4.2 Backward Slices......Page 208
7.4.3 Slice Operations......Page 209
7.4.5 Executable Slices......Page 211
7.5 Deducing Code Smells......Page 212
7.6 Limits of Static Analysis......Page 218
7.7 Concepts......Page 222
7.9 Further Reading......Page 223
7.10 Exercises......Page 224
8.1 Observing State......Page 228
8.2 Logging Execution......Page 229
8.2.1 Logging Functions......Page 231
8.2.2 Logging Frameworks......Page 235
8.2.3 Logging with Aspects......Page 237
8.2.4 Logging at the Binary Level......Page 242
8.3 Using Debuggers......Page 244
8.3.1 A Debugging Session......Page 245
8.3.2 Controlling Execution......Page 249
8.3.3 Postmortem Debugging......Page 250
8.3.4 Logging Data......Page 251
8.3.6 Fix and Continue......Page 252
8.3.7 Embedded Debuggers......Page 253
8.4 Querying Events......Page 254
8.4.1 Watchpoints......Page 255
8.4.2 Uniform Event Queries......Page 257
8.5 Visualizing State......Page 259
8.6 Concepts......Page 261
PIN......Page 262
JAVA SPIDER......Page 263
8.9 Exercises......Page 264
9.1 Reasoning Backwards......Page 272
9.2 Exploring Execution History......Page 273
9.3 Dynamic Slicing......Page 275
9.4 Leveraging Origins......Page 278
9.5 Tracking Down Infections......Page 282
ODB......Page 283
9.9 Exercises......Page 284
10.1 Automating Observation......Page 286
10.2 Basic Assertions......Page 288
10.3 Asserting Invariants......Page 290
10.4 Asserting Correctness......Page 294
10.5 Assertions as Specifications......Page 297
10.6 From Assertions to Verification......Page 298
10.7 Reference Runs......Page 301
10.8 System Assertions......Page 304
10.8.1 Validating the Heap with MALLOC_CHECK......Page 305
10.8.3 Detecting Memory Errors with VALGRIND......Page 306
10.8.4 Language Extensions......Page 308
10.9 Checking Production Code......Page 310
10.10 Concepts......Page 312
JML......Page 313
INSURE++......Page 314
10.12 Further Reading......Page 315
10.13 Exercises......Page 317
11.1 Capturing Normal Behavior......Page 324
11.2 Comparing Coverage......Page 326
11.3 Statistical Debugging......Page 331
11.4 Collecting Data in the Field......Page 332
11.5 Dynamic Invariants......Page 334
11.6 Invariants on the Fly......Page 338
11.7 From Anomalies to Defects......Page 340
11.8 Concepts......Page 341
11.10 Further Reading......Page 342
11.11 Exercises......Page 343
12.1 Causes and Alternate Worlds......Page 346
12.2 Verifying Causes......Page 348
12.3 Causality in Practice......Page 349
12.4 Finding Actual Causes......Page 351
12.5 Narrowing Down Causes......Page 352
12.6 A Narrowing Example......Page 353
12.8 Causes in Debugging......Page 354
12.9 Concepts......Page 355
12.10 Further Reading......Page 356
12.11 Exercises......Page 357
13.1 Isolating Causes Automatically......Page 360
13.2 Isolating versus Simplifying......Page 361
13.3 An Isolation Algorithm......Page 364
13.4 Implementing Isolation......Page 365
13.6 Isolating Failure-inducing Schedules......Page 369
13.7 Isolating Failure-inducing Changes......Page 372
13.8 Problems and Limitations......Page 378
13.9 Concepts......Page 380
CCACHE......Page 381
13.12 Exercises......Page 382
14.1 Useless Causes......Page 386
14.2 Capturing Program States......Page 389
14.3 Comparing Program States......Page 393
14.4 Isolating Relevant Program States......Page 395
14.5 Isolating Cause-Effect Chains......Page 399
14.6 Isolating Failure-inducing Code......Page 404
14.7 Issues and Risks......Page 408
14.8 Concepts......Page 411
14.10 Further Reading......Page 412
14.11 Exercises......Page 413
15.1 Locating the Defect......Page 416
15.2 Focusing on the Most Likely Errors......Page 418
15.3.1 Does the Error Cause the Failure?......Page 420
15.3.2 Is the Cause Really an Error?......Page 421
15.3.3 Think Before You Code......Page 422
15.4.1 Does the Failure No Longer Occur?......Page 424
15.4.2 Did the Correction Introduce New Problems?......Page 425
15.4.3 Was the Same Mistake Made Elsewhere?......Page 426
15.5 Workarounds......Page 427
15.6 Learning from Mistakes......Page 428
15.7 Concepts......Page 431
15.8 Further Reading......Page 432
15.9 Exercises......Page 433
A.1.2 Passing and Failing Run......Page 436
A.1.5 Simplifying......Page 437
A.1.6 Differences......Page 438
A.1.7 Isolating......Page 439
A.2.1 Formal Structure......Page 440
A.2.2 Unfolding Data Structures......Page 441
A.2.3 Matching Vertices and Edges......Page 443
A.2.5 Computing Graph Differences......Page 444
A.2.7 Capturing C State......Page 447
A.3 Cause-Effect Chains......Page 449
Glossary......Page 452
Bibliography......Page 458
Index......Page 468