Sriram Sankaranarayanan
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.
- Acharya, M., Xie, T., Pei, J., and Xu, J. Mining API patterns as partial orders from source code: from usage scenarios to specifications. In ESEC-FSE '07 (2007), ACM Press, pp. 25--34. Google Scholar
Digital Library
- Alur, R., Černý, P., Madhusudan, P., and Nam, W. Synthesis of interface specifications for java classes. In Proc. ACM SIGPLAN symp. on Principles of prog. lang. (POPL) (2005), ACM Press, pp. 98--109. Google ScholarDigital Library
- Ammons, G., Bodík, R., and Larus, J. R. Mining specifications. In POPL (2002), pp. 4--16. Google ScholarDigital Library
- Bergadano, F., and Gunetti, D. Inductive Logic Programming: From Machine Learning to Software Engineering. MIT Press, 1996. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Christodorescu, M., Kruegel, C., and Jha, S. Mining specifications of malicious behavior. In ESEC-FSE '07 (2007), ACM Press, pp. 5--14. Google ScholarDigital Library
- Cohen, W. W. Recovering software specifications with inductive logic programming. In AAAI (1994), pp. 142--148. Google ScholarDigital Library
- Csallner, C., and Smaragdakis, Y. Jcrasher: an automatic robustness tester for Java. Softw., Pract. Exper. 34, 11 (2004), 1025--1050. Google ScholarDigital Library
- de Alfaro, L., and Henzinger, T. A. Interface automata. In ESEC / SIGSOFT FSE (2001), ACM Press, pp. 109--120. Google ScholarDigital Library
- Ernst, M. D. Dynamically Discovering Likely Program Invariants. Ph.D., University of Washington Department of Computer Science and Engineering, Seattle, Washington, Aug. 2000. Google ScholarDigital Library
- Godefroid, P., Klarlund, N., and Sen, K. DART: Directed Automated Random Testing. In ACM SIGPLAN 2005 Conference on Programming Language Design and Implementation (PLDI'05) (2005), pp. 213--223. Google ScholarDigital Library
- Jiang, G., Chen, H., Ungureanu, C., and Yoshihira, K. Multi-resolution abnormal trace detection using varied-length N-grams and automata. In ICAC (2005), IEEE Computer Society, pp. 111--122. Google ScholarDigital Library
- Jones, C. B. Software Development: A Rigorous Approach. 1980. Google ScholarDigital Library
- Mitchell, T. M. Machine Learning. McGraw-Hill, 1997. Google ScholarDigital Library
- Muggleton, S. Inverse resolution and Progol. New Generation Computing 13 (1995), 245--286.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Quinlan, J. R. Learning logical definitions from relations. Machine Learning 5 (1990), 239--266. Google ScholarDigital Library
- Ramanathan, M. K., Grama, A., and Jagannathan, S. Static specification inference using predicate mining. In Proc. ACM SIGPLAN Prog. Lang. Design & Implementation (PLDI) (2007), ACM press, pp. 123--134. Google ScholarDigital Library
- Sen, K., Marinov, D., and Agha, G. Cute: A concolic unit testing engine for c. In ESEC/FSE'05 (2005), ACM Press. Google ScholarDigital Library
- Srinivasan, A. The Aleph manual. Available at http://www.comlab.ox.ac.uk/oucl/ research/areas/machlearn/Aleph/.Google Scholar
- Whaley, J., and Lam, M. S. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In PLDI '04 (2004), ACM Press, pp. 131--144. Google ScholarDigital Library
- Whaley, J., Martin, M. C., and Lam, M. S. Automatic extraction of object-oriented component interfaces. In ISSTA (2002), pp. 218--228. Google ScholarDigital Library
- Yang, J., Evans, D., Bhardwaj, D., Bhat, T., and Das, M. Perracotta: Mining temporal API rules from imperfect traces. In Proc. of ICSE (2006). Google ScholarDigital Library
Index Terms
- Mining library specifications using inductive logic programming
Recommendations
Inductive equivalence in clausal logic and nonmonotonic logic programming
This paper provides a logical framework for comparing inductive capabilities among agents having different background theories. A background theory is called inductively equivalent to another background theory if the two theories induce the same ...
On temporal logic versus datalog
Logic and complexity in computer scienceWe provide a direct and modular translation from the temporal logics CTL, ETL, FCTL (CTL extended with the ability to express fairness) and the Modal µ-calculus to Monadic inf-Datalog with built-in predicates. We call it inf-Datalog because the ...
Complexity and expressive power of logic programming
This article surveys various complexity and expressiveness results on different forms of logic programming. The main focus is on decidable forms of logic programming, in particular, propositional logic programming and datalog, but we also mention ...
Comments