## 3 Preliminaries
### Program Execution Monitoring Based on Basic Block
#### 3.1.2 Extraction of Reference Information  
The intention of partitioning the instruction stream into BBs enables modular security checks for the proposed instruction monitor with minimal performance loss and great security. In the design of the instruction monitor, the reference information (\(INF_{ref}\)) of advisory BBs should be predefined to determine each BB's integrity monitoring parameter.  
To satisfy the security monitoring requirements against the various forms of instruction tampering attacks and achieve a quick integrity verification, the BB \(INF_{inf}\) constitution  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Instruction** & **Example** & **Instruction Operation** & **Transfer Type** \\ \hline lbf N & lbf 0x3 & EA\(+-\)exts(Immediate\(<<\)2)+Bran.Instr.Addr. & Direct branch \\  & & PC\(\leftarrow\)EA if SR[Flag] set & \\ l.bnf N & l.bnf 0x6 & EA\(+-\)exts(Immediate\(<<\)2)+Bran.Instr.Addr. & Direct branch \\  & PC\(\leftarrow\)EA if SR[Flag] cleared & \\  & & PC\(\leftarrow\)EA if SR[Flag] cleared & \\ lj N & lj 0x3 & PC\(+-\)exts(Immediate\(<<\)2)+JumpInstr.Addr. & Direct jump \\  & & PC\(\leftarrow\)(JumpInstr.Addr. & Direct jump \\  & & LR\(+-\)DelayInstr.Addr.+4 & \\  & & PC\(\leftarrow\)rB & \\  & & LR\(\leftarrow\)DelayInstr.Addr.+4 & \\  & & & PC\(\leftarrow\)rB & Indirect jump \\  & & LR\(\leftarrow\)DelayInstr.Addr.+4 & \\  & & & PC\(\leftarrow\)rB & Indirect jump \\  & & & \\ \hline \hline \end{tabular}
\end{table}
Table 1: The transfer type instructions in the OpenRISC instruction set architecture (ISA).  
Figure 2: Example of partitioning the benchmark of OpenECC into program basic blocks.  
requires meeting three conditions: (1) it must be associated with each BB, and its value for each BB is unique so that they can be searched for quickly and accurately; (2) it must be sensitive to any damage issue so that the injection, deletion, or tampering of instruction will cause the security monitoring parameter to change; and (3) it is easy to extract from each BB--its number of bits should not be overly long while ensuring adequate security with storage-resource-limited SoCs.  
After the above comprehensive consideration, we plan to extract the effective start address (\(ADD_{start}\)) and the integrity digest of each BB to constitute the expected 32-bit integrity monitoring \(INF_{ref}\), organically. The BB digest is generated by employing a light-weight hash function (\(DIG_{flush}\)) to calculate all the instruction codes (InsCodes) of each BB. Our adopted OpenRISC processor OR1200 has a 32-bit instruction code and target address, whose instruction and address are aligned to 4 bytes. Due to the lower 2 bits of the 32-bit instruction address in the program counter (PC) being fixed to 2'b00 (addressing RAM by word), the available value as the effective start address of each BB is PC[31:2].  
In general, the width of a 32-bit address can provide 4 GB of address space, where the PC[31:2] value of the BB start address leads to large on-chip storage consumption when it constitutes the integrity reference information of \(INF_{ref}\). For this reason, we selected the lower 16-bit effective values from PC, that is, PC[17:2], as the start address value of each BB into \(INF_{ref}\), which can provide the applications with up to 256 KB address space. Furthermore, the size of the address space can be extended by selecting more effective bits from PC[31:2] according to the real application requirements, and its storage resource overhead will also increase.  
In this work, the 32-bit \(INF_{ref}\) is composed of the 16-bit \(ADD_{start}\)[17:2] and the 16-bit golden \(DIG_{flush}\), where the \(ADD_{start}\)[17:2] is assigned to \(INF_{ref}\)[31:16] for identifying the current BB and searching its corresponding \(INF_{inf}\) from the reference information table; and the 16-bit golden \(DIG_{flush}\) is assigned to \(INF_{ref}\)[15:0] for checking the BB digest integrity.