Journal of Communications, Vol 7, No 6 (2012), 436-450, Jun 2012
doi:10.4304/jcm.7.6.436-450

Surviving in Cyberspace: A Game Theoretic Approach

Charles A. Kamhoua, Kevin A. Kwiat, Joon S. Park

Abstract


As information systems become ever more complex and the interdependence of these systems increases, a mission-critical system should have the fight-through ability to sustain damage yet survive with mission assurance in cyberspace. To satisfy this requirement, in this paper we propose a game theoretic approach to binary voting with a weighted majority to aggregate observations among replicated nodes. Nodes are of two types: they either vote truthfully or are malicious and thus lie. Voting is strategically performed based on a node’s belief about the percentage of compromised nodes in the system. Voting is cast as a stage game model that is a Bayesian Zero-sum game. In the resulting Bayesian Nash equilibrium, if more than a critical proportion of nodes are compromised, their collective decision is only 50% reliable; therefore, no information is obtained from voting. We overcome this by formalizing a repeated game model that guarantees a highly reliable decision process even though nearly all nodes are compromised. A survival analysis is performed to derive the total time of mission survival for both a one-shot game and the repeated game. Mathematical proofs and simulations support our model.


Keywords


Bayesian game; binary voting; cyberspace; fault-tolerant networks; fight-through; network security; survivability

References


 

[1] K. Kwiat, A. Taylor, W. Zwicker, D. Hill, S. Wetzonis, S. Ren “Analysis of binary voting algorithms for use in fault-tolerant and secure computing” International Conference on Computer Engineering and Systems (ICCES), Cairo, Egypt. December 2010.

[2] W. Du, J. Deng, Y. Han, P. Varshney “A withness-based approach for data fusion assurance in wireless sensor networks” IEEE GLOBECOM 2003.

[3] L. Wang, Z. Li, S. Ren, K. Kwiat “Optimal Voting Strategy Against Rational Attackers” The Sixth International Conference on Risks and Security of Internet and Systems CRiSIS 2011, Timisoara, Romania, September 2011.

[4] G. An and J. Park. “Cooperative component testing architecture in collaborating network environment” In Proceedings of the 4th International Conference on Autonomic and Trusted Computing (ATC), Lecture Notes in Computer Science (LNCS), pages 179-190,Hong Kong, China, July 11-13, 2007. Springer.

[5] J. Park, P. Chandramohan, G. Devarajan, J. Giordano. “Trusted component sharing by runtime test and immunization for survivable distributed systems”. In Ryoichi Sasaki, Sihan Qing, Eiji Okamoto, and Hiroshi Yoshiura, editors, Security and Privacy in the Age of Ubiquitous Computing, pages127–142. Springer, 2005. Proceedings of the 20th IFIP TC11 International Conference on Information Security (IFIP/SEC), Chiba, Japan, May 30-June 1, 2005.

[6] S. Bhattacharjee, S. Debroy, M. Chatterjee, K. Kwiat “Trust based Fusion over Noisy Channels throught Anomaly Detection in Cognitive Radio Networks” 4th International Conference on Security of Information and Networks (ACM SIN 2011), Sydney, Australia, November 2011.

[7] Z. S. Ma; A.W. Krings, "Dynamic Hybrid Fault Modeling and Extended Evolutionary Game Theory for Reliability, Survivability and Fault Tolerance Analyses" IEEE Transactions on Reliability, vol.60, no.1, pp.180-196, March 2011. http://dx.doi.org/10.1109/TR.2011.2104997
http://dx.doi.org/10.1109/TR.2011.2104997

[8] D. Malki, M. Reiter “Byzantine quorum systems” Distributed computer system, pp203-213 1998.

[9] D. Gao, M.K. Reiter, D. Song "Beyond Output Voting: Detecting Compromised Replicas Using HMM-Based Behavioral Distance", IEEE Transactions on Dependable and Secure Computing, vol.6, no.2, pp.96-110, April-June 2009. http://dx.doi.org/10.1109/TDSC.2008.39
http://dx.doi.org/10.1109/TDSC.2008.39

[10] C. Kamhoua, N. Pissinou, K. Makki " Game Theoretic Modeling and Evolution of Trust in Autonomous Multi-hop Networks: Application to Network Security and Privacy" in proceedings of the IEEE international conference on communications (IEEE ICC 2011). Kyoto, Japan. June 2011.

[11] S. Becker, J. Seibert, D. Zage, C. Nita-Rotaru, R. State“Applying Game Theory to Analyze Attacks and Defenses in Virtual Coordinate Systems” IEEE DSN 2011.

[12] F. Li; J. Wu; "Hit and Run: A Bayesian Game Between Malicious and Regular Nodes in MANETs" SECON '08. 5th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, vol., no., pp.432-440, 16-20 June 2008.

[13] Y. Liu, C. Comaniciu, H. Man "Modeling Misbehavior in Ad Hoc Networks: A Game Theoretic Approach for Intrusion Detection", International Journal of Security and Networks (IJSN) 2006. http://dx.doi.org/10.1504/IJSN.2006.011784
http://dx.doi.org/10.1504/IJSN.2006.011784

[14] M. Manshaei, Q. Zhu, T. Alpcan, T. Basar, J-P Hubaux “Game Theory Meets Network Security and Privacy” ACM transaction on Computational Logic, Vol. V, No. N, September 2010.

[15] S. Roy, C. Ellis, S. Shiva, D. Dasgupta, V. Shandilya, Q. Wu;, "A Survey of Game Theory as Applied to Network Security," 43rd Hawaii International Conference on System Sciences (HICSS), vol., no., pp.1-10, 5-8 Jan. 2010.

[16] Condorcet: “Essai sur l’application de l’analyse a la probabilite des decisions rendues a la pluralite des voix”. Paris: Imprimerie Royale. 1785.

[17] G. Owen, B. Grofman, S. Feld “Proving a Distribution-Free Generalization of the Condorcet Jury Theorem” Mathematical Social Sciences 17, 1-16, 1989. http://dx.doi.org/10.1016/0165-4896(89)90012-7
http://dx.doi.org/10.1016/0165-4896(89)90012-7

[18] R. Myerson “Extended Poisson Games and the Condorcet Jury Theorem” Games and Economic Behavior, Elsevier, 1998.

[19] J-F Laslier, J. W. Weibull “The Condorcet Jury Theorem and Heterogeneity” 2010.

[20] L. Shapley, B. Grofman “Optimizing group Judgemental Accuracy in Presence of Interdependencies” Public Choice 43: 329-343, 1984. http://dx.doi.org/10.1007/BF00118940
http://dx.doi.org/10.1007/BF00118940

[21] R. Goodin, D. Estlund “The Persuasiveness of Democratic Majorities” Politics, Philosophy & Economics 131-142, 2004. http://dx.doi.org/10.1177/1470594X04042960
http://dx.doi.org/10.1177/1470594X04042960

[22] B. Grofman, G. Owen, S. Feld “Thirteen Theorems in Search of the Truth” Theory and Decision 15, 261-278, 1983. http://dx.doi.org/10.1007/BF00125672
http://dx.doi.org/10.1007/BF00125672

[23] R. Myerson “Game theory: analysis of conflict” Harvard University Press, 1997.

[24] D. J. Leversage, E. J. Byres “Estimating a System's Mean Time-to-Compromise” IEEE Security & Privacy, 2008

[25] M. A. McQueen, W. F. Boyer, M. A. Flynn, G. A. Beitel “Time-to-Compromise Model for Cyber Risk Reduction Estimation” Quality of Protection, Springer, 2006.

[26] Rescorla, E., “Is Finding Security Holes a Good Idea,” IEEE Security & Privacy,January-2005.

[27] D. Bertsekas, “Dynamic Programming and Optimal Control”, vol. 1,2, Athena Scientific, Belmont, MA, Second edition, 2001.

[28] G. Mailath, L.Samuelson “Repeated Games and Reputations, Long-run relationships” Oxford university press, 2006. http://dx.doi.org/10.1093/acprof:oso/9780195300796.001.0001
http://dx.doi.org/10.1093/acprof:oso/9780195300796.001.0001

[29] G. Ellison “Cooperation in the Prisoner's Dilemma with Anonymous Random Matching” The Review of Economic Studies, Vol. 61. No. 3 pp. 567-588, Jul., 1994.
http://dx.doi.org/10.2307/2297904

http://dx.doi.org/10.2307/2297904


Full Text: PDF


Journal of Communications (JCM, ISSN 1796-2021)

Copyright @ 2006-2013 by ACADEMY PUBLISHER – All rights reserved.