Following Bad Apples: Reporting the Origin of Null Undefined Value Errors - PowerPoint PPT Presentation

tracking bad apples reporting the origin of null undefined value errors l.
Skip this Video
Loading SlideShow in 5 Seconds..
Following Bad Apples: Reporting the Origin of Null Undefined Value Errors PowerPoint Presentation
Following Bad Apples: Reporting the Origin of Null Undefined Value Errors

play fullscreen
1 / 40
Download Presentation
suki-stuart
Views
Download Presentation

Following Bad Apples: Reporting the Origin of Null Undefined Value Errors

Presentation Transcript

  1. Tracking Bad Apples:Reporting the Origin of Null & Undefined Value Errors

  2. Example Code User code: float[][] data = {{1.0f, 2.0f}, {3.0f, 4.0f}}; ScatterPlot plot = new ScatterPlot(data, null); ... plot.draw(...);

  3. NullPointerException at ScatterPlot.draw():315 at Test.doStuff():124 Example Code User code: float[][] data = {{1.0f, 2.0f}, {3.0f, 4.0f}}; ScatterPlot plot = new ScatterPlot(data, null); ... plot.draw(...);

  4. NullPointerException at ScatterPlot.draw():315 at Test.doStuff():124 Example Code User code: Library code: float[][] data = {{1.0f, 2.0f}, {3.0f, 4.0f}}; ScatterPlot plot = new ScatterPlot(data, null); ... ScatterPlot { draw(...) { ... xaxis.draw(); ... } } plot.draw(...);

  5. NullPointerException at ScatterPlot.draw():315 at Test.doStuff():124 Unusable Value • Null is unusable value • Use causes error • How/why did it become null? • Null’s origin? ScatterPlot { draw(...) { ... xaxis.draw(); ... } } plot.draw(...);

  6. Origin of Unusable Value float[][] data = {{1.0f, 2.0f}, {3.0f, 4.0f}}; ScatterPlot plot = new ScatterPlot(data, null); ... ScatterPlot { draw(...) { ... xaxis.draw(); ... } } Origin: Test.init():37 plot.draw(...);

  7. Origin of Unusable Value ScatterPlot { ScatterPlot(data, xaxis) { this.data = data; this.xaxis = xaxis; } ... draw(...) { ... xaxis.draw(); ... } } float[][] data = {{1.0f, 2.0f}, {3.0f, 4.0f}}; ScatterPlot plot = new ScatterPlot(data, null); ... Origin: Test.init():37 plot.draw(...); Origin: Test.init():37

  8. Origin Tracking ScatterPlot { ScatterPlot(data, xaxis) { this.data = data; this.xaxis = xaxis; } ... draw(...) { ... xaxis.draw(); ... } } float[][] data = {{1.0f, 2.0f}, {3.0f, 4.0f}}; ScatterPlot plot = new ScatterPlot(data, null); ... Origin: Test.init():37 Track every unusable value’s origin for 4% overhead Key: store origin in place of unusable value plot.draw(...); Origin: Test.init():37

  9. Outline • Introduction • Unusable values • Instances of origin tracking • Null pointer exceptions (Java) • Undefined value errors (C/C++) • Redefining program operations • Evaluation • Performance • Usefulness • Related Work

  10. Unusable Values • Using value causes error • Examples: • Null values • Undefined values • Tough bugs: no info • Why is value unusable? • Where did unusable value originate?

  11. Unusable Values • Using value causes error • Examples: • Null values • Undefined values • Tough bugs: no info • Why is value unusable? • Where did unusable value originate? Opportunity: Store info in place of value

  12. Origin Tracking Implementations • Null pointers (Java) • Jikes RVM • Undefined values (native code) • Valgrind’s MemCheck

  13. Origin Tracking Implementations • Null pointers (Java) • Jikes RVM • Undefined values (native code) • Valgrind’s MemCheck Jikes RVM Research Archive Valgrind Source Code Repository

  14. Origin Tracking Implementations • Null pointers (Java) • Jikes RVM • Undefined values (native code) • Valgrind’s MemCheck • Identifies origin for 32-bit values • 47 of 147 are 32-bit • For 32-bit: 34 of 47 identified • Adds negligible overhead (28X  28X) Jikes RVM Research Archive Valgrind Source Code Repository

  15. Storing Origins in Null Values • Requirements • Need bits in null values  multiple null values • Program operations support null values • Recover origin at exception

  16. Storing Origins in Null Values • Requirements • Need bits in null values  multiple null values • Program operations support null values • Recover origin at exception Null  high 5 bits are zero (27 bits available) Reserve & protect address range: 0x00000000–0x07ffffff 000002 Method ID Bytecode index 5 bits 14 bits 13 bits

  17. Implementing Java Operations

  18. Implementing Java Operations

  19. Implementing Java Operations

  20. Implementing Java Operations

  21. Implementing Java Operations

  22. Implementing Java Operations

  23. Outline • Introduction • Unusable values • Instances of origin tracking • Null pointer exceptions (Java) • Undefined value errors (C/C++) • Redefining program operations • Evaluation • Performance • Usefulness • Related Work

  24. Methodology • Adaptive methodology • Mix of application & compilation time • Single iteration; 25 trials • DaCapo, SPEC JBB2000, SPEC JVM98 • 3.6 GHz Pentium 4 w/Linux

  25. Performance of Java Implementation

  26. Finding and Fixing Bugs • 12 real NPEs from SourceForge Origin: identified by origin tracking? Triviality: origin obvious by inspection? Usefulness: origin useful for fixing bug?

  27. Null Pointer Exceptions

  28. Null Pointer Exceptions

  29. Null Pointer Exceptions

  30. Null Pointer Exceptions

  31. Null Pointer Exceptions

  32. Debugging Timeline Language design Static analysis Deployment Testing Late Early

  33. Debugging Timeline Prevent bugs • Memory bugs [Java & C#] • Null pointer exceptions [Chalin & James ‘06] • Add “never null” types to Java • Programmer effort • Exceptions still possible • Functional languages Language design Static analysis Deployment Testing Late Early

  34. Debugging Timeline Detect errors in any execution [FindBugs] [PMD] [ESC/Java] [JLint] [Metal] • Dataflow analysis & pattern matching • Program complexity  conservative (false positives) • Some intentionally unsound (false negatives) Language design Static analysis Deployment Testing Late Early

  35. Debugging Timeline Catch errors in real executions • Assertions • Checking tools [Valgrind] [Purify] • Dynamic slicing [Agrawal & Horgan ’90] [Zhang et al. ‘07] Powerful but high overhead Language design Static analysis Deployment Testing Late Early

  36. Debugging Timeline Ideal environment for debugging? • Stack/dump reporting • Invariant-based bug detection [Liblit et al. ’05] • Many executions • Limited dynamic slicing [TaintCheck] [Chilimbi & Hauswirth ’04] [Origin tracking] • Single execution • Narrow focus Language design Static analysis Deployment Testing Late Early

  37. Summary • Unusable values: tough bugs • Error stack trace not enough • Opportunity: store origin in place of unusable value • Managed and native implementations • Java null origins: fast, useful, silent • Add it to your VM today!

  38. Summary • Unusable values: tough bugs • Error stack trace not enough • Opportunity: store origin in place of unusable value • Managed and native implementations • Java null origins: fast, useful, silent • Add it to your VM today! Thank you!

  39. Extra slides

  40. Runtime Overhead (origin tracking)