Abstract
We propose an indexing technique for alert correlation that supports DFA-like patterns with user-defined correlation functions. Our AC-Index supports (i) the retrieval of the top-k (possibly non-contiguous) sub-sequences, ranked on the basis of an arbitrary user-provided severity function, (ii) the concurrent retrieval of sub-sequences that match any pattern in a given set, (iii) the retrieval of partial occurrences of the patterns, and (iv) the online processing of streaming logs. The experimental results confirm that, although the supported model is very expressive, the AC-Index is able to guarantee a very high efficiency of the retrieval process.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Some past works assume aciclicity of the patterns because, in many practical cases, (i) the attacker’s control over the network increases monotonically, i.e., the attacker need not relinquish resources already gained during the attack, and (ii) the “criticality” associated with a sequence of alerts does not change when the sequence contains a portion that is repeated multiple times as it matches a cycle in the pattern. In such cases, the overall sequence is equivalent to the one obtained after removing the portion matching the cycle. We do not make this assumption as it would reduce the expressiveness of the model and it is not required by the AC-Index.
- 2.
Note that a security expert may want to discard \(O_2\) and \(O_4\) because they are prefixes of \(O_1\) and \(O_3\) respectively.
- 3.
For simplicity of presentation, the run with all parameters set to default values is reported as three separate runs (6, 9, and 14) in Fig. 7.
References
Agrawal, J., Diao, Y., Gyllstrom, D., Immerman, N.: Efficient pattern matching over event streams. In: SIGMOD (2008)
Albanese, M., Jajodia, S., Pugliese, A., Subrahmanian, V.S.: Scalable analysis of attack scenarios. In: Atluri, V., Diaz, C. (eds.) ESORICS 2011. LNCS, vol. 6879, pp. 416–433. Springer, Heidelberg (2011)
Albanese, M., Pugliese, A., Subrahmanian, V.S.: Fast activity detection: Indexing for temporal stochastic automaton-based activity models. IEEE Trans. Knowl. Data Eng. 25(2), 360–373 (2013)
Babenko, A., Mariani, L., Pastore, F.: Ava: automated interpretation of dynamically detected anomalies. In: ISSTA (2009)
Bass, T.: Intrusion detection systems and multisensor data fusion. Commun. ACM 43(4), 99–105 (2000)
Branch, J., Bivens, A., Lee, T.K.: Denial of service intrusion detection using time dependent deterministic finite automata. In: Graduate Research Conference (2002)
Creech, G., Hu, J.: A semantic approach to host-based intrusion detection systems using contiguousand discontiguous system call patterns. IEEE Trans. Comput. 63(4), 807–819 (2014)
Cuppens, F., Miege, A.: Alert correlation in a cooperative intrusion detection framework. In: S&P (2002)
Demers, A., Gehrke, J., Hong, M., Riedewald, M., White, W.: Towards expressive publish/subscribe systems. In: Ioannidis, Y., Scholl, M.H., Schmidt, J.W., Matthes, F., Hatzopoulos, M., Böhm, K., Kemper, A., Grust, T., Böhm, C. (eds.) EDBT 2006. LNCS, vol. 3896, pp. 627–644. Springer, Heidelberg (2006)
Demers, A.J., Gehrke, J., Panda, B., Riedewald, M., Sharma, V., White, W.M.: Cayuga: a general purpose event monitoring system. In: CIDR (2007)
Garcia-Teodoro, P., Díaz-Verdejo, J.E., Maciá-Fernández, G., Vázquez, E.: Anomaly-based network intrusion detection: techniques, systems and challenges. Comput. Secur. 28(1–2), 18–28 (2009)
Gyllstrom, D., Agrawal, J., Diao, Y., Immerman, N.: On supporting kleene closure over event streams. In: ICDE (2008)
Kosoresow, A.P., Hofmeyr, S.A.: Intrusion detection via system call traces. IEEE Softw. 14(5), 35–42 (1997)
Kruegel, C., Valeur, F., Vigna, G.: Intrusion Detection and Correlation - Challenges and Solutions. Advances in Information Security. Springer, New York (2005)
Kumar, S., Spafford, E.H.: A pattern matching model for misuse intrusion detection. In: National Computer Security Conference (1994)
Lippmann, R., Haines, J.W., Fried, D.J., Korba, J., Das, K.: The 1999 DARPA off-line intrusion detection evaluation. Comp. Netw. 34(4), 579–595 (2000)
Liu, J., Li, R., Liu, Y., Zhang, Z.: Multi-sensor data fusion based on correlation function and fuzzy integration function. Syst. Eng. Electron. 28(7), 1006–1009 (2006)
Mao, C.H., Pao, H.K., Faloutsos, C., Lee, H.M.: Sbad: Sequence based attack detection via sequence comparison. In: PSDML (2010)
Michael, C., Ghosh, A.: Using finite automata to mine execution data for intrusion detection: a preliminary report. In: Debar, H., Mé, L., Wu, S.F. (eds.) RAID 2000. LNCS, vol. 1907, p. 66. Springer, Heidelberg (2000)
Molinaro, C., Moscato, V., Picariello, A., Pugliese, A., Rullo, A., Subrahmanian, V.S.: Padua: parallel architecture to detect unexplained activities. ACM Trans. Internet Techn. 14(1), 3 (2014)
Ning, P., Cui, Y., Reeves, D.S., Xu, D.: Techniques and tools for analyzing intrusion alerts. ACM Trans. Inf. Syst. Secur. 7(2), 274–318 (2004)
Ou, X., Govindavajhala, S., Appel, A.W.: Mulval: a logic-based network security analyzer. In: USENIX (2005)
Patcha, A., Park, J.M.: An overview of anomaly detection techniques: existing solutions and latest technological trends. Comp. Netw. 51(12), 3448–3470 (2007)
Paxson, V.: Bro: a system for detecting network intruders in real-time. Comp. Netw. 31(23–24), 2435–2463 (1999)
Piciarelli, C., Micheloni, C., Foresti, G.L.: Trajectory-based anomalous event detection. IEEE Trans. Circuits Syst. Video Techn. 18(11), 1544–1554 (2008)
Ren, H., Stakhanova, N., Ghorbani, A.A.: An online adaptive approach to alert correlation. In: Kreibich, C., Jahnke, M. (eds.) DIMVA 2010. LNCS, vol. 6201, pp. 153–172. Springer, Heidelberg (2010)
Roesch, M.: Snort: Lightweight intrusion detection for networks. In: LISA (1999)
Roschke, S., Cheng, F., Meinel, C.: A new alert correlation algorithm based on attack graph. In: Herrero, Á., Corchado, E. (eds.) CISIS 2011. LNCS, vol. 6694, pp. 58–67. Springer, Heidelberg (2011)
Sadoddin, R., Ghorbani, A.: Alert correlation survey: framework and techniques. In: PST (2006)
Sekar, R., Bendre, M., Dhurjati, D., Bollineni, P.: A fast automaton-based method for detecting anomalous program behaviors. In: S&P (2001)
Sheikhan, M., Jadidi, Z.: Misuse detection using hybrid of association rule mining and connectionist modeling. World Appl. Sci. J. 7, 31–37 (2009)
Shon, T., Moon, J.: A hybrid machine learning approach to network anomaly detection. Inf. Sci. 177(18), 3799–3821 (2007)
Valdes, A., Skinner, K.: Probabilistic alert correlation. In: Lee, W., Mé, L., Wespi, A. (eds.) RAID 2001. LNCS, vol. 2212, p. 54. Springer, Heidelberg (2001)
Valeur, F., Vigna, G., Krügel, C., Kemmerer, R.A.: A comprehensive approach to intrusion detection alert correlation. IEEE Trans. Dependable Sec. Comput. 1(3), 146–169 (2004)
Vigna, G., Kemmerer, R.A.: Netstat: A network-based intrusion detection system. J. Comput. Secur. 7(1), 37–71 (1999)
Wang, L., Liu, A., Jajodia, S.: Using attack graphs for correlating, hypothesizing, and predicting intrusion alerts. Comput. Commun. 29(15), 2917–2933 (2006)
Acknowledgements
This work has been partially supported by the “Technological District on Cyber Security” PON Project (grant n. PON03PE_00032_2), funded by the Italian Ministry of University and Research.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Pugliese, A., Rullo, A., Piccolo, A. (2015). The AC-Index: Fast Online Detection of Correlated Alerts. In: Foresti, S. (eds) Security and Trust Management. STM 2015. Lecture Notes in Computer Science(), vol 9331. Springer, Cham. https://doi.org/10.1007/978-3-319-24858-5_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-24858-5_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-24857-8
Online ISBN: 978-3-319-24858-5
eBook Packages: Computer ScienceComputer Science (R0)