Sybilアカウント検知手法のグラフ信号処理的解釈とその応用

オンラインソーシャルネットワーク (OSN) 上で偽のアカウント（Sybil アカウント）を大量に作成し，スパム・フィッシング URL の拡散や誤情報の流布による世論・市場の操作など様々な悪質な活動を行う Sybil 攻撃への対策は OSN セキュリティにおける重要な課題の一つである．この課題に対して，これまで様々な Sybil 検知手法が提案されてきてたが，それらの多くは各手法の性能やノイズ耐性に関して実験的に評価されているのみで，理論的な理解は不十分である．本研究では，既存のグラフベースの Sybil 検知手法はグラフ信号処理の枠組みで統一的に解釈できることを示す．これにより，各手法をフィルタカーネルの特性とシフト行列のスペクトルの 2 つの観点から理論的に比較・解析することが可能となる．さらに，解析に基づいて，我々は新たな Sybil 検知手法 (SybilHeat) を提案する．数値実験を通して，提案手法が高い性能及びノイズ耐性を発揮することを確かめた．本研究はグラフベースの Sybil 検知の理論的基礎を築き，Sybil 検知手法のより良い理解に繋がるものである．

Online social networks (OSNs) are threatened by Sybil attacks, in which attackers create a large number of fake accounts (also called Sybils) on OSNs and exploit them for various malicious activities. Therefore, Sybil detection is a fundamental task for OSN security. Although various methods have been proposed recently, theoretical understanding of them is still lacking. In this study, we show that existing graph-based Sybil detection methods can be interpreted in a unified framework of low-pass filtering. This framework enables us to theoretically compare and analyze each method from two perspectives: filter kernel properties and the spectrum of shift matrices. Furthermore, on the basis of the analysis, we propose a novel Sybil detection method called SybilHeat. Numerical experiments demonstrate that SybilHeat performs consistently well on graphs with various structural properties. This study lays a theoretical foundation for graph-based Sybil detection and leads to a better understanding of Sybil detection methods.