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}, pages = {303--313}, publisher = {EDP-Sciences}, volume = {40}, number = {2}, year = {2006}, doi = {10.1051/ita:2006010}, mrnumber = {2252641}, zbl = {1112.68017}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2006010/} }
TY - JOUR AU - Bruschi, Danilo AU - Pighizzini, Giovanni TI - String distances and intrusion detection : bridging the gap between formal languages and computer security JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 303 EP - 313 VL - 40 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2006010/ DO - 10.1051/ita:2006010 LA - en ID - ITA_2006__40_2_303_0 ER -
%0 Journal Article %A Bruschi, Danilo %A Pighizzini, Giovanni %T String distances and intrusion detection : bridging the gap between formal languages and computer security %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 303-313 %V 40 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2006010/ %R 10.1051/ita:2006010 %G en %F 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, Volume 40 (2006) no. 2, pp. 303-313. doi : 10.1051/ita:2006010. http://www.numdam.org/articles/10.1051/ita:2006010/
[1] The complexity of computing maximal word functions. Comput. Compl. 3 (1993) 368-391. | Zbl
, and ,[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
,[4] Distances between languages and reflexivity of relations. Theoret. Comput. Sci. 286 (2002) 117-138. | Zbl
and ,[5] Characterization of pushdown machines in terms of time-bounded computers. J. ACM 18 (1971) 4-18. | Zbl
,[6] A taxonomy of problems with fast parallel algorithms. Inform. Control 64 (1985) 2-22. | Zbl
,[7] An intrusion detection model. IEEE Trans. Software Engineering 13 (1987).
,[8] Anomaly detection using call stack information, in Proc. IEEE Symposium on Security and Privacy. IEEE Press (2003).
, , , and ,[9] A sense of self for Unix processes, in Proc. IEEE Symposium on Security and Privacy. IEEE Press (1996).
, , and ,[10] Intrusion detection using sequences of system calls. J. Comput. Security 6 (1998) 151-180.
, , and ,[11] A study in using neural networks for anomaly and misuse detection, in Proc. USENIX Security Symposium. USENIX Association (1999).
and ,[12] Introduction to automata theory, languages, and computations. Addison-Wesley, Reading, MA (1979). | MR | Zbl
and ,[13] A survey of parallel algorithms for shared-memory machines, in Handbook of Theoretical Computer Science, Vol. A. North Holland (1990). | MR | Zbl
and ,[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
,[16] A fast automaton-based method for detecting anomalous program behaviors, in Proc. IEEE Symposium on Security and Privacy. IEEE Press (2001).
, , and ,[17] Finding the maximum, merging and sorting in a parallel computation model. J. Algorithms 2 (1981) 88-102. | Zbl
and ,[18] Intrusion detection via static analisys, in Proc. IEEE Symposium on Security and Privacy (2001).
and ,[19] Properties that characterize LOGCFL. J. Comput. Syst. Sci. 43 (1991) 380-404. | Zbl
,Cited by Sources: