Techniques for specifying bug patterns

ABSTRACT

We present our on-going work to develop techniques for specifying source code signatures of bug patterns. Specifically, we discuss two approaches. The first approach directly analyzes a program in the intermediate representation (IR) of the ROSE compiler infrastructure using ROSE's API. The second analyzes the program using the bddbddb system of Lam, Whaley, et al.. In this approach, we store the IR produced by ROSE as a relational database, express patterns as declarative inference rules on relations in the language Datalog, and bddbddb implements the Datalog programs using binary decision diagram (BDD) techniques. Both approaches readily apply to large-scale applications, since ROSE provides full type analysis, control flow, and other available analysis information. In this paper, we primarily consider bug patterns expressed with respect to the structure of the source code or the control flow, or both. More complex techniques to specify patterns that are functions of data flow properties may be addressed by either of the above approaches, but are not directly treated here. Our Datalog-based work includes explicit support for expressing patterns on the use of the Message Passing Interface (MPI) in parallel distributed memory programs. We show examples of this on-going work as well.

REFERENCES

• 1: Coverity - Source Code Analysis, http://www.coverity.com.
• 2: Fortify - Source Code Analysis, http://www.fortifysoftware.com.
• 3: GrammaTech - Source Code Analysis, http://www.grammatech.com.
• 4: Klockwork - Source Code Analysis, http://www.klockwork.com.
• 5: Open64, http://www.open64.net.
• 6: S. P. Amarasinghe, J. M. Anderson, M. S. Lam, and C. W. Tseng. The SUIF compiler for scalable parallel machines. In Proc. SIAM Conference on Parallel Processing for Scientific Computing, Feb 1995.
• 7: D. H. Bailey, E. Barszcz, J. T. Barton, D. S. Browning, R. L. Carter, D. Dagum, R. A. Fatoohi, P. O. Frederickson, T. A. Lasinski, R. S. Schreiber, H. D. Simon, V. Venkatakrishnan, and S. K. Weeratunga. The nas parallel benchmarks. The International Journal of Supercomputer Applications, 5(3):63--73, Fall 1991.
• 8: H. Chen, D. Dean, and D. Wagner. Model checking one million lines of C code. In Proc. Network and Distributed System Security Symposium, San Diego, CA, USA, February 2004.
• 9: Shigeru Chiba, Macro Processing in Object-Oriented Languages, Proceedings of the Technology of Object-Oriented Languages and Systems, p.113, November 23-26, 1998
• 10: D. Dams and K. Namjoshi. Orion: High-precision methods for static error analysis of C and C++ programs. Technical Report ITD-04-45263Z, Bell Labs, April 2004.
• 11: Jayant DeSouza , Bob Kuhn , Bronis R. de Supinski , Victor Samofalov , Sergey Zheltov , Stanislav Bratanov, Automated, scalable debugging of MPI programs with Intel® Message Checker, Proceedings of the second international workshop on Software engineering for high performance computing system applications, May 15-15, 2005, St. Louis, Missouri [doi>10.1145/1145319.1145342]
• 12: D. Engler and M. Musuvathi. Static analysis versus software model checking for bug finding. In Proc.International Conference on Verification, Model Checking, and Abstract Interpretation, Venice, Italy, 2004.
• 13: M. S. et. al. MPI-The Complete Reference. MIT Press, 1996.
• 14: E. Farchi and B. R. Harrington. Assisting the code review process using simple pattern recognition. In Proc. IBM Verification Conference, Haifa, Israel, November 2005.
• 15: Douglas Gregor , Sibylle Schupp, STLlint: lifting static checking from languages to libraries, Software—Practice & Experience, v.36 n.3, p.225-254, March 2006 [doi>10.1002/spe.v36:3]
• 16: 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]
• 17: David Hovemeyer , William Pugh, Finding more null pointer bugs, but not too many, Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.9-14, June 13-14, 2007, San Diego, California, USA [doi>10.1145/1251535.1251537]
• 18: David Hovemeyer , Jaime Spacco , William Pugh, Evaluating and tuning a static analysis to find null pointer bugs, Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, September 05-06, 2005, Lisbon, Portugal
• 19: B. Krammer, K. Bidmon, M. S. Muller, and M. M. Resch. MARMOT: An MPI analysis and checking tool. In Proc. Parallel Computing: Software Technology, Algorithms, Architectures, and Applications, pages 493--500. Elsevier, 2004.
• 20: Monica S. Lam , John Whaley , V. Benjamin Livshits , Michael C. Martin , Dzintars Avots , Michael Carbin , Christopher Unkel, Context-sensitive program analysis as database queries, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065169]
• 21: G. Luecke, H. Chen, J. Coyle, J. Hoekstra, M. Kraeva, and Y. Zou. MPI-CHECK: A tool for checking Fortran 90 MPI programs. Concurrency and Computation: Practice and Experience, 15:93--100, 2003.
• 22: S. McPeak and G. C. Necula. Elkhound: A fast, practical GLR parser generator. In Proc. Conference on Compiler Construction, Barcelona, Spain, April 2004.
• 23: Message Passing Interface Forum (MPIF). MPI: A Message-Passing Interface Standard. Technical Report, University of Tennessee, Knoxville, June 1995. http://www.mpi-forum.org/.
• 24: Message Passing Interface Forum (MPIF). MPI-2: Extensions to the Message Passing Interface. Technical Report, University of Tennessee, Knoxville, 1997. http://www.mpi-forum.org/docs/mpi-20-html/mpi2-report.html.
• 25: NIST. SAMATE - Software Assurance Metrics And Tool Evaluation, http://samate.nist.gov/index.php.
• 26: D. Quinlan. Rose: Compiler support for object-oriented frameworks. In Proceedings of Conference on Parallel Compilers (CPC2000), Aussois, France, volume 10 of Parallel Processing Letters. Springer Verlag, 2000.
• 27: D. Quinlan, M. Schordan, B. Philip, and M. Kowarschik. The specification of source-to-source transformations for the compile-time optimization of parallel object-oriented scientific applications. In H. G. Dietz, editor, Languages and Compilers for Parallel Computing, 14th International Workshop, LCPC 2001, Revised Papers, volume 2624 of Lecture Notes in Computer Science, pages 570--578. Springer Verlag, 2003.
• 28: D. Quinlan, R. Vuduc, T. Panas, J. Hardtlein, and A. Sabjornsen. Support for whole-program analysis and verification of the One-Definition Rule in C++. In Proc. Static Analysis Summit, Gaithersburg, MD, USA, June 2006. National Institute of Standards and Technology Special Publication.
• 29: M. Schordan and D. Quinlan. A source-to-source architecture for user-defined optimizations. In JMLC'03: Joint Modular Languages Conference, volume 2789 of Lecture Notes in Computer Science, pages 214--223. Springer Verlag, Aug. 2003.
• 30: S. F. Siegel. Model checking nonblocking MPI programs. In Proc. Verification, Model Checking, and Abstract Interpretation (VMCAI), Nice, France, January 2007.
• 31: B. Stroustrop and G. D. Reis. Supporting SELL for high-performance computing. In Proc. Workshop on Languages and Compilers for Parallel Computing, Hawthorne, NY, USA, October 2005.
• 32: Jeffrey S. Vetter , Bronis R. de Supinski, Dynamic software testing of MPI applications with umpire, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.51-es, November 04-10, 2000, Dallas, Texas, United States
• 33: Richard Vuduc , Martin Schulz , Dan Quinlan , Bronis de Supinski , Andreas Sæbjørnsen, Improving distributed memory applications testing by message perturbation, Proceeding of the 2006 workshop on Parallel and distributed systems: testing and debugging, July 17-17, 2006, Portland, Maine, USA [doi>10.1145/1147403.1147409]
• 34: John Whaley , Monica S. Lam, Cloning-based context-sensitive pointer alias analysis using binary decision diagrams, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 35: D. Wilkerson. OINK: A collection of composable C++ static analysis tools, 2005. http://freshmeat.net/projects/oink.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Debuggers; Compilers

General Terms:
Languages, Verification

Keywords:
bug patterns, datalog, message passing interface, static analysis