# An Approach for Anomaly Detection in Network Communications Using _k-Path_ Analysis
## 4 Three-State Markovian Approach
### Modeling, Estimation, and Hypothesis Testing
In other words, given new observations \(\mathbf{S}(\gamma,I_{1})=\mathbf{s}(\gamma,I_{1})\), the goal is to test the null hypothesis \(H_{0}:\theta(\gamma,I_{1})=\theta_{0}(\gamma)\) against the alternative hypothesis that can be formed by restricting the global parameter space \(\Theta\) to a subset \(\Theta_{A}\subset\Theta\). The statistical test of the generalized likelihood ratio is a relevant measure to use in this context. It is defined as follows:  
\[\lambda(\gamma,I_{1})=-2\log\left(\frac{\mathcal{L}(\theta_{0}(\gamma)| \mathbf{s}(\gamma,I_{1}))}{\sup_{\theta\in\Theta_{A}}\mathcal{L}(\theta( \gamma,I_{1})|\mathbf{s}(\gamma,I_{1}))}\right)\]  
with  
\[\gamma=\{e_{1},e_{2},\cdots,e_{k-1},e_{k}\}\subset E.\]  
In other words, this statistic measures the divergence between the likelihood of the model under the null hypothesis and the maximum likelihood under all alternative hypotheses. In [PERSON] et al. [4], the authors introduce the assumption of independence between the edges of a _k-path_. This assumption translates to:  
\[\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)},\]0  
So, this assumption gives us the ability to model the behavior of each edge of the _k-path_ to deduce a modeling of the _k-path_, \(\gamma\). To design a generalized likelihood ratio test, it is imperative to constrain our global parameter space to include alternatives reflecting the behaviors of attackers we seek to detect. These alternatives must be formulated generically to encompass a variety of behaviors. Our underlying hypothesis is that the attacker's behavior leads to an increase in the maximum likelihood estimators of the model parameters. Specifically, we posit that the attacker's actions result in an increase in certain transition probabilities between specific pairs of states such as \((\alpha,\beta)\in\mathbb{S}^{2}\) where \((\alpha\leq\beta)\in\mathbb{S}^{2}\). Additionally, the attacker's behavior will also manifest as a decrease in the frequency of observing state 1 in the sequences of observations. For each \(e\in\gamma\), this concerns the transition probabilities from state \(\alpha\) to state \(\beta\) with \(\beta\geq\alpha\) where \(\beta>1\). \[ \begin{cases}H_{0}:\forall\alpha,\beta,\ \hat{p}_{\alpha,\beta}(e)\leq\hat{p}_{ \alpha,\beta}(e)\ \ \text{with}\ \ \beta\geq\alpha\ \ \text{or}\ \ \hat{f}_{1}(e)\geq\hat{f}_{1}(e)\\ H_{1}:\exists\alpha,\beta,\ \hat{p}_{\alpha,\beta}(e)>\hat{p}_{\alpha,\beta}(e)\ \ \text{with}\ \ \beta\geq\alpha\ \ \text{and}\ \ \hat{f}_{1}(e)<\hat{f}_{1}(e),\end{cases} \]  
where \((\hat{p}_{\alpha,\beta}(e))_{(\alpha,\beta)\in\mathbb{S}^{2}}\) are the historical parameter values on \(e\), \(\hat{f}_{1}(e)\) is the frequency of observing the state 1 in the historical observations on \(e\), \((\hat{p}_{\alpha,\beta}(e))_{(\alpha,\beta)\in\mathbb{S}^{2}}\) are the parameter values that maximize the likelihood of the model for a new series of observations on \(e\), and \(\hat{f}_{1}(e)\) is the frequency of observing the state 1 for the new series of observations on \(e\). Thus, for any edge \(e\in\gamma\), we can determine the statistic of the generalized likelihood ratio \(\lambda(e,I_{1})\) given by:  
\[\lambda(e,I_{1})=-2\log\left(\frac{\mathcal{L}\Big{(}(\tilde{p}_{\alpha,\beta }(e))_{(\alpha,\beta)\in\mathbb{S}^{2}}|\mathbf{S}(e,I_{1})=\mathbf{s}(e,I_{1 })\Big{)}}{\mathcal{L}\Big{(}(\hat{p}_{\alpha,\beta}(e))_{(\alpha,\beta)\in \mathbb{S}^{2}}|\mathbf{S}(e,I_{1})=\mathbf{s}(e,I_{1})\Big{)}}\right).\]  
We are seeking a \(p\)-value for the observed generalized likelihood ratio test, \(\lambda(\gamma,I_{1})\). The assumption of independence among network communications [4] implies:  
\[\lambda(\gamma,I_{1})=\sum_{e\in\gamma}\lambda(e,I_{1}).\]  
Under conditions of moderate regularity, the generalized likelihood ratio test \(\lambda(e,.