Assessing Attack Vulnerability in Networks with Uncertainty - todo314 @ ウィキ

Assessing Attack Vulnerability in Networks with Uncertainty

• Thang N. Dinh, My T. Thai
• INFOCOM 2015

概要

• ネットワーク脆弱性を「期待対連結性」で評価したい
• 「k頂点消すと期待対連結性はどれ位下がるか？」という離散最適化問題
• 提案手法は、LPによる緩和＋交換ヒューリスティクス
• 期待対連結性のFPRASを提案

期待対連結性

• 脆弱性の色々な尺度
  • 最短経路長、代数的連結性、連結成分数・サイズ…はあまり良くない
  • 対連結性 (pairwise connectivity)は結構良いらしい
• 致命的頂点検出問題 (critical node detection; CND)
  • 普通のグラフで対連結性を最小化する問題
  • 近似手法いくつか
• 期待対連結性 (expected pairwise connectivity)
  • $$ \textsf{EPC}(\mathcal{G}) = \frac{1}{2} \sum_{\{u,v\} \in {V \choose 2}} \textsf{rel}_{\mathcal{G}}(u,v) $$
• 確率的致命的頂点検出問題 (probabilistic critical node detection; k-pCND)
  • k頂点取り除いてEPC(G)を最小化

提案手法

全体の流れ

• CNDはIPで記述できるらしい
• k-pCNDも確率的なIPとして考えられる
• MIP_F: 確率的な所を展開したIP
  • 変数・制約数が指数的になってショボンヌ
• MIP_R: 各ランダムグラフに関する制約を足し算でまとめる
  • MIP_Fの下限（最小化問題なので）にはなっている

1. MIP_Rを逐次的にk回解く
2. 交換ヒューリスティクスでEPCが下がるだけ更新する

EPCの近似計算

• 相対誤差で多項式時間近似したい

1. $$ \sum_{e} (辺確率) < \frac{2}{1}\epsilon n^{-2} $$
   • $$ \sum_{e} (辺確率) $$で十分良い近似
   • ここをMonte-Carloすると大変
2. それ以外; 辺確率和がそこそこ大きい
   • 頂点uを一様無作為標本
   • uから（ランダムグラフ上の）BFSして連結成分サイズを計算
   • ごにょごにょする

実験

• すごーい！
• kの値が分からん…

まとめ

• EPCの近似計算が少し面白いだけ
• これでINFOCOM的に評価されるんですかね…？
• 辺確率和が大きいときは、多分普通にやってもうまくいく

INFOCOM uncertain graphs 信頼性 脆弱性

2017/03/24