An Online Log Anomaly Detection Method Based on Grammar Compression
Yu Han Gao · Chinese Journal of Computers · 2014
Nowadays,mining program logs is a widely used technique for detecting anomalies in program states.Basically,existing anomaly detection methods require considerable computation efforts,or their effectiveness relies on some prior assumptions of the distribution holding on test logs.Therefore,they can hardly work online and cannot be used in all scenarios.To address the aforementioned problems,this paper proposed a new anomaly detection method called CADM. CADM exploited relative entropy between test logs and normal logs to measure the anomalous level.Instead of computing the relative entropy directly based on predefined distribution family, our method took advantage of the relationship between relative entropy and compression size by an adapted grammar-based compression method and eliminated such kind of assumptions.In addition, our method has only an O(n)computation complexity and scales well on large logs.Experiments with both synthetic logs and real world logs show that our method is more suitable for online log mining tasks since it has higher detection accuracy on broader variety of program logs.