anomaly detection with Markov chain

Question

The paper uses a simple technique to detect intrusions in computer systems. I will briefly explain it and ask a question:

The paper proposes a simple 1-order Markov chain modelling approach to detect if a given sequence $S = S_1S_2S_3...S_n$ is an anomaly (Here $S_i$'s are Unix system commands) . The author determines the likelihood of $S$, $P(S)$, using the following equation

$P(S)=q_{S_1}\prod_{t=2}^{|S|}p_{S_{t-1}S_t}$

where $q_{S_1}$ is the probability of observing the symbol $S_1$ in the training set and $p_{S_{t-1}S_t}$ is the probability of observing the symbol $S_t$ after symbol $S_{t−1}$ in the training set. The inverse of $P(S)$ is the anomaly score for $S$.

(The description above is taken from this paper.)

And my question:

How can we handle the case if the sequences are of different sizes (the paper assumes sequences of fixed sizes). The problem is that longer sequences will have smaller probability values compared to shorter ones. So, longer sequences will more likely to be treated as anomalous. I think we need to apply a kind of normalization but I could not figure out what kind of normalization to apply.

Thanks

Answer 1

The final properties of the score may depend on the normalization procedure. Therefore, it may be better to keep using fixed length unix command sequences.

However, something that offers "basic consistency" is geometric average. Most likely : $\hat{P}(S)=(q_{S_1}\prod_{t=2}^{|S|}p_{S_{t-1}S_t})^{1/S}$

Therefore, typing two times the same sequence leads to the following :

$\hat{P}(S+S)=(q_{S_1} p_{S_{t}S_{1}}\prod_{t=2}^{|S|}p_{S_{t-1}S_t} \prod_{t=2}^{|S|}p_{S_{t-1}S_t})^{1/2S}$

If the sequence is long enough (i.e. $S$ large), you obtain that:

$\hat{P}(S+S)\approx\hat{P}(S)$