网络验证中数据平面验证的方法与挑战

前 言

如今网络变得越来越复杂，在运营商对网络进行配置时，一些不经意间违规配置可能会酿成大错，因此需要最大程度上保证网络的配置正确，但人工检查又太过繁琐，所以一种新的研究领域——网络验证进入了研究者的视野。网络验证指使用数学中的形式化方法对网络配置进行检查。网络验证可以分为数据平面验证和控制平面验证，如图1[1]所示，数据平面是指网络设备中指定数据包的转发行为的功能，比如转发表、流表;控制平面是指结合网络拓扑、环境信息等生成数据平面的功能，如网络设备的配置文件。本文主要对目前数据平面验证工具进行介绍，主要参考了Li[1]等在2019年发表的综述。 图1 网络层次结构和常见错误

ConfigChecker

早在2009年由Al-Shaer[2]首先提出ConfigChecker数据平面验证工具，ConfigChecker是基于模型检查的，是形式化验证中十分常见且重要的验证方法。ConfigChecker使用状态机建模网络，状态机的状态是由数据包的头部信息和位置确定的，将由转发表等数据平面信息建模为状态转移关系，不同设备的行为都可以用一组规则来表示，每一个规则都有一个条件和一个动作，条件可以用状态中的参数来表示一个布尔公式，如果设备上的报文满足该公式，则触发相应动作，此过程使用了BDD(二元决策图)对访问控制策略编码，然后使用CTL(计算树逻辑)表示网络验证属性，如可达性检查、环路检测以及发现安全性问题，最后检查所有状态是否满足各属性。虽然模型检查存在状态爆炸的问题，以模型检查为基础的验证工具很难应用在大型网络上，但是ConfigChecker的提出证明了使用形式化方法验证网络的可行性，通过对该篇文章的阅读我也对模型检测有了更好的认识。 Mai[3]等在2011年提出了首次在真实网络中进行网络验证的数据平面验证工具Anteater，核心思想是将网络验证问题转化为SAT问题，然后通过SAT求解器进行求解。Anteater验证的主要流程较简单：通过分析网络中的转发表获得数据平面信息，将网络建模成有向图，图中的节点是网络中各设备可能到达的目的地，图中的边是允许在两节点通过的数据包需要满足的条件(通过策略函数来表示，也就是多个布尔公式);再将所需验证的属性使用一些声明式语言(如Ruby)来表示，并转换成SAT公式(该过程是需要通过各边上策略函数的组合来得到一个SAT公式)，最后通过SAT求解器计算验证属性所转化的SAT公式是否可满足(参考了可达性验证算法思想，计算节点之间各路径允许通过的数据包集合)。我认为该文章中对系统建模的方法是比较容易理解的，基于有向图，节点为地点，边为条件，在节点之间流动的数据包用一种称为符号包(symbolic packet)的变量表示(其中包含了数据包的IP地址、MAC地址、端口号等信息)。本文的网络属性验证方面基本都是围绕着可达性验证算法展开的，可达性算法思想是若判定s、t两点的可达性就是判定是否存在symbolic packet满足从s到t的路径上所有边上的约束条件，将这些条件合并成一个SAT公式，然后求解。转发循环验证是为每一个顶点v加一个虚拟节点v’，再分别验证v-v’的可达性。丢包验证是网络中添加一个汇聚节点d，假设它可以到达任意目的地，然后分别测试个节点v的v-d可达性。一致性验证是分别验证这两个节点与其它节点的可达性、丢包情况，然后求异或(即看结果是否一样)。虽然Anteater不能进行实时验证，扩展性、时间效率都不够好，但是我认为这种将可达性验证算法用于对数据包的计算上是十分有意义的，之后的工具中也有应用该思想的。

HSA

Kazemian[4]等在2012年提出了HSA(Header Space Analysis 头空间分析技术)，基于符号执行技术，与之前的Anteater完全不同，HSA更加抽象，不易理解。HSA的系统建模过程较复杂：有七个需要注意的部分。(1)文章提出了头空间(Header Space)H的概念，将报头看作是一组由0、1组成的序列，在{0,1}L(L表示序列长度)头空间中，一个报头是一个点，一个流是一片区域。(2)将各个网络设备的各输入端口所可能输入的所有报头组成为网络空间N(即头空间H×{所有设备入端口})。(3)将各网络设备根据其功能定义出不同网络转移函数，函数有两个参数，分别是报头header和端口port，函数定义了头空间中不同区域通过某一网络设备后的转换情况。(4)定义拓扑转移函数，函数参数与网络转移函数的参数相同(header，port)，该函数用于描述网络中各链路，一般一组(header，port)经历过网络传递函数转换后，其链路状况也会改变，需要拓扑转移函数来计算新的拓扑状况。(5)定义了Slice三元组(网络空间N的一个子集，读写操作，对于该Slice的所有转移函数)，我认为Slice的主要功能就是描述数据包集合，与Anteater中符号包(symbolic packet)功能类似。(6)定义了头空间的代数，因为每个数据包(或流)在头空间是一组0、1组合，定义了交、并、补、差、T(转移函数能够输出的(header，port)集合)和T-1等操作，用于对头空间中的子空间进行操作，得到最后的空间(即剩余的数据包)。(7)网络设备建模，将不同网络设备根据其功能，将多个传递函数组合，得到一个总的函数，比如路由器处理数据包的过程为重写源、目的地址(T1)、减少TTL(T2)、更新校验和(T3)、转发到出端口(T4)，则该路由器可通过符合以上四个转移函数得到Trouter=T1(T2(T3(T4(header，port))))。 网络验证是将网络属性建模成头空间的相关断言，验证过程是先根据断言构造特定的符号数据包几何，输入到网络中的转移函数进行分析，然后通过分析转移函数对符号数据包集合的处理过程确定断言的满足性以完成属性验证。由于使用了基于函数的分析方法，能够找到违反验证属性的全部反例。可达性分析如图2[4]所示，是考虑离开源地址的所有报头空间，在到达目的地址的过程中，跟踪这个空间(中间会经历很多传递函数，空间会减少)，到达目的地址时，若头空间还有剩余，则可达，再根据之前提到的T-1(转移函数的逆)函数找到源地址发送的可以到达目的地址的报头集合。循环检测是通过给每个端口输入一个全是x(通配符)的测试报头，追踪数据包，如果数据包返回源端口，则说明有循环。 图2 计算从a到b的可达性示意图 我认为HAS相较于Anteater更难理解一些，但是提出的头空间是十分巧妙的，以数据包为点，以网络设备为点与点之间的线(与Anteater刚好相反：以设备地址为点，以数据包为线)，这种抽象在一定程度上能让复杂的网络空间变得更简单。 于2013年被提出的VeriFlow[5]是首个的对数据平面进行实时验证的工具。VeriFlow在某种程度上是在Anteater的基础上增加了增量计算，实现实时验证，因为VeriFlow也是基于可达性算法，对数据包进行计算。VeriFlow的大致思想是：实时监控SDN网络中所有的网络更新时事件，VeriFlow处于控制器与网络设备的夹层中;然后VeriFlow旨在受网络更新影响的小范围内进行网络验证，验证过程使用自定义算法。VeriFlow实现只在小范围内进行验证的方法是：通过分析SDN控制器下发的新规则，基于新规则和与新规则有重叠部分的老规则，将网络划分为一组等价类，每次网络更新只会影响一小部分等价类，然后为每个被修改的等价类构建各自的转发图，转发图用于表示网络的转发行为，最后通过遍历转发图来检查网络属性。由于VeriFlow只进行小范围验证，所以验证速度很快，从而基于等价类实现了实时验证的目的。其中等价类的划分是将网络中具有相同转发行为的数据包集合划为一个等价类，为了加速等价类的划分和找到受更新影响的等价类，文中使用多维前缀树(trie)这种适用于包分类算法的数据结构。trie中的每一层对应于转发规则中的特定位，trie的每个节点存在1，0，x三个分支，一个trie可以看作是几个trie或几个维度的组合，每个维度对应数据包头中的一个字段，从trie的根到叶子节点的路径表示与该规则匹配的包集，每个叶子节点存储了匹配数据包集的规则和它们所处的位置，由此完成了等价类的划分，如图3[5]所示。等价类划分后是为每个等价类都生成一个转发图，转发图是用于表示等价类中的数据包是如何被转发的，图中节点表示特定网络设备的等价类，有向边表示对于该(等价类，设备)对的转发规则，若图中两节点X，Y相连表示根据节点X所在设备的转发表，该等价类中的数据包可以发送到Y所在的设备中。构建转发图的过程为了找到与等价类匹配的包和规则，需要再次遍历trie。网络属性的检查是建立在转发图上的，将检查的属性设定为一个验证函数，将转发图作为输入，执行函数，得到结果。VeriFlow开发了一个可编程接口，用于编写和插入新的属性检查函数。在VeriFlow中可达性验证、循环验证、一致性验证等都是通过编写特定函数完成的。 图3 VeriFlow计算等价类的过程 数据平面实时验证工具NetPlumber[6]同样出现于2013年，主要是应用在SDN网络中。SDN网络中主要是通过控制器向各网络设备发送各种规则，而NetPlumber就是处于控制器和设备之间，对这些规则进行检查。它首先是继承了HSA的思想，借助了头空间的思想(header space)，将一个报文看作头空间的一个点，将一组报文看作一片区域，将网络设备定义为不同转移函数，完成数据包在头空间的流动。该文中更清楚地介绍了转移函数：每个转移函数由一些列规则构成，一个规则包括一组输入端口、一个通配符表达式(用于过滤数据包)和一组对符合表达式的数据包的操作，操作包括转发、删除、重写、封装等。NetPlumber对于HSA的改进主要体现在实现了实时增量检查和提出了一种新的属性检查方式。所以HSA中可以检查的属性NetPlumber都可以完成。

NetPlumber

NetPlumber的核心是首先通过各转发表构建了一种依赖图，叫做plumbing graph，如图4[6]所示，然后再通过分析SDN控制器下发的规则对该图进行调整，其中图的节点对应规则，图的有向边称为pipes，对应了规则之间的依赖关系，代表了匹配数据包的可能路径。定义每个pipe边包含一个pipe fliter，用于过滤数据包。文中对规则(节点的定义也是非常巧妙的，定义为一个二元组，match字段用于标识出可以受该规则处理的数据包，action字段表示对这些数据包的操作。在plumbing graph中若两规则节点相连，一是可能这两个规则所属的网络设备之间存在物理链路，二是可能被第一个规则节点处理后的数据包能够被第二个规则节点识别并再进行处理。对于规则的增加、删除和链路的增加、删除文中都介绍了如何对plumbing graph进行更新，该内容也是NetPlumber能够进行实时验证的基础，每一次网络发生变化时，不会重新建立plumbing graph，而只是小范围的更新，计算速度较快，以实现实时更新。文中提到的还有助于实时网络更新的一个思想是分布式NetPlumber，将plumbing graph分成多个集群，一个集群内的节点交互更多，集群间的共用节点复制出一个划入另一个集群，然后各集群之间可以同时计算，速度更快。 图4 由4个交换机组成的简单网络的plumbing graph NetPlumber中的所有属性验证也是基于对plumbing graph进行检测的，通过向图中指定位置增加probe nodes收集数据包，进行验证，定义每个probe node、具有一个过滤表达式和一个测试表达式，过滤表达式用于过滤数据包，测试表达式用于验证属性。比如计算端口s到端口d的可达性，向s注入一个全是x通配符的一组数据包，使其沿着所有的有向边传播，在每一个规则节点上，flow由match过滤，由action转换后得到一个新的flow，继续传到下一个节点，如果在d处存在来自s的数据包，则说明s和d可达。我认为NetPlumber的整体构思可以分为两部分，一是将整个网络都表示在头空间中，二是由头空间得到plumbing graph，通过对plumbing graph中节点的验证以完成属性验证。借助plumbing graph这个巧妙的设计首先实现了实时验证数据平面，还可以检测一切由网络状态更新相关的网络属性验证，同时可以对graph进行聚类的划分实现并行计算。

小 结

目前已经完成了几个比较常见的数据平面验证工具的介绍，包括ConfigChecker、Anteater、HSA、VeriFlow、NetPlumber。数据平面验证基本都是基于Xie[7]提出的可达性算法，通过对一条路径中的数据包进行计算，结果不为空则表明可达。不同工具也有各自的特点和有价值的思想，下面进行简要的总结：(1)ConfigChecker基于符号模型检测技术，根据数据包头信息和所处位置建模为状态，使用BDD表达的布尔公式表示状态转移关系，使用CTL表达验证属性，通过遍历所有的状态来验证属性。(2)Anteater基于SAT问题，根据数据平面信息将网络构建成一个有向图，节点表示位置，有向边表示数据包通过的条件(策略)，将网络用布尔公式编码。用一组表示数据包头字段的变量的符号包示数据包，再将验证属性表示成一个个SAT实例，通过SAT求解器进行验证。(3)HSA基于符号执行技术，提出头空间的概念，一个数据包为头空间中的一个点，对头空间中区域的过滤就是对数据包的过滤。将不同设备的功能定义为转移函数，用于对头空间的区域进行操作。属性验证过程是将不同属性写成头空间内的不同断言，通过判定断言的真假来验证属性。(4)VeriFlow基于等价类思想实现了实时验证，它通过监控SDN网络中控制器与网络设备间的通信，将具有相同转发行为的数据包划为一个等价类，再为每一个等价类建立一个转发图，节点代表网络设备，边代表该设备的转发规则。属性检查是在各个等价类的转发图上基于图算法进行验证。(5)NetPlumber基于增量计算的思想，在完成HSA中将数据包映射到头空间后，把网络建成了一种叫作plumbing graph的依赖图，节点表示规则，边表示规则间的依赖关系，通过在plumbing graph中增加探测节点，然后根据探测节点(带有过滤表达式和测试表达式)完成相应属性验证。 数据平面能够完成网络当前这一时刻的网络验证，并且只能在网络配置完成后真正运行网络出现错误时才能检查出来，不能对错误进行提前检查，所以今后网络验证的发展方向还是需要集中在控制平面上，但本文数据平面验证工具也很都起着重要的作用，因为有很大一部分控制平面验证工具是先通过一些方法根据网络设备控制平面信息生成数据平面后，再对生成的数据平面进行验证，这个验证过程也是需要数据平面验证工具的。综上可以看出网络验证领域的数据平面验证出现了很多巧妙的验证思想和工具，为网络验证更好的发展奠定了基础。

参考文献

[1]Li Y H, Yin X,Wang Z L, et al. A Survey on Network Verification and Testing With FormalMethods: Approaches and Challenges.IEEE Communications Surveys & Tutorials,2019, 21(1): 940-969. [2]Al-Shaer E,Marrero W, El-Atawy A, et al. Network configuration in a box: towardsend-to-end verification of network reachability and security. In: 2009 17thIEEE International Conference on Network Protocols, 2009: 123-132. [3]Mai H, KhurshidA, Agarwal R, et al. Debugging the data plane with anteater. In: Proceedings ofthe ACM SIGCOMM 2011 conference, 2011: 290-301. [4]Kazemian P,Varghese G, Mckeown N. Header space analysis: Static checking for networks. In:Proceedings of the 9th USENIX conference on Networked Systems Design andImplementation, 2012: 9. [5]Khurshid A, ZouX, Zhou W, et al. VeriFlow: Verifying Network-Wide Invariants in Real Time. In:10th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI}13), 2013: 15-27. [6]Kazemian P,Chang M, Zeng H, et al. Real time network policy checking using header spaceanalysis. In: Proceedings of the 10th USENIX conference on Networked SystemsDesign and Implementation, 2013: 99–112. [7]Xie G G, JibinZ, Maltz D A, et al. On static reachability analysis of IP networks. In:Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer andCommunications Societies., 2005: 2170-2183 vol. 3.