US 8,621,187 B2 · Method of program obfuscation and processing device for executing obfuscated programs

Abstract

A program is obfuscated by reordering its instructions. Original instruction addresses are mapped to target addresses. A cache efficient obfuscated program is realized by restricting target addresses of a sequence of instructions to a limited set of the disjoint ranges (33a-d) of target addresses, which are at lease half filled with instructions. Mapped address steps (34) are provided between the target addresses to which successive ones of the original instruction addresses are mapped. The address steps (34) include first address steps within at least a first one of the mutually disjoint ranges (33a-d). Between said first address steps, second address steps within at least a second one of the mutually disjoint ranges (33a-d). Thus, a deviation from successive addresses for logically successive instructions is realized. In an embodiment the mapping of original instruction addresses to target addresses may be visualized by means of a path (36) along points in an n-dimensional array, where n is greater than one. Successive original instruction addresses are mapped to successive locations in the path, and locations along respective rows of the array are mapped to respective ones of the mutually disjoint ranges (33a-d). Because an n-dimensional path is used a form of locality is preserved that provides for cache efficiency, whereas the multi-dimensional nature of the path makes it possible to combine this locality with pseudo-random steps.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims6

Dependent claims

A method of converting a program of instructions for a programmable processor, the method comprising reordering a sequence of the instructions, whereby original instruction addresses are mapped to respective target addresses, the sequence comprising successive sub-sequences, the method comprising:

mapping each sub-sequence of the sequence to addresses in a respective set of mutually disjoint ranges, separated by further ranges to which other ones of the sub-sequences are mapped,
filling at least half of each of the disjoint ranges in the respective set of mutually disjoint ranges with instructions from the sub-sequence,
providing address steps between the target addresses to which successive ones of the original instruction addresses are mapped for each sub-sequence, the address steps for the sub-sequence comprising first address steps within at least a first one of the mutually disjoint ranges and, between said first address steps, second address steps within at least a second one of the mutually disjoint ranges;
and
wherein the target addresses are computed based on a hierarchy with successive levels of cells, each cell corresponding to a respective set of ranges, cells at successively lower levels corresponding to sub-sets of ranges that are sub-sets of the sets of cells at higher levels, the cells in the hierarchy being associated with indices, the method comprising:
providing sub-division information that defines the sets of ranges as a function of values of the indices;
providing path information that defines respective ones of target addresses to which respective values of the indices map within the set of ranges of a lowest level cell;
deriving a set of values of the indices for at least one of the original instruction addresses;
accessing the sub-division information using the set of values of the indices to index the sub-division information;
combining the accessed sub-division information from different levels to define the set of ranges of the lowest level cell for said at least one of the original instruction addresses,
accessing the path information using the set of values of the indices to index the path information;
using the accessed path information to select the target address for the at least one original instruction address within the set of ranges defined by combining the accessed sub-division information.

9 more elements

A data processing device, comprising a programmable processor, the programmable processor comprising:

a functional unit for executing instructions from a memory,
an address output for supplying target addresses of instructions to the memory;
a program flow control unit configured to determine the target addresses for supply to the address output, the program flow control unit being configured to introduce address steps of position dependent size and/or direction between target addresses of instructions at logically successive positions in the program,
wherein the program flow control unit is configured to determine a set of respective target addresses for successive original instruction addresses, with successive address steps between the target addresses that are determined for successive ones of the original instruction addresses, the respective target addresses of the set lying in a plurality of non-overlapping address ranges, the set of respective target addresses filling at least half of each of the mutually non overlapping ranges of the plurality with instructions, the successive address steps comprising first address steps within at least a first one of the mutually non-overlapping ranges and, between said first address steps, second address steps within at least a second one of the ranges;
and
wherein the data processing, device is configured to determine target addresses based on a hierarchy with successive levels of cells, each cell corresponding to a respective set of ranges, cells at successively lower levels corresponding to sub-sets of ranges that are sub-sets of the sets of cells at higher levels, the cells in the hierarchy being associated with indices, the device comprising:
a program counter;
a look up circuit providing sub-division information that defines the sets of ranges as a function of values of the indices and path information that defines respective ones of target addresses to which respective values of the indices map within the set of ranges of a lowest level cell, the lookup circuit having inputs coupled to the program counter for receiving index values;
a combining circuit configured to combine sub-division information from different levels that has been accessed under control of the program counter to define the set of ranges of the lowest level cell for said at least one of the original instruction addresses and to combine the accessed path information to select the target address for the at least one original instruction address within the set of ranges defined by combining the accessed sub-division information.

6 more elements

Dependencies are inferred from the claim text.

Description10,266 words

Summary529 words

#The invention relates to a data processing device comprising a programmable processor and to a method of converting a program of instructions for a programmable processor.

#Code obfuscation is a general name for techniques for converting a program of instructions for a computer in a way that obscures its content. Code obfuscation may be applied to make it more difficult to identify the relevant part of the program needed to execute a program on an unlicensed type of computer or without protection measures.

#U.S. Pat. No. 6,779,114 describes a code obfuscation technique that involves obscuring control flow of a program. Branch instructions are added to lumps of instructions in a way that obscures the intended execution order of the lumps. U.S. Pat. No. 5,559,884 describes pseudo-random reordering of basic blocks of a program to create a signature that can be used to identify a source through which the program has been distributed.

Brief description of the drawings7 figures

#These and other objects and advantageous aspects will become apparent from a description of exemplary embodiments, using the following Figures.

#FIG. 1 shows a data processing device

#FIGS. 1a-d show a program flow control unit

Detailed description9,660 words

#Basic Data Processing Device

#FIG. 1 shows a data processing device, for example an integrated circuit. Except for its program flow control unit 16, the processing device may have a conventional

#architecture, comprising a memory 10, an instruction issue circuit 12 and a plurality of functional units 14, along with the program flow control unit 16. Instruction issue circuit 12 has an address output and an instruction input coupled and address input and a data output of memory 10, respectively. Instruction issue circuit 12 has an instruction output coupled to functional units 14 and the program flow control unit 16. Program flow control unit 16 has an address output coupled to instruction issue circuit 12.

Facts

Application

12/866,866Filed 9 Feb 2009

Priority

EP 0810148611 Feb 2008

Published

US 2010/0332759 A130 Dec 2010

Granted

31 Dec 2013

Term ends

26 Jan 2031

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 716 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification2 codes

G06F 21/14
Protecting executable software: against software analysis or reverse engineering, e.g. by obfuscation
G06F
Computing and data processing

Timeline

11 Feb 2008Priority claimedEP 08101486
9 Feb 2009Application filedUS 12/866,866
9 Aug 2010Assigned to NXP B.V.assignment of assignor's interest
30 Dec 2010PublishedUS 2010/0332759 A1
31 Dec 2013GrantedUS 8,621,187 B2
7 Mar 2016Assigned to Morgan Stanley Senior Funding, Inc.security agreement supplement
14 Jul 2016Assigned to Morgan Stanley Senior Funding, Inc.corrective assignment to correct the remove application 12092129 previously recorded on reel 038017 frame 0058. assignor(s) hereby confirms the security agreement supplement.
9 May 2017Assigned to Morgan Stanley Senior Funding, Inc.corrective assignment to correct the remove application 12681366 previously recorded on reel 039361 frame 0212. assignor(s) hereby confirms the security agreement supplement.
9 May 2017Assigned to Morgan Stanley Senior Funding, Inc.corrective assignment to correct the remove application 12681366 previously recorded on reel 038017 frame 0058. assignor(s) hereby confirms the security agreement supplement.
10 Sep 2019Assigned to NXP B.V.release of security interest
22 Oct 2019Assigned to Morgan Stanley Senior Funding, Inc.corrective assignment to correct the remove application 12298143 previously recorded on reel 042985 frame 0001. assignor(s) hereby confirms the security agreement supplement.
22 Oct 2019Assigned to Morgan Stanley Senior Funding, Inc.corrective assignment to correct the remove application 12298143 previously recorded on reel 039361 frame 0212. assignor(s) hereby confirms the security agreement supplement.
22 Oct 2019Assigned to Morgan Stanley Senior Funding, Inc.corrective assignment to correct the remove application 12298143 previously recorded on reel 038017 frame 0058. assignor(s) hereby confirms the security agreement supplement.
22 Oct 2019Assigned to Morgan Stanley Senior Funding, Inc.corrective assignment to correct the remove application 12298143 previously recorded on reel 042762 frame 0145. assignor(s) hereby confirms the security agreement supplement.
12 Oct 2026TodayWithin its term
26 Jan 2031Term endsEstimated, includes 716 days of adjustment

Method of program obfuscation and processing device for executing obfuscated programs

Life of this patent

Method of program obfuscation and processing device for executing obfuscated programs

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims6

Description10,266 words

Drawings

Classification2 codes

Life of this patent

Description10,266 words