skip to main content
10.1145/2623330.2623729acmconferencesArticle/Chapter ViewAbstractPublication PageskddConference Proceedingsconference-collections
research-article

Towards scalable critical alert mining

Published: 24 August 2014 Publication History

Abstract

Performance monitor software for data centers typically generates a great number of alert sequences. These alert sequences indicate abnormal network events. Given a set of observed alert sequences, it is important to identify the most critical alerts that are potentially the causes of others. While the need for mining critical alerts over large scale alert sequences is evident, most alert analysis techniques stop at modeling and mining the causal relations among the alerts.
This paper studies the critical alert mining problem: Given a set of alert sequences, we aim to find a set of k critical alerts such that the number of alerts potentially triggered by them is maximized. We show that the problem is intractable; therefore, we resort to approximation and heuristic algorithms. First, we develop an approximation algorithm that obtains a near-optimal alert set in quadratic time, and propose pruning techniques to improve its runtime performance. Moreover, we show a faster approximation exists, when the alerts follow certain causal structure. Second, we propose two fast heuristic algorithms based on tree sampling techniques. On real-life data, these algorithms identify a critical alert from up to 270,000 mined causal relations in 5 seconds; meanwhile, they preserve more than 80% of solution quality, and are up to 5,000 times faster than their approximation counterparts.

Supplementary Material

MP4 File (p1057-sidebyside.mp4)

References

[1]
Full version. http://www.cs.ucsb.edu/?bzong/doc/full.pdf.
[2]
S. O. Al-Mamory and H. Zhang. Intrusion detection alarms reduction using root cause analysis and clustering. Computer Communications, 32(2):419--430, 2009.
[3]
A. Arnold, Y. Liu, and N. Abe. Temporal causal modeling with graphical granger methods. In SIGKDD, 2007.
[4]
C. Budak, D. Agrawal, and A. El Abbadi. Limiting the spread of misinformation in social networks. In WWW, 2011.
[5]
H. Cam and P. Mouallem. Mission-aware time-dependent cyber asset criticality and resilience. CSIIRW, 2013.
[6]
W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In SIGKDD, 2010.
[7]
W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In SIGKDD, 2009.
[8]
W. Chen, Y. Yuan, and L. Zhang. Scalable influence maximization in social networks under the linear threshold model. In ICDM, 2010.
[9]
S. Cheng, H. Shen, J. Huang, G. Zhang, and X. Cheng. Staticgreedy: solving the scalability-accuracy dilemma in influence maximization. In CIKM, 2013.
[10]
O. Dain and R. K. Cunningham. Fusing a heterogeneous alert stream into scenarios. In ACM workshop on Data Mining for Security Applications, volume 13, 2001.
[11]
N. Du, L. Song, M. Gomez-Rodriguez, and H. Zha. Scalable influence estimation in continuous-time diffusion networks. In NIPS, 2013.
[12]
P. Gill, N. Jain, and N. Nagappan. Understanding network failures in data centers: measurement, analysis, and implications. In ACM SIGCOMM Computer Communication Review, 2011.
[13]
A. Goyal, F. Bonchi, and L. V. Lakshmanan. A data-based approach to social influence maximization. VLDB, 2011.
[14]
A. Goyal, W. Lu, and L. V. Lakshmanan. Celf++: optimizing the greedy algorithm for influence maximization in social networks. In WWW, 2011.
[15]
X. He, G. Song, W. Chen, and Q. Jiang. Influence blocking maximization in social networks under the competitive linear threshold model. In SDM, 2012.
[16]
K. Julisch. Clustering intrusion detection alarms to support root cause analysis. TISSEC, 2003.
[17]
K. Julisch and M. Dacier. Mining intrusion detection alarms for actionable knowledge. In SIGKDD, 2002.
[18]
B. Karrer and M. E. J. Newman. Random graph models for directed acyclic networks. Phys. Rev. E, 2009.
[19]
D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In SIGKDD, 2003.
[20]
S. Kim and E. N. Brown. A general statistical framework for assessing granger causality. In ICASSP, 2010.
[21]
T. Lappas, E. Terzi, D. Gunopulos, and H. Mannila. Finding effectors in social networks. In SIGKDD, 2010.
[22]
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In SIGKDD, 2007.
[23]
A. A. Mahimkar, Z. Ge, A. Shaikh, J. Wang, J. Yates, Y. Zhang, and Q. Zhao. Towards automated performance diagnosis in a large iptv network. In ACM SIGCOMM Computer Communication Review, 2009.
[24]
D. S. Mitrinović, J. E. Pečarić, and A. Fink. Bernoulli's inequality. In Classical and New Inequalities in Analysis, 1993.
[25]
J. Moore, J. Chase, K. Farkas, and P. Ranganathan. Data center workload monitoring, analysis, and emulation. In Eighth Workshop on Computer Architecture Evaluation using Commercial Workloads, 2005.
[26]
K. P. Murphy. Dynamic bayesian networks: representation, inference and learning. PhD thesis, University of California, 2002.
[27]
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions-I. Mathematical Programming, 14(1):265--294, 1978.
[28]
H. Nguyen and R. Zheng. Influence spread in large-scale social networks--a belief propagation approach. In PKDD, 2012.
[29]
U. H. Nielsen, J.-P. Pellet, and A. Elisseeff. Explanation trees for causal bayesian networks. In UAI, pages 427--434, 2008.
[30]
M. G. Rodriguez and B. Schölkopf. Influence maximization in continuous time diffusion networks. In ICML, 2012.
[31]
A. K. Seth. A matlab toolbox for granger causal connectivity analysis. Journal of neuroscience methods, 2010.
[32]
C. Silverstein, S. Brin, R. Motwani, and J. Ullman. Scalable techniques for mining causal structures. Data Mining and Knowledge Discovery, 2000.
[33]
J. Tian and J. Pearl. Probabilities of causation: Bounds and identification. Annals of Mathematics and Artificial Intelligence, 2000.
[34]
A. W. Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[35]
V. V. Vazirani. Approximation Algorithms. Springer 2003.
[36]
C. Zhou, P. Zhang, J. Guo, X. Zhu, and L. Guo. Ublf: An upper bound based approach to discover influential nodes in social networks. In ICDM, 2013.

Cited By

View all
  • (2020)Distributed Attack Modeling Approach Based on Process Mining and Graph SegmentationEntropy10.3390/e2209102622:9(1026)Online publication date: 14-Sep-2020
  • (2020)Kronos: Lightweight Knowledge-based Event Analysis in Cyber-Physical Data Streams2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00165(1766-1769)Online publication date: Apr-2020
  • (2019)Event Extraction and Representation: A Case Study for the Portuguese LanguageInformation10.3390/info1006020510:6(205)Online publication date: 8-Jun-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
KDD '14: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining
August 2014
2028 pages
ISBN:9781450329569
DOI:10.1145/2623330
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 August 2014

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. critical alert mining
  2. data center troubleshooting
  3. data mining
  4. graph mining
  5. root cause analysis

Qualifiers

  • Research-article

Funding Sources

Conference

KDD '14
Sponsor:

Acceptance Rates

KDD '14 Paper Acceptance Rate 151 of 1,036 submissions, 15%;
Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)1
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2020)Distributed Attack Modeling Approach Based on Process Mining and Graph SegmentationEntropy10.3390/e2209102622:9(1026)Online publication date: 14-Sep-2020
  • (2020)Kronos: Lightweight Knowledge-based Event Analysis in Cyber-Physical Data Streams2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00165(1766-1769)Online publication date: Apr-2020
  • (2019)Event Extraction and Representation: A Case Study for the Portuguese LanguageInformation10.3390/info1006020510:6(205)Online publication date: 8-Jun-2019
  • (2019)Proactive Failure Detection Learning Generation Patterns of Large-Scale Network LogsIEICE Transactions on Communications10.1587/transcom.2018EBP3103E102.B:2(306-316)Online publication date: 1-Feb-2019
  • (2018)TGNetProceedings of the 27th ACM International Conference on Information and Knowledge Management10.1145/3269206.3271698(97-106)Online publication date: 17-Oct-2018
  • (2017)ALACANetworks10.1002/nem.198027:4(n/a-n/a)Online publication date: 1-Jul-2017
  • (2016)The Information NetworkProceedings of the 2016 ACM on Conference on Human Information Interaction and Retrieval10.1145/2854946.2854974(223-232)Online publication date: 13-Mar-2016
  • (2015)Behavior query discovery in system-generated temporal graphsProceedings of the VLDB Endowment10.14778/2856318.28563209:4(240-251)Online publication date: 1-Dec-2015
  • (2015)Event Extraction from Unstructured Text DataProceedings, Part I, of the 26th International Conference on Database and Expert Systems Applications - Volume 926110.1007/978-3-319-22849-5_38(543-557)Online publication date: 1-Sep-2015

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media