删除或更新信息,请邮件至freekaoyan#163.com(#换成@)

基于社交关系的DHT网络Sybil攻击防御

清华大学 辅仁网/2017-07-07

闂傚倸鍊搁崐鐑芥嚄閸洖绠犻柟鎹愵嚙鐟欙箓鎮楅敐搴″闁搞劍绻堥獮鏍庨鈧俊鑲╃棯閹佸仮闁哄被鍔戦幃銈夊磼濞戞﹩浼�2婵犵數濮烽弫鎼佸磻閻愬搫鍨傞柛顐f礀缁犳壆绱掔€n偓绱╂繛宸簻鎯熼梺鍐叉惈椤戝洨绮欒箛娑欌拺闁革富鍘奸崝瀣亜閵娿儲顥㈢€规洜鏁婚崺鈧い鎺戝閳锋垿鏌涘☉姗堝伐濠殿噯绠戦湁婵犲﹤鎳庢禒杈┾偓瑙勬礃濡炰粙寮幘缁樺亹鐎规洖娲ら獮姗€姊绘担鍛婃儓妞わ富鍨堕幃妯衡攽鐎n亝杈堥梺闈涚箞閸婃牠鎮¢悢鍏肩叆闁哄洦顨呮禍鎯ь渻閵堝繐顩柡浣割煼閻涱噣宕橀埡鍐炬祫闁诲函缍嗛崑鎺懳涢崘銊㈡斀闁绘劖娼欓悘锔剧棯閺夎法效妤犵偛顦垫俊鍫曞幢濞嗘埈鍟庨梻浣烘嚀椤曨參宕戦悙鏍稿寮介鐔蜂化婵炴挻鑹鹃敃锕傚箖閸忛棿绻嗛柛娆忣槸婵洭鏌嶇拠鏌ュ弰妤犵偛娲畷婊勬媴閾忕懓骞€婵犵數濮烽。钘壩i崨鏉戝瀭闂傚牊绋堥弸宥夋煥濠靛棙濯兼繛灏栨櫊閺屾洘绻涢悙顒佺彆闂佺粯鎸堕崕鑼崲濞戙垹绠i柣鎰╁妿缁变即姊虹紒妯烘诞闁衡偓闁秴桅闁告洦鍨奸弫鍐煏韫囧﹥娅呴柛鎾讳憾濮婃椽骞愭惔锝傚闂佸憡姊归悷鈺呮偘椤旈敮鍋撻敐搴℃珮闁轰礁绉电换婵囩節閸屾稑顎涘┑鈥冲级閹稿啿顫忕紒妯诲闁告盯娼у﹢閬嶅箲閵忋倕绠涙い鏂垮⒔閻撳姊虹紒妯虹伇婵☆偄瀚板畷褰掑磼閻愬鍘遍悗鍏夊亾闁逞屽墴瀹曟垿鎮欓崫鍕紱闂侀潧艌閺呮粓鎮¢妷鈺傜厽闁哄洨鍋涢埀顒€婀遍埀顒佺啲閹凤拷
婵犵數濮烽弫鍛婃叏娴兼潙鍨傜憸鐗堝笚閸嬪鏌曡箛瀣偓鏇㈡倷婵犲嫭鍠愮€广儱妫欓崣蹇涙煏閸繍妲归柍閿嬪灴閺屾稑鈽夊鍫濅紣缂備焦顨嗙敮妤佺┍婵犲浂鏁冮柨婵嗘处閸掓稑顪冮妶鍐ㄧ仾婵☆偄鍟幈銊╁焵椤掑嫭鐓忛柛顐g箖閿涘秵淇婇銏狀伃闁哄矉绲鹃幆鏃堫敍濠婂憛锝夋⒑閸濄儱校闁绘濮撮悾鐑藉閵堝懐顔掑銈嗘⒒閺咁偊宕㈤幖浣光拺闁告稑锕ョ粈瀣箾娴e啿娲﹂崐鍫曟煥濠靛棙顥撳ù婊勭矒閺岀喓鈧稒岣跨粻鏍ь熆鐠哄搫顏紒杈ㄥ笧閳ь剨缍嗘禍璺何熼埀顒勬⒑缁洘鏉归柛瀣尭椤啴濡堕崱妤€娼戦梺绋款儐閹瑰洭寮诲鍥ㄥ珰闁哄被鍎卞鏉库攽閿熺姷鐣哄ù婊冪埣瀵顓奸崼顐n€囬梻浣告啞閹稿鎮烽埡浣烘殾妞ゆ牗绋戦閬嶆倵濞戞顏呯椤栨埃鏀介柣鎰级閳绘洖霉濠婂嫮绠炵€殿喗鐓¢、妤呭礋椤掆偓閳ь剙鐖奸弻锝夊箛椤旇姤姣勯梺纭呮閸婂潡寮诲☉銏犖ч柛銉仢閵忋倖顥嗗璺侯儑缁♀偓婵犵數濮撮崐鎼佸汲閿濆棎浜滈幖娣焺濞堟洟鏌曢崶褍顏柛鈺冨仱椤㈡﹢鎮欏顔荤棯濠电姵顔栭崹閬嶅箰閹惰棄钃熼柨鐔哄Т閻愬﹪鏌嶆潪鎵妽闁诲繋绶氬娲川婵犲嫭鍠涢梺绋款儐閹瑰洤顫忕紒妯诲闁告縿鍎虫婵犵數鍋橀崠鐘诲幢閹邦亝鐫忛梻浣虹帛閸旀寮崫銉т笉闁哄啫鐗婇悡娆撴煙椤栧棗鑻▓鍫曟⒑瀹曞洨甯涙慨濠傜秺楠炲牓濡搁妷搴e枔閹风娀骞撻幒婵囨祰闂傚倷鐒﹂幃鍫曞磹瑜忕划濠氬箻鐠囪尪鎽曢梺缁樻濞咃綁鎯屽▎鎾寸厵缂佸鐏濋銏ゆ煙椤旂晫鎳囨慨濠勫劋鐎电厧鈻庨幋鐘樻粎绱撴担鍝勑i柣妤佹礋椤㈡岸鏁愭径妯绘櫇闂佸啿鐏堥弲婊堟倵婵犳碍鈷戠憸鐗堝笒娴滀即鏌涘Ο鍝勨挃缂侇喗鐟╁畷鐔碱敍濞戞帗瀚奸梻浣告贡鏋繛瀵稿厴閸┿儲寰勯幇顓犲幐闂佸壊鍋掗崑鍕櫠鐎电硶鍋撶憴鍕缂傚秴锕ユ穱濠傤潰瀹€濠冃┑鐘愁問閸ㄤ即濡堕幖浣歌摕婵炴垶菤濡插牊鎱ㄥΔ鈧悧濠囧极閸撗呯=濞达絽鎼牎闁汇埄鍨抽崑銈夊春閳ь剚銇勯幒鍡椾壕闂佽绻戦懝楣冣€﹂崹顕呮建闁逞屽墴楠炲啳顦圭€规洖宕湁闁哄瀵ч崰妯尖偓瑙勬礈鏋摶鏍归敐澶嬫珳闁汇儺浜缁樻媴娓氼垱鏁梺瑙勬た娴滎亜顫忔禒瀣妞ゆ牗绋掑▍鏍⒑閸濆嫮鈻夐柛妯圭矙閹ょ疀濞戞瑧鍘遍梺鏂ユ櫅閸燁垳绮堥埀顒€顪冮妶蹇曞矝闁哄棙绔糴婵犵數濮烽弫鍛婃叏娴兼潙鍨傞柛锔诲幘缁€濠傗攽閻樺弶鎼愰柣鎺戠仛閵囧嫰骞掑鍫濆帯闂佹剚鍨卞ú鐔煎蓟閺囥垹骞㈡俊銈傚亾闁哄棴缍侀弻锛勪沪閸撗勫垱濡ょ姷鍋炵敮锟犵嵁鐎n喗鍊婚柛鈩冿供濡冣攽閿涘嫬浜奸柛濠冪墱閺侇噣鎮欓崫鍕崶闂佸綊鍋婇崰姘舵儗濞嗗繆鏀介柣妯哄级婢跺嫰鏌涚€n偄濮嶉柡宀嬬秮婵偓闁靛繆鍓濆В鍕煛娴e摜澧︽慨濠勭帛閹峰懐绮欓幐搴♀偓顖氣攽閻橆喖鐏柨鏇樺灩閻g兘顢涘☉姗嗗殼闁诲孩绋掗敋濞存粠鍨跺娲川婵犲嫮鐣垫繝娈垮灥妞存悂骞嗛弮鍫濐潊闁挎稑瀚倴濠碉紕鍋戦崐鏍礉濡ゅ懎绐楅幖娣灮椤╂彃螖閿濆懎鏆為柣鎾寸洴閺屾盯濡烽敐鍛瀴闂佹眹鍔嶉崹鍧楀蓟閿濆鍋勯柛娆忣槹閻濇棃姊虹€圭姵顥夋い锔炬暬閻涱喖螣閼测晝顦╅梺缁樏畷顒勵敆閵忊€茬箚闁绘劦浜滈埀顒佺墪鐓ゆ繝闈涙閺嬪秹鏌¢崶鈺佷憾缂傚倹宀搁悡顐﹀炊閵娧€妲堥悗鐟版啞缁诲啴濡甸崟顖氱婵°倐鍋撻柛鐕佸灦椤㈡瑩鏁撻敓锟�20濠电姴鐥夐弶搴撳亾濡や焦鍙忛柣鎴f绾惧鏌eΟ娆惧殭缂佺姴鐏氶妵鍕疀閹炬惌妫″銈庡亝濞叉ḿ鎹㈠┑瀣棃婵炴垵宕崜鎵磽娴e搫校闁搞劌娼″濠氬Χ閸℃ê寮块梺褰掑亰閸忔﹢宕戦幘婢勬棃鍩€椤掑嫬鐓濋柡鍐ㄧ墕椤懘鏌eΟ鐑橆棤闁硅櫕鎹囬妶顏呭閺夋垹顦ㄩ梺鍐叉惈閿曘儵鏁嶉崨顖滅=闁稿本鐟чˇ锔姐亜閿旇鐏︽い銏″哺椤㈡﹢濮€閻橀潧濮︽俊鐐€栧濠氬磻閹惧绡€闁逞屽墴閺屽棗顓奸崨顖ょ幢闂備胶绮濠氬储瑜斿鍛婄瑹閳ь剟寮婚弴銏犻唶婵犲灚鍔栨晥闂備胶枪妤犲摜绮旇ぐ鎺戣摕婵炴垯鍨归崡鎶芥煏婵炲灝鍔氭い顐熸櫊濮婄儤瀵煎▎鎴犳殸缂傚倸绉撮敃顏堢嵁閸愩剮鏃堝礃閳轰焦鐎梻浣告啞濞诧箓宕f惔銊ユ辈闁跨喓濮甸埛鎴︽煕濠靛棗顏い銉﹀灴閺屾稓鈧綆鍋呭畷灞炬叏婵犲啯銇濈€规洦鍋婂畷鐔煎垂椤愬诞鍥ㄢ拺闁告稑锕ラ埛鎰版煟濡ゅ啫鈻堟鐐插暣閺佹捇鎮╅搹顐g彨闂備礁鎲″ú锕傚礈濞嗘挻鍋熷ù鐓庣摠閳锋垿姊婚崼鐔恒€掔紒鐘冲哺閺屾盯骞樼€靛摜鐤勯梺璇″枓閳ь剚鏋奸弸搴ㄦ煙闁箑鏋ゆい鏃€娲樼换婵嬪閿濆棛銆愬銈嗗灥濡稓鍒掗崼銉ョ劦妞ゆ帒瀚崐鍨箾閸繄浠㈡繛鍛Ч閺岋繝鍩€椤掑嫬纭€闁绘垵妫楀▓顐︽⒑閸涘﹥澶勯柛瀣浮瀹曘儳鈧綆鍠楅悡鏇㈡煛閸ャ儱濡兼鐐瓷戞穱濠囧矗婢跺﹦浼屽┑顔硷攻濡炶棄鐣烽锕€绀嬫い鎰枎娴滄儳霉閻樺樊鍎滅紓宥嗙墪椤法鎹勯悜妯绘嫳闂佺ǹ绻戠划鎾诲蓟濞戙埄鏁冮柨婵嗘椤︺劑姊洪崫鍕闁告挾鍠栭獮鍐潨閳ь剟骞冨▎鎾搭棃婵炴垶顨呴ˉ姘辩磽閸屾瑨鍏屽┑顔炬暩閺侇噣鍨鹃幇浣圭稁婵犵數濮甸懝楣冩倷婵犲洦鐓ユ繝闈涙閸gǹ顭跨憴鍕婵﹥妞介幊锟犲Χ閸涱喚鈧儳鈹戦悙鎻掔骇闁搞劌娼¢獮濠偽旈崘鈺佺/闁荤偞绋堥崜婵嬫倶娓氣偓濮婅櫣娑甸崨顔兼锭闂傚倸瀚€氭澘鐣烽弴銏犵闁挎棁妫勯埀顒傛暬閺屻劌鈹戦崱娑扁偓妤侇殽閻愮榿缂氱紒杈ㄥ浮閹晛鐣烽崶褉鎷伴梻浣告惈婢跺洭宕滃┑鍡╁殫闁告洦鍋€濡插牊绻涢崱妤佺濞寸》鎷�
基于社交关系的DHT网络Sybil攻击防御
韩心慧(),肖祥全,张建宇,刘丙双,张缘
Sybil defenses in DHT networks based on social relationships
Xinhui HAN(),Xianquan XIAO,Jianyu ZHANG,Bingshuang LIU,Yuan ZHANG
Institute of Computer Science and Technology, Peking University, Beijing 100871, China

摘要:
HTML
输出: BibTeX | EndNote (RIS) 背景资料
文章导读
摘要Sybil攻击通过恶意伪造大量虚假身份,破坏对等网络(P2P)网络中正常节点的寻路过程,是分布式Hash表网络(distributed Hash table, DHT)中主要的安全威胁。该文利用社交网络中社交关系的高可信度以及伪造难度大等特点,设计了Social-DHT方法以缓解DHT网络中Sybil攻击的影响。该方法采用基于社交关系的随机游走策略以构建相对可信的路由表,继而可以有效抵御Sybil恶意节点的影响,实现安全、高效的寻路过程。此外对该方法建立模型,对路由表的可信性和寻路阶段的成功概率进行了理论分析。仿真实验表明: 在有10 000条攻击边的情况下节点路由表中Sybil节点比例不超过3%, 搜索成功率则能够达到99%, 并且在搜索速度和带宽开销等方面优于已有的算法。

关键词 对等网络(P2P),分布式Hash表(DHT),Sybil攻击,社交网络
Abstract:The Sybil attack, which creates a large amount of fake node identities to break the normal routing process in the peer-to-peer (P2P) networks, is the main threat faced by distributed networks. A Social-DHT protocol was developed using the properties of social relationships to mitigate Sybil attacks in distributed Hash table (DHT) networks using random walks over the social relationships. In addition, a model is given using a formalized definition to analyze the successful probability of searches. Simulations show that the Social-DHT routing table includes less than 3% of the Sybil nodes when there are 10000 attack edges and the successful search ratio reaches 99%, which is better than existing methods.

Key wordspeer-to-peer (P2P)distributed Hash table (DHT)Sybil attacksocial networks
收稿日期: 2013-12-01 出版日期: 2015-04-16
ZTFLH: 
基金资助:
引用本文:
韩心慧, 肖祥全, 张建宇, 刘丙双, 张缘. 基于社交关系的DHT网络Sybil攻击防御[J]. 清华大学学报(自然科学版), 2014, 54(1): 1-7.
Xinhui HAN, Xianquan XIAO, Jianyu ZHANG, Bingshuang LIU, Yuan ZHANG. Sybil defenses in DHT networks based on social relationships. Journal of Tsinghua University(Science and Technology), 2014, 54(1): 1-7.
链接本文:
http://jst.tsinghuajournals.com/CN/ http://jst.tsinghuajournals.com/CN/Y2014/V54/I1/1


图表:
社交网络与DHT网络的映射关系示意图
Social-DHT节点行为流程图
在社交关系网络图中的一次随机游走示意图
不同步长的随机游走终点概率累积分布图
7比特等分后各ID子空间buddy节点数量分布图
一轮更新后获得buddy节点数量统计图
一轮更新后获得sibling节点数量统计图
Sybil攻击下目标搜索成功率累积分布图
实验方法 随机游走
步长ω
路由表参数 查询轮次 询问节点
Whanau 5 rf=100
rd=100
rs=100
20 20
Social-DHT 5 rb=128
rs=25
5 8


Social-DHT与Whanau对比实验参数
Social-DHT与Whanau路由表恶意节点比例对比
Social-DHT与Whanau建立路由表带宽开销对比
Social-DHT与Whanau获得数据所需消息量对比


参考文献:
[1] Steinmetz R. Peer-to-Peer Systems and Applications [M]. Berlin, Germany:Springer, 2005.
[2] Ratnasamy S, Francis P, Handley M, et al.A Scalable Content-Addressable Network [M]. Danvers, USA:Association for Computing Machinery, 2001.
[3] Rowstron A, Druschel P. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems [C]// Middleware 2001. Berlin, Germany:Springer, 2001: 329-350.
[4] Stoica I, Morris R, Karger D, et al.Chord: A scalable peer-to-peer lookup service for internet applications [J]. ACM SIGCOMM Computer Communication Review, 2001, 31(4): 149-160.
[5] Maymounkov P, Mazieres D. Kademlia: A peer-to-peer information system based on the xor metric [C]// Peer-to-Peer Systems. Berlin, Germany: Springer, 2002: 53-65.
[6] Douceur J R. TheSybil attack [C]// Peer-to-Peer Systems. Berlin, Germany: Springer, 2002: 251-260.
[7] Castro M, Druschel P, Ganesh A, et al.Secure routing for structured peer-to-peer overlay networks[J]. ACM SIGOPS Operating Systems Review, 2002, 36(SI): 299-314.
[8] WANG Honghao, ZHU Yingwu, HU Yiming. An efficient and secure peer-to-peer overlay network [C]// The IEEE Conference on Local Computer Networks 30th Anniversary. Washington DC, USA: IEEE Press, 2005: 764-771.
[9] Bazzi R A, Konjevod G. On the establishment of distinct identities in overlay networks[J]. Distributed Computing, 2007, 19(4): 267-287.
[10] ZHANG Ren, ZHANG Jianyu, CHEN Yu, et al.Making eclipse attacks computationally infeasible in large-scale DHTs [C]// Performance Computing and Communications Conference (IPCCC), 2011 IEEE 30th International. Washington DC, USA: IEEE Press, 2011: 1-8.
[11] Rowaihy H, Enck W, McDaniel P, et al. Limiting sybil attacks in structured peer-to-peer networks [C]// IEEE Infocom Mini-Symposium. Washington DC, USA: IEEE Press, 2005.
[12] Mittal P, Caesar M, Borisov N. X-Vine: Secure and pseudonymous routing using social networks [Z/OL]. (2013-10-13), http://arxiv.org/pdf/1109.0971.pdf.
[13] Lesniewski-Lass C, Kaashoek M F. Whanau: Sybil-Proof Routing with Social Networks, Technical Report MIT-CSAIL-TR-2009-045 [R]. Cambridge, USA: Massachusetts Institute of Technology, 2009.
[14] Lesniewski-Lass C, Kaashoek M F. Whanau: A sybil-proof distributed hash table [C]// 7th USENIX Symposium on Network Design and Implementation. Boston, USA: ACM SIGCOMM Computer Communication Review, 2010: 3-17.
[15] Marti S, Ganesan P, Garcia-Molina H. SPROUT: P2P routing with social networks [C]// Current Trends in Database Technology-EDBT 2004 Workshops. Berlin, Germany: Springer, 2005: 425-435.
[16] Hardt D. The OAuth 2.0 Authorization Framework [Z/OL]. (2013-10-13), http://tools.ietf.org/html/rfc6749.
[17] Sina Corp. Sina Weibo Oauth API [Z/OL]. (2013-10-13), http://open.weibo.com/wiki/Oauth.
[18] Renren Corp. Renren Oauth Wiki [Z/OL]. (2013-10-13), http://wiki.dev.renren.com/wiki/Authentication.
[19] Tencent Corp. Tencent Weibo Oauth Wiki [Z/OL]. (2013-10-13), http://wiki.open.t.qq.com/index.php/OAuth授权说明.
[20] Mitzenmacher M, Upfal E. Probability and computing: Randomized algorithms and probabilistic analysis [M]. Cambridge, UK: Cambridge University Press, 2005.
[21] Viswanath B, Mislove A, Cha M, et al.On the evolution of user interaction in facebook [C]// Proceedings of the 2nd ACM Workshop on Online Social Networks. Danvers, USA: Association for Computing Machinery, 2009: 37-42.


相关文章:
[1]朱涵钰,吴联仁,吕廷杰. 社交网络用户隐私量化研究: 建模与实证分析[J]. 清华大学学报(自然科学版), 2014, 54(3): 402-406.

相关话题/网络 实验 概率 比例 空间