# WCET Analysis Based on Micro-Architecture Modeling for Embedded System Security
## 2 Related Work  
There are three types of WCET analysis methods: static analysis, dynamic analysis, and their hybrid [10]. Dynamic analysis obtains the estimated WCET by executing the given task on the given hardware or a simulator, for some set of inputs, and measuring the execution time of the task or its parts. Static analysis is the process of analyzing program code using offline methods without executing the code. Due to the introduction of mathematical theory, the estimated result of the static analysis is higher than the actual value and is considered the safest. This approach is usually used for hard real-time systems that have stringent execution time requirements [11]. Static analysis is comprised of three main sub-tasks: control flow analysis, processor behavior analysis, and WCET calculation. The tool in this paper is designed using static analysis. The first task of IPET static analysis is to perform control flow analysis and construct the control flow diagram (CFG). CFG is a directed graph with one entry and one exit. Each node, or basic block, in a CFG represents the maximum sequence of consecutive instructions. Except for the last instruction, there is no more branch instructions in the block. Each edge between nodes represents a branch in the control flow. Basic blocks are divided by scanning the symbols using binary. Figure 1 shows an example program and its corresponding CFG. Currently, there are three types of static WCET analysis methods: the Tree-based Technique, Implicit Path Enumeration Technique [12; 13], and Path-Based Technique [14]. The Tree-based Technique translates the structure of a program into a syntax tree, where reduction is performed from the bottom of the tree upwards. When reduction reaches the root of the syntax tree, the WCET of the program is obtained. The Implicit Path Enumeration Technique converts the longest execution time path search problem into the problem of finding the maximum number of executions for each basic block. This can be modeled and solved using the ILP method. The Path-Based Technique is similar to the Tree-based Technique, but it uses a Scope Graph to represent the structure of the program hierarchically. Table 1 provides a comparison of the characteristics of the methods. We adopt IPET in this paper because this method achieves good performance in various aspects when the input program is not too complex. The purpose of control flow analysis is to find the program path with the longest execution time. Since IPET is based on the construction and solving of an ILP, the WCET target equation is given by Equation (1), ignoring hardware configuration. From basic block 0 to basic block \(n\) there is one possible control flow of the program, where the corresponding execution time and execution count of each block are \(cost_{i}\) and \(cnt_{i}\), respectively. \[WCET=max\sum_{i=0}^{N}(cost_{i}\times cnt_{i}); \tag{1}\] \begin{table}
\begin{tabular}{c c c c} \hline \hline \multirow{2}{*}{**Analysis Method**} & \multirow{2}{*}{**Tree-Based**} & **Implicit Path** & \multirow{2}{*}{**Path-Based**} \\  & & **Enumeration** & \\ \hline
**Efficiency** & Highest & High & Low \\ \hline
**Accuracy** & Average & Good & Best \\ \hline
**Ability to Describe** & \multirow{2}{*}{Poor} & \multirow{2}{*}{Good} & \multirow{2}{*}{Best} \\
**Flow Information** & & & \\ \hline
**Affected by Compiler** & \multirow{2}{*}{Yes} & \multirow{2}{*}{No} & \multirow{2}{*}{No} \\
**Optimization** & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison of the three analysis methods. Figure 1: A C program and its CFG. Then, the purpose of control flow analysis shifts to obtaining constraints from the program structure for the target equation. There are three kinds of constraints that should be established: basic block constraints, loop iteration upper limits, and infeasible path constraints [13]. Basic block constraints are relations regarding the execution count of basic blocks.