确保业务意图在网络中的正确实施——网络验证

 引 言

随着网络变得复杂和庞大，网络管理也变得更加困难，网络升级或改造过程中的细小失误可能会对网络的正常运行造成严重影响。根据Veriflow公司于2016年对315名IT专业人员进行的调查得出的结果，59%的受访者表示网络复杂性的增加导致了更频繁的中断，74%的人表示网络变化每年或多次对企业产生重大影响[1]。2019年7月3日，Cloudflare公司在新的Web应用层防火墙中部署了一个配置错误的规则，导致了全球大面积宕机[2]。配置错误、硬软件实现错误、网络攻击或协议交互的意外错误都会影响网络的可用性和安全性。那么，关键问题在于我们如何才能确保业务的意图在复杂的网络环境中正确的实施运行?

[[332104]]

过去几年，已经出现了一个新的研究领域，即网络验证，旨在严格确保网络按期望的业务意图运行。网络验证的技术灵感来源于形式化方法，一种广义上基于数学方法，通过对复杂系统建立严格的数学模型，验证系统的性能与行为正确性的方法，主要有模型检测、定理证明、符号执行及SMT/SAT(可满足性理论)求解器四种技术[3]。形式化验证已经在硬软件领域得到的成功的应用。例如，NASA(美国航空航天局)成功使用形式化验证技术在火星探测器飞行软件中发现了并发错误[4]。如果我们可以验证硬软件，为什么不验证网络?最近，网络验证在验证和程序语言社区变得逐渐流行起来，学术界和产业界都开展了网络验证的相关研究。在学术界，主要有斯坦福大学、伊利诺伊大学香槟分校、加州大学洛杉矶分校、卡内基梅隆大学以及清华大学等高校。在工业界，主要有微软研究院和AT&T实验室。目前，该领域已经出现了一些初创公司，如Forward Networks、Veriflow、Intentionet。

本文将首先介绍一些相关背景知识，然后分别介绍网络验证中的控制平面验证和数据平面验证两个研究方向，最后进行总结。

背景知识

网络从路由转发的角度可以被分为三层，即策略、控制平面和数据平面，如图1所示[3]。策略是控制平面和数据平面的参考，体现了网络管理人员的意图，如主机A是否允许和主机B通信。控制平面是用于实现策略的，在传统网络中是指分散于各处的网络设备中的配置文件，在SDN(软件定义网络)中是指各种应用。数据平面是网络中根据控制平面生成的转发信息与拓扑结构，其中转发信息在传统网络中是指转发表，在SDN中是指流表。根据控制平面和数据平面两个层次，网络验证有控制平面验证和数据平面验证两个研究方向，其通过分析对应平面信息，然后验证网络策略的不变式完成检查。其中，不变式是一种属性，在网络中特指路由转发行为的正确属性，如无转发循环不变式，断言了数据包在网络中不会出现转发循环。在对一个特定网络如企业网、校园网进行验证时，除了需要考虑该网络的控制平面或数据平面信息，还需要考虑网络环境的因素，如网络外部发送给网络的路由通告。

图1 网络层次划分情况

控制平面验证

控制平面验证通过输入控制平面信息，验证网络策略的不变式以确保控制平面与策略要求的一致。其优点是可以在配置部署到网络之前完成验证，能够方便的定位到错误的配置位置;缺点是需要分析配置文件与网络行为之间的复杂关系，以及考虑形式各异的配置语言。

目前，传统网络目前仍占据主导地位，其控制平面的配置文件分散在各处的网络设备中，验证面临状态爆炸问题。相关研究方面，Feamster等人于2005年提出了rcc工具[5]，是第一个能在真实网络中检测BGP(边界网关协议)故障的静态分析工具，但其检查的范围仅限于BGP协议。rcc采用的是静态分析的方法，其将控制平面信息标准化成SQL数据，然后验证根据策略转换成的SQL上的约束条件判断BGP配置的正确性。为了提高验证范围，不再局限于特定的协议，Fogel等人提出了Batfish工具[6]。

Batfish并没有选择在控制平面上进行建模，而是选择通过控制平面生成数据平面，然后调用数据平面验证工具进行验证。这种方式结合了控制平面验证和数据平面验证的优点，既能提前检测错误也不需考虑协议的复杂交互。但是，Batfish面临着一个难题，即如何根据配置和环境生成一个可靠的数据平面，其通过使用DataLog(一种数据查询语言)的一种变式LogiQL建立了一个陈述式模型以解决此挑战。由于Batfish需要对整个数据平面进行模拟，速度很慢。Gemberjacobson等人发现，生成详细的数据平面是不必要的，提出了ARC，可以直接在控制平面进行快速分析[7]。

ARC使用加权有向图对控制平面建模，使用图算法进行分析完成验证。对于特定的属性不变式，可以比Batfish快出了三个数量级。但是，ARC只对一些特定的协议组合进行了分析，如OSPF，RIP，eBGP。为提高验证的协议范围，Fayaz等人提出了ERA工具[8]。

ERA使用二元决策图(BDD)对控制平面建模，通过探索BDD模型完成验证。相比ARC可以验证更多协议，相比Batfish验证速度快了2.5到17倍，且可以扩展到大型网络中。Beckett等人指出，控制平面验证的主要难点在于构建一个具有高度的网络设计覆盖范围与高度数据平面覆盖范围的验证工具，同时保持足够高的可扩展性[9]。

其中，网络设计覆盖范围是指工具能够支持网络的拓扑类型、路由协议和其他一些特点的范围;数据平面覆盖范围是指工具能够支持的数据平面的范围。为解决该挑战，Beckett等人提出了Minesweeper工具。Minesweeper使用SMT公式对控制平面建模，将公式放入SMT Solver中完成验证。相比之前的控制平面验证工具，可以验证更多的协议，覆盖更大的数据平面，且可以扩展到大型网络。值得说明的是，ARC、ERA和Minesweeper都使用了Batfish的配置解析器将不同厂商的配置转换为无关厂商的统一格式。表1从网络设计覆盖范围、扩展性、主要基于的技术3个方面对上述工具进行了总结。其中，扩展性是指工具扩展到大型网络的能力。

表1 传统网络控制平面验证工具总结

在SDN中，网络行为是集中由控制器决定的，这使得验证网络变得简单。目前SDN控制平面验证主要集中在两方面，一是对SDN程序的验证，二是开发验证控制器[3]。SDN使用应用程序制定策略管理网络设备，如路由或访问控制。如普通的软件程序一样，SDN程序会出现设计或实现错误，如果盲目的部署在网络中，很容易引起故障的发生。验证控制器用于检查控制器是否按照策略正确安装规则，因为其特定的编程语言支持不变式验证，可以在编译时与规则安装到交换机之前进行验证，防止错误的规则下发。目前，SDN程序验证方向有Verificare、VeriCon等工具，验证控制器方向有NetCore、NDLog、NetKAT等工具。

数据平面验证

数据平面验证通过输入数据平面信息，验证网络策略的不变式以确保数据平面与策略要求的一致。其优点是数据平面直接体现了配置的影响，分析起来更加简单。但是，其不能在配置部署前完成验证，而且需要重复采集数据以应对网络波动带来的数据平面变化。此外，数据平面验证不能提供错误配置的出处，需要人员自行关联发现，由于网络行为与配置文件之间的复杂关系，这是十分困难的。数据平面验证方面，传统网络与SDN网络的唯一区别在于数据采集过程，传统网络可以通过SNMP(简单网络管理协议)，终端或者控制会话来收集转发表，而SDN网络可以监视控制器获得。

由于控制平面验证不能发现网络设备将控制平面转换成数据平面的实现错误，以及存在分析复杂的问题，Mai等人于2011年提出了第一个在真实网络中发现错误的数据平面分析工具Anteater[10]。Anteater首先根据数据平面信息将网络建模成为一个图，然后将不变式建模为图上的函数，最后将函数转换为SAT公式放入SAT Solver进行求解。Anteater通过实验证明，分析数据平面是一种可行方法，相比于控制平面验证速度不一定更快，但实现方法上相比更容易。

Kazemian等人之后提出了一种数据平面验证框架HSA [11]。HSA框架是基于几何模型的，其将数据包建模成几何空间中的点，用头空间(Header Space)即最大长度为L的{0,1}字符串表示，网络设备建模成该几何空间上的转移函数，通过分析特定数据包头部在几何空间的变化，进行不变式的验证。相比于其他基于形式化验证方法的工具，HSA可以提供所有反例，使分析错误变得高效。Veriflow和NetPlumber使用等价类与增量技术分别改进了Anteater和HSA，有足够的速度和扩展性。

Lopes等人认为，Veriflow和NetPlumber是定制化的代码，难以扩展到新的数据包格式和协议。而网络验证若要发展成为一个网络CAD行业，必须要发展成一个更标准化、更加可扩展的技术。为解决该挑战，Lopes等人基于Datalog技术，提出了NOD工具[12,13]。NOD使用Datalog对策略和协议行为编码，能够进行通用的扩展，最后使用基于SMT Solver技术的Z3 Datalog框架进行验证。实验表明，NOD的Datalog模型计算可达数据集合比模型检测和SMT计算单个可达数据都快，相比于基于HSA的Hassel工具，虽然速度相比较慢，但更易于通用化。为专注于验证访问控制策略的正确实施，Jayaraman等人提出了SecGuru工具，是NOD的早期版本, 已经被部署在Azure中以检查数以百计的路由器和防火墙的正确性[14]。

SecGuru使用位向量对数据平面和策略进行编码，然后将这种位向量逻辑放入Z3 SMT Solver完成验证。表2从表达性、扩展性、主要基于的技术3个方面对上述工具进行了总结，其中，表达性是指分析网络功能的能力，如路由、NAT(网络地址转换)、IP分片等，扩展性是指工具扩展到大型网络的能力。

表2 数据平面验证工具总结

总 结

网络验证的目的是保证网络按照高级策略意图忠实的运行，即网络真实行为与策略一致。本文主要对网络验证中的控制平面验证和数据平面验证两个方向中的现有研究进行了简单概述。整体上来看，工具大多是基于形式化方法实现的，如基于SMT/SAT求解器的Minesweeper、Batfish、Anteater、NOD、SecGuru;基于符号执行的HSA。其他工具如rcc、ARC、ERA通过不同的建模方法实现了验证。上述工具的特点是基于模型的形式化验证，本质上是一种状态机验证技术。其大致框架如图2所示，首先将平面信息进行建模，然后使用与建模方法对应的算法或工具，验证对应模型下的策略不变式，以检测出不符合策略的错误，保证网络的真实行为与该策略一致。

图2 控制平面验证与数据平面验证大致框架

除了控制平面验证与数据平面验证，网络验证还有很多其他方向。例如，网络测试通过生成测试数据包以确保网络设备忠实的按照控制平面建立了转发信息，而且忠实的按照转发信息完成转发;网络规范的自动综合旨在开发一种综合工具从高级的策略中自动生成正确的配置;网络调试旨在网络领域中找到逐步调试、监视、断点、挂起或恢复等功能的等效实现方法。未来，网络验证仍需要解决一些面临的问题，如有状态网络(如包含有状态防火墙等中间件的网络)下的验证、复杂路由场景下的控制平面验证以及定量属性(延迟、带宽)不变式的验证等。

参考文献

[1] Veriflow. Network Complexity, Change, and Human Factors are Failing the Business. https://www.veriflow.net/survey/.

[2] John Graham-Cumming. Cloudflare outage caused by bad software deploy [EB/OL]. https://blog.cloudflare.com/cloudflare-outage/,2019–07–02.

[3] Li Y, Yin X, Wang Z, et al. A Survey on Network Verification and Testing With Formal Methods: Approaches and Challenges [J]. IEEE Communications Surveys and Tutorials, 2019, 21(1): 940-969.

[4] Brat G, Drusinsky D, Giannakopoulou D, et al. Experimental evaluation of verification and validation tools on martian rover software[J]. Formal Methods in System Design, 2004, 25(2-3): 167-198.

[5] Feamster N, Balakrishnan H. Detecting BGP configuration faults with static analysis[C]. networked systems design and implementation, 2005: 43-56.

[6] Fogel A, Fung S, Pedrosa L, et al. A general approach to network configuration analysis[C]. networked systems design and implementation, 2015: 469-483.

[7] Gemberjacobson A, Viswanathan R, Akella A, et al. Fast Control Plane Analysis Using an Abstract Representation[C]. acm special interest group on data communication, 2016: 300-313.

[8] Fayaz S K, Sharma T, Fogel A, et al. Efficient network reachability analysis using a succinct control plane representation[C]. operating systems design and implementation, 2016: 217-232.

[9] Beckett R, Gupta A, Mahajan R, et al. A General Approach to Network Configuration Verification[C]. acm special interest group on data communication, 2017: 155-168.

[10] Mai H, Khurshid A, Agarwal R, et al. Debugging the data plane with anteater[C]. acm special interest group on data communication, 2011, 41(4): 290-301.

[11] Kazemian P, Varghese G, Mckeown N, et al. Header space analysis: static checking for networks[C]. networked systems design and implementation, 2012: 9-9

[12] Lopes N P, Bjorner N, Godefroid P, et al. Checking beliefs in dynamic networks[C]. networked systems design and implementation, 2015: 499-512.

[13] Lopes N P, Bjørner N, Godefroid P, et al. Network verification in the light of program verification[J]. MSR, Rep, 2013.

[14] Jayaraman K, Bjørner N, Outhred G, et al. Automated analysis and debugging of network connectivity policies[J]. Microsoft Research, 2014: 1-11.