Dynamic syslog mining for network failure monitoring

ABSTRACT

Syslog monitoring technologies have recently received vast attentions in the areas of network management and network monitoring. They are used to address a wide range of important issues including network failure symptom detection and event correlation discovery. Syslogs are intrinsically dynamic in the sense that they form a time series and that their behavior may change over time. This paper proposes a new methodology of dynamic syslog mining in order to detect failure symptoms with higher confidence and to discover sequential alarm patterns among computer devices. The key ideas of dynamic syslog mining are 1) to represent syslog behavior using a mixture of Hidden Markov Models, 2) to adaptively learn the model using an on-line discounting learning algorithm in combination with dynamic selection of the optimal number of mixture components, and 3) to give anomaly scores using universal test statistics with a dynamically optimized threshold. Using real syslog data we demonstrate the validity of our methodology in the scenarios of failure symptom detection, emerging pattern identification, and correlation discovery.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 2: L. E. Baum and T. Petrie and G. Soules and N. Weiss. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. The Annals of Statistics, 41(1):164--171,1970.
• 3: L. Burns and J. L. Hellerstein and S. Ma and C. S. Perng and D. A. Rabenhorst and D. Taylor. A systematic approach to discovering correlation rules for event management. In Proc. of IEEE/IFIP International Sysmposium on Integrated Network Management, 2001.
• 4: G. Jakobson and M. D. Weissman. Alarm correlation. IEEE Networks, 37:52--59, 1993.
• 5: Stephen E. Hansen , E. Todd Atkins, Automated System Monitoring and Notification With Swatch, Proceedings of the 7th USENIX conference on System administration, November 01-05, 1993, Monterey, California, USA
• 6: Mika Klemettinen , Heikki Mannila , Hannu Toivonen, Rule Discovery in Telecommunication AlarmData, Journal of Network and Systems Management, v.7 n.4, p.395-423, 7 [doi>10.1023/A:1018787815779]
• 7: R. E. Krichevsky and V. K. Trofimov. The performance of universal encoding. IEEE Trans. on Inform. Theory, 27:199--207, 1981.
• 8: C. Lonvick. The BSD syslog protocol, RFC, 3164, 2001.
• 9: Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997 [doi>10.1023/A:1009748302351]
• 10: Y. Maruyama and K. Yamanishi. Dynamic model selection with its applications to computer security. In Proc. of 2004 IEEE International Workshop on Information Theory, 2004.
• 11: Radford M. Neal , Geoffrey E. Hinton, A view of the EM algorithm that justifies incremental, sparse, and other variants, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 12: Chang-Shing Perng , David Thoenen , Genady Grabarnik , Sheng Ma , Joseph Hellerstein, Data-driven validation, completion and construction of event relationship networks, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956848]
• 13: J. Rissanen. Universal coding, information, prediction, and estimation. IEEE Trans. on Inform. Theory, 30:629--636, 1984.
• 14: P. Smyth. Markov monitoring with unknown states. IEEE Journal on Selected Areas in Communications (JSAC), Special Issue on Intelligent Signal Processing for Communications, 1994.
• 15: M. Steinder and A. Sethi. The present and future of event correlation: A need for end-to-end service fault localization. In Proc. of 2001 World Multi-Conference on Systemics, Cybernetics and Informatics, 2001.
• 16: Małgorzata Steinder , Adarshpal S. Sethi, Probabilistic fault localization in communication systems using belief networks, IEEE/ACM Transactions on Networking (TON), v.12 n.5, p.809-822, October 2004 [doi>10.1109/TNET.2004.836121]
• 17: R. Vaarandi. A data clustering algorithm for mining patterns from event logs. In Proc. of 2003 IEEE Workshop on IP Operations & Management (IPOM2003), 2003.
• 18: R. Vaarandi. Sec - a lightweight event correlation tool. In Proc. of 2002 IEEE Workshop on IP Operations & Management (IPOM2002), 2002.
• 19: A. J. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. on Inform. Theory, IT-13:260--267, 1967.
• 20: Kenji Yamanishi , Jun-Ichi Takeuchi , Graham Williams , Peter Milne, On-line unsupervised outlier detection using finite mixtures with discounting learning algorithms, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.320-324, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347160]
• 21: Kenji Yamanishi , Jun-ichi Takeuchi, A unifying framework for detecting outliers and change points from non-stationary time series data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775148]
• 22: S. A. Yemini and S. Kliger and E. Mozes and Y. Yemini and D. Ohsie. High speed and robust event correlation. IEEE Communications Magazine, 34(5):82--90, 1996.
• 23: J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Trans. on Inform. Theory, IT-24:530--536, 1978.
• 24: J. Ziv. On classification with empirically observed statistics and universal data compression. IEEE Trans. on Inform. Theory, IT-34:278--286, 1988.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Experimentation, Theory

Keywords:
correlation analysis, failure detection, model selection, probabilistic modeling, syslog mining