# Paper Submission

Submission page: https://www.easychair.org/conferences/?conf=gamesec2013

**Submission instructions**

Prospective authors are encouraged to submit a PDF version of their papers adhering to the Springer Lecture Notes in Computer Science (LNCS) format. Each submission should be previously unpublished work that is not currently under submission to another conference. Submissions can be (but do not have to be) anonymized. Full paper submissions are not to exceed 20 pages including references and well-formatted appendices. Full papers should make a strong technical contribution and adequately highlight the novel aspects of the work in relation to related research. Short paper submissions may present work in progress, novel applications and practice/industry experiences. Potential short papers will be evaluated based on their novelty and potential for sparking discussions and future collaborations. Short paper submissions are limited to 10 pages.

# GameSec 2013 Proceedings

The conference proceedings published by Springer as part of the LNCS series are available here and here.

# List of Accepted Full Papers

**Monotonic Maximin: A Robust Stackelberg Solution Against Boundedly Rational Followers**

Albert Xin Jiang, University of Southern California (Presenter)

Thanh H. Nguyen, University of Southern California

Milind Tambe, University of Southern California

Ariel D. Procaccia, Carnegie Mellon University

**Abstract:**There has been recent interest in applying Stackelberg games to infrastructure security, in which a defender must protect targets from attack by an adaptive adversary. In real-world security settings the adversaries are humans and are thus boundedly rational. Most existing approaches for computing defender strategies against boundedly rational adversaries try to optimize against specific behavioral models of adversaries, and provide no quality guarantee when the estimated model is inaccurate. We propose a new solution concept, monotonic maximin, which provides guarantees against all adversary behavior models satisfying monotonicity, including all in the family of Regular Quantal Response functions. We propose a mixed-integer linear program formulation for computing monotonic maximin. We also consider top-monotonic maximin, a related solution concept that is more conservative, and propose a polynomial-time algorithm for top-monotonic maximin.

**Equilibrium Concepts for Rational Multiparty Computation**

John Ross Wallrabenstein, C.S. Dept., Purdue University (Presenter)

Chris Clifton, C.S. Dept., Purdue University

**Abstract:**In this work, we build upon previous results to strengthen the equilibrium concept for rational multiparty computation. We consider only rational players, acting to maximize their utility functions. We consider extensive form dynamic games of imperfect information, using a computational variant of perfect Bayesian equilibrium as the solution concept. We argue that the perfect Bayesian equilibrium is a more appropriate solution concept than current solutions, as in cryptographic protocols information is often imperfect by design. Further, the perfect Bayesian equilibrium concept is able to address dynamic games, where players move sequentially rather than simultaneously. By considering players that move sequentially, we are able to remove the assumption of a broadcast channel. Finally, we give novel definitions of privacy, correctness and fairness solely in terms of game theoretic constructs.

**Optimizing Active Cyber Defense**

Wenlian Lu, School of Mathematical Sciences, Fudan University and Department of Computer Science, University of Warwick

Shouhuai Xu, Department of Computer Science, University of Texas at San Antonio (Presenter)

Xinlei Yi, School of Mathematical Sciences, Fudan University

**Abstract:**Active cyber defense is one important defensive method for combating cyber attacks. Unlike traditional defensive methods such as firewall-based filtering and anti-malware tools, active cyber defense is based on spreading "white" or "benign" worms to combat against the attackers' malwares (i.e., malicious worms) that also spread over the network. In this paper, we initiate the study of*optimal*active cyber defense in the setting of strategic attackers and/or strategic defenders. Specifically, we investigate infinite-time horizon optimal control and fast optimal control for strategic defenders (who want to minimize their cost) against non-strategic attackers (who do not consider the issue of cost). We also investigate the Nash equilibria for strategic defenders and attackers. We discuss the cyber security meanings/implications of the theoretic results. Our study brings interesting open problems for future research.

**Quantifying Network Topology Robustness Under Budget Constraints: General Model and Computational Complexity**

Aron Laszka, Laboratory of Cryptography and System Security (CrySyS Lab), Budapest University of Technology and Economics (Presenter)

Assane Gueye, National Institute of Standards and Technology (NIST)

**Abstract:**Recently, network blocking game (NBG) models have been introduced and utilized to quantify the vulnerability of network topologies in adversarial environments. In NBG models, the payoff matrix of the game is only "implicitly" given. As a consequence, computing a Nash equilibrium in these games is expected to be harder than in more conventional models, where the payoff matrix is "explicitly" given.

In this paper, we first show that computing a Nash equilibrium of a NBG is in general NP-hard. Surprisingly, however, there are particular interesting cases for which the game can be solved in polynomial time. We revisit these cases in a framework where the network is to be operated under budget constraints, which previous models did not consider. We generalize previous blocking games by introducing a budget limit on the operator and consider two constraint formulations: the maximum and the expected cost constraints.

For practical applications, the greatest challenge posed by blocking games is their computational complexity. Therefore, we show that the maximum cost constraint leads to NP-hard problems, even for games that were shown to be efficiently solvable in the unconstrained case. On the other hand, we show that the expected cost constraint formulation leads to games that can be solved efficiently.

**Mitigation of Targeted and Non-Targeted Covert Attacks as a Timing Game**

Aron Laszka, Laboratory of Cryptography and System Security (CrySyS Lab), Budapest University of Technology and Economics (Presenter)

Benjamin Johnson, University of California, Berkeley

Jens Grossklags, Pennsylvania State University

**Abstract:**We consider a strategic game in which a defender wants to maintain control over a resource that is subject to both targeted and non-targeted covert attacks. Because the attacks are covert, the defender must choose to secure the resource in real time without knowing who controls it. Each move by the defender to secure the resource has a one-time cost and these defending moves are not covert, so that a targeted attacker may time her attacks based on the defender's moves. The time between when a targeted attack starts and when it succeeds is given by an exponentially distributed random variable with a known rate. Non-targeted attackers are modeled together as a single attacker whose attacks arrive following a Poisson process. We find that in this regime, the optimal moving strategy for the defender is a periodic strategy, so that the time intervals between consecutive moves are constant.

# List of Accepted Short Papers

**The Cooperative Ballistic Missile Defense Game**

Lanah Evers^{1,2,3}

Ana Isabel Barros^{1,2}

Herman Monsuur^{2}(Presenter)

^{1}TNO - Defence, Safety and Security

^{2}Netherlands Defence Academy

^{3}Econometric Institute, Erasmus University Rotterdam

**Abstract:**The increasing proliferation of ballistic missiles and weapons of mass destruction poses new risks worldwide. For a threatened nation and given the characteristics of this threat a layered ballistic missile defence system strategy appears to be the preferred solution. However, such a strategy involves negotiations with other nations concerning the use of their defence systems as part of the layered defence system. This paper introduces the Cooperative Ballistic Missile Defense Game, CBMDG, to support the strategic negotiations between a threatened nation and the possible coalition nations. The model determines the assignment of ballistic missile interceptors to the coalition nations that minimizes the expected number of interceptors required to achieve the desired defence level in case of an attack. Simultaneously, it identifies the bargaining strength of each coalition of nations, in order to determine the compensation for participating in the layered defence system to protect the threatened nation.

**New Efficient Utility Upper Bounds for the Fully Adaptive Model of Attack Trees**

Aleksandr Lenin, Cybernetica AS, Tallinn University of Technology (Presenter)

Ahto Buldas, Guardtime AS, Tallinn University of Technology

**Abstract:**We present a new fully adaptive computational model for attack trees that allows attackers to repeat atomic attacks if they fail and to play on if they are caught and have to pay penalties. The new model allows safer conclusions about the security of real-life systems and is somewhat (computationally) easier to analyze. We show that in the new model optimal strategies always exist and finding the optimal strategy is (just) an NP-complete problem. We also present methods to compute adversarial utility estimation and utility upper bound approximated estimation using a bottom-up pproach.

**True Randomness Generators using Human Gameplay**

Mohsen Alimomeni, University of Calgary

Reihaneh Safavi-Naini, University of Calgary (Presenter)

Setareh Sharifian, University of Calgary

**Abstract:**True Randomness Generators (TRG) use the output of an entropy source to generate a sequence that is sufficiently close to a uniformly random string and so can be securely used in applications that rely on unpredictability of the string. A TRG algorithm generally consists of (i) an entropy source and (ii) an extractor algorithm that uses a random seed to extract the randomness of the entropy source. We propose a TRG that uses the user input in a game played between the user and the computer, both as the output of an entropy source, and the random seed required for the extractor. An important property of the TRG is that the quality of its output can be flexibly adjusted.

We describe our approach and the implementation of a game based on the approach, and provide the results of our experiments with users and analysis of the output strings. Our results show effectiveness of the approach in generating high quality randomness that users can trust. We discuss our results and propose directions for future work.