Temporal sequence learning and data reduction for anomaly detection

ABSTRACT

The anomaly-detection problem can be formulated as one of learning to characterize the behaviors of an individual, system, or network in terms of temporal sequences of discrete data. We present an approach on the basis of instance-based learning (IBL) techniques. To cast the anomaly-detection task in an IBL framework, we employ an approach that transforms temporal sequences of discrete, unordered observations into a metric space via a similarity measure that encodes intra-attribute dependencies. Classification boundaries are selected from an a posteriori characterization of valid user behaviors, coupled with a domain heuristic. An empirical evaluation of the approach on user command data demonstrates that we can accurately differentiate the profiled user from alternative users when the available features encode sufficient information. Furthermore, we demonstrate that the system detects anomalous conditions quickly — an important quality for reducing potential damage by a malicious user. We present several techniques for reducing data storage requirements of the user profile, including instance-selection methods and clustering. As empirical evaluation shows that a new greedy clustering algorithm reduces the size of the user model by 70%, with only a small loss in accuracy.

REFERENCES

• 1: David W. Aha , Dennis Kibler , Marc K. Albert, Instance-Based Learning Algorithms, Machine Learning, v.6 n.1, p.37-66, Jan. 1991 [doi>10.1023/A:1022689900470]
• 2: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• 3: Javed A. Aslam , Ronald L. Rivest, Inferring graphs from walks, Proceedings of the third annual workshop on Computational learning theory, p.359-370, August 06-08, 1990, Rochester, New York, United States
• 4: BALASUBRAMANIYAN, J. S., GARCIA-FERNANDEZ, J. O., ISACOFF, D., SPAFFORD, E., AND ZAMBONI, D. 1998. An architecture for intrusion detection using autonomous agents. Tech. Rep. COAST TR 98/05. Purdue University, West Lafayette, IN.
• 5: Béla Bollobás , Gautam Das , Dimitrios Gunopulos , Heikki Mannila, Time-series similarity problems and well-separated geometric sets, Proceedings of the thirteenth annual symposium on Computational geometry, p.454-456, June 04-06, 1997, Nice, France [doi>10.1145/262839.263080]
• 6: CASELLA, G. AND BERGER, R. L. 1990. Statistical Inference. Brooks-Cole, CA.
• 7: CHARNIAK, E. 1997. Statistical techniques for natural language parsing. AI Mag. 18, 4, 33-43.
• 8: CHENOWETH, T. AND OBRADOVIC, Z. 1996. A multi-component nonlinear prediction system for the S&P 500 index. Neurocomputing 10, 3, 275-290.
• 9: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 10: Gautam Das , Dimitrios Gunopulos , Heikki Mannila, Finding Similar Time Series, Proceedings of the First European Symposium on Principles of Data Mining and Knowledge Discovery, p.88-100, June 24-27, 1997
• 11: Dorothy E. Denning, An intrusion-detection model, IEEE Transactions on Software Engineering, v.13 n.2, p.222-232, Feb. 1987 [doi>10.1109/TSE.1987.232894]
• 12: DOMINGOS, P. 1995. Rule induction and instance-based learning: A unified approach. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (AAAI-95, Montreal, Que., Canada). Morgan Kaufmann, San Mateo, CA, 1226-1232.
• 13: FARMER, D. AND VENEMA, W. 1995. SATAN overview (Security Administrator Tool for Analyzing Networks).
• 14: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504 ]
• 15: Keinosuke Fukunaga, Introduction to statistical pattern recognition (2nd ed.), Academic Press Professional, Inc., San Diego, CA, 1990
• 16: GORDON, S. 1996. Current computer virus threats, countermeasures, and strategic solutions, White paper. McAfee Associates.
• 17: HEBERLEIN, L. T., DIAS, G. V., LEVITT, K. N., MUKHERJEE, B., WOOD, J., AND WOLBER, D. 1990. A network security monitor. In Proceedings of the IEEE Symposium on Research in Security and Privacy (Oakland, CA). IEEE Computer Society Press, Los Alamitos, CA, 296-30304.
• 18: IBA, G.A. 1979. Learning disjunctive concepts from examples. Master's Thesis. MIT Press, Cambridge, MA.
• 19: Sandeep Kumar, Classification and detection of computer intrusions, Purdue University, West Lafayette, IN, 1996
• 20: KUMAR, S. AND SPAFFORD, E. 1994. An application of pattern matching in intrusion detection. Tech. Rep. CSD-TR-94-013. Purdue University, West Lafayette, IN.
• 21: LANE, T. 1999. Hidden Markov models for human/computer interface modeling. In Proceedings of the IJCAI-99 Workshop on Learning About Users. 35-44.
• 22: LANE, T. AND BRODLEY, C. E. 1997a. An application of machine learning to anomaly detection. In Proceedings of the 20th National Conference on National Information Systems Security. Vol.1 (Baltimore, MD). National Institute of Standards and Technology, Gaithersburg, MD, 366-380.
• 23: LANE, T. AND BRODLEY, C. E. 1997b. Sequence matching and learning in anomaly detection for computer security. In Proceedings of the AAAI-97 Workshop on AI Approaches to Fraud Detection and Risk Management (AAAI-97). 43-49.
• 24: LANE, T. AND BRODLEY, C. E. 1998. Approaches to online learning and concept drift for user identification in computer security. In Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining. 259-263.
• 25: LUNT, T. F. AND JAGANNATHAN, R. 1988. A prototype real-time intrusion-detection expert system. In Proceedings of the IEEE Symposium on Research in Security and Privacy. IEEE Computer Society Press, Los Alamitos, CA, 59-66.
• 26: MOON, T. K. 1996. The expectation-maximization algorithm. IEEE Trans. Signal Process. 44, 1, 47-59.
• 27: Steven W. Norton, Learning to recognize promoter sequences in E. coli by modeling uncertainty in the training data, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.657-663, October 1994, Seattle, Washington, United States
• 28: Alan V. Oppenheim , Ronald W. Schafer, Discrete-time signal processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 29: PORRAS, P. AND NEUMANN, P. 1997. EMERALD: Event monitoring enabling responses to anomalous live disturbances. In Proceedings of the 20th National Conference on National Information Systems Security. Vol.1 (Baltimore, MD). National Institute of Standards and Technology, Gaithersburg, MD, 353-365.
• 30: Foster Provost , Tom Fawcett, Robust classification systems for imprecise environments, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.706-713, July 1998, Madison, Wisconsin, United States
• 31: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 32: Lawrence Rabiner , Biing-Hwang Juang, Fundamentals of speech recognition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 33: RABINER, L. R. 1989. A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77, 2 (Feb.).
• 34: Brian D. Ripley , N. L. Hjort, Pattern Recognition and Neural Networks, Cambridge University Press, New York, NY, 1995
• 35: R. L. Rivest , R. E. Schapire, Inference of finite automata using homing sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.411-420, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73047]
• 36: Steven Salzberg, A Nearest Hyperrectangle Learning Method, Machine Learning, v.6 n.3, p.251-276, May 1991 [doi>10.1023/A:1022661727670]
• 37: SALZBERG, S. 1995. Locating protein coding regions in human DNA using a decision tree algorithm. J. Comput. Biology 2, 3, 473-485.
• 38: SCHAFFER, C. 1994. Cross-validation, stacking, and bi-level methods for stacking: Metamethods for classification learning. In Selecting Models from Data: Artificial Intelligence and Statistics, P. Cheeseman and W. Oldford, Eds. Springer-Verlag, Vienna, Austria.
• 39: SMAHA, S. E. 1988. Haystack: An intrusion detection system. In Proceedings of the Fourth Conference on Aerospace Computer Security Applications. 37-44.
• 40: Ramakrishnan Srikant , Rakesh Agrawal, Mining Sequential Patterns: Generalizations and Performance Improvements, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.3-17, March 25-29, 1996
• 41: 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 Conference on National Information Systems Security (Oct.). National Institute of Standards and Technology, Gaithersburg, MD.
• 42: D. Randall Wilson , Tony R. Martinez, Reduction Techniques for Instance-BasedLearning Algorithms, Machine Learning, v.38 n.3, p.257-286, March 2000 [doi>10.1023/A:1007626913721 ]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Experimentation, Security

Keywords:
anomaly detection, clustering, data reduction, empirical evaluation, instance based learning, machine learning, user profiling