A Multi-Order Markov Chain Based Scheme for Anomaly Detection

This paper presents a feasible multi-order Markov chain based scheme for anomaly detection in server systems. In our approach, both the high-order Markov chain and multivariate time series are taken into account, along with the detailed design of training and testing algorithms. To evaluate its effectiveness, the Defense Advanced Research Projects Agency (DARPA) Intrusion Detection Evaluation Data Set is used as stimuli to our model, by which system calls and the corresponding return values form a two-dimensional input set. The calculation result shows that this approach is able to produce several effective indicators of anomalies. In addition to the absolute values given by an individual single-order model, we also notice a novelty unprecedented before, i.e., the changes in ranking positions of outputs from different-order ones also correlate closely with abnormal behaviours. Moreover, the analysis and application proves our approach's efficiency in consuming reasonable cost of time and storage.