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
Access Full Article
top
Abstract
topHow to cite
topBruschi, 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- E. Allender, D. Bruschi and G. Pighizzini, The complexity of computing maximal word functions. Comput. Compl.3 (1993) 368–391.
- J.P. Anderson, Computer security threat monitoring and surveillance. Tech. Rep., James P. Anderson Company, Fort Washington (1980).
- F. Brandenburg, On one-way auxiliary pushdown automata, in Proc. 3rd GI Conference. Lect. Notes Comput. Sci.48 (1977) 133–144.
- C. Choffrut and G. Pighizzini, Distances between languages and reflexivity of relations. Theoret. Comput. Sci.286 (2002) 117–138.
- S. Cook, Characterization of pushdown machines in terms of time–bounded computers. J. ACM18 (1971) 4–18.
- S. Cook, A taxonomy of problems with fast parallel algorithms. Inform. Control64 (1985) 2–22.
- D.E. Denning, An intrusion detection model. IEEE Trans. Software Engineering13 (1987).
- 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).
- 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).
- S. Forrest, S. Hofmeyr, A. Somayaji and T. Longstaff, Intrusion detection using sequences of system calls. J. Comput. Security6 (1998) 151–180.
- 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).
- J. Hopcroft and J. Ullman, Introduction to automata theory, languages, and computations. Addison-Wesley, Reading, MA (1979).
- 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).
- C. Marceau, Characterizing the behavior of a program using Multiple length N-grams, in Proc. New Security Paradimg Workshop. ACM Press (2000) 101–110.
- G. Pighizzini, How Hard is Computing the Edit Distance? Inform. Comput.165 (2001) 1–13.
- 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).
- Y. Shiloach and U. Vishkin, Finding the maximum, merging and sorting in a parallel computation model. J. Algorithms2 (1981) 88–102.
- D. Wagner and D. Dean, Intrusion detection via static analisys, in Proc. IEEE Symposium on Security and Privacy (2001).
- H. Venkateswaran, Properties that characterize LOGCFL. J. Comput. Syst. Sci.43 (1991) 380–404.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.