# WCET Analysis Based on Micro-Architecture Modeling for Embedded System Security
## 3 Design
### Branch Prediction Analysis  
This paper adopts the GAg prediction model for micro-architecture analysis. In this model, the branch predictor first looks up the Global History Register (GHR) to obtain the current global history of the branches when predicting a branch instruction. This history is then used as an index to access entry into the Pattern History Table (PHT), which contains the results of the branch direction. Prediction errors can lead to pipeline flushes and delays in instruction prefetching. To analyze the impact of branch prediction on program execution time, let \(bcm_{i}\) denote the count of prediction errors and \(penalty\) represent the delay penalty. The target equation is then revised to:  
\[WCET=\sum_{i=0}^{N}(cost_{i}\times cnt_{i}+penalty\times bmc_{i}); \tag{8}\]  
To obtain the constraints bounding the count of mispredictions under the GAg model, information about the execution history of each branch instruction must be recorded. Therefore, we introduce the Historical State (HS) into the CFG. Since there is only one branch instruction per basic block, each basic block will have an HS attribute that records the possible branch history when the control flow reaches that block. Assuming that the BHR is a two-bit register, the CFG, after adding the HS attribute to each basic block, is shown in Figure 5. Let 0 represent the branch that is not taken and 1 represent the branch that is taken. Basic block \(B_{0}\) is the starting block, so its HS is always 00. Basic block \(B_{1}\) has two incoming edges and the two possible paths to this block are \(B_{0}\to B_{1}\) and \(B_{2}\to B_{3}\to B_{1}\). The branch history of these two paths are not taken (\(B_{0}\)), not taken (\(B_{0}\to B_{1}\)), and taken (\(B_{2}\to B_{3}\)), not taken (\(B_{3}\to B_{1}\)); therefore, the HS is \(\{00,11\}\). In an execution, the current HS of each basic block is used as its global history to access and modify the branch prediction result in the BHT, as proposed by the GAg prediction model.  
After adding HS information, the condition still holds that for each basic block in the CFG, the sum of the control flows into the block equals the sum of the control flows out of the block. Let \(d_{i,j}\) denote the execution count from \(B_{i}\) to \(B_{j}\), \(hs\in B_{i}\) represents all HS of basic block \(B_{i}\), \(bmc_{i}^{hs}\), and \(cnt_{i}^{hs}\) represents the corresponding variable when the control flow comes with the \(hs\) historical state. Then, the constraints for the target equation can be obtained:  
\[d_{i,j}=\sum_{hs\in\mathcal{B}_{i}}d_{i,j}^{hs}; \tag{9}\] \[bmc_{i}=\sum_{hs\in B_{i}}bmc_{i}^{hs}; \tag{10}\]  
Figure 5: CFG with HS information.  
\[cnt_{i}=\sum_{hs\in B_{i}}cnt_{i}^{hs}\geq bmc_{i}^{hs}; \tag{11}\]  
If there is an edge from basic block \(B_{j}\) to basic block \(B_{i}\), and the HS of this control flow at \(B_{j}\) is \(h^{pre}\), the HS at \(B_{i}\) in this control flow can occur after recording the branch of the edge \(B_{j}\to B_{i}\). The sum of the incoming control flow from all possible basic blocks under all possible HSs is the execution count of a basic block. Constrains can be obtained in Equation (12).  
\[cnt_{i}^{h}=\sum_{j}d_{j,i}^{h^{pre}}=\sum_{j}\sum_{l^{\prime}\in\{h|h|^{pre} \to h\}}d_{j,i}^{h^{\prime}}; \tag{12}\]  
Let \(spec_{(i,j)}^{(h,n)}\) denote the count of the executions when the HS \(h\) remains unchanged on the longest path from \(B_{i}\) to \(B_{j}\). This means that along the path, branches are either always taken or always not taken, and \(n\) represents the branch result of \(B_{i}\). If a basic block takes (1) the branch to the next block and the branch prediction under HS \(h\) is incorrect, the count of the incorrect prediction must be smaller than the total execution count when the basic block takes the branch. So, the following constraints can be obtained:  
\[bmc_{i}^{(h,1)}\leq\sum_{j}spc_{(i,j)}^{(h,1)}; \tag{13}\]  
\[bmc_{i}^{(h,0)}\leq\sum_{j}spc_{(i,j)}^{(h,0)}; \tag{14}\]