基于图社区发现的活跃地址探测方法及装置

摘要

本发明公开了一种基于图社区发现的活跃地址探测方法及装置，将收集的IPv6种子地址集合划分为多个地址集合，并对每个地址集合生成其地址结构模式，通过计算这些模式之间的相似度建立无向图，最终利用图社区发现算法从该图结构中挖掘热门的地址结构模式，并将这些模式通过组织关联策略用于无种子地址的BGP前缀下进行IPv6活跃地址发现。提供了一种基于图社区发现算法的通用、自动化并且具有高命中率的无种子地址区域的IPv6活跃地址探测方案。

权利要求

1.一种基于图社区发现的活跃地址探测方法，其特征在于，包括以下步骤：获取IPv6种子地址集合，对所述IPv6种子地址集合进行处理得到无向图；

通过图社区发现算法对所述无向图进行处理得到多个社区，对多个社区进行平均加权度计算，根据设定的平均加权阈值对社区采用全交集合并或全并集合并的方式进行过滤，利用过滤后的社区中的模式字符串集合组成模式库；

采用组织关联的方式从所述模式库中筛选与目标BGP前缀对应的模式字符串；

对所述IPv6种子地址进行处理得到无向图，包括：对所述IPv6种子地址集合进行划分；

对划分后的每个地址集合用地址结构模式表示；

使用并查集对地址结构模式进行预处理，合并相似度高于预设阈值的地址结构模式字符串；

根据合并后的地址结构模式构建无向图。

2.根据权利要求1所述的方法，其特征在于，通过杰卡德相似度计算方法对地址结构模式间的相似度进行计算。

3.根据权利要求1所述的方法，其特征在于，对于任一个社区，平均加权等于社区内每个顶点的加权度总和除以社区内部的顶点数量，其中每个顶点的加权度等于该顶点的在社区内的所有边的权重之和；

如果平均加权度大于所述平均加权阈值，对社区采用全交集合并方式，将社区内所有顶点的模式字符串按照交集合并；

如果平均加权度小于等于述平均加权阈值，对社区采用全并集合并方式，将社区内所有顶点的模式字符串按照并集合并。

4.根据权利要求1所述的方法，其特征在于，采用组织关联的方式从所述模式库中筛选与目标BGP前缀对应的模式字符串，包括：对每个模式字符串所属的BGP前缀查询其组织标签，获得每个BGP前缀对应的多个英文单词；

查询目标BGP前缀的组织标签，获得目标BGP前缀的英文单词列表；

将英文单词转换为向量，计算任意两个BGP前缀组织标签之间的相似程度；

根据计算的任意两个BGP前缀标签之间的相似程度，排序筛选出最相似的k个模式字符串列表；

利用候选模式生成新的IPv6地址，再将目标BGP前缀换替IPv6地址的前缀。

5.一种基于图社区发现的活跃地址探测装置，其特征在于，包括：无向图构建模块，用于获取IPv6种子地址集合，对所述IPv6种子地址集合进行处理得到无向图；

图算法应用模块，用于通过图社区发现算法对所述无向图进行处理得到多个社区，对多个社区进行平均加权度计算，根据设定的平均加权阈值对社区采用全交集合并或全并集合并的方式进行过滤，利用过滤后的社区中的模式字符串集合组成模式库；

地址探测模块，用于采用组织关联的方式从所述模式库中筛选与目标BGP前缀对应的模式字符串；

对所述IPv6种子地址进行处理得到无向图，包括：对所述IPv6种子地址集合进行划分；

对划分后的每个地址集合用地址结构模式表示；

使用并查集对地址结构模式进行预处理，合并相似度高于预设阈值的地址结构模式字符串；

根据合并后的地址结构模式构建无向图。

6.根据权利要求5所述的装置，其特征在于，通过杰卡德相似度计算方法对地址结构模式间的相似度进行计算。

7.根据权利要求5所述的装置，其特征在于，对于任一个社区，平均加权等于社区内每个顶点的加权度总和除以社区内部的顶点数量，其中每个顶点的加权度等于该顶点的在社区内的所有边的权重之和；

如果平均加权度大于所述平均加权阈值，对社区采用全交集合并方式，将社区内所有顶点的模式字符串按照交集合并；

如果平均加权度小于等于述平均加权阈值，对社区采用全并集合并方式，将社区内所有顶点的模式字符串按照并集合并。

8.根据权利要求5所述的装置，其特征在于，所述地址探测模块，进一步用于，对每个模式字符串所属的BGP前缀查询其组织标签，获得每个BGP前缀对应的多个英文单词；

查询目标BGP前缀的组织标签，获得目标BGP前缀的英文单词列表；

将英文单词转换为向量，计算任意两个BGP前缀组织标签之间的相似程度；

根据计算的任意两个BGP前缀标签之间的相似程度，排序筛选出最相似的k个模式字符串列表；

利用候选模式生成新的IPv6地址，再将目标BGP前缀换替IPv6地址的前缀。

说明书

基于图社区发现的活跃地址探测方法及装置

技术领域

[0001] 本发明涉及网络地址探测技术领域，特别涉及一种基于图社区发现的活跃地址探测方法及装置。

背景技术

[0002] 随着IPv4的地址分配耗尽，下一代互联网协议IPv6也在全球范围内开始加速推广和部署，各种厂商和运营商也在其网络中支持IPv6。IPv6的推进与普及让许多研究者和网
络管理员就研究重点转移到对IPv6的空间测绘、拓扑发现和安全审计。这些工作的重点涉
及网络测量技术，庞大的IPv6地址空间使得传统的暴力探测技术很难用于IPv6空间的地址
发现。在万兆链路条件下，ZMAPv6采用最高的配置模式进行IPv6全网空间扫描，也至少需要
上亿年的时间，这是无法实现的事情。

[0003] 近年来，IPv6探测领域的主流相关工作已经能够在一定范围内发现较多的活跃地址，比如基于种子地址的探测方法和基于服务的地址发现方法。然而目前这些公开的IPv6
探测方法都很难解决全球IPv6单播地址探测面临的一个重要挑战——如何在只有无种子
地址的BGP前缀下进行活跃地址发现。

[0004] 基于种子地址的探测方法都是通过对大量的种子地址进行建模，挖掘种子地址的结构规律，进而生成新的IPv6候选地址。这类探测方法发现活跃地址的效果完全依赖种子
地址的质量和分布规律，这会导致两个方面的缺陷：一是无法在没有种子地址的BGP前缀下
发现新的IPv6活跃地址；二是种子地址在BGP前缀分布不均衡的现象会使得这类探测方法
生成的候选地址也在BGP前缀上分布不均衡，甚至只会生成高密度区域的种子地址，从而忽
略种子地址数量较少的BGP前缀下可能存在的活跃地址。

[0005] 基于服务的地址发现方法是从服务数据获取IPv6活跃地址，比如DNS查询以及CDN日志等。这类地址发现方法的效果完全取决于服务数据的质量，这也会导致三个方面的缺
陷：一是对用户权限要求较高，需要研究人员有权限获取许多核心服务日志数据，或者在重
要的网关出口进行流量抓取；二是地址发现的数量有限，即这些服务数据能够提供的地址
数量存在上界；三是地址发现的目标不可控，研究者能够获取哪些BGP前缀下的IPV6活跃地
址完全取决于服务记录的日志数据内容，很难保证一定发现指定前缀下的IPv6活跃地址。

[0006] 此外，Song等人在2020年提出的Random‑Bytes方法\尝试采用固定的地址模式主动探测全部BGP前缀空间的活跃地址。但是该方法使用的地址模式单一并且固定，发现的活
跃地址数量也非常有限，难以进一步扩展。

发明内容

[0007] 本发明旨在至少在一定程度上解决相关技术中的技术问题之一。

[0008] 为此，本发明的一个目的在于提出一种基于图社区发现的活跃地址探测方法，该方法利用图社区发现算法自动化挖掘通用的IPv6地址结构规律，并结合组织关联策略将这
些通用的IPv6地址结构规律迁移到任意BGP前缀下进行地址生成。

[0009] 本发明的另一个目的在于提出一种基于图社区发现的活跃地址探测装置。

[0010] 为达到上述目的，本发明一方面实施例提出了一种基于图社区发现的活跃地址探测方法，包括：

[0011] 获取IPv6种子地址集合，对所述IPv6种子地址集合进行处理得到无向图；

[0012] 通过图社区发现算法对所述无向图进行处理得到多个社区，对多个社区进行平均加权度计算，根据设定的平均加权阈值对社区进采用全交集合并或全并集合并的方式进行
过滤，利用过滤后的社区中的模式字符串集合组成模式库；

[0013] 采用组织关联的方式从所述模式库中筛选与目标BGP前缀对应的模式字符串。

[0014] 为达到上述目的，本发明另一方面实施例提出了一种基于图社区发现的活跃地址探测装置，包括：

[0015] 无向图构建模块，用于获取IPv6种子地址集合，对所述IPv6种子地址集合进行处理得到无向图；

[0016] 图算法应用模块，用于通过图社区发现算法对所述无向图进行处理得到多个社区，对多个社区进行平均加权度计算，根据设定的平均加权阈值对社区进采用全交集合并
或全并集合并的方式进行过滤，利用过滤后的社区中的模式字符串集合组成模式库；

[0017] 地址探测模块，用于采用组织关联的方式从所述模式库中筛选与目标BGP前缀对应的模式字符串。

[0018] 本发明实施例的基于图社区发现的活跃地址探测方法及装置，基于图社区发现算法的通用、自动化并且具有高命中率的无种子地址区域的IPv6活跃地址探测技术。通用性
体现在该技术可以用于任意BGP前缀下的地址发现，自动化体现在该技术能够处理任意数
量、任意类型和任意分布的种子地址集合，高命中率体现在比暴力探测、随机探测和
Random‑Bytes方法具有更高的探测命中率。本技术会首先对IPv6种子地址(收集的曾经或
者一直存活的IPv6地址)处理并建立无向图，然后运用图社区发现算法挖掘常见的地址结
构模式，之后这些模式能够被直接用于任意BGP前缀下的活跃地址发现。此外，本发明为了
解决工程实现中图处理效率较低的问题，引入了并查集对图结构进行预处理。

[0019] 本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

[0020] 本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明显和容易理解，其中：

[0021] 图1为根据本发明一个实施例的基于图社区发现的活跃地址探测方法流程图；

[0022] 图2为根据本发明一个实施例的基于图社区发现的活跃地址探测方法流程框图；

[0023] 图3为根据本发明一个实施例的通用地址结构规律挖掘完整过程图；

[0024] 图4为根据本发明一个实施例的组织关联策略实现原理图；

[0025] 图5为根据本发明一个实施例的探测效果示意图；

[0026] 图6为根据本发明一个实施例的基于图社区发现的活跃地址探测装置结构示意图。

具体实施方式

[0027] 下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附
图描述的实施例是示例性的，旨在用于解释本发明，而不能理解为对本发明的限制。

[0028] 下面参照附图描述根据本发明实施例提出的基于图社区发现的活跃地址探测方法及装置。

[0029] 首先将参照附图描述根据本发明实施例提出的基于图社区发现的活跃地址探测方法。

[0030] 图1为根据本发明一个实施例的基于图社区发现的活跃地址探测方法流程图。

[0031] 图2为根据本发明一个实施例的基于图社区发现的活跃地址探测方法流程框图。

[0032] 如图1和图2所示，该基于图社区发现的活跃地址探测方法包括以下步骤：

[0033] 步骤S1，获取IPv6种子地址集合，对IPv6种子地址集合进行处理得到无向图。

[0034] 进一步地，对IPv6种子地址进行处理得到无向图，包括：

[0035] 对IPv6种子地址集合进行划分；

[0036] 对划分后的每个地址集合用地址结构模式表示；

[0037] 使用并查集对地址结构模式进行预处理，合并相似度高于预设阈值的地址结构模式字符串；

[0038] 根据合并后的地址结构模式构建无向图。

[0039] 具体地，建图阶段目的是获得以每个地址集合的模式表示pattern为节点，超过一定阈值的相似度为边建立的无向图数据。全部过程可自动化完成并且能够处理各种量级的
种子地址集合。建图阶段主要由四个步骤组成：

[0040] 1)对于种子地址集合的划分。首先将全部种子地址按照/64前缀划分，然后根据地址的IID取值量化指标LOG_Q分别再对每一个/64前缀下的IPv6地址集合进一步细分。IID
(Interface Identifier，接口标识符)用于指明主机或路由器单个的网络接口，通常是
IPv6后64比特位，即最后16个半字节位。IPv6活跃地址生成算法最重要的就是对IID部分进
行预测和生成。为了量化IPv6地址的IID半字节取值情况，用xi表示IPv6地址第i个半字节
的取值(标准的IPv6地址有32个半字节)，其取值范围是16进制[0,f]；对于IID部分，i的取
值范围是[17,32]；符号r表示IID部分取值种类；这样用于刻画IID取值情况的量化指标Q计
算公式如下：

[0041]

[0042]

[0043] 其中分子含义是IPv6地址最后16个半字节IID部分取值最多的个数，比如0000:0000:0000:0000中取值为0的个数最多，是16；而0123:4567:89ab:cdef每种取值都有一个，
因此分子是1。为了让Q取值更加均匀并且避免取对数后出现负数，使用式(3)作为刻画IID
取值情况的最终指标LOG_Q。

[0044] LOG_Q＝log16Q+1   (3)

[0045] 进一步细分，就是计算每个/64前缀下的地址LOG_Q取值，从小到大排序，根据人为设定的跃变阈值确定合适的切分点。

[0046] 2)地址结构的模式表示，即得到每个地址集合的pattern。定义4种表示策略用于生成任意地址集合的模式表示——Single、List、Range和Wildcard策略，其中Single是用
于表示输入的地址集合中没有取值变化的半字节位置。4种策略的取值来源如下：

[0047] Single：地址集合该半字节固定的取值。

[0048] List：地址集合在该半字节取值的集合。

[0049] Range：地址集合在该半字节的最小值到最大值范围，可能会包括该半字节在地址集合中未出现的取值。

[0050] Wildcard：16进制全部取值[0,f]，可能会包括该半字节在地址集合中未出现的取值。

[0051] 该模式表示会根据每个半字节在输入的地址集合中的3个统计量(极差、香农熵、取值种类数)决定采用哪种策略。表1展示了该步骤是如何根据这3种统计量大小确定该半
字节位的表示策略。3种统计量属于较大还是较小分别由极差阈值range_t，熵值阈值
entropy_t和取值种类数阈值type_t决定。

[0052] 表1 BSPR使用的4种表示策略和3种统计量关系

[0053]

[0054] 3)步骤三，使用并查集对获取的pattern进行预处理，合并相似度非常高的pattern字符串，减少后续建图的节点和边的数量。

[0055] 首先定义计算任意两个pattern相似度的方法。因为pattern是一定数量的IPv6地址集合得到的文本字符串，以表示这批IPv6地址集合的取值情况。该专利采用常见的文本
相似度计算方法来获取任意两个pattern的相似度——杰卡德相似度。相似度计算策略如
下：

[0056] a)因为任意的IPv6地址集合都是32个半字节位，会得到由32策略组成的pattern，这些策略属于Single、List、Range、Wildcard。从左到右遍历两个pattern对应位置的策略。

[0057] b)如果一个策略是Single，而另一个策略是非Single模式，相似度分数为0。

[0058] c)如果两个策略都属于是List、Range、Wildcard模式之一，按照如下公式计算杰卡德相似度：

[0059]

[0060] 其中c1表示其中一个策略代表的取值集合，c2表示另一个策略代表的取值集合，因为都是动态模式额外加上1.0分数。

[0061] d)如果两组策略都是Single，如果相同计算1.0，如果不同计算为0.0。

[0062] 最终32组策略的全部分数总和作为这两个pattern的相似度，分数越大表明相似度约高。

[0063] 接着，采用并查集进行节点和边的优化。并查集，一个实现了合并和查询集合方法的数据结构，其最终目的是将输入的节点按照其连接关系，分割成一个或多个子集，主要涉
及两种操作——合并和查找。执行步骤如下：初始化每一个pattern都是一个单独的集合，
其Find操作的父节点都是自己本身；依次遍历所有还是初始化的pattern节点并和其余未
被比较过得pattern节点计算相似度分数，如果超过人为设定的较高阈值，则进行Union操
作。

[0064] 通常这一步需要将阈值设置的较高，确保将高度相似的pattern在这一步寻找出来，然后将这些节点的IPv6地址集合生成新的一个pattern作为新的节点，实现性能优化。

[0065] 4)步骤四，计算任意两个pattern之间的相似度，根据人为设置的阈值决定相似度较高的视为存在边的关系，构建无向图。这一步骤设定的阈值相对较小，目的是将相似度非
常小的边去除，在经过并查集处理后的pattern节点之间建立无向边得到无向图。

[0066] 步骤S2，通过图社区发现算法对无向图进行处理得到多个社区，对多个社区进行平均加权度计算，根据设定的平均加权阈值对社区进采用全交集合并或全并集合并的方式
进行过滤，利用过滤后的社区中的模式字符串集合组成模式库。

[0067] 通用地址结构规律挖掘的核心是如何自动化地挖掘相似度较高、联系紧密的多个模式字符串组成的群体，并将群体内部的模式字符串合并得到通用地址结构规律。处理无
向图节点聚类的经典方法就是图社区发现算法,包括基于分裂的方法、基于模块度的方法、
基于随机游走的方法、基于信息熵的方法这四类。

[0068] 在处理IPv6地址数据的时候，使用图社区发现算法会存在一个问题：如果某个模式字符串包含的表示策略取值范围都比较大(比如[0‑f])，那么这个模式字符串会和很多
模式字符串之间有较高的相似度，最终会导致图社区发现算法将这些节点聚类为一个地址
空间范围非常大的社区，称这种社区为“差社区”。

[0069] 为了解决这种差社区在经过顶点合并之后地址空间范围过大，引入平均加权度来衡量一个社区是否属于这种“差社区”，并根据平均加权度的大小选择不同的合并社区内部
顶点的策略。对于任何一个社区，平均加权等于每个顶点的加权度总和除以社区内部的顶
点数量，其中每个顶点的加权度等于该顶点的在社区内的所有边的权重之和。

[0070] 通用地址结构规律挖掘完整过程如图3所示。通用地址结构规律挖掘过程需要人为预先设定一个平均加权度阈值以判断平均加权度过大还是过小。如果平均加权度过大，
采用全交集合并方式，如果平均少量和无种子地址场景下的活跃地址探测加权度过小，采
用全并集合并方式，如下：

[0071] 全交集合并方式：如果该社区平均加权度过大，将社区内所有顶点的模式字符串按照交集合并，即pnew＝p1∩p2∩p3...∩pn；

[0072] 全并集合并方式：如果该社区平均加权度过小，将社区内所有顶点的模式字符串按照并集合并，即pnew＝p1∪p2∪p3...∪pn。

[0073] 根据空间范围大小过滤掉空间范围过大的模式字符串，因为如果一个模式字符串空间范围越大那么它能提供的地址结构规律信息越小，比如Wildcard策略(用*表示)较多
的模式字符串。将最终得到的模式字符串集合称为模式库。

[0074] 步骤S3，采用组织关联的方式从模式库中筛选与目标BGP前缀对应的模式字符串。

[0075] 在无种子地址场景，仅仅只能知道待探测的目标BGP前缀信息。将上万条记录的模式库数据全部用于在目标BGP前缀进行地址发现会带来巨大的开销，因此针对每一个目标
BGP前缀，提出采用组织关联的方式从模式库筛选更可能适合用于该目标BGP前缀的模式字
符串。图4展示了利用组织标签筛选模式库的实现原理。

[0076] Hurricane Electric网站提供针对IPv6地址或BGP前缀相关信息查询的服务。从该网站可以获取任何BGP前缀的所属组织信息，并以多个英文单词呈现，比如2402:f000::/
32的组织标签是由两个英文单词组成的"Tsinghua Universty"。我们采用目前自然语言处
理领域热门的Word2Vec预训练模型(比如fastText)直接将这些英文单词转换为向量。组织
关联策略详细步骤如下：

[0077] 1、模式库组织标签预处理：利用Hurricane Electric网站对每个模式字符串所属的BGP前缀查询其组织标签，即获得每个BGP前缀对应的多个英文单词。对于部分只包含专
有名词的组织标签，我们手动通过Google或Baidu查询专有名词的含义，然后使用通用的英
文单词代替专用名词，比如2a03:4000::/32前缀经过查询得到DE‑NETCUP，是德国的老牌主
机商，因此在该前缀的组织标签里添加"hosting provider"这两个英文单词；

[0078] 2、目标BGP前缀标签获取：同样利用Hurricane Electric网站查询目标BGP前缀的组织标签，获得目标BGP前缀的英文单词列表。如果出现专有名词，也通过Google或Baidu查
询专有名词的含义，然后使用通用的英文单词代替专用名词。

[0079] 3、英文单词转向量：采用Word2Vec领域热门的公开预训练模型fastText直接进行转换，以便计算任意两个BGP前缀组织标签的相似程度。

[0080] 4、排序粗筛：计算任意两个BGP前缀标签之间的相似程度，排序筛选出最相似的k个模式字符串列表。

[0081] 5、地址生成和主动探测：利用候选的模式生成新的IPv6地址，再将目标BGP前缀替这些IPv6地址的前缀。

[0082] 虽然组织关联策略涉及一些人为操作，比如查询专有名词的通用英文单词，但是因为宣告的BGP前缀都是公开可获得的并且数量有限，所以只需要事先给全部BGP前缀打好
组织标签，这样在执行GAG方法的过程中就无需任何人为干预。

[0083] 本发明的效果是图社区发现的地址结构规律(模式)可以直接用于在任意BGP前缀下进行活跃地址探测，能够解决IPv6地址空间庞大带来的全网扫描难题。

[0084] 图5展示了采用GAG算法在无种子场景的命中率和发现的活跃数量。横坐标是每个BPG前缀生成的候选地址数量(单位：个)，纵坐标表示发现的活跃地址数量(单位：个)或命
中率。在生成候选地址数量较多的情况下，GAG方法使用的组织关联策略具备最高的命中
率，并且能够发现最多的IPv6活跃地址，这表明本发明提出的GAG方法具有更好的大规模探
测能力。本发明作为一种新型的基于图社区发现的活跃地址探测算法，在探测效率、自动化
水平和可拓展性这几个方面均优于已有的用于同一任务的方法。

[0085] 根据本发明实施例提出的基于图社区发现的活跃地址探测方法，基于图社区发现算法的通用、自动化并且具有高命中率的无种子地址区域的IPv6活跃地址探测技术。通用
性体现在该技术可以用于任意BGP前缀下的地址发现，自动化体现在该技术能够处理任意
数量、任意类型和任意分布的种子地址集合，高命中率体现在比暴力探测、随机探测和
Random‑Bytes方法具有更高的探测命中率。本技术会首先对IPv6种子地址(收集的曾经或
者一直存活的IPv6地址)处理并建立无向图，然后运用图社区发现算法挖掘常见的地址结
构模式，之后这些模式能够被直接用于任意BGP前缀下的活跃地址发现。此外，本发明为了
解决工程实现中图处理效率较低的问题，引入了并查集对图结构进行预处理。

[0086] 其次参照附图描述根据本发明实施例提出的基于图社区发现的活跃地址探测装置。

[0087] 图6为根据本发明一个实施例的基于图社区发现的活跃地址探测装置结构示意图。

[0088] 如图6所示，该基于图社区发现的活跃地址探测装置包括：无向图构建模块601、图算法应用模块602和地址探测模块603。

[0089] 无向图构建模块601，用于获取IPv6种子地址集合，对IPv6种子地址集合进行处理得到无向图。

[0090] 图算法应用模块602，用于通过图社区发现算法对无向图进行处理得到多个社区，对多个社区进行平均加权度计算，根据设定的平均加权阈值对社区进采用全交集合并或全
并集合并的方式进行过滤，利用过滤后的社区中的模式字符串集合组成模式库。

[0091] 地址探测模块603，用于采用组织关联的方式从模式库中筛选与目标BGP前缀对应的模式字符串。

[0092] 进一步地，在本发明的实施例中，对IPv6种子地址进行处理得到无向图，包括：

[0093] 对IPv6种子地址集合进行划分；

[0094] 对划分后的每个地址集合用地址结构模式表示；

[0095] 使用并查集对地址结构模式进行预处理，合并相似度高于预设阈值的地址结构模式字符串；

[0096] 根据合并后的地址结构模式构建无向图。

[0097] 进一步地，在本发明的实施例中，通过杰卡德相似度计算方法对地址结构模式间的相似度进行计算。

[0098] 进一步地，在本发明的实施例中，对于任一个社区，平均加权等于社区内每个顶点的加权度总和除以社区内部的顶点数量，其中每个顶点的加权度等于该顶点的在社区内的
所有边的权重之和；

[0099] 如果平均加权度大于平均加权阈值，对社区采用全交集合并方式，将社区内所有顶点的模式字符串按照交集合并；

[0100] 如果平均加权度小于等于述平均加权阈值，对社区采用全并集合并方式，将社区内所有顶点的模式字符串按照并集合并。

[0101] 进一步地，在本发明的实施例中，地址探测模块，进一步用于，

[0102] 对每个模式字符串所属的BGP前缀查询其组织标签，获得每个BGP前缀对应的多个英文单词；

[0103] 查询目标BGP前缀的组织标签，获得目标BGP前缀的英文单词列表；

[0104] 将英文单词转换为向量，计算任意两个BGP前缀组织标签之间的相似程度；

[0105] 根据计算的任意两个BGP前缀标签之间的相似程度，排序筛选出最相似的k个模式字符串列表；

[0106] 利用候选模式生成新的IPv6地址，再将目标BGP前缀换替IPv6地址的前缀。

[0107] 需要说明的是，前述对方法实施例的解释说明也适用于该实施例的装置，此处不再赘述。

[0108] 根据本发明实施例提出的基于图社区发现的活跃地址探测装置，基于图社区发现算法的通用、自动化并且具有高命中率的无种子地址区域的IPv6活跃地址探测技术。通用
性体现在该技术可以用于任意BGP前缀下的地址发现，自动化体现在该技术能够处理任意
数量、任意类型和任意分布的种子地址集合，高命中率体现在比暴力探测、随机探测和
Random‑Bytes方法具有更高的探测命中率。本技术会首先对IPv6种子地址(收集的曾经或
者一直存活的IPv6地址)处理并建立无向图，然后运用图社区发现算法挖掘常见的地址结
构模式，之后这些模式能够被直接用于任意BGP前缀下的活跃地址发现。此外，本发明为了
解决工程实现中图处理效率较低的问题，引入了并查集对图结构进行预处理。

[0109] 此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者
隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三
个等，除非另有明确具体的限定。

[0110] 在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特
点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不
必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任
一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技
术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结
合和组合。

[0111] 尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述
实施例进行变化、修改、替换和变型。