US 7,681,190 B2 · Minimum delta generator for program binaries

Abstract

Implementations provide a technology for generating a minimum delta between at least two program binaries. An implementation is given a source program (S) in a binary format and a target program (T) in a binary form. It constructs control flow graphs (CFGs) of each. It matches common blocks of the S's CFGs and T's CFGs. The blocks are matched based upon their content and their local neighborhoods. In addition, the register renaming problems is solved so that blocks can be fairly compared. This implementation produces an intermediate output, which is the content of unmatched blocks. It generates a set of edge edit operations for merging the unmatched blocks into S. The combination of the unmatched blocks and the edit operations is the delta. To patch S to produce a reconstructed copy of T, the delta is merged with S.

Claims6

Dependent claims

A method for matching blocks between a first control flow graph (CFG) representation of a portion of a first program and a second CFG representation of a portion of a second program, the method comprising:

matching blocks, by one or more computing devices configured to match blocks between the first CFG representation of the portion of the first program and the second CFG representation of the portion of the second program, between the first and second CFG representations based upon the content of the blocks;
detecting outliers, by one or more computing devices, wherein outliers are blocks in the first CFG representation that do not match any block in the second CFG representation during the matching step;
computing a neighborhood, that may have a depth greater than 1, of each block in the first and second CFG representations by performing a breadth first traversal;
removing the outliers from each neighborhood.

1 more element

Dependencies are inferred from the claim text.

Minimum delta generator for program binaries

Life of this patent

Minimum delta generator for program binaries

Life of this patent

Abstract

Claims6