許可された経路から逸脱するための最適なセンサー欺瞞
Optimal Sensor Deception to Deviate from an Allowed Itinerary
エージェントがセンサー読み取り値を改ざんして、許可された経路をたどったと監視システムに誤認させ、最小コストで検知されずに逸脱する戦略を求める問題を定式化し、NP困難性を示し、整数線形計画法に基づく厳密解法を提案した。
著者: Hazhar Rahmani, Arash Ahadi, Jie Fu
分類: cs.RO
原文アブストラクト
In this work, we study a class of deception planning problems in which an agent aims to alter a security monitoring system's sensor readings so as to disguise its adversarial itinerary as an allowed itinerary in the environment. The adversarial itinerary set and allowed itinerary set are captured by regular languages. To deviate without being detected, we investigate whether there exists a strategy for the agent to alter the sensor readings, with a minimal cost, such that for any of those paths it takes, the system thinks the agent took a path within the allowed itinerary. Our formulation assumes an offline sensor alteration where the agent determines the sensor alteration strategy and implement it, and then carry out any path in its deviation itinerary. We prove that the problem of solving the optimal sensor alteration is NP-hard, by a reduction from the directed multi-cut problem. Further, we present an exact algorithm based on integer linear programming and demonstrate the correctness and the efficacy of the algorithm in case studies.
