導入
導入
ピアツーピア (p2p) コンピューティング パラダイムには、他の従来のパラダイムに比べて多くの利点があります。たとえば、帯域幅、メモリ、データなどのリソースは、参加している他のすべてのユーザーが利用できます [1]。大まかに言えば、このパラダイムには構造化システムと非構造化システムの両方が含まれます。構造化オーバーレイ (Kademlia [2] や Chord [3] など) は、データとピア発見のための決定論的なメカニズムを提供しますが、非構造化オーバーレイ (Gnutella [4] など) は、ランダムなグラフでピアを編成し、ピアとデータに Pan Hung アルゴリズムを使用します。発見。一般的なピアツーピア システムのほとんどには「中央機関」が欠如しており、そのためこのパラダイムは障害攻撃に対して耐性があります。一方で、そのような集中権限の欠如は、多くの困難なセキュリティ問題につながります。ネットワーク化されたシステムを保護するために必要なセキュリティ サービスのほとんどは、1 つまたは別の集中権限を必要とするため、これらのサービスはピアツーピア システムでは使用できなくなります [5]。 ]。さらに悪いことに、これらのシステムの多くは完全に分散化されオープンな性質を持っているため、他の分散システムでは Sybil 攻撃を含む幅広い未知のセキュリティ脅威が発生しています [6]。
Sybil 攻撃は、ピアツーピア、有線および無線ネットワーク環境でよく知られています。その基本的な形式では、攻撃者を表すピアは可能な限り多くの ID を生成し、あたかもシステム内の複数のピアであるかのように動作します [6]。これは、システムの通常の動作を妨害するように設計されています。攻撃者が生成できる ID の数は、システム内の他のピアからの同時要求に応答し、生成された各 Sybil ID に対応するノードのルーティング情報を保存するために必要な帯域幅によって制限される攻撃者の能力にのみ依存します。 、および顕著な遅延なく同時リクエストを処理するために必要なコンピューティング リソース。ハードウェアの劇的な成長 (ストレージ容量や処理など) と、高い帯域幅レートを備えたブロードバンド インターネットの普及により、汎用ハードウェアで実行されている攻撃者であっても、大規模システムに重大な損害を与える可能性があります。
Sybil 攻撃は、ピアツーピア システムや、マイニング サービスに不可欠なその他の一般的な分散システムやパラダイムでよく見られるように、さまざまな状況で発生します。このような環境には、投票システム、評判システム、ルーティング、分散ストレージなどが含まれます。この攻撃が現実のシステムでどのように機能するかを説明するために、ピアツーピア オーバーレイ上に構築されたレコメンダー システムを想像してください [7]。このようなシステムでは、システムの目標は、他者からの推奨に基づいてユーザーが興味を持つ可能性のある情報を除外することです。この場合、複数の ID (Sybil) を偽造することで複数のユーザーになりすます攻撃者は、正規のユーザーが投票した正規のオブジェクトに簡単に投票できます。
現実的なレコメンダー システムでは、通常、オブジェクトに投票する正当なユーザーの数がシステムの全ユーザーの 1% を超えないことがほぼ保証されています [7]。このことを考慮すると、この攻撃は、高いインセンティブを提供するシステムを攻撃しようとするシステムの潜在的なユーザーである攻撃者にとって魅力的です。たとえば、オンライン市場の eBay は、顧客の声を使用して販売者、つまりそのプラットフォームを使用して商品を販売する販売者の評判を判断しているため、そのような販売者はより高い評判を得るために不正行為に手を染める誘惑にかられます。同様のことは、コンテンツがユーザーによって評価されるピアツーピアのファイル共有、評判に基づいた帯域幅の割り当てなど、他の多くの状況でも起こります。この場合、ユーザーが配布するコンテンツの品質を決定するために評判さえも使用されます。 。このようなすべての例には、ユーザーが不正行為をする動機があり、Sybil 攻撃はそのような攻撃者にとって目的を達成するための強力なツールであることが証明されています。
攻撃を防御するために、攻撃を防御したり、攻撃の影響を制限したりするために、いくつかの形式の防御または緩和が試みられてきました。このような攻撃は、集中防御と分散 (分散) 防御という 2 つの考え方に大別できます。集中防御 [6、8、9、10] では、中央機関がシステム内の各ユーザーの身元を確認する責任を負います。この防御は攻撃に対する防御にはある程度効果的ですが、システムに関して特定の前提を設けており、その一部はピアツーピア分散システムでは簡単に実装できません。まず、名前と操作説明が示すように、このようなシステムには集中管理された権限が必要ですが、セキュリティと機能上の理由から、多くの人にとって手頃な価格ではない可能性があります。さらに、このような集中管理機関が存在する場合でも、ユーザーの資格情報とデジタル ID を照合するには、システム内のユーザーに関連する資格情報が必要になります。多くの場合、そのような資格情報を取得することは非常に困難です。
一方、分散型防御には、[11、12、13、14、15、16、17、18、19、20、7、21、22、23] の作業が含まれますが、これらに限定されません。集中化された権限と、分散化されたピアツーピア システム向けに慎重に設計されています。このような防御は、攻撃者の可能性のあるユーザーを許可または拒否するために、システム内のユーザー間の協力を評価します。ユーザーの許可または拒否は、暗号化された分散防御の場合のようにユーザーに関連付けられた資格情報、またはソーシャル グラフを使用した Sybil 防御の場合のように正当な正直なユーザーのネットワーク属性に基づいて行われます。どちらのソリューションでも、防御の最終目標は、分散型の方法で中央当局の権限をシミュレートし、この権限を使用して魔女と正直なノードを検出することです。
防御の別の分類は、その防御がどのように機能するかに基づく場合があります。したがって、以前の研究では、Sybil の防御は、信頼できる証明書を使用した防御に分割できます。証明書は通常、正直なユーザーに対して生成され、信頼できる機関の公開鍵と照合して検証され、コストが発生します。ユーザーは何らかのコスト罰を受けるため、金額が制限されます。彼らが利用できるリソースを増やし、彼らの不正行為を減らし、ソーシャルネットワークベースのシビル防御を実現します。
最初のレベルのタイトル
2. シビル攻撃モデルと目標
このセクションでは、ほとんどの Sybil 攻撃の研究と防御で一般的に想定されている攻撃者モデルを詳しく説明し、攻撃者の目標と防御の目標をさらに調査します。
2.1 問題ステートメントとモデル
この問題は、システム内の 1 人のユーザーが、あたかも複数のコピーを持っているかのように振る舞うことを可能にするシステム内の能力を持っているとして定式化されます。このようなアプリケーションの正しさは、ピアの動作、ピアの数、システム内のコラボレーションに正直に参加する意欲に依存するため、これは多くのアプリケーションにとって問題となります。ただし、システム全体の動作を偏らせようとする単一の攻撃者のシビル ID では、そのようなシステムの目標を満たすことはできません。
攻撃者は、システムに注入できる偽の ID の数によって正式に特徴付けられます。攻撃者の動機は、偽の ID の数を最大化することです。攻撃者が生成してシステムに注入する ID の数の値と重要性は、アプリケーション自体に依存し、アプリケーションごとに異なります。たとえば、レコメンダー システムを攻撃するには、システム内の誠実なユーザーの 1% からの一致の合計を偽の ID として取得するだけで十分です。このシステム内で非常に人気のあるオブジェクトであっても、それに投票するのは誠実なノードのわずか 1% であることが一般に観察されているため、これは特に、システムの動作にバイアスをかけてシステム内の誠実なノードを上回る十分な強力な要因となります。つまり、システム内のオブジェクトに投票する正直なノードの正確な数よりも多くの単一 ID を持つことにより、Sybil 攻撃者は正直なノードの投票を追い抜くことができます。
一方、通信の匿名化に使用されるハイブリッド ネットワーク (Tor ネットワークなど) などの他のシステムでは、たとえ少量のシビル ID であっても、システム内の約束が大きく損なわれる可能性があります。理論的には、回路上の 2 つのノードの妥協は、このようなハイブリッド ネットワーク上の通信の送信者と受信者を識別するのに十分です [24]。一方、ネットワーク内の十分な数の ID が侵害されると、攻撃者は任意の数の回線を監視できるようになります。 ID の数自体が重要となる他のアプリケーションには、ファイル共有システムに対する攻撃 [25] などがあります。
図 1 P2P 重畳環境における Sybil 防御のいくつかの異なる方法
C/CA は集中認証局の略です
D/C は分散型暗号化プリミティブの略です
T/D は Trusted Device Authentication の略です
IP/T は IP 検出の略です
R/C はコスト サイクル ベースの検出の略です
S/G はソーシャル グラフ ベースの防御の略です
2.2 Sybil Defense の目的と成功基準
シビル防御の最終目標は、オーバーレイ ネットワーク内のシビル ID、またはそれらのシビル ID を生成できるピアを検出して隔離することによって、シビル攻撃を排除することです。ただし、この最終的な目標は常に達成できるわけではありません。なぜなら、集中型の信頼できる認証に基づくものを除くほとんどの防御には、その検出メカニズムに偽陽性と偽陰性の可能性があり、一部のシビル ノードは許容される一方で、他の誠実なノードを誤って報告する可能性があるためです。偽陽性レポートと偽陰性レポートで見てきたように。誤検知レポートは、Sybil ノードが正直なノードとしてレポートされる場合です。一方、偽陰性の正直なノードは Sybil ノードとして報告されます。防御メカニズムの現実的かつ実際に達成可能な目標は、偽陰性率を可能な限り減らすことです。
2.3 魔女の防御の深さ
最初のレベルのタイトル
3. 信頼できる証明書を使用する
Douceur [6] が Sybil 攻撃 [26] を排除する可能性を実証しているため、信頼できる認証方法はおそらく現在最も人気のある方法の 1 つです。このアプローチの従来の形式では、集中管理機関 (CA) を使用して、各ピアに割り当てられた ID を事前に割り当てられた資格情報と照合することで、これらの ID が一意で正当であることを確認します。これらの資格情報には、暗号化キー、通常はワンタイム パスワード ジェネレーター (OTP) によって生成される同期ランダム文字列、または中央機関によって発行されたデジタル証明書が含まれる場合があります。
上記の集中認証局の従来の形式は文献で明確に定義されていますが、分散証明書スキームは、Collaborate がオーバーレイに参加している他のピアを証明できるようにする分散マルチパーティ モデルに適した暗号化プリミティブを適用することによって定義されています。
3.1 集中認証局
一元化された信頼できる認証が、Sybil 攻撃を排除する唯一の方法である可能性があります [6]。 P2P の範囲では、資格情報の生成、配布、検証に集中認証局を使用する取り組みが行われてきました。たとえば、セクション 5 で説明したソーシャル グラフを使用し、公開鍵暗号を構成要素として利用する研究では、ユーザーの公開鍵の信頼性が、オフライン段階で集中管理機関を通じてユーザーに割り当てられた証明書を介して渡されると想定しています [19] ]。 CCA ベースの方法を利用する他のスキームの例には、[8]、[9]、[6]、および [10] の研究が含まれます。
3.2 暗号化プリミティブ
最近、暗号プリミティブに関するいくつかの研究が発表されました [11、12、13、14、15]。これらのプリミティブは、正規のピアのみをオーバーレイに参加させることで Sybil 攻撃の発生を困難にするために、ピアを検証するためのインフラストラクチャを提供することを目的としています。通常、これらの取り組みでは、分散型の方法で公開鍵インフラストラクチャ (PKI) を活用し、しきい値暗号化コンポーネント (秘密共有やしきい値署名など) を使用して、いわゆる正直なユーザー間のコラボレーションを確保し、その操作時間に重ねて結合を認証しようとします。ピア。興味深いことに、文献にある多くの非暗号化プロトコルは、正規のユーザーをカバーする認証システムの存在を前提としているため (SybilGuard やシビルリミット)。したがって、暗号化方法は、そのようなプロトコルが確実に正常に動作するように設計されています。
3.3 信頼できるデバイス
最初のレベルのタイトル
4. リソースのテスト
Sybil 攻撃を防御するために使用されるリソース テスト方法に加えて、基本的な考え方は、異なるユーザーと関連付けられている一連の ID に、ID の数に一致する十分なリソースがあるかどうかを確認することです。これらのリソースには、コンピューティング能力、帯域幅、メモリ、IP アドレス、さらには信頼できる資格情報が含まれる場合があります。 Douceur はリソース テストのアイデアが無効であることを証明しました [6] が、一部の研究者はそれが最小限の防御策であると考えています。つまり、この方法では攻撃を完全に排除することはできませんが、Sybil 攻撃が発生しにくくなります。
理論的には、そのような防御策のほとんどの計画は、防御策がない場合よりも魔女のアイデンティティの数をより少ない数に制限します。しかし、実際には、魔女の ID の数が少なくても、多くのシステムの使いやすさとセキュリティを脅かすのに十分です。たとえば、前述したように、Tor などの匿名システムの匿名性は、回線あたり 2 つのノードに依存します。さらに、オンライン評判システム内の 1% の偽の ID があれば、正規のノードに投票するのに十分です。
4.1 IPテスト
一般的なテスト シナリオには、ピアの場所を特定し、そのアクティビティと一致させるために、ピアの IP アドレスをテストすることが含まれます。特に、同じ特定の地理的領域から大量の活動が発生している場合、その活動の一部は魔女によるものである可能性があります。また、このような作業では、地理的に異なる地域の IP アドレスを取得することが前提となっていますが、これは決して安価ではありません。たとえば、Friedman et al. [29] は、特定の自律システム内の地理的位置に基づいてノードの IP アドレスがテストされる Tarzan を導入しています。同様の結果が Cornelli らによって [30] および [30] で示されています。
これらの作業の主な前提は、広い地理的領域では IP アドレスを取得することが困難であるということです。しかし、最近、感染したホストが単一の管理主体によって制御され、異なる自律システムに常駐する巨大なボットネット [31] の存在が示唆されており、この防御メカニズムが役に立たないことは確かです。
4.2 コストサイクル
いくつかの研究や実践では、Sybil 攻撃に対する防御として繰り返しコストがかかることが示唆されています。特に、計算パズル [16、32] とチューリング テスト (CAPTCHA [33] など) が解決策として提案されています。ただし、ボットネットを制御する攻撃者に対しては IP テストが機能しないのと同じように、これらのコストベースのスキームも機能しません。さらに、CAPTCHA のようなソリューションでは、Sybil 攻撃者が管理されたサイトで CAPTCHA テストを発行し、ユーザーが攻撃者が提供するサービスへのアクセスをテストする可能性があることが判明しています。
最初のレベルのタイトル
5. ソーシャルグラフに基づく防御
分散システムにおけるシビル攻撃の問題に対してこれまでに提案された解決策のほとんどには制限と欠点がありますが、ソーシャル ネットワーク ベースのシビル防御はこれらの問題をエレガントな方法で克服しようとします。まず、ソーシャル ネットワーク ベースの Sybil 防御は、ほとんどが Sybil 攻撃問題に対する分散型ソリューションです。これは、これらの設計が中央の権限を持たずに動作することを意味します。これは、ほとんどの分散システムにおける重要な特性です。この分散型の運用モデルは、これらの防御で最も一般的に使用される要素であるランダム ウォーク理論のおかげで簡単になります。第 2 に、これらの防御はソーシャル ノード間のソーシャル リンクの信頼を利用して、正直なノード間のコラボレーションを可能かつ簡単にします。第三に、これらの防御は、低コストでシビル攻撃に対して実用的かつ効果的であることがいくつかの研究で証明されており、現在では、分散ハッシュ テーブル (DHT)、反シビル投票、およびモバイルネットワークルーティング用。
設計の詳細や運用は大きく異なりますが、すべてのソーシャル ネットワーク ベースの Sybil 防御は、アルゴリズム特性 (高速混合特性など) と信頼という 2 つの共通の前提を共有しています。まず、これらの防御はソーシャル グラフの「急速な混合」特性に基づいています。非公式には、ソーシャル グラフの高速混合特性は、そのようなグラフ内の「正直な」ノードがうまくメッシュし、正直な領域にはまばらなカットが含まれないことを意味します。これは、正直なノードの 2 つの大きなサブセットをソーシャル ネットワークの一部に分割して接続する方法です。簡単にするために、ソーシャル グラフの高速混合の性質は、ソーシャル グラフ内の任意のノードからのランダム ウォークが、数ステップ後にグラフ上で定義されたマルコフ連鎖 (MC) の定常分布に厳密に近似することを意味します。数百万のノードからなるネットワークでは、このようなステップの推奨数は 10 ～ 15 ステップです。
この防御面での 2 番目の一般的な前提は信頼です。特に、これらの防御はすべて、たとえばノード間の対面の対話によって証明されるように、基礎となるソーシャル グラフにおける良好な信頼値を前提としています。この特定の仮定は、任意の数の攻撃者のソーシャル リンクを持つソーシャル ネットワークに侵入することの困難さを推測するために必要です。ソーシャル グラフ内の「正直な」ノードを正しく識別するための Sybil 防御の動作は、高速混合の仮定と、このアルゴリズム特性を使用した対応するスキームの構築によって保証されますが、Sybil ノードを識別する機能は、この仮定の下でのみ保証されます。攻撃者、または攻撃者の集合体が、それ自身とソーシャル グラフ内の他の誠実なノードとの間のいくつかのリンク (そのようなリンクは攻撃エッジと呼ばれます) を制御します。
以下に、広く引用され、懸念されるソーシャルネットワークベースのシビル防御方法をいくつか整理します。
5.1 Sybil Guard
Yu ら [19、20] による SybilGuard の設計は、信頼所有のソーシャル ネットワークの高速混合特性を使用して Sybil ノードを検出します。技術的には、SybilGuard は、初期化フェーズとオンライン検出フェーズの 2 つのフェーズで構成されます。初期化フェーズ中に、各ノードは、入力エッジと出力エッジのペアの隣接ノードのランダムな並べ替えとしてルーティング テーブルを構築します。次に、各ノードは長さ w = O(root n log n) のランダム ウォークを開始し、ランダムな並べ替えを使用して構築されたルーティング テーブルに従って、それを近隣ノードに伝播します。ランダム ウォーク パス上のすべてのノードは、ランダム ウォークの開始者の証人として登録され、ノードが疑わしいノードになったときにノードの証人として機能します。さらに、ランダム ウォークの遡及的な性質を利用して、ランダム ウォークの各開始者は「証人」のリスト (つまり、開始者の公開鍵を登録し、開始者のランダムなキーによって構築されたパス上に位置するノード) のリストを受け取ります。歩く）。
オンラインフェーズでは、検証者は容疑者が正直であるかどうかを次のように判断します。まず、容疑者はランダムなルートで「目撃者」のアドレスを検証者に送信します。したがって、バリデーターは、監視リストとそのバリデーターのルーティング リストを比較します。 2 つのセット間に交差がない場合 (非常に可能性の高いイベント)、ベリファイアは中止され、容疑者を拒否します。それ以外の場合、検証者は続行して、2 つのセット間の交差部分にあるノードを比較して、容疑者が公開鍵を使用して登録したかどうかを検証します。容疑者がクロスノードによって検証された場合、バリデーターは容疑者を受け入れるか、それを Sybil ノードとしてマークします。
5.2 Sybil Limit
単一の長いランダム ウォークを使用する SybilGuard とは異なり、SybilLimit は複数の短いランダム ウォークを提案します。さらに、SybilGuard (検証者と容疑者の公開鍵がソーシャル グラフのノードに登録される) とは異なり、SybilLimit [18] は、そのような鍵をソーシャル グラフのエッジに登録することを提案しています。初期化フェーズでは、各ノードは SybilGuard で説明されているのと同じ方法を使用してルーティング テーブルを構築し、毎回長さ w = O(log n) の r = O(root n) のランダム ウォークを実行します。ここで、O(log n)混合時間ソーシャル グラフの 10 ～ 15 個のソーシャル グラフです。理論的には、統計的分布に非常に近い分布からノードをサンプリングするのに十分であると想定されています。SybilGuard とは異なり、ランダム ルーティング パス上のすべてのノードは、ランダム ウォーク イニシエーターを登録するために使用されます。 r 個のランダム ウォークのそれぞれのエッジは、発信元ノードの公開鍵を登録するために使用されます (そのような各エッジはテールと呼ばれます)。特に、ウォークの発信元の公開鍵は、最後のエッジの下の最後のノードに登録されます。また、ランダム ルーティングの遡及的な性質を利用して、イニシエータ ノードの公開キーを登録する証人 (容疑者または検証者になる可能性がある) は、自分の ID をノードに返します。ソーシャル グラフ内の各ノードは、同じプロセスであり、登録されたランダム ウォークを開始する各ノードは、一連の証人 (または検証者) を収集します。
オンライン段階では、SybilLimit も SybilGuard と同じであり、容疑者は証人の識別子とアドレスを検証者ノードに送信し、検証者ノードは容疑者リスト内の証人を比較して矛盾を見つけようとします。検証者側の 2 つのセットで矛盾が発生した場合、検証者は両方のセットの共通の身元を持つ証人に容疑者の身元を確認するよう依頼し、このプロセスの結果に基づいて容疑者を受け入れるか拒否するかを決定します。 2 つの間に交差がない場合 (これは起こりそうにありません)、バリデーターは中止され、容疑者を攻撃者としてマークすることで拒否します。
SybilLimit について推論するために使用される証明可能な保証の主なコンポーネントは、Sybil Guard の場合と同じです。特に、ランダム ウォークの長さ w がソーシャル グラフの混合時間であると仮定すると、そのようなランダム ウォークで選択される最後のノードは定常分布に従います。
さらに、ランダム ウォークの最後のエッジは、ソーシャル グラフのエッジの中から「ほぼ」均一にランダムに選択されます。さらに、r = O(root n) と仮定し、隠れ定数 r0 (r = r0 × root n) が正しく選択されていれば、検証者と容疑者のサンプリングされたエッジ間の交差が圧倒的な確率で存在します。著者らはこの条件を「交差」条件と呼び、正直な領域内のノードのランダム ウォークが高確率で交差することを保証するために使用されます。 SybilGuard と同様に、g 個の攻撃者のエッジがあると仮定すると、攻撃者は最大でも gwr = O(g × root n × log n) のテール (テイント テールと呼ばれる) に自分の Sybil ID の公開鍵を登録することができます。この場合、エッジが追加されるたびに O(log n) 個の Sybil ID が追加されます (攻撃者が、汚染された可能性のあるそれぞれのテールに異なる Sybil ID の異なる公開鍵を登録することで最適な攻撃戦略を使用すると仮定します)。
SybilLimit の安全性も w に大きく依存しています。パラメーターの正確な値を推定するメカニズムがないため、上で示したように、これらのパラメーターを過小評価または過大評価することは問題になります。 SybilLimit は、このパラメータを推定するための「ベンチマーク手法」も提供しますが、これもパラメータ推定の品質について証明可能な保証を提供しません。最後に、Sybil Limit は、g = o (n / log n) である限り、攻撃エッジごとに導入されるシビル ID の数を保証します。 SybilGuard も SybilLimit も、動作するソーシャル ネットワークに関するグローバルな知識を必要とせず、完全に分散された方法で実装できることに注意してください。
5.3 Sybil Infer
SybilInfer は、ランダム ウォーク (軌跡と呼ばれる) で定義された確率モデルを使用して、そのような軌跡を生成するノード X のセットがどれほど現実的であるかを推測します。 SybilInfer の基本的な前提は、各ノードがソーシャル ネットワークのグローバルなビューと知識を持ち、ネットワークは急速に混合され、SybilInfer を開始するノードは誠実なノードであるということです。技術的には、SybilInfer は、最終的にグラフ内のさまざまなノードを正直ノードまたはシビル ノードとしてラベル付けしようとします。 SybilInfer では、n 個のノードのネットワーク内の各ノードが s 回のウォークを実行するため、一般的なトレースの合計ウォーク数は s × n になります。これらの各トレースは、ランダム ウォークの最初のノード (ランダム ウォークの開始者) と最後のノード (末尾) で構成されます。 SybilGuard および SybilLimit で使用される均一な (ノード次数を超える) 遷移確率とは異なり、SybilInfer はノード上に均一な遷移行列を定義し、次数が高いノードにペナルティを与えます。 SybilInfer 操作の最終的な目標は、確率 P (X = Honest | T) を計算すること、つまり、軌跡 T が与えられたノードのセット X が正直である確率を計算することです。この確率はベイズの定理を使用して計算されます。
SybilInfer は、技術的手段によって正直な構成をサンプリングします。これは元々、トレースからノードのセットの誠実さを判断するために使用されていました。このサンプリングは、Metropolis-Hasting アルゴリズムを使用して実行されます。このアルゴリズムは、最初にセット X0 を考慮し、そのセットにノードを削除または追加することによって一度に 1 つずつセットを変更します。そのたびに、確率で新しいノード x が X￣0 から追加されます。 X ' = X0 [x または X0 内のノードが確率的に premove で削除されます。この手順では、n × log n ラウンドを実行して、X0 に関係なく良好なサンプルを取得します。
5.4 Sum Up
一般的なノードアドミッション問題であり、個々のノードがソーシャルグラフに関するグローバル情報を運ぶ必要がないという意味で分散化されている SybilGuard や SybilLimit や、ノードの誠実さを推測するための Sybil-Infer とは異なり、SumUp [35] は、Sybil 攻撃の解決に対処しようとしています。投票集約のコンテキスト。この場合、投票コレクターと呼ばれるノードは、Sybil 耐性のある方法でネットワーク内の他のノードから投票を収集したいと考えています。つまり、与えられたオブジェクト投票数に対して、投票収集者は、正直なノードによって受け入れられる投票の割合を増やし、攻撃者が攻撃エッジを通じて投じる受け入れ投票の数を減らし、攻撃者が不正行為を繰り返す場合にそれを特定したいと考えます。 SumUp の中核では、リンク容量割り当てメカニズムを使用して、トラスト所有のソーシャル グラフ内のリンクに容量を適応的に割り当て、投票者側から投票コレクターに伝播される投票数を制限します。 SumUp の適応型投票ストリーミング メカニズムは、従来のオンライン投票システムの 2 つの観察を使用します。システム内の少数のユーザーが単一のオブジェクトに投票します。そして、そのような投票システムがソーシャル グラフの上に実装されている場合、チェーン上には輻輳のみが表示されます。票集めに近い。したがって、SumUp は、(幅優先検索アルゴリズムを使用して計算されたあるレベルに従って) 投票コレクターからの距離に応じて、ソーシャル グラフ内のさまざまなリンクに多数のチケットを分散することを提案します。
この手法の明らかな魅力は、その高い計算要件にあります。一般的なアルゴリズム (フォード フルカーソン アルゴリズムなど) の実行時間には、1 人の投票者の投票を集めるために操作されるエッジの数のオーダーが必要になります。さらに、その著者らは、グラフの直径ステップの順序のみを使用するヒューリスティックを提案しています。このヒューリスティックでは、各ノードが、ゼロ以外の容量を使用して接続する上位レベルのノードを貪欲に選択し、投票がコレクターに到達するまで投票を伝播します。各ノードはいつでも、貪欲なステップによって非ゼロの容量が得られない可能性があることを考慮して、同じランクまたはそれより低いランクのパスを求めて他のノードを探索することができます。
5.5 GateKeeper
GateKeeper [21] は、効率的な操作を実現するために SumUp と SybilLimit からツールを借用しています。特に、SumUp のチケット配布コンポーネントを組み込むことで、SybilLimit のパフォーマンスの向上を試みます。前述したように、投票者からコレクターへのゼロ以外のパスを介してノードが許可される SumUp とは異なり、GateKeeper は、ノードを許可するためにアドミッション コントローラーによってチケットが使用される、SumUp の「チケット割り当て」フェーズのみを考慮します。このようなチケットは、SumUp と同じ方法でコントローラーからすべてのノードに伝播されます。ただし、攻撃者がより多くのチケットを取得する可能性を制限し、その全体的な利点を減らすために、GateKeeper のコントローラーは m 個の異なるランダム ノードをランダムに選択します。これらのノードは、有利なポイントが受信した場合にのみ許可されます。 fadmitm チケット (fadmit はランダムに選択された有利なポイントの一部です。GateKeeper では 0.2 が使用されます)。したがって、この有利な点の一部によってノードが許可されると、そのノードは許可されます。二重支払い攻撃を防ぐために、Gate Keeper は、チケットのパス (コントローラーに伝播される) の暗号化署名のチェーンを使用することを提案します。
5.6 ソーシャルネットワークに基づくその他の DHT
SPROUT [36] は、信頼できるソーシャル グラフとのソーシャル リンクを使用して、ソーシャル ネットワーク上で動作しているユーザーに情報をルーティングする別の DHT ルーティング プロトコルです。 SPROUT は実際には Chord [3] の上に構築されており、Chord では、いつでもオンラインになっている任意のノードのソーシャル ネットワーク内の他のユーザーに追加のリンク (ルーティング テーブル エントリ) を追加します。これにより、SPROUT は Chord 自体の信頼性と負荷分散を向上させると主張しています。
Whanau はもともと [23] で提案され、[22] の作業には、パフォーマンスとセキュリティのさらなる分析と証明、およびエンドツーエンド保証の実装と実証が含まれています。
[1] では、著者らはブートストラップ グラフ (Sybil 攻撃を防御するために DHT に導入された関係を示すツリー) を使用しています。著者らは、各ノードが知っているすべてのノード (エントリ ポイントを含む) のアドレスを返すように対象の DHT コードの動作を変更することで、Sybil 攻撃の影響を軽減するためのいくつかの戦略を考案しました。 Chord 上の近接性をルーティング (クエリ) メトリックとして使用する元の Chord とは異なり、このソリューションでは、ダイバーシティ、ハイブリッド、ジグザグなどの複数のルーティング戦略が考慮されています。著者らは、このような戦略を使用すると、Sybil 攻撃下で動作する場合に、Sybil 耐性のある DHT ルックアップをより効率的に実行できること、および、通常の Chord 設計に必要なクエリよりも少ないクエリが必要になることを実験的に示しています。
最初のレベルのタイトル
6 結論
投票経過: DAO委員会4/7可決
DAOrayaki DAOリサーチボーナスプール:
資金提供アドレス: 0xCd7da526f5C943126fa9E6f63b7774fA89E88d71
投票経過: DAO委員会4/7可決
賞金総額: 170 USDC
研究の種類: DAO、ソーシャルネットワーク、シビル防御、アンケート
原作者：アジズ・モハイセン、キム・ジュンホン
投稿者: Natalie、DAOctor @DAOrayaki
参考文献:
参考文献:
[1] George Danezis, Chris Lesniewski-laas, M. Frans Kaashoek, and Ross Anderson. Sybil-resistant dht
routing. In In ESORICS, Lecture Notes in Computer Science, pages 305–318, Berlin, Heidelberg, 2005. Springer.
[2] Petar Maymounkov and David Mazi`eres. Kademlia: A peer-to-peer information system based on the xor metric. In Peter Druschel, M. Frans Kaashoek, and Antony I. T. Rowstron, editors, IPTPS, Lecture Notes in Computer Science, pages 53–65, Berlin, Heidelberg, 2002. Springer.
[3] Ion Stoica, Robert Morris, David R. Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In SIGCOMM, pages 149–160, New York, NY, USA, 2001. ACM.
[4] Yong Wang, Xiao chun Yun, and Yifei Li. Analyzing the characteristics of gnutella overlays. In ITNG, pages 1095–1100, Washington, DC, USA, 2007. IEEE Computer Society.
[5] Vivek Pathak and Liviu Iftode. Byzantine fault tolerant public key authentication in peer-to-peer
systems. Computer Networks, 50(4):579–596, 2006.
[6] John Douceur and Judith S. Donath. The sybil attack. In IPDPS, pages 251–260, Washington, DC, USA, 2002. IEEE.
[7] Haifeng Yu, Chenwei Shi, Michael Kaminsky, Phillip B. Gibbons, and Feng Xiao. Dsybil: Optimal sybil-resistance for recommendation systems. In IEEE Symposium on Security and Privacy, pages 283–298, Washington, DC, USA, May 2009. IEEE Computer Society.
[8] Miguel Castro, Peter Druschel, Ayalvadi J. Ganesh, Antony I. T. Rowstron, and Dan S. Wallach. Secure routing for structured peer-to-peer overlay networks. In OSDI, Berkeley, CA, USA, 2002. USENIX Association.
[9] Atul Adya, William J. Bolosky, Miguel Castro, Gerald Cermak, Ronnie Chaiken, John R. Douceur, Jon Howell, Jacob R. Lorch, Marvin Theimer, and Roger Wattenhofer. Farsite: Federated, available, and reliable storage for an incompletely trusted environment. In OSDI, New York, NY, USA, 2002. USENIX Association.
[10] Jonathan Ledlie and Margo I. Seltzer. Distributed, secure load balancing with skew, heterogeneity and churn. In INFOCOM, pages 1419–1430, Washington, DC, USA, 2005. IEEE.
[11] Fran¸cois Lesueur, Ludovic M´e, and Val´erie Viet Triem Tong. An efficient distributed pki for structured p2p networks. In Proceeding of P2P, pages 1–10, Washington, DC, USA, 2009. IEEE
Computer Society.
[12] Fran¸cois Lesueur, Ludovic M´e, and Val´erie Viet Triem Tong. A distributed certification system for structured p2p networks. In David Hausheer and J¨urgen Sch¨onw¨alder, editors, AIMS, volume 5127 of Lecture Notes in Computer Science, pages 40–52, Berlin, Heidelberg, 2008. Springer.
[13] Fran¸cois Lesueur, Ludovic M´e, and Val´erie Viet Triem Tong. A sybil-resistant admission control coupling sybilguard with distributed certification. In WETICE, pages 105–110, Washington, DC, USA, 2008. IEEE Computer Society.
[14] Fran¸cois Lesueur, Ludovic M´e, and Val´erie Viet Triem Tong. A sybilproof distributed identity
management for p2p networks. In ISCC, pages 246–253, Washington, DC, USA, 2008. IEEE.
[15] Agapios Avramidis, Panayiotis Kotzanikolaou, and Christos Douligeris. Chord-pki: Embedding a
public key infrastructure into the chord overlay network. In Javier Lopez, Pierangela Samarati,
and Josep L. Ferrer, editors, EuroPKI, volume 4582 of Lecture Notes in Computer Science, pages 354–361, Berlin, Heidelberg, 2007. Springer.
[16] Nikita Borisov. Computational puzzles as sybil defenses. In Alberto Montresor, Adam Wierzbicki,
and Nahid Shahmehri, editors, Peer-to-Peer Computing, pages 171–176, Washington, DC,
USA, 2006. IEEE Computer Society.
[17] Haifeng Yu, Phillip B. Gibbons, and Michael Kaminsky. Toward an optimal social network
defense against sybil attacks. In Indranil Gupta and Roger Wattenhofer, editors, PODC, pages
376–377. ACM, 2007.
[18] Haifeng Yu, Phillip B. Gibbons, Michael Kaminsky, and Feng Xiao. Sybillimit: A near-optimal social network defense against sybil attacks. In IEEE Symposium on Security and Privacy, pages 3–17, Washington, DC, USA, 2008. IEEE Computer Society.
[19] Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, and Abraham Flaxman. SybilGuard: defending against sybil attacks via social networks. In Luigi Rizzo, Thomas E. Anderson, and Nick McKeown, editors, SIGCOMM, pages 267–278, New York, NY, USA, 2006. ACM.
[20] Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, and Abraham D. Flaxman. Sybilguard: defending against sybil attacks via social networks. IEEE/ACM Trans. Netw., 16(3):576–589, 2008.
[21] Nguyen Tran, Jinyang Li, Lakshminarayanan Subramanian, and Sherman S.M. Chow. Optimal sybil-resilient node admission control. In The 30th IEEE International Conference on Computer Communications (INFOCOM 2011), Shanghai, P.R. China, 2011. IEEE.
[22] Chris Lesniewski-Lass and M. Frans Kaashoek. Wh¯anau: A sybil-proof distributed hash table. In
7th USENIX Symposium on Network Design andImplementation, pages 3–17, Berkeley, CA, USA,
2010. USENIX Association.
[23] C. Lesniewski-Laas. A Sybil-proof one-hop DHT. In Proceedings of the 1st workshop on Social network systems, pages 19–24, New York, NY, USA, 2008. ACM.
[24] Paul F. Syverson, David M. Goldschlag, and Michael G. Reed. Anonymous connections and
onion routing. In IEEE Symposium on Security and Privacy, pages 44–54, Washington, DC, USA,
1997. IEEE Computer Society.
[25] Peng Wang, James Tyra, Eric Chan-tin, Tyson Malchow, Denis Foo Kune, and Yongdae Kim.
Attacking the kad network, 2009.
[26] B.N. Levine, C. Shields, and N.B. Margolin. A survey of solutions to the sybil attack. Technical
report, University of Massachusetts Amherst, Amherst, MA, 2006.
[27] Rodrigo Rodrigues, Barbara Liskov, and Liuba Shrira. The design of a robust peer-to-peer system. In 10th ACM SIGOPS European Workshop, pages 1–10, New York, NY, USA, 2002. ACM.
[28] James Newsome, Elaine Shi, Dawn Song, and Adrian Perrig. The sybil attack in sensor networks: analysis & defenses. In IPSN ’04: Proceedings of the 3rd international symposium on Information processing in sensor networks, pages 259–268, New York, NY, USA, 2004. ACM.
[29] Michael J. Freedman and Robert Morris. Tarzan: a peer-to-peer anonymizing network layer. In
Vijayalakshmi Atluri, editor, ACM Conference on Computer and Communications Security, pages 193–206, Washington, DC, USA, 2002. ACM.
[30] Fabrizio Cornelli, Ernesto Damiani, Sabrina De Capitani di Vimercati, Stefano Paraboschi, and Pierangela Samarati. Choosing reputable servents in a p2p network. In WWW, pages 376–386, New York, NY, USA, 2002. ACM.
[31] Brent ByungHoon Kang, Eric Chan-Tin, Christopher P. Lee, James Tyra, Hun Jeong Kang, Chris Nunnery, Zachariah Wadler, Greg Sinclair, Nicholas Hopper, David Dagon, and Yongdae Kim. Towards complete node enumeration in a peer-to-peer botnet. In Wanqing Li, Willy Susilo, Udaya Kiran Tupakula, Reihaneh Safavi-Naini, and Vijay Varadharajan, editors, ASIACCS, pages 23–34, New York, NY, USA, 2009. ACM.
[32] Frank Li, Prateek Mittal, Matthew Caesar, and Nikita Borisov. Sybilcontrol: practical sybil
defense with computational puzzles. In Proceedings of the seventh ACM workshop on Scalable trusted computing, pages 67–78. ACM, 2012.
[33] Luis von Ahn, Manuel Blum, Nicholas J. Hopper and John Langford. Captcha: Using hard ai problems for security. In Eli Biham, editor, EUROCRYPT, volume 2656 of Lecture Notes in Computer Science, pages 294–311, Berlin, Heidelberg, 2003. Springer.
[34] Jeff Yan and Ahmad Salah El Ahmad. Breaking visual captchas with naive pattern recognition algorithms. In ACSAC, pages 279–291, Washington, DC, USA, 2007. IEEE Computer Society.
[35] N. Tran, B. Min, J. Li, and L. Subramanian. Sybil-resilient online content voting. In NSDI, Berkeley, CA, USA, 2009. USENIX.
[36] Sergio Marti, Prasanna Ganesan, and Hector Garcia-Molina. Dht routing using social links. In IPTPS, pages 100–111, Washington, DC, USA, 2004. IEEE.
[37] Daniele Quercia and Stephen Hailes. Sybil attacks against mobile users: friends and foes to the
rescue. In INFOCOM’10: Proceedings of the 29th conference on Information communications, pages
336–340, Piscataway, NJ, USA, 2010. IEEE Press.
[38] Abedelaziz Mohaisen, Aaram Yun, and Yongdae Kim. Measuring the mixing time of social graphs. In Proceedings of the 10th annual conference on Internet measurement, IMC ’10, pages 383–389,
New York, NY, USA, 2010. ACM.
[39] Bimal Viswanath, Ansley Post, Krishna P. Gummadi, and Alan Mislove. An analysis of social network-based sybil defenses. In SIGCOMM, New York, NY, USA, August 2010. ACM.
[40] George Danezis and Prateek Mittal. SybilInfer: Detecting sybil nodes using social networks. In
The 16th Annual Network & Distributed System Security Conference, Lecture Notes in Computer Science, Berlin, Heidelberg, 2009. Springer-Verlag.
[41] Abedelaziz Mohaisen, Huy Tran, Nicholas Hopper, and Yongdae Kim. Understanding social networks properties for trustworthy computing. In ICDCS Workshops, pages 154–159. IEEE, 2011.
[42] Abedelaziz Mohaisen and Scott Hollenbeck. Improving social network-based sybil defenses by augmenting social graphs. In WISA, 2013.
[43] Abedelaziz Mohaisen, Nicholas Hopper, and Yongdae Kim. Keep your friends close: Incorporating trust into social network-based sybil defenses. In INFOCOM, pages 1943–1951. IEEE, 2011.
[44] Haifeng Yu. Sybil defenses via social networks: a tutorial and survey. ACM SIGACT News, 42(3):80–101, 2011.
