Kiekintveld, Christopher


Strategic Information Revelation and Commitment in Security Games

AAAI Conferences

The Strong Stackelberg Equilibrium (SSE) has drawn extensive attention recently in several security domains, which optimizes the defender's random allocation of limited security resources. However, the SSE concept neglects the advantage of defender's strategic revelation of her private information, and overestimates the observation ability of the adversaries. In this paper, we overcome these restrictions and analyze the tradeoff between strategic secrecy and commitment in security games. We propose a Disguised-resource Security Game (DSG) where the defender strategically disguises some of her resources. We compare strategic information revelation with public commitment and formally show that they have different advantages depending the payoff structure. To compute the Perfect Bayesian Equilibrium (PBE), several novel approaches are provided, including basic MILP formulations with mixed defender strategy and compact representation, a novel algorithm based on support set enumeration, and an approximation algorithm for epsilon-PBE. Extensive experimental evaluation shows that both strategic secrecy and Stackelberg commitment are critical measures in security domain, and our approaches can solve PBE for realistic-sized problems with good enough and robust solution quality.


Adapting Honeypot Configurations to Detect Evolving Exploits

AAAI Conferences

Honeypots are fake resources that gain value in being probed and attacked. They deceive network intruders into detailing the intruder's behavior and the nature of an intended attack. A honeypot's success relies on the quality of its deception and the perceived value to the attacker. In this paper, we emphasize the latter. We model a repeated game where a defender must select from a list of honeypot configurations to detect an adversary's attack. The adversary's attacks each contain their own unique value function and required features to execute an exploit. Each exploits "evolves" by having its value decreases with the number of detections and new attacks may be added to the adversary's arsenal as the game progresses. We show that this model demands the defender to act strategically, by showing the adversary can exploit naive defense strategies. To solve this problem, we leverage the Multi-Armed Bandit (MAB) framework, a class of machine learning problems that demand balance between exploration and exploitation.


Optimizing Personalized Email Filtering Thresholds to Mitigate Sequential Spear Phishing Attacks

AAAI Conferences

Highly targeted spear phishing attacks are increasingly common, and have been implicated in many major security breeches. Email filtering systems are the first line of defense against such attacks. These filters are typically configured with uniform thresholds for deciding whether or not to allow a message to be delivered to a user. However, users have very significant differences in both their susceptibility to phishing attacks as well as their access to critical information and credentials that can cause damage. Recent work has considered setting personalized thresholds for individual users based on a Stackelberg game model. We consider two important extensions of the previous model. First, in our model user values can be substitutable, modeling cases where multiple users provide access to the same information or credential. Second, we consider attackers who make sequential attack plans based on the outcome of previous attacks. Our analysis starts from scenarios where there is only one credential and then extends to more general scenarios with multiple credentials. For single-credential scenarios, we demonstrate that the optimal defense strategy can be found by solving a binary combinatorial optimization problem called PEDS. For multiple-credential scenarios, we formulate it as a bilevel optimization problem for finding the optimal defense strategy and then reduce it to a single level optimization problem called PEMS using complementary slackness conditions. Experimental results show that both PEDS and PEMS lead to significant higher defender utilities than two existing benchmarks in different parameter settings. Also, both PEDS and PEMS are more robust than the existing benchmarks considering uncertainties.


Teaching Automated Strategic Reasoning Using Capstone Tournaments

AAAI Conferences

Courses in artificial intelligence and related topics often cover methods for reasoning under uncertainty, decision theory, and game theory. However, these methods can seem very abstract when students first encounter them, and they are often taught using simple “toy” problems. Our goal is to help students to operationalize this knowledge by designing sophisticated autonomous agents that must make complex decisions in games that capture their interest. We describe a tournament-based pedagogy that we have used in two different courses with two different games based on current research topics in artificial intelligence to engage students in designing agents that use strategic reasoning. Many students find this structure very engaging, and we find that students develop a deeper understanding of the abstract strategic reasoning concepts introduced in the courses.


Preventing Illegal Logging: Simultaneous Optimization of Resource Teams and Tactics for Security

AAAI Conferences

Green security — protection of forests, fish and wildlife — is a critical problem in environmental sustainability. We focus on the problem  of  optimizing the defense of forests againstillegal logging, where often we are faced with the challenge of teaming up many different groups,  from national police to forest guards to NGOs, each with differing capabilities and costs. This paper introduces a new, yet fundamental problem: SimultaneousOptimization of Resource Teams and Tactics (SORT).  SORT contrasts with most previous game-theoretic research for green security — in particular based onsecurity games — that has solely focused on optimizing patrolling tactics, without consideration of team formation or coordination.  We develop new models and scalable algorithms to apply SORT towards illegal logging in large forest areas. We evaluate our methods on a variety of synthetic examples, as well as a real-world case study using data from our on-going collaboration in Madagascar .


Using Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form Games

AAAI Conferences

Strong Stackelberg Equilibrium (SSE) is a fundamental solution concept in game theory in which one player commits to a strategy, while the other player observes this commitment and plays a best response. We present a new algorithm for computing SSE for two-player extensive-form general-sum games with imperfect information (EFGs) where computing SSE is an NP-hard problem. Our algorithm is based on a correlated version of SSE, known as Stackelberg Extensive-Form Correlated Equilibrium (SEFCE). Our contribution is therefore twofold: (1) we give the first linear program for computing SEFCE in EFGs without chance, (2) we repeatedly solve and modify this linear program in a systematic search until we arrive to SSE. Our new algorithm outperforms the best previous algorithms by several orders of magnitude.


Reports on the 2015 AAAI Spring Symposium Series

AI Magazine

The AAAI 2015 Spring Symposium Series was held Monday through Wednesday, March 23-25, at Stanford University near Palo Alto, California. The titles of the seven symposia were Ambient Intelligence for Health and Cognitive Enhancement, Applied Computational Game Theory, Foundations of Autonomy and Its (Cyber) Threats: From Individuals to Interdependence, Knowledge Representation and Reasoning: Integrating Symbolic and Neural Approaches, Logical Formalizations of Commonsense Reasoning, Socio-Technical Behavior Mining: From Data to Decisions, Structured Data for Humanitarian Technologies: Perfect Fit or Overkill?


Reports on the 2015 AAAI Spring Symposium Series

AI Magazine

The AAAI 2015 Spring Symposium Series was held Monday through Wednesday, March 23-25, at Stanford University near Palo Alto, California. The titles of the seven symposia were Ambient Intelligence for Health and Cognitive Enhancement, Applied Computational Game Theory, Foundations of Autonomy and Its (Cyber) Threats: From Individuals to Interdependence, Knowledge Representation and Reasoning: Integrating Symbolic and Neural Approaches, Logical Formalizations of Commonsense Reasoning, Socio-Technical Behavior Mining: From Data to Decisions, Structured Data for Humanitarian Technologies: Perfect Fit or Overkill? and Turn-Taking and Coordination in Human-Machine Interaction.The highlights of each symposium are presented in this report.


Combining Compact Representation and Incremental Generation in Large Games with Sequential Strategies

AAAI Conferences

Many search and security games played on a graph can be modeled as normal-form zero-sum games with strategies consisting of sequences of actions. The size of the strategy space provides a computational challenge when solving these games. This complexity is tackled either by using the compact representation of sequential strategies and linear programming, or by incremental strategy generation of iterative double-oracle methods. In this paper, we present novel hybrid of these two approaches: compact-strategy double-oracle (CS-DO) algorithm that combines the advantages of the compact representation with incremental strategy generation. We experimentally compare CS-DO with the standard approaches and analyze the impact of the size of the support on the performance of the algorithms. Results show that CS-DO dramatically improves the convergence rate in games with non-trivial support


Initial Exploration of Machine Learning to Predict Customer Demand in an Energy Market Simulation

AAAI Conferences

The PowerTAC competition focuses on trading activities in energy markets. One of the important subtasks of designing an effective agent for this scenario is to predict the energy use and generation of the customer agents in the marketplace. These predictions can inform pricing and tariff design questions, as well as decisions to balance power use and generation over time. Similar prediction problems are also important in real world energy markets. Here we present some initial experiments applying machine learning to predict future customer energy usage patterns in the PowerTAC simulation.