利用工作量证明的P2P信誉女巫攻击防范

李标奇，付晓东，2，岳 昆，刘 骊，2，刘利军，2，冯 勇，2

1(昆明理工大学 信息工程与自动化学院，昆明 650500)2(昆明理工大学 云南省计算机技术应用重点实验室，昆明 650500)3(云南大学 信息学院，昆明 650091)

1 引 言

对等网络(Peer-to-Peer Network)是由许多具备高度匿名性的自治对等体，相互之间发生诸如文件共享等应用而组成的网络[1].P2P网络通常引入信誉度量以帮助用户在众多不同的资源或服务中做出更好的选择.但是，P2P网络作为一种基于身份的系统，容易受到来自身份管理相关攻击的威胁[2].例如，模仿攻击是一种典型的基于身份的攻击，攻击者将自己伪装成另一个身份来实施攻击，以此获利并隐藏真实身份.此外，攻击者还可以创建并操纵多个身份实施攻击以实现其目的，这种攻击就是女巫攻击[1，3](Sybil Attack).

女巫攻击是分布式系统中基于身份的攻击.攻击者可以在P2P信誉系统中创建许多伪造的身份，以操纵目标节点的评分或信誉值.例如，攻击者可以通过控制大量女巫节点(伪造身份节点)多次与目标节点进行交互且给予正面评价以提高目标节点的信誉值，较高的信誉将会为目标节点提供更多服务请求机会.女巫攻击会对P2P网络信誉系统造成严重破坏.

因此，如何有效抵御P2P信誉系统中的女巫攻击成为了一个重要的问题.目前主要可以通过两种类型的方法来缓解此问题，分别为资源证明和行为检测.资源证明要求节点执行单个实体需要耗费一定资源才能够完成的任务，以证明其是拥有独立资源的实体.行为检测(如SybilGuard[4]和SybilLimit[5])通过关系网络或图论来检测可疑节点，并将这些节点与正常节点隔离以消除攻击者的影响.行为检测通常需要与特定的场景(如无人驾驶网络、社交网络)结合，以高效检测攻击者.比较而言，资源证明更适合于一般场景下的P2P信誉系统.

为从源头上抑制女巫攻击，力图使攻击对攻击者而言不经济，换言之即让攻击的效费比最小化，最大限度抑制攻击.鉴于行为检测是在攻击后生效并且依赖于特定的场景，且资源证明方案大多在节点注册时执行一次资源消耗验证，很难大幅度提升攻击者的开销.因此本文引入具备充分鲁棒性PoW(Proof of Work)作为验证任务，让新加入节点在系统接受其身份之前进行验证，并设计了一种多轮验证机制来进一步降低女巫攻击的效用.同时考虑到多轮验证机制，部分女巫节点验证难度增加而被放弃，攻击者采取注册新节点的方式来洗白(whitewashing)其攻击行为的影响.针对次生出的洗白攻击，在攻击者的效用函数中引入洗白攻击影响因子，并通过理论分析和实验对比验证了本文防御模型的防范效果.

本文的工作主要包括以下几点：

1)通过引入工作量证明来实现在P2P信誉系统中抵御女巫攻击以及次生的洗白攻击，并通过实验和理论分析验证本方法的有效性.

2)提出了动态调整难度的验证模型，让验证时间随着节点的当前信誉动态变化，以给攻击者带来更大的攻击开销，进一步限制女巫攻击.

3)对防御模型进行了理论分析，并使用不同的实验参数设置对模型的防御效果进行了全方位的评估.

2 相关工作

女巫攻击的目的通常是篡改信誉系统中目标节点的信誉值.分布式系统中抵御女巫攻击的方法大体上可以分为两种，一类是资源证明，另一类是行为检测.

2.1 资源证明

中心化证书要求受信任的第三方作为证书颁发机构(CA)在节点加入系统之前向其颁发证书，以确保系统中的每个节点都是单个实体.CA可能还要求提供现实世界身份证明，以确保每个实体仅持有一个唯一系统标识符[6].此类解决方案必须是中心化的，由于维护开销高，它们很难规模化扩展.而且中心化网络结构易受单点攻击或单点故障的影响.E.Friedman在注册环节引入了押金或入场费[7].一段时间后，当节点没有不良历史记录时，押金将被退还.注册的过程将给女巫攻击者带来较大的开销，并削弱攻击者持续攻击的动力.

2.2 行为检测

Haifeng Yu基于社交网络提出了SybilGuard[3].他们利用恶意节点可以创建许多身份而身份之间很少建立信任关系的特征，将女巫节点和正常节点之间的关系图进行切割以削弱攻击者的影响.Haifeng Yu还提出了SybilGuard的改进版本SybilLimit[4]，采用图来表示社交网络的特征以进一步限制女巫节点的数量.Tianyu Gao通过基于内容的方法结合深度学习技术在在线社交网络中检测到女巫节点[8].Martin Byrenheid提出了一种领导者选举算法，以区分女巫节点和普通节点[9].G.Danezis 结合社交网络和贝叶斯理论，提出了SybilInfer[10]，给定节点之间的关系结构，使用贝叶斯理论将节点标记为诚实或不诚实.Pradhan.S提出了一种基于区块链的P2P资源共享系统安全框架[11]，他们让区块链的矿工来监视节点的活动，并在区块链中记录活动日志.这意味着所有活动日志都向每个节点开放，没有人可以篡改记录.如果攻击者尝试实施女巫攻击，则系统中的任何参与者都会发现异常活动.这些行为检测模型通过在女巫攻击期间或之后检测女巫节点来抑制攻击.

对于信誉系统中的洗白攻击，主要有两种方法可以防范[12-14]：

1)将假名与真实身份绑定.

2)对所有的新加入成员(包括whitewasher)采用无差别的惩罚机制，提高获取假名的门槛.

对所有节点的无差别消耗性验证相当于第二种方法中对成员的无差别惩罚，能够在一定程度上抑制洗白攻击.

现有的抗女巫攻击模型存在着一些问题与局限.例如，中心化方法将遇到可扩展性和单点故障的问题.行为检测需要特定的场景依托且在攻击发生之后才生效.本文考虑如何抵御一般情况下P2P网络中针对信誉的女巫攻击.从攻击者的目的出发，提升攻击者攻击开销的心理期望从而从源头抑制攻击的发生，因此我们可以采取一些机制来降低攻击的经济性.此外，由于女巫攻击基于身份的特性，现有方法只能抑制理性攻击者.即要求攻击回报大于开销的攻击者，对于不计开销的攻击者很难完全防御[2].因此本文的目标是最大程度地减少攻击的影响.

3 问题定义

在P2P系统中存在许多服务或资源可供用户选择.基于节点历史行为的信誉可帮助用户做出更好的选择，越高的信誉意味着节点能够提供越好的服务或资源.反之，低信誉节点将无人问津甚至被系统惩罚.女巫攻击者的目的就是让某一个(些)节点的信誉按照攻击者的期望发生变化.本文研究中假设攻击者的目的是让某一个目标节点的信誉值尽可能高，因此攻击者将操控女巫节点与目标交互并给予正面评价，以达到提升该节点信誉的目的.

本文考虑存在一个女巫攻击者的P2P资源共享系统.其中，系统中参与资源共享的节点总数为N，资源提供方定义为有限集P={p1，p2，…}，资源接收方定义为有限集R={r1，r2，…}，系统中的每个节点均可以是提供方或接收方.女巫攻击者及其控制的女巫节点定义为有限集S={sA，s1，s2，…，sn}，其中s1，s2，…，sn是被sA所控制的女巫节点，且n≪N.假设sA控制s1，s2，…，sn实施攻击的开销为C，sA，实施攻击所 获取的收益为B.作为攻击者，期望开销尽可能低的同时获取更高的收益.为了方便量化sA的攻击效用，我们定义攻击效用E为：

(1)

随着E的增长，sA将获得更好的攻击效果.我们的目的是要尽可能遏制E的增长，可以从两个方面着手实现这一目标.一是提升sA的攻击开销C，另一方面降低sA的攻击收益B.就注册策略来说，大多数基于难题的验证方法仅提供单次验证(注册时验证)，这就意味着攻击者sA及女巫节点s1，s2，…，sn只需要付出一次性开销，且这些开销可以在未来的收益中均摊.Margolin[15]指出抑制女巫攻击，执行反复多次验证比仅执行单次验证更高效.因此，如果想要提升sA的开销C，我们需要采用多轮次验证的方式.对于降低攻击收益B，行为检测的方法可以找到sA，s1，s2，…，sn等女巫节点之间的联系，以此来限制sA的收益B.同时通过在多轮验证中引入对攻击规模限制的约束机制，来限制sA的收益，以此增加攻击者的攻击难度.

4 基于PoW的女巫攻击防范模型

任何攻击的效用都受成本(时间或金钱)规模的影响.具有无限资源的攻击者可以破坏任何基于身份的系统[5].例如，如果女巫攻击者拥有无限资源，则无论注册过程中付出多高的代价，它都可以篡改任意节点的信誉.因此，本文考虑的防范对象是通常的理智攻击者，不会不计代价实施攻击.

如果没有资源消耗的证明，那也将没有办法验证节点是否为真正的实体[16]；Dewan也指出，可以通过让身份生成耗费资源，让攻击者无力负担生成多个身份的高昂代价，从而抵御女巫攻击[17].为了使女巫攻击变得不经济并通过资源证明抑制攻击，可以通过要求节点完成消耗资源的任务来验证其作为单个实体的合法性.由于女巫攻击者控制系统中的许多女巫节点，所有女巫节点单独完成任务的开销总和将非常大，能够在很大程度上增加攻击者的攻击难度.因此，我们采用资源消耗型的难题作为验证任务，来防止单个实体创造多个虚假身份的女巫攻击.采用难题来验证节点的身份需要满足以下两个原则[3]，一是难题必须同时发布给所有节点，二是难题必须具备难解和容易验证两个属性.此外难题一般分为存储型和计算型两类.存储型难题要求节点存储大量特殊不可压缩的数据，但大量的数据传输会给网络带来负担，不利于P2P网络的效率；计算型难题可以采用本地计算的方式，计算结果为一个值，很容易验证其正确性.受分布式计算验证的启发，我们利用区块链中验证节点的方法实现了对信誉系统中节点的资源消耗验证.大多数区块链，类似比特币[注]https：//bitcoin.org/bitcoin.pdf采用了PoW和PoS(proof of stake)来验证节点的工作量或所持股权，这些协议同时还可以保障区块链免受女巫攻击的威胁[18].该类共识机制能够保证节点在被系统接受之前执行资源消耗的验证，基于SHA256散列算法的PoW具备鲁棒性，攻击者很难利用算法漏洞有效减少验证时间.

4.1 女巫攻击防范模型框架

我们提出了一种基于PoW的防范女巫攻击验证模型，模型的验证流程如图1所示.

图1 防范模型验证流程Fig.1 Process of Sybil resistant model

本文使用P2P资源共享系统作为研究对象，系统中的每个节点都可以作为资源的提供方或者接收方.首先，在系统中随机生成初始节点.其次，初始化所有节点的信誉值.由于使用布尔值表示信誉(如果rj成功下载，pi的信誉值将增加1，否则将增加0)，并使用取平均值法[19]作为信誉值的汇总方法.因此，最合适的节点信誉初始值为0.5(0和1的平均值).另一方面，为了使所有节点根据初始值公平地累积信誉，我们假设所有节点(正常节点，攻击者和女巫节点)的初始信誉值为0.5，即：

Repnormal=Repattacker=RepSybil=0.5

(2)

随后，节点之间将随机两两组合生成交易对.每个交易对都有提供方和接收方两种角色.节点的交易对集为TX={tx1，tx2，…}，tx=(pi，rj)，每个tx将生成pi指向rj的信誉值Rep，Rep将获取的实时信誉增长取平均自累计.例如，如果某一个节点e作为提供方参与了m个交易对的生成，在每一次交易中e得到了Repi(i=1，2，…，m)的信誉值，按照信誉值平均计算法则，则e的当前信誉为：

(3)

在评价模型防范性能前，需要量化攻击者的攻击效果.本文定义EA表示攻击者sA的攻击效用，假设单个节点的平均验证消耗时间为ti，攻击者sA需要消耗nti(n为女巫节点的数量)完成所有女巫节点的验证，也即sA的攻击开销.sA通过控制女巫节点来提升目标节点的信誉值，假设攻击者sA自身为目标节点，每当女巫节点作为提供方与sA生成交易对时，无论交互结果如何，女巫节点都会给予sA的正面的信誉评价，以达到提升目标节点信誉的目的.因此，sA的信誉增量ΔRepattacker即可表示攻击者sA的攻击收益，参照式(1)的效用函数，攻击者sA的效用可以表示为：

(4)

随着ΔRepattacker的增大或ti的减小，EA将增大，意味着sA的攻击效果良好，模型防范效果不佳.通常，sA的攻击开销C随着攻击者控制的女巫节点数量n呈线性增长.为了更加有效防范女巫攻击，本文采用多轮次动态难度调整的PoW验证策略.

多轮次验证使用PoW每隔固定时间间隔T对所有节点同时执行验证，并根据节点的当前信誉值动态调整验证难度.由于sA的目的是提高自身的信誉值，因此我们设置信誉值的不同梯度分化让PoW的验证难度随信誉增加而增加.随着信誉的提高，开销C会大幅度提升，EA会减小.该机制对于非女巫节点，只在合理范围内增加很少的时间消耗，不影响正常节点的活动.

为了尽可能减少验证难度的提升对普通节点的影响，每轮验证之间的时间间隔T应设置为远大于节点执行一次验证的平均时间.对于攻击者sA，女巫节点几乎不可能全部在T以内完成验证，这将导致一部分女巫节点无法完成一轮内的验证.在本模型中，在一轮时间间隔内无法完成验证的节点将被标记为可疑节点.在下一轮的验证中，可疑节点的验证难度将提高一个单位，这将在下一轮验证中给予sA更大的验证开销，并逐渐形成一个恶性循环.算法描述如下：

算法1.多轮次动态难度调节验证算法.

输入：节点集合N，节点初始信誉Repnode=0.5，验证难度d=init_d，验证时间间隔T

输出：通过验证节点集合N*，可疑节点集合S*

IFRepnode≥0.5THEN

d=init_d+1

FOREACHnodei∈NDO

PoW验证(难度init_d)

IF节点验证时间ti

d=init_d

ELSETHEN

S*←nodei

d=init_d+1

ENDIF

ENDFOR

IF本轮验证时间≥TTHEN

执行下轮验证

ENDIF

RETURNN*ANDS*

考虑到sA会抛弃被标记为可以节点增加了验证难度的女巫节点，转而重新注册新的女巫节点加入攻击，实施洗白攻击.本文将给出攻击者实施洗白攻击时重新生成女巫节点的速率作为模型考察洗白攻击的指标，并将生成节点速率纳入到攻击者效用函数中，进而分析和实验验证模型防范洗白攻击的效果.

4.2 女巫攻击防范模型理论分析

我们将在接下来的部分中对上述过程作理论分析.我们假设P2P资源共享系统中的节点总数为N，女巫节点(包括sA)占节点总数的比例为S，ti，满足验证难题函数f(d)，d为验证难度：

ti=f(d)

(5)

因此，sA控制所有女巫节点完成验证的平均时间开销是：

Ts=NSti=NS·f(d)

(6)

为了降低对正常节点的影响且能够一定程度限制sA，考虑极限情况，ti需满足：

f(d)≤ti≤NS·f(d)

(7)

在单轮验证中，无法在ti时间内完成验证的女巫节点个数为：

(8)

这部分节点将被系统标记为可疑节点，并在下一轮验证中执行增加1单位的验证难度，即以d+1难度执行下轮验证.因此，在下轮验证中攻击者sA的平均验证时间开销是：

(9)

考虑与不引入难度增加机制比较，攻击者的平均验证时间开销增加了：

(10)

由于验证算法是PoW，随着难度增加，验证时间近似指数级增长(实验部分给出)，故f(d+1)-f(d)也随着d呈现指数增长.

(11)

(12)

(13)

此后sA的攻击效用为：

(14)

Su=Vs·ti

(15)

等于sA新注册的女巫节点数量，NS在后续轮次中为前次验证中剩余的女巫节点数量.因此，sA在每一轮验证后需要保证此时的Vs≥V°s才能够在下一轮验证时维持本轮的攻击规模.

从实际情况考虑，攻击者实施攻击的收益为正，B≥0，C<∞，且B作为信誉增量，存在一定范围内的随机性，故E不存在确定的最小取值.为了达到更好的防范效果，可以让攻击者的开销C尽可能大.通常文献[6-8]方法对节点采用注册时一次性验证的机制，其攻击者开销C随着操控节点数量n呈线性增长，而多轮动态验证难度调节机制让C随着n呈指数增长，由此我们可以获得更大的C以及更小的EA.

这里将给出PoW作为验证函数的f(d)随着d是呈现指数增长趋势的证明.PoW方案是基于穷举搜索目标Hash值，采用的是十六进制表示的SHA256.我们假设Hash值总共有l位，查找目标Hash的难度是d(目标Hash前d位均为0)，考虑Hash函数的特性，查找目标Hash的概率近似服从均匀分布，因此，找到目标Hash的概率H可以表示为：

(16)

考虑极限情况：

·第1次尝试就找到了目标Hash，查找次数为1

·遍历完所有的可能Hash值才找到目标Hash，查找次数为24l-24(l-d)

(17)

因此，PoW函数的时间复杂度函数T(n)为：

(18)

综上，PoW是一种指数规模的算法，时间规模随着难度呈指数增长.这可以在正常节点和女巫攻击者之间提供更多的时间消耗差异.另一方面，SHA256为PoW算法提供了足够的鲁棒性.攻击者很难通过破解PoW来减少验证时间开销.

5 实验研究

本节展示实验结果，以说明本文提出的女巫攻击防范模型的有效性.所有实验均在配备Intel Core i7 3.6 GHz CPU和16 GB RAM的PC上进行，该算法的开发语言为Python3.7，开发平台为为PyCharm CE.

本文主要通过攻击者的效用EA和开销C来研究模型的防范效果.实验中，设置了10000个节点模拟P2P资源共享系统下的女巫攻击.在攻击模型中，假设一次攻击中仅存在一个攻击者.且基于简单的女巫攻击策略，即女巫节点之间不相互交流.

实验首先生成10000个节点，包括普通节点，攻击者和女巫节点.参考Tien Tuan[20]的女巫攻击防范模型的参数设置，我们假设只有一个攻击者sA，而女巫节点的比例S在1%～5%之间变化.信誉值初始化后，随机选择两个节点来构建交易对tx=(pi，rj)，并为资源提供方P={p1，p2，…}生成信誉值.

在生成tx的同时，每个节点将每隔固定时间执行一次PoW验证.为了确保每个正常节点都可以在合法时间内完成验证，增加模型的容错性，同时能够有力限制女巫攻击的规模，本模型中取间隔时间T=50ti作为多轮时间间隔验证的限制指标.

5.1 效用函数设置

ti的值由多次实验求平均值获得.如图2所示，虚线是通过线性回归拟合散点图得到的时间随难度增长变化趋势，R2接近1.0表示PoW难度与ti的关系近似指数分布.

图2 PoW验证时间与验证难度的关系Fig.2 Relationship between verification time and verification difficulty

在NS=500(女巫节点数)的情况下，第1轮验证Su=450；f(d)在d=5的情况下验证平均时间为2s(100次实验平均值).因此，攻击者注册效率临界值为V°s=225；由于NS∈(100，200，300，400，500)，即V°s∈(25，225)，考虑实际实验值EA∈(0，2)，故a=0.004规格化Vs较为合适，此时用于评估模型的效用函数为：

(19)

5.2 女巫攻击防范效果

为了验证防范模型对攻击者sA的防范效果，本文先考察了随着攻击规模的增长(女巫节点占比1%～5%).如图3所示，当sA未采取洗白攻击策略时(Vs=0)，攻击者效用EA的变化.

图3 攻击效用随攻击者控制节点占比的变化Fig.3 Effectiveness changes with the proportion of Sybil nodes

攻击者sA提升女巫节点数量能够更有效地实施攻击，然而在本模型中，随着S的增加，EA表现出显着的下降趋势.由于每个女巫节点都必须执行验证难题，因此女巫节点的时间消耗都将累加到攻击者sA上，故C将随着S线性增长，但sA的信誉值不可能随时间消耗而线性增长，因此EA将呈现下降趋势.

5.3 洗白攻击防范效果

为验证模型对女巫攻击中的洗白攻击防范效果，对比不同Vs下防御模型对EA的影响，我们选取Vs=0，112.5，225，337.5，500 5种情况，(S=0.05，V°s=225)，如图4所示，在sA经历5轮验证下观察EA的变化.

Vs=0即sA未实施洗白攻击的情况相较于其它实施洗白攻击的情况，EA在显著更高水平范围内波动；当Vs>V°s以后，EA波动范围水平更低，由于此时sA生成新女巫节点后，女巫节点数量大于原始规模，控制更多的节点意味着更高的时间开销，在ΔRepattacker变化不大的情况下，EA相较于之前会更低.

图4 不同Vs情况下5轮验证内的效用变化Fig.4 Effectiveness changes within 5 rounds of verification under different Vs situations

5.4 动态难度变化防范效果

在引入验证难度动态变化机制时，要避免对正常节点的验证产生过大影响.因此，本文考察随着攻击规模S的增长，正常节点和女巫攻击者的时间消耗变化趋势(如图5所示).

图5 攻击者与正常节点的时间消耗变化Fig.5 Changes in time consumption between attacker and normal nodes

随着S的增加，正常节点的验证时间消耗保持在较低的稳定水平，女巫攻击者的时间消耗显着增加.说明了动态验证难度调整机制对正常节点的影响微乎其微.

另一方面，我们需要研究动态难度调整机制是否有效地影响攻击者sA.如图6所示，这里我们使用恒定难度和动态难度两种情况下的攻击者效用进行比较.在动态难度的情况下，我们假设如果当前节点实时的信誉值大于或等于0.5，则该节点的下轮验证难度将增1个单位.

图6 动态难度与难度不变的情况下攻击效用变化Fig.6 Changes of effectiveness in dynamic difficulty and static difficulty

实验结果表明，在攻击规模变化的过程中，采用动态难度调节时的攻击者效用显著低于采用恒定难度时的攻击者效用.因此，动态难度调节机制对攻击者sA的效用有着更为显着影响.

5.5 多轮验证防范效果

为了验证多轮验证相较于传统单次验证的优势，本文在这两者之间进行了对比实验.我们在单次和多轮验证情况下采集了不同难度值下的平均效用(如图7所示).

图7 单次验证与多轮验证情况下攻击效用变化Fig.7 Changes of effectiveness in once and multiple rounds of verification

随着攻击规模增长，多轮验证下的攻击效用始终维持在较低水平，单次验证随着S增长，效用将逐步降低，多轮验证在攻击规模不是很高的情况下对攻击者有更显著的防范效果.综合考虑，多轮验证较单次验证能够更好地防范女巫攻击.

6 总 结

本文针对P2P信誉系统中防范女巫攻击存在的验证力度不足及防御滞后的问题，通过引入PoW作为验证难题来增加女巫攻击者的攻击开销，提出了一种针对P2P信誉系统的女巫攻击以及次生的洗白攻击的防范模型.我们采用固定时间间隔和动态难度调整的多轮验证来进一步限制攻击者，增加其攻击开销，并从理论和实验的角度验证了模型的有效性.

尽管我们进行了多次实验以获取平均数据，但由于Hash计算的随机性，仍然存在一些实验误差.未来的工作包括合理地调整间隔时间以更有效地限制攻击者的行为，以及调整模型以应对系统中存在多个不同的女巫攻击者的情况.