giới thiệu

giới thiệu

Mô hình điện toán ngang hàng (p2p) có nhiều ưu điểm hơn các mô hình truyền thống khác. Ví dụ: các tài nguyên như băng thông, bộ nhớ và dữ liệu có sẵn cho tất cả người dùng tham gia khác [1]. Nói rộng ra, mô hình này bao gồm cả hệ thống có cấu trúc và phi cấu trúc. Các lớp phủ có cấu trúc (chẳng hạn như Kademlia [2] và Chord [3]) cung cấp các cơ chế xác định cho dữ liệu và khám phá ngang hàng, trong khi các lớp phủ không có cấu trúc (chẳng hạn như Gnutella [4]) tổ chức các đồng nghiệp trong một biểu đồ ngẫu nhiên và sử dụng thuật toán pan Hung cho ngang hàng và dữ liệu khám phá. Hầu hết các hệ thống ngang hàng phổ biến đều thiếu "cơ quan trung ương", điều này làm cho mô hình này chống lại các cuộc tấn công lỗi. Mặt khác, việc thiếu một cơ quan tập trung như vậy dẫn đến nhiều vấn đề bảo mật đầy thách thức: hầu hết các dịch vụ bảo mật cần thiết để bảo vệ các hệ thống mạng đều yêu cầu một hoặc một cơ quan tập trung khác, khiến các dịch vụ này không thể sử dụng được bởi các hệ thống ngang hàng [5] ]. Tồi tệ hơn, tính chất mở và phi tập trung hoàn toàn của nhiều hệ thống này đã dẫn đến một loạt các mối đe dọa bảo mật chưa biết trong các hệ thống phân tán khác, bao gồm cả các cuộc tấn công Sybil [6].

Các cuộc tấn công Sybil nổi tiếng trong môi trường mạng ngang hàng, có dây và không dây. Ở dạng cơ bản, một người ngang hàng đại diện cho kẻ tấn công tạo ra càng nhiều danh tính càng tốt và hành xử như thể cô ta là nhiều người ngang hàng trong hệ thống [6], được thiết kế để can thiệp vào hành vi bình thường của hệ thống. Số lượng danh tính mà kẻ tấn công có thể tạo chỉ phụ thuộc vào khả năng của kẻ tấn công, bị giới hạn bởi băng thông cần thiết để đáp ứng các yêu cầu đồng thời từ các đồng nghiệp khác trong hệ thống, lưu trữ thông tin định tuyến của nút tương ứng với từng danh tính Sybil được tạo. và tài nguyên điện toán cần thiết để xử lý các yêu cầu đồng thời mà không bị chậm trễ đáng kể. Với sự phát triển mạnh mẽ của phần cứng (ví dụ: về dung lượng lưu trữ và xử lý) và sự phổ biến rộng rãi của Internet băng thông rộng với tốc độ băng thông cao, ngay cả những kẻ tấn công chạy trên phần cứng đa năng cũng có thể gây ra thiệt hại đáng kể cho các hệ thống lớn.

Các cuộc tấn công Sybil xảy ra trong nhiều bối cảnh, như phổ biến trên các hệ thống ngang hàng và các hệ thống và mô hình phân tán chung khác cần thiết cho các dịch vụ khai thác. Những môi trường như vậy bao gồm hệ thống bỏ phiếu, hệ thống danh tiếng, định tuyến, lưu trữ phân tán, v.v. Để minh họa cách tấn công này hoạt động trong một hệ thống trong thế giới thực, hãy tưởng tượng một hệ thống đề xuất được xây dựng trên các lớp phủ ngang hàng [7]. Trong các hệ thống như vậy, mục tiêu của hệ thống là lọc ra thông tin mà người dùng có thể quan tâm dựa trên các đề xuất từ ​​người khác. Trong trường hợp này, kẻ tấn công có thể mạo danh nhiều người dùng bằng cách giả mạo nhiều danh tính (Sybil) có thể dễ dàng bỏ phiếu cho các đối tượng hợp pháp mà người dùng hợp pháp đã bỏ phiếu.

Trong bất kỳ hệ thống giới thiệu thực tế nào, gần như đảm bảo rằng số lượng người dùng hợp pháp thường bỏ phiếu cho một đối tượng luôn không quá 1% tổng số người dùng của hệ thống [7]. Vì điều này, cuộc tấn công này hấp dẫn đối với những kẻ tấn công, những người là người dùng tiềm năng của hệ thống đang cố gắng tấn công các hệ thống cung cấp các ưu đãi cao. Ví dụ, thị trường trực tuyến eBay sử dụng lời chứng thực của khách hàng để xác định danh tiếng của người bán, những người sử dụng nền tảng của eBay để bán hàng hóa, do đó, những người bán như vậy sẽ có hành vi sai trái để có được danh tiếng cao hơn. Điều tương tự cũng xảy ra trong nhiều tình huống khác, chẳng hạn như chia sẻ tệp ngang hàng trong đó nội dung được người dùng xếp hạng, phân bổ băng thông dựa trên danh tiếng và trong trường hợp này, thậm chí danh tiếng được sử dụng để xác định chất lượng nội dung do người dùng phân phối. . Trong tất cả các ví dụ như vậy, đều có động cơ khiến người dùng có hành vi sai trái và cuộc tấn công Sybil đã được chứng minh là một công cụ mạnh mẽ để những kẻ tấn công như vậy đạt được mục tiêu của chúng.

Để chống lại các cuộc tấn công, một số hình thức phòng thủ hoặc giảm nhẹ đã được cố gắng chống lại hoặc hạn chế tác động của các cuộc tấn công. Các cuộc tấn công như vậy có thể được chia thành hai trường phái tư tưởng: phòng thủ tập trung và phi tập trung (tức là phân tán). Trong phòng thủ tập trung [6, 8, 9, 10], cơ quan trung tâm chịu trách nhiệm xác minh danh tính của từng người dùng trong hệ thống. Mặc dù biện pháp phòng thủ này phần nào có hiệu quả trong việc chống lại các cuộc tấn công, nhưng nó đưa ra một số giả định nhất định về hệ thống, một số giả định không dễ thực hiện trong hệ thống phi tập trung ngang hàng. Đầu tiên, như tên gọi và mô tả hoạt động gợi ý, các hệ thống như vậy yêu cầu một cơ quan có thẩm quyền tập trung, điều này có thể không phù hợp với nhiều người vì lý do bảo mật và chức năng. Hơn nữa, ngay cả khi có sự hiện diện của một cơ quan tập trung như vậy, một số thông tin đăng nhập liên quan đến người dùng trong hệ thống là cần thiết để khớp các thông tin đăng nhập đó của người dùng với danh tính kỹ thuật số của họ: trong nhiều trường hợp, việc có được thông tin đăng nhập như vậy là rất khó khăn.

Mặt khác, phòng thủ phi tập trung bao gồm nhưng không giới hạn ở công việc trong [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 7, 21, 22, 23], không yêu cầu Quyền hạn tập trung và được thiết kế cẩn thận cho các hệ thống ngang hàng phi tập trung. Cốt lõi của hoạt động của họ, các biện pháp phòng thủ như vậy cân nhắc sự hợp tác giữa những người dùng trong hệ thống để thừa nhận hoặc từ chối những người dùng có thể là kẻ tấn công. Việc chấp nhận hoặc từ chối người dùng dựa trên thông tin đăng nhập được liên kết với người dùng, như trong trường hợp phòng thủ phân tán được mã hóa hoặc thuộc tính mạng của người dùng trung thực hợp pháp, như trong trường hợp phòng thủ Sybil sử dụng biểu đồ xã hội. Trong cả hai giải pháp, mục tiêu cuối cùng của phòng thủ là mô phỏng sức mạnh của cơ quan trung ương theo cách phi tập trung và sử dụng sức mạnh này để phát hiện phù thủy và các nút trung thực.

Một cách phân loại phòng thủ khác có thể dựa trên cách thức phòng thủ đó hoạt động. Do đó, trong công việc trước đây, phòng thủ Sybil có thể được chia thành phòng thủ sử dụng chứng chỉ đáng tin cậy - nơi chứng chỉ thường được tạo cho người dùng trung thực và được xác minh dựa trên khóa công khai của cơ quan đáng tin cậy, phát sinh chi phí - nơi người dùng phải chịu một số hình phạt chi phí, do đó hạn chế số lượng các tài nguyên có sẵn cho họ, giảm hành vi sai trái của họ và phòng thủ Sybil dựa trên mạng xã hội.

tiêu đề cấp đầu tiên

2. Mô hình và mục tiêu tấn công của Sybil

Trong phần này, mô hình kẻ tấn công thường được giả định trong hầu hết các nghiên cứu và phòng thủ về tấn công Sybil được xây dựng chi tiết, tiếp tục khám phá mục tiêu của kẻ tấn công và mục tiêu phòng thủ.

2.1 Phát biểu vấn đề và mô hình

Vấn đề được đặt ra là một người dùng duy nhất trong hệ thống có một khả năng trong hệ thống cho phép cô ấy hành động như thể cô ấy có nhiều bản sao. Đây là vấn đề đối với rất nhiều ứng dụng, vì tính chính xác của các ứng dụng như vậy phụ thuộc vào hành vi của các đồng nghiệp, số lượng của họ và sự sẵn sàng tham gia cộng tác một cách trung thực trong hệ thống. Tuy nhiên, danh tính sybil của một kẻ tấn công đơn lẻ đang cố gắng làm sai lệch hành vi của toàn bộ hệ thống không thể đáp ứng các mục tiêu hệ thống như vậy.

Kẻ tấn công được đặc trưng chính thức bởi số lượng danh tính giả mà cô ta có thể đưa vào hệ thống. Động lực của kẻ tấn công là tối đa hóa số lượng danh tính giả. Giá trị và tầm quan trọng của số lượng danh tính mà kẻ tấn công tạo ra và đưa vào hệ thống phụ thuộc vào chính ứng dụng đó và thay đổi theo từng ứng dụng. Ví dụ: để tấn công một hệ thống giới thiệu, chỉ cần có tổng số kết quả phù hợp từ 1% người dùng trung thực trong hệ thống dưới dạng danh tính giả. Vì người ta thường quan sát thấy rằng ngay cả đối với các đối tượng rất phổ biến trong hệ thống này, chỉ có 1% số nút trung thực bỏ phiếu cho nó, đặc biệt đây là một yếu tố đủ mạnh để làm sai lệch hành vi của hệ thống và vượt qua các nút trung thực trong hệ thống. Nghĩa là, bằng cách có nhiều danh tính đơn lẻ hơn số lượng chính xác các nút trung thực bỏ phiếu cho một đối tượng trong hệ thống, những kẻ tấn công Sybil sẽ có thể vượt qua số phiếu bầu của các nút trung thực.

Mặt khác, trong các hệ thống khác, chẳng hạn như mạng hỗn hợp được sử dụng để ẩn danh hóa thông tin liên lạc (chẳng hạn như mạng Tor), ngay cả một lượng nhỏ nhận dạng sybil cũng có thể làm suy yếu nghiêm trọng những lời hứa trong hệ thống. Về mặt lý thuyết, sự thỏa hiệp của hai nút trên một mạch là đủ để xác định người gửi và người nhận thông tin liên lạc trên một mạng kết hợp như vậy [24]. Mặt khác, việc thỏa hiệp đủ danh tính trong mạng sẽ cho phép kẻ tấn công giám sát bất kỳ số lượng mạch nào. Các ứng dụng khác mà bản thân số lượng nhận dạng cũng quan trọng bao gồm các cuộc tấn công vào các hệ thống chia sẻ tệp [25], để kể tên một số.

Hình 1 Một số cách phòng thủ Sybil khác nhau trong môi trường chồng chất P2P

C/CA là viết tắt của Cơ quan chứng nhận tập trung

D/C là viết tắt của Decentralized Cryptographic Primitives

T/D là viết tắt của Xác thực thiết bị đáng tin cậy

IP/T là viết tắt của phát hiện IP

R/C là viết tắt của phát hiện dựa trên chu kỳ chi phí

S/G là viết tắt của xã hội đồ thị dựa trên phòng thủ

2.2 Mục tiêu và tiêu chí thành công của Sybil Defense

Mục tiêu cuối cùng của phòng thủ sybil là loại bỏ các cuộc tấn công sybil bằng cách phát hiện và cô lập các danh tính sybil trong mạng lớp phủ hoặc những đồng nghiệp có khả năng tạo ra các danh tính sybil đó. Tuy nhiên, mục tiêu cuối cùng này không phải lúc nào cũng đạt được, bởi vì hầu hết các biện pháp phòng thủ, ngoại trừ những biện pháp dựa trên xác thực đáng tin cậy tập trung, đều có khả năng dương tính giả và âm tính giả trong cơ chế phát hiện của chúng, điều này có thể được chấp nhận đối với một số nút sybil trong khi báo cáo sai các nút trung thực khác. như chúng ta đã thấy với báo cáo dương tính giả và âm tính giả. Báo cáo dương tính giả là khi nút Sybil được báo cáo là nút trung thực. Mặt khác, các nút trung thực âm tính giả được báo cáo là các nút Sybil. Một mục tiêu thực tế và có thể đạt được trên thực tế của các cơ chế phòng vệ là giảm tỷ lệ âm tính giả càng nhiều càng tốt.

2.3 Độ sâu phòng thủ của phù thủy

tiêu đề cấp đầu tiên

3. Sử dụng chứng chỉ đáng tin cậy

Phương pháp xác thực đáng tin cậy được cho là một trong những phương pháp phổ biến nhất hiện nay, vì Douceur [6] đã chứng minh tiềm năng của nó trong việc loại bỏ các cuộc tấn công Sybil [26]. Ở dạng truyền thống của phương pháp này, một cơ quan tập trung (CA) được sử dụng để đảm bảo rằng các danh tính được gán cho mỗi ngang hàng là duy nhất và hợp pháp bằng cách khớp các danh tính này với thông tin đăng nhập được chỉ định trước. Những thông tin xác thực này có thể bao gồm khóa mã hóa, chuỗi ngẫu nhiên đồng bộ thường được tạo bởi trình tạo mật khẩu dùng một lần (OTP) hoặc chứng chỉ kỹ thuật số do cơ quan tập trung cấp.

Mặc dù các hình thức truyền thống của cơ quan cấp chứng chỉ tập trung được mô tả ở trên đã được xác định rõ trong tài liệu, nhưng các sơ đồ chứng chỉ phân tán đã được xác định bằng cách áp dụng các nguyên tắc mật mã phù hợp với các mô hình đa bên phân tán cho phép Cộng tác chứng thực các đồng nghiệp khác tham gia lớp phủ.

3.1 Cơ quan chứng nhận tập trung

Xác thực đáng tin cậy tập trung có thể là cách duy nhất để loại bỏ các cuộc tấn công Sybil [6]. Trong bối cảnh phủ sóng P2P, đã có một số công việc sử dụng cơ quan cấp chứng chỉ tập trung để tạo, phân phối và xác minh thông tin xác thực. Ví dụ: các nghiên cứu sử dụng biểu đồ xã hội được giải thích trong Phần 5 và sử dụng mật mã khóa công khai làm khối xây dựng giả định rằng tính xác thực của khóa công khai của người dùng được chuyển qua chứng chỉ được gán cho người dùng thông qua cơ quan có thẩm quyền tập trung trong giai đoạn ngoại tuyến [19 ]. Ví dụ về các lược đồ khác sử dụng các phương pháp dựa trên CCA bao gồm công việc trong [8], [9], [6] và [10].

3.2 Mật mã nguyên thủy

Gần đây, một số công trình về mật mã nguyên thủy đã xuất hiện [11, 12, 13, 14, 15]. Những nguyên mẫu này nhằm cung cấp cơ sở hạ tầng để xác thực các đồng nghiệp nhằm làm cho các cuộc tấn công Sybil khó xảy ra hơn bằng cách chỉ có các đồng nghiệp hợp pháp tham gia vào lớp phủ. Thông thường, những nỗ lực này cố gắng tận dụng cơ sở hạ tầng khóa công khai (PKI) theo cách phi tập trung và sử dụng các thành phần mật mã ngưỡng (ví dụ: chia sẻ bí mật và chữ ký ngưỡng) để đảm bảo sự cộng tác giữa những người được gọi là người dùng trung thực để xác thực các tham gia được phủ lên Thời gian hoạt động của ngang nhau. Điều thú vị là, các động cơ được nêu rõ ràng vượt xa một số nguyên tắc này (ví dụ: [11, 12, 13, 14]), vì nhiều giao thức phi mã hóa trong tài liệu giả định sự tồn tại của một hệ thống xác thực để bảo vệ người dùng hợp pháp (chẳng hạn như SybilGuard và SybilLimit). Do đó, các phương pháp mã hóa được thiết kế để đảm bảo hoạt động thành công của các giao thức đó.

3.3 Thiết bị đáng tin cậy

tiêu đề cấp đầu tiên

4. Kiểm tra tài nguyên

Ngoài phương pháp kiểm tra tài nguyên được sử dụng để chống lại các cuộc tấn công Sybil, ý tưởng cơ bản là kiểm tra xem một tập hợp các danh tính được liên kết với những người dùng được cho là khác nhau có đủ tài nguyên để khớp với số lượng danh tính hay không. Các tài nguyên này có thể bao gồm sức mạnh tính toán, băng thông, bộ nhớ, địa chỉ IP và thậm chí cả thông tin xác thực tin cậy. Mặc dù Douceur đã chứng minh ý tưởng thử nghiệm tài nguyên là không hợp lệ [6], nhưng một số nhà nghiên cứu coi đó là một biện pháp phòng vệ tối thiểu. Tức là phương pháp này không loại bỏ hoàn toàn cuộc tấn công nhưng nó khiến các cuộc tấn công Sybil khó xảy ra hơn.

Về lý thuyết, hầu hết các kế hoạch phòng vệ như vậy đều giới hạn số lượng danh tính phù thủy ở mức nhỏ hơn so với trường hợp không có phòng thủ. Tuy nhiên, trên thực tế, ngay cả một số lượng nhỏ danh tính phù thủy cũng đủ đe dọa khả năng sử dụng và bảo mật của nhiều hệ thống. Ví dụ, như đã đề cập trước đó, tính ẩn danh trong một hệ thống ẩn danh như Tor phụ thuộc vào hai nút trên mỗi mạch. Ngoài ra, 1% danh tính giả trong hệ thống danh tiếng trực tuyến là đủ để bỏ phiếu cho các nút hợp pháp.

4.1 Kiểm tra IP

Một kịch bản thử nghiệm phổ biến liên quan đến việc kiểm tra địa chỉ IP của các đồng nghiệp nhằm xác định vị trí của họ và khớp địa chỉ này với hoạt động của họ. Đặc biệt, nếu một số lượng đáng kể hoạt động bắt nguồn từ cùng một khu vực địa lý cụ thể, thì một số hoạt động đó có khả năng là do tình trạng phù thủy. Ngoài ra, giả định trong các công việc như vậy là lấy địa chỉ IP cho các vùng địa lý khác nhau, điều này không hề rẻ. Ví dụ, Friedman và cộng sự [29] giới thiệu Tarzan, nơi địa chỉ IP của một nút được kiểm tra dựa trên vị trí địa lý của nó trong một hệ thống tự trị cụ thể. Kết quả tương tự đã được trình bày bởi Cornelli và cộng sự trong [30] và [30].

Giả định chính của các công trình này là địa chỉ IP khó có được trong một khu vực địa lý rộng. Tuy nhiên, với những dấu hiệu gần đây về sự tồn tại của các mạng botnet khổng lồ [31] với các máy chủ bị nhiễm được kiểm soát bởi một thực thể quản trị duy nhất và cư trú trong các hệ thống tự trị khác nhau, chắc chắn rằng cơ chế bảo vệ này là vô dụng.

4.2 Chu kỳ chi phí

Một số nghiên cứu và thực tiễn đề xuất chi phí định kỳ như một biện pháp bảo vệ chống lại các cuộc tấn công của Sybil. Cụ thể, các câu đố tính toán [16, 32] và bài kiểm tra Turing (ví dụ: CAPTCHA [33]) được đề xuất làm giải pháp. Tuy nhiên, cũng giống như việc kiểm tra IP sẽ không hoạt động trước những kẻ tấn công kiểm soát botnet, các kế hoạch dựa trên chi phí này cũng vậy. Ngoài ra, đối với các giải pháp giống như CAPTCHA, người ta đã chứng minh rằng những kẻ tấn công Sybil có thể thực hiện kiểm tra CAPTCHA trên các trang web được kiểm soát để người dùng kiểm tra quyền truy cập vào các dịch vụ do kẻ tấn công cung cấp.

tiêu đề cấp đầu tiên

5. Phòng thủ dựa trên biểu đồ xã hội

Trong khi hầu hết các giải pháp được đề xuất trước đây cho vấn đề tấn công sybil trong các hệ thống phân tán đều có những hạn chế và thiếu sót, phòng thủ sybil dựa trên mạng xã hội cố gắng khắc phục những vấn đề này một cách tinh tế. Đầu tiên, hệ thống phòng thủ Sybil dựa trên mạng xã hội hầu hết là các giải pháp phi tập trung cho vấn đề tấn công Sybil, nghĩa là các thiết kế này hoạt động mà không có bất kỳ cơ quan trung ương nào—một thuộc tính quan trọng trong hầu hết các hệ thống phân tán. Mô hình hoạt động phi tập trung này được thực hiện dễ dàng hơn nhờ lý thuyết bước đi ngẫu nhiên, thành phần được sử dụng phổ biến nhất trong các hệ thống phòng thủ này. Thứ hai, những biện pháp bảo vệ này tận dụng sự tin cậy của các liên kết xã hội giữa các nút xã hội để giúp việc cộng tác giữa các nút trung thực trở nên khả thi và dễ dàng. Thứ ba và cũng là cuối cùng, các biện pháp phòng vệ này đã được chứng minh trong một số nghiên cứu là thực tế và hiệu quả trước các cuộc tấn công Sybil với chi phí thấp và hiện chúng được phát triển thêm dưới dạng các thành phần của nhiều dịch vụ, bao gồm Bảng băm phân tán (DHT), bỏ phiếu chống Sybil và để định tuyến mạng di động.

Mặc dù chúng khác nhau rất nhiều về chi tiết thiết kế và hoạt động, nhưng tất cả các biện pháp phòng thủ Sybil dựa trên mạng xã hội đều có chung hai giả định: thuộc tính thuật toán, tức là thuộc tính trộn nhanh và độ tin cậy. Đầu tiên, những biện pháp phòng vệ này dựa trên đặc tính "pha trộn nhanh" của các biểu đồ xã hội. Một cách không chính thức, thuộc tính trộn nhanh của biểu đồ xã hội có nghĩa là các nút "trung thực" trong các biểu đồ như vậy được kết nối tốt và các vùng trung thực không chứa các vết cắt thưa thớt - một phương pháp kết nối hai tập hợp con lớn của các nút trung thực với một số mạng xã hội được chia cắt. Để đơn giản, bản chất trộn nhanh của biểu đồ xã hội có nghĩa là một bước đi ngẫu nhiên từ bất kỳ nút nào trong biểu đồ xã hội sẽ gần đúng với phân phối cố định của chuỗi Markov (MC) được xác định trên biểu đồ sau một vài bước. Trong một mạng có hàng triệu nút, số bước được khuyến nghị là từ 10 đến 15 bước.

Giả định phổ biến thứ hai trong mạch phòng thủ này là sự tin tưởng. Cụ thể, tất cả các biện pháp phòng vệ này đều giả định các giá trị tin cậy tốt trong biểu đồ xã hội cơ bản, ví dụ: bằng chứng là các tương tác trực tiếp giữa các nút. Giả định cụ thể này là cần thiết để suy ra khó khăn khi xâm nhập mạng xã hội với số lượng liên kết xã hội tùy ý của kẻ tấn công. Mặc dù hoạt động của phòng thủ Sybil để xác định chính xác các nút "trung thực" trong biểu đồ xã hội được đảm bảo bằng giả định trộn nhanh và việc xây dựng các sơ đồ tương ứng bằng thuộc tính thuật toán này, nhưng khả năng xác định các nút Sybil chỉ được đảm bảo theo giả định rằng Kẻ tấn công hoặc một nhóm kẻ tấn công kiểm soát một số liên kết giữa chính nó và các nút trung thực khác trong biểu đồ xã hội (các liên kết như vậy được gọi là cạnh tấn công).

Dưới đây chúng tôi sắp xếp một số cách tiếp cận được trích dẫn rộng rãi và được quan tâm để phòng thủ Sybil dựa trên mạng xã hội.

5.1 Sybil Guard

Thiết kế của SybilGuard, do Yu và cộng sự [19, 20], sử dụng các thuộc tính trộn nhanh của các mạng xã hội thuộc sở hữu của niềm tin để phát hiện các nút Sybil. Về mặt kỹ thuật, SybilGuard bao gồm hai giai đoạn: giai đoạn khởi tạo và giai đoạn phát hiện trực tuyến. Trong giai đoạn khởi tạo, mỗi nút xây dựng bảng định tuyến của nó dưới dạng hoán vị ngẫu nhiên của các nút lân cận cho các cặp cạnh đầu vào và đầu ra. Tiếp theo, mỗi nút bắt đầu một bước đi ngẫu nhiên có độ dài w = O(gốc n log n) và truyền nó đến các nút lân cận của nó theo bảng định tuyến được xây dựng bằng cách sử dụng hoán vị ngẫu nhiên. Mọi nút trên đường đi bộ ngẫu nhiên sẽ đăng ký với tư cách là nhân chứng của người khởi xướng bước đi ngẫu nhiên, sau đó đóng vai trò là nhân chứng của nút khi nút đó trở thành nút đáng ngờ. Ngoài ra, tận dụng tính chất hồi cứu của bước đi ngẫu nhiên, mỗi người khởi xướng bước đi ngẫu nhiên sẽ nhận được một danh sách "nhân chứng" (nghĩa là các nút đăng ký khóa công khai của người khởi tạo và nằm trên đường dẫn được xây dựng bởi bước đi ngẫu nhiên của người khởi tạo). đi bộ).

Trong giai đoạn trực tuyến, người xác minh xác định xem nghi phạm có trung thực hay không, như sau. Đầu tiên, kẻ tình nghi gửi địa chỉ của một "nhân chứng" theo lộ trình ngẫu nhiên của nó tới người xác minh. Do đó, trình xác thực so sánh danh sách nhân chứng với danh sách định tuyến trình xác thực của nó. Nếu không có giao điểm giữa hai tập hợp (một sự kiện rất có thể xảy ra), trình xác minh sẽ hủy bỏ và từ chối nghi ngờ. Nếu không, trình xác minh sẽ tiếp tục, yêu cầu so sánh các nút trên giao điểm giữa hai bộ để xác minh rằng nghi phạm đã đăng ký bằng khóa công khai của họ. Nếu nghi phạm được xác minh bởi các nút chéo, trình xác nhận sẽ chấp nhận nghi ngờ hoặc đánh dấu nó là nút Sybil.

5.2 Sybil Limit

Không giống như SybilGuard, sử dụng một bước đi ngẫu nhiên dài duy nhất, SybilLimit đề xuất nhiều bước đi ngẫu nhiên ngắn hơn. Hơn nữa, không giống như SybilGuard (nơi khóa công khai của người xác minh và nghi phạm được đăng ký trên các nút trong biểu đồ xã hội), SybilLimit [18] đề xuất đăng ký các khóa đó trên các cạnh trong biểu đồ xã hội.SybilLimit bao gồm giai đoạn khởi tạo và giai đoạn xác minh trực tuyến .Trong giai đoạn khởi tạo, mỗi nút xây dựng bảng định tuyến của nó bằng cách sử dụng cùng một phương pháp được mô tả trong SybilGuard và thực hiện các bước đi ngẫu nhiên của r = O(gốc n), mỗi lần có độ dài w = O(log n) trong đó O(log n) là 10 đến 15 biểu đồ xã hội của các biểu đồ xã hội hỗn hợp theo thời gian, về mặt lý thuyết được giả định là đủ để lấy mẫu các nút từ một phân phối rất gần với phân phối thống kê. Cạnh của mỗi trong số r bước đi ngẫu nhiên được sử dụng để đăng ký khóa công khai của nút khởi tạo (mỗi cạnh như vậy được gọi là đuôi). đạt được bằng cách đi bộ ngẫu nhiên. Cũng sử dụng tính chất hồi cứu của định tuyến ngẫu nhiên, các nhân chứng đăng ký khóa công khai của nút khởi tạo (có thể là nghi phạm hoặc người xác minh) trả lại danh tính của họ cho nút. Mỗi nút trong biểu đồ xã hội thực hiện cùng một quy trình và mỗi nút bắt đầu bước đi ngẫu nhiên đã đăng ký sẽ tập hợp một nhóm nhân chứng (hoặc người xác thực).

Trong giai đoạn trực tuyến, SybilLimit cũng giống như SybilGuard, nghi phạm gửi mã định danh và địa chỉ của nhân chứng đến nút xác minh, nút này sẽ so sánh các nhân chứng trong danh sách nghi phạm, cố gắng tìm ra xung đột. Nếu xung đột xảy ra trong hai nhóm về phía người xác minh, người xác minh sẽ yêu cầu các nhân chứng có danh tính chung trong cả hai nhóm để xác minh danh tính của nghi phạm và quyết định chấp nhận hay từ chối nghi phạm dựa trên kết quả của quá trình này. Nếu không có giao điểm nào giữa hai (điều này rất khó xảy ra), trình xác thực sẽ hủy bỏ và từ chối nghi phạm bằng cách đánh dấu nó là kẻ tấn công.

Các thành phần chính của các đảm bảo có thể chứng minh được sử dụng để suy luận về SybilLimit cũng giống như trong Sybil Guard. Cụ thể, giả sử rằng độ dài bước đi ngẫu nhiên w là thời gian trộn của đồ thị xã hội, thì nút cuối cùng được chọn trong bước đi ngẫu nhiên như vậy là theo phân phối cố định.

Hơn nữa, cạnh cuối cùng trong bước đi ngẫu nhiên được chọn "gần như" một cách ngẫu nhiên từ các cạnh trong biểu đồ xã hội. Hơn nữa, giả sử r = O(gốc n), nếu hằng số ẩn r0 (trong đó r = r0 × gốc n) được chọn chính xác, giao điểm giữa các cạnh được lấy mẫu của người xác minh và nghi ngờ sẽ tồn tại với xác suất vượt trội . Các tác giả gọi điều kiện này là điều kiện "giao lộ", được sử dụng để đảm bảo giao điểm có xác suất cao của các bước đi ngẫu nhiên của các nút trong vùng trung thực. Giống như SybilGuard, giả sử có g cạnh kẻ tấn công, kẻ tấn công được phép đăng ký khóa công khai của danh tính Sybil của mình trên tối đa gwr = O(g × root n × log n) đuôi (được gọi là đuôi taint). Trong trường hợp này, mỗi cạnh bổ sung giới thiệu một danh tính Sybil O(log n) bổ sung (giả sử kẻ tấn công sử dụng chiến lược tấn công tối ưu bằng cách đăng ký các khóa công khai khác nhau của các danh tính Sybil khác nhau với mỗi đuôi bị nhiễm độc có thể).

Sự an toàn của SybilLimit cũng phụ thuộc rất nhiều vào w. Vì không có cơ chế ước tính giá trị chính xác của các tham số nên việc đánh giá thấp hoặc đánh giá quá cao các tham số này là một vấn đề, như đã trình bày ở trên. SybilLimit cũng cung cấp một "kỹ thuật đo điểm chuẩn" để ước tính tham số này, đồng thời cũng không cung cấp bất kỳ đảm bảo có thể chứng minh nào về chất lượng của ước tính tham số. Cuối cùng, Giới hạn Sybil đảm bảo số lượng nhận dạng sybil được giới thiệu trên mỗi cạnh tấn công miễn là g = o (n / log n). Lưu ý rằng cả SybilGuard và SybilLimit đều không yêu cầu bất kỳ kiến ​​thức toàn cầu nào về mạng xã hội mà nó hoạt động và có thể được triển khai theo cách hoàn toàn phi tập trung.

5.3 Sybil Infer

SybilInfer sử dụng một mô hình xác suất được xác định trên các bước đi ngẫu nhiên (được gọi là quỹ đạo) để suy ra mức độ thực tế của một tập hợp các nút X tạo ra các quỹ đạo như vậy. Giả định cơ bản trong SybilInfer là mỗi nút có chế độ xem toàn cầu và kiến ​​thức về mạng xã hội, mạng được kết hợp nhanh chóng và nút khởi tạo SybilInfer là một nút trung thực. Về mặt kỹ thuật, SybilInfer cuối cùng cố gắng gắn nhãn các nút khác nhau trong biểu đồ là nút trung thực hoặc nút sybil. Trong SybilInfer, mỗi nút trong mạng gồm n nút thực hiện s bước đi, vì vậy tổng số bước đi trong dấu vết chung là s × n. Mỗi dấu vết này bao gồm nút đầu tiên (người bắt đầu bước đi ngẫu nhiên) và nút cuối cùng trong bước đi ngẫu nhiên (đuôi). Không giống như xác suất chuyển tiếp thống nhất (vượt quá mức độ nút) được sử dụng trong SybilGuard và SybilLimit, SybilInfer xác định ma trận chuyển đổi thống nhất trên các nút, xử phạt các nút có mức độ cao hơn. Mục tiêu cuối cùng của hoạt động SybilInfer là tính xác suất P (X = Trung thực | T); nghĩa là tính xác suất mà một tập hợp các nút X có quỹ đạo T là trung thực. Xác suất này được tính bằng định lý Bayes.

SybilInfer lấy mẫu cấu hình trung thực bằng phương tiện kỹ thuật, ban đầu được sử dụng để xác định tính trung thực của một tập hợp các nút từ dấu vết. Việc lấy mẫu này được thực hiện bằng cách sử dụng thuật toán Metropolis-Hasting, trước tiên xem xét một tập hợp X0 và ​​sửa đổi từng tập hợp một bằng cách loại bỏ hoặc thêm các nút vào tập hợp: tại mỗi thời điểm, với xác suất một nút x mới được thêm vào từ X¯0 thành X0 sao cho X ′ = X0 [x hoặc các nút trong X0 bị xóa với xác suất di chuyển trước. Quy trình thực hiện n × log n vòng để thu được các mẫu tốt không phụ thuộc vào X0.

5.4 Sum Up

Không giống như SybilGuard và SybilLimit là các vấn đề tiếp nhận nút chung và phi tập trung theo nghĩa là các nút riêng lẻ không bắt buộc phải mang thông tin toàn cầu về biểu đồ xã hội và Sybil-Infer để suy luận tính trung thực của nút, SumUp [35] cố gắng giải quyết các cuộc tấn công Sybil trong bối cảnh tổng hợp phiếu bầu. Trong trường hợp này, một nút được gọi là người thu thập phiếu bầu mong muốn thu thập phiếu bầu từ các nút khác trong mạng theo cách chống lại Sybil. Nghĩa là, đối với một số phiếu bầu đối tượng nhất định, người thu thập phiếu bầu muốn tăng tỷ lệ phiếu bầu được các nút trung thực chấp nhận, giảm số phiếu bầu chấp nhận của những kẻ tấn công thông qua các cạnh tấn công của họ và xác định những kẻ tấn công khi chúng liên tục có hành vi sai trái. Tại cốt lõi của SumUp, cơ chế phân bổ dung lượng liên kết được sử dụng để phân bổ dung lượng một cách thích ứng cho các liên kết trong biểu đồ xã hội thuộc sở hữu của niềm tin và giới hạn số lượng phiếu bầu được truyền từ phía cử tri sang người thu thập phiếu bầu. Cơ chế phát trực tuyến biểu quyết thích ứng của SumUp sử dụng hai quan sát về hệ thống bỏ phiếu trực tuyến truyền thống: một số lượng nhỏ người dùng trong hệ thống bỏ phiếu cho một đối tượng và - nếu hệ thống bỏ phiếu như vậy được triển khai trên biểu đồ xã hội - chỉ tắc nghẽn Xuất hiện trên chuỗi gần người thu phiếu. Do đó, SumUp đề xuất phân phối một số lượng lớn vé trên các liên kết khác nhau trong biểu đồ xã hội tùy theo khoảng cách của chúng với người thu thập phiếu bầu (theo một số cấp độ được tính toán bằng thuật toán tìm kiếm theo chiều rộng).

Sự hấp dẫn rõ ràng của kỹ thuật này nằm ở yêu cầu tính toán cao của nó: thời gian chạy của một thuật toán điển hình (chẳng hạn như thuật toán Ford-fulkerson) sẽ yêu cầu thứ tự số cạnh được thao tác để thu thập phiếu bầu của một cử tri. Các tác giả của nó đề xuất thêm một heuristic chỉ sử dụng thứ tự các bước đường kính đồ thị, trong đó mỗi nút tham lam chọn một nút cấp cao hơn để kết nối bằng cách sử dụng dung lượng khác không và truyền phiếu bầu cho đến khi đạt được phiếu bầu của người thu thập. Tại bất kỳ thời điểm nào, mỗi nút được phép khám phá các nút khác để tìm các đường dẫn có cùng thứ hạng hoặc thấp hơn, có tính đến việc bước tham lam có thể không dẫn đến dung lượng khác không.

5.5 GateKeeper

GateKeeper [21] mượn các công cụ từ SumUp và SybilLimit để đạt được hoạt động hiệu quả. Cụ thể, nó cố gắng cải thiện hiệu suất của SybilLimit bằng cách kết hợp thành phần phân phối vé của SumUp. Không giống như trong SumUp, nơi các nút được thừa nhận thông qua các đường dẫn khác không từ người bỏ phiếu đến người thu thập, như đã đề cập trước đó, GateKeeper chỉ xem xét giai đoạn "phân bổ vé" của SumUp, trong đó vé được sử dụng bởi bộ điều khiển tuyển sinh để thừa nhận các nút. Các vé như vậy được truyền từ bộ điều khiển đến tất cả các nút giống như trong SumUp. Tuy nhiên, để hạn chế cơ hội nhận được nhiều vé hơn của kẻ tấn công và giảm lợi thế tổng thể của nó, bộ điều khiển trong GateKeeper chọn ngẫu nhiên m nút ngẫu nhiên khác nhau; các nút này được gọi là "nút thuận lợi" khi và chỉ khi Nó sẽ chỉ được phép nếu điểm thuận lợi nhận được một vé fadmitm (trong đó fadmit là một phần của điểm thuận lợi được chọn ngẫu nhiên; 0,2 được sử dụng trong GateKeeper). Do đó, một khi nút được cho phép bởi một phần nhỏ của điểm thuận lợi này, nó sẽ được phép. Để ngăn chặn các cuộc tấn công chi tiêu gấp đôi, Gate Keeper đề xuất sử dụng chuỗi chữ ký mật mã của đường dẫn vé (được truyền đến bộ điều khiển).

5.6 Các DHT khác dựa trên mạng xã hội

SPROUT [36] là một giao thức định tuyến DHT khác sử dụng các liên kết xã hội với biểu đồ xã hội đáng tin cậy để định tuyến thông tin tới người dùng hoạt động trên mạng xã hội. SPROUT thực sự được xây dựng trên Chord [3], và trong Chord thêm các liên kết bổ sung (các mục trong bảng định tuyến) cho những người dùng khác trong mạng xã hội của bất kỳ nút cụ thể nào đang trực tuyến vào bất kỳ lúc nào. Bằng cách này, SPROUT tuyên bố sẽ cải thiện độ tin cậy và phân phối tải của chính Hợp âm.

Whanau ban đầu được đề xuất trong [23], trong đó công việc trong [22] bao gồm phân tích sâu hơn và bằng chứng về hiệu suất và bảo mật cũng như triển khai và trình diễn bảo đảm từ đầu đến cuối.

Trong [1], các tác giả sử dụng đồ thị bootstrap - cây hiển thị các mối quan hệ được giới thiệu trong DHT để chống lại các cuộc tấn công Sybil. Bằng cách sửa đổi hoạt động của Hợp âm DHT quan tâm để mỗi nút trả về địa chỉ của tất cả các nút mà nó biết (bao gồm cả các điểm vào), các tác giả đã nghĩ ra một số chiến lược để giảm tác động của các cuộc tấn công Sybil. Không giống như Chord ban đầu sử dụng độ gần trên Chord làm chỉ số định tuyến (truy vấn), giải pháp này xem xét nhiều chiến lược định tuyến bao gồm đa dạng, kết hợp và ngoằn ngoèo. Các tác giả cho thấy bằng thực nghiệm rằng một chiến lược như vậy có thể được sử dụng để thực hiện tra cứu DHT kháng Sybil hiệu quả hơn khi hoạt động dưới một cuộc tấn công Sybil và nó sẽ yêu cầu ít truy vấn hơn so với yêu cầu đối với thiết kế Hợp âm vanilla.

tiêu đề cấp đầu tiên

6 Kết luận

Tiến độ bỏ phiếu: Ủy ban DAO 4/7 thông qua

Nhóm tiền thưởng nghiên cứu DAOrayaki DAO:

Địa chỉ tài trợ: 0xCd7da526f5C943126fa9E6f63b7774fA89E88d71

Tiến độ bỏ phiếu: Ủy ban DAO 4/7 thông qua

Tổng tiền thưởng: 170 USDC

Các loại nghiên cứu: DAO, Mạng xã hội, Phòng thủ Sybil, Khảo sát

Tác giả gốc: Aziz Mohaisen, Joongheon Kim

Người đóng góp: Natalie, DAOctor @DAOrayaki

người giới thiệu:

người giới thiệu:

[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.