Control flow graph flattening device and method

Patent metadata

Field	Value
Publication number	US-2016117153-A1
Application number	US-201514922155-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 of software code comprising a plurality of basic blocks having an address and at least one instruction. A processor creates a dispatcher basic block comprising instructions to look up an address in a jump table and to jump to the address, creates the jump table associating a label of each basic block with the address of the basic block, creates a coefficient array comprising diffusion function coefficients, replaces a Jump terminal instruction by a jump to the dispatcher basic block in each of the plurality of basic blocks, creates and inserts a first branch function and a second branch function, the first branch function calculating the label of a subsequent basic block based on a diffusion function for the present basic block, the second branch function calculating the diffusion function index of the subsequent basic block based on the present diffusion function index, creates and inserts 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 creates and inserts diffusion functions in the plurality of basic blocks, each diffusion function calculating a value based on at least one diffusion coefficient in the coefficient array and the label of the present 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:
assigning a value to at least one diffusion function coefficient of a diffusion function of each of the plurality of basic blocks; calculating changes for labels and diffusion functions indices upon transitions between the plurality of basic blocks, the changes corresponding to modifications made by a linear first branch function and a linear second branch function; creating a dispatcher basic block comprising instructions to look up an address in a jump table and to jump to the address; creating the jump table associating the label of each basic block with the address of the basic block; creating a coefficient array comprising diffusion function coefficients; replacing a jump terminal instruction by a jump to the dispatcher basic block in each of the plurality of basic blocks; creating and inserting into each of the plurality of basic blocks the first branch function and the second branch function, the first branch function taking as input a result of a diffusion function in the present basic block and outputting the label of the subsequent basic block to execute, the second branch function taking as input a diffusion function index of the present basic block and outputting a diffusion function index of the subsequent basic block based; creating 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 the subsequent basic block; and creating and inserting diffusion functions in the plurality of basic blocks, a diffusion function inserted in the present basic block calculating a value based on at least one diffusion function coefficient dependant on the diffusion function index and the label of the present basic block.

2 . The method of claim 1 , wherein the transition function obtains the address in the jump table based on also at least one diffusion function coefficient of the subsequent basic block.

3 . The method of claim 1 , further comprising, before creating and inserting the branch functions, assigning a value to the label of each of the plurality of basic blocks.

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

5 . 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:
assign a value to at least one diffusion function coefficient of a diffusion function of each of the plurality of basic blocks; calculate changes for labels and diffusion functions indices upon transitions between the plurality of basic blocks, the changes corresponding to modifications made by a linear first branch function and a linear second branch function; create a dispatcher basic block comprising instructions to look up an address in a jump table and to jump to the address; create the jump table associating a label of each basic block with the address of the basic block; create a coefficient array comprising diffusion function coefficients; replace a jump terminal instruction by a jump to the dispatcher basic block in each of the plurality of basic blocks; create and insert into each of the plurality of basic blocks the first branch function and the second branch function, the first branch function taking as input a result of a diffusion function in the present basic block and outputting the label of the subsequent basic block to execute, the second branch function taking as input a diffusion function index of the present basic block and outputting a diffusion function index of the subsequent basic block based; 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 the subsequent basic block; and create and insert diffusion functions in the plurality of basic blocks, a diffusion function inserted in the present basic block calculating a value based on at least one diffusion function coefficient dependant on the diffusion function index and the label of the present basic block; and an interface configured to output the function after control flow graph flattening.

6 . The device of claim 5 , wherein the processor is further configured to make the transition function obtain the address in the jump table based on also at least one diffusion function coefficient of the subsequent basic block.

7 . The device of claim 5 , wherein the processor is further configured to assign a value to the label of each of the plurality of basic blocks, before creating and inserting the branch functions.

8 . The device of claim 5 , wherein the processor is further configured to obtain coefficients for each of the plurality of basic blocks.

Assignees

• Thomson Licensing

Inventors

• Salmon-Legagneur Charles
• Monsifrot Antoine

Classifications

• G06F8/433 Primary

  Dependency analysis; Data or control flow analysis · CPC title

• G06F8/443

  Optimisation · CPC title

• G06F9/30058

  Conditional branch instructions · CPC title

• G06F21/14 Primary

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