Matching program sections through feature extraction

• US 9,378,001 B2
• Filed: 05/02/2014
• Issued: 06/28/2016
• Est. Priority Date: 05/02/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Rahbar, Ali, Bachaalany, Elias, Pezeshk, Ali
• Primary Examiner(s): Kang, Insun
• Application Number:
  US14/268,248
• Publication Number:
  US 20150317138A1
• Time in Patent Office: 788 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/4436 Exlining; Procedural abstraction
• CPC Class Codes: G06F 8/53 Decompilation; Disassembly

Abstract

A method includes organizing a program into blocks based on control flow. The method also includes calculating a plurality of features for each block. The method further includes comparing the calculated features for each block with other blocks and creating a list of equivalent blocks. The method also further includes constructing a list of equivalent program sections utilizing the list of equivalent blocks.

Claims

1. A method for matching program sections, comprising:

organizing, via a processor, a program into blocks based on control flow;

calculating, via the processor, a plurality of block features for each block;

comparing, via the processor, the plurality of block features for each block with other blocks and creating a list of equivalent blocks, the equivalent blocks representing an inlined function; and

transforming, via the processor, the equivalent blocks representing the inlined function into an alternate program by replacing each of the equivalent blocks with a call to a new function created from the equivalent blocks.

2. The method of claim 1, wherein organizing the program into blocks based on control flow comprises transforming a program to an intermediate language representation and organizing the intermediate language representation into blocks based on control flow.

3. The method of claim 1, further comprising receiving a manual adjustment to a set of features that is to be used for equivalence checks and the detected equivalences.

4. The method of claim 1, further comprising creating a graph with the blocks as nodes and with edges determined from control flow.

5. The method of claim 4, further comprising identifying equivalent subgraphs in the graph, wherein the equivalent blocks are used to identify the equivalent subgraphs, starting with a pair of equivalent blocks as head nodes.

6. The method of claim 5, further comprising determining whether the equivalent subgraphs are functions that have been inlined or are to be interpreted as an inlined function.

7. The method of claim 2, wherein the plurality of block features for each block comprises two or more of:

a feature derived from a mapping of each instruction in the block to an instruction type and chaining the instruction types as they appear in the block;

a feature derived from a mapping of each instruction in the block to an instruction type, combining the instruction types that appear in the block such that the combination result is order agnostic;

a feature derived from the frequency of the different instruction types in the block, allowing for partial or fuzzy matching of two blocks;

a feature derived from symbolic execution of the block; and

a feature derived from translating the block into another intermediate representation, and passing it through an optimizer.

8. The method of claim 5, further comprising loading a program based on the graph and equivalent subgraphs into a user interface and visualizing the code of the program and equivalent subgraphs.

9. The method of claim 8, further comprising accepting a user input to alter one or more decisions around subgraph equivalence and visualizing an updated code and updated equivalent subgraphs.

10. One or more computer-readable hardware storage media that match program sections, comprising a plurality of instructions that, when executed by a hardware processor, cause the processor to:

transform a program to an intermediate language representation;

organize the intermediate language representation into blocks based on control flow;

calculate a plurality of block features for each block;

compare the plurality of block features for each block with other blocks and create a list of equivalent blocks, the equivalent blocks representing an inlined function; and

transform the equivalent blocks representing the inlined function into an alternate program by replacing each of the equivalent blocks with a call to a new function created from the equivalent blocks.

11. The one or more computer-readable storage media of claim 10, further comprising a plurality of instructions that, when executed by a processor, cause the processor to receive a manual adjustment to a set of features that is to be used for equivalence checks and the detected equivalences.

12. The one or more computer-readable storage media of claim 10, further comprising a plurality of instructions that, when executed by a processor, cause the processor to create a graph with the blocks as nodes and with edges determined from control flow.

13. The one or more computer-readable storage media of claim 12, further comprising a plurality of instructions that, when executed by a processor, cause the processor to identify equivalent subgraphs in the graph, wherein the equivalent blocks are used to identify the equivalent subgraphs, starting with a pair of equivalent blocks as head nodes.

14. The one or more computer-readable storage media of claim 13, further comprising a plurality of instructions that, when executed by a processor, cause the processor to determine whether the equivalent subgraphs are functions that have been inlined or are to be interpreted as an inlined function.

15. The one or more computer-readable storage media of claim 10, wherein the plurality of block features for each instruction sequence comprises two or more of:

a feature derived from a mapping of each instruction in the block to an instruction type and chaining the instruction types as they appear in the block;

a feature derived from a mapping of each instruction in the block to an instruction type, combining the instruction types that appear in the block such that the combination result is order agnostic;

a feature derived from the frequency of the different instruction types in the block, allowing for partial or fuzzy matching of two blocks;

a feature derived from symbolic execution of the block; and

a feature derived from translating the block into another intermediate representation, and passing it through an optimizer.

16. The one or more computer-readable storage media of claim 13, further comprising a plurality of instructions that, when executed by a processor, cause the processor to load the program based on the graph and equivalent subgraphs into a user interface and visualize code of the program and equivalent subgraphs.

17. The one or more computer-readable storage media of claim 16, further comprising a plurality of instructions that, when executed by a processor, cause the processor to accept a user input to alter one or more decisions around subgraph equivalence and visualize an updated code and updated equivalent subgraphs.

18. A system for matching program sections, comprising:

a hardware processor to execute processor executable code; and

a storage device that stores processor executable code, wherein the processor executable code, when executed by the processor, causes the processor to;

organize a program into blocks based on control flow;

calculate a plurality of block features for each block;

compare the plurality of block features for each block with other blocks and create a list of equivalent blocks, the equivalent blocks representing an inlined function; and

transform the equivalent blocks representing the inlined function into an alternate program by replacing each of the equivalent blocks with a call to a new function created from the equivalent blocks.