Analysis of risks and costs in intruder detection with Markov Decision Processes

  • Dr. Jorma Jormakka Aalto University
  • Sourangshu Ghosh Indian Institute of Technology Kharagpur
Keywords: combinatorics, risk analysis, decision analysis


Let us assume that defence mechanisms are so strong that the average outcome of a hacking attack is unsuccessful. How to calculate the costs arising from false positives and false negatives in intruder detection? Is it better for the hacker to make fewer but more effective attacks rather than several but less effective attacks? How to calculate the difference between these alternative strategies?


Download data is not yet available.


[1] R.Bellman, “A Markovian Decision Process”, Journal of Mathematics and Mechanics. 6 (5): 679-684 JSTOR 24900506, 1957 [2] R.A.Howards, “Dynamic Programming and Markov Process”, TheM.I.TPress,1960 [3] P. Ver´ıssimo, N. Neves and M. Correia. “Intrusion-tolerant architectures: concepts and design,” in Architecting Dependable Systems”, LNCS 2677:3-36, Springer, 2003. [4] Anderson, J.P.: Computer security threat monitoring and surveillance. Technical report, James P. Anderson Co., Fort Washington, PA (1980)
[5] Denning, D.E.: An intrusion-detection model. IEEE Transactions on Software Engineering 13 (1987) 222–232. [6] Davison, B.D., Hirsh, H.: Predicting sequences of user actions. In: Proceedings of the AAAI-98/ICML-98 Joint Workshop on AI Approaches to Time-series Analysis. (1998) 5–12 [7] DuMouchel, W.: Computer intrusion detection based on bayes factors for comparing command transition probabilities. Technical Report 91, National Institute of Statistical Sciences, Research Triangle Park, NC (1999)
[8] Ju, W.H., Vardi, Y.: A hybrid high-order markov chain model for computer intrusion detection. Technical Report 92, National Institute of Statistical Sciences, Research Triangle Park, NC (1999) [9] Lane, T., Brodley, C.E.”: An empirical study of two approaches to sequence learning for anomaly detection”. Machine Learning 51 (2003)73–107 [10] Forrest, S., Perelson, A.S., Allen, L., Cherukuri, R.:” Self-nonself discrimination in a computer.” In: Proceedings of the 1994 IEEE Symposium on Research in Security and Privacy, Los Alamitos, CA, IEEE Computer Society Press (1994) [11] Balthrop, J., Esponda, F., Forrest, S., Glickman, M.: Coverage and generalization in an artificial immune system. In Langdon, W.B., Cantu-Paz, E., Mathias, K., Roy, R., Davis, D., Poli, R., Balakrishnan, K., Hanovar, V., Rudolph, G., Wegener, J., Bull, L., Potter, M.A., Schultz, A.C., Miller, J.F., Burke, E., Jonaska, N., eds.:Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), Morgan Kaufmann (2002) 3–10 [12] Dasgupta, D., Gonz´alez, F.: An immunity-based technique to characterize intrusions in computer networks. IEEE Transactions on Evolutionary Computation 6 (2002) 1081–1088 [13] Kim, J., Bentley, P.J.: Towards an artificial immune system for network intrusion detection: An investigation of clonal selection with a negative selection operator. In: Proceedings of the 2002 Congress on Evolutionary Computation. (2001) [14] E. Jonsson and T. Olovsson. “A quantitative model of the security intrusion process based on attacker behavior,” IEEE Trans. on Software Engineering, 23(4):1-11, Apr 1997. [15] D. Nicol, W. Sanders and K. Trivedi. “Model-based evaluation: from dependability to security,” IEEE Trans. on Dependable and Secure Computing, 1(1):48-65, Jan 2004. [16] B. Madan, et al. “A method for modeling and quantifying the security attributes of intrusion tolerant systems,” Performance Evaluation,56:167-186,(2004). [17] A. Arnes, et al. “Real-time risk assessment with network sensors and intrusion detection systems,” in Computational Intelligence and Security, 388-397, Springer, 2005. [18] Y. Huang, D. Arsenault and A. Sood. “Incorruptible selfcleansing intrusion tolerance and its application to DNS security,” J. of Networks, 1(5):21-30, Sep 2006. [19] K. Joshi, et al. “Automated recovery using bounded partially observable Markov decision processes,” in Proc. of Dependable Systems and Networks (DSN), 445:456, Jun 2006. [20] O. Kreidl and T. Frazier. “Feedback control applied to survivability: a host-based autonomic defense system,” IEEE Trans. on Reliability, 53(1):148-166, Mar 2004.
[21] L. Dubins, L. Savage, How to gamble if you must, inequalities for stochastic processes, McGraw-Hill, 1965.
[22] F. P. Kelly, Reversibility and Stochastic Networks, New York: Wiley, 1979.
[23] E. Altman, “Applications of Markov Decision Processes in telecommunications: a survey,” Research Report RR-3984, MISTRAL-project, INRIA, 2000, p.51.
[24] T. Darling, and M.A. Shayman, “Network Intruder Location Using Markov Decision Processes,” in Third International Workshop on Recent Advances in Intrusion Detection (RAID 2000), 2000.
How to Cite
Jormakka, J., & Ghosh, S. (2021). Analysis of risks and costs in intruder detection with Markov Decision Processes. COMPUSOFT: An International Journal of Advanced Computer Technology, 10(8), 3993-3999. Retrieved from