[B-16] インターネットアーキテクチャ

[B-16-10] A study on the robustness of random walks against hostile attacks

^○椎名智, 河村宇記, Nay Aung Han, 大崎博之 (関西学院大)

Keywords:ランダムウォーク、探索妨害

近年、未知のグラフにおける対象ノードの探索手法として、ランダムウォークが広く用いられている。
BFSやDFSのような決定的なアルゴリズムとは異なり、ランダムウォークに基づくノード探索は確率的なアルゴリズムであるため、探索を妨害する敵対的な攻撃にも比較的堅牢であると期待されている。%敵対的攻撃とは？？
しかし、最近では、ランダムウォークに対する敵対的な攻撃として、グラフのトポロジを動的に切り替えることによる
攻撃に対する特性の分析が行われつつある。\cite{wei2020adversarial}。この攻撃手法により、ランダムウォークの探索効率が大幅に低下する可能性があることが示唆されている。さらに、より現実的な攻撃に対して、ランダムウォークによるノード探索の堅牢性を明らかにする必要がある。%最近たまたま研究が行われただけ、 事例がない
そこで本稿では、ランダムウォークに基づくノード探索が、攻撃者によるリンクの張り替え攻撃に対してどの程度堅牢であるか
を定量的に評価する。
攻撃頻度やグラフのトポロジなどの要素を変化させながら、ランダムウォークの
初回到着時間に与える影響を実験により測定することで評価する。