Generating semantic flow graphs representing computer programs

• US 10,628,282 B2
• Filed: 06/28/2018
• Issued: 04/21/2020
• Est. Priority Date: 06/28/2018
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Soares, Ioana Monica Baldini, Mojsilovic, Aleksandra, Patterson, Evan, Varshney, Kush Raj
• Primary Examiner(s): Kang, Insun
• Application Number:
  US16/021,080
• Publication Number:
  US 20200004659A1
• Time in Patent Office: 663 Days
• Field of Search: None
• CPC Class Codes: G06F 11/302 where the computing system component is a software system
• CPC Class Codes: G06F 11/323 Visualisation of programs or trace data
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 11/3608 using formal methods, e.g. model checking, abstract interpretation theorem proving G06N5/013
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis

Abstract

A computer-implemented method includes generating a raw flow graph based on execution of a program. A semantic flow graph is generated based on the raw flow graph and based on an ontology in a subject matter-domain associated with the program. The semantic flow graph illustrates one or more semantic concepts of the program.

Claims

1. A computer-implemented method comprising:

generating, using a processor, a raw flow graph based on execution of a program, the raw flow graph comprises a plurality of boxes and a plurality of wires; and

generating a semantic flow graph based on the raw flow graph and based on an ontology in a subject matter-domain associated with the program, wherein the generating the semantic flow graph includes, for each box in the raw flow graph;

identifying a respective concrete function represented by the box in the raw flow graph, wherein the respective concrete function is a function called during the execution of the program;

searching the ontology for the respective concrete function; and

based at least in part on determining that the respective concrete function is found in the ontology;

identifying a respective semantic concept corresponding to the respective concrete function according to the ontology; and

replacing the box in the raw flow graph with one or more objects representing the respective semantic concept,

wherein the semantic flow graph illustrates one or more semantic concepts of the program.

2. The computer-implemented method of claim 1 further comprising:

determining that the respective concrete function of a first box of the raw flow graph is not found in the ontology; and

collapsing the first box with one or more other boxes of the raw flow graph, responsive to the respective concrete function not being found in the ontology.

3. The computer-implemented method of claim 1, wherein:

the ontology annotates a plurality of concrete functions; and

the ontology maps each concrete function that is annotated to an abstract function that is a semantic concept.

4. The computer-implemented method of claim 1, wherein:

the ontology annotates a plurality of concrete types; and

the ontology maps each concrete type that is annotated to an abstract type that is a semantic concept.

5. The computer-implemented method of claim 1 further comprising selecting the ontology from a plurality of ontologies, wherein each of the plurality of ontologies is associated with a respective subject-matter domain.

6. The computer-implemented method of claim 1 further comprising:

generating, using the processor, a second raw flow graph based on execution of a second program;

generating a second semantic flow graph based on the second raw flow graph and based on the ontology, wherein the second semantic flow graph illustrates one or more semantic concepts of the second program;

comparing the second semantic flow graph to the semantic flow graph; and

determining that the second program is semantically equivalent to the program, based on the comparing the second semantic flow graph to the semantic flow graph.

7. A system comprising:

a memory having computer-readable instructions; and

one or more processors for executing the computer-readable instructions to cause the one or more processors to;

generate a raw flow graph based on execution of a program, the raw flow graph comprises a plurality of boxes and a plurality of wires; and

generate a semantic flow graph based on the raw flow graph and based on an ontology in a subject matter-domain associated with the program, wherein the generating the semantic flow graph includes, for each box in the raw flow graph;

identifying a respective concrete function represented by the box in the raw flow graph, wherein the respective concrete function is a function called during the execution of the program;

searching the ontology for the respective concrete function; and

based at least in part on determining that the respective concrete function is found in the ontology;

identifying a respective semantic concept corresponding to the respective concrete function according to the ontology; and

replacing the box in the raw flow graph with one or more objects representing the respective semantic concept,

wherein the semantic flow graph illustrates one or more semantic concepts of the program.

8. The system of claim 7, wherein the computer-readable instructions further cause the one or more processors to:

determine that the respective concrete function of a first box of the raw flow graph is not found in the ontology; and

collapse the first box with one or more other boxes of the raw flow graph, responsive to the respective concrete function not being found in the ontology.

9. The system of claim 7, wherein:

the ontology annotates a plurality of concrete functions; and

the ontology maps each concrete function that is annotated to an abstract function that is a semantic concept.

10. The system of claim 7, wherein:

the ontology annotates a plurality of concrete types; and

the ontology maps each concrete type that is annotated to an abstract type that is a semantic concept.

11. The system of claim 7, wherein the computer-readable instructions further cause the one or more processors to:

select the ontology from a plurality of ontologies, wherein each of the plurality of ontologies is associated with a respective subject-matter domain.

12. The system of claim 7, wherein the computer-readable instructions further cause the one or more processors to:

generate a second raw flow graph based on execution of a second program;

generate a second semantic flow graph based on the second raw flow graph and based on the ontology, wherein the second semantic flow graph illustrates one or more semantic concepts of the second program;

compare the second semantic flow graph to the semantic flow graph; and

determine that the second program is semantically equivalent to the program, based on the comparing the second semantic flow graph to the semantic flow graph.

13. A computer-program product for generating a semantic flow graph, the computer-program product comprising a computer-readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:

generating a raw flow graph based on execution of a program, the raw flow graph comprises a plurality of boxes and a plurality of wires; and

generating a semantic flow graph based on the raw flow graph and based on an ontology in a subject matter-domain associated with the program, wherein the generating the semantic flow graph includes, for each box in the raw flow graph;

identifying a respective concrete function represented by the box in the raw flow graph, wherein the respective concrete function is a function called during the execution of the program;

searching the ontology for the respective concrete function; and

based at least in part on determining that the respective concrete function is found in the ontology;

identifying a respective semantic concept corresponding to the respective concrete function according to the ontology; and

replacing the box in the raw flow graph with one or more objects representing the respective semantic concept,

wherein the semantic flow graph illustrates one or more semantic concepts of the program.

14. The computer-program product of claim 13, the method further comprising:

determining that the respective concrete function of a first box of the raw flow graph is not found in the ontology; and

collapsing the first box with one or more other boxes of the raw flow graph, responsive to the respective concrete function not being found in the ontology.

15. The computer-program product of claim 13, wherein:

the ontology annotates a plurality of concrete functions; and

the ontology maps each concrete function that is annotated to an abstract function that is a semantic concept.

16. The computer-program product of claim 13, wherein:

the ontology annotates a plurality of concrete types; and

the ontology maps each concrete type that is annotated to an abstract type that is a semantic concept.

17. The computer-program product of claim 13, the method further comprising selecting the ontology from a plurality of ontologies, wherein each of the plurality of ontologies is associated with a respective subject-matter domain.