Mining library specifications using inductive logic programming

ABSTRACT

Software libraries organize useful functionalities in order to promote modularity and code reuse. A typical library is used by client programs through an application programming interface (API) that hides its internals from the client. Typically, the rules governing the correct usage of the API are documented informally. In many cases, libraries may have complex API usage rules and unclear documentation. As a result, the behaviour of the library under some corner cases may not be well understood by the programmer. Formal specifications provide a precise understanding of the API behaviour.

We propose a methodology for learning interface specifications using Inductive Logic Programming (ILP). Our technique runs several unit tests on the library in order to generate relations describing the operation of the library. The data collected from these tests are used by an inductive learner to obtain rich Datalog/Prolog specifications. Such specifications capture essential properties of interest to the user. They may be used for applications such as reverse engineering the library internals or constructing checks on the application code to enforce proper API usage along with other properties of interest.

REFERENCES

• 1: Mithun Acharya , Tao Xie , Jian Pei , Jun Xu, Mining API patterns as partial orders from source code: from usage scenarios to specifications, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia [doi>10.1145/1287624.1287630]
• 2: 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
• 3: 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
• 4: Francesco Bergadano , Daniele Gunetti, Inductive Logic Programming: From Machine Learning to Software Engineering, MIT Press, Cambridge, MA, 1995
• 5: Cadar, C., and Engler, D. R. Execution Generated Test Cases: How to make systems code crash itself. In SPIN (2005), vol. 3639 of LNCS, Springer-Verlag, pp. 2--23.
• 6: Mihai Christodorescu , Somesh Jha , Christopher Kruegel, Mining specifications of malicious behavior, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia [doi>10.1145/1287624.1287628]
• 7: William W. Cohen, Recovering software specifications with inductive logic programming, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.142-148, October 1994, Seattle, Washington, United States
• 8: Christoph Csallner , Yannis Smaragdakis, JCrasher: an automatic robustness tester for Java, Software—Practice & Experience, v.34 n.11, p.1025-1050, September 2004 [doi>10.1002/spe.602]
• 9: Luca de Alfaro , Thomas A. Henzinger, Interface automata, Proceedings of the 8th European software engineering conference held jointly with 9th ACM SIGSOFT international symposium on Foundations of software engineering, September 10-14, 2001, Vienna, Austria
• 10: Michael Dean Ernst , David Notkin, Dynamically discovering likely program invariants, University of Washington, 2000
• 11: Patrice Godefroid , Nils Klarlund , Koushik Sen, DART: directed automated random testing, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 12: Guofei Jiang , Haifeng Chen , Cristian Ungureanu , Kenji Yoshihira, Multi-resolution Abnormal Trace Detection Using Varied-length N-grams and Automata, Proceedings of the Second International Conference on Automatic Computing, p.111-122, June 13-16, 2005 [doi>10.1109/ICAC.2005.42]
• 13: Cliff B. Jones, Software Development: A Rigorous Approach, Prentice Hall PTR, Upper Saddle River, NJ, 1980
• 14: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 15: Muggleton, S. Inverse resolution and Progol. New Generation Computing 13 (1995), 245--286.
• 16: Pazzani, M., Brunk, C., and Silverstein, G. A knowledge-intensive approach to learning relational concepts. In Proc. Workshop on Machine Learning (1991), Morgan Kauffmann, pp. 432--436.
• 17: J. R. Quinlan, Learning Logical Definitions from Relations, Machine Learning, v.5 n.3, p.239-266, Aug. 1990 [doi>10.1023/A:1022699322624]
• 18: Murali Krishna Ramanathan , Ananth Grama , Suresh Jagannathan, Static specification inference using predicate mining, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 19: Koushik Sen , Darko Marinov , Gul Agha, CUTE: a concolic unit testing engine for C, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 20: Srinivasan, A. The Aleph manual. Available at http://www.comlab.ox.ac.uk/oucl/ research/areas/machlearn/Aleph/.
• 21: 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
• 22: 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
• 23: Jinlin Yang , David Evans , Deepali Bhardwaj , Thirumalesh Bhat , Manuvir Das, Perracotta: mining temporal API rules from imperfect traces, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134325]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Statistical methods

General Terms:
Theory, Verification

Keywords:
datalog, inductive logic programming, machine learning., software specification, verification