# \(HM^{3}a1D\): Polymorphic Malware Detection Using Program Behavior-Aware Hidden Markov Model
## 4 Proposed Method: \(HM^{3}aID\)
### Training Phase
#### 4.1.5 Computing Decision Thresholds  
Recall that, in \(HM^{3}alD\), we learn only malware HMMs \(\lambda_{c_{i}}\), to distinguish between malware and benign programs at detection phase. In this section, we compute a threshold \(\mathcal{T}_{c_{i}}\) on each HMM \(\lambda_{c_{i}}\) using another fraction of malware action sequences and some benign action sequences. To present well the process of computing the decision thresholds, first we devise some definitions about the HMM threshold concept. Figure 3: A six-state program behavior-aware HMM topology and its corresponding transition probability matrix \(A\). Figure 2: The proposed program behavior-aware HMM topology in \(HM^{3}alD\). ```
0:\(\mathcal{C}=\{c_{1},c_{2},\ldots,c_{k}\}\) denotes the set of malware clusters
0: Trained HMMs set, \(TrainedHMMs=\{\lambda_{c_{1}},\lambda_{c_{2}},\ldots,\lambda_{c_{k}}\}\). 1:\(TrainedHMMs=\emptyset\)\(\triangleright\) an empty set
2:for\(i=1\) to \(|\mathcal{C}|\)do
3: Estimate the number of states (\(N_{c_{i}}\)) for cluster \(c_{i}\)
4: Initialize \(\tau_{c_{i}}\), \(A_{i}\) and \(B_{i}\) using the proposed program behavior-aware topology
5: Compute \(\lambda_{c_{i}}(A_{i},B_{i})\) using Baum-Welch algorithm
6: Add \(\lambda_{c_{i}}\) to \(TrainedHMMs\)
7:endfor
```  
**Algorithm 2**\(Hm^{3}aID\)**-Training phase  
**Definition 1**. : _For each malware HMM \(\lambda_{c_{i}}\) and its corresponding threshold \(\mathcal{T}_{c_{i}}\), the pair \((\lambda_{c_{i}},\mathcal{T}_{c_{i}})\) is a discriminator such that an observation (action) sequence \(O^{l}\) is identified as a malware action sequence if Equation (2) is satisfied. Note that, from now on, we use \(LP(O|\lambda)\) instead of \(log(P(O|\lambda))\) for simplicity._  
\[LP(O^{l}|\lambda_{c_{i}})\geq\mathcal{T}_{c_{i}}= \begin{cases}1,&\text{if $O^{l}$ is a malware action sequence}\\ 0,&\text{otherwise, no decision}\end{cases} . \tag{2}\]  
In Equation (2), if the output is zero, the result (benign/malware) depends on the other HMM decisions. **Definition 2**. : _For each malware HMM \(\lambda_{c_{i}}\), its corresponding rejection rate \(R_{c_{i}}\) is a certain fraction of \(V_{c_{i}}\) (the validation part of observation sequences of malware cluster \(c_{i}\)) that specifies the maximum permissible error on HMM \(\lambda_{c_{i}}\). For simplicity, we set \(R_{c_{1}}=R_{c_{2}}=\ldots=R_{c_{k}}\), which leads to different values of the decision thresholds \(\mathcal{T}_{c_{i}}\)._  
**Definition 3**. : _For each malware HMM \(\lambda_{c_{i}}\), the maximum benign probability \(Pb_{c_{i}}\) is the greatest log probability that is returned by HMM \(\lambda_{c_{i}}\) for \(V_{b}\), benign action sequences, and is computed by Equation (3)._  
\[Pb_{c_{i}}=\max_{l}\{LP(O^{l}|\lambda_{c_{i}}),\text{ for all }O^{l}\in V_{b}\}. \tag{3}\]  
The pseudo-code of computing decision thresholds is shown in Algorithm 3. To compute threshold \(\mathcal{T}_{c_{i}}\) by using Algorithm 3, we proceed as follows. First, we estimate the log probabilities of the all action sequences belong to \(V_{c_{i}}\) and reorder them in ascending order (Lines 3-8). Then, we obtain the malware threshold point \(tm\) (Lines 9-10). In many conditions, we find that the \(Pb_{c_{i}}\) is less than or equal to \(tm\), which means that the corresponding HMM \(\lambda_{c_{i}}\) is sufficiently powerful and returns small log probabilities for benign action sequences. Thus, we finally compute \(\mathcal{T}_{c_{i}}\) based on this condition (lines 12-16). ```
1:\(\textit{fracrej}=R_{c_{1}}=R_{c_{2}}=\ldots=R_{c_{k}}\). 2:\(V_{\mathrm{C}}=\{V_{\mathrm{c_{1}}},V_{\mathrm{c_{2}}},\ldots,V_{\mathrm{c_{k} }}\}\) and each \(V_{c_{i}}=\{O^{l}\}_{l=1}^{|V_{c_{i}}|}\) is the malware validation part of cluster \(c_{i}\). \(V_{b}=\{O^{l}\}_{l=1}^{|V_{b_{i}}|}\); is a set of benign action sequences. \(\textit{Malware\_HMM}=\{\lambda_{c_{1}},\lambda_{c_{2}},\ldots,\lambda_{c_{k}}\}\), learned HMM set corresponding to malware clusters.