Behavioral similarity matching using concrete source code templates in logic queries

ABSTRACT

Program query languages and pattern-detection techniques are an essential part of program analysis and manipulation systems. Queries and patterns permit the identification of the parts of interest in a program's implementation through a representation dedicated to the intent of the system (e.g. call-graphs to detect behavioral flaws, abstract syntax trees for transformations, concrete source code to verify programming conventions, etc). This requires that developers understand and manage all the different representations and techniques in order to detect various patterns of interest. To alleviate this overhead, we present a logic-based language that allows the program's implementation to be queried using concrete source code templates. The queries are matched against a combination of structural and behavioral program representations, including call-graphs, points-to analysis results and abstract syntax trees. The result of our approach is that developers can detect patterns in the queried program using source code excerpts (embedded in logic queries) which act as prototypical samples of the structure and behavior they intend to match.

REFERENCES

• 1: Chris Allan , Pavel Avgustinov , Aske Simon Christensen , Laurie Hendren , Sascha Kuzins , Ondřej Lhoták , Oege de Moor , Damien Sereni , Ganesh Sittampalam , Julian Tibble, Adding trace matching with free variables to AspectJ, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 2: Jacques Cohen , Timothy J. Hickey, Parsing and compiling using Prolog, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.2, p.125-163, April 1987 [doi>10.1145/22719.22946]
• 3: Roger F. Crew, ASTLOG: a language for examining abstract syntax trees, Proceedings of the Conference on Domain-Specific Languages on Conference on Domain-Specific Languages (DSL), 1997, p.18-18, October 15-17, 1997, Santa Barbara, California
• 4: M. d'Amorim, C. Nogueira, G. Santos, A. Souza, and P. Borba. Integrating code generation and refactoring. In Proc. of the ECOOP Workshop on Generative Programming, 2002.
• 5: Coen De Roover , Johan Brichau , Theo D'Hondt, Combining fuzzy logic and behavioral similarity for non-strict program validation, Proceedings of the 8th ACM SIGPLAN symposium on Principles and practice of declarative programming, July 10-12, 2006, Venice, Italy [doi>10.1145/1140335.1140339]
• 6: Coen De Roover , Isabel Michiels , Kim Gybels , Kris Gybels , Theo D'Hondt, An Approach to High-Level Behavioral Program Documentation Allowing Lightweight Verification, Proceedings of the 14th IEEE International Conference on Program Comprehension (ICPC'06), p.202-211, June 14-16, 2006 [doi>10.1109/ICPC.2006.10]
• 7: S. Ducasse, M. Freidig, and R. Wuyts. Logic and trace-based object-oriented application testing. In Proc. of the Int. Workshop on Object-Oriented Reengineering, 2004.
• 8: J. Fabry and T. Mens. Language-independent detection of object-oriented design patterns. Elsevier Int. Journal on Computer Languages, Systems & Structures, 30(1-2):21--33, 2004.
• 9: P. Flach. Simply Logical. John Wiley, 1994.
• 10: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java Language Specification, Second Edition: The Java Series, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 11: E. Hajiyev, M. Verbaere, and O. de Moor. Codequest: Scalable source code queries with datalog. In Proc. of the 20th European Conf. on Object-Oriented Programming, volume 4067 of Lecture Notes in Computer Science, pages 2--27, Berlin, Germany, 2006. Springer.
• 12: Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379665]
• 13: David Hovemeyer , William Pugh, Finding bugs is easy, ACM SIGPLAN Notices, v.39 n.12, December 2004 [doi>10.1145/1052883.1052895]
• 14: Christian Kramer , Lutz Prechelt, Design Recovery by Automated Search for Structural Design Patterns in Object-Oriented Software, Proceedings of the 3rd Working Conference on Reverse Engineering (WCRE '96), p.208, November 08-10, 1996
• 15: Claus Lewerentz , Frank Simon, A Product Metrics Tool Integrated into a Software Development Environment, Workshop ion on Object-Oriented Technology, p.256-260, July 20-24, 1998
• 16: O. Lhoták. Spark: A flexible points-to analysis framework for Java. Master's thesis, McGill University, December 2002.
• 17: Michael Martin , Benjamin Livshits , Monica S. Lam, Finding application errors and security flaws using PQL: a program query language, ACM SIGPLAN Notices, v.40 n.10, October 2005
• 18: K. Mens, I. Michiels, and R. Wuyts. Supporting software development through declaratively codified programming patterns. In Proc. of the 13th Int. Software Engineering and Knowledge Engineering Conf., 2001.
• 19: C. Noguera and R. Pawlak. Open static pointcuts through source code templates. In Proc. of the AOSD Workshop on Open and Dynamic Aspect Languages, 2006.
• 20: Yoann Padioleau , René Rydhof Hansen , Julia L. Lawall , Gilles Muller, Semantic patches for documenting and automating collateral evolutions in Linux device drivers, Proceedings of the 3rd workshop on Programming languages and operating systems: linguistic support for modern operating systems, p.10-es, October 22-22, 2006, San Jose, California [doi>10.1145/1215995.1216005]
• 21: B. G. Ryder. Dimensions of precision in reference analysis of object-oriented programming languages. In Proc. of the 12th Int. Conf. on Compiler Construction, volume 2622, pages 126--137, 2003.
• 22: The Smalltalk Open Unification Language (SOUL). http://prog.vub.ac.be/SOUL/.
• 23: M. A. Tobias Rho, Günter Kniesel. Fine-grained generic aspects. In Proc. of the AOSD Workshop on Foundations of Aspect-Oriented Languages. 2006.
• 24: Eelco Visser, Meta-programming with Concrete Object Syntax, Proceedings of the 1st ACM SIGPLAN/SIGSOFT conference on Generative Programming and Component Engineering, p.299-315, October 06-08, 2002
• 25: R. Wuyts. A Logic Meta-Programming Approach to Support the Co-Evolution of Object-Oriented Design and Implementation. PhD thesis, Vrije Universiteit Brussel, Belgium, January 2001.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

General Terms:
Algorithms, Design, Languages, Verification

Keywords:
logic meta programming, pattern detection, program analysis, program querying, program validation, source code templates