# \(HM^{3}a1D\): Polymorphic Malware Detection Using Program Behavior-Aware Hidden Markov Model
## 5 Experimental Evaluation
### The Performance of \(HM^{3}aID\)
#### 5.4.1 Training Phase  
First, we determined the basic parameters such as the number of malware clusters and the number of states for each malware HMM. Then, we clustered malware action sequence sets, and, according to the program based HMM topology (Figure 2), we trained HMMs \(\lambda_{c_{i}}\) on the training part of all malware clusters \(\{\mathcal{X}_{c_{i}}\}_{i=1}^{k}\). Finally, we applied Algorithm 3 to compute their corresponding decision thresholds, \(\mathcal{T}_{c_{i}}\). **Determining the number of malware clusters**  
According to the cross-validation strategy, we should choose different values for \(k\) in hierarchical agglomerative clustering method. As stated in Section 4.1.3, we applied the complete-link agglomerative clustering method on malware action sequence set. Then, for different values of \(k\), its results in terms of reconstruction error are presented in Figure 4.  
As Figure 4 shows, different values can be considered for \(k\). According to the elbow method (see Section 4.1.3), the suitable value of \(k\) is one of the candidate values of \(k\_Set=\{3,6,12,17,20,24,\)[26; 27; 31; 36; 39]. As mentioned in Section 4.1.3, we tended to select the smallest \(k\) from the \(k\_Set\) such that it satisfies Conditions (1) and (2). To summarize, Tables 1 and 2 show the results of two values of \(k\) in which \(k=17\) satisfies the corresponding conditions but \(k=12\) does not. In other words, by considering \(k=12\), we have a cluster (i.e., Cluster 4) such that its size is great and its centroid is less than 0.5 (highlighted row in Table 1). Thus, we can choose one of the \(k\) values that is greater than or equal to 17. According to the experiments, which are discussed in Section 5.4.2, the best value of \(k\) is 24. **Training HMMs**  
As in Section 4.1.4, first we calculated the number of states of each cluster (i.e., \(N_{c_{i}}\)). Table 3 presents the number of states for each malware cluster as their corresponding unique actions on training data. According to Figure 2 and Table 3, we design program behavior-aware topology of each HMM, \(\lambda_{c_{i}}\). Then, by applying Algorithm 3, we computed their corresponding decision thresholds, \(\mathcal{T}_{c_{i}}\) and finally built all malware HMMs, \((\lambda_{c_{i}},\mathcal{T}_{c_{i}})\). Note that we only use 15% of benign action sequences to compute decision thresholds, \(\mathcal{T}_{c_{i}}\). Figure 4: Variation of reconstruction error for different number of malware clusters. Black points shows candidate \(k\) values. \begin{table}
\begin{tabular}{c c c} \hline
**Cluster No.** & **Cluster Size** & **Centroid** \\ \hline
1 & 273 & 0.65 \\ \hline
2 & 1638 & 0.59 \\ \hline
3 & 243 & 0.89 \\ \hline
4 & 318 & 0.41 \\ \hline
5 & 311 & 0.82 \\ \hline
6 & 268 & 0.81 \\ \hline
7 & 376 & 0.56 \\ \hline
8 & 510 & 0.62 \\ \hline
9 & 372 & 0.73 \\ \hline
10 & 588 & 0.68 \\ \hline
11 & 592 & 0.83 \\ \hline
12 & 860 & 0.95 \\ \hline \end{tabular}
\end{table} 
Table 1: The malware clusters for \(k=12\). \begin{table}
\begin{tabular}{c c c} \hline
**Cluster No.** & **Cluster Size** & **Centroid** \\ \hline  
\end{tabular}
\end{table} 
Table 2: The malware clusters for \(k=17\). \begin{table}
\begin{tabular}{c c c} \hline
**Cluster No. ** & **Cluster Size** & **Centroid** \\ \hline
1 & 468 & 0.79 \\ \hline
2 & 1170 & 0.61 \\ \hline
3 & 54 & 0.13 \\ \hline
4 & 264 & 0.58 \\ \hline
5 & 492 & 0.90 \\ \hline
6 & 100 & 0.63 \\ \hline
7 & 92 & 0.72 \\ \hline
8 & 284 & 0.59 \\ \hline
9 & 308 & 0.79 \\ \hline
10 & 64 & 0.56 \\ \hline
11 & 273 & 0.65 \\ \hline
12 & 243 & 0.89 \\ \hline
1 rate \(frac{j}=0.05\) in Algorithm 3 and, by default, we use program behavior-aware topology to train the HMMs, \(\lambda_{c_{i}}\). **The impact of clustering on the performance of \(HM^{3}aID\)**  
When \(k\), the number of clusters, increases in the clustering process of \(HM^{3}aID\), the corresponding reconstruction error decreases and also the number of clusters is increased, so it means we should learn more HMMs.