一种基于BGP前缀树的IP地址路由可达性识别方法

摘要

本发明公开了一种基于BGP前缀树的IP地址路由可达性识别方法，包括：步骤1.获取多个数据采集节点的BGP路由数据并汇总和预处理，所述预处理包括将所有BGP路由数据按照目标前缀字段进行排序；步骤2.针对步骤1排序后的BGP路由数据，根据前缀间的包含关系进行分组并基于各组前缀构建前缀树；步骤3.针对步骤2获得的各个前缀树，独立地计算其中各个前缀路由可达的置信度；步骤4.对比各个前缀路由可达的置信度和预设门限，获得整个IPv4地址空间路由可达的所有前缀。本发明可实现对多源BGP信息的合理融合，进而为整个IPv4地址空间生成一致的IP地址路由可达性分析结果，为后续的深度探测扫描提供优选目标。

权利要求

1.一种基于BGP前缀树的IP地址路由可达性识别方法，其特征在于，包括：步骤1. 获取多个数据采集节点的BGP路由数据并汇总和预处理，所述预处理包括将所有BGP路由数据按照目标前缀字段进行排序；

步骤2. 针对步骤1排序后的BGP路由数据，根据前缀间的包含关系进行分组并基于各组前缀构建前缀树；

步骤3. 针对步骤2获得的各个前缀树，独立地计算其中各个前缀路由可达的置信度；

步骤4. 对比各个前缀路由可达的置信度和预设门限，获得整个IPv4地址空间路由可达的所有前缀；

所述步骤1包括以下子步骤：

步骤101. 从包括但不限于Routeviews和RIPE NCC的BGP监测项目中获取最新的BGP路由数据；

步骤102. 每条BGP路由数据包含Network, Next Hop, Metric, LocPrf, Weight, Path字段，抽取其中的Network和Next Hop字段，然后对所有BGP路由数据进行预处理；

所述对所有BGP路由数据进行预处理包括以下子步骤：

步骤1021. 将Next Hop字段的IP地址替换为该IP地址对应的/24位网段；

步骤1022. 将BGP路由数据进行去重，若多条数据的Network字段和替换后的Next Hop字段都相同，则仅保留一条；

步骤1023. 按照Network字段对应的起始地址和末尾地址的大小对所有BGP路由数据进行排序，获得Network字段起始地址从小到大排列的数据序列；

所述步骤2包括以下子步骤：

步骤201. 遍历排序后的所有BGP路由数据，判断当前BGP路由数据Network字段对应的前缀 是否为根前缀，若是则执行步骤202，否则执行步骤203；同时将Next Hop字段的网段地址加入前缀 对应的观测节点集 中；

步骤202. 初始化一个新的前缀树，用包含前缀 的前缀列表 表示，再执行步骤

204；

步骤203. 如果前缀 不是新前缀树的根前缀，且不同于当前前缀树的前缀列表中最后一个前缀，则将前缀 加入到当前前缀树中，用前缀列表 表示，再执行步骤

204；

步骤204. 将每个前缀树按照前缀间的包含关系由前缀列表的形式转换为树状结构；

所述步骤3包括以下子步骤：

步骤301. 按照自上而下的方向更新前缀树中除根节点外的所有节点对应的观测节点集合，节点 即前缀 的父节点记为 ，更新准则为 ；

步骤302. 对前缀树中每个叶节点对应的前缀 ，用其对应的观测节点集合的元素个数 表示其路由可达的置信度，记为 。

2.根据权利要求1所述的基于BGP前缀树的IP地址路由可达性识别方法，其特征在于，所述前缀树是一种节点为前缀、边为前缀之间包含关系的树状结构，如果两个不同的前缀和前缀 满足前缀 包含前缀 ，则存在一条前缀 指向前缀 的边。

3.根据权利要求1所述的基于BGP前缀树的IP地址路由可达性识别方法，其特征在于，所述步骤4包括以下子步骤：步骤401. 计算所有前缀对应的观测节点集合的并集，记为 ；

步骤402.  设置判决门限 （如），对各个前缀树中的叶节点前缀 ，如果，则认为前缀 是路由可达的，否则认为前缀 路由不可达。

4.根据权利要求1‑3任一项所述的基于BGP前缀树的IP地址路由可达性识别方法，其特征在于，对于步骤2和步骤3，采用并行计算方式对不同前缀树进行处理。

说明书

一种基于BGP前缀树的IP地址路由可达性识别方法

技术领域

[0001] 本发明涉及网络空间测绘技术领域，尤其涉及一种基于BGP前缀树的IP地址路由可达性识别方法。

背景技术

[0002] 随着网络空间发展为人类生产生活的第五空间，学术界和产业界对通过网络空间测绘技术生成能够反映全球网络空间资源分布及其连接关系的网络地图的需求越发强烈。在生成网络空间地图的过程中，IP地址通常被作为区分网络空间资源的唯一标识，是对各类网络目标进行探测时的直接输入。长度为32bit的IPv4地址总数有近43亿，虽然IP地址资源管理的官方机构在2019年11月宣告已将所有可用地址分配出去，但并不代表所有IPv4地址均已投入使用。在对网络空间中的各类目标进行深度探测前，若能首先通过主动或被动的方式掌握目标区域在用且路由可达的IP地址集合，可以极大地减小探测目标输入集，提升探测效率。

[0003] 在主动探测方面，Zmap和Masscan是最为典型的两个IP地址存活性探测工具。它们的工作原理类似，向每个目标IP地址发送特定类型的探测报文，然后根据目标的响应行为判定其是否存活。这类方法的问题在于：一方面，主动发包的方式在大规模探测过程中会给网络带宽带来极大压力，严重时会使得网络发生拥塞，从而导致网络性能下降影响网络的正常业务；另一方面，由于依赖于探测目标对探测报文的响应，当探测目标由于安全等级设置较高而不对探测报文进行响应，或者由于网络拥塞发生丢包而导致探测源未能收到响应报文时，会导致大量存活IP地址被遗漏。

[0004] 在被动探测方面，可用的信息来源包括流量数据、系统访问日志数据、BGP路由数据等。它们的工作原理大同小异，认为能够从源数据中解析获得的IP地址即为存活IP或者可路由IP。流量、系统访问日志等数据的问题在于它们有很强的局限性，只能覆盖地址空间的极小部分。在数据采集节点数量较多、分布合理的前提下，根据BGP路由数据中可以判断整个地址空间的各个IP前缀是否路由可达。但是，IP前缀的划分粒度在不同数据采集节点对应的数据中各不相同，导致不同节点获得的IP前缀之间存在复杂的嵌套关系或者异常冲突，因此，需要对这些数据进行合理的融合并生成一致的结果。

[0005] 然而，现有方法常采用简单粗暴的方法将所有IP地址划分到/24位前缀中，然后计算每个/24位IP前缀的出现次数，认为出现次数超过某个预设门限值的前缀即为可路由前缀。例如，文献Lost in Space:Improving Inference of IPv4 Address  Space Utilization,IEEE Journal on Selected Areas in Communications,vol.34,no.6,pp.1862‑1875,Jun.2016.和Estimating Internet Address Space Usage Through Passive Measurements,ACM SIGCOMM Comput.Commun.Rev.,vol.44,no.1,pp.42‑49,Jan.2014均采用上述思路分析/24位IP前缀在互联网中的使用情况。

发明内容

[0006] 为解决现有技术中存在的技术问题，特别是基于被动数据的IP地址路由可达性识别方法中，对多源BGP数据进行融合时未能有效解决IP前缀间的复杂关系和异常冲突的问题，本发明提出一种基于BGP前缀树的IP地址路由可达性识别方法，通过构建以前缀为节点、前缀间的包含关系为边的前缀树，用树状结构中节点间的父子关系在前缀间传递BGP数据采集节点的信息，从而实现对多源BGP信息的合理融合，进而为整个IPv4地址空间生成一致的IP地址路由可达性分析结果，为后续的深度探测扫描提供优选目标。

[0007] 本发明采用的技术方案如下：

[0008] 一种基于BGP前缀树的IP地址路由可达性识别方法，包括：

[0009] 步骤1.获取多个数据采集节点的BGP路由数据并汇总和预处理，所述预处理包括将所有BGP路由数据按照目标前缀字段进行排序；

[0010] 步骤2.针对步骤1排序后的BGP路由数据，根据前缀间的包含关系进行分组并基于各组前缀构建前缀树；

[0011] 步骤3.针对步骤2获得的各个前缀树，独立地计算其中各个前缀路由可达的置信度；

[0012] 步骤4.对比各个前缀路由可达的置信度和预设门限，获得整个IPv4地址空间路由可达的所有前缀。

[0013] 进一步地，所述步骤1包括以下子步骤：

[0014] 步骤101.从包括但不限于Routeviews和RIPE NCC的BGP监测项目中获取最新的BGP路由数据；

[0015] 步骤102.每条BGP路由数据包含Network,Next Hop,Metric,LocPrf,Weight,Path字段，抽取其中的Network和Next Hop字段，然后对所有BGP路由数据进行预处理。

[0016] 进一步地，所述对所有BGP路由数据进行预处理包括以下子步骤：

[0017] 步骤1021.将Next Hop字段的IP地址替换为该IP地址对应的/24位网段；

[0018] 步骤1022.将BGP路由数据进行去重，若多条数据的Network字段和替换后的Next Hop字段都相同，则仅保留一条；

[0019] 步骤1023.按照Network字段对应的起始地址和末尾地址的大小对所有BGP路由数据进行排序，获得Network字段起始地址从小到大排列的数据序列。

[0020] 进一步地，所述步骤2包括以下子步骤：

[0021] 步骤201.遍历排序后的所有BGP路由数据，判断当前BGP路由数据Network字段对应的前缀Fc是否为根前缀，若是则执行步骤202，否则执行步骤203；同时将Next Hop字段的网段地址加入前缀Fc对应的观测节点集V(Fc)中；

[0022] 步骤202.初始化一个新的前缀树，用包含前缀Fc的前缀列表[Fc]表示，再执行步骤204；

[0023] 步骤203.如果前缀Fc不同于当前前缀树的前缀列表中最后一个前缀，则将前缀Fc加入到当前前缀树中，用前缀列表[Fr,…,Fe,Fc]表示，再执行步骤204；

[0024] 步骤204.将每个前缀树按照前缀间的包含关系由前缀列表的形式转换为树状结构。

[0025] 进一步地，所述前缀树是一种节点为前缀、边为前缀之间包含关系的树状结构，如果两个不同的前缀Fp和前缀Fc满足前缀Fp包含前缀Fc，则存在一条前缀Fp指向前缀Fc的边。

[0026] 进一步地，所述步骤3包括以下子步骤：

[0027] 步骤301.按照自上而下的方向更新前缀树中除根节点外的所有节点对应的观测节点集合，节点Fc即前缀Fc的父节点记为Fp，更新准则为V(Fc)＝V(Fc)∪V(Fp)；

[0028] 步骤302.对前缀树中每个叶节点对应的前缀Fl，用其对应的观测节点集合的元素个数|V(Fl)|表示其路由可达的置信度，记为

[0029] 进一步地，所述步骤4包括以下子步骤：

[0030] 步骤401.计算所有前缀对应的观测节点集合的并集，记为Va；

[0031] 步骤402.设置判决门限tj，对各个前缀树中的叶节点前缀Fl，如果则认为前缀Fl是路由可达的，否则认为前缀Fl路由不可达。

[0032] 进一步地，对于步骤2和步骤3，采用并行计算方式对不同前缀树进行处理。

[0033] 与现有技术方案相比，本发明的上述技术方案具有如下有益的技术效果：

[0034] (1)提出了IP前缀树模型和相应的生成方法，以IP前缀为节点、前缀间的包含关系为边，将每个前缀对应的BGP数据采集节点集合作为前缀节点的路由可达性置信度计算依据，用节点间的父子关系在前缀间传递置信度信息，准确反映了BGP协议执行路由聚合时的规则，能够有效消除从不同BGP数据采集节点获得的观测数据中的冲突。

[0035] (2)IP前缀的路由可达判决结果基于多个BGP数据采集节点的观测数据综合判断得到，能够有效降低由于小范围的路由波动等异常情况造成的测量误差的影响，判别结果更具鲁棒性。

[0036] (3)本发明输出互不相交且规模大小不等的IP前缀，这些前缀在全球BGP路由系统中作为路由寻址的基本单元出现，可为网络拓扑测绘技术在制订IP路径探测任务时的目标IP选择策略、绘制互联网拓扑地图时的“地图比例尺”选取等工作提供重要参考。

附图说明

[0037] 图1是本发明的IP地址路由可达性识别方法流程图。

[0038] 图2是原始的BGP路由数据样例。

[0039] 图3是本发明的IP地址路由可达性识别方法处理后的BGP路由数据样例。

[0040] 图4是本发明提出的前缀树构造流程示例。

具体实施方式

[0041] 为了对本发明的技术特征、目的和效果有更加清楚的理解，现说明本发明的具体实施方式。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明，即所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明的实施例，本领域技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0042] 如图1所示，本实施例提供了一种基于BGP前缀树的IP地址路由可达性识别方法，包括BGP数据汇聚及预处理、前缀分组及前缀树构建、前缀路由可达性的置信度计算、前缀路由可达性判决这4个步骤。

[0043] 一、BGP数据汇聚及预处理

[0044] 从包括但不限于Routeviews和RIPE NCC的多个BGP监测项目数据集中获得其最新的BGP路由数据，然后抽取每条BGP数据中的Network和Next Hop字段，再对所有数据基于Next Hop对应的/24位前缀去重以及基于Network排序。

[0045] 去重时，首先将Next Hop字段的IP地址转换为/24位前缀后，然后将完全一致的数据去重。例如，图2中的第3条和第5条数据的Network均为1.0.4.0/22，Next Hop分别为147.28.7.1和147.28.7.2，转换为/24位前缀后均为147.28.7.0/24，因此仅保留其中一条即可。

[0046] 排序时，判断两个前缀先后顺序的准则为：记前缀F1和F2的起始IP分别为x1和x2，末尾IP分别为y1和y2；如果x1x2，则F1位于F2后面；x1＝x2的情况下，如果y1≥y2则F1位于F2前面，如果y1

[0047] 例如，图3所示的两个前缀1.0.4.0/22和1.0.5.0/24对应的起始IP分别为1.0.4.0和1.0.5.0，由于1.0.4.0<1.0.5.0，因此1.0.4.0/22将位于1.0.5.0/24前面。特别地，1.0.4.0/22和1.0.4.0/24对应起始IP都为1.0.4.0，而他们的末尾IP分别为1.0.7.255和
1.0.4.255，由于1.0.7.255>1.0.4.255，因此1.0.4.0/22位于1.0.4.0/24前面。

[0048] 二、前缀分组及前缀树构建

[0049] 将排序后的前缀划分为若干个互不相交的组，每组前缀可以形成一颗前缀树。分组时的关键步骤在于找到组的起始前缀，也就是后续生成前缀树时的根前缀。

[0050] 判断当前前缀Fc是否根前缀的准则包括：(1)若Fc是第一个前缀，则它必然是新前缀树的根前缀；(2)记当前根前缀为Fr，若Fc和Fr不同且不是Fr的子网段，即Fc的起始IP大于Fr的末尾IP，则Fc为新前缀树的根前缀。

[0051] 例如，图4所示的输入数据中所有数据已按照Network字段排序，其中第一个前缀1.0.4.0/22是根前缀，其后续的1.0.4.0/24、1.0.5.0/24、1.0.5.0/25都是它的子前缀。因此1.0.4.0/22、1.0.4.0/24、1.0.5.0/24、1.0.5.0/25被划分到同一组，作为前缀树构建步骤的输入。此外，输入数据中1.0.5.0/25后面一条数据的Network值为1.0.16.0/24，由于
1.0.16.0/24和1.0.4.0/22不同且不是1.0.4.0/22的子网段，因此1.0.16.0/24应是下一个分组的第一个前缀，即另一个前缀树的根前缀。

[0052] 将每个分组的前缀列表转换为树状结构的步骤包括：

[0053] (1)针对列表中除根前缀外的每个前缀寻找其最近的父节点前缀，增加一条父节点前缀到当前前缀的有向边；

[0054] (2)定义前一步获得的树状结构中没有子节点的前缀为叶节点前缀，按照自下而上的方向删除冗余的叶节点前缀——如果叶节点前缀Fl的所有兄弟节点前缀以及它自身对应的观测节点集合与它们的父节点前缀Fp的观测节点集合相同，则将Fl和它所有的兄弟节点删除。

[0055] (3)迭代执行第(2)步，直到无法继续删除冗余的叶节点前缀。

[0056] (4)在适当位置补充缺失的叶节点前缀，使得前缀树中每个非叶节点的子节点是“完备的”，即子节点的并集和父节点相等，每个新补充的叶节点前缀Fl对应的观测节点集合V(Fl)和其父节点前缀Fp对应的观测节点集合V(Fp)一致，即V(Fl)＝V(Fp)。

[0057] 例如，图4中第一个前缀序列[1.0.4.0/22,1.0.4.0/24,1.0.5.0/24,1.0.5.0/25]，其中1.0.4.0/22为根前缀，因此需要从第二个前缀开始寻找各个前缀的最近父节点前缀。对于1.0.4.0/24和1.0.5.0/24，其最近父节点前缀都是1.0.4.0/22；对于1.0.5.0/25，其最近父节点前缀为1.0.5.0/24。因此上述第(1)步执行结束后，生成的树状结构包含4个节点，3条边。其中，1.0.4.0/22为根节点，1.0.4.0/24和1.0.5.0/25为叶节点。在上述第(2)步，并无叶节点被删除，因为1.0.4.0/24和1.0.5.0/25都不满足所述条件。假如，1.0.5.0/
25对应的观测节点集合不包含91.218.184.0/24，因此和1.0.5.0/24对应的观测节点集合相同，且1.0.5.0/25没有其他兄弟节点，第(2)步操作将会直接将叶节点1.0.5.0/25删除，使得1.0.5.0/24成为新的叶节点，并继续执行第(3)步。执行第(4)步时，可以发现非叶节点为1.0.5.0/24和1.0.4.0/22，它们的子节点都不完备。需要为1.0.5.0/24新增子节点
1.0.5.128/25，为1.0.4.0/22新增子节点1.0.6.0/23，且新增的子节点都为叶节点，它们对应的观测节点集合和各自父节点对应的观测节点集合一致。

[0058] 特别地，分组完成后某些分组可能只包含一个前缀，由此得到的前缀树即为只有一个节点的平凡树结构。例如，图4中的第二个前缀序列仅包含1.0.16.0/24一个前缀，因此构建得到的前缀树为平凡树。

[0059] 三、前缀路由可达性的置信度

[0060] 前缀路由可达性的置信度由可路由到该前缀的BGP数据采集节点的数量进行反映。但是为了消除BGP数据采集节点在整个互联网中分布不均匀导致的采样偏差，本实施例在前述步骤中首先将BGP数据中Next Hop的IP地址转换为/24位前缀。例如，图2中的147.28.7.1和147.28.7.2在互联网中处于相同子网，应该被视为同一个数据采集节点而非两个，因此在数据预处理步骤将它们转换为147.28.7.0/24并去重后可以消除采样偏差。

[0061] 此外，由于前述步骤构建得到的前缀树中，所有叶节点形成一个对根前缀的完备划分：(1)所有叶节点互不相交；(2)所有叶节点的并集和根前缀相等。因此，对所有叶节点计算可路由到该前缀的BGP数据采集节点数量即可。同时，考虑到路由器在收到多条BGP路由信息时，会根据Network字段对多条信息进行聚合。因此，按照自上而下的方向更新前缀树中除根节点外的所有节点对应的的观测节点集合，使得子节点对应的观测节点集合能够继承其父节点对应的观测节点集合。

[0062] 例如，对于图4中的节点1.0.5.0/24，根据原始数据可知其对应的观测节点集合为{147.28.7.0/24,87.121.64.0/24}。但由于从144.228.241.0/24到1.0.5.0/22是可路由的，从144.228.241.0/24到1.0.5.0/24也必然是可路由的，因而需要将144.228.241.0/24增加到1.0.5.0/24对应的观测节点集合中，即V(1.0.5.0/24)被更新为{144.228.241.0/24,147.28.7.0/24,87.121.64.0/24}。类似的，在原始数据中节点1.0.5.0/25对应的观测节点仅有91.218.184.0/24，但其父节点1.0.5.0/24对应的观测节点集合被更新后为{144.228.241.0/24,147.28.7.0/24,87.121.64.0/24}，因此1.0.5.0/25对应的观测节点集合为V(1.0.5.0/25)＝{144.228.241.0/24,147.28.7.0/24,87.121.64.0/24,
91.218.184.0/24}。相应的，1.0.5.0/25的路由可达性的置信度值为4。

[0063] 四、前缀路由可达性判决

[0064] 以所有观测节点数为基数，根据预设门限决定该前缀是否路由可达，避免少量观测节点上的异常BGP数据干扰。

[0065] 在图4的示例中，所有观测节点对应的/24位前缀集合为Va＝{144.228.241.0/24,147.28.7.0/24,87.121.64.0/24,91.218.184.0/24,198.58.198.0/24}。若门限th＝0.6，可得1.0.4.0/24、1.0.5.0/25、1.0.5.128/25三个前缀是路由可达的，因为它们对应的观测节点集合分别包含3、4、3个元素，达到门限要求的th*|Va|＝3个。需要说明的是，实际应用中门限th的取值可以根据需要进行调整。

[0066] 需要说明的是，对于前述的方法实施例，为了简便描述，故将其表述为一系列的动作组合，但是本领域技术人员应该知悉，本申请并不受所描述的动作顺序的限制，因为依据本申请，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例，所涉及的动作和模块并不一定是本申请所必须的。