在线社会网络中Sybil攻击检测方法

技术领域

本发明涉及在线社会网络中Sybil攻击的检测方法，适合网络水军检测、 电子选举和投票表决、在线社会网络推荐等多种应用领域。

背景技术

Sybil攻击指网络中恶意用户通过多次注册获得多重身份，并利用这些 身份在网络事务中占据支配性地位，从而影响网络正常功能，破坏网络秩 序。

Sybil攻击广泛存在于各种使用推荐或共享机制的网络应用和网络系统 中。典型的如在线投票系统中，通过多次注册重复投票，扰乱公平秩序， 操纵得票结果；在电子商务网站中，利用多重身份制造虚假交易和虚假评 价，误导消费者判断，引发不良竞争；在在线社交网站中，使用多个账户 进行消息转发和评论，制造“热门话题”，进行谣言传播。

随着在线社会网络的兴起，个人逐渐在网络中凸显，扮演越来越重要 的角色。通过构建个人页面、参与网络活动，每个人都成为了网络中的一 部分。人们不仅通过网络相互交流，也进行积极共享，这主要表现在资源 和知识两个方面。无论是资源共享还是知识共享，实际上都使用了推荐机 制，每一个用户都可以基于自己的知识背景进行推荐，网络应用或网络系 统将所有用户的推荐进行整合，利用群体智能得出最终评价结果的一般性 结论，并为其他用户的决策提供支持。推荐机制一个很重要的原则在于用 户身份的对等性，即用户之间是公平的，用户推荐的权重是一致的，这样 才能保证最终的结果体现出大多数用户的意愿，使推荐机制发挥作用。由 于Sybil攻击的存在，虽然用户之间仍然表现出公平性，但由于攻击者掌握 了多重身份，如果将这些身份融合为同一用户，那么该用户所占的权重远 大于正常用户的权重，且正比于该用户所掌握的Sybil身份的数量。Sybil攻 击打破了用户身份的公平性，使得攻击者在推荐过程中占据更多优势甚至 可以直接操纵最终结果。

Sybil攻击广泛存在于多种网络应用中，不但破坏了网络应用原有功能， 误导用户并造成用户对网络的不信任，还可能带来多重恶意严重后果。例 如在视频、图片网站利用Sybil攻击推广暴力、色情等非法内容；上传附带 恶意病毒木马程序的文件，并通过Sybil攻击欺骗人们下载；在微博、微信 等在线社会应用上利用Sybil攻击进行谣言传播，不但可以损害他人声誉， 甚至能够引发社会性恐慌。

解决Sybil攻击最有效方式是控制用户注册，例如要求使用实名制方式 进行注册。这样用户账号与用户真实身份一一关联，加大了Sybil账号注册 的难度，使单一用户无法继续操纵无限多的Sybil账号，从而减弱或消除Sybil 攻击。但由于这种方式要求用户在网络上使用和存储自己的实名信息，一 方面可能引发用户隐私泄漏，另一方面可能使用户产生顾虑，从而造成用 户流失，因此难以在实际中部署和应用。

由于无法从根源上消除Sybil攻击，当前主要从攻击检测入手，发现已 爆发的Sybil攻击和潜在的Sybil威胁。由于攻击形式和组织方法的不同，传 统的检测方法例如入侵检测等很难有效检测出Sybil攻击。Sybil攻击检测的 目的在于发现Sybil节点群，主要依据成员间社会关系的差异性。由于Sybil 节点主要被用来发动Sybil攻击，而很少用于日常交互，因此造成与正常节 点关系的缺失，在关系图上表现出局部紧密，与外界联系松散的最小割特 征。这一特征Yu在SIGCOMM06的SybilGuard中最早提出，并作为Sybil攻 击检测的基本假设被延用。SybilGuard使用随机路由的方式对到达验证者节 点的路径进行选择，并以最终的可达路径数目作为每个节点判断标准。 SybilLimit对SybilGuard进行了改进，但二者都存在误判率和漏判率高的问题。 Tran的GateKeeper利用社会关系在节点间进行票据分发，以最终每个节点 获得的票据数量作为判断标准，提高了检测的准确率，但为了确定初始阶 段发布的票据总量，需要检测系统多次迭代运行分发操作，加大了系统运 行时间和资源消耗。且这几种方法为了对路径或票据进行验证，都需要额 外关键基础设施的支持。

如何利用轻量级部署方式获得高准确度的攻击检测结果是本领域技术 人员极为关注的技术问题。

发明内容

本发明要解决的技术问题是提供一种在社会网络中Sybil攻击检测方 法。

技术方案是：选取某一节点为验证节点，以成员关系为依据进行路径 通告和传播，构建到达验证节点的关系路径；传播过程中采用基于路径k 相似的路径选择方法剔除冗余路径和共享路径；最终以每个节点可信路径 的数量作为验证标准，由验证节点对其它节点是否为Sybil节点进行验证。

使用N代表网络中节点个数，对于路径P₁＝<u₁，u₂，u₃...u_m>，(1≤m≤ N)和路径P₂＝<v₁，v₂，v₃...v_n>，(1≤n≤N)，定义节点相似和路径相似如 下，m是路径P₁的长度，n是路径P₂的长度。

定义1.节点r相似：对于1≤r≤min(m，n)（min(m，n)表示取m,n中 较小的数），如果P₁的第r个节点u_r和P₂的第r个节点v_r是同一节点，那么P₁和P₂是节点r相似的。

定义2.路径k相似：设1≤k≤min(m，n)，如果对任意1≤j≤k，P₁和 P₂都是节点j相似的，那么P₁和P₂是k相似的。如果满足P₁和P₂是k相似的，k 最大取值为K,(1≤K≤min(m，n))，那么P₁和P₂是(K+1)差异的，差异系 数为(K+1)。

由定义1和定义2可知，若两条路径是k相似的，那么这两条路径第k个 节点之前的节点序列都一样；如果两条路径是K差异的，那么这两条路径 的前(K-1)个节点序列都一样，而且如果路径长度都大于K，那么它们的 第K个节点为不同节点。

本发明具体技术方案包括以下步骤：

第一步，选取某一节点为验证节点，标记为v，任意节点都可以作为验证节 点，除验证节点之外的所有节点都为待验证节点，各节点进行初始化 操作，方法是：

1.1所有节点定义自己的加解密算法，算法无需对外公开，可以使用 DES（Data Encryption Standard）、AES（Advanced Encryption Standard）、 MD5、RSA等经典算法，也可以使用自定义算法。

1.2验证节点创建关系表，并定义任意的字符串T₀作为验证字符串； 所有待验证节点创建关系表和路径表。其中关系表存储已经与自 己建立起可信关系的其他节点，表中每一项都是一个节点标识； 路径表用来存储到达验证节点的可达路径，表中每一项是一个二 元组，表示为<P_i，Sign(P_i)>，(1≤i≤M)，其中M为网络中总路径 数，P_i表示第i条路径，Sign(P_i)表示P_i的标识。每一条路径都是 一个有序的节点序列，每一个标识是一个加密后的字符串。关系 表由各节点根据历史经验自己定义，路径表初始为空。

第二步，由验证节点v对其它节点进行可达路径通告，方法是：

2.1v发送通告信息M₀给v的关系表中所有成员。通告信息M₀的内容 包括路径、标识、可接受的最大差异系数K以及可接受的最大路 径长度L。由于v就是验证节点，因此路径为{v}；以v的加密算法 对T₀加密作为路径{v}的标识；可接受的最大差异系数K和可接受 的最长路径长度L都由验证节点自己确定，实验给出的参考取值 为K＝1，L＝7。

2.2接收到了通告信息M₀的节点u_j首先对M₀中路径的有效性进行检 查。设M₀中路径为P，标识为Sign(P)，如果满足以下条件，则判 定P相对于u_j是有效的：

(1)P的长度小于可接受的最长路径长度L；

(2)P与u_j的路径表中的任一路径的差异系数小于K，或者虽然 u_j的路径表中存在与P差异系数大于或等于K的路径，但P更短。 如果P相对于u_j是有效的，执行步骤2.3，否则转2.5。

2.3u_j将P添加到自己的路径表中，并删除路径表中与P的差异系数大 于K且比P长的其它路径。

2.4u_j构造新的路径和标识。u_j将自己添加到P的尾部构成新的路径P′， 如果P＝{u₁，u₂...u_l}，(1≤l)，那么P′＝{u₁，u₂...u_l，u_j}，并使用 u_j自己的加密算法Crypt_uj()对Sign(P)加密构成新的路径标识 Sign(P′）＝Crypt_uj(Sign(P))。

2.5u_j发送新的通告信息。使用原通告信息M₀中K和L的值，与新的 路径P′和标识Sign(P′)一起构成新的通告信息M₁并发送给u_j关系 列表中的成员，并发送通告提醒给v，转步骤2.6。通告提醒的内 容为u_j的节点标识u_j，仅用来通知v通告仍在进行。

2.6如果u_j接收到新的通告信息M₁，将M₀的内容更新为M₁，转步骤 2.2，否则转步骤2.7。

2.7验证节点v根据网络规模定义提醒时间间隔，并初始化提醒计时 器并开始计时。设置提醒时间间隔τ＝10*logN秒，如果在τ时 间内接收到了通告提醒，那么重置计时器为零并转步骤2.2；如果 计时器超出提醒时间间隔且没有接收到任何通告提醒，那么通告 结束，执行第三步。

第三步，所有待验证节点发送包含可达路径的验证请求给验证节点v，使所 有的可达路径聚集到验证节点v处，然后由验证节点v检查所有可达路 径是否可信。方法是：

3.1所有待验证节点采用步骤2.4的方法构造新的路径和标识，并将 新的路径和标识发送给验证节点v。

3.2接收到来自所有待验证节点的验证请求后，验证节点v对所有路 径按照长度排序，并依次进行路径可信性验证，目的在于防止某 些节点私自捏造不存在的路径或篡改路径，验证方法为：

3.2.1验证节点v将接收到的所有路径按照长度排序，加入待验证表 unverified_table中。unverified_table的数据结构与路径表 相同，每一项都由路径和标识组成，区别是unverified_table 是按照路径长度排序的。

3.2.2从unverified_table中取出最短路径P_s及其对应的标识 Sign(P_s)，由通告流程可知P_s的长度一定大于等于2，设 P_s＝{u₁，u₂...u_t}，(2≤t≤N)。首先验证P_s是否可信，方法为：

3.2.2.1如果u₁为验证节点v，转3.2.2.2，否则转3.2.2.8；

3.2.2.2如果P_s的长度等于2，转3.2.2.3；否则转3.2.2.4；

3.2.2.3如果u₂存在于v的关系表中，由 u₂利用自己的解密算法()对Sign(P_s)解密，并 令结果$\mathrm{Res}\left(P_s\right)={\mathrm{Decrypt}}_{u_2}\left(\mathrm{Sign}\left(P_s\right)\right),$其中 （）为u₂的解密算法。如果结果Res(P_s)等于 初始字符串T₀，则验证成功，转3.2.2.7；否则验证失败 转3.2.2.8；如果u_t不存在于v的关系表中，说明有人假冒 路径，验证失败，转3.2.2.8；

3.2.2.4检查P_s-1＝{u₁，u₂，...，u_t-1}是否存在于verified_table 中，如果不存在，验证失败转3.2.2.8；否则进入步骤3.2.2.5；

3.2.2.5将P_s-1和Sign(P_s)发送给P_s的最末端节点u_t；

3.2.2.6u_t首先检查P_s-1＝{u₁，u₂...u_t-1}是否在u_t的路径表中， 然后使用u_t的解密算法对Sign(P_s)进行解密， 方法为$\mathrm{Res}\left(P_s\right)={\mathrm{Decrypt}}_{u_t}\left(\mathrm{Sign}\left(P_s\right)\right),$并将结果与 P_s-1的标识Sign(P_s-1)对比，如果Res(P_s)＝Sign(P_s-1) 则说明该路径未被篡改过，返回正反馈消息给v，转 3.2.2.7；否则说明路径被篡改，给出负反馈，转3.2.2.8。

3.2.2.7验证成功，转3.3；

3.2.2.8验证失败，转3.4。

3.3将P_s从unverified_table移动到verified_table中，转3.5。

3.4将P_s从unverified_table中删除，转3.5。

3.5如果unverified_table非空，转步骤3.2.2，否则转第四步。

第四步，由验证节点根据每个节点的可信路径数量判断该节点是否为Sybil 节点。

4.1验证节点v将所有提交验证请求的节点加入待验证集合 unverified_set，初始化Sybil节点集合sybil_set为空集，并设定 判断阀值α。α的值是可变的，可以根据需求自由调整，较低的取 值会接受更多的正常节点，但同时也可能使Sybil节点被接受，从 而增高漏检率；较高的取值会拒绝更多的Sybil节点，但同时也可 能使正常节点被拒绝，从而使误检率增高。我们通过多次试验拟 合出α的最佳经验取值为α＝15*(logN)²。

4.2从unverified_set取出一个节点，设为u，假设其提交的路径表为 path_table(u)，计算可信路径集 trusted_table(u)＝path_table(u)∩verified_table。如果 trusted_table(u)中元素个数大于α则转4.3，否则转4.4。

4.3验证成功即u不是Sybil节点，将u从unverified_set删除，转4.5。

4.4验证失败即u是Sybil节点，将u从unverified_set删除并加入 sybil_set中，转4.5。

4.5如果unverified_set非空，转4.2，否则转4.6。

4.6结束，集合sybil_set中的节点都为Sybil节点，。

采用本发明能达到以下有益效果：

对于Sybil用户，由于受时间、精力等的影响，无法使用所有账户进 行日常的交互活动，通常只会使用其中某一个或少数几个，造成了其它账 号关系的匮乏。同时，由于同时使用这些账号进行Sybil攻击，这些账号 之间形成了紧密的关联。这些特征表现在关系图上，就呈现出内部联系紧 密，与外部联系松散的结构，这造成Sybil节点到达其它正常节点的可达 路径缺失。本发明以此为检测依据。

在第一步中，各节点定义了自己的加解密算法，这些算法用来构建路 径的标识，在第三步中根据标识对所有路径进行可信性验证，从而保证路 径的真实性与正确性，防止节点私自伪造、篡改路径。

在第二步中，通过验证节点对可达路径的宣告以及节点间对可达路径 的传播，各节点都建立起了到达验证节点的路径。对Sybil节点来说，由 于关系的匮乏，因此其路径都来自于少数几个节点，称这些路径为冗余路 径。通过定义K相似路径并在传播时对路径有效性进行检查，可以有效消 除冗余路径，使得Sybil节点的关系匮乏表现在有效路径的匮乏上，为第 四步的检测提供基础。

第三步将所有节点的可达路径聚集到验证节点，并由验证节点对这些 路径进行真实性检查。这样避免节点为了通过验证而私自伪造路径或篡改 路径；使用每个节点自定义的加解密算法对路径进行标识，无需依靠关键 基础设施或其它辅助设备的支持，具有轻量级、易部署的优势，更适合网 络环境。

第四步利用每个节点的可达路径数量判断该节点是否为Sybil节点， 由于真实还原并利用了节点关系的差异性，具有准确性高、误报率低等优 点。

附图说明

图1是本发明总体流程图；

图2是网络拓扑的一部分；

图3是图2所示拓扑结构中节点自定义的关系列表；

图4是图2所示拓扑中节点u₇的路径表变化；

图5是图2所示拓扑总验证过程中验证者节点接收到的所有路径；

图6是方法在不同网络规模下检测方法的性能。

具体实施方式

图1给出了检测方法的总流程。以一个具体的网络为例，说明本发明 的具体实施方法。使用随机网络模型生成模拟网络，包括1,500个节点以及 22,004条边。由于网络节点过多，我们使用图2所示的部分节点构成的拓 扑来解释具体实施细节。其中v是验证者节点，其它为待验证节点。

检测方法共包括四个步骤。

第一步，选取某一节点为验证节点，标记为v，任意节点都可以作为验 证节点，除验证节点之外的所有节点都为待验证节点，各节点进行初始 化操作：各节点定义自己的加解密算法；并根据关系初始化关系列表， 如图3所示。

第二步，由验证节点v对其它节点进行可达路径通告，方法是：

首先v发送宣告信息给关系列表中的成员u₁和u₂，其中路径参数为{v}， 标识为Crypt_v(T₀),其中Crypt_v()为v的加密算法,T₀为v定义的任意字符串。 取其余参数K＝4,L＝7。初始时各节点的路径表都为空，所以路径{v}和 其标识被加入到u₁和u₂的路径表中。

随后,u₂将自身添加到原路径中构成新路径{v，u₂}，并使用加密程序对 原标识加密形成新的标识，然后将新路径和标识发送给他的关系列表中的 成员u₃和u₄。由于u₁的关系列表为空,因此不需要进行路径宣告。

类似地，u₃和u₄也按照步骤一流程对路径进行宣告。图4显示了节点u₇的路径表随着通告流程的变化过程。u₇的路径表初始化为空，在收到u₄发 出的宣告信息后，路径表如图4(a)所示；当u₇接收到来自u₅的宣告信息后， 依照通告流程，首先对路径有效性进行检查。新路径{v，u₂，u₃，u₅}和 {v，u₂，u₄，u₅}的长度都小于L，与原有路径{v，u₂，u₄}的差异系数分别为3和 4，由于定义的最大差异系数K＝4，因此{v，u₂，u₃，u₅}是有效的被加入路径 表，而{v，u₂，u₄，u₅}是无效的被丢弃。此时u₇的路径表如图4(b)所示。最 后，u₇收到来自于u₆的宣告信息，新路径{v，u₂，u₄，u₆}与原路径{v，u₂，u₄}差 异系数等于4，等于最大差异系数，因此被丢弃。最终u₇的路径表如图4(c) 所示。

当所有节点不再收到新的通告信息后，通告阶段结束。

第三步，所有待验证节点发送包含可达路径的验证请求给验证节点v， 使所有的可达路径聚集到验证节点v处，然后由验证节点v检查所有可达路 径是否可信。

所有待验证节点将自己路径表中的内容按通告信息的格式发送给验证 节点v等待验证。v在收到所有待验证请求后，按照路径长度排序，如图5 所示。其中最短路径形如{v，u₁}和{v，u₂}，因为u₁和u₂都在v的关系表中， 因此发送验证消息给u₁和u₂，其中各包括路径{v，u₁}和{v，u₂}以及各自的标 识。u₁和u₂对标识解密后返回给v，v解密后得到初始字符串T₀，因此验证 成功，将{v,u₁}和{v，u₂}加入verified_table中。

对{v，u₂，u₃}进行验证时，首先发现{v,u₂}在verified_table中，然后给 最末节点u₃发送验证信息，u₃对标识解密后反馈给v，v将反馈结果与{v，u₂} 的标识进行比对，一致则验证成功，否则验证失败。

v依次对所有的路径进行验证后，聚集和路径可信性验证阶段结束。

第四步，由验证节点根据每个节点的可信路径数量判断该节点是否为 Sybil节点，方法是：

验证节点计算每个待验证节点拥有可信路径数量，如果可信路径数量 大于验证阀值，则说明该节点验证成功，否则验证失败。

验证成功表明验证者接受该节点，否则验证者拒绝该节点。为对发明 准确性进行评估，定义AR为对正常节点的接受率(Accept Rate)，RR表示对 Sybil节点的拒绝率(Reject Rate)。AR越高表示能接受的正常节点越多，但同 时可能接受到Sybil节点也越多；RR越高表示能检测出的Sybil节点越多， 但同时被误检的正常节点也可能越多。好的检测方法应该能够同时得到较 高的AR和RR。

使用不同规模的网络对方法的有效性进行了验证，并对不同参数下系 统性能进行了对比，结果如表6所示。从图中可以看到在不同网络规模下 本发明方法的接受率和拒绝率都可以高达90%，随着节点的增多，性能有 所下降，但也都维持在88%以上。

本发明对Sybil攻击进行检测，以节点在交互过程中形成的社会关系为 依据检测Sybil节点，不但可以发现已发动的Sybil攻击，还可以对潜在的 Sybil攻击威胁进行检测，从而最大限度地避免攻击造成的危害。可以应用 在使用推荐机制和共享机制的各种在线社会网络领域，例如网络在线投票、 在线评分、视频共享等。