# An Approach for Anomaly Detection in Network Communications Using _k-Path_ Analysis
## 4 Three-State Markovian Approach
### Definition of the States  
Most anomaly detection methods based on the observed Markov model and the generalized likelihood ratio detect network anomalies using information extracted from flows, even though some flows may persist for a considerable duration. These methods are, therefore, more suitable for offline detection [4]. In order to detect malicious traffic at an early stage, [PERSON] et al. [4] aim to identify an anomaly based on the specific number of exchanges between two IP addresses. In this paper, aimed at furthering the method described in [4], we present an approach to identify such anomalies, based on the specific number of packets exchanged between two IP addresses. From an active graph, let us consider a _k-path_ of adjacent edges, denoted as  
\[\gamma=\{e_{1},e_{2},\cdots,e_{k-1},e_{k}\}\subset E.\]  
By collecting flow data along each edge of this path, we gather information about the number of packets exchanged per minute between the involved IP addresses. Let \(e\in\gamma\) ; at discrete time points \(t\in\{t_{0},t_{1},\cdots,t_{n}\}\) with \(t_{i}=t_{0}+i\) where \(t_{0}\) is the initial date and \(n\) is the total number of minutes in the sequence, we designate a time window \((e,I)\), where \(I=\{[t_{i-1},t_{i}],i=1,\cdots,n\}\). Let \(X_{t}(e)\) be the number of packets recorded on \(e\) during the period \([t-1,t]\). Let \(X(e,I)\) represent the data in window \((e,I)\) we have:  
\[X(e,I)=\left(X_{t_{i}}(e)\right)_{i=1,\cdots,n}.\]  
For each value of \(X_{t_{i}}(e)\), we can deduce a state for the edge \(e\). Figure 5 associated with Figure 3 illustrates the three zones where the variable \(X_{t}\) can be located. Each zone represents a state of the edge during the given period. The first zone, _State 1_, corresponds to the absence of packets; it represents periods of one minute where the counters are zero. In this configuration, we qualify this state as _inactive_. The second zone, _State 2_, is characterized by the presence of activity resulting in an exchange of packets, but at a moderate level. This means that the number of packet exchanges is controlled and does not exceed a defined threshold. In this regard, we describe this state as _moderate_. Finally, the third zone corresponds to cases where exchanges explode, far exceeding the defined threshold. This scenario, _State 3_, represents periods of intense activity where the number of packet exchanges is well beyond the established threshold. We qualify this state as _Peak_. In summary, these three zones describe the different possible states of the edge, ranging from inactivity to moderate activity, up to intense activity. This classification helps to better understand and analyze the behavior of the edge in different contexts and levels of activity. Figure 5: Zones of different states. We have a data process \(\mathbf{S}_{t_{i}}(e)\) representing the state of the edge during the period \([t_{i-1},t_{i}[\); it takes values in \(\mathbb{S}=\{1,2,3\}\) with  
\[\mathbf{S}_{t_{i}}(e)= \begin{cases}1&\text{if }X_{t_{i}}(e)=0\\ 2&\text{if }0<X_{t_{i}}(e)\leq X_{\text{Peak}}(e)\\ 3&\text{if }X_{t_{i}}(e)\geq X_{\text{Peak}}(e).\end{cases} \]  
In this formulation, \(X_{\text{Peak}}(e)\) represents the threshold of \(X_{t_{i}}(e)\), determining the transition from the moderate state to the peak state. A network data flux peak occurs when there is a sudden and significant increase in the volume of data traversing through a computer network over a defined period. However, determining an appropriate threshold to conclude that a flux peak has occurred can be challenging. One commonly used approach is to employ statistical analysis techniques to model the distribution of network data flux. These models help determine threshold values based on features such as the mean, standard deviation, quantiles, or other statistics (see the works of Standardization Working Group No. 5 [25]).