# WCET Analysis Based on Micro-Architecture Modeling for Embedded System Security
## 4 Implementation  
This section provides a description of the implementation process of the tool, including the establishment of the CFG and CCG, the extension of the CFG, and WCET calculation. Each basic block in the CFG must indicate whether it contains a branch instruction. For blocks with branch instructions, there are two outgoing edges representing the two possible execution directions of the branch instruction. In addition to edges, other information, such as the basic block index, must also be stored. The data type of a basic block is shown in Table 2.  
To analyze the impact of the cache on program execution time, basic blocks are divided into multiple cache basic blocks. If a basic block is smaller than the size of a cache line configured by the user, it is treated as a single node. Otherwise, the basic block is divided into multiple cache basic blocks. The data type for a cache basic block is shown in Table 3. Each cache basic block must record information such as the starting instruction address, the index of the cache set it is mapped to, and the index of the basic block it belongs to. This data type can also be used to describe nodes in the CCG. Consequently, the edges in the CCG only need to record the indices of the start and end nodes, and the count of conflicts. For branch prediction analysis, the introduction of HS requires the extension of CFG. A new node is used to store the branch history information for nodes in the CFG. The data type is shown in Table 4. The main steps in analyzing branch prediction are collecting the set of instructions on the erroneous path, constructing the HS of nodes, and analyzing the HSs of edges to feasible nodes. Function \(collect\_mp\_insts\) is used to collect instructions along the predicted path, function \(build\_bfg\) collects control flow information between \begin{table}
\begin{tabular}{c c l} \hline \hline
**Data Type** & **Name** & **Description** \\ \hline \(int\) & _id_ & Index of the basic block. \\ \hline \(proc\_t^{*}\) & _proc_ & Function the node belongs to. \\ \hline \(addr\_t\) & _sa_ & Starting address of the node. \\ \hline \(int\) & _size_ & Size of the basic block. \\ \hline \(int\) & \(num\_inst\) & Number of instructions in the basic block. \\ \hline \(de\_inst\_t^{*}\) & _code_ & Pointer to the first instruction in the basic block. \\ \hline \(bb\_type\_t\) & _type_ & Whether include branch instruction. \\ \hline \(cfg\_edge\_t^{*}\) & \(out\_n,out\_t\) & Cutting edges of the basic block. \\ \hline \(int\) & \(num\_in\) & Number of the edges out. \\ \hline \(cfg\_edge\_t^{**}\) & \(int\) & Set of the edges in. \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Data type of basic block. \begin{table}
\begin{tabular}{c c l} \hline \hline
**Data Type** & **Name** & **Description** \\ \hline \(inst\_t\) & _start\_inst_ & Starting instruction of the basic block. \\ \hline \(size\_t\) & _lb\_size_ & Size of the cache basic block. \\ \hline \(unsigned\) & _lb\_set_ & Cache line the basic block mapped to. \\ \hline \(cfg\_node\_t\) & \(cfg\_bb\) & Basic block the cache basic block belongs to. \\ \hline \(unsigned\) & _id_ & Index of the cache basic block in CFG. \\ \hline \(ccg\_edge\_^{*}\) & _edges\_in_ & Set of edges in. \\ \hline \(ccg\_edge\_^{*}\) & _edges\_out_ & Set of edges out. \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Data type of cache basic block. adjacent branch instructions under a specific HS, and function \(build\_btg\) uses BFS to collect the information of all nodes reachable from a specific CFG node. The pipeline model analysis is implemented using execution graphs, with the goal of determining the execution time of a basic block. When computing the execution time of a basic block, it is insufficient to consider the block in isolation; the block's context within the CFG must also be considered.