【CN109905497A】一种IPv6活跃地址动态发现方法【专利】

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号(43)申请公布日(21)申请号201910162578.X(22)申请日2019.03.05(71)申请人长沙学院地址410022湖南省长沙市开福区洪山路98号(72)发明人朱培栋　熊荫乔　刘知竹　王平　崔鹏帅　郑昱　冯璐　(74)专利代理机构长沙中科启明知识产权代理事务所(普通合伙)43226代理人任合明(51)Int.Cl.H04L29/12(2006.01)(54)发明名称一种IPv6活跃地址动态发现方法(57)摘要本发明公开了一种IPV6活跃地址动态发现方法，目的是解决目前IPV6活跃地址发现方法正确率较低、速度较低的问题。技术方案是将IPv6地址转化为高进制向量并对已知活跃地址对应的向量即种子向量集合采用自顶向下分裂层次聚类的方法生成空间树，利用空间树根据在分裂层次聚类过程后种子向量在每个维度扩展后的有效地址密度值来预测不同维度的取值变化性，并提供从叶子结点到根结点路径的搜索方向。本发明能够基于实时扫描结果和空间树动态地调整方向以在发现了更多活跃地址的路径上快速得到下一步的扫描目标地址，达到提高活跃地址发现正确率和速度的目的。权利要求书3页说明书7页附图3页CN109905497A2019.06.18CN109905497A1.一种IPv6活跃地址动态发现方法，其特征在于包括以下步骤：第一步：将已知的IPv6活跃地址作为种子向量，令此已知的IPv6活跃地址集合为集合G1，令G1中共有N个IPv6活跃地址，N为正整数，依据G1中IPv6地址二进制整数大小将G1中的IPv6地址排序，得到排序后的二进制IPv6地址集合G2；第二步：将G2中的N个二进制IPv6地址转换成K进制表示的IPv6地址，K为2的p次幂，p为正整数，即按照p位为一项将128bit的IPv6地址转换为用128/p维向量，一维即一个K进制位，得到N个用128/p维向量表示的IPv6地址的集合G3，G3中的每个向量的维度序号为1～128/p，越靠近维度序号1，维度就越低，越靠近维度序号128/p，维度就越高；第三步：采用分裂层次聚类方法对G3中的向量进行层次聚类，得到空间树，方法是：3.1定义空间树的结构：树中的每个节点是一个七元组结构，七元组结构为(AA，DS，TS，SS，NDA，NDAS，AAD)，AA是一个集合，存贮IPv6地址向量；DS是一个栈结构，存贮IPv6地址向量的维度序号，其项数小于等于IPv6地址向量的维度数即128/p，非叶子节点的DS从低维到高维压入AA内所有向量在同一维度上的值相同的维度序号；叶子节点首先继承父节点的DS栈信息，还从低维到高维压入剩下的不在栈中的维度信息；TS是存储所属节点即将扫描的目标IPv6地址向量的集合，SS是存储所属节点已经扫描过的IPv6地址向量的集合，NDA为所属节点下扫描到的活跃地址数量，是一个正整数，NDAS为所属节点下扫描到的活跃地址集合，AAD为有效地址密度值，AAD＝在所属节点内扫描到的活跃地址数/在所属节点内扫描过的地址数；3.2将G3中的元素按维度向下进行层次聚类，具体步骤如下：3.2.1初始化空间树Tree：令Tree的根节点V0的AA＝G3，令V0的TS和SS都为空，令V0的NDA为0，将V0的AA内所有向量在同一维度上的值相同的维度序号压入DS；初始化向量个数变量n＝|G3|为V0中向量个数，若n小于进制数K，则表示空间树已生成，不再产生聚类，转第四步，否则执行步骤3.2.2；3.2.2扩展Tree的节点，方法是：3.2.2.1令l为Tree中当前需要进行聚类操作的层，令l＝1，令NL_l为Tree中第l层的节点个数；3.2.2.2如若第l层不存在节点，则转第四步，否则，令节点vli表示Tree中第l层的第i个节点，令i＝1；3.2.2.3令节点v＝vli，判定节点v的AA中向量个数是否大于等于K，若满足，转3.2.3.4进行聚类；否则，表示节点v不再往下聚类，并按低维到高维将不在v的DS中的维度信息压入DS，转3.2.3.5；3.2.2.4从低维度向高纬度观察节点v的AA内所有向量，找到第一个值不同的维度序号，设此维度序号为k，1≤k≤128/p，根据k对节点v的AA内的向量进行分组，根据维度k上的取值将节点聚合成不同的子节点，令维度k上共有M种不同的值，则将AA中的向量根据这M个不同的值分成M组，节点v根据维度k上的取值聚合成M个不同的子节点,这M个子节点定义为V1,V2,…Vm,…,VM，1≤m≤M，且这些子节点处在树的第l+1层上，令V1,V2,…Vm,…,VM的DS值均等于节点v的DS值，并将维度序号k压入V1,V2,…Vm,…,VM的DS中，V1,V2,…Vm,…,VM都是节点v的子节点，且同一个子节点的AA内的所有向量在维度k上的值相同，不同子节点的AA在维度k上的值不同；权　利　要　求　书1/3页2CN109905497A23.2.2.5令i＝i+1，若i＝NL_l则转入3.2.2.3进行同一层下一个节点的聚类操作，否则l＝l+1，并转入3.2.2.2进行下一层次聚类操作；第四步：利用空间树对IPv6地址进行动态扫描，得到活跃地址，方法是：4.1对IPv6地址预扫描，初始化叶子节点，方法是：4.1.1令Tree的所有叶子节点构成叶子节点序列PP，令PP中有MM个节点，令PPjj为序列PP中第jj个叶子节点，将PP中MM个叶子节点的TS、SS初始化为空，将PP中MM个叶子节点的NDA初始化为0：4.1.2令叶子节点顺序变量jj＝1；4.1.3弹出叶子节点PPjj的DS栈顶值DS0，将叶子节点PPjj的AA中每个向量在维度DS0处枚举0～K-1所有取值情况(即K进制中的0～K-1这K个数字，即每个向量形成扩展后的K个向量，形成PPjj的新向量集合，并将PPjj的新向量集合除去扩展前的PPjj的向量集合的结果赋值给叶子节点PPjj的TS集合；4.1.4依次扫描PPjj的TS集合中向量所对应的IPv6地址，得到活跃的IPv6地址，同时得到活跃的IPv6地址数量，将此数量赋值给PPjj的NDA，同时将PPjj的TS中的向量全部移到PPjj的SS中，并将扫描到的活跃的IPv6地址对应的向量存入PPjj的活跃地址集合NDAS中；4.1.5计算叶子节点PPjj的有效地址密度值AADjj，AADjj＝PPjj的NDA/PPjj的|SS|，|SS|表示SS中元素的个数；4.1.6令jj＝jj+1,若jj小于等于MM，转4.1.3，若jj大于MM，表示此时已得到AAD1，…，AADjj,…,AADMM，转4.1.7；4.1.7叶子节点序列PP中所有的叶子节点都将自身的NDA值、SS集合和NDAS集合添加到各自父节点的NDA值、SS集合和NDAS集合中，添加过程NDA为累加，SS和NDAS为集合的并操作；4.1.8利用链表List_Leaf将叶子节点序列PP中的叶子节点按照AAD值从大到小排列，即AAD最大的叶子节点为表头，AAD最小的叶子节点为表尾，并令List_Leaf中有NN个节点，NN为正整数；4.2对IPv6地址进行正式扫描，方法是：4.2.1若链表List_Leaf中只有一个节点，即NN＝1，转4.2.4，否则转4.2.2；4.2.2将链表List_Leaf按照叶子节点AAD值从大到小重新排列，即AAD最大的叶子节点为表头，AAD最小的叶子节点为表尾，并令NN＝排列后的List_Leaf中的节点个数；4.2.3按List_Leaf的节点顺序对Tree进行剪枝，方法是：4.2.3.1令节点序号变量ii＝1；4.2.3.2检查List_Leaf的第ii个节点，若发现第ii个节点的DS值与第ii个节点的父节点相同，则进行剪枝，即将第ii个节点的父节点下所有子节点的SS和NDAS集合中的元素分别添加到第ii个节点的父节点的SS和NDAS集合中，并将这些子节点的NDA值累加到第ii个节点的父节点的NDA值中，并令第ii个节点的父节点的NDA值为所有叶子节点NDA值之和的平均值即所有叶子节点NDA值之和/该父节点的子节点个数，然后将Tree中该父节点下的所有叶子节点删除，该父节点成为Tree中新的叶子节点，并顶替原叶子节点在List_Leaf中的第ii个位置，转4.2.2；若第ii个节点的DS值与第ii个节点的父节点不相同，则转4.2.3.3；4.2.3.3令ii＝ii+1,判定ii≤NN是成立，若成立，转4.2.3.2，若不成立，说明对Tree剪权　利　要　求　书2/3页3CN109905497A3枝完毕，转4.2.4；4.2.4按List_Leaf的节点顺序，选择IPv6扫描对象，方法是：4.2.4.1令节点序号变量ii＝1；4.2.4.2弹出List_Leaf的第ii个节点的DS的栈顶值DS_0，将第ii个节点内的每个向量在维度DS_0处枚举0～K-1所有取值情况，即每个向量形成扩展后的K个向量，形成第ii个节点的新向量集合，并将所得扩展后的向量集合除去扩展前的叶子节点集合的结果赋值给第ii个叶子节点的TS集合；4.2.4.3将第ii个节点的TS与SS的差集放到差集集合dii中；4.2.4.4扫描dii内向量对应的IPv6地址，将差集集合dii中的元素添加到第ii节点的SS集合中，根据扫描到的活跃地址结果计算第ii节点的NDA和AAD值，并将扫描到的活跃地址所对应的向量存入第ii节点的NDAS集合中；4.2.4.5若NN＝1，转第五步；若NN≠1，则转4.2.2；第五步：将List_Leaf中唯一节点的NDAS中的每个向量的每一维度转换为p位2进制数，所对应的所有二进制数则为扫描到的活跃IPv6地址，将活跃IPv6地址输出。2.如权利要求1所述的一种IPv6活跃地址动态发现方法，其特征在于第四步所述扫描IPv6地址采用ZMapv6扫描器。3.如权利要求1所述的一种IPv6活跃地址动态发现方法，其特征在于所述p＝4,K＝16。权　利　要　求　书3/3页4CN109905497A4一种IPv6活跃地址动态发现方法技术领域[0001]本发明涉及互联网领域IP地址发现方法，尤其指一种针对IPv6活跃地址主动扫描的动态发现方法。背景技术[0002]作为下一代互联网的网络层基础，IPv6在加速演进发展。在2018年，超过20％的谷歌用户使用IPv6来访问其服务，而这个比例从2016年来前所未有地翻了两倍，同样规律的还有从BGP路由表中统计出来的IPv6路由数量，这说明IPv6的部署已经逐渐从网络的骨干走向边缘。估计到2019年，IPv6前缀的数量会达到IPv4前缀数量的25％到50％，并且IPv6流量会成为互联网中的重要组成部分。巨大的地址规模和方便的地址配置方式为未来互联网的发展奠定了良好基础。[0003]在IPv6地址空间中收集活跃IPv6地址集合可以帮助收集互联网上的联网设备属性信息，从而支持一系列研究和应用，包括：网络安全态势感知和应对、网络主机身份识别、IP地址分析和地理位置确定、网络拓扑发现等。目前这方面具有代表性的两个工作是：[0004]Entropy/IP(2016年P.Foremski,D.Plonka,A.W.Berger,Entropy/IP:Uncovering structure in IPv6addresses,in:Proceedings of the 2016 ACM on Internet Measurement Conference,IMC 2016,Santa Monica,CA,USA,November 14-16,2016,2016,pp.167–181.即2016年11月由P.Foremski,D.Plonka,A.W.Berger,Entropy在ACM网络测量国际会议上发表的论文《Entropy/IP:在IPv6地址中发现结构》)和6Gen(2017年A.Murdock,F.Li,P.Bramsen,Z.Durumeric,V.Paxson,Target g