Anomaly Detection Using Program Control Flow Graph Mining From Execution Logs
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.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Most related work infers the application topology using Control Flow Graphs extracted from logs or distributed traces to capture how microservices depend on each other.
“Most related work infers the application topology. It does this by using Control Flow Graphs (CFG) extracted from logs or distributed traces to capture how microservices depend on each other [11].”
From Toward Context-Aware Anomaly Detection for AIOps in Microservices Using Dynamic Knowledge Graphs (2026) · cites this paper as [11]
Cites
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188 · see citing works
Workflow mining: discovering process models from event logs
van der Aalst, W. M. P., Weijters, T., & Măruşter, L. (2004) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2004.47 · Cited by 2,216 · see citing works
PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth
Pei, J., Han, J., Mortazavi-Asl, B., Pinto, H. M., Chen, Q., Umeshwar Dayal, B., & Hsu, M. (2005) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2001.914830 · Cited by 1,791 · see citing works
Discovery of Frequent Episodes in Event Sequences
Mannila, H., Toivonen, H. T. T., & Verkamo, A. I. (1997) · Data Mining and Knowledge Discovery · doi:10.1023/a:1009748302351 · Cited by 1,468 · see citing works
Fuzzy Mining – Adaptive Process Simplification Based on Multi-perspective Metrics
Günther, C., & van der Aalst, W. M. P. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-75183-0_24 · Cited by 894 · see citing works
Execution Anomaly Detection in Distributed Systems through Unstructured Log Analysis
Fu, Q., Lou, J., Wang, Y., & Jiang, L. (2009) · Proceedings · doi:10.1109/icdm.2009.60 · Cited by 555 · see citing works
A data clustering algorithm for mining patterns from event logs
Vaarandi, R. (2004) · doi:10.1109/ipom.2003.1251233 · Cited by 461 · see citing works
Inferring Networks of Diffusion and Influence
Gomez-Rodriguez, M., Leskovec, J., & Krause, A. (2012) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2086737.2086741 · Cited by 451 · see citing works
Clustering event logs using iterative partitioning
Makanju, A., Zincir-Heywood, N., & Milios, E. (2009) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1557019.1557154 · Cited by 346 · see citing works
Finding interesting associations without support pruning
Cohen, E., Datar, M., Fujiwara, S., Gionis, A., Indyk, P., Motwani, R., Ullman, J. D., & Yang, C. (2001) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.908981 · Cited by 343 · see citing works
LogCluster - A data clustering and pattern mining algorithm for event logs
Vaarandi, R., & Pihelgas, M. (2015) · Conference on Network and Service Management · doi:10.1109/cnsm.2015.7367331 · Cited by 294 · see citing works
Online System Problem Detection by Mining Patterns of Console Logs
Xu, W., Huang, L., Fox, A., Patterson, D. A., & Jordan, M. I. (2009) · Proceedings · doi:10.1109/icdm.2009.19 · Cited by 207 · see citing works
Discovering Process Models from Unlabelled Event Logs
Ferreira, D. R., & Gillblad, D. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03848-8_11 · Cited by 122 · see citing works
Towards informatic analysis of syslogs
Stearley, J. (2005) · Proceedings · doi:10.1109/clustr.2004.1392628 · Cited by 120 · see citing works
Mining program workflow from interleaved traces
Lou, J., Fu, Q., Yang, S., et al. (2010) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1835804.1835883 · Cited by 104 · see citing works
Mining dependency in distributed systems through unstructured logs analysis
Lou, J., Fu, Q., Wang, Y., et al. (2010) · ACM SIGOPS Operating Systems Review · doi:10.1145/1740390.1740411 · Cited by 99 · see citing works
A Breadth-First Algorithm for Mining Frequent Patterns from Event Logs
Vaarandi, R. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30179-0_27 · Cited by 82 · see citing works
Trace complexity of network inference
Abrahão, B., Chierichetti, F., Kleinberg, R., et al. (2013) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2487575.2487664 · Cited by 82 · see citing works
An integrated framework on mining logs files for computing system management
Li, T., Liang, F., Ma, S., et al. (2005) · doi:10.1145/1081870.1081972 · Cited by 72 · see citing works
On fault resilience of OpenStack
Ju, X., Soares, L., Shin, K. G., et al. (2013) · Symposium on Cloud Computing · doi:10.1145/2523616.2523622 · Cited by 60 · see citing works
Association Mining in Large Databases: A Re-examination of Its Measures
Wu, T., Chen, Y., & Han, J. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-74976-9_66 · Cited by 59 · see citing works
Mining unstructured log files for recurrent fault diagnosis
Reidemeister, T., Jiang, M., & Ward, P. A. S. (2011) · IFIP/IEEE International Symposium on Integrated Network Management (IM) · doi:10.1109/inm.2011.5990536 · Cited by 34 · see citing works
Mining temporal invariants from partially ordered logs
Beschastnikh, I., Brun, Y., Ernst, M. D., et al. (2011) · doi:10.1145/2038633.2038636 · Cited by 28 · see citing works
Detecting Large-Scale System Problems by Mining Console Logs
Xu, W., & Huang, L. (2010) · Cited by 28 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Robust Anomaly Detection for Multivariate Time Series through Stochastic Recurrent Neural Network
Su, Y., Zhao, Y., Niu, C., Liu, R., Sun, W., & Pei, D. (2019) · Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining · doi:10.1145/3292500.3330672 · Cited by 1,804 · see citing works
LogAnomaly: Unsupervised Detection of Sequential and Quantitative Anomalies in Unstructured Logs
Meng, W., Liu, Y., Zhu, Y., Zhang, S., Pei, D., Liu, Y., Chen, Y., Zhang, R., Tao, S., Sun, P., et al. (2019) · Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2019/658 · Cited by 708 · see citing works
A Survey on Automated Log Analysis for Reliability Engineering
He, S., He, P., Chen, Z., Yang, T., Su, Y., & Lyu, M. R. (2022) · ACM Computing Surveys · doi:10.1145/3460345 · Cited by 334 · see citing works
Soldani, J., & Brogi, A. (2023) · ACM Computing Surveys · doi:10.1145/3501297 · Cited by 256 · see citing works
Unsupervised Detection of Microservice Trace Anomalies through Service-Level Deep Bayesian Networks
Liu, P., Xu, H., Ouyang, Q., Jiao, R., Chen, Z., Zhang, S., Yang, J., Mo, L., Zeng, J., Xue, W., et al. (2020) · 2020 IEEE 31st International Symposium on Software Reliability Engineering (ISSRE) · doi:10.1109/issre5003.2020.00014 · Cited by 252 · see citing works
Detecting anomalies in microservices with execution trace comparison
Meng, L., Ji, F., Sun, Y., & Wang, T. (2021) · Future Generation Computer Systems · doi:10.1016/j.future.2020.10.040 · Cited by 70 · see citing works
Workflow-Aware Automatic Fault Diagnosis for Microservice-Based Applications With Statistics
Wang, T., Zhang, W., Xu, J., & Gu, Z. (2020) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2020.3022028 · Cited by 54 · see citing works
Panahandeh, M., Hamou-Lhadj, A., Hamdaqa, M., & Miller, J. (2024) · Journal of Systems and Software · doi:10.1016/j.jss.2023.111917 · Cited by 49 · see citing works
Anomaly Detection in Microservice-Based Systems
Nobre, J., Pires, E. J. S., & Reis, A. (2023) · Applied Sciences · doi:10.3390/app13137891 · Cited by 34 · see citing works
Lin, W., Ma, M., Pan, D., & Wang, P. (2018) · 2018 IEEE 37th International Performance Computing and Communications Conference (IPCCC) · doi:10.1109/pccc.2018.8711092 · Cited by 29 · see citing works
AI for IT Operations (AIOps) on Cloud Platforms: Reviews, Opportunities and Challenges
Cheng, Q., Sahoo, D., Saha, A., Yang, W., Liu, C., Woo, G., Singh, M., Saverese, S., & Hoi, S. C. H. (2023) · arXiv · doi:10.48550/arxiv.2304.04661 · Cited by 23 · see citing works
AcLog: An Approach to Detecting Anomalies from System Logs with Active Learning
Duan, C., Jia, T., Li, Y., & Huang, G. (2023) · 2023 IEEE International Conference on Web Services (ICWS) · doi:10.1109/icws60048.2023.00062 · Cited by 20 · see citing works
AFALog: A General Augmentation Framework for Log-based Anomaly Detection with Active Learning
Duan, C., Jia, T., Cai, H., Li, Y., & Huang, G. (2023) · 2023 IEEE 34th International Symposium on Software Reliability Engineering (ISSRE) · doi:10.1109/issre59848.2023.00068 · Cited by 17 · see citing works
Ren, R., Wang, Y., Liu, F., Li, Z., & Xie, G. (2023) · 2023 IEEE/ACM 31st International Symposium on Quality of Service (IWQoS) · doi:10.1109/iwqos57198.2023.10188773 · Cited by 16 · see citing works
Efficient and Robust Trace Anomaly Detection for Large-Scale Microservice Systems
Zhang, S., Pan, Z., Liu, H., Jin, P., Sun, Y., Ouyang, Q., Wang, J., Jia, X., Zhang, Y., Yang, H., et al. (2023) · 2023 IEEE 34th International Symposium on Software Reliability Engineering (ISSRE) · doi:10.1109/issre59848.2023.00012 · Cited by 14 · see citing works
Toward Context-Aware Anomaly Detection for AIOps in Microservices Using Dynamic Knowledge Graphs
Moens, P., Steenwinckel, B., Ongenae, F., Volckaert, B., & Hoecke, S. V. (2026) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2026.3652304 · Cited by 6 · see citing works
“It does this by using Control Flow Graphs (CFG) extracted from logs or distributed traces to capture how microservices depend on each other [11].”
syslrn: learning what to monitor for efficient anomaly detection
Sanvito, D., Siracusano, G., Santhanam, S., Gonzalez, R., & Bifulco, R. (2022) · Proceedings of the 2nd European Workshop on Machine Learning and Systems · doi:10.1145/3517207.3526979 · Cited by 4 · see citing works
MicroKGCL: A Knowledge Graph for Root Cause Localization of Feedback Issues in Microservices
Yao, X.-W., Lu, Q.-C., Li, Q., Liu, L.-L., & Zhu, Z.-C. (2023) · 2023 IEEE 23rd International Conference on Software Quality, Reliability, and Security (QRS) · doi:10.1109/qrs60937.2023.00067 · Cited by 3 · see citing works
- Authors
- Nandi, A., Mandal, A., Atreja, S., Dasgupta, G. B., & Bhattacharya, S.
- Affiliations
- IBM (India) (IN)
- Indian Institute of Technology Kanpur (IN)
- Venue
- Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
- Publisher
- ACM
- Published
- 2016-08-13
- Pages
- 215-224
- OpenAlex
- W2508465325
- Cited by
- 154
- References
- 24
- Citations by year
- 2026: 13 · 2025: 15 · 2024: 15 · 2023: 26 · 2022: 18 · 2021: 29 · 2020: 11 · 2019: 9 · 2018: 8 · 2017: 10
- FWCI
- 7.69
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Software System Performance and Reliability
- Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Anomaly Detection Techniques and Applications
- Keywords
- anomaly detection, execution logs, log mining, distributed applications, scalability
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
