Simple, state-based approaches to program-based anomaly detection

ABSTRACT

This article describes variants of two state-based intrusion detection algorithms from Michael and Ghosh [2000] and Ghosh et al. [2000], and gives experimental results on their performance. The algorithms detect anomalies in execution audit data. One is a simply constructed finite-state machine, and the other two monitor statistical deviations from normal program behavior. The performance of these algorithms is evaluated as a function of the amount of available training data, and they are compared to the well-known intrusion detection technique of looking for novel n-grams in computer audit data.

REFERENCES

• 1: Anderson, J. 1980. Computer security threat monitoring and surveillance. Tech. Rep. James P. Anderson Co., Fort Washington, Pa.
• 2: Michèle Basseville , Igor V. Nikiforov, Detection of abrupt changes: theory and application, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 3: Cannady, J. 1998. Artificial neural networks for misuse detection. In Proceedings of the 1998 National Information Systems Security Conference (NISSC'98). (Arlington, Va.), 443--456.
• 4: Patrik D'haeseleer , Stephanie Forrest , Paul Helman, An Immunological Approach to Change Detection: Algorithms, Analysis and Implications, Proceedings of the 1996 IEEE Symposium on Security and Privacy, p.110, May 06-08, 1996
• 5: D. Endler, Intrusion Detection Applying Machine Learning to Solaris Audit Data, Proceedings of the 14th Annual Computer Security Applications Conference, p.268, December 07-11, 1998
• 6: Stephanie Forrest , Steven A. Hofmeyr , Anil Somayaji , Thomas A. Longstaff, A Sense of Self for Unix Processes, Proceedings of the 1996 IEEE Symposium on Security and Privacy, p.120, May 06-08, 1996
• 7: Yoav Freund , Michael Kearns , Dana Ron , Ronitt Rubinfeld , Robert E. Schapire , Linda Sellie, Efficient learning of typical finite automata from random walks, Information and Computation, v.138 n.1, p.23-48, Oct. 10, 1997 [doi>10.1006/inco.1997.2648]
• 8: Anup K. Ghosh , Christoph Michael , Michael Schatz, A Real-Time Intrusion Detection System Based on Learning Program Behavior, Proceedings of the Third International Workshop on Recent Advances in Intrusion Detection, p.93-109, October 02-04, 2000
• 9: Anup K. Ghosh , Aaron Schwartzbard , Michael Schatz, Learning Program Behavior Profiles for Intrusion Detection, Proceedings of the Workshop on Intrusion Detection and Network Monitoring, p.51-62, April 09-12, 1999
• 10: A. K. Gosh , J. Wanken , F. Charron, Detecting Anomalous and Unknown Intrusions Against Programs, Proceedings of the 14th Annual Computer Security Applications Conference, p.259, December 07-11, 1998
• 11: Grimmet, G. R. and Stirzaker, R. D. 1992. Probability and Random Processes. Oxford University Press.
• 12: M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
• 13: Gene H. Kim , Eugene H. Spafford, The design and implementation of tripwire: a file system integrity checker, Proceedings of the 2nd ACM Conference on Computer and communications security, p.18-29, November 1994, Fairfax, Virginia, United States [doi>10.1145/191177.191183]
• 14: Andrew P. Kosoresow , Steven A. Hofmeyr, Intrusion Detection via System Call Traces, IEEE Software, v.14 n.5, p.35-42, September 1997 [doi>10.1109/52.605929]
• 15: Lai, T. L. 1998. Information bounds and quick detection of parameter changes in stochastic systems. IEEE Trans. Inf. Theory 44, 7, 2917--2929.
• 16: Lane, T. and Brodley, C. 1997. An application of machine learning to anomaly detection. In Proceedings of the 20th National Information Systems Security Conference. 366--377.
• 17: Terran Lane , Carla E. Brodley, Temporal sequence learning and data reduction for anomaly detection, ACM Transactions on Information and System Security (TISSEC), v.2 n.3, p.295-331, Aug. 1999 [doi>10.1145/322510.322526]
• 18: Kevin J. Lang , Barak A. Pearlmutter , Rodney A. Price, Results of the Abbadingo One DFA Learning Competition and a New Evidence-Driven State Merging Algorithm, Proceedings of the 4th International Colloquium on Grammatical Inference, p.1-12, July 12-14, 1998
• 19: Lee, W., Stolfo, S., and Chan, P. 1997. Learning patterns from Unix process execution traces for intrusion detection. In Proceedings of AAAI97 Workshop on AI Methods in Fraud and Risk Management.
• 20: Lunt, T. 1990. Ides: an intelligent system for detecting intruders. In Proceedings of the Symposium: Computer Security, Threat and Countermeasures (Rome, Italy).
• 21: Teresa F. Lunt, A survey of intrusion detection techniques, Computers and Security, v.12 n.4, p.405-418, June 1993 [doi>10.1016/0167-4048(93)90029-5]
• 22: Lunt, T. and Jagannathan, R. 1988. A prototype real-time intrusion-detection system. In Proceedings of the 1988 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif.
• 23: Lunt, T., Tamaru, A., Gilham, F., Jagannthan, R., Jalali, C., Javitz, H., Valdos, A., Neumann, P., and Garvey, T. 1992. A real-time intrusion-detection expert system (ides). Tech. Rep. Computer Science Laboratory, SRI Internationnal.
• 24: C. C. Michael , A. Ghosh, Two state-based approaches to program-based anomaly detection, Proceedings of the 16th Annual Computer Security Applications Conference, p.21, December 11-15, 2000
• 25: Porras, P. and Neumann, P. 1997. Emerald: Event monitoring enabling responses to anomalous live disturbances. In Proceedings of the 20th National Information Systems Security Conference. 353--365.
• 26: Lawrence Rabiner , Biing-Hwang Juang, Fundamentals of speech recognition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 27: R. Sekar , M. Bendre , D. Dhurjati , P. Bollineni, A Fast Automaton-Based Method for Detecting Anomalous Program Behaviors, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.144, May 14-16, 2001
• 28: Staniford-Chen, S., Cheung, S., Crawford, R., Dilger, M., Frank, J., Hoagland, J., Levitt, K., Wee, C., Yip, R., and Zerkle, D. 1996. GrIDS---A graph based intrusion detection system for large networks. In Proceedings of the 19th National Information Systems Security Conference.
• 29: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 30: Warrender, C., Forrest, S., and Pearlmutter, B. 1999. Detecting intrusions using system calls: Alternative data models. In Proceedings of the 1999 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, Calif., 133--145.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

General Terms:
Experimentation, Performance, Security

Keywords:
Anomaly detection, finite automata, information system security, intrusion detection, machine learning