# \(HM^{3}a1D\): Polymorphic Malware Detection Using Program Behavior-Aware Hidden Markov Model
## 4 Proposed Method: \(HM^{3}aID\)
### Training Phase
#### 4.1.4 Training HMMs  
This section is presented in three parts: (1) input sequences; (2) HMM topology; and (3) graining.  
**Input sequences:** Action sequences of programs at runtime are observation sequences.  
**HMM topology:** We define the topology of HMMs based on program behavior. Recall that each program consists of three main stages at runtime: (1) initialization; (2) running; and (3) termination. In the initialization stage, each program sets its variables by initial values and allocates its required resources. Thus, we consider this stage as following the serial Bakis topology. In the running stage, programs perform some iterative units of work in the form of conditions and loops. Thus, we consider this stage as following the parallel fully connected (ergodic) topology. The termination stage is somewhat similar to the initialization stage: it publishes the program outputs, deallocates the resources, and terminates the program. Thus, we consider this stage as following the Bakis topology. Figure 2 expresses the novel program behavior-aware HMM topology where the number of states at running stage should be determined.  
**Training:** To learn an HMM, \(\lambda_{c_{i}}=(\pi_{c_{i}},A_{c_{i}},B_{c_{i}})\), on each malware cluster \(c_{i}\), we must set its initial state probability \(\pi_{c_{i}}=\{\pi_{1}=1\}\); its transition probability matrix \(A_{c_{i}}=\{a_{\eta j}=P(q_{l+1}=S_{j}|q_{t}=S_{r})\}\); and its observation probability matrix \(B_{c_{i}}=\{b_{j}(v_{m})=P(O_{t}=v_{m}|q_{t}=S_{j})\}\). To learn HMM \(\lambda_{c_{i}}\), we first determine the number of states \(N_{c_{i}}\) and then initialize \(A_{c_{i}}\) and \(B_{c_{i}}\) matrices.  
According to the proposed program behavior-aware topology (Figure 2), matrix \(A_{c_{i}}\) consists of some transitions so the weights of other transitions are zero. Thus, we initialize the values of its non-zero elements randomly with constraint \(\sum_{j=1}^{N_{c_{i}}}a_{\eta j}=1\). We initialize matrix \(B_{c_{i}}\) randomly with constraint \(\sum_{m=1}^{M}b_{j}(v_{m})=1\), where \(M=26\) (i.e., the number of actions). Figure 3 shows a six-state HMM topology and its corresponding matrix \(A\).  
To estimate the number of states of each cluster (i.e., \(N_{c_{i}}\)), we compute the number of unique actions that are observed across all sequences corresponding to that cluster. Since they are based on three-stage program behavior-aware topology, the minimum and maximum values of \(N_{c_{i}}\) are 3 and 26, respectively.  
After calculation of \(N_{c_{i}}\) and initialization of \(A_{c_{i}}\) and \(B_{c_{i}}\), we apply the Baum-Welch algorithm [29] on each cluster \(c_{i}\) to train (the parameters of) its corresponding HMM, \(\lambda_{c_{i}}\). The Baum-Welch algorithm is an EM-like algorithm and guarantees to converge towards local optima. The Baum-Welch algorithm iterates the E step and the M step, yielding monotonically increasing log-likelihoods, and the algorithm is terminated when the difference of two subsequent log-likelihoods falls below \(\epsilon\) that is near to zero or the maximum number of iterations is met. Typically, the algorithm reaches different local maxima or saddle points for different initializations, so we run it multiple times on each cluster \(c_{i}\) with different initializations and we finally select HMM, \(\lambda_{c_{i}}\) that has the highest probability. Algorithm 2 shows the steps of training HMMs.