Security via Strategic Randomization

The ARMOR (Assistant for Randomized Monitoring Over Routes) project has been developing methods for creating randomized plans and processes, so that even if an attacker observes the plans over time, he/she cannot predict its progression or how it will unfold in the future, thus providing risk reduction while guaranteeing a certain level of protection quality. Our key research accomplishments have been developing efficient algorithms to address the problem of providing decision support to a patrolling or security service in an adversarial domain.  The idea is to create patrols that can achieve a high level of coverage or reward while taking into account the presence of an adversary.  We assume that the adversary can learn or observe the patrolling strategy and use this to its advantage.   We follow two different approaches depending on what is known about the adversary.  If there is no information about the adversary we use a Markov Decision Process (MDP) to represent patrols and identify randomized solutions that minimize the information available to the adversary. This leads to algorithms BRLP, for policy randomization of MDPs, and RDR, for Decentralized-Partially Observable MDPs.  Second, when there is partial information about the adversary we decide on efficient patrols by solving a Bayesian Stackelberg game.  Here, the leader decides first on a patrolling strategy and then an adversary, of possibly many adversary types, selects its best response for the given patrol. We provide an efficient MIP formulation to solve this NP-hard problem.   Our experimental results show the efficiency of these algorithms and illustrate how these techniques provide optimal and secure patrolling policies. The result of this research is embedded in the ARMOR system currently being applied at the Los Angeles International Airport. The ARMOR system, the result of our project, has been applied on a trial basis for randomizing checkpoints at the Los Angeles International Airport (LAX). This trial has been on-going since August 2007. Please see below for a checkpoint as recommended by ARMOR. We will soon be applying our system for randomizing deployment of K-9 units at LAX. In accomplishing this goal, we collaborated with the Los Angeles World Airport (LAWA) Police.  

SOW: