Control flow graph flattening device and method

Patent metadata

Field	Value
Publication number	US-2016117155-A1
Application number	US-201514922151-A
Country	US
Kind code	A1
Filing date	Oct 24, 2015
Priority date	Oct 24, 2014
Publication date	Apr 28, 2016
Grant date	—

Abstract

Control Flow Graph flattening of a function comprising a plurality of basic blocks having an address and at least one instruction. A processor creates a jump table associating a label of each basic block with its address, creates a coefficient array comprising constant coefficients, creates a dispatcher basic block comprising instructions to look up an address in the jump table and to jump to the address, replaces a Jump terminal instruction by a jump to the dispatcher basic block in each basic block, creates and inserts at least one lookup functions in each of the plurality of basic blocks, each lookup function returning a derived value based on a constant coefficient depending on at least an index of the basic block; creates and inserts a first branch function calculating the label of a subsequent basic block based on at least the derived value and a second branch function calculating the index of the subsequent basic block; and creates and inserts into the dispatcher basic block a transition function obtaining the address in the jump table based on at least the label of a subsequent basic block.

First claim

1 . A method for control flow graph flattening of a function of software code, the function comprising a plurality of basic blocks each having an address and at least one instruction, the method, performed by a processor of a device, comprising:
inserting a jump table associating a label of each basic block with the address of the basic block; inserting a coefficient array comprising constant coefficients for each of the plurality of basic blocks; inserting a dispatcher basic block comprising instructions to look up an address in the jump table and to jump to the address; replacing a jump terminal instruction by a jump to the dispatcher basic block in each of the plurality of basic blocks; inserting at least one lookup function in each of the plurality of basic blocks, each lookup function returning, depending on at least an index of the basic block, a derived value based on a constant coefficient from the coefficient array, each constant coefficient; inserting a first branch function and a second branch function, wherein the first branch function calculates the label of a subsequent basic block based on at least the derived value and the label of the present basic block, and wherein the second branch function calculates the index of the subsequent basic block based on the index of the present basic block; and inserting a transition function into the dispatcher basic block, the transition function obtaining the address in the jump table based on at least the label of a subsequent basic block.

2 . The method of claim 1 , wherein dummy values are included in the coefficient array.

3 . The method of claim 1 , wherein the transition function obtains the address in the jump table based on also the index of the subsequent basic block.

4 . The method of claim 1 , further comprising giving a value to the label of each of the plurality of basic blocks.

5 . The method of claim 1 , further comprising giving a value to the index of each of the plurality of basic blocks.

6 . The method of claim 1 , further comprising calculating changes for the labels and the indices that will result from transitions between the plurality of basic blocks, the changes corresponding to modifications made to the labels by the first branch function and to the indices by the second branch function.

7 . The method of claim 1 , further comprising calculating coefficients for each of the plurality of basic blocks.

8 . A device for control flow graph flattening of a function of software code, the function comprising a plurality of basic blocks each having an address and at least one instruction, the device comprising a hardware processor configured to:
create a jump table associating a label of each basic block with the address of the basic block; create a coefficient array comprising constant coefficients for each of the plurality of basic blocks; create a dispatcher basic block comprising instructions to look up an address in the jump table and to jump to the address; replace a jump terminal instruction by a jump to the dispatcher basic block in each of the plurality of basic blocks; create and insert at least one lookup function in each of the plurality of basic blocks, each lookup function returning, depending on at least an index of the basic block, a derived value based on a constant coefficient from the coefficient array, each constant coefficient; create and insert a first branch function and a second branch function, the first branch function calculating the label of a subsequent basic block based on at least the derived value and the label of the present basic block, and the second branch function calculating the index of the subsequent basic block based on the index of the present basic block; and create and insert a transition function into the dispatcher basic block, the transition function obtaining the address in the jump table based on at least the label of a subsequent basic block; and an interface configured to output the function after control flow graph flattening.

9 . The device of claim 8 , wherein the processor is configured to include dummy values in the coefficient array.

10 . The device of claim 8 , wherein the processor is further configured to make the transition function obtain the address in the jump table based on also the index of the subsequent basic block.

11 . The device of claim 8 , wherein the processor is further configured to give a value to the label of each of the plurality of basic blocks.

12 . The device of claim 8 , wherein the processor is further configured to give a value to the index of each of the plurality of basic blocks.

13 . The device of claim 8 , wherein the processor is further configured to calculate changes for the labels and the indices that will result from transitions between the plurality of basic blocks, the changes corresponding to modifications made to the labels by the first branch function and to the indices by the second branch function.

Assignees

• Thomson Licensing

Inventors

• Salmon-Legagneur Charles
• Monsifrot Antoine

Classifications

• G06F21/125 Primary

  by manipulating the program code, e.g. source code, compiled code, interpreted code, machine code · CPC title

• G06F21/14

  against software analysis or reverse engineering, e.g. by obfuscation · CPC title

• G06F8/443 Primary

  Optimisation · CPC title

• G06F8/433

  Dependency analysis; Data or control flow analysis · CPC title