Patches as better bug reports

ABSTRACT

Tools and analyses that find bugs in software are becoming increasingly prevalent. However, even after the potential false alarms raised by such tools are dealt with, many real reported errors may go unfixed. In such cases the programmers have judged the benefit of fixing the bug to be less than the time cost of understanding and fixing it.The true utility of a bug-finding tool lies not in the number of bugs it finds but in the number of bugs it causes to be fixed.Analyses that find safety-policy violations typically give error reports as annotated backtraces or counterexamples. We propose that bug reports additionally contain a specially-constructed patch describing an example way in which the program could be modified to avoid the reported policy violation. Programmers viewing the analysis output can use such patches as guides, starting points, or as an additional way of understanding what went wrong.We present an algorithm for automatically constructing such patches given model-checking and policy information typically already produced by most such analyses. We are not aware of any previous automatic techniques for generating patches in response to safety policy violations. Our patches can suggest additional code not present in the original program, and can thus help to explain bugs related to missing program elements. In addition, our patches do not introduce any new violations of the given safety policy.To evaluate our method we performed a software engineering experiment, applying our algorithm to over 70 bug reports produced by two off-the-shelf bug-finding tools running on large Java programs. Bug reports also accompanied by patches were three times as likely to be addressed as standard bug reports.This work represents an early step toward developing new ways to report bugs and to make it easier for programmers to fix them. Even a minor increase in our ability to fix bugs would be a great increase for the quality of software.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: A. V. Aho and T. G. Peterson. A minimum-distance error-correcting parser for context-free languages. SIAM Journal of Computation, 1(4):305--312, Dec. 1972.
• 3: Rajeev Alur , Pavol Černý , P. Madhusudan , Wonhong Nam, Synthesis of interface specifications for Java classes, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.98-109, January 12-14, 2005, Long Beach, California, USA
• 4: Glenn Ammons , Rastislav Bodík , James R. Larus, Mining specifications, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.4-16, January 16-18, 2002, Portland, Oregon
• 5: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 6: Thomas Ball , Mayur Naik , Sriram K. Rajamani, From symptom to cause: localizing errors in counterexample traces, ACM SIGPLAN Notices, v.38 n.1, p.97-105, January 2003
• 7: Thomas Ball , Sriram K. Rajamani, Automatically validating temporal safety properties of interfaces, Proceedings of the 8th international SPIN workshop on Model checking of software, p.103-122, May 2001, Toronto, Ontario, Canada
• 8: Lori Carter , Beth Simon , Brad Calder , Larry Carter , Jeanne Ferrante, Path analysis and renaming for predicted instruction scheduling, International Journal of Parallel Programming, v.28 n.6, p.563-588, Dec. 2000 [doi>10.1023/A:1007512717742]
• 9: Sagar Chaki , Alex Groce , Ofer Strichman, Explaining abstract counterexamples, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 10: H. Chen, D. Dean, and D. Wagner. Model checking one million lines of C code. In Network and Distributed System Security Symposium (NDSS), San Diego, CA, Feb. 2004.
• 11: E. M. Clarke , O. Grumberg , K. L. McMillan , X. Zhao, Efficient generation of counterexamples and witnesses in symbolic model checking, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.427-432, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217565]
• 12: James C. Corbett , Matthew B. Dwyer , John Hatcliff , Roby, Bandera: a source-level interface for model checking Java programs, Proceedings of the 22nd international conference on Software engineering, p.762-765, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337625]
• 13: L. Cosmides, J. Tooby, A. Montaldi, and N. Thrall. Character counts: Cheater detection is relaxed for honest individuals. In 11th Annual Meeting of the Human Behavior and Evolution Society, Salt Lake City, Utah, June 1999.
• 14: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 15: Manuvir Das, Unification-based pointer analysis with directional assignments, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.35-46, June 18-21, 2000, Vancouver, British Columbia, Canada
• 16: Manuvir Das , Sorin Lerner , Mark Seigle, ESP: path-sensitive program verification in polynomial time, ACM SIGPLAN Notices, v.37 n.5, May 2002
• 17: Pierpaolo Degano , Corrado Priami, Comparison of syntactic error handling in LR parsers, Software—Practice & Experience, v.25 n.6, p.657-679, June 1995 [doi>10.1002/spe.4380250606]
• 18: Robert DeLine , Manuel Fähndrich, Enforcing high-level protocols in low-level software, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.59-69, June 2001, Snowbird, Utah, United States
• 19: David Detlefs , Greg Nelson , James B. Saxe, Simplify: a theorem prover for program checking, Journal of the ACM (JACM), v.52 n.3, p.365-473, May 2005 [doi>10.1145/1066100.1066102]
• 20: Dominic Duggan , Frederick Bent, Explaining type inference, Science of Computer Programming, v.27 n.1, p.37-83, July 1996 [doi>10.1016/0167-6423(95)00007-0]
• 21: P. Eggert, M. Haertel, D. Hayes, R. Stallman, and L. Tower. diff - compare files line by line. In http://www.gnu.org/software/diffutils/diffutils.html, 2005.
• 22: D. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Symposium on Operating Systems Design and Implementation, 2000.
• 23: Cormac Flanagan , K. Rustan M. Leino , Mark Lillibridge , Greg Nelson , James B. Saxe , Raymie Stata, Extended static checking for Java, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 24: D. Freedman, R. Pisani, and R. Purves. Statistics. Third edition. W. W. Norton, 1998.
• 25: G. Gigerenzer and K. Hug. Domain-specific reasoning: social contracts, cheating and perspective change. In Cognition, volume 43, pages 127--171, 1992.
• 26: A. Groce. Error explanation with distance metrics. In Lecture Notes in Computer Science, volume 2988, pages 108--122, Jan. 2004.
• 27: A. Groce and D. Kroening. Making the most of bmc counterexamples. In Electronic Notes in Theoreitcal Computer Science, volume 119, pages 67--81, 2005.
• 28: A. Groce and W. Visser. What went wrong: Explaining counterexamples. In Lecture Notes in Computer Science, volume 2648, pages 121--135, Jan. 2003.
• 29: Thomas A. Henzinger , Ranjit Jhala , Rupak Majumdar , Grégoire Sutre, Lazy abstraction, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.58-70, January 16-18, 2002, Portland, Oregon
• 30: David Hovemeyer , William Pugh, Finding bugs is easy, Companion to the 19th annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 24-28, 2004, Vancouver, BC, CANADA [doi>10.1145/1028664.1028717]
• 31: Ranjit Jhala , Rupak Majumdar, Path slicing, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 32: Richard E. Korf, Depth-first iterative-deepening: an optimal admissible tree search, Artificial Intelligence, v.27 n.1, p.97-109, Sept. 1985 [doi>10.1016/0004-3702(85)90084-0]
• 33: Ted Kremenek , Ken Ashcraft , Junfeng Yang , Dawson Engler, Correlation exploitation in error ranking, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 34: T. Kremenek and D. Engler. Z-ranking: Using statistical analysis to counter the impact of static analysis approximations. In Static Analysis, 10th International Symposium (SAS), pages 295--315, Jan. 2003.
• 35: K. Rustan M. Leino , Todd Millstein , James B. Saxe, Generating error traces from verification-condition counterexamples, Science of Computer Programming, v.55 n.1-3, p.209-226, March 2005 [doi>10.1016/j.scico.2004.05.016]
• 36: Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]
• 37: Roman Manevich , Manu Sridharan , Stephen Adams , Manuvir Das , Zhe Yang, PSE: explaining program failures via postmortem static analysis, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 38: V. P. Ranganath, T. Amtoft, A. Banerjee, M. B. Dwyer, and J. Hatcliff. A new foundation for control-dependence and slicing for modern program structures. In European Symposium on Programming (ESOP), pages 77--93, Jan. 2005.
• 39: Torsten Robschink , Gregor Snelting, Efficient path conditions in dependence graphs, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581398]
• 40: U. Shankar, K. Talwar, J. S. Foster, and D. Wagner. Detecting format string vulnerabilities with type qualifiers. In USENIX Security Symposium, pages 201--220, 2001.
• 41: Michael Sipser, Introduction to the Theory of Computation: Preliminary Edition, PWS Publishing Co., Boston, MA, 1996
• 42: F. Tip , T. B. Dinesh, A slicing-based approach for locating type errors, ACM Transactions on Software Engineering and Methodology (TOSEM), v.10 n.1, p.5-55, Jan. 2001 [doi>10.1145/366378.366379]
• 43: Westley Weimer , George C. Necula, Finding and preventing run-time error handling mistakes, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 44: John Whaley , Michael C. Martin , Monica S. Lam, Automatic extraction of object-oriented component interfaces, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program modification

General Terms:
Algorithms, Experimentation, Human Factors, Languages, Verification

Keywords:
bug, bug report, counterexample, error, explanation, localization, patch