Mining library specifications using inductive learning

• US 8,191,045 B2
• Filed: 03/18/2008
• Issued: 05/29/2012
• Est. Priority Date: 09/04/2007
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Sankaranarayanan, Sriram, Ivancic, Franjo, Gupta, Aarti
• Primary Examiner(s): Khatri, Anil
• Application Number:
  US12/050,624
• Publication Number:
  US 20090064110A1
• Time in Patent Office: 1,533 Days
• Field of Search: 717124-131, 717141-143
• US Class Current: 717/124
• CPC Class Codes: G06F 11/3672 Test management
• CPC Class Codes: G06F 8/36 Software reuse
• CPC Class Codes: G06F 8/74 Reverse engineering; Extracting design information from source code

Abstract

A system and method for mining program specifications includes generating unit tests to exercise functions of a library through an application program interface (API), based upon an (API) signature. A response to the unit tests is determined to generate a transaction in accordance with a target behavior. The transaction is converted into a relational form, and specifications of the library are learned using an inductive logic programming tool from the relational form of the transaction.

Claims

1. A method for mining program specifications, comprising:

based upon an application program interface (API) signature, generating unit tests to exercise functions of a library through the API, wherein the generating unit tests are based upon instrumentation to define interests and a target behavior;

determining a response to the unit tests to generate a transaction in accordance with the target behavior;

converting the transaction into a relational form using a processor; and

learning specifications of the library using an inductive logic programming tool from the relational form of the transaction, wherein learning specifications includes expressing an occurrence of the target behavior in terms of a usage pattern of the unit tests.

2. The method as recited in claim 1, wherein generating unit tests includes generating random unit tests.

3. The method as recited in claim 1, wherein learning specifications of the library includes describing operation of the library without access to source code of the library.

4. The method as recited in claim 1, further comprising reverse engineering library internals using learned specifications.

5. The method as recited in claim 1, wherein learning specifications includes learning declarative specifications from relational data obtained by running the transaction.

6. A system for mining program specifications, comprising:

a unit test generator configured to generate unit tests to exercise functions of a library through an application program interface (API), wherein the generating unit tests are based upon instrumentation to define interests and a target behavior;

a compiler configured to compile and link library responses to the unit tests and user instrumentation which provides target behavior to generate transactions; and

an inductive logic programming tool configured to convert the transactions into a relational form and learn specifications of the library using from the relational form of the transaction, wherein learning specifications includes expressing an occurrence of the target behavior in terms of a usage pattern of the unit tests.

7. The system as recited in claim 6, wherein the test generator generates random unit tests.

8. The system as recited in claim 6, wherein specifications are learned from the library in terms of a usage pattern of the unit tests.

9. The system as recited in claim 6, wherein the specifications of the library include operating system functionalities, data structure implementations, utilities and database processing.

10. A non-transitory computer readable medium comprising a computer readable program for mining program specifications, wherein the computer readable program when executed on a computer causes the computer perform the steps of:

based upon an application program interface (API) signature, generating unit tests to exercise functions of a library through the API, wherein the generating unit tests are based upon instrumentation to define interests and a target behavior;

determining a response to the unit tests to generate a transaction in accordance with a the target behavior;

converting the transaction into a relational form; and

learning specifications of the library using an inductive logic programming tool from the relational form of the transaction, wherein learning specifications includes expressing an occurrence of the target behavior in terms of a usage pattern of the unit tests.

11. The non-transitory computer readable medium as recited in claim 10, wherein generating unit tests includes generating random unit tests.

12. The non-transitory computer readable medium as recited in claim 10, wherein learning specifications of the library includes describing operation of the library without access to source code of the library.

13. The non-transitory computer readable medium as recited in claim 10, further comprising reverse engineering library internals using learned specifications.

14. The non-transitory computer readable medium as recited in claim 10, wherein learning specifications includes learning declarative specifications from relational data obtained by running the transaction.