# US 8,751,823 B2 · System and method for branch function based obfuscation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,823 B2 - Document ID: US8751823B2 - Status: Granted - Kind: B2 - Application number: 13/195,748 - Filed: 2011-08-01 - Published: 2013-02-07 - Granted: 2014-06-10 - Earliest claimed: 2011-08-01 - Assignees: Apple Inc. - Applicants: Gideon M. Myles; Julien Lerouge; Jon McLachlan; Ganna Zaks; Augustin J. Farrugia - Inventors: Gideon M. Myles; Julien Lerouge; Jon McLachlan; Ganna Zaks; Augustin J. Farrugia - Web page: https://patentgrep.com/patent/US8751823B2 ## CPC - G06F 21/14: against software analysis or reverse engineering, e.g. by obfuscation - G06F 2221/033: Test or assess software - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Disclosed herein are systems, methods, and non-transitory computer-readable storage media for obfuscating branches in computer code. A compiler or a post-compilation tool can obfuscate branches by receiving source code, and compiling the source code to yield computer-executable code. The compiler identifies branches in the computer-executable code, and determines a return address and a destination value for each branch. Then, based on the return address and the destination value for each branch, the compiler constructs a binary tree with nodes and leaf nodes, each node storing a balanced value, and each leaf node storing a destination value. The non-leaf nodes are arranged such that searching the binary tree by return address leads to a corresponding destination value. Then the compiler inserts the binary tree in the computer-executable code and replaces each branch with instructions in the computer-executable code for performing a branching operation based on the binary tree. ## Claims ### Claim 1 A method comprising: receiving source code; compiling, via a processor, the source code to yield computer executable code, wherein compiling includes steps comprising: identifying a plurality of branches in the source code; determining a return address and a destination value for each branch of the plurality of branches; based on the return address and the destination value for each branch, constructing a binary tree data structure with nodes and leaf nodes, each node storing a constant value to yield constant values, and each leaf node storing a destination value to yield destination values, wherein the constant values are arranged such that searching the binary tree data structure by return address leads to a corresponding destination value; inserting the binary tree data structure in the computer executable code; and replacing each of the plurality of branches with instructions in the computer executable code for performing a branching operation based on the binary tree data structure. ### Claim 2 (depends on 1) The method of claim 1, wherein at least one of the leaf nodes stores a dummy destination value that is not intended for use. ### Claim 3 (depends on 1) The method of claim 1, wherein the binary tree data structure does not store return addresses for the plurality of branches. ### Claim 4 (depends on 1) The method of claim 1, wherein compiling includes steps further comprising: estimating a size for the binary tree data structure based on the plurality of branches; and constructing the binary tree data structure based on the size. ### Claim 5 (depends on 4) The method of claim 4, wherein if the binary tree data structure is too small to accommodate the plurality of branches, then replacing less than all of the plurality of branches with instructions in the computer executable code for performing the branching operation based on the binary tree data structure. ### Claim 6 (depends on 4) The method of claim 4, wherein if the binary tree data structure is too small to accommodate the plurality of branches, the compiling includes steps further comprising: estimating a revised size for the binary tree data structure; and reconstructing the binary tree data structure based on the revised size. ### Claim 7 (depends on 1) The method of claim 1, wherein identifying the plurality of branches in the source code is based on collisions in a hash function. ### Claim 8 (depends on 1) The method of claim 1, wherein each leaf node stores a representation of the destination value, wherein the destination value is derivable from the representation. ### Claim 9 A system comprising: a processor; a memory storing instructions for controlling the processor to perform steps comprising: receiving compiled code; determining a return address and destination value pair for each branch of a plurality of branches in the compiled code; based on the return address and the destination value for each branch, constructing a binary tree data structure with nodes and leaf nodes, each node storing a constant value to yield constant values, and each leaf node storing a destination value to yield destination values, wherein the constant values are arranged such that searching the binary tree data structure by return address leads to a corresponding destination value; inserting the binary tree data structure in the compiled code; and replacing each of the plurality of branches with instructions in the compiled code for performing a corresponding branching operation based on the binary tree data structure. ### Claim 10 (depends on 9) The system of claim 9, wherein nodes have at least one child node, and leaf nodes have no child nodes. ### Claim 11 (depends on 9) The system of claim 9, wherein the binary tree data structure is an ordered directed tree. ### Claim 12 (depends on 9) The system of claim 9, wherein the plurality of branches is identified based on collisions in a hash function. ### Claim 13 A non-transitory computer-readable storage medium storing instructions which, when executed by a computing device, cause the computing device to perform steps comprising: at a branch represented by a replacement branch instruction: determining a return address for the replacement branch instruction; searching a tree data structure, based on the return address, to determine a destination value corresponding to the return address, wherein the tree data structure does not contain the return address, and wherein a position of the destination value within the tree data structure is based on the return address; and executing the replacement branch instruction by jumping to the destination value, and, after executing additional instructions associated with the branch, jumping back to the return address. ### Claim 14 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the tree data structure is one of a binary tree, a B tree, and a multi-way tree. ### Claim 15 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the branch is a jump instruction. ### Claim 16 (depends on 13) The non-transitory computer-readable storage medium of claim 13, wherein the position of the destination value within the tree data structure is such that traversing the tree data structure based on the return address leads to the destination value. ### Claim 17 A system comprising: a processor; a memory storing instructions for controlling the processor to perform, at a branch represented by a replacement branch instruction, steps comprising: determining a return address for the replacement branch instruction; searching a tree data structure, based on the return address, to determine a destination value corresponding to the return address, wherein the tree data structure does not contain the return address, and wherein a position of the destination value within the tree data structure is based on the return address; and executing the replacement branch instruction by jumping to the destination value, and, after executing additional instructions associated with the branch, jumping back to the return address. ### Claim 18 (depends on 17) The system of claim 17, wherein the tree data structure is balanced to minimize traversal steps to access leaf nodes in the tree data structure. ### Claim 19 (depends on 17) The system of claim 17, wherein the position of the destination value within the tree data structure is such that traversing the tree data structure based on the return address leads to the destination value. ### Claim 20 (depends on 17) The system of claim 17, wherein at least one leaf node in the tree data structure stores a dummy destination value. ### Claim 21 A method comprising: receiving code including a plurality of branches; obfuscating, via a processor the plurality of branches via a hash table, based on a respective return address and destination value pair for at least some of the plurality of branches; identifying collisions in the hash table; for each collision in the hash table, inserting, via the processor, in a binary tree data structure a respective collision return address having a corresponding collision destination value, each internal node of the binary tree data structure storing a constant value to yield constant values, and each leaf node of the binary tree data structure storing a destination value to yield destination values, wherein the constant values are arranged such that searching the binary tree data structure by return address leads to a corresponding destination value; inserting, via the processor, the binary tree data structure in the code; and replacing, via the processor, branches corresponding to collisions with instructions in the code for performing a corresponding branching operation based on the binary tree data structure. ### Claim 22 (depends on 21) The method of claim 21, wherein the binary tree data structure is one of a binary tree, a B tree, and a multi-way tree. ### Claim 23 (depends on 21) The method of claim 21, wherein the binary tree data structure is balanced to minimize average traversal time to each leaf node. ### Claim 24 (depends on 21) The method of claim 21, wherein respective collision return addresses are inserted into a plurality of binary tree data structures. ### Claim 25 (depends on 21) The method of claim 21, wherein the binary tree data structure is stored in a text section of the code.