## 4 Proposed Method
### Control Flow Integrity Protection Mechanism
#### 4.3.2 Indirect Jump  
Due to the fact that indirect jump address cannot be accurately valued through static analysis, the protection mechanism by using CFG cannot monitor the CFI of the BBs containing indirect jump instructions or indirect function call instructions. We propose a CFI protection mechanism with lower time complexity for indirect jumps. When BBs are extracted, we can obtain the addresses of all instructions of the benchmark, the entry addresses of all functions, and the start addresses of all BBs. For the OR1200 embedded system, there are only three special indirect jump situations:  
* 1.jalr rB. The target address of an indirect function call instruction must be the entry address of a function. * 1.jr r9. This instruction functions as a return instruction. Its target address can only be the start address of a BB. * 1.jr rB. The target address of an indirect jump instruction must also be the start address of a BB. After the above analysis, the legal address range of all indirect jump instructions can be determined. When performing an indirect jump execution, the HMM can detect whether the target address is within the legal address range. This situation can be abstracted as a mathematical problem, that is, knowing N addresses arranged in sequence, of which M addresses are marked, and quickly judging whether a certain address A is within the marked address range. The bitmap algorithm can be used to solve this mathematical problem. It uses a bit to mark the value corresponding to an element. If this element exists in a certain space, its value is set to 1; otherwise, it is set to 0. \[ \begin{array}{l}\text{b}=\text{B}\ /\ 0x4,\text{ B is in the range of M marked addresses}\\ \text{i}=[\text{b}\ /\ 64],\text{ i}=0,\ 1,\ 2,\ \ldots,\ 1+[100,000/64]\\ \text{j}=\text{b}\ \%64,\text{ j}=0,\ 1,\ 2,\ \ldots,\ 63\end{array}  \tag{3}\]  
For example, N = 100,000. We assume that one bit in the bitmap corresponds to 8 bytes. Create an array a[] of length 1+[100,000/64]. Thus, a[0] occupies 64 bits in the memory, corresponding to the decimal number 0.63. Similarly, a[2] corresponds to the decimal number 64.127, and so on. Create an array b[] with a length of 64, representing a 64-bit decimal number. Traverse 100,000 addresses. If a certain address B is marked, the value of its corresponding array a[]b[] is set to 1. The calculation method is shown in Equation (3). This paper assumes that the instructions of the program start from address 0x0 and are stored in the memory in ascending order. Since the OR1200 processor is a 32-bit processor, the value of address B divided by 0x4 represents the b-th address of the program. For example, if B = 0x2000, b = 0x2000/0x4 = 0x800 = 2048, i = [2048/64] = 32, j = [2048 % 64] = 0. Thus, the value of the array a[32]b[0] corresponding to address 0x2000 is 1. The array a[]b[] is the point on the bitmap. For the marked address only, the value of its corresponding point on the bitmap is 1, and the values of other points on the bitmap are all 0. For address A, the corresponding values of i and j can be calculated according to Equation (3). By judging whether the value of a[]b[]j is 1, the HMM can quickly determine whether the address A is within the marked address range. Because S is determined, which is the total number of addresses for each benchmark, the time complexity of the bitmap algorithm is O(1). In addition, the bitmap size is the size of the benchmark divided by 64. Figure 5 describes the process of extracting the function entry address bitmap (FEAddress Bitmap) and the BB start address bitmap (BBAddress Bitmap). For the FEAddress Bitmap, if there is a function start address in every 8 bytes, the corresponding bit in the bitmap will be set to 1; otherwise, it will be set to 0. When executing an indirect jump instruction, the HMM only needs to calculate the i and j of the target address through Equation (3) and check whether the value of the corresponding a[]b[]j is 1, saving an amount of search time and storage resources.