The overall purpose of the GRIST lab is to develop and validate game theoretical models to protect infrastructures against man-made disasters. This includes planning in different levels in an organization’s hierarchy such as resource allocation, patrol scheduling, first responder assignment etc. To validate these models, we develop virtual games.

  Security Games with Unknown Adversarial Strategies:

The security community has witnessed a significant increase in the number of different types of security threats. This situation calls for the design of new techniques that can be incorporated into security protocols to meet these challenges successfully. Click here to continue... An important tool for developing new security protocols as well as estimating their effectiveness is game theory. This game theory framework usually involves two players or agents - a protector and an adversary, and two patterns of agent behavior are considered: (a) selfish behavior, where each of the agents wants to maximize his payoff, and (b) leader and follower behavior, where one agent (the leader) expects that the other agent (the follower) will respond to the leader's strategy. Such an approach assumes that the agents agree on which strategy to apply in advance. In this paper this strong assumption is relaxed. Namely, the following question is considered: what happens if it is unknown a priori what pattern of behavior the adversary is going to use, or in other words, it is not known, what game he intends to play? Using a simple game-theoretic model, it is shown that the protector can lose if he does not take into account the possibility that the adversary can play a game other than the one the protector has in mind. We further consider a repeated game in which the protector can learn about the presence of an adversary, and we analyze the behavior of belief probabilities. ▲Top

  How to Deal with an Intelligent Adversary:

Traditionally, the design of network protection strategies is based on the answers of a protector and an adversary to the question “How?'': how should the protector allocate its protection resources, and how should the adversary allocate its attacking resources? This paper considers a more sophisticated adversary, who, planning its malicious activities, considers two questions: “What for?'' and “How?''. Click here to continue... Namely, what is the motivation for the attack? and how to attack based on the chosen motivation? To study this problem, a simple game-theoretic network protection model is considered, in which the adversary decides whether to intrude on the network to inflict maximal damage or to perform a reconnaissance mission, and based on this decision an intrusion strategy is designed. The solution to this game shows that such an adversary may try a feint to draw the protector's efforts away from the nodes that the adversary intends to attack. Taking into account this feature of the adversary's behavior allows improvements in the reliability of a protection strategy. ▲Top

  A Game Theoretic Analysis of Secret and Reliable Communication with Active and Passive Adversarial Modes:

Secret and reliable communication presents a challenge involving a double dilemma for a user and an adversary. Click here to continue... Components of the adversary's dilemma are the following. While jamming can be quite effective to prevent reliable communication of the user, it can also be quite harmful for the adversary since s/he can be detected. On the other hand, in dealing with secret communication, eavesdropping is quite safe for the adversary; however it sometimes may not be so efficient compared to jamming if there is no time for correct interpretation of the eavesdropped information and for proper reaction to this information. Components of the user's dilemma are the following. The user can either transmit, thus, becoming vulnerable to malicious activity, or be in a silent mode (do not transmit) suffering in turn delaying his/her transmission. However, properly combining these modes the user can assist the Intruder Detection System to detect the adversary, since the transmission can provoke the adversary for a jamming attack, and proper switching to the silent mode while the jammer keeps on the jamming attack can increase the probability of detecting the adversary. In this paper, to get insight into this problem, two simple stochastic games are proposed. Explicit solutions are found that lead to the characterization of some interesting properties. In particular, it is shown that under some conditions, incorporating in the transmission protocol a time slot dealing just with the detection of malicious threats can improve the secrecy and reliability of the communication without extra transmission delay. ▲Top

  The Robust Game Model:

Most infrastructure security games assume that the parameters of the game are either deterministic or follow a known distribution. Whereas in reality, some parameters of the game may be uncertain with no known distribution or distributional information about them may be unreliable. In this project, we developed distribution-free models of the incomplete-information infrastructure security game with and without private information. Click here to continue... In these models, the players are uncertain about the node values and detection probabilities and they use a robust optimization approach to contend with such uncertainty. Moreover, the aim of the attack, to inflict maximum damage or to infiltrate, may be private to the adversary. We were able to prove that there always exists a unique Nash strategy for the defender. We also showed that this strategy is of threshold type. We then illustrated this approach by applying it to a case with real data. To obtain real data, we build immersive 3D virtual world. These games are designed to both collect data about the players' behavior and to validate the game models using metrics such as the expected damage, the fraction of unsuccessful attacks, etc. ▲Top Two-Stage Game Model:

Protecting infrastructures against terrorist attacks involves making both strategic and operational decisions in an organization's hierarchy. Although usually analyzed separately, these decisions influence each other. In this project, we studied the combined effect of strategic and operational decisions in a game-theoretic two-stage model. Click here to continue... The game is played between a defender and an attacker involving multiple target sites. In the first stage, the defender (attacker) makes a strategic decision of allocating investment resources to target sites in order to improve the defense (attack) capabilities. The investment allocations for each target site determine its detection probability. In the second stage, the players make operational decisions of which target site to defend/attack. We distinguish between two types of games that arise in the second stage: Maximal Damage game and Infiltration/Harassment game. We prove that the solution to this game under budget constraints is unique. In fact, when the second stage game is of Infiltration/Harassment type, the invest-defend game has a unique closed-form solution that is very intuitive. Our results lead to valuable insights about the interaction between decisions at different levels in an organizations hierarchy. ▲Top

Urban Rail Patrolling:

Patrol scheduling is a critical operational decision in protecting urban rail networks against terrorist activities. Designing patrols to protect such systems poses many challenges that have not been comprehensively addressed in the literature of patrol scheduling so far. These challenges include strategic attackers, dynamically changing station occupancy levels and human resource related limitations. In this project, we developed a game theoretic model for the problem of scheduling security teams to patrol an urban mass transit rail network. Click here to continue... Our main objective was to minimize the expected potential damage caused by terrorist activities while observing scheduling constraints. We modeled this problem as a non-cooperative simultaneous move game between a defender and an attacker. We then developed column generation based algorithms to find a Nash equilibrium for this game. We also presented a lower bound for the value of the game, which can be used to terminate the column generation algorithm when a desired solution quality is reached. We were able to apply this model to a real urban rail network. ▲Top

Patrolling Games with Dynamic Node Values on a General Graph:

Scheduling and deployment of patrols is an important operational decision in safeguarding an area against adversarial invasion or illicit activity. Patrolling game models are useful when dealing with strategic adversaries. Most of the patrolling games assume that all of the nodes have the same value or that their values are fixed throughout time. However, in reality, the nodes may have different values; moreover, these values may change over time. Click here to continue... In this project, we consider a general patrolling game model on a general graph with different and dynamically changing node values and different attack times. We develop an efficient column generation approach to solve this problem. We also present a lower bound for the value of the game, which can be used to terminate the column generation algorithm when a desired solution quality is reached. Our results show that the proposed column generation approach performs better than enumerating every possible strategy for players. Moreover, the performance gap increases as the edge density of graphs increase. Our results also show that the patroller can decrease the expected damage by using dynamic node values in designing her strategy. ▲Top