# An Approach for Anomaly Detection in Network Communications Using _k-Path_ Analysis
## 4 Three-State Markovian Approach
### Modeling, Estimation, and Hypothesis Testing  
We thus define the observed Markov model over \(e\), characterized by nine parameters,  
\[p_{\alpha,\beta}(e)=\mathbb{P}(\mathbf{S}_{t}(e)=\beta|\mathbf{S}_{t-1}(e)= \alpha)\ \ \text{for}\ \ (\alpha,\beta)\in\mathbb{S}^{2},\]  
where \(p_{\alpha,\beta}(e)\) represents the transition probability from state \(\alpha\) to state \(\beta\). We assume that the initial state of the model is fixed and known. Thus, the likelihood of the model is formulated as follows:  
\[\mathcal{L}\Big{(}(p_{\alpha,\beta}(e))_{(\alpha,\beta)\in\mathbb{S}^{2}}| \mathbf{s}(e,I)\Big{)}=\prod_{(\alpha,\beta)\in\mathbb{S}^{2}}\big{(}p_{ \alpha,\beta}(e)\big{)}^{n_{\alpha,\beta}(e)},\]  
where \(\mathbf{s}(e,I)=(\mathbf{s}_{t_{1}}(e),\mathbf{s}_{t_{2}}(e),\cdots,\mathbf{ s}_{t_{n}}(e))\) is the sequence of observation states on \((e,I)\) and \(n_{\alpha,\beta}(e)\) is the number of times the consecutive pair \(\{\alpha,\beta\}\) has been observed in \(\mathbf{s}(e,I)\) with  
\[\sum_{(\alpha,\beta)\in\mathbb{S}^{2}}  
The log-likelihood (\(\ell\)) is then obtained by taking the natural logarithm of the likelihood function, thus transforming the product into a sum:  
\[\ell\Big{(}(p_{\alpha,\beta}(e))_{(\alpha,\beta)\in\mathbb{S}^{2}}|\mathbf{s}(e,I)\Big{)}=\sum_{(\alpha,\beta)\in\mathbb{S}^{2}}n_{\alpha,\beta}(e)\log(p_{ \alpha,\beta}(e))\]  
The objective is to maximize this log-likelihood function with respect to the parameters \(\theta(e,I)=(p_{\alpha,\beta}(e))_{(\alpha,\beta)\in\mathbb{S}^{2}}\). This can be achieved using numerical optimization techniques. Sometimes it is necessary to consider constraints on the parameters; one common constraint is that for a given state \(\alpha\in\mathbb{S}\), the total transition probability from that state must be equal to 1:  
\[\sum_{l\in\mathbb{S}}p_{\alpha,l}(e)=1.\]  
We can introduce a Lagrange multiplier, denoted \(c_{\alpha}\), and modify the likelihood function to include the penalty term \(c_{\alpha}(\sum_{l\in\mathbb{S}}p_{\alpha,\beta}(e)-1)\). The parameter estimation problem then becomes that of maximizing this penalized likelihood function:  
\[\mathfrak{L}(p_{\alpha,\beta}(e),c_{\alpha})=\sum_{(\varepsilon_{1}, \varepsilon_{2})\in\mathbb{S}^{2}}n_{\varepsilon_{1},\varepsilon_{2}}(e)\log( p_{\varepsilon_{1},\varepsilon_{2}}(e))-c_{\alpha}(\sum_{l\in\mathbb{S}}p_{ \alpha,l}(e)-1).\]  
Using the method of Lagrange multipliers, we seek the value of the parameter \(p_{\alpha,\beta}(e)\) and the Lagrange multipliers \(c_{\alpha}\) that nullify the partial derivatives of the Lagrange function \(\mathfrak{L}(p_{\alpha,\beta}(e),c_{\alpha})\) with respect to the parameters \(p_{\alpha,\beta}(e)\) and the Lagrange multipliers \(c_{\alpha}\). Differentiating \(\mathfrak{L}(p_{\alpha,\beta}(e),c_{\alpha})\) with respect to \(p_{\alpha,\beta}(e)\) and setting the derivative to zero, we obtain:  
\[\frac{\partial\mathfrak{L}(p_{\alpha,\beta}(e),c_{\alpha})}{\partial p_{ \alpha,\beta}(e)}=\frac{n_{\alpha,\beta}(e)}{p_{\alpha,\beta}(e)}-c_{\alpha}=0\]  
Furthermore, since \(\sum_{\delta\in\mathbb{S}}p_{\alpha,\beta}(e)=1\), we then have:  
\[c_{\alpha}=\sum_{\delta\in\mathbb{S}}n_{\alpha,\delta}(e),\]  
\[\hat{p}_{\alpha,\beta}(e)=\frac{n_{\alpha,\beta}(e)}{\sum_{\delta\in\mathbb{ S}}n_{\alpha,\beta}(e)}.\]  
Now, we are discussing hypothesis testing within a statistical framework, specifically regarding the determination of whether new observations in a particular path (\(\gamma\)) are likely to have been generated by a known function of the parameters of the model associated with that path (\(\theta_{0}(\gamma)=(\theta_{0}(e_{1}),\theta_{0}(e_{2}),\cdots,\theta_{0}(e _{k}))\)), as opposed to hypotheses indicating that these parameters have changed.