POF表项指令和动作的合法性检测

封 栋，陈 晓

(1.中国科学院声学研究所国家网络新媒体工程技术研究中心，北京 100190; 2.中国科学院大学，北京 100049)

0 引 言

软件定义网络(Software-defined Networking, SDN)中采用控制平面和数据平面相分离的结构，具有容易管理、升级的特点[1]。在SDN中，控制器通过南向接口协议向交换机下发流表，交换机根据数据包对表项进行匹配，通过执行表项内的动作和指令，完成数据包的处理和转发。

OpenFlow是SDN的一个代表性南向接口协议[2-3]，但由于它的匹配域是协议相关的，导致OpenFlow存在拓展性差等限制。为了提高底层设备的可编程性，学者们做了许多研究。这其中比较有代表性的工作是可编程协议无关报文处理(Programming Protocol-independent Packet Processors, P4)[4]和协议无感知转发(Protocol Oblivious Forwarding, POF)[5]。P4设计了自己的处理语言和相应的转发模型[6-7]，从而提高了数据平面编程能力。而POF通过使用{类型，偏移，长度}元组的描述方式实现了协议无关。POF更加类似于OpenFlow的一种拓展，其转发模型与OpenFlow基本一致。文献[8]对P4和POF进行了详细的对比与介绍。POF定义了指令集，可对数据包等数据进行设置、比较等运算，实现了对数据平面的编程。由于POF具有灵活性，许多网络研究都是基于POF进行的[9-10]。

POF指令集包括指令(Instruction)和动作(Action)这2种类型。指令和动作在语义上有细微的区分，一个指令可以包含多个动作。为了方便表述，在下文中使用“指令块”一词指代POF表项中所包含的指令和动作所构成的程序。

早期的POF每个表项中执行的指令块很简单，指令只有顺序执行，没有复杂的执行控制。POF的发展过程中逐渐引入了新的指令和功能。特别是比较、跳转等指令的增加，改变了原本动作顺序执行模式，使得跳转、循环执行成为可能，软件交换机可编程能力得到了很大提高。

新的指令和功能的加入在提高底层设备可编程性的同时，也加大了软件漏洞产生的可能性。一旦控制器下发的一个流表中的指令块中出现了错误，有可能会直接导致整台交换机的故障。因此实现一种实时安全检测机制是很有必要的。本文要解决的问题就是希望通过预处理的方法，提前发现使得软交换机崩溃的情形，避免软交换机产生死机等问题。

造成软件漏洞的原因有很多，指令块作为一种专用领域的程序，常见且比较重要的漏洞可以总结为如下3类：

1)单条指令的错误。包括指令的类型和参数。使用了非法的指令类型，或者指令中出现了访问越界，都会导致交换机出现不可预期错误。

2)存在不可达指令。虽然不可达指令的存在不会直接造成交换机崩溃，但其往往是由于错误使用了跳转指令造成的，提示程序存在逻辑错误。

3)指令块中存在死循环。由于数据平面交换机的解释—执行模式，一个指令块的死循环可能会导致整个交换机被卡死。这一点与通常程序有很大不同。因为通常程序一般是作为一个进程运行的，由操作系统提供资源隔离，一个程序并不会引起整个系统的崩溃。因此，对于指令块来说，避免死循环问题十分重要。

需要指出的是，防止指令块出现死循环的最有效的处理方案是直接禁止程序中出现循环结构。但是考虑到循环在诸如数据包的组播等应用中会为控制平面编程提供很大的便利性，因此一种更合理的方案是允许简单的循环体出现，但必须通过严格的校验。

另外，由于指令块是在交换机运行时由控制平面动态下发，因此需要对其进行实时检测，这一点与通常检测程序有很大不同。

本文针对上述几种漏洞的检查给出相应的算法和实现方案。通过基于控制流图的检测可以发现是否有单条指令的错误、是否存在不可达指令以及是否存在循环。而对于存在的循环块，提出一种基于强连通分量的检测算法用以判断循环的合法性。检测方案的整体时间复杂度为线性，可以保证实时检测。

1 相关工作

目前尚未有针对POF协议的应用检测的相关研究，但是有一些针对其他协议和编程语言的SDN应用检测的研究可供参考。NICE是一款比较知名的对OpenFlow执行模型检查的工具，用于在SDN网络中的控制平面中查找可能存在的问题[11]。p4pktgen是针对P4程序的一款检测工具，通过使用自动生成测试用例对应用进行测试，以确保程序执行结果与预期相符。p4pktgen执行速度较慢，但可以发现程序中可能存在的逻辑错误[12]。Vera是P4的另一款调试检测工具，通过符号执行以发现程序中的常见问题，包括解析错误、访问越界、指令错误等[13]。p4pktgen和Vera这2种验证方式是相辅相成的。

由于P4和POF均为协议无关的数据平面编程技术，因此针对P4的检测研究具有重要的参考意义。本文的工作与Vera类似，旨在通过静态测试发现程序中的漏洞以保证交换机运行时的稳定性。

然而POF与P4存在2个很大的不同点。1)P4是编译型的程序，因此P4程序的校验过程可以离线进行，有足够时间对程序进行充分而细致的检测；而POF是解释型的，控制器下发指令块后会直接部署到交换机中，必须实现快速的实时性检测，因此类似于p4pktgen的检测方式在POF中是不适用的。2)P4语言本身不支持循环，因此无需在单条表项中对循环进行检验。而在POF中是允许循环出现的，针对循环合法性校验是本文要研究解决的重点问题之一。

若不局限于SDN领域，目前已经存在很多优秀的静态代码检查工具。比如Cppcheck是一种用于C和C++编程语言的静态代码分析工具[14]，主要检查的内容包括变量检查、边界检查、资源泄漏、风格检查等；Clang的静态分析器也是知名的源代码分析工具，用于发现C、C++和Objective-C程序中的错误。此外，针对Java、Python等其他主流语言也有很多对应的静态检查工具。

虽然现有的静态分析工具比较成熟，但却无法直接应用于POF的指令块的检测。原因主要有如下2点：

1)现有的程序静态检测研究和应用主要是针对高级语言进行的，主要检测内容包括代码风格、类型检查等，而POF指令块的程序更加类似于汇编，无法直接使用现有检测工具，并且检测重点也有所不同。

2)绝大多数静态检测工具不会对程序的循环合法性进行检测，而死循环检测在指令块中至关重要。

尽管无法直接使用现有的静态分析工具，但是其研究方法与实现方案可提供参考。张林等人[15]对现有的静态分析进行了分析与讨论；周宽久等人[16]提到了将程序转换为XML中间模型，从而可以实现检测与语言分离；而静态分析和程序编译中经常用到的分析控制流图等方法，对于指令块这样的程序也同样适用。

检测程序死循环的最直接有效的方法是动态检测，即在程序运行时监控代码块的运行时间或者运行次数，达到指定限制后即认为程序中存在死循环。但动态检测主要存在着2个问题。1)由于需要对程序运行状态进行监控，这将直接增加运行时负担，导致交换机性能降低；2)由于流表下发后只有对应的数据包到达时才会触发指令块执行，这会导致漏洞发现不及时。因此静态检测潜在的死循环是一种更好的选择。

然而，程序的死循环问题本质上等价于停机问题，因而通用的静态检测方法是不存在的。这也正是绝大多数静态检测工具都不做死循环检测的原因。尽管如此，针对特定模式的死循环检测还是可以实现的，目前也有了许多研究工作。文献[17]介绍了对于实际中的2种常见死循环条件的严格数学证明；文献[18]介绍了通过分析归纳变量的循环依赖从而生成程序测试用例的方法；文献[19]提到了利用循环变量分析程序代码的思想，但只是针对具体代码和循环模式进行了分析，并没有给出可用的算法实现。

2 检测方案设计与分析

指令块由控制平面下发，在数据平面执行。因此检测工作既可以在控制平面进行，也可以在数据平面进行。在控制平面进行的检测好处是无需下发流表即可提示出相应的错误。在数据平面进行检测则需要先将收到的南向协议数据包进行解析，才能返回错误信息。

但是在数据平面进行检测有如下3个好处：

1)可以直接使用数据平面已有的南向协议解析接口方便地提取出指令块。

2)虽然需要下达流表后才能返回错误信息，但是可以使用南向接口协议中定义的错误反馈接口，架构上更加清晰。

3)考虑到交换机的设计中可能会加载本地的指令块程序，检测程序统一放在数据平面更为合理。

基于以上考虑，最终决定在数据平面对检测程序进行实现。

指令块的主要检测内容包括指令参数检查、指令可达性检查以及潜在的死循环检查。具体来说，检测流程为：首先将POF协议的指令块按照语义转化成统一的中间指令，并对指令的类型与参数进行检查；然后构建控制流图，通过对控制流图的分析检查出不可达指令和存在的循环。针对循环块，进一步通过基于强连通分量的算法判断循环是否为合法循环。

系统整体流程如图1所示。

图1 系统整体流程图

3 基于控制流图的检测

3.1 中间表示与参数检测

为了便于分析与处理，同时考虑到支持其他南向接口协议的可能性，首先将指令块按照语义统一转换为中间指令。之前提到过，在POF协议中，指令块的内容被分为指令和动作2种类型，一个指令内可以包含多个动作。这种嵌套设定会为解析与校验带来许多困难，因此采用了将其按照语义转换为统一的中间表示的方法。中间指令表示由操作码、标志位、操作数3部分组成。

转换后的主要操作码类型包括字段操作计算指令、算术逻辑指令、输出指令、跳转指令、表操作指令。标志位字段用于标识操作数是数据包字段、元数据字段或者其他字段。操作数可以分为立即数和使用{类型，偏移，长度}元组描述的匹配数2种类型。

在得到中间表示后首先进行指令级别的检测。检测内容如下：

1)对操作码类型进行检测。判断是否为合法类型。通过预先存储合法指令类型，可以在常数时间内完成对一条指令的操作码校验。

2)对标志位进行检测。判断是否有非法标志。

3)对操作数进行检测。主要进行参数合法性检测。特别地，对于跳转类指令，检测跳转的目的地址是否合法。

3.2 构建控制流图

控制流图(Control Flow Graph, CFG)是指以有向图的形式抽象表示出程序执行中的所有路径[20]，是编译器优化和静态分析的重要工具，在支配分析、程序优化等领域都有使用[21-22]。

控制流图的单位为基本块。一个基本块由一条或几条连续的程序语句组成。本文所以使用了将每一条指令直接视为一个基本块的做法。这样可以免去基本块的判断条件的分析，并且在控制流图分析的过程中数据结构比较简单，同时可以方便地定位到指令的位置。

具体来说，本文所述的指令块的控制流图的生成方式为：遍历所有指令。如果指令为比较跳转类指令，则为其添加2条边：一条边指向下一个指令，另一条边指向目的指令；如果指令为直接跳转指令，添加一条指向目的位置的边；如果指令为结束指令或者表跳转指令，不添加边；其余类型的指令添加指向下一条指令的边。

得到的控制流图为一个有向图，图的入口为第一条指令，图的出口为最后一条指令或者结束指令。

3.3 指令可达性和循环检测

通过对控制流图的分析便可以找到图中存在的不可达指令和存在的循环结构。

图2 不可达指令和循环指令块

在图2左图中的深色节点为一个不可达指令，即无法通过程序的入口访问到。不可达指令块的存在通常是由于直接跳转等指令的错误使用而造成的。出现了不可达指令意味着程序存在着逻辑错误。右图的3个深色节点构成一个循环块。循环块的出现通常是由于比较跳转指令的使用。出现了循环块提示此处可能会有死循环问题，需要进一步检验循环合法性。

对于不可达指令的检测比较简单。只需对控制流图使用一次深度优先搜索(Depth-First Search, DFS)或者广度优先搜索(Breadth-First Search, BFS)进行遍历，如果存在无法到达的节点则意味着存在不可达指令。

对于有向连通图中的循环检测有多种方法。一种常用的方法是通过深度优先搜索树的边的类型进行判断，如果存在回边(Back Edge),则可判断图中存在循环。

通过对DFS过程中的节点进行染色标记，可以在一次DFS中同时找到不可达指令和存在的循环指令块。主要思想为：所有节点初始为白色，在DFS的过程中，第一次到达节点将其标记为灰色；搜索到路径的终点后在回溯的过程中将节点置为黑色。同时在DFS的过程中对边类型进行标记，如果边指向了灰色节点则标记为回边。DFS完成后存在非黑节点则说明有不可达指令。存在回边则说明存在循环体。该算法的时间复杂度为线性。

算法伪代码如图3所示。

4 基于强连通分量的循环判断

在上一章中通过控制流图分析的方法找出了循环块在程序中的位置。本章介绍有界循环判断的方法。

为了满足系统实时检测的需求，同时也因为死循环判断问题的复杂性，本文采用的算法中对循环的模式做了比较严格的限制。

4.1 循环的相关分析

循环变量是指在一个循环中不断变化而最终使得循环结束的变量。以C语言程序为例，while(i<1){…i++…}中的变量i即为循环变量。在指令块程序中，造成循环结构的回边的起始节点对应的指令中的源操作数即为循环变量。

循环终止条件通常是循环变量与一个常量或变量进行比较(比较条件为大于、小于、不等于等)，不满足比较条件后跳出循环。其中，循环变量与常量进行比较，且比较条件为大于或小于的循环是本文分析的重点。这是因为大于或小于的情况可以通过对循环块中各条路径的单调性分析给出循环合法性结论，而不等于的情况十分复杂，没有简单有效的判别方法。而只分析与常量进行比较的循环类型原因是如果同时跟踪2个变量，会导致检测算法复杂度增加，难以保证实时性。

图3 不可达指令和循环指令块检测伪代码

4.2 强连通分量计算

强连通分量(Strongly Connected Component)是图论中的概念。在有向图中，如果所有节点两两之间都存在一条连通路径，则该图为一个强连通图。而强连通分量则是指一张有向图的极大强连通子图。

图4 强连通分量示例

以图4中的有向图为例。图中共有2个强连通分量。其中白色节点构成一个强连通分量，深色节点构成另一个强连通分量。白色节点和深色节点之间不存在双向路径。

在程序中，一个循环对应着控制流图中的一个环。环中所有指令都互相可达，因此根据强连通分量的定义可知，一个循环块内的所有指令都属于控制流图中的同一个强连通分量。

计算有向图的强连通分量的算法比较多[23]，经典算法包括Kosaraju算法[24]、Gabow算法[25]和Tarjan算法[26]。算法的时间复杂度均为O(V+E)。其中V为顶点数，E为边数。本文选择使用Tarjan算法求取控制流图的强连通分量。

通过计算强连通分量，将控制流图划分为多个子图，从而缩减了循环变量跟踪时的搜索范围。

4.3 循环变量跟踪

通过强连通分量计算得到了可能会使循环变量的值发生改变的所有指令。循环体执行一次的过程对应于在循环块的起点节点到终点节点之间的某一条路径。对于while(i<1)形式的循环，理论上测试所有路径来判断循环变量是否总是增加便可以判断循环是否一定可以在某个点终止，反之亦然。

但是如果循环块中存在多个分支，由于分支之间可以任意组合，因此会存在路径爆炸问题。对所有路径进行遍历，将会导致算法复杂度急剧上升。

鉴于路径跟踪的复杂性，本文提出一种简化的基于强连通分量的检测算法。该算法主要基于以下事实(仍以while(i<1)形式的循环为例)：

1)循环体中任意一条可执行路径中的指令都是该循环所属强连通分量的子集。因此，如果强连通分量中所有指令都不存在可以使循环变量值增加的指令，那么该循环必为死循环。

2)分支和循环的产生都是由于跳转类指令造成的。如果一个循环所属强连通分量中只包含一条跳转类指令(即造成循环的那一条指令)，那么该指令块中的所有指令必为顺序执行。如果同时强连通分量中对于循环变量的修改指令只会使得其单调递增，那么该循环必为合法循环。

因此只需要对循环所属的强连通分量的所有指令进行一次遍历，便可以得到关于循环合法性的判断。算法复杂度由路径搜索的最坏情况下的指数复杂度变为了稳定的线性复杂度。这样做的代价是可以使检测的循环类型有所减少，但考虑到表项指令块中通常只会出现简单的循环语句，因此该算法在实际应用中仍可发挥重要作用。

算法伪代码如图5所示。

图5 循环合法性校验伪代码

5 实验与分析

根据以上介绍的方法，在POF软件交换机上实现了合法性检测程序。实验环境为运行在i5 3230M CPU上的Centos7.7系统,内存为8 GB。作为一种检测程序，主要针对其有效性和执行效率进行实验验证。

5.1 有效性测试

为验证检测程序的有效性，手动设计了多种类型的指令块进行测试。设计原则为尽可能多地包含实际指令块中可能出现的程序类型，包括非法指令、不可达指令以及多种类型的循环等。

对测试中使用到的所有指令块的检测结果进行汇总统计，结果如表1所示。其中对于死循环的检测存在一定的误报率，但不会漏报；而其他类型的检测成功率均为100%。

表1 实验结果统计分析

对于非法指令、不可达指令检测和循环识别等基于控制流图的具体测试结果如表2所示。从表2的测试结果中可以看出，常见的指令级别的错误和各种循环位置的检测全部可以正确检测出来。

表2 基于控制流图的检测结果

对于循环合法性的具体检测结果如表3所示。由于循环的类型多样，为方便表述，这里以等效C语言代码对测试的循环类型进行说明。

表3 循环合法性检测的测试结果

从表3的检测结果可以看出，本文中的算法可以对一些形式的循环给出一定合法或者一定非法的判断。但是需要注意的是，本文方案目前并不能支持所有的循环模式，比如测试7～测试9中的循环类型。同时，对于循环块中包含跳转指令的循环类型，比如测试6中的嵌套循环，只能给出“可能合法”的判断。由于这些无法完全判断的循环类型的存在，本文算法针对死循环的检测会存在一定的误报率。

5.2 性能测试

通过测量检测执行所消耗的时间对检测算法性能进行测试。

首先针对本文中所提的检测方案各阶段的检测速度进行测试。为了提高时间测量的精确性，测试的时间为执行10000次校验的结果。测试所使用的指令块使用脚本自动生成。测试程序类型包括3种：1)包含非法指令，指令校验过程中即被检测到；2)包含不可达指令，不包含循环，需要经过控制流图的搜索来检测；3)包含循环，会经过所有的检测流程。对于每种类型的不同长度进行测试。测试结果如图6所示。

图6 检测算法性能测试

从实验结果可以看出每一种情况下的运行时间都基本随着指令长度线性增加，这与本文对检测算法的复杂度分析结果是相吻合的。同时，完成对200行的指令块的一次完整的检测只需要0.2 ms左右，说明该检测方案可以满足对流表进行实时检测的需求。

此外，为了验证真实场景下的算法性能，本文针对数据平面常用的FIB表和ACL表进行实验测试，并与文献[13]中介绍的针对P4程序的Vera工具的测试结果进行对比。

将FIB表项转换为POF指令块并对检测性能进行测试。FIB表项功能比较简单，转换为指令块后每一条表项对应着一个简单的比较跳转条件。本文算法与Vera针对FIB表的测试对比结果如图7所示。

图7 针对FIB表项的性能对比

从图7的对比结果可以看出，在数据规模很大的情况下，本文算法也能保持良好的表现。与Vera算法相比，本文算法能更快完成对FIB指令块的校验。在对180000条FIB表项进行检测时Vera需要16 s，而本文算法只需要41 ms。这种明显的差距主要是因为2种检测方案在取舍上有所不同。Vera算法侧重于对程序进行全面而细致的检查以方便程序的开发调试，而本文算法侧重于在交换机运行时快速对表项进行实时检测以保证交换机的运行时安全。

接下来针对ACL表项进行性能测试。ACL表项用于对数据包进行分类与过滤，相较于FIB表项，ACL表项中的分支条件更为复杂，数据包的处理过程可以由IP地址、端口号、协议类型等多种判断条件决定。针对ACL表项的测试结果对比如图8所示。

图8 针对ACL表项的性能对比

在针对ACL表项的测试中，Vera算法对2200条ACL表项进行检测所需要的时间大约为1 min，比其对180000条FIB表项进行检测所需要的时间还要长。而本文所提出的算法可以在1 ms内完成相同数量ACL表项的检测，性能与FIB表项中的测试结果保持一致。这是因为Vera算法中只是使用了文献[27]中提到的方法针对程序中的分支进行简单优化，但该方法只适用于简单分支的情况，在复杂分支的情况下提升有限，因此其执行时间不稳定。而本文中实现的检测算法具有稳定的线性时间复杂度，即使指令块中包含复杂分支,也不会对算法性能造成显著影响。

6 结束语

由于数据平面编程的场景特殊性，其对程序校验的侧重点与普通程序有所不同。本文针对POF表项中指令块的特点，设计并实现了校验方案。其针对指令合法性的检测主要是通过规则检测实现的；针对不可达指令和循环的检测是使用一种改进的深度优先搜索算法实现的；而针对循环合法性的校验是通过一种基于强连通分量的算法实现的。

本文提出的检测方案可以快速有效地在指令块被解释执行之前就检测出其中的常见错误，在保证交换机的安全性的同时，也为控制平面程序开发调试带来了便利性。

需要指出的一点是，本文中的循环合法性校验算法中在设计中着重考虑了算法的运行效率，因此支持的循环类型有限，校验条件也相对比较严格。如何支持更多循环类型可以作为下一步的研究点。