Animesh Nandi
ABSTRACT
We focus on the problem of detecting anomalous run-time behavior of distributed applications from their execution logs. Specifically we mine templates and template sequences from logs to form a control flow graph (cfg) spanning distributed components. This cfg represents the baseline healthy system state and is used to flag deviations from the expected behavior of runtime logs. The novelty in our work stems from the new techniques employed to: (1) overcome the instrumentation requirements or application specific assumptions made in prior log mining approaches, (2) improve the accuracy of mined templates and the cfg in the presence of long parameters and high amount of interleaving respectively, and (3) improve by orders of magnitude the scalability of the cfg mining process in terms of volume of log data that can be processed per day. We evaluate our approach using (a) synthetic log traces and (b) multiple real-world log datasets collected at different layers of application stack. Results demonstrate that our template mining, cfg mining, and anomaly detection algorithms have high accuracy. The distributed implementation of our pipeline is highly scalable and has more than 500 GB/day of log data processing capability even on a 10 low-end VM based (Spark + Hadoop) cluster. We also demonstrate the efficacy of our end-to-end system using a case study with the Openstack VM provisioning system.
Supplemental Material
- B. Abrahao, F. ChieriChetti, R. Kleinberg, and A. Panconesi. Trace complexity of network inference. In KDD, 2013. Google Scholar
Digital Library
- Appdynamics. www.appdynamics.com.Google Scholar
- I. Beschastnikh, Y. Brun, M. D. Ernst, A. Krishnamurthy, and T. E. Anderson. Mining temporal invariants from partially ordered logs. In SLAML, 2011. Google ScholarDigital Library
- D. Bosnacki, W. Lightenberg, M. Odenbrett, A. Wijs, and P. Hilbers. Parallel algorithms for transitive reduction of weighted graphs. In Math Maced, 2010.Google Scholar
- E. Cohen, M. Datar, S. Fujiwara, A. Gionis, P. Indyk, R. Motwani, J. D. Ullman, and C. Yang. Finding interesting associations without support pruning. In TKDE, 2001. Google ScholarDigital Library
- W. V. der Aalst, T. Weijters, and L. Maruster. Workflow mining: Discovering process models from event logs. In TKDE, 2004. Google ScholarDigital Library
- Elasticsearch: Search and analyze data in real time. https://www.elastic.co/products/elasticsearch.Google Scholar
- D. R. Ferreira and D. Gillblad. Discovering process models from unlabelled event logs. In BPM, 2009.Google ScholarDigital Library
- Q. Fu, J.-G. Lou, Y. Wang, and J. Li. Execution anomaly detection in distributed systems through unstructured log analysis. In ICDM, 2009. Google ScholarDigital Library
- M. Gomez-Rodriguez, J. Leskovec, and A. Krause. Inferring networks of diffusion and influence. In KDD, 2010.Google ScholarDigital Library
- C. W. Gunther and W. M. van der Aalst. Fuzzy mining - adaptive process simplification based on multi-perspective metrics. In BPM, 2007. Google ScholarDigital Library
- P. Indyk and R. Motwani. Approximate nearest neighbor - towards removing the curse of dimensionality. In STOC, 1998. Google ScholarDigital Library
- X. Ju, L. Soares, K. G. Shin, K. D. Ryu, and D. D. Silva. On fault resilience of openstack. In SOCC, 2013. Google ScholarDigital Library
- Kafka: A high-throughput distributed messaging system. http://kafka.apache.org.Google Scholar
- T. Li, F. Liang, S. Ma, and W. Peng. An integrated framework on mining log files for computing system management. In KDD, 2005. Google ScholarDigital Library
- Logstash: Collect, enrich and transform data. https://www.elastic.co/products/logstash.Google Scholar
- J.-G. Lou, Q. Fu, Y. Wang, and J. Li. Mining dependency in distributed systems through unstructured logs analysis. In SIGOPS Operation Systems Review, 2010. Google ScholarDigital Library
- J.-G. Lou, Q. Fu, S. Yang, J. Li, and B. Wu. Mining program workflow from interleaved traces. In KDD, 2010. Google ScholarDigital Library
- A. Makanju, A. Z. Heywood, and E. E. Milios. Clustering event logs using iterative partitioning. In KDD, 2009. Google ScholarDigital Library
- H. Mannila, H. Toivonen, and A. I. Verkamo. Discovery of frequent episodes in event sequences. In DMKD, 1997. Google ScholarDigital Library
- Openstack: Open-source software for creating public and private clouds. www.openstack.org.Google Scholar
- J. Pei, J. Han, B. Mortazavi, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu. Mining sequential patterns efficiently by prefix-projected pattern growth. In ICDE, 2001.Google ScholarDigital Library
- T. Reidimeister, M. Jiang, and P. A. Ward. Mining unstructured log files for recurrent fault diagnosis. In IM, 2011.Google ScholarCross Ref
- Spark: Lightning-fast cluster computing. http://spark.apache.org.Google Scholar
- J. Stearley. Towards informatic analysis of syslogs. In Cluster, 2004. Google ScholarDigital Library
- R. Vaarandi. A data clustering algorithm for mining patterns from event logs. In IPOM, 2003.Google ScholarCross Ref
- R. Vaarandi. A breadth first algorithm for mining frequent patterns from event logs. In Intell. Comm., 2004.Google ScholarCross Ref
- R. Vaarandi and M. Pihelgas. Logcluster - a data clustering and pattern mining algorithm for event logs. In CNSM, 2015. Google ScholarDigital Library
- T. Wu, Y. Chen, and J. Han. Association mining in large datasets: A re-examination of its measures. In PKDD, 2009.Google Scholar
- W. Xu, L. Huang, A. Fox, D. Patterson, and M. Jordan. Online system problem detection by mining patterns of console logs. In ICDM, 2009. Google ScholarDigital Library
- W. Xu, L. Huang, A. Fox, D. Patterson, and M. Jordan. Detecting large scale system problems by mining console logs. In ICML, 2010.Google Scholar
Index Terms
- Anomaly Detection Using Program Control Flow Graph Mining From Execution Logs
Recommendations
An automated approach for abstracting execution logs to execution events
Special Issue on Program Comprehension through Dynamic Analysis (PCODA)Execution logs are generated by output statements that developers insert into the source code. Execution logs are widely available and are helpful in monitoring, remote issue resolution, and system understanding of complex enterprise applications. There ...
Scalable Vertical Mining for Big Data Analytics of Frequent Itemsets
Database and Expert Systems ApplicationsAbstractAdvances in technology and the increasing growth of popularity on Internet of Things (IoT) for many applications have produced huge volume of data at a high velocity. These valuable big data can be of a wide variety or different veracity. Embedded ...
Event log anomaly detection method based on auto-encoder and control flow
AbstractAnomaly detection is widely used in the field of business process management, and researchers have proposed various anomaly detection algorithms to detect anomalies in event logs. However, existing research focuses on detecting anomalies in event ...
Comments