String distances and intrusion detection : bridging the gap between formal languages and computer security

Bruschi, Danilo; Pighizzini, Giovanni

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 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.

Classification : 68M99, 68Q17, 68Q45

[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). | Zbl | MR

[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). | Zbl | MR

[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