METHOD AND APPARATUS FOR DETERMINING BINARY FUNCTION ENTRY

A method for determining a binary function entry includes distinguishing a text section and an exception handling section by parsing a binary code, disassembling the text section to determine an address of an end branch instruction, an address of a direct call target, and an address of a direct jump target, determining an indirect return function call address from the addresses of the end branch instructions, determining an exception handling block address from the addresses of the end branch instructions, excluding the indirect return function call address and the exception handling block address from the addresses of the end branch instructions and determining a tail call corresponding to the binary function entry from the addresses of the direct jump targets.

PRIORITY STATEMENT

This application claims priority under 35 U.S.C. § 119 to Korean Patent Application No. 10-2022-0162373, filed on Nov. 29, 2022 in the Korean Intellectual Property Office (KIPO), the contents of which are herein incorporated by reference in their entireties.

BACKGROUND

1. Technical Field

Embodiments relate to a method and an apparatus for determining a binary function entry. More particularly, embodiments relate to a method and an apparatus for determining a binary function entry using a location of an end branch instruction representing an indirect branch target.

2. Description of the Related Art

Function entry identification is a basic technique for generating a control flow graph. The accuracy of binary analysis and reversing may be determined by the function entry identification so that the function entry identification may be very important for the accurate binary analysis and the reversing.

In conventional studies and binary analysis tools, the function entry was identified using binary patterns, static analysis and meta information. In the binary analysis technique using existing patterns, regulations must be manually updated.

A conventional technology for automatically generating patterns through machine learning may vary in accuracy depending on the association (compiler types and options) between learning binaries and analysis target binaries.

A conventional analysis through a static analysis may require a long analysis time. In addition, a conventional function identification technology using meta information may not be applied to x86 binaries which do not have meta information.

SUMMARY

Embodiments provide a method for determining a binary function entry using a location of an end branch instruction representing an indirect branch target to implement a control flow integrity in hardware.

Embodiments provide an apparatus for determining the binary function entry using the location of the end branch instruction representing the indirect branch target to implement the control flow integrity in hardware.

In an example method for determining a binary function entry according to the present inventive concept, the method includes distinguishing a text section and an exception handling section by parsing a binary code, disassembling the text section to determine an address of an end branch instruction, an address of a direct call target, and an address of a direct jump target, determining an indirect return function call address from the addresses of the end branch instructions, determining an exception handling block address from the addresses of the end branch instructions, excluding the indirect return function call address and the exception handling block address from the addresses of the end branch instructions and determining a tail call corresponding to the binary function entry from the addresses of the direct jump targets.

In an embodiment, the binary function entry may be determined as a union of an address set excluding the indirect return function call address and the exception handling block address from the addresses of the end branch instructions, an address set of the direct call target and an address set of the tail call.

In an embodiment, the end branch instruction may represent an indirect branch target.

In an embodiment, the determining indirect return function call address may include checking whether there is a preceding call instruction which refers to a procedure linking table in a target instruction, extracting a target function name from the target instruction when there is the preceding call instruction which refers to the procedure linking table in the target instruction and comparing the target function name with names of predefined reference indirect return functions.

In an embodiment, the predefined reference indirect return functions may include a setjmp function and a vfork function.

In an embodiment, the predefined reference indirect return functions may further include a sigsetjmp function, a savectx function, and a getcontext function.

In an embodiment, in the determining the tail call, when a destination of a jump instruction is above a function including the jump instruction, the destination of the jump instruction may be determined as the tail call.

In an embodiment, in the determining the tail call, when a destination of a jump instruction is a destination of jump instructions of two or more functions, the destination of the jump instruction may be determined as the tail call.

In an embodiment, in the determining the tail call, when a destination of a jump instruction is above a function including the jump instruction and is a destination of jump instructions of two or more functions, the destination of the jump instruction may be determined as the tail call.

In an embodiment, when func_range(x) represents an address range of a function including an address x,represents a set of address pairs (a, b) of addresses a of direct jump instruction and the addresses b of the direct jump targets corresponding to the addresses a of the direct jump instructions,represents an address of the tail call, C1={b|(a,b)∈∧(b<min(func_range(a))∨b>max(func_range(a)))} and C2={b|(a,b)∈∧(c,b)∈∧func_range(a)≠func_range(c)},=C1∩C2may be satisfied.

In an embodiment, the end branch instructions may be located at the binary function entry, the indirect return function call address and the exception handling block address.

In an embodiment, the binary function entry may include the end branch instruction, the direct call target or the direct jump target.

In an example apparatus for determining a binary function entry according to the present inventive concept, the apparatus includes a parser, a disassembler, a filter and a tail call selector. The parser is configured to parse a binary code to distinguish a text section and an exception handling section. The disassembler is configured to disassemble the text section to determine an address of an end branch instruction, an address of a direct call target, and an address of a direct jump target. The filter is configured to determine an indirect return function call address and an exception handling block address from the addresses of the end branch instructions, and exclude the indirect return function call address and the exception handling block address from the addresses of the end branch instructions. The tail call selector is configured to determine a tail call corresponding to the binary function entry from the addresses of the direct jump targets.

In an embodiment, the binary function entries may be determined as a union of an address set excluding the indirect return function call address and the exception handling block address from the addresses of the end branch instructions, an address set of the direct call targets and an address set of the tail calls.

In an embodiment, the end branch instruction may represent an indirect branch target.

In an embodiment, when a destination of a jump instruction is above a function including the jump instruction and is a destination of jump instructions of two or more functions, the tail call selector may be configured to determine the destination of the jump instruction as the tail call.

In an embodiment, when func_range(x) represents an address range of a function including an address x,represents a set of address pairs (a, b) of addresses a of direct jump instruction and the addresses b of the direct jump targets corresponding to the addresses a of the direct jump instructions,represents an address of the tail call, C1={b|(a,b)∈∧(b)<min(func_range(a))∨b>max(func_range(a)))} and C2={b|(a,b)∈∧(c,b)∈∨func_range(a)≠func_range(c)},=C1∩C2may be satisfied.

In an example method for determining a binary function entry according to the present inventive concept, the method includes generating an end branch instruction address from a binary code as a candidate, excluding an indirect return function call address and an exception handling block address from the candidate set and determining an address of a tail call function and including the address of the tail call function in the candidate set.

In an embodiment, when a destination of a jump instruction is above a function including the jump instruction and is a destination of jump instructions of two or more functions, the destination of the jump instruction may be determined as the address of the tail call function.

According to the method and the apparatus for determining the binary function entry (the binary function start address), the binary function entry may be determined using the location of the end branch instruction representing the indirect branch target to implement the control flow integrity in hardware.

In addition, the indirect return function call address and the address of the exception handling block may be excluded from the addresses of the end branch instructions so that the binary function entry may be determined more accurately.

In addition, the address of the tail call may be selected from the addresses of the direct jump targets so that the binary function entry may be determined more accurately.

In this way, by accurately determining the binary function entry, the accurate execution flow graph may be restored, and the accuracy of binary analysis and reversing may be increased. In particular, the method of determining the function entry of the present inventive concept uses only binary codes and exception handling information which are essential for execution so that the method may be applied to commercial x86/x64 binaries which do not include symbols and debugging information.

DETAILED DESCRIPTION OF THE EMBODIMENTS

The present inventive concept now will be described more fully hereinafter with reference to the accompanying drawings, in which embodiments of the present invention are shown. The present inventive concept may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein.

Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the present invention to those skilled in the art. Like reference numerals refer to like elements throughout.

Hereinafter, the present inventive concept will be explained in detail with reference to the accompanying drawings.

FIG.1is a diagram illustrating a C code and an assembly code for explaining an end branch instruction and a notrack prefix.FIG.2is a diagram illustrating a location of an end branch instruction according to a compiler and a binary code package.FIG.3is a diagram illustrating an example of the end branch instruction corresponding to an indirect return.FIG.4is a diagram illustrating an example of the end branch instruction corresponding to an exception handling block.FIG.5is a diagram illustrating characteristics of a function in a predefined data set.

Referring toFIGS.1to5, CET (Control-Flow Enforcement Technology) is a hardware support technology developed to defend against control flow hijacking attacks using memory vulnerabilities. CET guarantees Control-Flow Integrity (CFI) of binary code through hardware technology, and memory vulnerability attacks may be prevented through this. CET may include two techniques defined for control flow integrity: Shadow Stack (SS) and Indirect Branch Tracking (IBT). In the SS, the function return address is copied and stored in an address space safe from attackers. In the SS, the called return address may be compared to the stored return address when performing a function return so that the integrity may be ensured. In the IBT, a specially predefined end branch instruction is forced to be inserted into an indirect branch target, and integrity may be guaranteed by checking whether or not there is an end branch instruction in the indirect branch target. This CET technique is performed at a hardware level so that it may generate little overhead.

A main stream Intel CPU is equipped with the CET function, and the Linux operating system also provides a library and runtime environment to support the CET function. In addition, the complier which generates the executable binary applies the CET function as a basic option, so the CET function is activated in most Linux binary files.

IBT may protect forward indirect branches, such as jmp and call instructions. IBT may check for every indirect branch instruction if it jumps to a predefined code location marked via an end branch (ENDBR32 or ENDBR64) instruction.

A left portion ofFIG.1shows an example C program containing a switch case statement and a right portion ofFIG.1shows the CET-enabled x86-64 binary counterpart corresponding to the example C program.

Note that every function in the binary starts with ENDBR64, which indicates that every function can potentially be a jump target of an indirect branch. In Line 12 of the right portion ofFIG.1, there is an indirect jump prefixed with NOTRACK. The instruction represents the switch statement in the left portion ofFIG.1, and the prefix NOTRACK may be used to mean that the instruction does not need to advance to an end branch instruction because compilers typically put an input range checking before the indirect jump instruction. Thus, the compilers do not insert an end branch instruction for the switch case clauses.

FIG.2represents a result of linearly disassembling every binary for a predetermined dataset to understand the usage pattern of the end branch instructions. As shown inFIG.2, the end branch instructions may be located at the binary function entry, the indirect return function call and the exception handling block (an exception catch block).

In the dataset, for the GCC compiler and the Coreutils binary code package, 99.98% of all end branch instructions are located at the function entries, and 0.02% of all end branch instructions are located at the indirect return function calls.

In the dataset, for the GCC compiler and the Binutils binary code package, 99.99% of all end branch instructions are located at the function entries, and 0.01% of all end branch instructions are located at the indirect return function calls.

In the dataset, for the GCC compiler and the SPEC CPU 2017 binary code package, 79.60% of all end branch instructions are located at the function entries, 0.02% of all end branch instructions are located at the indirect return function calls and 20.38% of all end branch instructions are located at the exception handling blocks.

In the dataset, for the Clang compiler and the Coreutils binary code package, 99.98% of all end branch instructions are located at the function entries, and 0.02% of all end branch instructions are located at the indirect return function calls.

In the dataset, for the Clang compiler and the Binutils binary code package, 99.99% of all end branch instructions are located at the function entries, and 0.01% of all end branch instructions are located at the indirect return function calls.

In the dataset, for the Clang compiler and the SPEC CPU 2017 binary code package, 72.10% of all end branch instructions are located at the function entries, 0.02% of all end branch instructions are located at the indirect return function calls and 27.88% of all end branch instructions are located at the exception handling blocks.

While the majority of end branch instructions were found at a function entry, more than 20% of the cases were found in an exception handling block for the SPEC CPU 2017 binaries. Note that the SPEC CPU 2017 benchmark includes C++ programs, while Coreutils and Binutils do not.

This result highlights that simply regarding an end branch instruction as a function entry may produce a considerable amount of false positives for C++ binaries.

Compilers tend to add an end branch instruction at every non-static function entry because one cannot decide whether a non-static function will be referenced by a function pointer before linking. Indeed, most of the end branch instructions in the dataset are located at a function entry. However, this does not mean that every function starts with an end branch instruction. For example, static functions do not have an end branch instruction unless they are referenced by a function pointer. In addition, there are many other cases where functions do not include an end branch instruction.

Functions may return via an indirect jump instruction instead of a ret. Such functions have the indirect return attribute, and an end branch instruction is inserted right after the call site, to protect the return edge. For example, setjmp is used to save the current execution context in a dedicated buffer, and the context may be restored by longjmp.

FIG.3illustrates this case, where an end branch instruction is located right after the call instruction at 0x40a9f9. At the end of the longjmp call, the indirect jump instruction at 0x132a6e will transfer the control flow of the program to 0x40a9fe. In addition, the compilers may predefine a list of indirect return functions, such as setjmp, sigsetjmp, and vfork. Therefore, it may be easily decided whether an end branch instruction is for handling an indirect return function call or not. For example, inFIG.3, an end branch instruction is disposed at a position returning after calling setjmp, but the end branch instruction disposed at the position returning after calling setjmp does not indicate the function entry.

C++ exceptions may be handled by the libstdc++ library, which uses an indirect jump to transfer the control to a catch clause. Therefore, each catch clause starts with an end branch instruction. In the dataset, C++ binaries from SPEC CPU 2017 show end branch instructions at an exception handling block.FIG.4presents an example of a catch block located at 0x109821 of the 508.namd binary. The catch block at 0x109821 starts with an end branch instruction. For example, inFIG.4, the catch block at 0x109821 means an exception handling code, and an end branch instruction is disposed at the catch block at 0x109821, but the end branch instruction disposed at the catch block at 0x109821 does not indicate the function entry.

FIG.5represents the results of examining the syntactic properties of all functions which may or may not include an end branch instruction. Now that we know end branch instructions may be placed at several different places other than a function entry, we now describe how many functions indeed start with an end branch instruction. To this end, we first extracted 11,209,121 functions from the dataset using the debugging symbols. We then linearly disassembled the entire code section of each binary to check if the following three properties hold for each of the functions:“EndBrAtHead”: there is an end branch at the function entry.“DirJmpTarget”: there is a direct jump to the function.“DirCallTarget”: there is a direct call to the function.

As such, the binary function entry may include the end branch instruction, the direct call target, or the direct jump target.

FIG.5illustrates how each of the properties holds and how they overlap with each other. Note that about 89.3% (=48.85+37.79+1.44+1.23) of the functions start with an end branch instruction (EndBrAtHead). This means one cannot completely retrieve function entries by simply looking at end branch instructions.

For the 11% of the functions without an end branch instruction, we found most of them are referenced by a direct jump or a direct call instruction. In other words, we found that at least one of the three properties holds for 99.99% of the functions. The two properties, DirJmpTarget and DirCallTarget, are useful to make up for the lack of end branch instructions because one can easily obtain the target address of direct branches.

We further analyzed the rest 0.01% of the functions which do not satisfy any of the properties, and found that they are all dead code that is never referenced by any other instruction.

FIG.6is a block diagram illustrating an apparatus for determining a binary function entry according to an embodiment of the present inventive concept.FIG.7is a diagram illustrating a method for determining the binary function entry according to an embodiment of the present inventive concept.FIG.8is a diagram illustrating an operation of excluding an indirect return function call address and an address of the exception handling block from addresses of the end branch instructions.FIG.9is a diagram illustrating an operation of determining a tail call.

Referring toFIGS.1to9, an input of the apparatus for determining binary function entry is a binary code and an output of the apparatus for determining binary function entry is binary function entries in the binary code.

The apparatus for determining binary function entry includes a parser, a disassembler, a filter and a tail call selector.

The parser may parse the binary code to distinguish a text section (txt) and an exception handling section (exn).

The disassembler may disassemble the text section to determine an end branch instruction address (ε), a direct call target address (), and an address pair () of a direct jump instruction address a and a direct jump target address b corresponding to the direct jump instruction address a.

The filter may determine an indirect return function call address and an exception handling block address from the end branch instruction addresses (ε), and exclude the indirect return function call address and the exception handling block address from the end branch instruction addresses. A result of excluding the indirect return function call address and the exception handling block address from the end branch instruction addresses is indicated by ε′ inFIGS.6and7.

The tail call selector may determine the tail call corresponding to the binary function entry from the address pair () regarding the direct jump instruction. An address of the tail call is indicated byinFIGS.6and7.

For example, the binary function entries may be determined as a union (ε∪∪′) of an address set (ε′) excluding the indirect return function call address and the exception handling block address from the end branch instruction addresses, an address set () of the direct call targets and an address setof the tail call.

As described above, the end branch instruction may indicate an indirect branch target. Specifically, the end branch instruction may indicate an indirect branch target in order to implement the control flow integrity in hardware.

The method for determining the binary function entry includes distinguishing the text section and the exception handling section by parsing the binary code, disassembling the text section to determine the end branch instruction address, the direct call target address, and the direct jump target address, determining the indirect return function call address from the end branch instruction addresses, determining the exception handling block address from the end branch instruction addresses, excluding the indirect return function call address and the exception handling block address from the end branch instruction addresses and determining a tail call corresponding to the binary function entry from the direct jump target addresses.

For example, PARSE (in Line 2 ofFIG.7) first analyzes the given binary bin to extract the text section (txt) and the C++ exception information (exn) from it. Note exn only exists for C++ binaries, and thus, it does not affect C binaries.

Next, DISASSEMBLE (in Line 3 ofFIG.7) linearly disassembles txt, and examines every direct branch instruction to return a 3-tuple (ε,;), Herein, ε is a set of end branch instruction addresses found in txt,is a set of direct call target addresses andis a set of address pairs (a, b) of the direct jump instruction addresses a and direct jump target addresses b corresponding to the direct jump instruction addresses a.

For example, DISASSEMBLE may perform linear-sweep disassembly from a start address of the given .text section txt until reaching the end of the section. For example, in case there is a disassembly error in DISASSEMBLE, we increase a program counter by one, and resume the disassembly process. The primary goal here is to find all the end branch instructions as well as direct jump instructions.

FILTERENDBR (in Line 4) then tries to remove end branch instructions that are not relevant to a function entry to obtain ε′.

As explained above, end branch instructions may be placed at two different locations other than a function entry. To reduce false-positives in identifying functions, we need to filter out end branch instructions that are placed either after an indirect return function call or at an exception handling block.

The determining the indirect return function call address may include checking whether there is a preceding call instruction which refers to a procedure linking table in a target instruction, extracting a target function name from the target instruction when there is the preceding call instruction which refers to the procedure linking table in the target instruction and comparing the target function name with names of predefined reference indirect return functions.

When the target function name is same as one of the names of the predefined reference indirect return functions, it means that the target function represents a return target of the indirect return function so that a corresponding branch instruction address may be removed from ε.

Referring toFIG.8, the predefined reference indirect return functions may include a setjmp function and a vfork function. In addition, the predefined reference indirect return functions may further include a sigsetjmp function, a savectx function, and a getcontext function.

In FILTERENDBR, every Language-Specific Data Area (LSDA) of the .gcc_except_table section may be analyzed to see if there is any end branch instruction that belongs to a landing pad, i.e., the exception handling block. The .gcc_except_table section is essential in handling C++ exceptions, and cannot be stripped.

Next, SELECTTAILCALL (in Line 5 ofFIG.7) identifies tail calls from a set of direct jump targetsto get.

Not all direct jump targets defined inindicate function entries. Only when the direct jump target defined inis the tail call (), the direct jump target indicates the function entry.

For example, in the determining the tail call, when a destination of a jump instruction is above a function including the jump instruction, the destination of the jump instruction may be determined as the tail call.

For example, in the determining the tail call, when a destination of a jump instruction is a destination of jump instructions of two or more functions, the destination of the jump instruction may be determined as the tail call.

For example, in the determining the tail call, when a destination of a jump instruction is above a function including the jump instruction and is a destination of jump instructions of two or more functions, the destination of the jump instruction may be determined as the tail call.

FIG.9represents an example of a specific method for determining the tail call. Referring toFIG.9, when func_range(x) represents an address range of a function including an address x, andrepresents the address of the tail call, C1={b|(a,b)∈{circumflex over ( )}(b)<min(func_range(a))∨b>max(func_range(a)))} and C2={b|(a,b)∈{circumflex over ( )}(c,b)∈∨func_range(a)≠func_range(c)},=C1∩C2may be satisfied. InFIG.9, 0x869690 satisfies C1and 0x869690 satisfies C2so that 0x869690 may be determined as the address of the tail call.

Herein, the addressof the direct jump target may mean a set of address pairs (a, b) of the direct jump instruction address a and the direct jump target address b corresponding to the direct jump instruction address a.

The method for determining the binary function entry according to an embodiment includes generating an end branch instruction address from the binary code as a candidate set ε, excluding an indirect return function call address and an exception handling block address from the candidate set ε and determining an addressof a tail call function and including the addressof the tail call function in the candidate set.

Herein, the candidate set from which the indirect return function call address and the exception handling block address are excluded may be expressed as ε′.

When a destination of a jump instruction is above a function including the jump instruction and is a destination of jump instructions of two or more functions, the destination of the jump instruction may be determined as the addressof the tail call function.

According to the present embodiment, the binary function entry may be determined using the location of the end branch instruction representing the indirect branch target to implement the control flow integrity in hardware.

In addition, the indirect return function call address and the address of the exception handling block may be excluded from the addresses of the end branch instructions so that the binary function entry may be determined more accurately.

In addition, the address of the tail call may be selected from the addresses of the direct jump targets so that the binary function entry may be determined more accurately.

In this way, by accurately determining the binary function entry, the accurate execution flow graph may be restored, and the accuracy of binary analysis and reversing may be increased. In particular, the method of determining the function entry of the present inventive concept uses only binary codes and exception handling information which are essential for execution so that the method may be applied to commercial x86/x64 binaries which do not include symbols and debugging information.

According to the present inventive concept, the binary function entry may be determined using the location of the end branch instruction representing the indirect branch target to implement the control flow integrity in hardware. By determining the binary function entry, the control flow graph may be generated.