基于密度的动态IPv6地址探测方法[发明专利]

(12)发明专利申请

(10)申请公布号 CN 111432043 A(43)申请公布日 2020.07.17

(21)申请号 202010157916.3(22)申请日 2020.03.09

(71)申请人 清华大学

地址 100084 北京市海淀区清华园(72)发明人 杨家海　宋光磊　何林　王之梁　(74)专利代理机构 北京清亦华知识产权代理事

务所(普通合伙) 11201

代理人 刘梦晴(51)Int.Cl.

H04L 29/12(2006.01)

权利要求书1页 说明书5页 附图2页

()发明名称

基于密度的动态IPv6地址探测方法(57)摘要

本发明公开了一种基于密度的动态IPv6地址探测方法，该方法包括以下步骤：对活跃的IPv6种子地址进行向量化，然后建立密度空间树学习种子地址的高密度区域，最后在高密度区域生成可能存活的IPv6地址，并对地址进行动态扫描。该方法解决6Gen过高的时间复杂度和6Tree地址探测范围的问题，同时有效的提升了地址探测效率，降低地址探测的时间和经济成本。

CN 111432043 ACN 111432043 A

权　利　要　求　书

1/1页

1.一种基于密度的动态IPv6地址探测方法，其特征在于，包括以下步骤：步骤S1，对活跃的IPv6种子地址进行向量化，得到高维度向量；步骤S2，在线性时间内，根据所述高维度向量构建密度空间树，在所述密度空间树中发现所述活跃的IPv6种子地址的高密度区域；

步骤S3，在所述高密度区域生成目标地址，并结合地址探测反馈机制进行地址动态生成。

2.根据权利要求1所述的基于密度的动态IPv6地址探测方法，其特征在于，所述步骤S1进一步包括：

将所述活跃的IPv6种子地址转换为非负整数；使用不同进制转化所述非负整数，并将转化后的进制数字作为所述高维度向量，其中，所述高维度向量的维度为

β表示进制。

3.根据权利要求1所述的基于密度的动态IPv6地址探测方法，其特征在于，所述密度空间树的根节点表示整个活跃IPv6地址所在的可变地址空间，叶子节点表示所述活跃的IPv6种子地址的高密度区域。

4.根据权利要求1所述的基于密度的动态IPv6地址探测方法，其特征在于，所述步骤S2中，采用向量最小熵值维度处的指标构建所述密度空间树，用以发现所述高密度区域。

5.根据权利要求4所述的基于密度的动态IPv6地址探测方法，其特征在于，构建所述密度空间树具体为：

利用所述高维度向量初始化根节点；将所述根节点执行层次聚类，在对应向量熵值最小的维度处进行，生成孩子节点，同时，将所述根节点对应的高维度向量在维度生成的向量子集，分布到对应的孩子节点上，直至当前待节点包含的高维度向量少于预设阈值，停止，完成所述密度空间树的构建。

6.根据权利要求5所述的基于密度的动态IPv6地址探测方法，其特征在于，在聚类过程中，当要节点存在多个最小熵时，需考虑地址层次结构，选择从左到右的方式进行，左边维度生成孩子节点的优先级高于右边的节点。

7.根据权利要求5所述的基于密度的动态IPv6地址探测方法，其特征在于，在聚类过程中，节点稳定维度数小于等于节点在空间树的深度。

8.根据权利要求1所述的基于密度的动态IPv6地址探测方法，其特征在于，所述步骤S3进一步包括：

在所述高密度区域生成所述目标地址，以根据所述目标地址进行地址预扫描；结合所述地址探测反馈机制对所述活跃的IPv6种子地址进行反馈扫描，引导所述活跃的IPv6种子地址在所述密度空间树中进行地址动态生成。

2

CN 111432043 A

说　明　书

基于密度的动态IPv6地址探测方法

1/5页

技术领域

[0001]本发明涉及互联网技术领域，特别涉及在一代互联网IPv6地址探测技术，即一种基于密度的动态IPv6地址探测方法。

背景技术

[0002]随着移动互联网、物联网和工业互联网等网络应用融合发展，全球对IP地址的需求持续快速增长，IPv4地址资源已经枯竭，基于IPv6的下一代互联网成为各国推动新科技产业和重塑国家竞争力的先导领域。IPv6具有128位的地址空间，巨大的地址空间使得IPv6地址空间不能全网探测。收集活跃的IPv6地址作为种子地址，分析种子地址结构和分布特性并生成可能活跃的IPv6地址作为地址扫描的目标，缩小地址探测的空间是在IPv6地址探测的有效方式。[0003]相关技术中，Murdock等提出基于密度聚类的6Gen算法。引入汉明距离作为种子间的距离指标，同时假设在高密度区域更可能存在活跃的IPv6地址。使用聚集层次聚类(AHC)，初始将每个种子地址作为聚类，贪婪的对聚类进行扩张，同时每个聚类维持最大密度区域和最小规模，生成高密度地址区域，直到密度小于设定阈值时聚类结束，最后在高密度区域进行地址生成。然而6Gen在对种子地址进行聚类时间复杂度过高(O(n3))，不能应用于大规模的地址空间探测，了地址探测空间；同时生成的目标地址中，活跃地址的比例小，地址探测效率低，浪费大量探测资源。

[0004]Liu等提出动态发现活跃地址算法6Tree。6Tree将IPv6地址视为高维向量，并对种子地址所对应的地址向量按照地址层次结构构建IPv6地址空间树。通过在聚类过程中所在维度的经验熵值变为零的顺序来估计种子向量不同维中值变异性，并且它提供了与从子节点到根节点的路径等效的建议搜索方向。6Tree在线性时间内学习种子地址的层次结构特征，取得了较好的探测效果。但是6Tree仅仅考虑IPv6地址的层次特性，构建的空间树不能根据新发现的地址动态变化，在生成的目标地址数目不变的情况下，每次在相同的地址空间进行地址生成，了探测地址的空间和探测资源。同时生成的目标地址中，活跃地址的比例虽然比6Gen有所提升，但是仍然比较低，浪费大量探测资源。[0005]综上可知，在IPv6地址探测中，虽然6Gen和6Tree在一定程度上提升了地址探测的效率。6Gen过高的时间复杂度导致不能应用于大规模地址空间探测，比如在种子地址为5000时，训练种子地址时间超过一天。6Tree巧妙的设计降低了训练种子地址的时间复杂度，但是仅仅考虑地址层次结构了IPv6地址生成的空间，在重复的进行地址探测时，生成的目标地址不变，浪费网络探测资源。同时两种方法的地址探测效率低，浪费地址探测资源。

[0006]因此，亟待一种新的目标地址生成算法解决针对地址探测效率低，6Gen过高的时间复杂度和6Tree地址探测范围的技术难题。

3

CN 111432043 A

说　明　书

2/5页

发明内容

[0007]本发明旨在至少在一定程度上解决相关技术中的技术问题之一。[0008]为此，本发明的目的在于提出一种基于密度的动态IPv6地址探测方法，该方法有效的提升了地址探测效率，降低地址探测的时间和经济成本。[0009]为达到上述目的，本发明实施例提出了基于密度的动态IPv6地址探测方法，包括以下步骤：步骤S1，对活跃的IPv6种子地址进行向量化，得到高维度向量；步骤S2，在线性时间内，根据所述高维度向量构建密度空间树，在所述密度空间树中发现所述活跃的IPv6种子地址的高密度区域；步骤S3，在所述高密度区域生成目标地址，并结合地址探测反馈机制进行地址动态生成。

[0010]本发明实施例的基于密度的动态IPv6地址探测方法，通过结合密度、信息熵和空间树设计高效的地址探测算法DET(Detective)，DET通过构建密度空间树，在线性时间内发现种子地址的高密度区域，同时尽可能维持地址的层次特征，然后在高密度区域结合地址探测反馈机制进行地址动态生成，解决了6Gen过高的时间复杂度和6Tree地址探测范围的问题，同时有效的提升了地址探测效率，降低地址探测的时间和经济成本。[0011]另外，根据本发明上述实施例的基于密度的动态IPv6地址探测方法还可以具有以下附加的技术特征：[0012]进一步地，在本发明的一个实施例中，所述步骤S1进一步包括：将所述活跃的IPv6种子地址转换为非负整数；使用不同进制转化所述非负整数，并将转化后的进制数字作为所述高维度向量，其中，所述高维度向量的维度为

[0013]

β表示进制。

进一步地，在本发明的一个实施例中，所述密度空间树的根节点表示整个活跃IPv6地址所在的可变地址空间，叶子节点表示活跃的IPv6种子地址的高密度区域。[0014]进一步地，在本发明的一个实施例中，所述步骤S2中，采用向量最小熵值维度处的指标构建所述密度空间树，用以发现所述高密度区域。[0015]进一步地，在本发明的一个实施例中，构建所述密度空间树具体为：利用所述高维度向量初始化根节点；将所述根节点执行层次聚类，在对应向量熵值最小的维度处进行，生成孩子节点，同时，将所述根节点对应的高维度向量在维度生成的向量子集，分布到对应的孩子节点上，直至当前待节点包含的高维度向量少于预设阈值，停止，完成所述密度空间树的构建。[0016]进一步地，在本发明的一个实施例中，在聚类过程中，当要节点存在多个最小熵时，需考虑地址层次结构，选择从左到右的方式进行，左边维度生成孩子节点的优先级高于右边的节点。[0017]进一步地，在本发明的一个实施例中，在聚类过程中，节点稳定维度数小于等于节点在空间树的深度。[0018]进一步地，在本发明的一个实施例中，所述步骤S3进一步包括：[0019]在所述高密度区域生成所述目标地址，以根据所述目标地址进行地址预扫描；[0020]结合所述地址探测反馈机制对所述活跃的IPv6种子地址进行反馈扫描，引导所述活跃的IPv6种子地址在所述密度空间树中进行地址动态生成。[0021]本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变

4

CN 111432043 A

说　明　书

3/5页

得明显，或通过本发明的实践了解到。

附图说明

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

[0023]图1为根据本发明一个实施例的基于密度的动态IPv6地址探测方法流程图；[0024]图2为根据本发明一个实施例步骤S2中密度空间树的构建过程示意图，其中，α指节点包含的最小地址向量数目。

具体实施方式

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

[0026]下面参照附图描述根据本发明实施例提出的基于密度的动态IPv6地址探测方法。[0027]图1是本发明一个实施例的基于密度的动态IPv6地址探测方法流程图。[0028]如图1所示，该基于密度的动态IPv6地址探测方法包括以下步骤：[0029]在步骤S1中，对活跃的IPv6种子地址进行向量化，得到高维度向量。[0030]进一步地，在本发明的一个实施例中，步骤S1进一步包括：将活跃的IPv6种子地址转换为非负整数；使用不同进制转化非负整数，并将转化后的进制数字作为高维度向量，其中，高维度向量的维度为

[0031]

β表示粒度基准数。

具体而言，IPv6地址是一个128位的二进制符号串，因此需要将活跃的IPv6种子地址重新定义为高纬度向量，并将活跃的IPv6种子地址表示成不同粒度(β)。具体实现方法的过程：首先将二进制表示的活跃的IPv6种子地址转换为非负整数，然后使用不同粒度β进行表示，并将转化的2β进制数字作为地址向量。例如，活跃的IPv6种子地址为2001:da8:abc:dfe::1，当粒度β＝4时，表示成的32维度地址向量为20010da80abc0dfe0000000000000001；当β＝2是，表示成维度地址向量为0200000100312220002223300002333200000000000000000000000000000001。[0032]在步骤S2中，根据高维度向量构建密度空间树，并在线性时间内，在密度空间树中发现活跃的IPv6种子地址的高密度区域。[0033]其中，密度空间树的根节点表示整个活跃IPv6地址所在的可变地址空间，叶子节点表示IPv6地址的高密度区域。[0034]进一步地，在本发明的一个实施例中，步骤S2中，采用向量最小熵值维度处的指标构建密度空间树，用以学习高密度区域。[0035]需要说明的是，采用在种子地址向量最小熵值维度处进行的指标，可避免种子地址的高密度区域不被，使得种子地址的高密度区域分布在密度空间树的叶子节点或者同一分支。[0036]进一步地，在本发明的一个实施例中，在对种子地址进行向量化后，利用高维度向量初始化根节点；将根节点执行层次聚类，在对应向量熵值最小的维度处进行，生

5

CN 111432043 A

说　明　书

4/5页

成叶子节点，同时，将根节点对应的高维度向量在维度生成的向量子集，分布到对应的叶子节点上，直至当前待节点包含的高维度向量少于预设阈值，停止，完成密度空间树的构建。

[0037]需要说明的是，在聚类过程中，需对密度空间数尽量维持地址层次的特性，因此，当要节点存在多个最小熵时，考虑地址层次结构，选择从左到右的方式进行，左边维度生成孩子节点的优先级高于右边的节点。且每次节点，孩子节点增加一个稳定维度，因此按照设计的层次聚类，节点稳定维度数小于等于节点在空间树的深度，例如，当节点包含向量数的阈值为1时，空间树的深度等于IPv6地址向量的维度。[0038]另外，本发明实施例还提出使用栈记录地址向量中维度熵值变为0的顺序，因此仅仅只有一个孩子的节点将会和孩子节点合并成一个节点。节点属性中栈的引入首先简化了空间树的结构，同时节省了存储密度空间树的内存消耗。例如，如图2所示，本发明实施例使用7个活跃的IPv6种子地址生成包含5个节点的密度空间树，其中，β＝4，α＝3。[0039]进一步地，在发现地址高密度区域时，可以使用多种数据结构去存储地址高密度区域。比如使用队列维护节点。初始时，将所有种子设为根结点进入队列。每轮迭代，计算当前集合的所有可变位的熵，选取熵最低的位，按该位的值当前集合，将划分出的子集合作为当前结并进入队列，后的节点出队列，最后队列中维护的区域表示地址的高密度区域。存储节点的数据结构仅仅是用来去记录地址密度信息，只要使用最小信息熵对节点进行发现地址高密度区域的都在本发明的潜在替代方案范围。[0040]在步骤S3中，在高密度区域生成目标地址，并结合地址探测反馈机制进行地址动态生成。

[0041]进一步地，在本发明的一个实施例中，步骤S3进一步包括：[0042]在高密度区域生成目标地址，以根据目标地址进行地址预扫描；[0043]结合地址探测反馈机制对活跃的IPv6种子地址进行反馈扫描，引导活跃的IPv6种子地址在密度空间树中进行地址动态生成。[0044]具体而言，首先在高密度地址空间生成目标地址，进行地址预扫描，然后结合6Tree空间树动态生成工具对活跃的IPv6种子地址进行反馈扫描，引导活跃的IPv6种子地址在密度空间树中生成的方向，进一步提升生成活跃IPv6地址的比例，提升IPv6地址空间探测效率。

[0045]综上，本发明实施例提出的基于密度的动态IPv6地址探测方法，与相关技术相比，具有以下优点：[0046]第一，使用2.3M全球活跃的种子地址生成50M目标地址，本发明实施例将发现新的活跃地址比例提升到32％，对比6Gen的16％，6Tree的18％。[0047]第二，极大幅度减少地址探测时间成本和经济成本。IPv6地址发现，工业界大量发送探测包扫描活跃的IPv6地址。当前探测的活跃地址耗时久、效率低下导致大量网络资源(流量)浪费。线性时间内对种子地址进行聚类，同时将IPv6地址探活比率提升到32％，大幅度的降低了探测时间，减少了网络资源的消耗。[0048]第三，推进了学术界在网络测量、网络测绘、网络安全等领域的研究。高效的IPv6地址探测技术建立活跃IPv6地址库，为网络测量、网络测绘、网络安全等领域提供数据支持。

6

CN 111432043 A[0049]

说　明　书

5/5页

第四，支持工业界网络测量领域和安全领域在IPv6网络产品化。高效的地址探测

和扫描能在短时间内收集大量活跃的IPv6地址。活跃的IPv6地址支持网络测量行业产品在下一代互联网领域推广，更支持了安全公司在IPv6网络的产品的拓展。[0050]第五，高效的IPv6地址探测扫描有利于掌握自身IPv6网络状况，确保国家信息网络安全，占领网络安全制高点和主动权。高效的IPv6地址探测扫描为IPv6网络设备和服务识别定位、漏洞发现、渗透测试等网络攻击的重要基础。防御角度：当前移动网络、物联网和工业互联网等关键信息基础设施对IPv6的建设应用更加紧迫，也面临较高风险，一旦受到攻击，会对社会经济和国计民生造成重大影响。通过地址探测及时掌握地址IPv6网络安全状况，规避风险、防御攻击。攻击角度：感知对手IPv6网络拓扑和关键节点，夺取IPv6信息优势具有重要经济和国防价值。[0051]此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。[0052]在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。

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

7

CN 111432043 A

说　明　书　附　图

1/2页

图1

8

CN 111432043 A

说　明　书　附　图

2/2页

图2

9