邓晓智，李昭桦

（1.广东电网有限责任公司电力调度控制中心，广东 广州 510000；2.中国能源建设集团广东省电力设计研究院有限公司，广东 广州 510000）

1 引言

随着IT技术的不断发展，人们对IT服务质量的要求越来越高。目前的服务等级协议（Service Level Agreement，SLA）[1]监测指标大都集中在延时、抖动、吞吐量、分组丢失率[2]等方面，旨在验证服务器正常运行的时间、存储可用性等[3]。而利用SLA来保障流量路径方面的研究还未形成体系，相关文献也较为稀缺。但无论是流量工程（Traffic Engineering，TE），服务功能链（Service Function Chain，SFC），还是基于策略的路由[3]，都要将流量引导到具体可控的路径上，否则将面临网络服务质量无法保证的问题。在网络功能虚拟化（Network Function Virtualization，NFV）的趋势下，流量传输路径的验证不再简单可控，这就需要研究一种满足虚拟网络下的传输路径验证（Proof of Transit，PoT）的新方法。

2 相关工作

已有部分研究对路由传输路径进行了验证，如文献[4]对安全连接（Security Association，SA）内路由的配置命令进行了分析，然后用模拟的方法对Internet路由进行验证，但这种方法有一定的局限性，并不能真实反映SA间的路由。文献[5]提出了一种胖树网络中源路由的生成与验证方法，但仅限于对物理网络设备端点的验证。文献[6]提出了基于协同的路由路径真实性验证机制，通过查询全局邻接信息和对等节点的邻接信息进行验证，这种方法同样无法应用于复杂多变的虚拟化网络。

随着软件定义网络（Software Defined Network，SDN）的不断推进，研究者对网络流量的路径定位迸发出了新的思路。文献[7]提出了一种路径流量监视机制，主要利用SDN控制器收集转发面流量，然后通过解析交换机流表项匹配次数来动态衡量网络流的经过情况。但这种方法在Overlay网络中不再适用，因为Overlay网络中的转发是通过虚拟逻辑节点，不需要知道这些节点之间的物理中间节点。

综合看来，分组遍历特定服务链的证据通常以间接方式提供：服务设备和网络转发过程位于不同的信任域中[8]，域之间定义不同的物理转发点，在转发域中，通过将流量传递到服务设备的入口，并从服务设备的出口返回的方式来标记路径。但随着NFV和SFC等新概念的涌现，定位编号分离协议（Locator Identity Separation，LISP）、网络服务头（Network Service Head，NSH）[9]等技术模糊了不同信任域之间的界限，信任域之间的接口将不再局限于物理接口，而是广泛地存在于虚拟接口上。因此需要将目标锁定在数据流上直接标记路径，这就对网络监控和测量提出了新的要求。

在面向网络监控和测量的技术中，最典型的当属Xiao H等人[10]提出的带内测量（In-band Network Telemetry，INT）技术。INT作为一种新型的网络测量手段，能够直接从SDN三层架构中的数据平面内部获取网络的状态参数，并在硬件上通过可编程交换机来完成测量。而Nick教授等人提出的P4高级编程语言[11]能实现对交换芯片流水线的控制，同时也解决了OpenFlow协议[12]编程能力不足以及其设计本身所带来的可拓展性差的难题。而在控制层面上，已有一种较为成熟的开放网络操作系统（Open Network Operating System，ONOS）控制器，它是一个采用开放服务网关倡议（Open Service Gateway Initiative，OSGI）技术来管理子项目的SDN控制器开源项目，同时提供P4 RunTime南向接口，能够很方便地对可编程数据平面进行集中控制。

根据现有的研究背景，提出的新方法就是对业务流量的一小部分进行标记并添加到每个数据包头中，以此作为传输证明的关键。再利用P4 RunTime和ONOS控制器对可编程交换机的集中控制来完成虚拟网络中传输路径的验证。

3 用于虚拟网络的PoT方法原理

在虚拟网络中，对流量真实路径验证方案的设计主要集中在两个方面：一是如何提取网络流抽象元素并与验证算法模型相对应；二是如何保证验证算法的真实有效性。

3.1 带内方式获取指标

首先，INT流量元将指令嵌入普通数据包中，由INT流接收器检索这些指令的收集结果，使得流接收器能够在包被转发的时候通过观测到的数据包监视到准确的数据平面状态。

其次，可以定义在多种设备上使用的元数据的一小部分，以传达这些元数据的准确含义，每个元数据都被编码为一个4B无符号值。

最后，在数据包传输的过程中，每经过一个交换机都会向数据包添加元数据，P4语言有自带的库可以读取这些元数据，包括交换机ID值、出入口时间戳值。数据包传到最后一个交换机时，之前向数据包添加的元数据会被弹出，送到分析引擎进行分析。

添加的PoT数据到达终点后，验证器可提取这些PoT数据来检查路径的正确性，这种方法的好处是其安全机制已经内嵌于PoT数据的构成中，以防止滥用。比如配置的错误、管理员恶意修改路由、拦截、回放数据包等。

3.2 多项式验证原理

在能够定位流量真实经过的中间节点基础之上，借用Shamir提出的秘密分享多项式算法，将传输路径看成是一组节点的有序组合，因此验证这个路径的正确性可以被等价为验证集合中每一个节点。这些点可以看成一个Secret的一些Shares，然后可以通过秘密分享多项式方法，在SDN控制器中还原成这个Secret多项式，具体如图1所示：

图1 PoT原理图

由于完整的Key设置只有控制器和验证器知道，这个Key就是完整的唯一的路径描述。当数据包经过路径上的每一个节点时，各节点使用自己的Secret或者Secret Share来更新PoT数据，当验证器收到这个包时，使用其Key来验证这个包是否沿着既定路径到达这里。

（1）模型参数

在二维空间中，将流量的路径抽象成一条曲线，途中经过的每个中间节点被看成组成曲线的点。横坐标是数据包头记录的节点标识ID，纵坐标是数据包头某固定字段中记录的对应各节点标识的值。

将部署流量路径的SDN控制器看作秘密分发者C，选取有n个中间节点作为秘密碎片的参与者V，这两类对象构成的(m, n)秘密分享SLA体制还需要满足多项式的分发与重构协议。

（2）秘密分发与重构

控制器在预先配置路径时，作为分发者首先需要选取一个m-1次多项式，并满足h(0)=R，则有：

随后控制器在一条流包含的全部节点域Fb中选择n个节点，并将它们在数据包标识字段中ID号定义为x1,x2, …, xn，最后，根据预先选取的多项式计算ym=h(xm),1≤i≤n，将y记录到被选取的节点ID对应的Value字段中，即定义了秘钥(xm, ym), 每对(xm, ym)就是曲线“h(x)”上的一个点。由于m个点唯一确定m-1次多项式h(x)，所以原参数R可以从m个碎片中重构出来。

进行重构时，先找到预先分发秘密碎片的中间节点，提取数据包头固定字段的信息(xi, yi)，然后利用拉格朗日（Lagrange）插值公式重构原参数R，如式(2)所示：

上述算法模型在数学理论上成立，但这种简单的秘密分享模型非常容易受到攻击，如果相同的多项式被每个数据包在同一条路径上重用，那么黑客也可以重用这些值。如果考虑在每个数据包上使用不同的多项式，那么这个计算的复杂度仍然是可控的。考虑到节点配置的复杂度，采用两个多项式会是一个折中的方案。

4 多项式叠加优化验证方案及论证

现有多项式A和B，其中A是一个保密的且不变的多项式，B是一个基于包的公开且随机的多项式。将每个节点上的A与B的Shares叠加作为第三个多项式C的点，并加到数据包上传给验证节点，验证节点会通过这些分散的点重构出多项式C，并验证C是否是A和B的叠加多项式，原理如图2所示。多项式A仅对验证节点是非保密的，这个方法利用了一定范围内质数的有限域算法。

4.1 多项式叠加验证步骤

验证的步骤主要分为以下三步：

图2 优化验证方案原理图

（1）节点配置

控制器首先生成维度为k的第一个多项式POLY-A以及POLY-A中的K+1个点，常数项即Secret，非常数项用来产生拉格朗日多项式常数（Lagrange Polynomial Constants，LPC）。然后给K个节点（包括验证节点）分配POLY-A中的点，其中验证节点被配置Secret常数。控制器同时也会产生一些系数（除了POLY-B常数项之外系数为随机数且各包不同）用于第二个同维度多项式POLY-B。

（2）传输

对于每个数据包而言，进入节点时会产生一个RND（POLY-B的常数项），此时累计值CML是0，RND和CML都是PoT中承载的重要数据，当数据包到达每个节点时，RND（POLY-B的Share）会被提取出来用于计算叠加后的Share，每个节点会计算POLY-A的Share叠加POLY-B的Share的值，同时CML会更新为此时的叠加值，这一步每个节点都会做，一直到数据包到达终点，验证器会做最后一次计算。

（3）验证

验证器检查CML是否等于Secret加RND的值，如果相等，那么数据包确实是按指定路径转发的，因为Shamir的加密分享多项式具有线性可叠加性质。为了更直观地表述，补充各个参数的定义如表1所示：

表1 参数定义说明表

4.2 给定场景中的算法论证

为了简化问题，假设一个三节点的场景，因此采用2阶多项式来描述路径。令Prime=53，Secret值为10，设置多项式：

令其通过3个点x0=2，x1=4，x2=5，分别带入式(3)，那么有：

以此类推，得到密码对：

将上述密码对分别带入拉格朗日公式，然后令LPC为拉格朗日多项式常数，由于定义的素数是53，那么LPC可能的值为10/3、-5、8/3，于是有：

那么有：

单多项式的PoT验证节点可通过上述算法简便地求解出Secret的值，对于提出的双多项式叠加的PoT方法而言，可依据上述论证方案再引入第二个多项式POLY-B。假设第二个多项式为：

它下发给节点的Shares会通过控制器提前定义好，比如这个多项式中的非常数项系数7和10。

由于每个节点已单独配置POLY-A的Share，于是这个累加值CML在重构的时候就得到了增强，对于每个节点而言，CML是这样更新的：

令起点处的RND为45，带入计算可以得到对应的Share为(2, 46)、(4, 21)、(5, 12)。然后根据式(10)计算每个节点的CML：

5 实验与结论

图3 实验原理图

将控制器提供给每个参与传输的节点的信息写入PoT配置文件，如图4所示，所有来自控制器提供的信息都参与到路径的验证中。

ONOS控制器以恒定速率创建新的PoT配置文件，并将PoT配置文件传送给节点，一旦PoT配置文件成功传送到所有节点（例如完成所有P4 RunTime事务），控制器就向入口节点发送“启用PoT配置文件”请求。所有节点也都保持两个PoT配置文件：一个会在当前处于活动状态并正在使用中；另一个处于待机状态并即将使用。

图4 PoT配置内容

还需要计算每个节点公共多项式的预估部分并将其添加到PoT配置文件，否则公共多项式的所有系数都必须添加到PoT配置文件中。公共部分只是常数系数RND值，所以每个节点的预估部分也应保密。为了使PoT数据中携带的累计值和随机数的大小更具灵活性，会在节点处共享和解析指示该字段。

采用32 bit位宽来存放RND和CML，在实验中其计算收敛耗时大约在200 s左右，根据第3章的论证可以完整地验证Secret值的正确性。

同时存在一个不可忽视的问题，即PoT字段的取值大小问题，PoT主要需要在每个数据包中传输RND随机数和CML累加数，其整个数据记录的大小决定了多长时间之后RND或者Secret的可用值会被耗尽。在最大值的情况下，RND值若用二进制表示可以决定它代表的POLY-B的个数，计算并归纳不同传输速度下两种字段位数分别需要的计算时间，如图5所示。当选择64 bit长度来表示RND和CML的数据时，即便是在100G的带宽下也可以维持3 100年而不用更新多项式。

6 结束语

随着虚拟化技术和云计算网络的广泛普及，SLA中的路径验证问题会变得越来越复杂且更重要，本文站在全局网络视图的角度，在经典的Shamir秘密多项式的基础上提出了一种新的叠加多项式的算法，并在小规模实验网络验证了其可行性和有效性，同时也归纳出如表2所示的计算收敛耗时表。这种结合了SDN集中控制和可编程数据平面带内测量技术的路径验证方式，既兼容虚拟化网络环境，也保证了验证过程自动且低负载，无需单独发送测试数据包，仅利用正常业务流量本身就能证明路径的一致性。

图5 多项式计算收敛耗时

表2 多项式计算收敛耗时表