소개

소개

P2P(Peer-to-Peer) 컴퓨팅 패러다임은 다른 기존 패러다임에 비해 많은 이점이 있습니다. 예를 들어 대역폭, 메모리 및 데이터와 같은 리소스는 다른 모든 참여 사용자가 사용할 수 있습니다[1]. 대체로 이 패러다임에는 구조화된 시스템과 구조화되지 않은 시스템이 모두 포함됩니다. 구조화된 오버레이(예: Kademlia[2] 및 Chord[3])는 데이터 및 피어 검색을 위한 결정론적 메커니즘을 제공하는 반면, 구조화되지 않은 오버레이(예: Gnutella [4])는 피어를 무작위 그래프로 구성하고 피어 및 데이터에 대해 팬 헝 알고리즘을 사용합니다. 발견. 대부분의 인기 있는 P2P 시스템에는 "중앙 권한"이 없기 때문에 이 패러다임은 오류 공격에 저항할 수 있습니다. 다른 한편으로, 그러한 중앙 집중식 권한의 부족은 많은 도전적인 보안 문제로 이어집니다. 네트워크 시스템을 보호하는 데 필요한 대부분의 보안 서비스는 하나 또는 다른 중앙 집중식 권한을 필요로 하므로 피어 투 피어 시스템에서 이러한 서비스를 사용할 수 없게 됩니다[5]. ]. 설상가상으로, 이러한 많은 시스템의 완전히 분산되고 개방된 특성으로 인해 Sybil 공격[6]을 포함하여 다른 분산 시스템에서 알려지지 않은 광범위한 보안 위협이 발생했습니다.

Sybil 공격은 P2P, 유선 및 무선 네트워크 환경에서 잘 알려져 있습니다. 기본 형태에서 공격자를 나타내는 피어는 가능한 한 많은 ID를 생성하고 시스템의 정상적인 동작을 방해하도록 설계된 시스템[6]의 여러 피어인 것처럼 행동합니다. 공격자가 생성할 수 있는 ID의 수는 공격자의 능력에만 의존하며, 이는 시스템의 다른 피어로부터의 동시 요청에 응답하는 데 필요한 대역폭에 의해 제한되며 생성된 각 Sybil ID에 해당하는 노드의 라우팅 정보를 저장합니다. , 눈에 띄는 지연 없이 동시 요청을 처리하는 데 필요한 컴퓨팅 리소스. 하드웨어의 급격한 성장(예: 저장 용량 및 처리 측면)과 높은 대역폭 속도의 광대역 인터넷이 널리 보급됨에 따라 범용 하드웨어에서 실행되는 공격자도 대형 시스템에 심각한 피해를 줄 수 있습니다.

Sybil 공격은 P2P 시스템 및 광산 서비스에 필수적인 다른 일반 분산 시스템 및 패러다임에서 일반적으로 발생하는 것처럼 많은 상황에서 발생합니다. 이러한 환경에는 투표 시스템, 평판 시스템, 라우팅, 분산 스토리지 등이 포함됩니다. 이 공격이 실제 시스템에서 어떻게 작동하는지 설명하기 위해 P2P 오버레이에 구축된 추천 시스템을 상상해 보십시오[7]. 이러한 시스템에서 시스템의 목표는 다른 사람의 추천을 기반으로 사용자가 관심을 가질 수 있는 정보를 필터링하는 것입니다. 이 경우 여러 ID(Sybil)를 위조하여 여러 사용자를 가장할 수 있는 공격자는 합법적인 사용자가 투표한 합법적 개체에 쉽게 투표할 수 있습니다.

현실적인 추천 시스템에서 일반적으로 객체에 투표하는 정당한 사용자의 수는 항상 전체 시스템 사용자의 1%를 넘지 않는다는 것이 거의 보장됩니다[7]. 따라서 이 공격은 높은 인센티브를 제공하는 시스템을 공격하려는 시스템의 잠재적 사용자인 공격자에게 매력적입니다. 예를 들어 온라인 시장인 eBay는 고객 평가를 사용하여 판매자의 평판을 결정합니다. 판매자는 플랫폼을 사용하여 상품을 판매하므로 더 높은 평판을 얻기 위해 이러한 판매자가 잘못된 행동을 하도록 유혹합니다. 콘텐츠가 사용자에 의해 평가되는 P2P 파일 공유, 평판에 기반한 대역폭 할당, 이 경우 사용자가 배포하는 콘텐츠의 품질을 결정하는 데 사용되는 평판과 같은 다른 많은 상황에서도 마찬가지입니다. . 이러한 모든 예에는 사용자가 오작동할 동기가 있으며 Sybil 공격은 이러한 공격자가 목표를 달성하는 데 강력한 도구임이 입증되었습니다.

공격을 방어하기 위해 공격의 영향을 방어하거나 제한하기 위해 여러 형태의 방어 또는 완화가 시도되었습니다. 이러한 공격은 크게 중앙 집중식 방어와 분산형(즉, 분산) 방어라는 두 가지 학파로 나눌 수 있습니다. 중앙 집중식 방어 [6, 8, 9, 10]에서 중앙 기관은 시스템의 각 사용자의 신원을 확인할 책임이 있습니다. 이 방어는 공격을 방어하는 데 어느 정도 효과적이지만 시스템에 대한 특정 가정을 하며 그 중 일부는 P2P 분산 시스템에서 쉽게 구현되지 않습니다. 첫째, 이름과 작동 설명에서 알 수 있듯이 이러한 시스템에는 중앙 집중식 권한이 필요하며 보안 및 기능상의 이유로 많은 사람들에게 적합하지 않을 수 있습니다. 또한 이러한 중앙 집중식 권한이 있는 경우에도 사용자의 자격 증명을 디지털 ID와 일치시키기 위해 시스템의 사용자와 관련된 일부 자격 증명이 필요합니다. 이러한 자격 증명을 얻는 것은 많은 경우에 매우 어렵습니다.

반면에 분산형 방어에는 [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 7, 21, 22, 23]의 작업이 포함되지만 이에 국한되지는 않습니다. 중앙 집중식 권한 및 분산 P2P 시스템을 위해 신중하게 설계되었습니다. 운영의 핵심에서 이러한 방어는 공격자일 수 있는 사용자를 인정하거나 거부하기 위해 시스템 사용자 간의 협력을 평가합니다. 사용자 승인 또는 거부는 암호화된 분산 방어의 경우와 같이 사용자와 관련된 자격 증명 또는 소셜 그래프를 사용하는 Sybil 방어의 경우와 같이 합법적이고 정직한 사용자의 네트워크 속성을 기반으로 합니다. 두 솔루션 모두에서 방어의 궁극적인 목표는 분산된 방식으로 중앙 권한의 권한을 시뮬레이션하고 이 권한을 사용하여 마녀와 정직한 노드를 탐지하는 것입니다.

방어의 또 다른 분류는 방어가 작동하는 방식을 기반으로 할 수 있습니다. 따라서 이전 작업에서 Sybil 방어는 신뢰할 수 있는 인증서를 사용하는 방어로 나눌 수 있습니다. 여기서 인증서는 일반적으로 정직한 사용자를 위해 생성되고 신뢰할 수 있는 기관의 공개 키에 대해 검증되어 비용이 발생합니다. 여기서 사용자는 약간의 비용 처벌을 받기 때문에 양을 제한합니다. 사용 가능한 리소스의 감소, 잘못된 행동 감소, 소셜 네트워크 기반 Sybil 방어.

첫 번째 레벨 제목

2. Sybil 공격 모델 및 목표

이 섹션에서는 대부분의 Sybil 공격 연구 및 방어에서 일반적으로 가정하는 공격자 모델을 자세히 설명하고 공격자의 목표 및 방어 목표를 자세히 살펴봅니다.

2.1 문제 설명 및 모델

문제는 마치 그녀가 여러 복사본을 가지고 있는 것처럼 행동할 수 있는 시스템 능력을 가진 시스템의 단일 사용자로 공식화됩니다. 이러한 응용 프로그램의 정확성은 피어의 동작, 그 수 및 시스템의 공동 작업에 정직하게 참여하려는 의지에 따라 달라지기 때문에 많은 응용 프로그램에서 문제가 됩니다. 그러나 시스템 전체의 동작을 편향시키려는 단일 공격자의 시빌 ID는 이러한 시스템 목표를 충족할 수 없습니다.

공격자는 공식적으로 시스템에 삽입할 수 있는 허위 ID의 수로 특징지어집니다. 공격자의 동기는 허위 ID의 수를 최대화하는 것입니다. 공격자가 생성하여 시스템에 주입하는 ID 수의 가치와 중요성은 응용 프로그램 자체에 따라 다르며 응용 프로그램마다 다릅니다. 예를 들어, 추천 시스템을 공격하려면 시스템에서 정직한 사용자의 1% 일치 항목의 합계를 가짜 ID로 지정하면 충분합니다. 이 시스템에서 매우 인기 있는 개체에 대해서도 정직한 노드의 1%만이 투표하는 것으로 일반적으로 관찰되기 때문에 특히 이것은 시스템의 동작을 편향시키고 시스템에서 정직한 노드를 능가하기에 충분히 강력한 요소입니다. 즉, 시스템의 개체에 대해 투표하는 정직한 노드의 정확한 수보다 더 많은 단일 ID를 가짐으로써 Sybil 공격자는 정직한 노드의 투표를 추월할 수 있습니다.

반면에 통신을 익명화하는 데 사용되는 하이브리드 네트워크(예: Tor 네트워크)와 같은 다른 시스템에서는 소량의 시빌 ID라도 시스템의 약속을 심각하게 훼손할 수 있습니다. 이론적으로, 회선에 있는 두 노드의 타협은 그러한 하이브리드 네트워크에서 통신의 발신자와 수신자를 식별하기에 충분합니다[24]. 반면에 네트워크에서 충분한 ID가 손상되면 공격자가 여러 회로를 모니터링할 수 있습니다. ID 자체의 수가 중요한 다른 애플리케이션에는 파일 공유 시스템[25]에 대한 공격이 포함됩니다.

그림 1 P2P 중첩 환경에서 Sybil 방어의 여러 가지 방법

C/CA는 중앙 인증 기관을 의미합니다.

D/C는 Decentralized Cryptographic Primitives의 약자입니다.

T/D는 Trusted Device Authentication의 약자입니다.

IP/T는 IP 감지를 나타냅니다.

R/C는 비용 주기 기반 감지를 나타냅니다.

S/G는 소셜 그래프 기반 방어를 의미합니다.

2.2 시빌 디펜스의 목적과 성공 기준

시빌 방어의 궁극적인 목표는 오버레이 네트워크에서 시빌 ID 또는 해당 시빌 ID를 생성할 수 있는 피어를 감지하고 격리하여 시빌 공격을 제거하는 것입니다. 그러나 중앙 집중식 신뢰할 수 있는 인증을 기반으로 하는 방어를 제외한 대부분의 방어는 탐지 메커니즘에서 거짓 긍정 및 거짓 부정의 가능성이 있기 때문에 이 궁극적인 목표를 항상 달성할 수는 없습니다. 위양성 및 위음성 보고에서 본 것처럼. 잘못된 긍정 보고는 Sybil 노드가 정직한 노드로 보고되는 경우입니다. 반면 거짓 부정 정직 노드는 Sybil 노드로 보고됩니다. 현실적이고 실질적으로 달성 가능한 방어 메커니즘의 목표는 위음성률을 최대한 줄이는 것입니다.

2.3 마녀 방어의 깊이

첫 번째 레벨 제목

3. 신뢰할 수 있는 인증서 사용

신뢰할 수 있는 인증 방법은 Douceur[6]가 Sybil 공격[26]을 제거할 수 있는 가능성을 입증했기 때문에 오늘날 가장 인기 있는 방법 중 하나입니다. 이 접근 방식의 전통적인 형태에서는 중앙 집중식 권한(CA)을 사용하여 각 피어에 할당된 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 공격이 발생하기 어렵게 만듭니다.

이론적으로 이러한 방어 체계의 대부분의 계획은 방어가 없는 경우보다 마녀 신원의 수를 더 적은 수로 제한합니다. 그러나 실제로는 적은 수의 마녀 신원만으로도 많은 시스템의 유용성과 보안을 위협할 수 있습니다. 예를 들어 앞서 언급했듯이 Tor와 같은 익명 시스템의 익명성은 회로당 두 개의 노드에 의존합니다. 또한 온라인 평판 시스템에서 가짜 ID의 1%는 합법적인 노드에 투표하기에 충분합니다.

4.1 IP 테스트

일반적인 테스트 시나리오에는 피어의 위치를 ​​확인하고 이를 활동과 일치시키기 위해 피어의 IP 주소를 테스트하는 것이 포함됩니다. 특히, 상당한 양의 활동이 동일한 특정 지리적 영역에서 발생하는 경우 해당 활동 중 일부는 마녀로 인한 것일 수 있습니다. 또한 이러한 작업의 가정은 서로 다른 지리적 영역에 대한 IP 주소를 얻는 것이므로 저렴하지 않습니다. 예를 들어, Friedman 등[29]은 노드의 IP 주소가 특정 자율 시스템 내의 지리적 위치를 기반으로 테스트되는 Tarzan을 소개합니다. 유사한 결과가 Cornelli 등이 [30] 및 [30]에서 제시했습니다.

이러한 작업의 주요 가정은 넓은 지리적 영역에서 IP 주소를 얻기 어렵다는 것입니다. 그러나 최근 단일 관리 엔티티에 의해 제어되고 서로 다른 자율 시스템에 상주하는 감염된 호스트가 있는 거대한 봇넷[31]의 존재에 대한 징후로 인해 이 방어 메커니즘이 쓸모가 없다는 것이 확실합니다.

4.2 비용 주기

여러 연구와 관행에 따르면 Sybil 공격에 대한 방어 수단으로 반복 비용이 발생합니다. 특히 계산 퍼즐[16, 32]과 튜링 테스트(e.g. CAPTCHA[33])가 해결책으로 제시된다. 그러나 IP 테스트가 봇넷을 제어하는 ​​공격자에 대해 작동하지 않는 것과 마찬가지로 이러한 비용 기반 계획도 마찬가지입니다. 또한 CAPTCHA와 유사한 솔루션의 경우 Sybil 공격자는 사용자가 공격자가 제공한 서비스에 대한 액세스를 테스트할 수 있도록 제어된 사이트에서 CAPTCHA 테스트를 실행할 수 있는 것으로 나타났습니다.

첫 번째 레벨 제목

5. 소셜 그래프 기반 방어

분산 시스템에서 시빌 공격 문제에 대해 이전에 제안된 대부분의 솔루션에는 한계와 단점이 있지만 소셜 네트워크 기반 시빌 방어는 이러한 문제를 우아한 방식으로 극복하려고 시도합니다. 첫째, 소셜 네트워크 기반 Sybil 방어는 대부분 Sybil 공격 문제에 대한 분산 솔루션입니다. 즉, 이러한 설계는 대부분의 분산 시스템에서 중요한 속성인 중앙 권한 없이 작동합니다. 이 분산형 운영 모델은 이러한 방어에서 가장 일반적으로 사용되는 요소인 랜덤 워크 이론 덕분에 더 쉬워졌습니다. 둘째, 이러한 방어는 소셜 노드 간의 소셜 링크 신뢰를 활용하여 정직한 노드 간의 협업을 가능하고 쉽게 만듭니다. 셋째, 마지막으로 이러한 방어는 여러 연구에서 저렴한 비용으로 Sybil 공격에 대해 실용적이고 효과적인 것으로 입증되었으며 현재 DHT(Distributed Hash Tables), anti-Sybil 투표, 모바일 네트워크 라우팅용.

설계 세부 사항과 운영 면에서 크게 다르지만 모든 소셜 네트워크 기반 Sybil 방어는 알고리즘 속성, 즉 빠른 혼합 속성과 신뢰라는 두 가지 공통 가정을 공유합니다. 첫째, 이러한 방어는 소셜 그래프의 "빠른 혼합" 속성을 기반으로 합니다. 비공식적으로 소셜 그래프의 빠른 혼합 속성은 이러한 그래프의 "정직한" 노드가 잘 맞물리고 정직한 영역에 희소 절단(정직한 노드의 두 개의 큰 하위 집합을 일부 소셜 네트워크 절단과 연결하는 방법)이 포함되지 않음을 의미합니다. 단순화를 위해 소셜 그래프의 빠른 혼합 특성은 소셜 그래프의 모든 노드에서 무작위로 걸으면 몇 단계 후에 그래프에 정의된 Markov 체인(MC)의 고정 분포에 근접하게 됩니다. 수백만 개의 노드로 구성된 네트워크에서 권장되는 이러한 단계 수는 10~15단계입니다.

이 방어적인 맥락에서 두 번째 일반적인 가정은 신뢰입니다. 특히 이러한 모든 방어는 예를 들어 노드 간의 대면 상호 작용에서 알 수 있듯이 기본 소셜 그래프에서 좋은 신뢰 값을 가정합니다. 임의의 수의 공격자의 소셜 링크로 소셜 네트워크에 침투하는 어려움을 추론하기 위해 이 특정 가정이 필요합니다. 소셜 그래프에서 "정직한" 노드를 올바르게 식별하기 위한 Sybil 방어의 작동은 빠른 혼합 가정과 이 알고리즘 속성을 사용하는 해당 체계의 구성에 의해 보장되는 반면, Sybil 노드를 식별하는 기능은 다음과 같은 가정에서만 보장됩니다. 공격자 또는 공격자 집단은 자신과 소셜 그래프의 다른 정직한 노드 사이의 일부 링크를 제어합니다(이러한 링크를 공격 에지라고 함).

아래에서 우리는 널리 인용되고 우려되는 소셜 네트워크 기반 Sybil 방어 방법을 정리했습니다.

5.1 Sybil Guard

Yu 등[19, 20]에 기인한 SybilGuard의 설계는 신뢰 소유 소셜 네트워크의 빠른 혼합 속성을 사용하여 Sybil 노드를 감지합니다. 기술적으로 SybilGuard는 초기화 단계와 온라인 감지 단계의 두 단계로 구성됩니다. 초기화 단계에서 각 노드는 입력 및 출력 에지 쌍에 대한 이웃의 임의 순열로 라우팅 테이블을 작성합니다. 다음으로, 각 노드는 길이 w = O(root n log n)의 랜덤 워크를 시작하고 이를 랜덤 순열을 사용하여 구축된 라우팅 테이블에 따라 이웃에게 전파합니다. 랜덤 워크 경로의 모든 노드는 랜덤 워크 개시자의 증인으로 등록한 다음 해당 노드가 의심 노드가 되면 노드의 증인 역할을 합니다. 또한 랜덤 워크의 회고적 특성을 활용하여 랜덤 워크의 각 개시자는 "증인"(즉, 개시자의 공개 키를 등록하고 개시자의 무작위로 구성된 경로에 있는 노드) 목록을 받게 됩니다. 걷다).

온라인 단계에서 검증자는 다음과 같이 용의자가 정직한지 여부를 판단합니다. 먼저, 피의자는 자신의 임의 경로에 있는 "증인"의 주소를 검증자에게 보냅니다. 따라서 유효성 검사기는 증인 목록을 유효성 검사기 라우팅 목록과 비교합니다. 두 세트 사이에 교차가 없으면(가능성이 매우 높은 이벤트) 검증자는 의심을 중단하고 거부합니다. 그렇지 않으면 검증자는 계속해서 두 세트 사이의 교차점에 있는 노드를 비교하여 용의자가 공개 키로 등록되었는지 확인하도록 요청합니다. 의심이 교차 노드에 의해 확인되면 유효성 검사기는 의심을 수락하거나 Sybil 노드로 표시합니다.

5.2 Sybil Limit

하나의 긴 랜덤 워크를 사용하는 SybilGuard와 달리 SybilLimit은 여러 개의 더 짧은 랜덤 워크를 제안합니다. 또한 SybilGuard(검증자와 용의자의 공개 키가 소셜 그래프의 노드에 등록됨)와 달리 SybilLimit [18]은 이러한 키를 소셜 그래프의 가장자리에 등록하도록 제안합니다. SybilLimit은 초기화 단계와 온라인 검증 단계로 구성됩니다. .초기화 단계에서 각 노드는 SybilGuard에서 설명한 것과 동일한 방법을 사용하여 라우팅 테이블을 구축하고 길이 w = O(log n)일 때마다 r = O(root n)의 랜덤 워크를 수행합니다. 여기서 O(log n) 혼합 시간 소셜 그래프의 10-15 소셜 그래프이며 이론적으로 통계 분포에 매우 가까운 분포에서 노드를 샘플링하기에 충분하다고 가정합니다 SybilGuard와 달리 임의 라우팅 경로의 모든 노드는 임의 보행 개시자를 등록하는 데 사용됩니다. r개의 random walk 각각의 edge는 originator 노드의 공개키를 등록하는데 사용된다.(이러한 각 edge를 tail이라고 부른다.) 특히 walk의 originator의 공개키는 마지막 edge 아래의 마지막 노드에 등록된다. 또한 임의 라우팅의 소급 특성을 사용하여 개시자 노드(용의자 또는 검증자일 수 있음)의 공개 키를 등록한 증인은 자신의 ID를 노드에 반환합니다. 소셜 그래프의 각 노드는 다음을 수행합니다. 동일한 프로세스와 등록된 랜덤 워크를 시작하는 각 노드는 일련의 증인(또는 검증자)을 수집합니다.

온라인 단계에서 SybilLimit는 SybilGuard와 동일하며, 용의자는 증인의 식별자와 주소를 검증자 노드로 전송하고 검증 노드는 용의자 목록의 증인을 비교하여 충돌을 찾으려고 합니다. 검증자 측의 두 집합에서 충돌이 발생하면 검증자는 두 집합의 공통 신원을 가진 증인에게 용의자의 신원을 확인하도록 요청하고 이 과정의 결과에 따라 용의자를 수락할지 또는 거부할지를 결정합니다. 둘 사이에 교차가 없으면(발생 가능성이 매우 낮음) 검증자는 용의자를 공격자로 표시하여 중단하고 거부합니다.

SybilLimit에 대해 추론하는 데 사용되는 증명 가능한 보장의 주요 구성 요소는 Sybil Guard에서와 동일합니다. 특히, 랜덤 워크 길이 w를 소셜 그래프의 혼합 시간이라고 가정하면, 이러한 랜덤 워크에서 선택된 마지막 노드는 고정 분포를 따른다.

또한 임의 보행의 마지막 가장자리는 소셜 그래프의 가장자리 중에서 "거의" 균일하게 무작위로 선택됩니다. 또한 r = O(루트 n)이라고 가정할 때 숨겨진 상수 r0(여기서 r = r0 × 루트 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는 결국 그래프의 다른 노드를 정직한 노드 또는 Sybil 노드로 레이블 지정하려고 합니다. SybilInfer에서 n 노드 네트워크의 각 노드는 s walk를 수행하므로 일반 트레이스의 총 walk 수는 s × n입니다. 이러한 각 추적은 첫 번째 노드(랜덤 워크의 개시자)와 랜덤 워크의 마지막 노드(꼬리)로 구성됩니다. SybilGuard 및 SybilLimit에서 사용되는 균일(노드 차수 초과) 전이 확률과 달리 SybilInfer는 노드에서 균일 전이 행렬을 정의하여 차수가 더 높은 노드에 페널티를 부여합니다. SybilInfer 작업의 궁극적인 목표는 확률 P(X = 정직 | T)를 계산하는 것입니다. 이 확률은 베이즈 정리를 사용하여 계산됩니다.

SybilInfer는 원래 추적에서 노드 집합의 정직성을 결정하는 데 사용된 정직한 구성을 기술적 수단으로 샘플링합니다. 이 샘플링은 Metropolis-Hasting 알고리즘을 사용하여 수행되며, 먼저 집합 X0을 고려하고 집합에 노드를 제거하거나 추가하여 한 번에 하나씩 집합을 수정합니다. 매번 새 노드 x가 X0에서 추가될 확률이 있습니다. X ′ = X0 [x 또는 X0의 노드가 확률 사전 이동으로 삭제되도록 X0에. 이 절차는 n × log n 라운드를 수행하여 X0과 독립적인 좋은 샘플을 얻습니다.

5.4 Sum Up

일반적인 노드 승인 문제인 SybilGuard 및 SybilLimit와 달리 개별 노드는 소셜 그래프에 대한 글로벌 정보를 전달할 필요가 없다는 점에서 분산되고 노드 정직성을 추론하기 위한 Sybil-Infer와 달리 SumUp[35]은 다음에서 시빌 공격 해결을 시도합니다. 투표 집계의 맥락. 이 경우 투표 수집기라는 노드는 Sybil-resistant 방식으로 네트워크의 다른 노드로부터 투표를 수집하려고 합니다. 즉, 주어진 개체 투표 수에 대해 투표 수집가는 정직한 노드가 수락한 투표의 비율을 늘리고, 공격자가 공격 가장자리를 통해 던진 수락 투표 수를 줄이고, 공격자가 반복적으로 오작동할 때 공격자를 식별하기를 원합니다. SumUp의 핵심에서 링크 용량 할당 메커니즘은 신뢰 소유 소셜 그래프의 링크에 용량을 적응적으로 할당하고 유권자 측에서 투표 수집기로 전파되는 투표 수를 제한하는 데 사용됩니다. SumUp의 적응형 투표 스트리밍 메커니즘은 기존 온라인 투표 시스템의 두 가지 관찰을 사용합니다. 시스템의 소수 사용자가 단일 개체에 투표하고, 이러한 투표 시스템이 소셜 그래프 위에 구현된 경우 혼잡만 체인에 나타납니다. 투표 수집가와 가깝습니다. 따라서 SumUp은 투표 수집가와의 거리에 따라(폭 우선 검색 알고리즘을 사용하여 계산된 일부 수준에 따라) 소셜 그래프의 여러 링크에 많은 수의 티켓을 배포할 것을 제안합니다.

이 기술의 명백한 매력은 높은 계산 요구 사항에 있습니다. 일반적인 알고리즘(예: Ford-fulkerson 알고리즘)의 실행 시간은 단일 유권자의 투표를 수집하기 위해 조작할 가장자리 수의 순서를 필요로 합니다. 저자는 또한 그래프 직경 단계의 순서만 사용하는 휴리스틱을 제안합니다. 여기서 각 노드는 0이 아닌 용량을 사용하여 연결하고 투표가 수집기에 도달할 때까지 투표를 전파할 상위 수준 노드를 탐욕스럽게 선택합니다. 욕심 많은 단계로 인해 용량이 0이 되지 않을 수 있다는 점을 고려하여 각 노드는 언제든지 동일하거나 낮은 순위의 경로에 대해 다른 노드를 탐색할 수 있습니다.

5.5 GateKeeper

GateKeeper [21]는 SumUp 및 SybilLimit에서 도구를 빌려 효율적인 운영을 달성합니다. 특히 SumUp의 티켓 배포 구성 요소를 통합하여 SybilLimit의 성능을 개선하려고 합니다. 이전에 언급한 바와 같이 노드가 0이 아닌 경로를 통해 유권자에서 수집가로 승인되는 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 조회를 수행하는 데 사용될 수 있으며 바닐라 코드 디자인에 필요한 것보다 적은 쿼리가 필요함을 실험적으로 보여줍니다.

첫 번째 레벨 제목

6 결론

투표 진행: DAO 위원회 4/7 통과

DAOrayaki DAO 리서치 보너스 풀:

펀딩 주소: 0xCd7da526f5C943126fa9E6f63b7774fA89E88d71

투표 진행: DAO 위원회 4/7 통과

총 현상금: 170 USDC

연구 유형: DAO, 소셜 네트워크, Sybil 방어, 설문 조사

원작자: Aziz Mohaisen, 김중헌

기여자: 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.