Matching Program Sections Through Feature Extraction
AssigneeMicrosoft Corporation
InventorsAli Rahbar, Elias Bachaalany, Ali Pezeshk
Life of this patent
Estimating the term…
Abstract
Various techniques for matching program sections are described herein. In one example, 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.
Claims20
A method for matching program sections, comprising:
- organizing a program into blocks based on control flow;
- calculating a plurality of features for each block;
- comparing the plurality of features for each block with other blocks and creating a list of equivalent blocks;
- and
- constructing a list of equivalent program sections utilizing the list of equivalent blocks.
One or more computer-readable storage media that match program sections, comprising a plurality of instructions that, when executed by a 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 features for each block;
- compare the plurality of features for each block with other blocks and create a list of equivalent blocks;
- and
- construct a list of equivalent program sections utilizing the list of equivalent blocks.
A system for matching program sections, comprising:
- a 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 features for each block;
- compare the plurality of features for each block with other blocks and create a list of equivalent blocks;
- and
- construct a list of equivalent program sections utilizing the list of equivalent blocks;
- create a graph with the blocks as nodes and with edges determined from control flow;
- 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;
- and
- determine whether the equivalent subgraphs are functions that have been inlined or are to be interpreted as an inlined function.
Dependencies are inferred from the claim text.