本发明属于网络安全技术，尤其涉及一种互联网自治系统间商业关系的推断方法。本发明方法包括两个阶段，可靠关系推断和不确定关系推断。在第一阶段，使用可靠的规则和数据源来推断高度可信的商业关系，并在时间维度上对推断的结果进行投票。利用将概率标签生成与集成学习相结合的半监督学习来推断不确定的商业关系。半监督学习方法可以发现之前获得的可靠商业关系中顾客和提供商关系以及对等体关系之间的固有差异，从而对未确定的关系进行分类。因此本发明方法在商业关系推断上既能保持准确性又具有稳定性，还解决了对等体商业关系难以推测的问题。
1.一种互联网自治系统间商业关系的推断方法，其特征在于，包括以下步骤：
(1)从互联网组织下载边界网关协议的原始数据，并对原始数据进行预处理，得到BGP路径，具体过程如下：(1‑1)从边界网关协议的原始数据中提取路径信息，从路径信息中删除因路由策略而导致的重复自治系统号，同时从路径信息中删除包含路由环路的异常路径，得到第一BGP路径；
(1‑2)从互联网号码分配机构获取步骤(1‑1)的第一BGP路径中自治系统号码分配记录，从该分配记录中删除未分配的自治系统号码和必须保留的自治系统号码，得到第二BGP路径；
(1‑3)根据互联网上公开的第一层自治系统列表，当步骤(1‑2)的第二BGP路径中的两个第一层自治系统之间被一个或多个非第一层自治系统隔开时，则删除该相应路径，得到第三BGP路径；
(1‑4)从互联网交换中心获取互联网交换中心列表，根据中心列表，将步骤(1‑3)的第三BGP路径上的已经出现在互联网交换中心列表中的自治系统号码删除，得到BGP路径；
(2)对步骤(1)预处理得到的BGP路径进行可靠商业关系推断，得到BGP路径中部分自治系统之间的可靠商业关系，包括以下步骤：(2‑1)从互联网路由注册表中获取自治系统的商业关系，根据商业关系，对步骤(1)的BGP路径上自治系统的商业关系进行标注，所述的商业关系为运营商客户关系、客户运营商关系或对等体关系；
(2‑2)从互联网上获取第一层自治系统列表，将步骤(1)的BGP路径上任意两个第一层自治系统的商业关系标注为对等体关系；
(2‑3)利用无谷原则，对BGP路径上自治系统的运营商客户关系进行标注，包括以下步骤：
(2‑3‑1)设一条BGP路径中的自治系统AS1、AS2、……、ASn‑1、ASn、ASn+1……、ASm中包含了第一层自治系统，其中下标n、m为任意自治系统的号码，若ASn是BGP路径中的最后一个第一层自治系统，则根据无谷原则，得到AS1～ASn‑1之间所有自治系统之间的商业关系为客户运营商关系，ASn+1～ASm之间所有自治系统之间的商业关系为运营商客户关系；
(2‑3‑2)设一条BGP路径中的自治系统AS1、AS2、……ASn、ASn+1……、ASm，其中包含了对等体关系，则将对等体关系之前的自治系统商业关系推断为客户运营商关系，之后的自治系统商业关系推断为运营商客户关系；
(2‑3‑3)设一条BGP路径中的自治系统AS1、AS2、……ASn、ASn+1……、ASm，其中没有一个自治系统属于第一层自治系统，或没有一个自治系统商业关系为对等体关系，但其中有一条链接ASn、ASn+1为运营商客户关系，则根据无谷原则，将ASn+1～ASm之间的所有链接推断为运营商客户关系；或其中有一条链接ASn、ASn+1为客户运营商关系，则根据无谷原则，将AS1到ASn之间的所有链接都推断为客户运营商关系；
(2‑4)遍历步骤(1)的BGP路径，重复步骤(2‑3‑3)的操作，直至推断得到BGP路径中的所有运营商客户关系或客户运营商关系，完成遍历；
(2‑5)多次从互联网组织下载边界网关协议的原始数据，并对原始数据进行预处理，重复上述步骤(2‑1)到步骤(2‑4)得到多个商业关系的推断结果，对多个商业关系的推断结果进行投票，即将多个商业关系的推断结果中的同一链接的推断结果相同，则将该推断得到的商业关系加入到该自治系统可靠商业关系中，重复上述过程，得到BGP路径中部分自治系统之间的可靠商业关系；
(3)将步骤(2)的自治系统可靠商业关系作为标签，利用机器学习方法训练模型，推断互联网自治系统间的不确定商业关系，包括以下步骤：(3‑1)将步骤(2)的BGP路径中部分自治系统之间的可靠商业关系作为带标签的链接样本LR，构建一个与链接相关的特征集，利用欧几里得距离作为链接之间距离的度量，计算BGP路径中商业关系不确定的自治系统链接到各个带标签样本之间的距离，选取与商业关系不确定的自治系统链接最近的k个带标签样本；将BGP路径中商业关系不确定的自治系统链接记为无标签数据集LU，将无标签数据集LU中与带标签样本的欧几里得距离最近的k个带标签样本记为Nk(i)，利用下式，计算无标签数据集LU中每个不确定商业关系样本li属于每一类商业关系的概率其中，n＝0、1和2分别表示三种商业关系p2c、p2p和c2p；
(3‑2)设定一个从均匀分布U[0，1]中采样得到的随机数αi，根据步骤(3‑1)的概率利用下式，分别计算每个不确定自治系统商业关系的标签yi，得到一份不确定自治系统商业关系的标签：其中，k为与商业关系不确定的自治系统链接最近的带标签样本数，i为无标签数据集LU中无标签数据的序号；
(3‑3)多次重复步骤(3‑2)生成多份不确定自治系统商业关系的标签；
(3‑4)根据步骤(3‑3)中的多份不确定自治系统商业关系的标签，用LjU表示多份不确定自治系统商业关系的标签中的第j份不确定自治系统商业关系的标签；
(3‑5)采用XGboost模型作为基分类器，将步骤(3‑4)的多个 与步骤(2)的带标签的链接样本LR组合，对XGboost模型进行训练得到多个基分类器Modelj，利用Bagging方法，将多个基分类器Modelj集成为一个最终模型：(3‑6)将无标签数据集LU输入到步骤(3‑5)的最终模型中，输出得到BGP路径中商业关系不确定的自治系统链接的商业关系，完成互联网自治系统间商业关系的推断。
一种互联网自治系统间商业关系的推断方法
技术领域
[0001] 本发明属于网络安全技术，尤其涉及一种互联网自治系统间商业关系的推断方法。
背景技术
[0002] 互联网的商业化使得互联网的规模发生了巨大的扩张，目前互联网是一个由数万个自治系统(Autonomous System，以下简称AS)组成的巨大网络拓扑。这些自治系统通过边界网关协议(Border Gateway Protocol，以下简称BGP)进行协作，以交换路由信息并获得全局可达性。自治系统之间的联系由确定流量交换的经济和技术方面的业务合同决定，也就是所谓的自治系统之间的商业关系。AS商业关系可以分为四种类型，包括客户运营商关系(customer‑to‑provider，以下简称c2p)，对等体关系(peer‑to‑peer，以下简称p2p)，同胞关系(sibling‑to‑sibling，以下简称s2s)和混合关系。在c2p关系中，客户AS向运营商支付费用以访问互联网的其他部分。在p2p关系中，两家公司同意交换流量以交换他们或他们的客户拥有的前缀，而不收取传输费。当两个AS具有多个合同协议时，可能会发生混合或复杂的关系，其中一个协议是针对存在互连的每个地理区域的。同一个组织之间的不同AS之间存在同胞关系，它们可以交换流量而没有任何成本或路由限制。通常来说，c2p(或是p2c)和p2p是两个最为常见的商业关系。如果知道自治系统之间的商业关系，就能帮助我们更好的分析理解互联网，比如分析网络拥塞、网络鲁棒性，检测路由泄漏，制定部署BGP安全机制等等。由于自治系统商业关系包含了运营商之间的一些商业策略或者商业机密，大部分的运营商不会将自己与其他自治系统之间的商业关系公布出来。
[0003] 传统的商业关系推断方法主要是基于路由策略(无谷原则)来判断：来自客户的路由可以发送给运营商、客户、对等体，来自对等体或者运营商的路由只能发送给客户。运营商不应故意宣传从一个对等方或提供者向另一个对等方或提供者学习的路线，因为这种“免费运输”增加了基础设施成本，但不提供报酬。但是对于网络中大量的路由来说，这种基于无谷原则的方法无法确定所有链接之间关系，因此需要将路由策略与其他算法相结合来推断自治系统的商业关系。自治系统商业关系推断是现在比较热门的研究方向，大量的研究投入到该领域中。现有的工作在准确性和稳定性上的表现不符合实际应用的需求。
[0004] 考虑到实际网络中推断商业关系有如下的一些困难和挑战：1)日常收集的路由中包含噪声。每天都会产生大量的路由异常事件，由路由异常产生的噪声路由将正常的路由混合在一起难以区分。2)实际自治系统拓扑的可见性受到限制。从现有部署的观测点(vantage point,VP)获得的路由仅是网络中的一部分。随着VP的不断部署，对全网路由的可见性将会增加，使用现有方法推断自治系统商业关系的结果将变得不稳定。3)对等体关系很难推断。对于对等体关系的推断没有像客户运营商关系这样直接的启发式规则来确定，现有工作往往将客户运营商关系确定完之后剩下的链接全都推断为p2p关系。
发明内容
[0005] 本发明的目的是提出一种互联网自治系统间商业关系的推断方法，针对已有技术中存在的缺点，提出了基于概率标签生成的半监督学习来推断网络自治系统商业关系的方法，以准确和稳定的推断网络中自治系统商业关系。
[0006] 本发明提出的互联网自治系统间商业关系的推断方法，包括可靠商业关系推断和不确定商业关系推断两个阶段，第一阶段，使用可靠的规则和数据源，推断高度可信的自治系统间商业关系，并在时间维度上对推断的结果进行投票；第二阶段，利用将概率标签生成与集成学习相结合的半监督学习，推断不确定的自治系统间商业关系。
[0007] 本发明提出的一种互联网自治系统间商业关系的推断方法，其优点是：
[0008] 首先，使用一些可靠的规则和数据源来推断高度可信的商业关系，并在时间维度上对推断的结果进行投票。使用的规则是一些简单规则，受拓扑可见性有限的影响较小，考虑到异常事件带来的噪声往往持续事件较短，投票可以减少噪声的影响。然后，本方法利用将概率标签生成与集成学习相结合的半监督学习来推断不确定的商业关系。半监督学习方法可以发现之前获得的可靠商业关系中顾客和提供商关系以及对等体关系之间的固有差异，从而对未确定的关系进行分类。这样本方法在商业关系推断上既能保持准确性又具有稳定性，还解决了对等体商业关系难以推测的问题。
附图说明
[0009] 图1是本发明提出的互联网自治系统间商业关系的推断方法的流程框图。
具体实施方式
[0010] 本发明提出的互联网自治系统间商业关系的推断方法，包括可靠商业关系推断和不确定商业关系推断两个阶段，第一阶段，使用可靠的规则和数据源，推断高度可信的自治系统间商业关系，并在时间维度上对推断的结果进行投票；第二阶段，利用将概率标签生成与集成学习相结合的半监督学习，推断不确定的自治系统间商业关系。
[0011] 本发明的互联网自治系统间商业关系的推断方法，其流程框图如图1所示，具体包括以下步骤：
[0012] (1)从互联网组织下载边界网关协议的原始数据，并对原始数据进行预处理，得到BGP路径，具体过程如下：
[0013] (1‑1)从边界网关协议的原始数据中提取路径信息，从路径信息中删除因路由策略而导致的重复自治系统号，同时从路径信息中删除包含路由环路的异常路径，得到第一BGP路径；
[0014] (1‑2)从互联网号码分配机构(InternetAssigned Numbers Authority，简称IANA)获取步骤(1‑1)的第一BGP路径中自治系统号码分配记录，从该分配记录中删除未分配的自治系统号码和必须保留的自治系统号码，得到第二BGP路径；
[0015] (1‑3)根据互联网上公开的第一层自治系统(Tier‑1 AS)列表，当步骤(1‑2)的第二BGP路径中的两个第一层自治系统之间被一个或多个非第一层自治系统隔开时，则删除该相应路径，得到第三BGP路径；
[0016] (1‑4)从互联网交换中心获取互联网交换中心列表，根据中心列表，将步骤(1‑3)的第三BGP路径上的已经出现在互联网交换中心列表中的自治系统号码删除，得到BGP路径；
[0017] (2)对步骤(1)预处理得到的BGP路径进行可靠商业关系推断，得到BGP路径中部分自治系统之间的可靠商业关系，包括以下步骤：
[0018] (2‑1)部分运营商自愿将其路由策略登记在互联网路由注册表，因此可以从互联网路由注册表中获取自治系统的商业关系，根据商业关系，对步骤(1)的BGP路径上自治系统的商业关系进行标注，所述的商业关系为运营商客户关系、客户运营商关系或对等体关系；
[0019] (2‑2)从互联网上获取第一层自治系统列表，将步骤(1)的BGP路径上任意两个第一层自治系统的商业关系标注为对等体关系；
[0020] (2‑3)利用无谷原则，对BGP路径上自治系统的运营商客户关系进行标注，包括以下步骤：
[0021] (2‑3‑1)设一条BGP路径中的自治系统AS1、AS2、……、ASn‑1、ASn、ASn+1……、ASm中包含了第一层自治系统，其中下标n、m为任意自治系统的号码，若ASn是BGP路径中的最后一个第一层自治系统，则根据无谷原则，虽然无法确定ASn‑1、ASn和ASn、ASn+1直接的商业关系，但是可以得到AS1～ASn‑1之间所有自治系统之间的商业关系为客户运营商关系，ASn+1～ASm之间所有自治系统之间的商业关系为运营商客户关系；
[0022] (2‑3‑2)设一条BGP路径中的自治系统AS1、AS2、……ASn、ASn+1……、ASm，其中包含了对等体关系，例如ASn、ASn+1为对等体关系，则将对等体关系之前的自治系统商业关系推断为客户运营商关系，之后的自治系统商业关系推断为运营商客户关系；
[0023] (2‑3‑3)设一条BGP路径中的自治系统AS1、AS2、……ASn、ASn+1……、ASm，其中没有一个自治系统属于第一层自治系统，或没有一个自治系统商业关系为对等体关系，但其中有一条链接ASn、ASn+1为运营商客户关系，则根据无谷原则，将ASn+1～ASm之间的所有链接推断为运营商客户关系；或其中有一条链接ASn、ASn+1为客户运营商关系，则根据无谷原则，将AS1到ASn之间的所有链接都推断为客户运营商关系；
[0024] (2‑4)遍历步骤(1)的BGP路径，重复步骤(2‑3‑3)的操作，直至推断得到BGP路径中的所有运营商客户关系或客户运营商关系，完成遍历；通过迭代推断得到更多的运营商客户关系或客户运营商关系。
[0025] (2‑5)本发明的一个实施例中，根据一个月四周，每周选一天数据，多次从互联网组织下载边界网关协议的原始数据，并对原始数据进行预处理，重复上述步骤(2‑1)到步骤(2‑4)，得到多个商业关系的推断结果，对多个商业关系的推断结果进行投票，即将多个商业关系的推断结果中的同一链接的推断结果相同，则将该推断得到的商业关系加入到该自治系统可靠商业关系中，重复上述过程，得到BGP路径中部分自治系统之间的可靠商业关系；
[0026] (3)将步骤(2)的自治系统可靠商业关系作为标签，利用机器学习方法训练模型，推断互联网自治系统间的不确定商业关系，包括以下步骤：
[0027] (3‑1)将步骤(2)的BGP路径中部分自治系统之间的可靠商业关系作为带标签的链接样本LR，构建一个与链接相关的特征集，利用欧几里得距离作为链接之间距离的度量，计算BGP路径中商业关系不确定的自治系统链接到各个带标签样本之间的距离，选取与商业关系不确定的自治系统链接最近的k个带标签样本；将BGP路径中商业关系不确定的自治系统链接记为无标签数据集LU，将无标签数据集LU中与带标签样本的欧几里得距离最近的k个带标签样本记为Nk(i)，利用下式，计算无标签数据集LU中每个不确定商业关系样本li属于每一类商业关系的概率 li∈LU：
[0028]
[0029] 其中，n＝0、1和2分别表示三种商业关系p2c、p2p和c2p；
[0030] (3‑2)设定一个从均匀分布U[0，1]中采样得到的随机数αi，根据步骤(3‑1)的概率利用下式，分别计算每个不确定自治系统商业关系的标签yi，得到一份不确定自治系统商业关系的标签；
[0031]
[0032] 其中，k为与商业关系不确定的自治系统链接最近的带标签样本数，i为无标签数据集LU中无标签数据的序号；
[0033] (3‑3)多次重复步骤(3‑2)，生成多份不确定自治系统商业关系的标签；
[0034] (3‑4)根据步骤(3‑3)中的多份不确定自治系统商业关系的标签，用 表示多份不确定自治系统商业关系的标签中的第j份不确定自治系统商业关系的标签；
[0035] (3‑5)采用XGboost模型作为基分类器，将步骤(3‑4)的多个 与步骤(2)的带标签的链接样本LR组合，对XGboost模型进行训练，得到多个基分类器Modelj，利用Bagging方法，将多个基分类器Modelj集成为一个最终模型：
[0036]
[0037] (3‑6)将无标签数据集LU输入到步骤(3‑5)的最终模型中，输出得到BGP路径中商业关系不确定的自治系统链接的商业关系，完成互联网自治系统间商业关系的推断。
