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

摘要

本发明公开了一种在线社会网络中Sybil攻击检测方法，目的是提供一种在社会网络中Sybil攻击检测方法。技术方案是选取某一节点为验证节点，以成员关系为依据进行路径通告，构建到达验证节点的关系路径；通告过程中采用基于路径k相似的路径选择方法剔除冗余路径和共享路径；通告结束后将所有可达路径聚集到验证节点进行可信性检验，以防止私造或篡改路径；最终以每个节点可信路径的数量作为验证标准，由验证节点对其它节点是否为Sybil节点进行验证。本发明利用每个节点的可达路径数量判断该节点是否为Sybil节点，真实还原并利用了节点关系的差异性，准确性高、误报率低，且无需依靠关键基础设施或其它辅助设备的支持，具有轻量级、易部署的优势。

主权项

1.一种在线社会网络中Sybil攻击检测方法，其特征在于包括以下步骤：第一步，选取某一节点为验证节点，标记为v，任意节点都可以作为验证节点，除验证节点之外的所有节点都为待验证节点，各节点进行初始化操作，方法是：1.1所有节点定义自己的加解密算法；1.2验证节点创建关系表，并定义任意的字符串T₀作为初始化的标识；所有待验证节点创建关系表和路径表；其中关系表存储已经与自己建立起可信关系的其他节点，表中每一项都是一个节点标识；路径表用来存储到达验证节点的可达路径，表中每一项是一个二元组，表示为<P_i，Sign(P_i)>，1≤i≤M，其中M为网络中总路径数，P_i表示第i条路径，Sgin(P_i)表示Pi的标识，每一条路径都是一个有序的节点序列，每一个标识是一个加密后的字符串，关系表由各节点根据历史经验自己定义，路径表初始为空；第二步，由验证节点v对其它节点进行可达路径通告，方法是：2.1v发送通告信息M₀给v的关系表中所有成员，M₀的内容包括到达v的可达路径、可达路径的标识、可接受的最大差异系数K以及可接受的最大路径长度L，以v的加密算法对T₀加密作为路径{v}的标识；可接受的最大差异系数K和可接受的最长路径长度L都由验证节点自己确定。2.2接收到了通告信息M₀的节点u_j首先对M₀中路径的有效性进行检查，设M₀中路径为P，标识为Sign(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}，则P′＝{u₁，u₂...u_l，u_j}，1≤l≤N，N为网络中节点个数，并使用u_j自己的加密算法Crypt_uj()对Sign(P)加密，构成新的路径标识，即Sogn(P′)＝Crypt_uj(Sign(P))；2.5u_j发送新的通告信息M₁：使用原通告信息M₀中K和L的值，与新的路径P′和标识Sign(P′)一起构成新的通告信息M₁并发送给u_j关系列表中的成员，并发送通告提醒给v，转步骤2.6；通告提醒的内容为u_j的节点标识u_j；2.6如果u_j接收到新的通告信息M₁，将M₀的内容更新为M₁，转步骤2.2，否则转步骤2.7；2.7验证节点v根据网络规模定义提醒时间间隔，并初始化提醒计时器并开始计时；设置提醒时间间隔τ，如果在τ时间内接收到了通告提醒，则重置计时器为零并转步骤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＝{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),$如果结果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)进行解密，方法为Ren(P_s)＝(Sign(P_s))，并将结果与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为空集，并设定判断阀值α，α根据需求自由调整；4.2从unverified_set取出一个节点u，计算可信路径集trusted_table(u)＝path_table(u)∩verified_table，其中path_table(u)为u提交的路径表，如果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节点。