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

Danilo Bruschi; Giovanni Pighizzini

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 2, page 303-313
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Bruschi, Danilo, and Pighizzini, Giovanni. "String distances and intrusion detection: Bridging the gap between formal languages and computer security." RAIRO - Theoretical Informatics and Applications 40.2 (2006): 303-313. <http://eudml.org/doc/249691>.

@article{Bruschi2006,
abstract = { 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. },
author = {Bruschi, Danilo, Pighizzini, Giovanni},
journal = {RAIRO - Theoretical Informatics and Applications},
language = {eng},
month = {7},
number = {2},
pages = {303-313},
publisher = {EDP Sciences},
title = {String distances and intrusion detection: Bridging the gap between formal languages and computer security},
url = {http://eudml.org/doc/249691},
volume = {40},
year = {2006},
}

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
DA - 2006/7//
PB - EDP Sciences
VL - 40
IS - 2
SP - 303
EP - 313
AB - 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.
LA - eng
UR - http://eudml.org/doc/249691
ER -

References

top
  1. E. Allender, D. Bruschi and G. Pighizzini, The complexity of computing maximal word functions. Comput. Compl.3 (1993) 368–391.  
  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.  
  4. C. Choffrut and G. Pighizzini, Distances between languages and reflexivity of relations. Theoret. Comput. Sci.286 (2002) 117–138.  
  5. S. Cook, Characterization of pushdown machines in terms of time–bounded computers. J. ACM18 (1971) 4–18.  
  6. S. Cook, A taxonomy of problems with fast parallel algorithms. Inform. Control64 (1985) 2–22.  
  7. D.E. Denning, An intrusion detection model. IEEE Trans. Software Engineering13 (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. Security6 (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).  
  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).  
  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.  
  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. Algorithms2 (1981) 88–102.  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.