, 林金磊1, 高浩11. 清华大学 网络科学与网络空间研究院, 北京 100084;
2. 北京信息科学与技术国家研究中心, 北京 100084;
3. 鹏城实验室, 深圳 518000
收稿日期：2020-01-20
基金项目：“十三五”国家重点研发计划（2018YFB1800201）
作者简介：李果(1996-), 男, 硕士研究生
通讯作者：杨家海, 教授, E-mail: yang@cernet.edu.cn
摘要：巨大的IPv6地址空间使得传统的IPv4地址暴力探测手段无法直接应用于IPv6活跃地址发现。该文提出一种基于多层级分类和空间建模的IPv6活跃地址发现算法。多层级分类算法引入多种维度信息用于对种子地址进行细粒度的划分；空间建模技术能够利用4种表示策略对任意地址集合建模，并生成合适的模式表示字符串，以权衡建模空间过大导致的探测效率低下问题和建模空间过小导致的样本偏差问题。通过对模式表示进行启发式遍历可发现新的活跃IPv6地址。实验结果表明所提出的地址发现算法比已有算法具有更高的命中率，并且验证了对种子地址进行细粒度的划分有助于提升地址发现算法的命中率。
关键词：IPv6网络测量扫描地址发现地址分类
IPv6 active address discovery algorithm based on multi-level classification and space modeling
LI Guo1, HE Lin1, SONG Guanglei1, WANG Zhiliang1,2, YANG Jiahai1,2,3
, LIN Jinlei1, GAO Hao11. Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing 100084, China;
2. Beijing National Research Center for Information Science and Technology, Beijing 100084, China;
3. Peng Cheng Laboratory, Shenzhen 518000, China
Abstract: The enormous IPv6 address space makes it impossible to apply traditional IPv4 brute-force scanning for IPv6 active address discovery. This paper presents an IPv6 address discovery algorithm based on multi-level classification and space modeling. The multi-level classification algorithm uses multi-dimensional information for fine-grained division of the seed addresses. The space modeling uses four representation strategies to model any address set with pattern representation used to balance the low detection efficiency caused by the large modeling space and the sample error caused by the small modeling space. New active IPv6 addresses can be discovered by heuristic traversal of the pattern representation. Tests show that this address discovery algorithm has a higher hit rate than previous methods and verifies that the fine-grained division of the seed address improves the hit rate of the address discovery algorithm.
Key words: IPv6network measurementsscanningaddress discoveryaddress classification
IPv6地址空间庞大，难以采用ZMap[1]全网暴力探测技术发现存活地址。近年来，许多研究者提出基于种子地址的活跃IPv6地址探测方法，即通过对IPv6种子地址结构规律的学习来生成待探测的可能存活的IPv6新地址。种子地址指的是研究者收集的长期或短期存活的IPv6地址。Ullrich等[2]在2015年提出根据种子地址集合在每个比特位的取值情况建立二叉搜索树，按照一定优先级顺序遍历每个比特位的取值。Foremski等[3]提出的Entropy/IP率先使用Shannon熵分析IPv6地址每个半字节位的随机程度，并使用Bayes网络对IPv6地址空间建模。Murdock等[4]提出基于密度聚类的6Gen算法，从高密度的取值空间生成可能存活的IPv6新地址。Gasser等[5]则是侧重研究种子地址本身，首次指出种子地址和生成地址分布都存在不平衡的问题；然后通过将种子地址按照自治号划分，分别采样一定数量的地址作为Entropy/IP和6Gen的输入来缓解不平衡问题。Liu等[6]提出了基于层次分裂的6Tree算法。Song等[7]提出在6Tree算法基础上改进的侦探(detective, DET)算法，该算法在寻找分裂点的过程中结合Shannon熵进行优化。
以上这些相关工作仍然存在许多不足：1) 这些工作存在生成的地址分布不平衡问题，即生成地址大部分集中在某些地址数量非常多的前缀或者某些特别活跃的地址空间区域。2) 相关工作几乎都是依靠IPv6本身的128比特信息对种子地址进行划分或分类，而忽略了地址关联的多个维度信息。3) 相关工作提出的地址空间建模的方法在建模空间大小的选择上存在缺陷，要么过分依赖收集的种子地址导致地址建模空间变小从而引发样本偏差问题，要么建模空间过大导致待生成的地址范围较大从而大幅降低命中率。
为了克服相关工作的不足，本文提出一种活跃地址发现算法，命名为Multi-BSPR-Gen (multi-level balanced space pattern representation generation)，该算法主要包括两大部分：1) 提出融合种子地址多维信息的多层级分类算法——Multi-level classification，用于将收集的全部种子地址集合进行更细粒度的划分，从包含全部种子地址集合的根节点开始不断对当前节点进行分裂，最终形成一个树状结构；2) 提出一种针对任意地址集合的空间建模技术——平衡空间模式表示(balanced space pattern representation, BSPR)，该技术能够对任意地址集合处理生成由4种表示策略组成的模式表示，并且在建模空间大小上有较好的平衡，然后通过启发式遍历模式表示的取值空间发现新的IPv6活跃地址。图 1展示了本文算法的组成模块。最终实验结果表明，Multi-BSPR-Gen不仅拥有比相关工作更高的命中率，也验证了对种子地址进行细粒度的划分有助于提升地址发现算法的命中率。
 |
| 图 1 Multi-BSPR-Gen算法组成关系 |
| 图选项 |
1 多层级分类算法与基于地址分裂的6Tree算法不同，多层级分类算法Multi-level classification不仅利用IPv6地址128比特本身蕴含的信息(地址结构信息)，还结合每个IPv6地址关联的多维信息对种子地址集合进行划分。
1.1 种子地址的多维信息多层级分类算法总共使用种子地址的4个维度信息：
1) 自治号(autonomous system number, ASN)和边界网关协议(border gateway protocol, BGP)前缀。每个自治系统都需要1个ASN，同时IPv6地址的BGP前缀也是路由过程中重要的特征依据。多数相关工作以ASN或BGP前缀对种子地址进行划分，然后在每个地址集合上分别生成新的地址，并通过探测判断地址是否活跃。
2) 地址响应类型。地址响应类型是指IPv6种子的响应情况，命名为activity。本文对每个IPv6种子地址进行存活性探测，包括联网控制信息协议版本6(Internet control message protocol version 6, ICMPv6)请求、20个常见传输控制协议(transmission control protocol, TCP)和20个常见用户数据包协议(user datagram protocol, UDP)服务端口[8]。根据响应情况划分为4类：存在端口开放并且响应ICMPv6、存在端口开放但不响应ICMPv6、仅响应ICMPv6以及没有任何响应ICMPv6。虽然对IPv6地址进行端口扫描会增加探测时间成本和带宽开销，但是却能带来两方面好处：(1) 结合端口探测和ICMPv6请求的响应结果可更加准确地判断地址存活性。文[9-12]指出仅依靠ICMPv6是否有响应判断地址存活性会出现较多漏报和误报，因为部分网络环境会丢弃ICMPv6请求或由中间节点响应接收到的ICMPv6请求。(2) IPv6地址探测响应情况往往反映了该地址真实类型，比如服务器地址大部分会存在端口开放、路由节点地址大部分没有端口开放等。将类型相近的地址划分到一起，有助于改善地址发现算法的学习效果，进而提高命中率。
3) 地址稳定信息。地址稳定信息是指IPv6地址在一定时间范围内的活跃天数，属于时间维度上的特征，命名为stability。文[9]指出结合这个信息有助于挖掘地址活跃空间。本文对收集的种子地址进行了为期30 d的存活性探测，因此stability在本文的取值范围是[0, 30]的整数域。在实践中，IPv6地址会由于多种原因导致并不是稳定活跃的情况，比如客户端地址、动态分配的地址以及临时地址等。
4) 地址的接口标识符号(interface identifier, IID)取值量化指标。IID用于指明主机或路由器单个的网络接口，通常是IPv6后64个比特位，即最后16个半字节位。基于种子地址的IPv6活跃地址发现算法最重要的就是对IID部分进行预测和生成。为了量化IPv6地址的IID取值情况，用xi表示IPv6地址第i个半字节的取值(标准的IPv6地址有32个半字节)，其取值范围是16进制[0, f]；对于IID部分，i的取值范围是[17, 32]；符号r表示IID部分取值种类。描述IID取值情况的量化指标Q可由式(1)计算得到：
| $(x, v) = \left\{ {\begin{array}{*{20}{l}}{1, }&{x = v;}\\{0, \;\;\;{\kern 1pt} }&{x \ne v.}\end{array}} \right.$ | (1) |
| $Q = \frac{{\max \left\{ {\sum\limits_{i = 17}^{32} c \left( {{x_i}, v} \right)\mid v = 0, 1, \cdots , {\rm{e}}, {\rm{f}}} \right\}}}{r}$ | (2) |
表 1 IID取值量化指标示例
| IID示例 | r | Q | LOG_Q |
| 0000:0000:0000:0000 | 1 | 16.0 | 2.0 |
| ffff: ffff: ffff: 0001 | 3 | 4.0 | 1.5 |
| 0000:0000:ac43:262f | 8 | 1.0 | 1.0 |
| 80b3:4154:c437:d7fe | 12 | 0.25 | 0.5 |
| 0123:4567:89ab: cdef | 16 | 0.062 5 | 0.0 |
表选项
为了让Q取值更加均匀并且避免取对数后出现负数，使用式(3)得到描述IID取值情况的最终指标LOG_Q。
| ${\rm{LO}}{{\rm{G}}_ - }{\rm{Q}} = {\log _{16}}Q + 1.{\rm{ }}$ | (3) |
表 2 种子地址的多维信息
| 多维信息 | 描述 | 数值类型 | 取值范围 | 获取方式 |
| ASN/BGP PREFIX | 自治号/BGP前缀 | 非数值型 | 数据库查询 | |
| activity | 探测响应类型 | 非数值型 | 4种类型 | ICMPv6和40个端口的主动探测 |
| stability | 稳定信息 | 数值型 | [0, 30] | 持续30 d的主动存活探测 |
| LOG_Q | IID取值量化指标 | 数值型 | [0.0, 2.0] | 式(3) |
表选项
 |
| 图 2 (网络版彩图)Multi-level classification算法实现效果示意图 |
| 图选项 |
 |
| 图 3 Multi-level classification算法 |
| 图选项 |
1) 和大部分相关工作一样，首先将种子地址集合按照ASN和BGP前缀进行划分。
2) 根据响应信息这个离散特征的4类情况进行划分，分别为存在端口开放并且响应ICMPv6请求、存在端口开放但不响应ICMPv6请求、仅响应ICMPv6以及没有任何响应ICMPv6共4类。
3) IPv6地址的stability和LOG_Q是数值型特征，利用FINDBESTSPLIT函数分别对当前节点IPv6地址的stability和LOG_Q特征进行排序，然后从小到大遍历，根据输入的预设阈值h_rate和最小地址数量限制min_num寻找符合条件的跃变位置作为切分点，最后将地址集合依次根据stability的切分点和LOG_Q的切分点进行划分。
为了避免出现过多拥有地址数量较少的叶子节点，算法引入最小地址数量限制——min_num机制。在ASN之后的其余划分过程中，如果某次划分导致新生成的节点中超过25%以上节点的地址数量小于min_num，那么就跳过本次划分，保留父节点继续后续划分步骤。
2 空间建模和地址生成本节提出的BSPR-Gen技术可以用于处理任何输入的IPv6地址集合，是本文提出的Multi-BSPR-Gen的重要模块。
BSPR-Gen算法的核心是BSPR。BSPR会基于输入的地址集合生成最合适的模式表示，然后通过启发式遍历模式表示生成新的IPv6地址。
2.1 相关工作地址空间建模缺陷地址空间建模的目的是生成任意一个IPv6种子地址集合的某种表示方式，该表示方式能够刻画这个种子地址集合所在的地址空间范围，这样地址生成策略和地址探测策略就能在该范围内发现新的IPv6地址。相关工作的地址空间建模方法主要包括3种：1) Pattern-based[2]方法使用二叉搜索树。二叉搜索树利用地址集合的每一个比特位取值为0或1的相对大小表示IPv6地址集合的地址空间范围。2) Entropy/IP[3]使用的Bayes网络。Bayes网络根据每个半字节的Shannon熵进行分块，然后在块之间建立条件概率关系。3) 6Gen[4]和6Tree[6]使用的通配符。这种方式是将IPv6地址集合中所有变化的半字节都用一个通配符代替，这些半字节的取值范围为16进制单个数字的所有取值情况。
前两种地址建模方法得到的地址空间范围过小，即完全依赖种子地址本身取值情况生成新的地址，这会导致样本偏差问题，最终使得地址探测策略很难发现未被种子地址收集到的潜在活跃IPv6地址；最后一种地址建模方法得到的地址空间范围过大，即认为变化的半字节取值范围为16进制单个数字的所有取值情况，这会导致待生成的地址范围过大，最终降低探测效率和命中率。
2.2 空间建模技术BSPR为了克服相关工作中模式表示单一以及建模空间过大过小的问题，本文提出BSPR。该技术通过分析输入的IPv6地址集合，生成合适的模式表示。BSPR主要由2个步骤组成：
步骤1?? BSPR采用4种表示策略生成任意地址集合的模式表示：Single、List、Range和Wildcard。其中Single策略用于表示输入的地址集合中没有取值变化的半字节位置。本文提出的4种表示策略含义和取值范围如下：
? Single：固定值，表示地址集合在该半字节位置没有变化。
? List：变化值，取值范围是地址集合在该半字节位置取值的集合。
? Range：变化值，取值范围是地址集合在该半字节位置的最小值到最大值的闭区间，可能会包括该半字节位置在地址集合中未出现的取值。
? Wildcard：变化值，取值范围是16进制全部取值，可能会包括该半字节位置在地址集合中未出现的取值，使用通配符*表示。
BSPR会计算IPv6地址的每个半字节位置在输入的地址集合中的3个统计量：极差、Shannon熵、取值种类数。对于第i个半字节位置其Shannon熵定义为
| ${\rm{ Shannon }}\left( {{x_i}} \right) = - \sum\limits_{v = 0}^{\rm{f}} p \left( {{x_i} = v} \right){\log _{16}}p\left( {{x_i} = v} \right).$ | (4) |
表 3展示了BSPR是如何根据这3个统计量确定该半字节位置的模式表示。3个统计量属于较大还是较小分别由极差阈值range_t、熵值阈值entropy_t和取值种类数阈值type_t决定。图 4展示了1个典型的地址集合的模式表示。
表 3 BSPR使用的4种表示策略和3个统计量的关系
| 序号 | 极差 | 熵值 | 取值种类数 | 表示策略 | 符号示例 | 取值个数 |
| 0 | 0 | 0.00 | 1 | Single | {a} | 1 |
| 1 | 较大 | 较大 | 较大 | Wildcard | *(通配符) | 16 |
| 2 | 较大 | 较大 | 较小 | List | {1, c, f} | 3 |
| 3 | 较大 | 较小 | 较大 | Range | {1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e} | 14 |
| 4 | 较大 | 较小 | 较小 | List | {2, b, e} | 3 |
| 5 | 较小 | 较大 | 较大 | Range | {6, 7, 8, 9, a, b} | 6 |
| 6 | 较大 | 较大 | 较小 | List | {6, 7, 9} | 3 |
| 7 | 较小 | 较小 | 较大或较小 | List | {6, 7} | 2 |
表选项
 |
| 图 4 (网络版彩图)一个典型的地址集合的模式表示 |
| 图选项 |
步骤2?? BSPR需要解决如何确定3个超参阈值的问题，即极差阈值range_t、熵值阈值entropy_t和取值种类数阈值type_t。如果阈值过小，那么建模的地址空间迅速增大，极端情况是3个超参均被设置为0，则生成的模式表示几乎等同于Wildcard策略。如果阈值过大，那么建模空间过小，极端情况是3个超参均取最大值，则生成的模式表示几乎等同于List策略，而List策略的取值完全依赖种子地址集合的取值情况，会加重样本偏差问题。
假设模式表示中的List、Range和Wildcard个数分别为l、r、w；用Lj、Rj分别代表在第j个List或Range策略的取值个数，j的取值范围最大值对于List或Range策略分别是l、r；Wildcard是通配符，取值范围是单个半字节的全部取值，即单个16进制数字的16种取值。任意一个模式表示的空间范围(space range, SR)的大小由式(5)计算得到，
| ${\rm{SR}} = {16^w} \cdot \prod\limits_{j = 1}^l {{L_j}} \cdot \prod\limits_{j = 1}^r {{R_j}} .$ | (5) |
设三元函数SR在式(5)定义域的值域为集合Y，因为自定义域是有限个数的网格，所以集合Y也是有限的，不妨设SR在Y值域有N个取值。BSPR选择的最平衡的BalancedSR应该是Y值域的几何平均值，
| ${\rm{ BalancedSR }} = \sqrt[N]{{\prod\limits_{{\rm{S}}{{\rm{R}}_j} \in Y} {{\rm{S}}{{\rm{R}}_j}} }}.$ | (6) |
| $\mathop {{\mathop{\rm argmin}\nolimits} }\limits_{{\rm{rang}}{{\rm{e}}\_{\rm{t}}},{\rm{entrop}}{{\rm{y}}\_{\rm{t}}}, {\rm{typ}}{{\rm{e}}\_{\rm{t}}}} \mid {\rm{ SR - BalancedSR }}\mid .$ | (7) |
1) 对于输入的单一地址集合。
首先使用BSPR在输入的单一地址集合上生成模式表示，然后采用深度优先搜索(depth first search, DFS)遍历模式表示的取值范围得到新的IPv6地址。设S表示输入的单一地址集合，对于不同的表示策略有不同的遍历顺序：
? Single：固定值，仅一种取值。
? List：按照该策略所在的半字节位置在S中的不同取值出现次数，从高到低遍历。
? Range：优先遍历该策略表示的地址范围里在S对应半字节位置出现过的数值，并按照该数值在S对应半字节位置出现次数从高到低遍历；对于没有在S对应半字节位置出现过的数值，采用随机遍历。
? Wildcard：该策略的取值范围是单个半字节的全部取值，即单个16进制数字的16种取值，因此先生成16种取值的随机全排列，然后按照顺序遍历。
此外，深度优先搜索在遍历过程中会跳过种子地址集合中已有的IPv6地址，并且不会生成重复的IPv6新地址。当模式表示的地址范围被全部遍历或者达到生成的地址总量时，遍历操作停止。
2) 对于Multi-level classification的多个叶子节点。
BSPR-Gen会对每个叶子节点集合生成模式表示，然后按照模式表示的地址范围大小顺序依次生成地址(从地址范围较小的叶子节点开始生成地址)，在这个过程中根据生成的地址总量设置每个叶子节点生成的地址上限(尽可能保证每个叶子节点都能贡献一定新的地址)。
最终算法会在所有叶子节点的地址范围被遍历完成或者达到用户指定的生成地址总量时停止。
3 实验本文主要通过文[5]提供的ZMapv6和Nmap[13]扫描工具进行主动探测，并从相关工作公开的IPv6地址来源以及私有服务器提取IPv6地址作为数据集，即种子地址。
3.1 数据集表 4展示本文使用的IPv6种子地址源的名称、来源、地址类型、日期和对应的地址数量，去重后总共获得大约2 424万条地址，涵盖1.5万个ASN以及4.7万个BGP前缀。为了缓解别名地址对地址发现算法的影响，本文采用文[5]在2020年12月份累计公开的别名前缀数据集对收集的种子地址进行过滤，发现1 252个别名前缀，最终保留了大约1 700万条种子地址。BGP前缀数据是2020-10-24通过PYASN[14]获取。
表 4 本研究收集的IPv6种子地址
| 数据集名称 | 数据集来源 | 地址类型 | 日期 | 地址数量/万条 |
| Rapid7-dnsaaaa | Rapid7 FDNS AAAA数据集 | Server | 2020-12-24 | 1 116.325 |
| Caida-dnsnames | CAIDA IPv6 DNS数据集 | Server | 2020-12-24 | 8.97 |
| Alexa | Alexa百万域名列表 | Server | 2020-12-20 | 9.64 |
| Statvoo | Statvoo百万域名列表 | Server | 2020-12-20 | 8.92 |
| Umbrella | Cisco Umbrella百万域名列表 | Server | 2020-12-20 | 11.61 |
| Openipmap | RIPE OpenIPMap数据集 | Router | 2020-12-20 | 3.17 |
| Ripe-atlas | RIPE Atlas数据集 | Router | 2020-12-24 | 19.22 |
| Gasser-weekly | 每周更新的数据集 | Server/Router/Client | 2020-12-20 | 0.34 |
| Vantagepoints | 探测系统(Multi-BSPR-Gen-Sys) | Server/Router/Client | 2020-12-20 | 1 112.674 |
| CT | 证书透明日志中的TLS证书 | Server | 2020-12-18 | 81.78 |
表选项
3.2 实验设置存活性探测：采用ZMapv6发送ICMPv6请求，采用Nmap对常见的20个TCP端口[8]和常见的20个UDP端口[8]进行探测。对于任意1个IPv6地址，扫描器将发送41个请求，如果有任何1个请求收到对应的响应，则将该IPv6地址视为存活地址。
实验节点：本文设置了2个扫描节点，即扫描器发送请求的节点，分别部署于清华大学和DigitalOcean的新加坡节点。
输入的数据集：本文收集的经过去重和别名去除后的全部种子地址集合，命名为C。
参数设置：根据集合C中全部地址的stability和activity取值情况，设置h_rate=0.1较为合适。此外，最小地址数量限制min_num设置为10。
命中率定义：探测发现的存活IPv6地址总数与算法生成的地址数量的比值。
3.3 命中率对比实验本文使用Multi-BSPR-Gen和Entropy/IP、6Gen、6Tree、DET共5种算法分别生成10万、20万、30万、40万和50万条新的IPv6地址，并对比命中率，算法的输入都是种子地址集合C。
同时，为了分析本文提出的Multi-level classification对地址发现算法命中率影响，将Entropy/IP和6Gen两种算法分别在经过Multi-level classification处理过的叶子节点上运行，计算总的命中率。针对6Tree和DET，可使用本文提出的Multi-level classification替换原本的层次分裂算法。实验结果如图 5所示，图 5的图例中前缀“Multi-”表示该方法结合了本文提出的Multi-level classification算法。
 |
| 图 5 (网络版彩图)Multi-level classification |
| 图选项 |
对5种地址生成算法命中率的影响对比图 5中各曲线在不同生成地址数量上的表现可以发现，使用Multi-BSPR-Gen具有最高的命中率，即最好的探测效果。随着生成地址数量增加，Multi-BSPR-Gen的命中率稳定性较好，该算法即便在生成50万条新的IPv6地址的条件下也仍然能发现大约15万条新的IPv6存活地址。此外，从是否使用了Multi-level classification算法的实验对照组中可以得出结论：对种子地址进行更细粒度的划分并将地址发现算法分别作用于划分后的多个地址集合上，有助于提升探测命中率。即使6Tree和DET这些算法提出了各自的层次分裂方法，也可以结合本文提出的多层次分类算法来提升命中率。
3.4 种子地址多维信息的作用与主要依靠ASN和BGP前缀划分种子地址的相关工作相比，本文提出的Multi-level classification利用了与地址相关的多维信息。为了进一步分析这些额外引入的相关信息对最终命中率的提升究竟有多大贡献，本文设置了如下5组对照实验：
?组1：完全按照Multi-level classification执行。
?组2：关闭Multi-level classification里的activity划分模块，其他划分模块保持打开。
?组3: 关闭Multi-level classification里的stability划分模块，其他划分模块保持打开。
?组4: 关闭Multi-level classification里的LOG_Q划分模块，其他划分模块保持打开。
?组5：保留Multi-level classification按照ASN和BGP前缀划分的模块，关闭所有其他划分模块。
将BSPR-Gen算法分别应用于组1到组5的实验中，生成100万、500万、1 000万条IPv6地址并进行存活性探测，然后统计命中率。为了消除随机生成地址操作带来的误差，重复5次实验并计算平均命中率。图 6展示了组1到组5在BSPR-Gen算法下的命中率。
 |
| 图 6 (网络版彩图)种子地址相关信息对命中率的影响 |
| 图选项 |
从图 6可以看出，与组1相比，其他实验组的命中率在生成不同数量的候选地址条件下都有所降低，说明这些多维信息对最终的探测效果都有所贡献，其中组4的LOG_Q特征贡献最大。组5命中率表现最差，表明将本文提出的BSPR-Gen算法直接用于处理每个前缀下的全部种子地址总体效果较差。此外，随着生成地址数量增加，各组命中率都有所下降，其中组1的命中率下降幅度相对较小，这表明对种子地址进行更细粒度的划分有助于稳定地址生成算法在不同生成地址数量上的命中率。
3.5 地址发现算法成本比较这里主要讨论本文提出的Multi-BSPR-Gen算法以及相关工作的6Gen、6Tree、DET、Entropy/IP这5种地址生成算法在预处理耗时、算法时间复杂度、发包效率和运行耗时(定量) 4个方面的成本代价对比。采用定性分析结合定量对比来评估这5种算法各自的成本代价，结果如表 5所示。
表 5 5种地址发现算法的成本代价对比
| 地址发现算法 | 预处理耗时 | 算法时间复杂度 | 发包效率 | 运行耗时/s |
| Multi-BSPR-Gen | 稳定信息和端口信息获取耗时较长 | O(n) | 较高 | 3 765.2 |
| 6Gen | 按照前缀划分，较快 | O(n4) | 较高 | 153 267.3 |
| 6 Tree | 无 | O(nlbn) | 较低 | 14 481.6 |
| DET | 无 | O(n) | 较低 | 6 031.9 |
| Entropy/IP | 按照前缀划分，较快 | O(n) | 较高 | 11 232.7 |
表选项
预处理耗时指的是将收集的种子地址交给地址发现算法处理之前需要花费的时间。算法时间复杂度是指地址发现算法的时间复杂度。发包效率指的是在探测生成地址时能否结合高并发的发包和收包技术。运行耗时(定量)是指程序从启动到结束花费的时间。
此外，考虑到6Gen耗时过高，本文从收集的种子地址集合中按照ASN分别采样总计大约200万条地址集合作为5种地址发现算法的输入，生成5 000万条待探测IPv6地址，以此计算其运行耗时。
本文提出的算法在运行耗时上优于其他地址发现算法，但是预处理耗时远高于其他相关工作；6Gen时间复杂度较高，运行耗时远高于其他算法；6Tree和DET由于探测和地址生成是反馈进行的，导致很难应用一些高效的并发探测技术对生成地址作存活性验证，发包效率较低。此外，DET和6Tree相比，在探测反馈阶段少了排序操作，算法时间复杂度略低。
3.6 发现的活跃地址类型分析为了进一步评估发现的活跃IPv6地址，本小节分析了所发现的活跃地址所属的地址类型，即Server端地址、Router地址和Client地址。为了提高地址类型分析的准确性，本文提出两种策略来识别IPv6地址所属类型：
策略1?? 根据发现的IPv6活跃地址的BGP前缀所属的种子地址源来判断该地址的类型。比如发现的活跃地址前缀属于表 4的Ripe-atlas，则认为是Router地址。这里有2个要点需要说明：1) 与大多数基于种子地址的地址发现算法类似，Multi-BSPR-Gen算法生成的地址BGP前缀一定属于种子地址的BGP前缀集合；2) 如果BGP前缀属于多个种子地址来源或者属于表 4中Gasser-weekly和Vantage points这类有多种地址类型的种子地址源，可以根据Multi-BSPR-Gen执行过程中用于生成该活跃IPv6地址的种子地址中出现次数最多的地址类型作为生成地址的类型。
策略2?? 结合文本涉及的端口探测信息和提出的LOG_Q指标对地址进行分类。如果发现的活跃地址LOG_Q较大、没有开放任何端口服务并且以: : 1或者: : 2这类模式结尾则优先视为Router地址；如果有任何开放的端口服务信息则视为Server地址；其余的情况视为Client地址。
表 6展示了Multi-BSPR-Gen在种子地址集合C上发现的29.7万条活跃地址(生成100万条地址)的地址类型分析结果。从表 6可以看出，两种策略得到的Server、Router和Client地址类型数量相对大小关系是一致的，即服务地址最多，客户端地址最少。客户端地址占比较少的主要原因是客户端地址稳定时间太短且可达性较差。
表 6 29.7万条活跃地址的地址类型统计
| 地址类型 | 地址类型占比/% | |
| 策略1 | 策略2 | |
| Server | 67.9 | 62.1 |
| Router | 24.3 | 21.1 |
| Client | 7.8 | 16.8 |
表选项
通过横向对比可以发现，两种策略在分析结果中具体的比例上存在差异。这种差异性来自多种原因，常见的原因有：所属来源是Server种子地址但是完全没有端口开放，或者所属地址来源是Router种子地址但是生成的地址结构不符合: : 1或者: : 2模式。
4 结论本文针对IPv6活跃地址探测问题提出一种基于多层级分类和空间建模的活跃地址发现算法Multi-BSPR-Gen。该算法由两个部分组成：1) 基于种子地址多维信息的多层级分类算法对种子地址进行了更细粒度的划分；2) 基于4种表示策略对任意地址集合建模的空间建模技术，能够生成地址集合最合适的模式表示，以权衡建模空间过大导致的探测效率低下问题和建模空间过小导致的样本偏差问题，然后通过启发式遍历规则生成新的IPv6地址。实验结果证明了Multi-BSPR-Gen具有最好的命中率，并且也验证了对种子地址进行更细粒度的划分能够提升多种地址发现算法的命中率。在下一步工作中，一方面将改进地址发现算法使其能处理某些地址数量极少场景下的地址发现，另一方面将尝试设计更好的空间建模技术以便能够找到尽可能覆盖全部潜在活跃地址的最小地址空间范围。
参考文献
| [1] | DURUMERIC Z, WUSTROW E, HALDERMAN J A. ZMap: Fast Internet-wide scanning and its security applications[C]//Proceedings of the 22nd USENIX Conference on Security (SEC'13). Washington DC, USA, 2013: 605-620. |
| [2] | ULLRICH J, KIESEBERG P, KROMBHOLZ K, et al. On reconnaissance with IPv6: A pattern-based scanning approach[C]//10th International Conference on Availability, Reliability and Security (ARES). Toulouse, France, 2015: 186-192. |
| [3] | FOREMSKI P, PLONKA D, BERGER A. Entropy/IP: Uncovering structure in IPv6 addresses[C]//Proceedings of the 2016 Internet Measurement Conference. Santa Monica, USA, 2016: 167-181. |
| [4] | MURDOCK A, LI F, BRAMSEN P, et al. Target generation for Internet-wide IPv6 scanning[C]//Proceedings of the 2017 Internet Measurement Conference. London, UK, 2017: 242-253. |
| [5] | GASSER O, SCHEITLE Q, FOREMSKI P, et al. Clusters in the expanse: Understanding and unbiasing IPv6 hitlists[C]//Internet Measurement Conference (IMC). Boston, USA, 2018: 364-378. |
| [6] | LIU Z Z, XIONG Y Q, LIU X, et al. 6Tree: Efficient dynamic discovery of active addresses in the IPv6 address space[J]. Computer Networks, 2019, 155: 31-46. |
| [7] | SONG G L, HE L, WANG Z L, et al. Towards the construction of global IPv6 hitlist and efficient probing of IPv6 address space[C]//International Symposium on Quality of Service (IWQoS). Hangzhou, China, 2020: 1-10. |
| [8] | NMAP. Top 20 and 200 most scanned ports in the cybersecurity industry[Z/OL]. [2021-01-15]. https://nmap.org/book/port-scanning.html. |
| [9] | PLONKA D, BERGER A. Temporal and spatial classification of active IPv6 addresses[C]//Internet Measurement Conference (IMC). Tokyo, Japan, 2015: 509-522. |
| [10] | RICHTER P, SMARAGDAKIS G, PLONKA D, et al. Beyond counting: New perspectives on the active IPv4 address space[C]//Internet Measurement Conference (IMC). Santa Monica, USA, 2016: 135-149. |
| [11] | MCINNES L, HEALY J, ASTELS S. hdbscan: Hierarchical density based clustering[J]. The Journal of Open Source Software, 2017, 2(11): 205. |
| [12] | GASSER O, SCHEITLE Q, GEBHARD S, et al. Scanning the IPv6 Internet: Towards a comprehensive hitlist[C]//Proceeding of the 8th International Workshop on Traffic Monitoring and Analysis (TMA). Louvain-la-Neuve, Belgium, 2016: 1-8. |
| [13] | NMAP. Nmap: The network mapper[Z/OL]. [2021-01-15]. https://nmap.org. |
| [14] | PYASN. PYASN[Z/OL]. [2020-12-24]. https://github.com/hadiasghari/pyasn. |
