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.

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 x and a language L. In particular, the main differences among the various approaches adopted for building intrusion detection systems can be reduced to the characteristics of the language L 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.

DOI: 10.1051/ita:2006010
Classification: 68M99, 68Q17, 68Q45
@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] E. Allender, D. Bruschi and G. Pighizzini, The complexity of computing maximal word functions. Comput. Compl. 3 (1993) 368-391. | Zbl

[2] J.P. Anderson, Computer security threat monitoring and surveillance. Tech. Rep., James P. Anderson Company, Fort Washington (1980).

[3] F. Brandenburg, On one-way auxiliary pushdown automata, in Proc. 3rd GI Conference. Lect. Notes Comput. Sci. 48 (1977) 133-144. | Zbl

[4] C. Choffrut and G. Pighizzini, Distances between languages and reflexivity of relations. Theoret. Comput. Sci. 286 (2002) 117-138. | Zbl

[5] S. Cook, Characterization of pushdown machines in terms of time-bounded computers. J. ACM 18 (1971) 4-18. | Zbl

[6] S. Cook, A taxonomy of problems with fast parallel algorithms. Inform. Control 64 (1985) 2-22. | Zbl

[7] D.E. Denning, An intrusion detection model. IEEE Trans. Software Engineering 13 (1987).

[8] H. Feng, O. Kolesnikov, P. Fogla, W. Lee and W. Gong, Anomaly detection using call stack information, in Proc. IEEE Symposium on Security and Privacy. IEEE Press (2003).

[9] S. Forrest, S. Hofmeyr, A. Somayaji and T. Longstaff, A sense of self for Unix processes, in Proc. IEEE Symposium on Security and Privacy. IEEE Press (1996).

[10] S. Forrest, S. Hofmeyr, A. Somayaji and T. Longstaff, Intrusion detection using sequences of system calls. J. Comput. Security 6 (1998) 151-180.

[11] A.K. Ghosh and A. Schwartzbard, A study in using neural networks for anomaly and misuse detection, in Proc. USENIX Security Symposium. USENIX Association (1999).

[12] J. Hopcroft and J. Ullman, Introduction to automata theory, languages, and computations. Addison-Wesley, Reading, MA (1979). | MR | Zbl

[13] R. Karp and V. Ramachandran, A survey of parallel algorithms for shared-memory machines, in Handbook of Theoretical Computer Science, Vol. A. North Holland (1990). | MR | Zbl

[14] C. Marceau, Characterizing the behavior of a program using Multiple length N-grams, in Proc. New Security Paradimg Workshop. ACM Press (2000) 101-110.

[15] G. Pighizzini, How Hard is Computing the Edit Distance? Inform. Comput. 165 (2001) 1-13. | Zbl

[16] R. Sekar, M. Bendre, D. Dhurjati and P. Bollineni, A fast automaton-based method for detecting anomalous program behaviors, in Proc. IEEE Symposium on Security and Privacy. IEEE Press (2001).

[17] Y. Shiloach and U. Vishkin, Finding the maximum, merging and sorting in a parallel computation model. J. Algorithms 2 (1981) 88-102. | Zbl

[18] D. Wagner and D. Dean, Intrusion detection via static analisys, in Proc. IEEE Symposium on Security and Privacy (2001).

[19] H. Venkateswaran, Properties that characterize LOGCFL. J. Comput. Syst. Sci. 43 (1991) 380-404. | Zbl

Cited by Sources: