Critical Infrastructures Protection 

Critical Infrastructures (such as traffic systems, utility networks or communication infrastructures) represent a spinal cord of our everyday life. A possible failures to operate, caused either by an adversarial operation or by malfunction, may have huge negative impact. Protecting critical infrastructures is a highly asymmetric challenge, where preventing rather inexpensive attack require substantial effort on defence side. Often, the protective measures need to be compensated by lowering efficiency of the infrastructure or higher capital investment. We apply basic research in game theory, planning and adversarial reasoning to create abstract mathematical models of critical infrastructures typically represented by a graph structure or a set of spatially distributed targets. The models are then used to design optimal protection policies with limited defensive resources, which is typically computationally expensive and requires research of novel and scalable algorithms. As the level of abstraction can be often substantial, we employ large-scale multi-agent simulations to assess robustness of the proposed solution in rich environments which capture additional properties of the physical world.

Team

Ondřej Vaněk (contact person), Michal JakobViliam LisýBranislav BošanskýOndřej Hrstka 

Security of Maritime Traffic System

Around 90% of the world trade is transported by the international shipping industry. Any disruption to world shipping lanes thus has a significant impact on the world economy. The recent steep rise of maritime piracy represents one of the biggest threats to maritime shipping in decades.. Even though various countermeasures have been put into effect, no solution has been found yet, and the pirates grow stronger with each year. Only in 2010, 53 cargo-vessels were hijacked and 1181 crew members held hostage. The situation has been further deteriorating in 2011, with further steep increases in attack numbers, pirate brutality and ransom paid, which reached an all-time high in April 2011 with $13M paid for the release of the Greek owned oil tanker Irene SL.

Objectives and Approach

We explore how multi-agent systems can be used to improve maritime security, with particular focus on fighting maritime piracy. Our ultimate objective is to develop an integrated set of algorithmic techniques for maximizing transit security given the limited protection resources available. We achieve this by improving the coordination of the movement of merchant vessels and naval patrols, while taking into account the behavior of pirates. In order to evaluate the proposed techniques and to gain better insight into the structure and dynamics of maritime piracy, we also employ agent-based simulation and machine learning techniques to build dynamic models of maritime transit and to model and assess piracy risk. All methods are implemented within a modular software testbed featuring a scalable simulation engine, connectors to real-world data sources and powerful visualization front-end based on Google Earth.

Results

Vessel Behavior Models [1] -- We have developed a highly-detailed agent-based model of each vessel class. We designed a number of parametrized pirate behavioral models capturing realistic decision-making of a pirate. Maritime Simulation Platform [2, 3] -- We have developed a modular agent-based simulation platform providing base layer for the Maritime Transit simulation. Maritime Domain Data [4] -- We have assembled real-world data sources concerning key aspects of maritime transit, including AIS vessel trajectories, transit corridors, piracy incidents etc. Piracy Risk Modeling and Assessment -- We have applied data mining and machine learning on real-world pirate incidents data and derived models predicting piracy risk in different regions. Optimization of Group Transit Schedules [5] -- We have designed an optimized group transit scheme which results in shorter delay and higher speed of travel when transiting pirate waters (e.g. the Gulf of Aden). Risk-aware Route Planning -- We have developed a route planner able to weigh length of route planned with risk taken along the route. The planner is able to work with spatial risk models Risk-minimizing

Transit and Patrol Routing [6] -- We have applied game theory and security games in particular to optimize transit and patrol routes to decrease transit predictability and maximize deterrence of navy patrolling.

For addtional details, see the AgentC project website.

References

[1] Michal Jakob, Ondrej Vanek, Ondrej Hrstka and Michal Pechoucek: Agents vs. Pirates: Multi-Agent Simulation and Optimization to Fight Maritime Piracy. In 12th International Conference on Autonomous Agents and Multiagent Systems. 2012.
[2] Ondrej Vanek, Michal Jakob, Ondrej Hrstka and Michal Pechoucek: Using Multi-Agent Simulation to Improve the Security of Maritime Transit. Proceedings of 12th International Workshop on Multi-Agent-Based Simulation (MABS). 2011, p. 1-16.
[3] Ondrej Vanek, Michal Jakob, Ondrej Hrstka, and Michal Pechoucek: AgentC: Agent-based System for Securing Maritime Transit (Demonstration). In Proceedings of The 10th International Conference on Autonomous Agents and Multiagent Systems. 2011.
[4] Michal Jakob and Ondrej Vanek and Stepan Urban and Petr Benda and Michal Pechoucek: Adversarial Modeling and Reasoning in the Maritime Domain (Year 3 Report). 2011.
[5] Ondrej Hrstka and Ondrej Vanek: Optimizing Group Transit in the Gulf of Aden. In Proceedings of 15th International Student Conference on Electrical Engineering (POSTER). 2011.
[6] Ondrej Vanek, Branislav Bosansky, Michal Jakob, Viliam Lisy and Michal Pechoucek: Extending Security Games to Defenders with Constrained Mobility. In Proceedings of AAAI Spring Symposium GTSSH. 2012.

Security in Computer Networks

The problem of attacks on computer systems and corporate computer networks gets more pressing each year as the sophistication of the attacks increases together with the cost of their prevention. A number of intrusion detection and monitoring systems are being developed in order to increase the security of sensitive information, and many research works seek methods for optimizing the use of available security resources.

Additional cluster of activities can be found directly on the Cybersecurity website.

Objectives and Approach

We focus on network monitoring systems using deep packet inspection (DPI) techniques; specifically, on DPI on intermediate nodes inside a corporate network under a constraint of latency caused by such inspection. Game-theoretic methods are appropriate for modeling such problems and the optimal behavior of the involved parties can be found using the well-defined concept of an equilibrium computation. We build on previous work on game-theoretic approaches to network security and security games to present a novel approach to the challenges of malicious packet detection. In our approach, we follow the deep packet inspection scenario on an arbitrary network topology, and consider the following assumptions, that hold true in this domain: the attacker can access the computer network through multiple entry points, can attack multiple targets of differing importance in parallel, and the defender has limited resources that can be used for packet analysis.

Results

We propose a game-theoretic model of distributed DPI that can be characterized as a graph-based security game with multiple heterogeneous attacker and defender resources [1]. We give a mathematical program for finding the optimal solution for this problem formulated both as a non-zero sum and zero sum game. We describe a polynomial approximation algorithm that scales well with the increasing size of the network at the cost of a known bounded error.

References

[1] Ondrej Vanek, Zhengyu Yin, Manish Jain, Branislav Bosansky, Milind Tambe and Michal Pechoucek: Game-theoretic Resource Allocation for Malicious Packet Detection in Computer Networks. In Proceedings of AAMAS. 2012.

Protection of Critical Urban Buildings

Securing sensitive buildings (such as hospitals, banks, trade centers or government buildings) in urban networks, is a large and growing area of concern. The key challenge faced is to effectively schedule a limited number of resources to protect against an intelligent and adaptive attacker. The adversarial aspect poses significant challenges for the resource allocation problem. An intelligent attacker may observe the strategy of the defender, and then plan more effective attacks. Predictable scheduling of defender resources can be exploited by the attacker. Randomization has thus been used to keep attackers at bay by increasing the uncertainty they face.

The work is a joint effort with Teamcore group at the University of Southern California and Levine Science Research Center at the Duke University.

Objectives and Approach

Game theory offers a principled way of achieving effective randomization. It models the varying preferences of both the defender and the attacker, and allows us to solve for optimal strategies. We model an urban network security problem as a game with two players: the defender and the attacker. The pure strategies of the defender correspond to allocations of resources to edges in the network—for example, an allocation of police checkpoints to roads in the city. The pure strategies of the attacker correspond to paths from any source node to any target node -- for example, a path from a landing spot on the coast to the airport.The strategy space of the defender grows exponentially with the number of available resources, whereas the strategy space of the attacker grows exponentially with the size of the network. Our goal is to find a minimax strategy for the defender, that is, a strategy that minimizes the maximum expected utility that the attacker can obtain.

Results

We propose a double-oracle based approach that does not require the ex-ante enumeration of all pure strategies for either of the players [1]. We propose algorithms for both the defender’s and the attacker’s oracle problems, which are used iteratively to provide pure-strategy best responses for both players. We provide experimental results on real-city networks, specifically on graphs obtained from the GIS data [1, 2].

References

[1] Manish Jain and Dmytro Korzhyk and Ondrej Vanek and Vincent Conitzer and Milind Tambe and Michal Pechoucek: Double Oracle Algorithm for Zero-Sum Security Games on Graph. In Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2011.
[2] Ondrej Vanek, Branislav Bosansky, Michal Jakob, Viliam Lisy and Michal Pechoucek: Extending Security Games to Defenders with Constrained Mobility. In Proceedings of AAAI Spring Symposium GTSSH. 2012.

Protection of Energy Infrastructures

Energy infrastructure is a necessary physical structure needed for everyday operation of basically every unit of modern civilization. The security of the infrastructure is thus a vital part of its design, construction and operation. However, with growing interconnection of the world and steep development of technologies used for energy harvesting and transportation, energy infrastructures become increasingly complex and large, prohibiting effective securing using human forces and more importantly, human intellect. A modern approach, taking into account semi- or fully automatic autonomous units instead of the human labor and advanced computational methods instead of pure human reasoning, is needed.

Objectives and Approach

The objective of this line of research is to provide high-level control of UAVs, allowing the operator to communicate with a fleet of UAVs on a high level in terms of collection tasks and their results, with detailed allocation of the tasks to individuals UAVs and planning of their optimum trajectories performed automatically. We focus on (1) persistent surveillance, i.e., provide and maintain the information about the target area, keeping the average information age at minimum; and (2) tracking, i.e. provide uninterrupted information about the selected mobile ground target (or a group of targets). In both cases, the control algorithms have to respect UAV’s flight model constraints, sensory constraints and maintain collision-free trajectories [1].

Results

The results can be divided into three main contributions: mobile target tracking, mobile unit operation control and persistent area surveillance, which are described in detail in the Tactical Operations section.

References

[1] Ondrej Vanek and Michal Pechoucek: Modern Technologies for Securing Critical Energy Infrastructures. In Energy Security in the Wider Black Sea Area - National and Allied Approaches (to appear). NATO ARW, 2012.

Related Projects and Funding

  • AgentC project (Office of Naval Research project no. N00014-09-1-0537)
  • Tactical AgentFly
  • Kontakt II (Czech Ministry of Education, Youth and Sports under project number N00014-09-1-0537)
  • CAMNEP (European Research Office of the US Army under Contract No. N62558-07-C-0001 and Czech Ministry of Education grants 1M0567, 6840770038 [CTU] and 6383917201 [CESNET])