## 4 Proposed Method
### Control Flow Integrity Protection Mechanism
#### 4.3.1 Control Flow Graph  
The CFG represents all the paths traversed during the execution of a program. It uses the form of graph to show the possible flow of execution of all BBs when the program is executed. Each node in the CFG represents a BB, and the directional arcs represent the jump of BBs in the control flow. In Table 1 and Figure 1, the target addresses of direct jump instructions, branch jump instructions, and direct function call instructions can be obtained when extracting BBs. Among them, there is only one target address for the direct jump instruction and the direct function jump instruction, and there are two target addresses for the branch jump instruction. For example, the target address of ljal 159b4 is 0x159b4, and the target addresses of l.bf 2020 are 0x2020 and 0x2030. To evaluate the HIIMA, we select real-life embedded applications of various scales from MiBench [18; 1; 28] as the test program. Table 2 shows the characteristics of the selected benchmarks. In Table 2, only a few BBs contain jump instructions that are indirect jump instructions or indirect function call instructions, indicating that most of the BBs are in the CFG. However, due to the lack of the target address of the indirect jump address, the CFG is not completely connected. In addition, the jump addresses of different BBs may be repeated. If the BBs with repeated jump targets are included when constructing the CFG, the entire CFG will be very large and complex, which is not conducive to assigning a CFI\({}_{\text{label}}\) to each BB. Therefore, when constructing the CFG for the BB whose jump target address is the second occurrence, we no longer link it with other BBs. After the above operations, the CFG will be divided \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Benchmarks**} & \multirow{2}{*}{\begin{tabular}{c} **Total** \\ **Instructions** \\ \end{tabular} } & \begin{tabular}{c} **Direct Jump** \\ **and Branch** \\ **and Call** \\ \end{tabular} & \
\begin{tabular}{c} **Indirect** \\ **Jump and** \\ **Indirect Call** \\ \end{tabular} &
\begin{tabular}{c} **Total BB** \\ **Size (KB)** \\ \end{tabular} \\ \hline OpenECC & 56,313 & 5439 & 1295 & 6734 & 197 \\ SHA1 & 20,455 & 2822 & 578 & 3400 & 86 \\ FFT & 13,506 & 1818 & 325 & 2143 & 91 \\ CRC16 & 18,941 & 2672 & 559 & 3231 & 79 \\ BasicMath & 26,515 & 3667 & 660 & 4327 & 149 \\ AES & 22,170 & 2926 & 609 & 3535 & 92 \\ Bitcount & 19,684 & 2760 & 584 & 3344 & 83 \\ Blowfish & 19,128 & 2685 & 562 & 3247 & 83 \\ Patricia & 23,130 & 3288 & 565 & 3853 & 97 \\ QuickSort & 6707 & 854 & 164 & 1018 & 79 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Characteristics of the selected benchmarks. into subgraphs. Each subgraph does not contain indirect jump information, and there are no repeated jump targets in subgraphs. Figure 4 shows an example of extracting CFI reference information, including \(\text{CFI}_{\text{label}}\) and \(\text{HD}_{\text{special}}\). The first step is to extract the CFG. The nodes in CFG include three parameters. The value of Start_Addr is the start address of each BB. For direct jump instructions and direct function call instructions, the value of the Target_Addr_Left is their target address. For branch instructions, the value of Target_Addr_Left is the target address after the jump condition is met, and the value of Target_Addr_Right is the target address when the jump condition is not met. According to these parameters, BBs can be linked to form a CFG. To avoid the influence of repeated jumps and indirect jumps, the CFG will be divided into subgraphs. Equation (2) describes how to calculate the size of the \(\text{CFI}_{\text{label}}\)[31]. Num\({}_{\text{Child}}\) is the maximum number of children nodes for a BB, and Num\({}_{\text{Parent}}\) is the maximum number of parent nodes. [log\({}_{2}\)N] is the integer part of log\({}_{2}\)N, where N is the number of BBs in the subgraph. In Figure 4, the subgraph contains five BBs and three levels.