Lidé

doc. Mgr. Branislav Bošanský, Ph.D.

Všechny publikace

Cyber Deception Against Zero-Day Attacks: A Game Theoretic Approach

  • Autoři: Sayed, M.A., Anwar, A.H., Kiekintveld, C., doc. Mgr. Branislav Bošanský, Ph.D., Kamhoua, C.
  • Publikace: Decision and Game Theory for Security. Cham: Springer International Publishing, 2023. p. 44-63. LNCS. vol. 13727. ISSN 1611-3349. ISBN 978-3-031-26369-9.
  • Rok: 2023
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Reconnaissance activities precedent other attack steps in the cyber kill chain. Zero-day attacks exploit unknown vulnerabilities and give attackers the upper hand against conventional defenses. Honeypots have been used to deceive attackers by misrepresenting the true state of the network. Existing work on cyber deception does not model zero-day attacks. In this paper, we address the question of “How to allocate honeypots over the network?” to protect its most valuable assets. To this end, we develop a two-player zero-sum game theoretic approach to study the potential reconnaissance tracks and attack paths that attackers may use. However, zero-day attacks allow attackers to avoid placed honeypots by creating new attack paths. Therefore, we introduce a sensitivity analysis to investigate the impact of different zero-day vulnerabilities on the performance of the proposed deception technique. Next, we propose several mitigating strategies to defend the network against zero-day attacks based on this analysis. Finally, our numerical results validate our findings and illustrate the effectiveness of the proposed defense approach.

Solving zero-sum one-sided partially observable stochastic games

  • DOI: 10.1016/j.artint.2022.103838
  • Odkaz: https://doi.org/10.1016/j.artint.2022.103838
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Many real-world situations are dynamic, with long-term interactions between multiple agents with uncertainty and limited observations. The agents must reason about which actions to take while also predicting and learning about what actions the other agents will take and how their choices will interact. In the most general setting, there is no limitation on the length of the sequence of actions the agent can perform - that is, there is no fixed horizon that can be used as an endpoint for analysis. These settings can be modeled as partially observable stochastic games (POSGs). Many adversarial domains (e.g., security settings) can be modeled as strictly competitive (or zero-sum) variants of these games. While these models are capable of modeling a wide variety of realistic problems, solving general POSGs is computationally intractable, so we focus on a broad subclass of POSGs called one-sided POSGs. In these games, only one agent has imperfect information while their opponent has full knowledge of the current situation. We provide a complete approach for solving zero-sum, one-sided POSGs: we (1) give a theoretical analysis of one-sided POSGs and their value functions, (2) show that a variant of a value-iteration algorithm converges in this setting, (3) adapt the heuristic search value-iteration algorithm for solving one-sided POSGs, (4) describe how to use approximate value functions to derive strategies in the game, and (5) experimentally demonstrate that our algorithm can solve one-sided POSGs of non-trivial sizes and analyze the scalability of our algorithm in three different domains: pursuit-evasion, patrolling, and search games.(c) 2022 Elsevier B.V. All rights reserved.

Computing Quantal Stackelberg Equilibrium in Extensive-Form Games

  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Deployments of game-theoretic solution concepts in the real world have highlighted the necessity to consider human opponents' boundedly rational behavior. If subrationality is not addressed, the system can face significant losses in terms of expected utility. While there exist algorithms for computing optimal strategies to commit to when facing subrational decision-makers in one-shot interactions, these algorithms cannot be generalized for solving sequential scenarios because of the inherent curse of strategy-space dimensionality in sequential games and because humans act subrationally in each decision point separately. We study optimal strategies to commit to against subrational opponents in sequential games for the first time and make the following key contributions: (1) we prove the problem is NP-hard in general; (2) to enable further analysis, we introduce a non-fractional reformulation of the direct non-concave representation of the equilibrium; (3) we identify conditions under which the problem can be approximated in polynomial time in the size of the representation; (4) we show how an MILP can approximate the reformulation with a guaranteed bounded error, and (5) we experimentally demonstrate that our algorithm provides higher quality results several orders of magnitude faster than a baseline method for general non-linear optimization.

Solving Partially Observable Stochastic Shortest-Path Games

  • DOI: 10.24963/ijcai.2021/575
  • Odkaz: https://doi.org/10.24963/ijcai.2021/575
  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    We study the two-player zero-sum extension of the partially observable stochastic shortest-path problem where one agent has only partial information about the environment. We formulate this problem as a partially observable stochastic game (POSG): given a set of target states and negative rewards for each transition, the player with imperfect information maximizes the expected undiscounted total reward until a target state is reached. The second player with the perfect information aims for the opposite. We base our formalism on POSGs with one-sided observability (OS-POSGs) and give the following contributions: (1) we introduce a novel heuristic search value iteration algorithm that iteratively solves depth-limited variants of the game, (2) we derive the bound on the depth guaranteeing an arbitrary precision, (3) we propose a novel upper-bound estimation that allows early terminations, and (4) we experimentally evaluate the algorithm on a pursuit-evasion game.

Automated Construction of Bounded-loss Imperfect-recall Abstractions in Extensive-form Games

  • DOI: 10.1016/j.artint.2020.103248
  • Odkaz: https://doi.org/10.1016/j.artint.2020.103248
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Extensive-form games (EFGs) model finite sequential interactions between players. The amount of memory required to represent these games is the main bottleneck of algorithms for computing optimal strategies and the size of these strategies is often impractical for real-world applications. A common approach to tackle the memory bottleneck is to use information abstraction that removes parts of information available to players thus reducing the number of decision points in the game. However, existing information-abstraction techniques are either specific for a particular domain, they do not provide any quality guarantees, or they are applicable to very small subclasses of EFGs. We present domain-independent abstraction methods for creating imperfect recall abstractions in extensive-form games that allow computing strategies that are (near) optimal in the original game. To this end, we introduce two novel algorithms, FPIRA and CFR+IRA, based on fictitious play and counterfactual regret minimization. These algorithms can start with an arbitrary domain specific, or the coarsest possible, abstraction of the original game. The algorithms iteratively detect the missing information they require for computing a strategy for the abstract game that is (near) optimal in the original game. This information is then included back into the abstract game. Moreover, our algorithms are able to exploit imperfect-recall abstractions that allow players to forget even history of their own actions. However, the algorithms require traversing the complete unabstracted game tree. We experimentally show that our algorithms can closely approximate Nash equilibrium of large games using abstraction with as little as 0.9% of information sets of the original game. Moreover, the results suggest that memory savings increase with the increasing size of the original games.

Automated construction of bounded-loss imperfect-recall abstractions in extensive-form games

  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Information abstraction is one of the methods for tackling large extensive-form games (EFGs). Removing some information available to players reduces the memory required for computing and storing strategies. We present novel domain-independent abstraction methods for creating very coarse abstractions of EFGs that still compute strategies that are (near) optimal in the original game. First, the methods start with an arbitrary abstraction of the original game (domain-specific or the coarsest possible). Next, they iteratively detect which information is required in the abstract game so that a (near) optimal strategy in the original game can be found and include this information into the abstract game. Moreover, the methods are able to exploit imperfect-recall abstractions where players can even forget the history of their own actions. We present two algorithms that follow these steps - FPIRA, based on fictitious play, and CFR+IRA, based on counterfactual regret minimization. The experimental evaluation confirms that our methods can closely approximate Nash equilibrium of large games using abstraction with only 0.9% of information sets of the original game.

Dinkelbach-type algorithm for computing quantal stackelberg equilibrium

  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Stackelberg security games (SSGs) have been deployed in many real-world situations to optimally allocate scarce resource to protect targets against attackers. However, actual human attackers are not perfectly rational and there are several behavior models that attempt to predict subrational behavior. Quantal response is among the most commonly used such models and Quantal Stackelberg Equilibrium (QSE) describes the optimal strategy to commit to when facing a subrational opponent. Non-concavity makes computing QSE computationally challenging and while there exist algorithms for computing QSE for SSGs, they cannot be directly used for solving an arbitrary game in the normal form. We (1) present a transformation of the primal problem for computing QSE using a Dinkelbach's method for any general-sum normal-form game, (2) provide a gradient-based and a MILP-based algorithm, give the convergence criteria, and bound their error, and finally (3) we experimentally demonstrate that using our novel transformation, a QSE can be closely approximated several orders of magnitude faster.

Discovering Imperfectly Observable Adversarial Actions Using Anomaly Detection

  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Defenders in security problems often use anomaly detection (AD) to examine effects of (adversarial) actions and detect malicious behavior. Attackers seek to accomplish their goal (e.g., exfiltrate data) while avoiding the detection. Game theory can be used to reason about this interaction. While AD has been used in game-theoretic frameworks before, we extend the existing works to more realistic settings by (1) allowing players to have continuous action spaces and (2) assuming that the defender cannot perfectly observe the action of the attacker. We solve our model by (1) extending existing algorithms that discretize the action spaces and use linear programming and (2) by training a neural network using an algorithm based on exploitability descent, termed EDA. While both algorithms are applicable for low feature-space dimensions, EDA produces less exploitable strategies and scales to higher dimensions. In a data exfiltration scenario, EDA outperforms a range of classifiers when facing a targeted exploitative attacker.

Finite State Machines Play Extensive-Form Games

  • Autoři: Černý, J., doc. Mgr. Branislav Bošanský, Ph.D., An, B.
  • Publikace: EC '20: Proceedings of the 21st ACM Conference on Economics and Computation. Association for Computing Machinery, 2020. p. 509-533. ISBN 978-1-4503-7975-5.
  • Rok: 2020
  • DOI: 10.1145/3391403.3399517
  • Odkaz: https://doi.org/10.1145/3391403.3399517
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Finite state machines are a well-known representation of strategies in (in)finitely repeated or stochastic games. Actions of players correspond to states in the machine and the transition between machine-states are caused by observations in the game. For extensive-form games (EFGs), machines can act as a formal grounding for abstraction methods used for solving large EFGs and as a domain-independent approach for generating sufficiently compact abstractions. We show that using machines of a restricted size in EFGs can both (i) reduce the theoretical complexity of computing some solution concepts, including Strong Stackelberg Equilibrium (SSE), (ii) as well as bring new practical algorithms that compute near-optimal equilibria considering only a fraction of strategy space. Our contributions include (1) formal definition and theoretical characterization of machine strategies in EFGs, (2) formal definitions and complexity analysis for solution concepts and their computation when restricted to small classes of machines, (3) new algorithms for computing SSE in general-sum games and Nash Equilibrium in zero-sum games that both directly use the concept of machines. Experimental results on two different domains show that the algorithms compute near-optimal strategies and achieve significantly better scalability compared to previous state-of-the-art algorithms.

Using One-Sided Partially Observable Stochastic Games for Solving Zero-Sum Security Games with Sequential Attacks

  • DOI: 10.1007/978-3-030-64793-3_21
  • Odkaz: https://doi.org/10.1007/978-3-030-64793-3_21
  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    Security games are a defender-attacker game-theoretic model where the defender determines how to allocate scarce resources to protect valuable targets against the attacker. A majority of existing work has focused on the one-shot game setting in which the attacker only attacks once. However, in many real-world scenarios, the attacker can perform multiple attacks in a sequential manner and leverage observable e_ects of these attacks for better attack decisions in the future. Recent work shows that in order to provide e_ective protection over targets, the defender has to take the prospect of sequential attacks into consideration. The algorithm proposed by existing work to handle sequential attacks, however, can only scale up to two attacks at most. We extend this line of work and focus on developing new scalable algorithms for solving the zero-sum variant of security games.We formulate security games with sequential attacks as a one-sided partially observable stochastic games. We show that the uncertainty about the state in the game can be modeled compactly and we can use variants of heuristic search value iteration algorithm for solving these games. We give two variants of the algorithm { an exact one and a heuristic formulation where the resource reallocation possibilities of the defender are simpli_ed. We experimentally compare these two variants of the algorithm and show that the heuristic variant is typically capable of _nding high-quality strategies while scaling to larger scenarios compared to the exact variant.

Compact Representation of Value Function in Partially Observable Stochastic Games

  • Autoři: Ing. Karel Horák, Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., Kiekintveld, Ch., Kamhoua, Ch.
  • Publikace: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2019. p. 350-356. ISSN 1045-0823. ISBN 978-0-9992411-4-1.
  • Rok: 2019
  • DOI: 10.24963/ijcai.2019/50
  • Odkaz: https://doi.org/10.24963/ijcai.2019/50
  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    Value methods for solving stochastic games with partial observability model the uncertainty of the players as a probability distribution over possible states, where the dimension of the belief space is the number of states. For many practical problems, there are exponentially many states which causes scalability problems. We propose an abstraction technique that addresses this curse of dimensionality by projecting the high-dimensional beliefs onto characteristic vectors of significantly lower dimension (e.g., marginal probabilities). Our main contributions are (1) a novel compact representation of the uncertainty in partially observable stochastic games and (2) a novel algorithm using this representation that is based on existing state-of-the-art algorithms for solving stochastic games with partial observability. Experimental evaluation confirms that the new algorithm using the compact representation dramatically increases scalability compared to the state of the art.

Hardening networks against strategic attackers using attack graph games

  • DOI: 10.1016/j.cose.2019.101578
  • Odkaz: https://doi.org/10.1016/j.cose.2019.101578
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    We consider the problem faced by a network administrator (defender) when deploying limited security resources to protect a network against a strategic attacker. To evaluate the effectiveness of a defense strategy, one must consider possible counterattacks that an attacker can choose. We use game theory to model the interaction between the defender and the attacker. Game theory provides relevant concepts and algorithms for computing optimal strategies in environments with multiple decision makers. To model the space of attacker's possible actions, we use attack graphs, that compactly represent all known sequences of attacker's action that may lead to successful attack for a given network. We demonstrate our approach on a specific type of defense actions, where the defender deploys deceptive hosts and services (honeypots) to detect and mitigate attacks. We assume the worst-case attacker who has a complete knowledge of the (typically randomized) defense strategy. We seek the optimal defense strategy against this attacker in the form of a Stackelberg equilibrium. Computing this solution exactly using standard techniques has limited scalability, so we investigate several approaches for increasing scalability to realistic problems. We introduce optimization methods for finding exact solutions for these games and then propose a variety of polynomial heuristic algorithms that scale to significantly larger games. We analyze the scalability and the quality of these heuristic solutions on realistic network topologies. We show that the strategies found by the heuristics are often near-optimal and that they outperform non-game-theoretic baselines. Finally, we show how attack graph games can be used to answer various research questions relevant to network security administrators.

Optimizing Honeypot Strategies Against Dynamic Lateral Movement Using Partially Observable Stochastic Games

  • DOI: 10.1016/j.cose.2019.101579
  • Odkaz: https://doi.org/10.1016/j.cose.2019.101579
  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    Partially observable stochastic games (POSGs) are a general game-theoretic model for capturing dynamic interactions where players have partial information. The existing algorithms for solving subclasses of POSGs have theoretical guarantees for converging to approximate optimal strategies, however, their scalability is limited and they cannot be directly used to solve games of realistic sizes. In our problem, the attacker uses lateral movement through the network in order to reach a specific host, while the defender wants to discover the attacker by dynamically reallocating honeypots. We demonstrate that restricting to a specific domain allows us to substantially improve existing algorithms: (1) we formulate a compact representation of uncertainty the defender faces, (2) we exploit the incremental strategy-generation method that over iterations expands the possible actions for players. The experimental evaluation shows that our novel algorithms scale several orders of magnitude better compared to the existing state of the art.

Solving Partially Observable Stochastic Games with Public Observations

  • DOI: 10.1609/aaai.v33i01.33012029
  • Odkaz: https://doi.org/10.1609/aaai.v33i01.33012029
  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    n many real-world problems, there is a dynamic interactionbetween competitive agents. Partially observable stochasticgames (POSGs) are among the most general formal mod-els that capture such dynamic scenarios. The model capturesstochastic events, partial information of players about the en-vironment, and the scenario does not have a fixed horizon.Solving POSGs in the most general setting is intractable.Therefore, the research has been focused on subclasses ofPOSGs that have a value of the game and admit designing(approximate) optimal algorithms. We propose such a sub-class for two-player zero-sum games with discounted-sumobjective function—POSGs withpublic observations(PO-POSGs)—where each player is able to reconstruct beliefs ofthe other player over the unobserved states. Our results in-clude: (1) theoretical analysis of PO-POSGs and their valuefunctions showing convexity (concavity) in beliefs of maxi-mizing (minimizing) player, (2) a novel algorithm for approx-imating the value of the game, and (3) a practical demon-stration of scalability of our algorithm. Experimental resultsshow that our algorithm can closely approximate the value ofnon-trivial games with hundreds of states

Tackling Sequential Attacks in Security Games

  • Autoři: Nguyen, T.H., Yadav, A., doc. Mgr. Branislav Bošanský, Ph.D., Liang, Y.
  • Publikace: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Wien: Springer, 2019. p. 331-351. vol. 11836. ISSN 0302-9743. ISBN 9783030324292.
  • Rok: 2019
  • DOI: 10.1007/978-3-030-32430-8_20
  • Odkaz: https://doi.org/10.1007/978-3-030-32430-8_20
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Many real-world security problems exhibit the challenge of sequential attacks (i.e., the attacker carries out multiple attacks in a sequential manner) on important targets. Security agencies have to dynamically allocate limited security resources to the targets in response to these attacks, upon receiving real-time observations regarding them. This paper focuses on tackling sequential attacks using Stackelberg security games (SSGs), a well-known class of leader-follower games, which have been applied for solving many real-world security problems. Previous work on SSGs mainly considers a myopic attacker who attacks one or multiple targets simultaneously against each defense strategy. This paper introduces a new sequential-attack game model (built upon the Stackelberg game model), which incorporates real-time observations, the behavior of sequential attacks, and strategic plans of non-myopic players. Based on the new game model, we propose practical game-theoretic algorithms for computing an equilibrium in different game settings. Our new algorithms exploit intrinsic properties of the equilibrium to derive compact representations of both game state history and strategy spaces of players (which are exponential in number in the original representations). Finally, our computational experiments quantify benefits and losses to the attacker and defender in the presence of sequential attacks.

Using Classical Planning in Adversarial Problems

  • DOI: 10.1109/ICTAI.2019.00185
  • Odkaz: https://doi.org/10.1109/ICTAI.2019.00185
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Many problems from classical planning are applied in the environment with other, possibly adversarial agents. However, plans found by classical planning algorithms lack the robustness against the actions of other agents - the quality of computed plans can be significantly worse compared to the model. To explicitly reason about other (adversarial) agents, the game-theoretic framework can be used. The scalability of game-theoretic algorithms, however, is limited and often insufficient for real-world problems. In this paper, we combine classical domain-independent planning algorithms and game-theoretic strategy-generation algorithm where plans form strategies in the game. Our contribution is threefold. First, we provide the methodology for using classical planning in this game-theoretic framework. Second, we analyze the trade-off between the quality of the planning algorithm and the robustness of final randomized plans and the computation time. Finally, we analyze different variants of integration of classical planning algorithms into the game-theoretic framework and show that at the cost a minor loss in the robustness of final plans, we can significantly reduce the computation time.

When Players Affect Target Values: Modeling and Solving Dynamic Partially Observable Security Games

  • Autoři: Wang, X., Tambe, M., doc. Mgr. Branislav Bošanský, Ph.D., An, B.
  • Publikace: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Wien: Springer, 2019. p. 542-562. vol. 11836. ISSN 0302-9743. ISBN 9783030324292.
  • Rok: 2019
  • DOI: 10.1007/978-3-030-32430-8_32
  • Odkaz: https://doi.org/10.1007/978-3-030-32430-8_32
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Most of the current security models assume that the values of targets/areas are static or the changes (if any) are scheduled and known to the defender. Unfortunately, such models are not sufficient for many domains, where actions of the players modify the values of the targets. Examples include wildlife scenarios, where the attacker can increase value of targets by secretly building supporting facilities. To address such security game domains with player-affected values, we first propose DPOS3G, a novel partially observable stochastic Stackelberg game where target values are determined by the players’ actions; the defender can only partially observe these targets’ values, while the attacker can fully observe the targets’ values and the defender’s strategy. Second, we propose RITA (Reduced game Iterative Transfer Algorithm), which is based on the heuristic search value iteration algorithm for partially observable stochastic game (PG-HSVI) and introduces three key novelties: (a) building a reduced game with only key states (derived from partitioning the state space) to reduce the numbers of states and transitions considered when solving the game; (b) incrementally adding defender’s actions to further reduce the number of transitions; (c) providing novel heuristics for lower bound initialization of the algorithm. Third, extensive experimental evaluations of the algorithms show that RITA significantly outperforms the baseline PG-HSVI algorithm on scalability while allowing for trade off in scalability and solution quality.

An Initial Study of Targeted Personality Models in the FlipIt Game

  • Autoři: Basak, A., Černý, J., Gutierrez, M., Curtis, S., Kamhoua, C., Jones, D., doc. Mgr. Branislav Bošanský, Ph.D., Kiekintveld, C.
  • Publikace: Decision and Game Theory for Security. Basel: Springer, 2018. p. 623-636. ISBN 978-3-030-01553-4.
  • Rok: 2018
  • DOI: 10.1007/978-3-030-01554-1_36
  • Odkaz: https://doi.org/10.1007/978-3-030-01554-1_36
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Game theory typically assumes rational behavior for solution concepts such as Nash equilibrium. However, this assumption is often violated when human agents are interacting in real-world scenarios, such as cybersecurity. There are different human factors that drive human decision making, and these also vary significantly across individuals leading to substantial individual differences in behavior. Predicting these differences in behavior can help a defender to predict actions of different attacker types to provide better defender strategy tailored towards different attacker types. We conducted an initial study of this idea using a behavioral version of the FlipIt game. We show that there are identifiable differences in behavior among different groups (e.g., individuals with different Dark Triad personality scores), but our initial attempts at capturing these differences using simple known behavioral models does not lead to significantly improved defender strategies. This suggests that richer behavioral models are needed to effectively predict and target strategies in these more complex cybersecurity game.

Approximating Maxmin Strategies in Imperfect Recall Games Using A-loss Recall Property

  • DOI: 10.1016/j.ijar.2017.11.010
  • Odkaz: https://doi.org/10.1016/j.ijar.2017.11.010
  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    Extensive-form games with imperfect recall are an important model of dynamic games where the players are allowed to forget previously known information. Often, imperfect recall games result from an abstraction algorithm that simplifies a large game with perfect recall. Solving imperfect recall games is known to be a hard problem, and thus it is useful to search for a subclass of imperfect recall games which offers sufficient memory savings while being efficiently solvable. The abstraction process can then be guided to result in a game from this class. We focus on a subclass of imperfect recall games called A-loss recall games. First, we provide a complete picture of the complexity of solving imperfect recall and A-loss recall games. We show that the A-loss recall property allows us to compute a best response in polynomial time (computing a best response is NP-hard in imperfect recall games). This allows us to create a practical algorithm for approximating maxmin strategies in two-player games where the maximizing player has imperfect recall and the minimizing player has A-loss recall. This algorithm is capable of solving some games with up to 5⋅109 states in approximately 1 hour. Finally, we demonstrate that the use of imperfect recall abstraction can reduce the size of the strategy representation to as low as 0.03% of the size of the strategy representation in the original perfect recall game without sacrificing the quality of the maxmin strategy obtained by solving this abstraction.

Goal-HSVI: Heuristic Search Value Iteration for Goal POMDPs

  • Autoři: Ing. Karel Horák, Ph.D., doc. Mgr. Branislav Bošanský, Ph.D., Chatterjee, K.
  • Publikace: Proceedings of the International Joint Conferences on Artifical Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2018. p. 4764-4770. ISSN 1045-0823. ISBN 978-0-9992411-2-7.
  • Rok: 2018
  • DOI: 10.24963/ijcai.2018/662
  • Odkaz: https://doi.org/10.24963/ijcai.2018/662
  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    Partially observable Markov decision processes (POMDPs) are the standard models for planning under uncertainty with both finite and infinite horizon. Besides the well-known discounted-sum objective, indefinite-horizon objective (aka Goal-POMDPs) is another classical objective for POMDPs. In this case, given a set of target states and a positive cost for each transition, the optimization objective is to minimize the expected total cost until a target state is reached. In the literature, RTDP-Bel or heuristic search value iteration (HSVI) have been used for solving Goal-POMDPs. Neither of these algorithms has theoretical convergence guarantees, and HSVI may even fail to terminate its trials. We give the following contributions: (1) We discuss the challenges introduced in Goal-POMDPs and illustrate how they prevent the original HSVI from converging. (2) We present a novel algorithm inspired by HSVI, termed Goal-HSVI, and show that our algorithm has convergence guarantees. (3) We show that Goal-HSVI outperforms RTDP-Bel on a set of well-known examples.

Incremental Strategy Generation for Stackelberg Equilibria in Extensive-Form Games

  • Autoři: Černý, J., doc. Mgr. Branislav Bošanský, Ph.D., Kiekintveld, C.
  • Publikace: Proceedings of the 2018 ACM Conference on Economics and Computation. New York: ACM, 2018. p. 151-168. ISBN 978-1-4503-5829-3.
  • Rok: 2018
  • DOI: 10.1145/3219166.3219219
  • Odkaz: https://doi.org/10.1145/3219166.3219219
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Dynamic interaction appears in many real-world scenarios where players are able to observe (perhaps imperfectly) the actions of another player and react accordingly. We consider the baseline representation of dynamic games - the extensive form - and focus on computing Stackelberg equilibrium (SE), where the leader commits to a strategy to which the follower plays a best response. For one-shot games (e.g., security games), strategy-generation (SG) algorithms offer dramatic speed-up by incrementally expanding the strategy spaces. However, a direct application of SG to extensive-form games (EFGs) does not bring a similar speed-up since it typically results in a nearly-complete strategy space. Our contributions are twofold: (1) for the first time we introduce an algorithm that allows us to incrementally expand the strategy space to find a SE in EFGs; (2) we introduce a heuristic variant of the algorithm that is theoretically incomplete, but in practice allows us to find exact (or close-to optimal) Stackelberg equilibrium by constructing a significantly smaller strategy space. Our experimental evaluation confirms that we are able to compute SE by considering only a fraction of the strategy space that often leads to a significant speed-up in computation times.

An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games

  • DOI: 10.24963/ijcai.2017/130
  • Odkaz: https://doi.org/10.24963/ijcai.2017/130
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    We solve large two-player zero-sum extensive-form games with perfect recall. We propose a new algorithm based on fictitious play that significantly reduces memory requirements for storing average strategies. The key feature is exploiting imperfect recall abstractions while preserving the convergence rate and guarantees of fictitious play applied directly to the perfect recall game. The algorithm creates a coarse imperfect recall abstraction of the perfect recall game and automatically refines its information set structure only where the imperfect recall might cause problems. Experimental evaluation shows that our novel algorithm is able to solve a simplified poker game with 7.10^5 information sets using an abstracted game with only 1.8% of information sets of the original game. Additional experiments on poker and randomly generated games suggest that the relative size of the abstraction decreases as the size of the solved games increases.

Combining Incremental Strategy Generation and Branch and Bound Search for Computing Maxmin Strategies in Imperfect Recall Games

  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Extensive-form games with imperfect recall are an important model of dynamic games where the players are allowed to forget previously known information. Often, imperfect recall games are the result of an abstraction algorithm that simplifies a large game with perfect recall. Unfortunately, solving an imperfect recall game has fundamental problems since a Nash equilibrium does not have to exist. Alternatively, we can seek maxmin strategies that guarantee an expected outcome. The only existing algorithm computing maxmin strategies in two-player imperfect recall games without absentmindedness, however, requires approximating a bilinear mathematical program that is proportional to the size of the whole game and thus has a limited scalability. We propose a novel algorithm for computing maxmin strategies in this class of games that combines this approximate algorithm with an incremental strategy-generation technique designed previously for extensive-form games with perfect recall. Experimental evaluation shows that the novel algorithm builds only a fraction of the game tree and improves the scalability by several orders of magnitude. Finally, we demonstrate that our algorithm can solve an abstracted variant of a large game faster compared to the algorithms operating on the unabstracted perfect-recall variant.

Combining Incremental Strategy Generation and Branch and Bound Search for Computing Maxmin Strategies in Imperfect Recall Games

  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Extensive-form games with imperfect recall are an important model of dynamic games where the players are allowed to forget previously known information. Often, imperfect recall games are the result of an abstraction algorithm that simplifies a large game with perfect recall. Unfortunately, solving an imperfect recall game has fundamental problems since a Nash equilibrium does not have to exist. Alternatively, we can seek maxmin strategies that guarantee an expected outcome. The only existing algorithm computing maxmin strategies in two-player imperfect recall games without absentmindedness, however, requires approximating a bilinear mathematical program that is proportional to the size of the whole game and thus has a limited scalability. We propose a novel algorithm for computing maxmin strategies in this class of games that combines this approximate algorithm with an incremental strategy-generation technique designed previously for extensive-form games with perfect recall. Experimental evaluation shows that the novel algorithm builds only a fraction of the game tree and improves the scalability by several orders of magnitude. Finally, we demonstrate that our algorithm can solve an abstracted variant of a large game faster compared to the algorithms operating on the unabstracted perfect-recall variant.

Comparing Strategic Secrecy and Stackelberg Commitment in Security Games

  • Autoři: Qingyu, G., An, B., doc. Mgr. Branislav Bošanský, Ph.D., Kiekintveld, C.
  • Publikace: Proceedings of the International Joint Conference on Artificial Intelligence. Palo Alto, California: Association for the Advancement of Artificial Intelligence (AAAI), 2017. p. 3691-3699. ISSN 1045-0823. ISBN 978-0-9992411-0-3.
  • Rok: 2017
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    The Strong Stackelberg Equilibrium (SSE) has drawn extensive attention recently in several security domains. 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 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 efficiently solve PBEs for realistic-sized problems.

Computation of Stackelberg Equilibria of Finite Sequential Games

  • Autoři: doc. Mgr. Branislav Bošanský, Ph.D., Branzei, S., Hansen, K.A., Lund, T.B., Miltersen, P.B.
  • Publikace: ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION. 2017, 5(4), ISSN 2167-8375.
  • Rok: 2017
  • DOI: 10.1145/3133242
  • Odkaz: https://doi.org/10.1145/3133242
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    The Stackelberg equilibrium is a solution concept that describes optimal strategies to commit to: Player 1 (the leader) first commits to a strategy that is publicly announced, then Player 2 (the follower) plays a best response to the leader's choice. We study the problem of computing Stackelberg equilibria in finite sequential (i.e., extensive-form) games and provide new exact algorithms, approximation algorithms, and hardness results for finding equilibria for several classes of such two-player games.

Computing Maxmin Strategies in Extensive-form Zero-sum Games with Imperfect Recall

  • DOI: 10.5220/0006121200630074
  • Odkaz: https://doi.org/10.5220/0006121200630074
  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    Extensive-form games with imperfect recall are an important game-theoretic model that allows a compact representation of strategies in dynamic strategic interactions. Practical use of imperfect recall games is limited due to negative theoretical results: a Nash equilibrium does not have to exist, computing maxmin strategies is NP-hard, and they may require irrational numbers. We present the first algorithm for approximating maxmin strategies in two-player zero-sum imperfect recall games without absentmindedness. We modify the wellknown sequence-form linear program to model strategies in imperfect recall games resulting in a bilinear program and use a recent technique to approximate the bilinear terms. Our main algorithm is a branch-andbound search that provably reaches the desired approximation after an exponential number of steps in the size of the game. Experimental evaluation shows that the proposed algorithm can approximate maxmin strategies of randomly generated imperfect recall games of sizes beyond toy-problems within few minutes.

Dynamic Programming for One-sided Partially Observable Pursuit-evasion Games

  • DOI: 10.5220/0006190605030510
  • Odkaz: https://doi.org/10.5220/0006190605030510
  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    Pursuit-evasion scenarios appear widely in robotics, security domains, and many other real-world situations. We focus on two-player pursuit-evasion games with concurrent moves, infinite horizon, and discounted rewards. We assume that the players have partial observability, however, the evader has an advantage of knowing the current position of pursuer’s units. This setting is particularly interesting for security domains where a robust strategy, maximizing the utility in the worst-case scenario, is often desirable. We provide, to the best of our knowledge, the first algorithm that provably converges to the value of a partially observable pursuitevasion game with infinite horizon. Our algorithm extends well-known value iteration algorithm by exploiting that (1) value functions of our game depend only on the position of the pursuer and the belief he has about the position of the evader, and (2) that these functions are piecewise linear and convex in the belief space.

Heuristic Search Value Iteration for One-Sided Partially Observable Stochastic Games

  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    Security problems can be modeled as two-player partially observable stochastic games with one-sided partial observability and infinite horizon (one-sided POSGs). We seek for optimal strategies of player 1 that correspond to robust strategies against the worst-case opponent (player 2) that is assumed to have a perfect information about the game. We present a novel algorithm for approximately solving one-sided POSGs based on the heuristic search value iteration (HSVI) for POMDPs. Our results include (1) theoretical properties of one-sided POSGs and their value functions, (2) guarantees showing the convergence of our algorithm to optimal strategies, and (3) practical demonstration of applicability and scalability of our algorithm on three different domains: pursuit-evasion, patrolling, and search games.

Manipulating Adversary’s Belief: A Dynamic Game Approach to Deception by Design for Proactive Network Security

  • Autoři: Ing. Karel Horák, Ph.D., Zhu, Q., doc. Mgr. Branislav Bošanský, Ph.D.,
  • Publikace: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Düsseldorf: Springer VDI Verlag, 2017. p. 273-294. ISSN 0302-9743. ISBN 978-3-319-68710-0.
  • Rok: 2017
  • DOI: 10.1007/978-3-319-68711-7_15
  • Odkaz: https://doi.org/10.1007/978-3-319-68711-7_15
  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    Due to the sophisticated nature of current computer systems, traditional defense measures, such as firewalls, malware scanners, and intrusion detection/prevention systems, have been found inadequate. These technological systems suffer from the fact that a sophisticated attacker can study them, identify their weaknesses and thus get an advantage over the defender. To prevent this from happening a proactive cyber defense is a new defense mechanism in which we strategically engage the attacker by using cyber deception techniques, and we influence his actions by creating and reinforcing his view of the computer system. We apply the cyber deception techniques in the field of network security and study the impact of the deception on attacker’s beliefs using the quantitative framework of the game theory. We account for the sequential nature of an attack and investigate how attacker’s belief evolves and influences his actions. We show how the defender should manipulate this belief to prevent the attacker from achieving his goals and thus minimize the damage inflicted to the network. To design a successful defense based on cyber deception, it is crucial to employ strategic thinking and account explicitly for attacker’s belief that he is being exposed to deceptive attempts. By doing so, we can make the deception more believable from the perspective of the attacker.

Optimal Strategies for Detecting Data Exfiltration by Internal and External Attackers

  • DOI: 10.1007/978-3-319-68711-7_10
  • Odkaz: https://doi.org/10.1007/978-3-319-68711-7_10
  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    We study the problem of detecting data exfiltration in computer networks. We focus on the performance of optimal defense strategies with respect to an attacker’s knowledge about typical network behavior and his ability to influence the standard traffic. Internal attackers know the typical upload behavior of the compromised host and may be able to discontinue standard uploads in favor of the exfiltration. External attackers do not immediately know the behavior of the compromised host, but they can learn it from observations.We model the problem as a sequential game of imperfect information, where the network administrator selects the thresholds for the detector, while the attacker chooses how much data to exfiltrate in each time step. We present novel algorithms for approximating the optimal defense strategies in the form of Stackelberg equilibria. We analyze the scalability of the algorithms and efficiency of the produced strategies in a case study based on real-world uploads of almost six thousand users to Google Drive. We show that with the computed defense strategies, the attacker exfiltrates 2–3 times less data than with simple heuristics; randomized defense strategies are up to 30% more effective than deterministic ones, and substantially more effective defense strategies are possible if the defense is customized for groups of hosts with similar behavior.

Towards Solving Imperfect Recall Games

  • Autoři: Čermák, J., doc. Mgr. Branislav Bošanský, Ph.D.,
  • Publikace: Proceedings of the 31th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2017. ISSN 1548-8403. ISBN 978-1-5108-5507-6.
  • Rok: 2017
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Imperfect recall games represent dynamic interactions where players can forget previously known information, such as the exact history of played actions. Opposed to perfect recall games, where the players remember all information, imperfect recall games allow a concise representation of strategies. However, most of the existing algorithmic results are negative for imperfect recall games and many theoretical and computational results do not translate from perfect recall games. The goal of this paper is to (1) summarize the existing results regarding imperfect recall games and (2) extend these results to a restricted subclass of imperfect recall games termed A-loss recall games. Finally, (3) we emphasize the impact of these theoretical results on algorithms that compute (approximately) optimal strategies in extensive-form games and show that they cannot be easily extended to imperfect recall games

A Point-Based Approximate Algorithm for One-Side Partially Observable Pursuit-Evasion Games

  • DOI: 10.1007/978-3-319-47413-7_25
  • Odkaz: https://doi.org/10.1007/978-3-319-47413-7_25
  • Pracoviště: Katedra počítačů, Centrum umělé inteligence
  • Anotace:
    Pursuit-evasion games model many security problems where an evader is trying to escape a group of pursuing units. We consider a variant with partial observability and simultaneous moves of all units, and assume the worst-case setup, where the evader knows the location of pursuer’s units, but the pursuer does not know the location of the evader. Recent work has shown that the solution of such games is compactly representable as a collection of finite-dimensional value functions. We extend this result and propose the first practical algorithm for approximating optimal policies in pursuit-evasion games with one-sided partial observability. Our approach extends the point-based updates that exist for POMDPs to one-sided partially observable stochastic games. The experimental evaluation on multiple graphs shows significant improvementsover approximate algorithms that operate on finite game trees.

Algorithms for computing strategies in two-player simultaneous move games

  • DOI: 10.1016/j.artint.2016.03.005
  • Odkaz: https://doi.org/10.1016/j.artint.2016.03.005
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    Simultaneous move games model discrete, multistage interactions where at each stage players simultaneously choose their actions. At each stage, a player does not know what action the other player will take, but otherwise knows the full state of the game. This formalism has been used to express games in general game playing and can also model many discrete approximations of real-world scenarios. In this paper, we describe both novel and existing algorithms that compute strategies for the class of two-player zero-sum simultaneous move games. The algorithms include exact backward induction methods with efficient pruning, as well as Monte Carlo sampling algorithms. We evaluate the algorithms in two different settings: the offline case, where computational resources are abundant and closely approximating the optimal strategy is a priority, and the online search case, where computational resources are limited and acting quickly is necessary. We perform a thorough experimental evaluation on six substantially different games for both settings. For the exact algorithms, the results show that our pruning techniques for backward induction dramatically improve the computation time required by the previous exact algorithms. For the sampling algorithms, the results provide unique insights into their performance and identify favorable settings and domains for different sampling algorithms. (C) 2016 Elsevier B.V. All rights reserved.

Case Studies of Network Defense with Attack Graph Games

  • DOI: 10.1109/MIS.2016.74
  • Odkaz: https://doi.org/10.1109/MIS.2016.74
  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    The increaing complexity of securing modern computer networks makes decision support systems an important tool for administrators. A challenge many existing tools fail to address is that attackers react strategically to new security measures, adapting their behaviors in response. Game theory provides a methodology for making decisions that takes into account these reactions, rather than assuming static attackers. The authors present an overview of how game theory can be used to inform one type of security decision: how to optimally place honeypots in a network. They demonstrate this approach on a realistic case study and present initial validation results based on a study comparing their approach with human decision makers.

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

  • Pracoviště: Centrum umělé inteligence
  • Anotace:
    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.

Approximate Solutions for Attack Graph Games with Imperfect Information

  • DOI: 10.1007/978-3-319-25594-1_13
  • Odkaz: https://doi.org/10.1007/978-3-319-25594-1_13
  • Pracoviště: Katedra počítačů
  • Anotace:
    We study the problem of network security hardening, in which a network administrator decides what security measures to use to best improve the security of the network. Specifically, we focus on deploying decoy services or hosts called honeypots. We model the problem as a general-sum extensive-form game with imperfect information and seek a solution in the form of Stackelberg Equilibrium. The defender seeks the optimal randomized honeypot deployment in a specific computer network, while the attacker chooses the best response as a contingency attack policy from a library of possible attacks compactly represented by attack graphs. Computing an exact Stackelberg Equilibrium using standard mixed-integer linear programming has a limited scalability in this game. We propose a set of approximate solution methods and analyze the trade-off between the computation time and the quality of the strategies calculated.

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

  • Autoři: doc. Mgr. Branislav Bošanský, Ph.D., Jiang, AX, Tambe, M., Kiekintveld, C D
  • Publikace: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference. Menlo Park: AAAI Press, 2015. p. 812-818. ISSN 2159-5399. ISBN 978-1-57735-698-1.
  • Rok: 2015
  • Pracoviště: Katedra počítačů
  • Anotace:
    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

Computation of Stackelberg Equilibria of Finite Sequential Games

  • Autoři: doc. Mgr. Branislav Bošanský, Ph.D., Branzei, S., Hansen, KA, Miltersen, PB, Sorensen, TB
  • Publikace: Web and Internet Economics. Berlin: Springer, 2015. pp. 201-215. Lecture Notes in Computer Science. ISSN 0302-9743. ISBN 978-3-662-48994-9.
  • Rok: 2015
  • DOI: 10.1007/978-3-662-48995-6_15
  • Odkaz: https://doi.org/10.1007/978-3-662-48995-6_15
  • Pracoviště: Katedra počítačů
  • Anotace:
    The Stackelberg equilibrium is a solution concept that describes optimal strategies to commit to: Player 1 (the leader) first commits to a strategy that is publicly announced, then Player 2 (the follower) plays a best response to the leader’s choice. We study Stackelberg equilibria in finite sequential (i.e., extensive-form) games and provide new exact algorithms, approximate algorithms, and hardness results for finding equilibria for several classes of such two-player games.

Game-Theoretic Algorithms for Optimal Network Security Hardening Using Attack Graphs

  • Pracoviště: Katedra počítačů
  • Anotace:
    In network security hardening a network administrator may need to use limited resources (such as honeypots) to harden a network against possible attacks. Attack graphs are a common formal model used to represent possible attacks. However, most existing works on attack graphs do not consider the reactions of attackers to different defender strategies. We introduce a game-theoretic model of the joint problem where attacker’s strategies are represented using attack graphs, and defender’s strategies are represented as modifications of the attack graph. The attack graphs we use allow for sequential attack actions with associated costs and probabilities of success/failure. We present an algorithm for an computing attack policy that maximizes attacker’s expected reward and empirical results demonstrating our methods on a case study network.

Optimal Network Security Hardening Using Attack Graph Games

  • Pracoviště: Katedra počítačů
  • Anotace:
    Preventing attacks in a computer network is the core problem in network security. We introduce a new game-theoretic model of the interaction between a network administrator who uses limited resource to harden a network and an attacker who follows a multi-stage plan to attack the network. The possible plans of the attacker are compactly represented using attack graphs, while the defender adds fake targets (honeypots) to the network to deceive the attacker. The compact representation of the attacker’s strategies presents a computational challenge and finding the best response of the attacker is NP-hard. We present a solution method that first translates an attack graph into an MDP and solves it using policy search with a set of pruning techniques. We present an empirical evaluation of the model and solution algorithms, evaluating scalability, the types of solutions that are generated for realistic cases, and sensitivity analysis.

Sequence-Form Algorithm for Computing Stackelberg Equilibria in Extensive-Form Games

  • Autoři: doc. Mgr. Branislav Bošanský, Ph.D., Čermák, J.
  • Publikace: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference. Menlo Park: AAAI Press, 2015. p. 805-811. ISSN 2159-5399. ISBN 978-1-57735-698-1.
  • Rok: 2015
  • Pracoviště: Katedra počítačů
  • Anotace:
    Stackelberg equilibrium is a solution concept prescribing for a player an optimal strategy to commit to, assuming the opponent knows this commitment and plays the best response. Although this solution concept is a cornerstone of many security applications, the existing works typically do not consider situations where the players can observe and react to the actions of the opponent during the course of the game. We extend the existing algorithmic work to extensive-form games and introduce novel algorithm for computing Stackelberg equilibria that exploits the compact sequence-form representation of strategies. Our algorithm reduces the size of the linear programs from exponential in the baseline approach to linear in the size of the game tree. Experimental evaluation on randomly generated games and a security-inspired search game demonstrates significant improvement in the scalability compared to the baseline approach.

An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information

  • Pracoviště: Katedra počítačů
  • Anotace:
    Developing scalable solution algorithms is one of the central problems in computational game theory. We present an iterative algorithm for computing an exact Nash equilibrium for two-player zero-sum extensive-form games with imperfect information. Our approach combines two key elements: (1) the compact sequence-form representation of extensive-form games and (2) the algorithmic framework of double-oracle methods. The main idea of our algorithm is to restrict the game by allowing the players to play only selected sequences of available actions. After solving the restricted game, new sequences are added by finding best responses to the current solution using fast algorithms. We experimentally evaluate our algorithm on a set of games inspired by patrolling scenarios, board, and card games. The results show significant runtime improvements in games admitting an equilibrium with small support, and substantial improvement in memory use even on games with large support. The improvement in memory use is particularly important because it allows our algorithm to solve much larger game instances than existing linear programming methods. Our main contributions include (1) a generic sequence-form double-oracle algorithm for solving zero-sum extensive-form games; (2) fast methods for maintaining a valid restricted game model when adding new sequences; (3) a search algorithm and pruning methods for computing best-response sequences; (4) theoretical guarantees about the convergence of the algorithm to a Nash equilibrium; (5) experimental analysis of our algorithm on several games, including an approximate version of the algorithm.

Practical Performance of Refinements of Nash Equilibria in Extensive-Form Zero-Sum Games

  • DOI: 10.3233/978-1-61499-419-0-201
  • Odkaz: https://doi.org/10.3233/978-1-61499-419-0-201
  • Pracoviště: Katedra kybernetiky, Katedra počítačů
  • Anotace:
    Nash equilibrium (NE) is the best known solution concept used in game theory. It is known that NE is particularly weak even in zero-sum extensive-form games since it can prescribe irrational actions to play that do not exploit mistakes made by an imperfect opponent. These issues are addressed by a number of refinements of NE that strengthen the requirements for equilibrium strategies. However, a thorough experimental analysis of practical performance of the Nash equilibria refinement strategies is, to the best of our knowledge, missing. This paper aims to fill this void and provides the first broader experimental comparison of the quality of refined Nash strategies in zero-sum extensive-form games. The experimental results suggest that (1) there is a significant difference between the best and the worst NE strategy against imperfect opponents, (2) the existing refinements outperform the worst NE strategy, (3) they typically perform close to the best possible NE strategy, and (4) the difference in performance of all compared refinements is very small.

Solving adversarial patrolling games with bounded error

  • Autoři: Abaffy, M., Brázdil, T., Řehák, V., doc. Mgr. Branislav Bošanský, Ph.D., Kučera, A., Krčál, J.
  • Publikace: Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems. County of Richland: IFAAMAS, 2014. p. 1617-1618. ISBN 978-1-4503-2738-1.
  • Rok: 2014
  • Pracoviště: Katedra počítačů
  • Anotace:
    Patrolling games are partially observable games played by two players, the defender and the attacker. The defender aims for detecting intrusions into vulnerable targets by following randomized routes among them, the attacker strives to maximize the probability of a successful (undetected) intrusion. We show how to translate patrolling games into turn-based perfect information stochastic games with safety objectives so that optimal strategies in the perfect information games can be transferred back to patrolling games. We design, to the best of our knowledge, the first algorithm which can compute an ε-optimal strategy for the defender among all (history-dependent) strategies.

Convergence of Monte Carlo Tree Search in Simultaneous Move Games

  • Pracoviště: Katedra počítačů
  • Anotace:
    We study Monte Carlo tree search (MCTS) in zero-sum extensive-form games with perfect information and simultaneous moves. We present a general template of MCTS algorithms for these games, which can be instantiated by various selection methods. We formally prove that if a selection method is epsilon-Hannan consistent in a matrix game and satisfies additional requirements on exploration, then the MCTS algorithm eventually converges to an approximate Nash equilibrium (NE) of the extensive-form game. We empirically evaluate this claim using regret matching and Exp3 as the selection methods on randomly generated games and empirically selected worst case games. We confirm the formal result and show that additional MCTS variants also converge to approximate NE on the evaluated games.

Double-Oracle Algorithm for Computing an Exact Nash Equilibrium in Zero-Sum Extensive-Form Games

  • Pracoviště: Katedra počítačů
  • Anotace:
    We investigate an iterative algorithm for computing an exact Nash equilibrium in two-player zero-sum extensive-form games with imperfect information. The approach uses the sequence-form representation of extensive-form games and the double-oracle algorithmic framework. The main idea is to restrict the game by allowing the players to play only some of the sequences of available actions, then iteratively solve this restricted game, and exploit fast best-response algorithms to add additional sequences to the restricted game for the next iteration. In this paper we (1) extend the sequence-form double-oracle method to be applicable on non-deterministic extensive-form games, (2) present more efficient methods for maintaining valid restricted game and computing best-response sequences, and finally we (3) provide theoretical guarantees of the convergence of the algorithm to a Nash equilibrium. We experimentally evaluate our algorithm on two types of games: a search game on a graph and simplified variants of Poker. The results show significant running-time improvements compared to the previous variant of the double-oracle algorithm, and demonstrate the ability to find an exact solution of much larger games compared to solving full linear program for the complete game.

Knowledge-Based Support of Medical Work in Home Care

  • Autoři: Lhotská, L., Doležal, J., doc. Mgr. Branislav Bošanský, Ph.D.,
  • Publikace: Handbook of Research on ICTs and Management Systems for Improving Efficiency in Healthcare and Social Care. Hershey, Pennsylvania: IGI Global, 2013. p. 786-804. ISBN 978-1-4666-3990-4.
  • Rok: 2013
  • DOI: 10.4018/978-1-4666-3990-4.ch041
  • Odkaz: https://doi.org/10.4018/978-1-4666-3990-4.ch041
  • Pracoviště: Katedra počítačů
  • Anotace:
    Healthcare applications involve complex structures of interacting processes and professionals that need to exchange information to provide the care services. In this kind of system, many different professional competencies, ethical and sensibility requirements, as well as legal frameworks coexist, and because of that, the information managed inside the system should not be freely accessed. On the contrary, it must be subject to very complex privacy restrictions. In the chapter, the authors describe a case study of a knowledge-based distributed system, the fundamental issues that must be considered in design of a distributed healthcare application. The K4CARE system is an example of an application to the medical domain of homecare assistance. Homecare involves professionals from different institutions (hospital, social workers, etc.) that must interact around any particular patient, and which used to be located in different physical places having their own and independent information systems.

Solving Extensive-Form Games with Double-Oracle Methods

  • Autoři: doc. Mgr. Branislav Bošanský, Ph.D.,
  • Publikace: AAMAS '13 Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems. County of Richland: IFAAMAS, 2013. pp. 1423-1424. AAMAS '13. ISBN 978-1-4503-1993-5.
  • Rok: 2013
  • Pracoviště: Katedra počítačů
  • Anotace:
    We investigate iterative algorithms for computing exact Nash equilibria in two-player zero-sum extensive-form games. The algorithms use an algorithmic framework of double-oracle methods. The main idea is to restrict the game by allowing the players to play only some of the strategies, and then iteratively solve this restricted game and exploit fast best-response algorithms to add additional strategies to the restricted game for the next iteration. The experimental evaluation on different games shows that the double-oracle methods often provide significant improvement in running-time, and can find exact solution of much larger games compared to the existing approaches.

Using Double-Oracle Method and Serialized Alpha-Beta Search for Pruning in Simultaneous Move Games

  • Pracoviště: Katedra počítačů
  • Anotace:
    We focus on solving two-player zero-sum extensive-form games with perfect information and simultaneous moves. In these games, both players fully observe the current state of the game where they simultaneously make a move determining the next state of the game. We solve these games by a novel algorithm that relies on two components: (1) it iteratively solves the games that correspond to a single simultaneous move using a double-oracle method, and (2) it prunes the states of the game using bounds on the sub-game values obtained by the classical Alpha-Beta search on a serialized variant of the game. We experimentally evaluate our algorithm on the Goofspiel card game, a pursuit-evasion game, and randomly generated games. The results show that our novel algorithm typically provides significant running-time improvements and reduction in the number of evaluated nodes compared to the full search algorithm.

Anytime Algorithms for Multi-agent Visibility-based Pursuit-evasion Games

  • Pracoviště: Katedra počítačů
  • Anotace:
    We investigate algorithms for playing multi-agent visibility-based pursuit-evasion games. A team of pursuers attempts to maintain visibility contact with an evader who actively avoids tracking. We aim for applicability of the algorithms in real-world scenarios; hence, we impose hard constraints on the run-time of the algorithms and we evaluate them in a simulation model based on a real-world urban area. We compare Monte-Carlo tree search (MCTS) and iterative deepening minimax algorithms running on the information-set tree of the imperfect-information game. The experimental results demonstrate that both methods create comparable good strategies for the pursuer, while the later performs better in creating the evader's strategy.

Extending Security Games to Defenders with Constrained Mobility

  • Pracoviště: Katedra počítačů
  • Anotace:
    A number of real-world security scenarios can be cast as a problem of transiting an area guarded by a mobile patroller, where the transiting agent aims to choose its route so as to minimize the probability of encountering the patrolling agent, and vice versa. We model this problem as a two-player zero-sum game on a graph, termed the transit game. In contrast to the existing models of area transit, where one of the players is stationary, we assume both players are mobile. We also explicitly model the limited endurance of the patroller and the notion of a base to which the patroller has to repeatedly return. Noting the prohibitive size of the strategy spaces of both players, we develop single- and double-oracle based algorithms including a novel acceleration scheme, to obtain optimum route selection strategies for both players. We evaluate the developed approach on a range of transit game instances inspired by real-world security problems in the urban and naval security domains.

Game Theoretic Model of Strategic Honeypot Selection in Computer Networks

  • DOI: 10.1007/978-3-642-34266-0_12
  • Odkaz: https://doi.org/10.1007/978-3-642-34266-0_12
  • Pracoviště: Katedra počítačů
  • Anotace:
    A honeypot is a decoy computer system used in network security to waste the time and resources of attackers and to analyze their behaviors. While there has been significant research on how to design honeypot systems, less is known about how to use honeypots strategically in network defense. Based on formal deception games, we develop two game-theoretic models that provide insight into how valuable should honeypots look like to maximize the probability that a rational attacker will attack a honeypot. The first model captures a static situation and the second allows attackers to imperfectly probe some of the systems on the network to determine which ones are likely to be real systems (and not honeypots) before launching an attack. We formally analyze the properties of the optimal strategies in the games and provide linear programs for their computation. Finally, we present the optimal solutions for a set of instances of the games and evaluate their quality in comparison to several baselines.

Game-theoretic Approach to Adversarial Plan Recognition

  • DOI: 10.3233/978-1-61499-098-7-546
  • Odkaz: https://doi.org/10.3233/978-1-61499-098-7-546
  • Pracoviště: Katedra počítačů
  • Anotace:
    We argue that the problem of adversarial plan recognition, where the observed agent actively tries to avoid detection, should be modeled in the game theoretic framework. We define the problem as an imperfect-information extensive-form game between the observer and the observed agent. We propose a novel algorithm that approximates the optimal solution in the game using Monte-Carlo sampling. The experimental evaluation is performed on a syn- thetic domain inspired by a network security problem. The proposed method produces significantly better results than several simple baselines on a practically large domain.

Game-theoretic Resource Allocation for Malicious Packet Detection in Computer Networks

  • Pracoviště: Katedra počítačů
  • Anotace:
    We study the problem of optimal resource allocation for packet selection and inspection to detect potential threats in large computer networks with multiple valuable computers of differing importance. An attacker tries to harm these targets by sending malicious packets from multiple entry points of the network; the defender thus needs to optimally allocate his resources to maximize the probability of malicious packet detection under network latency constraints. We formulate the problem as a graph-based security game with multiple resources of heterogeneous capabilities and propose a mathematical program for finding optimal solutions. Due to the very limited scalability caused by the large attacker's strategy space and non-linearity of the program, we investigate solutions with approximated utility function and propose Grande, a novel polynomial approximate al- gorithm utilizing submodularity of the problem able to find solutions with a bounded error on problem of a realistic size.

Iterative Algorithm for Solving Two-player Zero-sum Extensive-form Games with Imperfect Information

  • Pracoviště: Katedra počítačů
  • Anotace:
    We develop and evaluate a new exact algorithm for finding Nash equilibria of two-player zero-sum extensive-form games with imperfect information. Our approach is based on the sequence-form representation of the game, and uses an algorithmic framework of double-oracle methods that have been used successfully in other classes of games. The algorithm uses an iterative decomposition, solving restricted games and exploiting fast best-response algorithms to add additional sequences to the game over time. We demonstrate our algorithm on a class of adversarial graph search games motivated by real world border patrolling scenarios. The results indicate that our framework is a promising way to scale up solutions for extensive-form games, reducing both memory and computation time requirements.

Strategy Representation Analysis for Patrolling Games

  • Pracoviště: Katedra počítačů
  • Anotace:
    This paper considers the problem of patrolling multiple targets in a Euclidean environment by a single patrolling unit. We use game-theoretic approach and model the problem as a two-player zero-sum game in the extensive form. Based on the existing work in the domain of patrolling we propose a novel mathematical non-linear program for finding strategies in a discretized problem, in which we introduce a general concept of internal states of the patroller. We experimentally evaluate game value for the patroller for various graphs and strategy representations. The results suggest that adding internal states for the patroller yields better results in comparison to adding choice nodes in the used discretization.

Tactical Operations of Multi-Robot Teams in Urban Warfare (Demonstration)

  • Pracoviště: Katedra počítačů
  • Anotace:
    With scaling of multi-robot teams deployed in military operations, there is a need to boost autonomy of individual, as well as team behaviors. We developed a feature-rich simulation testbed for experimental evaluation of multi-agent coordination mechanisms applicable in tactical military operations in urban warfare. In particular, we investigated and implemented four approaches including multi-agent mission planning and plan repair, reactive planning for teamwork, patrolling of mobile targets, and tracking of smart targets. Besides the live-system demonstrator, we aim to showcase a scenario engaging a human in a pursuit-evasion game against the algorithms we implemented.

AgentC: Agent-based System for Securing Maritime Transit (Demonstration)

  • Pracoviště: Katedra kybernetiky
  • Anotace:
    Recent rise in maritime piracy prompts the search for novel techniques for addressing the problem. We therefore developed AgentC, a prototype system that demonstrates how agent-based traffic management techniques can be used to improve the security of transit through piracy-affected areas. Combining agent-based modeling and simulation of maritime traffic and novel route planning and vessel scheduling techniques, the system shows the promising potential of agent-based methods for increasing maritime security.

Agentni simulaci proti somalskym piratum

  • Pracoviště: Katedra kybernetiky
  • Anotace:
    Výzkumníci z Katedry kybernetiky Fakulty elektrotechnické na ČVUT studují použitelnost metod umělé inteligence a agentních technologií při zajišťování bezpečnosti v námořní doméně. Předmětem výzkumu sponzorovaného americkým Úřadem pro námořní výzkum (ONR) je vytvoření podrobného multiagentního modelu chování pirátů v prostředí námořní dopravy a návrh algoritmů pro optimálně znáhodněné plánování bezpečného transitu Adenským zálivem.

Computing Time-Dependent Policies for Patrolling Games with Mobile Targets

  • Pracoviště: Katedra kybernetiky
  • Anotace:
    We study how a mobile defender should patrol an area to protect multiple valuable targets from being attacked by an attacker. In contrast to existing approaches we allow the targets to move through the area according to a priori known deterministic movement schedules. We represent the patrol area by a graph of arbitrary topology and do not put any restrictions on the movement schedules. We assume the attacker can observe the defender and has full knowledge of the strategy the defender employs. We construct a game-theoretic formulation and seek defender's optimal randomized strategy in a Stackelberg equilibrium of the game. We formulate the computation of the strategy as a mathematical program whose solution corresponds to an optimal time-dependent Markov policy for the defender.

Integration of Procedural Knowledge in Multi-Agent Systems in Medicine

  • Autoři: Lhotská, L., doc. Mgr. Branislav Bošanský, Ph.D., Doležal, J.
  • Publikace: Information Technology in Bio- and Medical Informatics. Heidelberg: Springer, 2011, pp. 82-95. LNCS. ISSN 0302-9743. ISBN 978-3-642-23207-7. Available from: http://www.springerlink.com/content/y17011337n358833/
  • Rok: 2011
  • DOI: 10.1007/978-3-642-23208-4_8
  • Odkaz: https://doi.org/10.1007/978-3-642-23208-4_8
  • Pracoviště: Katedra kybernetiky
  • Anotace:
    In this paper we present two developed multi-agent architectures. The first one models knowledge-based support of the eServices in the domain of home care, while the second one represents a general model that uses procedural knowledge in the form of organizational processes and formalized medical guidelines in a decision support system. We show that integration of both architectures is feasible and moreover, it can enhance functionality of the home care system.

Iterative Game-theoretic Route Selection for Hostile Area Transit and Patrolling

  • Pracoviště: Katedra kybernetiky
  • Anotace:
    A number of real-world security scenarios can be cast as a problem of transiting an area patrolled by a mobile adversary, where the transiting agent aims to choose its route so as to minimize the probability of encountering the patrolling agent, and vice versa. We model this problem as a two player zero-sum game on a graph, termed the transit game. In contrast to the existing models of area transit, where one of the players is stationary, we assume both players are mobile. We also explicitly model the limited endurance of the patroller and the notion of a base to which the patroller has to repeatedly return. Noting the prohibitive size of the strategy spaces of both players, we employ iterative oracle-based algorithms including a newly proposed accelerated scheme, to obtain optimum route selection strategies for both players. We evaluate the developed approach on a range of transit game instances inspired by real-world security problems in the urban and naval security domains.

Process-based Multi-agent Architecture in Home Care

  • Pracoviště: Katedra kybernetiky
  • Anotace:
    Utilization of procedural knowledge in the form of organizational processes and formalized medical guidelines can be useful in decision support systems (DSSs) in health care domain. The problem of using this form of knowledge arises when a multi-agent paradigm is to be applied in a DSS due to differences in specification of behavioural models of agents and process formalisms. In this work we continue in enhancing a novel process-based multi-agent architecture and demonstrate its integration into an existing DSS (K4care) focused on home care. We analysed available documentation of the complex system K4Care and identified possible mutual common functionalities of implemented multi-agent system with the new architecture. These were the entry points, using which we further enhanced the K4Care platform with respect to the process-based multi-agent architecture.

Towards Cooperation in Adversarial Search with Confidentiality

  • DOI: 10.1007/978-3-642-23181-0_24
  • Odkaz: https://doi.org/10.1007/978-3-642-23181-0_24
  • Pracoviště: Katedra kybernetiky
  • Anotace:
    We investigate the problem of cooperation of self-interested agents with respect to the confidentiality of their plans and without a presence of any third-party mediator. We base our approach on non-zero-sum n-player games in the extensive form focusing on two main goals: (1) the analysis of the maximal improvement of the utility value that an agent can gain by negotiation, and (2) the dependence of this improvement on the basic characteristics of the game -- the number of agents, size of the branching factor, and correlation of the utility functions. We provide theoretical definitions together with experimental results evaluated on games abstracting real-world scenarios.

Agent Subset Adversarial Search for Complex Non-cooperative Domains

  • DOI: 10.1109/ITW.2010.5593351
  • Odkaz: https://doi.org/10.1109/ITW.2010.5593351
  • Pracoviště: Katedra kybernetiky
  • Anotace:
    We investigate reduction of the complexity of a multi-agent adversarial search in the domain of n-player games. We describe a method that decomposes the game into a set of smaller overlapping sub-games, solves each sub-game separately, and then combines the results into a global solution. This way, the exponential dependence of the adversarial search complexity on the number of agents can be reduced to polynomial. Still, the proposed method performs well in the domains with sparse agents' interactions. The method can be used with a generic adversarial search algorithm. For the experimental evaluation, we implement it on top of an existing adversarial search algorithm designed for complex domains and we evaluate its performance on a game, which is a model of a humanitarian relief operation in conflict environment. The results show that the method often finds the same solutions as the complete search, but the search efficiency is significantly improved.

Goal-Based Game Tree Search for Complex Domains

  • DOI: 10.1007/978-3-642-11819-7_8
  • Odkaz: https://doi.org/10.1007/978-3-642-11819-7_8
  • Pracoviště: Katedra kybernetiky
  • Anotace:
    We present a novel approach to reducing adversarial search space by employing background knowledge represented in the form of higher-level goals that players tend to pursue in the game. The algorithm is derived from a simultaneous-move modification of the max n algorithm by limiting the search to those branches of the game tree that are consistent with pursuing player's goals. The algorithm has been tested on a real-world-based scenario modelled as a large-scale asymmetric game. The experimental results obtained indicate the ability of the goal-based heuristic to reduce the search space to a manageable level even in complex domains while maintaining the high quality of resulting strategies.

Transiting Areas Patrolled by a Mobile Adversary

  • DOI: 10.1109/ITW.2010.5593377
  • Odkaz: https://doi.org/10.1109/ITW.2010.5593377
  • Pracoviště: Katedra kybernetiky
  • Anotace:
    We study the problem of a mobile agent trying to cross an area patrolled by a mobile adversary. The transiting agent aims to choose its route so as to minimize the probability of hostile encounter; the patroller agent, controlling one or more patrol units, aims at the opposite. We model the problem as a two-player zero-sum game (termed transit game) and search for an optimum route selection strategy as a mixed Nash equilibrium of the game. In contrast to existing game-theoretic models of this kind, we explicitly consider the limited endurance of patrols and the notion of bases to which the patrols need to repeatedly return. Noting the prohibitive size of the transit game, we employ two techniques for reducing the complexity of finding Nash equilibria - a compact network-flow-based representation of transit routes and iterative single- and doubleoracle algorithms for incremental game matrix construction

Adversarial Search with Procedural Knowledge Heuristic

  • Pracoviště: Katedra kybernetiky
  • Anotace:
    We introduce an adversarial planning algorithm based on game tree search, which is applicable in large-scale multiplayer domains. In order to tackle the scalability issues of game tree search, the algorithm utilizes procedural knowledge capturing how individual players tend to achieve their goals in the domain; the information is used to limit the search only to the part of the game tree that is consistent with pursuing players' goals. We impose no specific requirements on the format of the procedural knowledge; any programming language or agent specification paradigm can be employed. We evaluate the algorithm both theoretically and empirically, confirming that the proposed approach can lead to a substantial search reduction with only a minor negative impact on the quality of produced solutions.

Goal-Based Adversarial Search - Searching Game Trees in Complex Domains using Goal-based Heuristic

  • Pracoviště: Katedra kybernetiky
  • Anotace:
    We present a novel approach to reducing adversarial search space by using background knowledge represented in the form of higher-level goals that players tend to pursue in the game. The algorithm is derived from a simultaneous-move modification of the maxn algorithm by only searching the branches of the game tree that are consistent with pursuing player's goals. The algorithm has been tested on a real-world-based scenario modelled as a large-scale asymmetric game. The experimental results obtained indicate the ability of the goal-based heuristic to reduce the search space to a manageable level even in complex domains while maintaining the high quality of resulting strategies.

Za stránku zodpovídá: Ing. Mgr. Radovan Suk