In this paper we analyze some intrusion detection strategies proposed in the literature and we show that they represent the various facets of a well known formal languages problem: computing the distance between a string and a language . In particular, the main differences among the various approaches adopted for building intrusion detection systems can be reduced to the characteristics of the language and to the notion of distance adopted. As a further contribution we will also show that from the computational point of view all these strategies are equivalent and they are amenable to efficient parallelization.
@article{ITA_2006__40_2_303_0,
author = {Bruschi, Danilo and Pighizzini, Giovanni},
title = {String distances and intrusion detection : bridging the gap between formal languages and computer security},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {40},
year = {2006},
pages = {303-313},
doi = {10.1051/ita:2006010},
mrnumber = {2252641},
zbl = {1112.68017},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2006__40_2_303_0}
}
Bruschi, Danilo; Pighizzini, Giovanni. String distances and intrusion detection : bridging the gap between formal languages and computer security. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) pp. 303-313. doi : 10.1051/ita:2006010. http://gdmltest.u-ga.fr/item/ITA_2006__40_2_303_0/
[1] , and, The complexity of computing maximal word functions. Comput. Compl. 3 (1993) 368-391. | Zbl 0802.68061
[2] , Computer security threat monitoring and surveillance. Tech. Rep., James P. Anderson Company, Fort Washington (1980).
[3] , On one-way auxiliary pushdown automata, in Proc. 3rd GI Conference. Lect. Notes Comput. Sci. 48 (1977) 133-144. | Zbl 0359.68055
[4] and, Distances between languages and reflexivity of relations. Theoret. Comput. Sci. 286 (2002) 117-138. | Zbl 1016.68045
[5] , Characterization of pushdown machines in terms of time-bounded computers. J. ACM 18 (1971) 4-18. | Zbl 0222.02035
[6] , A taxonomy of problems with fast parallel algorithms. Inform. Control 64 (1985) 2-22. | Zbl 0575.68045
[7] , An intrusion detection model. IEEE Trans. Software Engineering 13 (1987).
[8] ,,, and, Anomaly detection using call stack information, in Proc. IEEE Symposium on Security and Privacy. IEEE Press (2003).
[9] ,, and, A sense of self for Unix processes, in Proc. IEEE Symposium on Security and Privacy. IEEE Press (1996).
[10] ,, and, Intrusion detection using sequences of system calls. J. Comput. Security 6 (1998) 151-180.
[11] and, A study in using neural networks for anomaly and misuse detection, in Proc. USENIX Security Symposium. USENIX Association (1999).
[12] and, Introduction to automata theory, languages, and computations. Addison-Wesley, Reading, MA (1979). | MR 645539 | Zbl 0426.68001
[13] and, A survey of parallel algorithms for shared-memory machines, in Handbook of Theoretical Computer Science, Vol. A. North Holland (1990). | MR 1127183 | Zbl 0900.68267
[14] , Characterizing the behavior of a program using Multiple length N-grams, in Proc. New Security Paradimg Workshop. ACM Press (2000) 101-110.
[15] , How Hard is Computing the Edit Distance? Inform. Comput. 165 (2001) 1-13. | Zbl 1003.68054
[16] ,, and, A fast automaton-based method for detecting anomalous program behaviors, in Proc. IEEE Symposium on Security and Privacy. IEEE Press (2001).
[17] and, Finding the maximum, merging and sorting in a parallel computation model. J. Algorithms 2 (1981) 88-102. | Zbl 0456.68062
[18] and, Intrusion detection via static analisys, in Proc. IEEE Symposium on Security and Privacy (2001).
[19] , Properties that characterize LOGCFL. J. Comput. Syst. Sci. 43 (1991) 380-404. | Zbl 0776.68046