Measuring intrusion detection capability: an information-theoretic approach

ABSTRACT

A fundamental problem in intrusion detection is what metric(s) can be used to objectively evaluate an intrusion detection system (IDS) in terms of its ability to correctly classify events as normal or intrusive. Traditional metrics (e.g., true positive rate and false positive rate) measure different aspects, but no single metric seems sufficient to measure the capability of intrusion detection systems. The lack of a single unified metric makes it difficult to fine-tune and evaluate an IDS. In this paper, we provide an in-depth analysis of existing metrics. Specifically, we analyze a typical cost-based scheme [6], and demonstrate that this approach is very confusing and ineffective when the cost factor is not carefully selected. In addition, we provide a novel information-theoretic analysis of IDS and propose a new metric that highly complements cost-based analysis. When examining the intrusion detection process from an information-theoretic point of view, intuitively, we should have less uncertainty about the input (event data) given the IDS output (alarm data). Thus, our new metric, CI D (Intrusion Detection Capability), is defined as the ratio of the mutual information between the IDS input and output to the entropy of the input. CI D has the desired property that: (1) It takes into account all the important aspects of detection capability naturally, i.e., true positive rate, false positive rate, positive predictive value, negative predictive value, and base rate; (2) it objectively provides an intrinsic measure of intrusion detection capability; and (3) it is sensitive to IDS operation parameters such as true positive rate and false positive rate, which can demonstrate the effect of the subtle changes of intrusion detection systems. We propose CI D as an appropriate performance measure to maximize when fine-tuning an IDS. The obtained operation point is the best that can be achieved by the IDS in terms of its intrinsic ability to classify input data. We use numerical examples as well as experiments of actual IDSs on various data sets to show that by using CI D, we can choose the best (optimal) operating point for an IDS and objectively compare different IDSs.

REFERENCES

• 1: Stefan Axelsson, The base-rate fallacy and its implications for the difficulty of intrusion detection, Proceedings of the 6th ACM conference on Computer and communications security, p.1-7, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319710]
• 2: S. Axelsson. A preliminary attempt to apply detection and estimation theory to intrusion detection. Technical Report 00-4, Dept. of Computer Engineering, Chalmers University of Technology, Sweden, March 2000.
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 4: M. Dacier. Design of an intrusion-tolerant intrusion detection system, Maftia Project, deliverable 10. Available at http://www.maftia.org/deliverables/D10.pdf. 2005.
• 5: 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]
• 6: John E. Gaffney Jr , Jacob W. Ulvila, Evaluation of Intrusion Detectors: A Decision Theory Approach, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.50, May 14-16, 2001
• 7: I. Graf, R. Lippmann, R. Cunningham, K. K. D. Fried, S. Webster, and M. Zissman. Results of DARPA 1998 off-line intrusion detection evaluation. Presented at DARPA PI Meeting, 15 December 1998.
• 8: G. Gu, P. Fogla, D. Dagon, W. Lee, and B. Skoric. An information-theoretic measure of intrusion detection capability. Technical Report GIT-CC-05-10, College of Computing, Georgia Tech, 2005.
• 9: J. Hancock and P. Wintz. Signal Detection Theory. McGraw-Hill, 1966.
• 10: P. Helman , G. Liepins, Statistical Foundations of Audit Trail Analysis for the Detection of Computer Misuse, IEEE Transactions on Software Engineering, v.19 n.9, p.886-901, September 1993 [doi>10.1109/32.241771 ]
• 11: Wenke Lee , Dong Xiang, Information-Theoretic Measures for Anomaly Detection, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.130, May 14-16, 2001
• 12: R. P. Lippmann, D. J. Fried, and I. G. etc. Evaluating intrusion detection systems: The 1998 darpa off-line intrusion detection evaluation. In Proceedings of the 2000 DARPA Information Survivability Conference and Exposition (DISCEX'00), 2000.
• 13: M. V. Mahoney and P. K. Chan. Phad: Packet header anomaly detection for indentifying hostile network traffic. Technical Report CS-2001-4, Florida Tech, 2001.
• 14: Roy A. Maxion , Kymie M. C. Tan, Benchmarking Anomaly-Based Detection Systems, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.623-630, June 25-28, 2000
• 15: Testing Intrusion detection systems: a critique of the 1998 and 1999 DARPA intrusion detection system evaluations as performed by Lincoln Laboratory, ACM Transactions on Information and System Security (TISSEC), v.3 n.4, p.262-294, Nov. 2000 [doi>10.1145/382912.382923]
• 16: MIT Lincoln Laboratory. 1999 darpa intrusion detection evaluation data set overview. http://www.ll.mit.edu/IST/ideval/, 2001.
• 17: Vern Paxson, Bro: a system for detecting network intruders in real-time, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.23-24, p.2435-2463, Dec. 1999 [doi>10.1016/S1389-1286(99)00112-7 ]
• 18: J. Pluim, J. Maintz, and M. Viergever. Mutual information based registration of medical images: A survey. IEEE Trans on Medical Imaging, 22(8):986--1004, Aug 2003.
• 19: T. H. Ptacek and T. N. Newsham. Insertion, evasion, and denial of service: Eluding network intrusion detection. Technical report, Secure Networks Inc., January 1998. http://www.aciri.org/vern/Ptacek-Newsham-Evasion-98.ps.
• 20: Nicholas J. Puketza , Kui Zhang , Mandy Chung , Biswanath Mukherjee , Ronald A. Olsson, A Methodology for Testing Intrusion Detection Systems, IEEE Transactions on Software Engineering, v.22 n.10, p.719-729, October 1996 [doi>10.1109/32.544350 ]
• 21: R. F. Puppy. Libwhisker official release v2.1, 2004. Available at http://www.wiretrip.net/rfp/lw.asp.
• 22: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 23: Alexander Strehl , Joydeep Ghosh, Relationship-based clustering and cluster ensembles for high-dimensional data mining, 2002
• 24: J. A. Swets. Measuring the accuracy of diagnostic systems. Science, 240(4857): 1285--1293, 1988.
• 25: K. Wang and S. J. Stolfo. Anomalous payload-based network intrusion detection. In Proceedings of RAID'2004, September 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory

General Terms:
Measurement, Security

Keywords:
information-theoretic, intrusion detection, performance measurement