封 棟，陳 曉

(1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190; 2.中國科學(xué)院大學(xué)，北京 100049)

0 引 言

軟件定義網(wǎng)絡(luò)(Software-defined Networking, SDN)中采用控制平面和數(shù)據(jù)平面相分離的結(jié)構(gòu)，具有容易管理、升級的特點[1]。在SDN中，控制器通過南向接口協(xié)議向交換機下發(fā)流表，交換機根據(jù)數(shù)據(jù)包對表項進(jìn)行匹配，通過執(zhí)行表項內(nèi)的動作和指令，完成數(shù)據(jù)包的處理和轉(zhuǎn)發(fā)。

OpenFlow是SDN的一個代表性南向接口協(xié)議[2-3]，但由于它的匹配域是協(xié)議相關(guān)的，導(dǎo)致OpenFlow存在拓展性差等限制。為了提高底層設(shè)備的可編程性，學(xué)者們做了許多研究。這其中比較有代表性的工作是可編程協(xié)議無關(guān)報文處理(Programming Protocol-independent Packet Processors, P4)[4]和協(xié)議無感知轉(zhuǎn)發(fā)(Protocol Oblivious Forwarding, POF)[5]。P4設(shè)計了自己的處理語言和相應(yīng)的轉(zhuǎn)發(fā)模型[6-7]，從而提高了數(shù)據(jù)平面編程能力。而POF通過使用{類型，偏移，長度}元組的描述方式實現(xiàn)了協(xié)議無關(guān)。POF更加類似于OpenFlow的一種拓展，其轉(zhuǎn)發(fā)模型與OpenFlow基本一致。文獻(xiàn)[8]對P4和POF進(jìn)行了詳細(xì)的對比與介紹。POF定義了指令集，可對數(shù)據(jù)包等數(shù)據(jù)進(jìn)行設(shè)置、比較等運算，實現(xiàn)了對數(shù)據(jù)平面的編程。由于POF具有靈活性，許多網(wǎng)絡(luò)研究都是基于POF進(jìn)行的[9-10]。

POF指令集包括指令(Instruction)和動作(Action)這2種類型。指令和動作在語義上有細(xì)微的區(qū)分，一個指令可以包含多個動作。為了方便表述，在下文中使用“指令塊”一詞指代POF表項中所包含的指令和動作所構(gòu)成的程序。

早期的POF每個表項中執(zhí)行的指令塊很簡單，指令只有順序執(zhí)行，沒有復(fù)雜的執(zhí)行控制。POF的發(fā)展過程中逐漸引入了新的指令和功能。特別是比較、跳轉(zhuǎn)等指令的增加，改變了原本動作順序執(zhí)行模式，使得跳轉(zhuǎn)、循環(huán)執(zhí)行成為可能，軟件交換機可編程能力得到了很大提高。

新的指令和功能的加入在提高底層設(shè)備可編程性的同時，也加大了軟件漏洞產(chǎn)生的可能性。一旦控制器下發(fā)的一個流表中的指令塊中出現(xiàn)了錯誤，有可能會直接導(dǎo)致整臺交換機的故障。因此實現(xiàn)一種實時安全檢測機制是很有必要的。本文要解決的問題就是希望通過預(yù)處理的方法，提前發(fā)現(xiàn)使得軟交換機崩潰的情形，避免軟交換機產(chǎn)生死機等問題。

造成軟件漏洞的原因有很多，指令塊作為一種專用領(lǐng)域的程序，常見且比較重要的漏洞可以總結(jié)為如下3類：

1)單條指令的錯誤。包括指令的類型和參數(shù)。使用了非法的指令類型，或者指令中出現(xiàn)了訪問越界，都會導(dǎo)致交換機出現(xiàn)不可預(yù)期錯誤。

2)存在不可達(dá)指令。雖然不可達(dá)指令的存在不會直接造成交換機崩潰，但其往往是由于錯誤使用了跳轉(zhuǎn)指令造成的，提示程序存在邏輯錯誤。

3)指令塊中存在死循環(huán)。由于數(shù)據(jù)平面交換機的解釋—執(zhí)行模式，一個指令塊的死循環(huán)可能會導(dǎo)致整個交換機被卡死。這一點與通常程序有很大不同。因為通常程序一般是作為一個進(jìn)程運行的，由操作系統(tǒng)提供資源隔離，一個程序并不會引起整個系統(tǒng)的崩潰。因此，對于指令塊來說，避免死循環(huán)問題十分重要。

需要指出的是，防止指令塊出現(xiàn)死循環(huán)的最有效的處理方案是直接禁止程序中出現(xiàn)循環(huán)結(jié)構(gòu)。但是考慮到循環(huán)在諸如數(shù)據(jù)包的組播等應(yīng)用中會為控制平面編程提供很大的便利性，因此一種更合理的方案是允許簡單的循環(huán)體出現(xiàn)，但必須通過嚴(yán)格的校驗。

另外，由于指令塊是在交換機運行時由控制平面動態(tài)下發(fā)，因此需要對其進(jìn)行實時檢測，這一點與通常檢測程序有很大不同。

本文針對上述幾種漏洞的檢查給出相應(yīng)的算法和實現(xiàn)方案。通過基于控制流圖的檢測可以發(fā)現(xiàn)是否有單條指令的錯誤、是否存在不可達(dá)指令以及是否存在循環(huán)。而對于存在的循環(huán)塊，提出一種基于強連通分量的檢測算法用以判斷循環(huán)的合法性。檢測方案的整體時間復(fù)雜度為線性，可以保證實時檢測。

1 相關(guān)工作

目前尚未有針對POF協(xié)議的應(yīng)用檢測的相關(guān)研究，但是有一些針對其他協(xié)議和編程語言的SDN應(yīng)用檢測的研究可供參考。NICE是一款比較知名的對OpenFlow執(zhí)行模型檢查的工具，用于在SDN網(wǎng)絡(luò)中的控制平面中查找可能存在的問題[11]。p4pktgen是針對P4程序的一款檢測工具，通過使用自動生成測試用例對應(yīng)用進(jìn)行測試，以確保程序執(zhí)行結(jié)果與預(yù)期相符。p4pktgen執(zhí)行速度較慢，但可以發(fā)現(xiàn)程序中可能存在的邏輯錯誤[12]。Vera是P4的另一款調(diào)試檢測工具，通過符號執(zhí)行以發(fā)現(xiàn)程序中的常見問題，包括解析錯誤、訪問越界、指令錯誤等[13]。p4pktgen和Vera這2種驗證方式是相輔相成的。

由于P4和POF均為協(xié)議無關(guān)的數(shù)據(jù)平面編程技術(shù)，因此針對P4的檢測研究具有重要的參考意義。本文的工作與Vera類似，旨在通過靜態(tài)測試發(fā)現(xiàn)程序中的漏洞以保證交換機運行時的穩(wěn)定性。

然而POF與P4存在2個很大的不同點。1)P4是編譯型的程序，因此P4程序的校驗過程可以離線進(jìn)行，有足夠時間對程序進(jìn)行充分而細(xì)致的檢測；而POF是解釋型的，控制器下發(fā)指令塊后會直接部署到交換機中，必須實現(xiàn)快速的實時性檢測，因此類似于p4pktgen的檢測方式在POF中是不適用的。2)P4語言本身不支持循環(huán)，因此無需在單條表項中對循環(huán)進(jìn)行檢驗。而在POF中是允許循環(huán)出現(xiàn)的，針對循環(huán)合法性校驗是本文要研究解決的重點問題之一。

若不局限于SDN領(lǐng)域，目前已經(jīng)存在很多優(yōu)秀的靜態(tài)代碼檢查工具。比如Cppcheck是一種用于C和C++編程語言的靜態(tài)代碼分析工具[14]，主要檢查的內(nèi)容包括變量檢查、邊界檢查、資源泄漏、風(fēng)格檢查等；Clang的靜態(tài)分析器也是知名的源代碼分析工具，用于發(fā)現(xiàn)C、C++和Objective-C程序中的錯誤。此外，針對Java、Python等其他主流語言也有很多對應(yīng)的靜態(tài)檢查工具。

雖然現(xiàn)有的靜態(tài)分析工具比較成熟，但卻無法直接應(yīng)用于POF的指令塊的檢測。原因主要有如下2點：

1)現(xiàn)有的程序靜態(tài)檢測研究和應(yīng)用主要是針對高級語言進(jìn)行的，主要檢測內(nèi)容包括代碼風(fēng)格、類型檢查等，而POF指令塊的程序更加類似于匯編，無法直接使用現(xiàn)有檢測工具，并且檢測重點也有所不同。

2)絕大多數(shù)靜態(tài)檢測工具不會對程序的循環(huán)合法性進(jìn)行檢測，而死循環(huán)檢測在指令塊中至關(guān)重要。

盡管無法直接使用現(xiàn)有的靜態(tài)分析工具，但是其研究方法與實現(xiàn)方案可提供參考。張林等人[15]對現(xiàn)有的靜態(tài)分析進(jìn)行了分析與討論；周寬久等人[16]提到了將程序轉(zhuǎn)換為XML中間模型，從而可以實現(xiàn)檢測與語言分離；而靜態(tài)分析和程序編譯中經(jīng)常用到的分析控制流圖等方法，對于指令塊這樣的程序也同樣適用。

檢測程序死循環(huán)的最直接有效的方法是動態(tài)檢測，即在程序運行時監(jiān)控代碼塊的運行時間或者運行次數(shù)，達(dá)到指定限制后即認(rèn)為程序中存在死循環(huán)。但動態(tài)檢測主要存在著2個問題。1)由于需要對程序運行狀態(tài)進(jìn)行監(jiān)控，這將直接增加運行時負(fù)擔(dān)，導(dǎo)致交換機性能降低；2)由于流表下發(fā)后只有對應(yīng)的數(shù)據(jù)包到達(dá)時才會觸發(fā)指令塊執(zhí)行，這會導(dǎo)致漏洞發(fā)現(xiàn)不及時。因此靜態(tài)檢測潛在的死循環(huán)是一種更好的選擇。

然而，程序的死循環(huán)問題本質(zhì)上等價于停機問題，因而通用的靜態(tài)檢測方法是不存在的。這也正是絕大多數(shù)靜態(tài)檢測工具都不做死循環(huán)檢測的原因。盡管如此，針對特定模式的死循環(huán)檢測還是可以實現(xiàn)的，目前也有了許多研究工作。文獻(xiàn)[17]介紹了對于實際中的2種常見死循環(huán)條件的嚴(yán)格數(shù)學(xué)證明；文獻(xiàn)[18]介紹了通過分析歸納變量的循環(huán)依賴從而生成程序測試用例的方法；文獻(xiàn)[19]提到了利用循環(huán)變量分析程序代碼的思想，但只是針對具體代碼和循環(huán)模式進(jìn)行了分析，并沒有給出可用的算法實現(xiàn)。

2 檢測方案設(shè)計與分析

指令塊由控制平面下發(fā)，在數(shù)據(jù)平面執(zhí)行。因此檢測工作既可以在控制平面進(jìn)行，也可以在數(shù)據(jù)平面進(jìn)行。在控制平面進(jìn)行的檢測好處是無需下發(fā)流表即可提示出相應(yīng)的錯誤。在數(shù)據(jù)平面進(jìn)行檢測則需要先將收到的南向協(xié)議數(shù)據(jù)包進(jìn)行解析，才能返回錯誤信息。

但是在數(shù)據(jù)平面進(jìn)行檢測有如下3個好處：

1)可以直接使用數(shù)據(jù)平面已有的南向協(xié)議解析接口方便地提取出指令塊。

2)雖然需要下達(dá)流表后才能返回錯誤信息，但是可以使用南向接口協(xié)議中定義的錯誤反饋接口，架構(gòu)上更加清晰。

3)考慮到交換機的設(shè)計中可能會加載本地的指令塊程序，檢測程序統(tǒng)一放在數(shù)據(jù)平面更為合理。

基于以上考慮，最終決定在數(shù)據(jù)平面對檢測程序進(jìn)行實現(xiàn)。

指令塊的主要檢測內(nèi)容包括指令參數(shù)檢查、指令可達(dá)性檢查以及潛在的死循環(huán)檢查。具體來說，檢測流程為：首先將POF協(xié)議的指令塊按照語義轉(zhuǎn)化成統(tǒng)一的中間指令，并對指令的類型與參數(shù)進(jìn)行檢查；然后構(gòu)建控制流圖，通過對控制流圖的分析檢查出不可達(dá)指令和存在的循環(huán)。針對循環(huán)塊，進(jìn)一步通過基于強連通分量的算法判斷循環(huán)是否為合法循環(huán)。

系統(tǒng)整體流程如圖1所示。

圖1 系統(tǒng)整體流程圖

3 基于控制流圖的檢測

3.1 中間表示與參數(shù)檢測

為了便于分析與處理，同時考慮到支持其他南向接口協(xié)議的可能性，首先將指令塊按照語義統(tǒng)一轉(zhuǎn)換為中間指令。之前提到過，在POF協(xié)議中，指令塊的內(nèi)容被分為指令和動作2種類型，一個指令內(nèi)可以包含多個動作。這種嵌套設(shè)定會為解析與校驗帶來許多困難，因此采用了將其按照語義轉(zhuǎn)換為統(tǒng)一的中間表示的方法。中間指令表示由操作碼、標(biāo)志位、操作數(shù)3部分組成。

轉(zhuǎn)換后的主要操作碼類型包括字段操作計算指令、算術(shù)邏輯指令、輸出指令、跳轉(zhuǎn)指令、表操作指令。標(biāo)志位字段用于標(biāo)識操作數(shù)是數(shù)據(jù)包字段、元數(shù)據(jù)字段或者其他字段。操作數(shù)可以分為立即數(shù)和使用{類型，偏移，長度}元組描述的匹配數(shù)2種類型。

在得到中間表示后首先進(jìn)行指令級別的檢測。檢測內(nèi)容如下：

1)對操作碼類型進(jìn)行檢測。判斷是否為合法類型。通過預(yù)先存儲合法指令類型，可以在常數(shù)時間內(nèi)完成對一條指令的操作碼校驗。

2)對標(biāo)志位進(jìn)行檢測。判斷是否有非法標(biāo)志。

3)對操作數(shù)進(jìn)行檢測。主要進(jìn)行參數(shù)合法性檢測。特別地，對于跳轉(zhuǎn)類指令，檢測跳轉(zhuǎn)的目的地址是否合法。

3.2 構(gòu)建控制流圖

控制流圖(Control Flow Graph, CFG)是指以有向圖的形式抽象表示出程序執(zhí)行中的所有路徑[20]，是編譯器優(yōu)化和靜態(tài)分析的重要工具，在支配分析、程序優(yōu)化等領(lǐng)域都有使用[21-22]。

控制流圖的單位為基本塊。一個基本塊由一條或幾條連續(xù)的程序語句組成。本文所以使用了將每一條指令直接視為一個基本塊的做法。這樣可以免去基本塊的判斷條件的分析，并且在控制流圖分析的過程中數(shù)據(jù)結(jié)構(gòu)比較簡單，同時可以方便地定位到指令的位置。

具體來說，本文所述的指令塊的控制流圖的生成方式為：遍歷所有指令。如果指令為比較跳轉(zhuǎn)類指令，則為其添加2條邊：一條邊指向下一個指令，另一條邊指向目的指令；如果指令為直接跳轉(zhuǎn)指令，添加一條指向目的位置的邊；如果指令為結(jié)束指令或者表跳轉(zhuǎn)指令，不添加邊；其余類型的指令添加指向下一條指令的邊。

得到的控制流圖為一個有向圖，圖的入口為第一條指令，圖的出口為最后一條指令或者結(jié)束指令。

3.3 指令可達(dá)性和循環(huán)檢測

通過對控制流圖的分析便可以找到圖中存在的不可達(dá)指令和存在的循環(huán)結(jié)構(gòu)。

圖2 不可達(dá)指令和循環(huán)指令塊

在圖2左圖中的深色節(jié)點為一個不可達(dá)指令，即無法通過程序的入口訪問到。不可達(dá)指令塊的存在通常是由于直接跳轉(zhuǎn)等指令的錯誤使用而造成的。出現(xiàn)了不可達(dá)指令意味著程序存在著邏輯錯誤。右圖的3個深色節(jié)點構(gòu)成一個循環(huán)塊。循環(huán)塊的出現(xiàn)通常是由于比較跳轉(zhuǎn)指令的使用。出現(xiàn)了循環(huán)塊提示此處可能會有死循環(huán)問題，需要進(jìn)一步檢驗循環(huán)合法性。

對于不可達(dá)指令的檢測比較簡單。只需對控制流圖使用一次深度優(yōu)先搜索(Depth-First Search, DFS)或者廣度優(yōu)先搜索(Breadth-First Search, BFS)進(jìn)行遍歷，如果存在無法到達(dá)的節(jié)點則意味著存在不可達(dá)指令。

對于有向連通圖中的循環(huán)檢測有多種方法。一種常用的方法是通過深度優(yōu)先搜索樹的邊的類型進(jìn)行判斷，如果存在回邊(Back Edge),則可判斷圖中存在循環(huán)。

通過對DFS過程中的節(jié)點進(jìn)行染色標(biāo)記，可以在一次DFS中同時找到不可達(dá)指令和存在的循環(huán)指令塊。主要思想為：所有節(jié)點初始為白色，在DFS的過程中，第一次到達(dá)節(jié)點將其標(biāo)記為灰色；搜索到路徑的終點后在回溯的過程中將節(jié)點置為黑色。同時在DFS的過程中對邊類型進(jìn)行標(biāo)記，如果邊指向了灰色節(jié)點則標(biāo)記為回邊。DFS完成后存在非黑節(jié)點則說明有不可達(dá)指令。存在回邊則說明存在循環(huán)體。該算法的時間復(fù)雜度為線性。

算法偽代碼如圖3所示。

4 基于強連通分量的循環(huán)判斷

在上一章中通過控制流圖分析的方法找出了循環(huán)塊在程序中的位置。本章介紹有界循環(huán)判斷的方法。

為了滿足系統(tǒng)實時檢測的需求，同時也因為死循環(huán)判斷問題的復(fù)雜性，本文采用的算法中對循環(huán)的模式做了比較嚴(yán)格的限制。

4.1 循環(huán)的相關(guān)分析

循環(huán)變量是指在一個循環(huán)中不斷變化而最終使得循環(huán)結(jié)束的變量。以C語言程序為例，while(i<1){…i++…}中的變量i即為循環(huán)變量。在指令塊程序中，造成循環(huán)結(jié)構(gòu)的回邊的起始節(jié)點對應(yīng)的指令中的源操作數(shù)即為循環(huán)變量。

循環(huán)終止條件通常是循環(huán)變量與一個常量或變量進(jìn)行比較(比較條件為大于、小于、不等于等)，不滿足比較條件后跳出循環(huán)。其中，循環(huán)變量與常量進(jìn)行比較，且比較條件為大于或小于的循環(huán)是本文分析的重點。這是因為大于或小于的情況可以通過對循環(huán)塊中各條路徑的單調(diào)性分析給出循環(huán)合法性結(jié)論，而不等于的情況十分復(fù)雜，沒有簡單有效的判別方法。而只分析與常量進(jìn)行比較的循環(huán)類型原因是如果同時跟蹤2個變量，會導(dǎo)致檢測算法復(fù)雜度增加，難以保證實時性。

圖3 不可達(dá)指令和循環(huán)指令塊檢測偽代碼

4.2 強連通分量計算

強連通分量(Strongly Connected Component)是圖論中的概念。在有向圖中，如果所有節(jié)點兩兩之間都存在一條連通路徑，則該圖為一個強連通圖。而強連通分量則是指一張有向圖的極大強連通子圖。

圖4 強連通分量示例

以圖4中的有向圖為例。圖中共有2個強連通分量。其中白色節(jié)點構(gòu)成一個強連通分量，深色節(jié)點構(gòu)成另一個強連通分量。白色節(jié)點和深色節(jié)點之間不存在雙向路徑。

在程序中，一個循環(huán)對應(yīng)著控制流圖中的一個環(huán)。環(huán)中所有指令都互相可達(dá)，因此根據(jù)強連通分量的定義可知，一個循環(huán)塊內(nèi)的所有指令都屬于控制流圖中的同一個強連通分量。

計算有向圖的強連通分量的算法比較多[23]，經(jīng)典算法包括Kosaraju算法[24]、Gabow算法[25]和Tarjan算法[26]。算法的時間復(fù)雜度均為O(V+E)。其中V為頂點數(shù)，E為邊數(shù)。本文選擇使用Tarjan算法求取控制流圖的強連通分量。

通過計算強連通分量，將控制流圖劃分為多個子圖，從而縮減了循環(huán)變量跟蹤時的搜索范圍。

4.3 循環(huán)變量跟蹤

通過強連通分量計算得到了可能會使循環(huán)變量的值發(fā)生改變的所有指令。循環(huán)體執(zhí)行一次的過程對應(yīng)于在循環(huán)塊的起點節(jié)點到終點節(jié)點之間的某一條路徑。對于while(i<1)形式的循環(huán)，理論上測試所有路徑來判斷循環(huán)變量是否總是增加便可以判斷循環(huán)是否一定可以在某個點終止，反之亦然。

但是如果循環(huán)塊中存在多個分支，由于分支之間可以任意組合，因此會存在路徑爆炸問題。對所有路徑進(jìn)行遍歷，將會導(dǎo)致算法復(fù)雜度急劇上升。

鑒于路徑跟蹤的復(fù)雜性，本文提出一種簡化的基于強連通分量的檢測算法。該算法主要基于以下事實(仍以while(i<1)形式的循環(huán)為例)：

1)循環(huán)體中任意一條可執(zhí)行路徑中的指令都是該循環(huán)所屬強連通分量的子集。因此，如果強連通分量中所有指令都不存在可以使循環(huán)變量值增加的指令，那么該循環(huán)必為死循環(huán)。

2)分支和循環(huán)的產(chǎn)生都是由于跳轉(zhuǎn)類指令造成的。如果一個循環(huán)所屬強連通分量中只包含一條跳轉(zhuǎn)類指令(即造成循環(huán)的那一條指令)，那么該指令塊中的所有指令必為順序執(zhí)行。如果同時強連通分量中對于循環(huán)變量的修改指令只會使得其單調(diào)遞增，那么該循環(huán)必為合法循環(huán)。

因此只需要對循環(huán)所屬的強連通分量的所有指令進(jìn)行一次遍歷，便可以得到關(guān)于循環(huán)合法性的判斷。算法復(fù)雜度由路徑搜索的最壞情況下的指數(shù)復(fù)雜度變?yōu)榱朔€(wěn)定的線性復(fù)雜度。這樣做的代價是可以使檢測的循環(huán)類型有所減少，但考慮到表項指令塊中通常只會出現(xiàn)簡單的循環(huán)語句，因此該算法在實際應(yīng)用中仍可發(fā)揮重要作用。

算法偽代碼如圖5所示。

圖5 循環(huán)合法性校驗偽代碼

5 實驗與分析

根據(jù)以上介紹的方法，在POF軟件交換機上實現(xiàn)了合法性檢測程序。實驗環(huán)境為運行在i5 3230M CPU上的Centos7.7系統(tǒng),內(nèi)存為8 GB。作為一種檢測程序，主要針對其有效性和執(zhí)行效率進(jìn)行實驗驗證。

5.1 有效性測試

為驗證檢測程序的有效性，手動設(shè)計了多種類型的指令塊進(jìn)行測試。設(shè)計原則為盡可能多地包含實際指令塊中可能出現(xiàn)的程序類型，包括非法指令、不可達(dá)指令以及多種類型的循環(huán)等。

對測試中使用到的所有指令塊的檢測結(jié)果進(jìn)行匯總統(tǒng)計，結(jié)果如表1所示。其中對于死循環(huán)的檢測存在一定的誤報率，但不會漏報；而其他類型的檢測成功率均為100%。

表1 實驗結(jié)果統(tǒng)計分析

對于非法指令、不可達(dá)指令檢測和循環(huán)識別等基于控制流圖的具體測試結(jié)果如表2所示。從表2的測試結(jié)果中可以看出，常見的指令級別的錯誤和各種循環(huán)位置的檢測全部可以正確檢測出來。

表2 基于控制流圖的檢測結(jié)果

對于循環(huán)合法性的具體檢測結(jié)果如表3所示。由于循環(huán)的類型多樣，為方便表述，這里以等效C語言代碼對測試的循環(huán)類型進(jìn)行說明。

表3 循環(huán)合法性檢測的測試結(jié)果

從表3的檢測結(jié)果可以看出，本文中的算法可以對一些形式的循環(huán)給出一定合法或者一定非法的判斷。但是需要注意的是，本文方案目前并不能支持所有的循環(huán)模式，比如測試7～測試9中的循環(huán)類型。同時，對于循環(huán)塊中包含跳轉(zhuǎn)指令的循環(huán)類型，比如測試6中的嵌套循環(huán)，只能給出“可能合法”的判斷。由于這些無法完全判斷的循環(huán)類型的存在，本文算法針對死循環(huán)的檢測會存在一定的誤報率。

5.2 性能測試

通過測量檢測執(zhí)行所消耗的時間對檢測算法性能進(jìn)行測試。

首先針對本文中所提的檢測方案各階段的檢測速度進(jìn)行測試。為了提高時間測量的精確性，測試的時間為執(zhí)行10000次校驗的結(jié)果。測試所使用的指令塊使用腳本自動生成。測試程序類型包括3種：1)包含非法指令，指令校驗過程中即被檢測到；2)包含不可達(dá)指令，不包含循環(huán)，需要經(jīng)過控制流圖的搜索來檢測；3)包含循環(huán)，會經(jīng)過所有的檢測流程。對于每種類型的不同長度進(jìn)行測試。測試結(jié)果如圖6所示。

圖6 檢測算法性能測試

從實驗結(jié)果可以看出每一種情況下的運行時間都基本隨著指令長度線性增加，這與本文對檢測算法的復(fù)雜度分析結(jié)果是相吻合的。同時，完成對200行的指令塊的一次完整的檢測只需要0.2 ms左右，說明該檢測方案可以滿足對流表進(jìn)行實時檢測的需求。

此外，為了驗證真實場景下的算法性能，本文針對數(shù)據(jù)平面常用的FIB表和ACL表進(jìn)行實驗測試，并與文獻(xiàn)[13]中介紹的針對P4程序的Vera工具的測試結(jié)果進(jìn)行對比。

將FIB表項轉(zhuǎn)換為POF指令塊并對檢測性能進(jìn)行測試。FIB表項功能比較簡單，轉(zhuǎn)換為指令塊后每一條表項對應(yīng)著一個簡單的比較跳轉(zhuǎn)條件。本文算法與Vera針對FIB表的測試對比結(jié)果如圖7所示。

圖7 針對FIB表項的性能對比

從圖7的對比結(jié)果可以看出，在數(shù)據(jù)規(guī)模很大的情況下，本文算法也能保持良好的表現(xiàn)。與Vera算法相比，本文算法能更快完成對FIB指令塊的校驗。在對180000條FIB表項進(jìn)行檢測時Vera需要16 s，而本文算法只需要41 ms。這種明顯的差距主要是因為2種檢測方案在取舍上有所不同。Vera算法側(cè)重于對程序進(jìn)行全面而細(xì)致的檢查以方便程序的開發(fā)調(diào)試，而本文算法側(cè)重于在交換機運行時快速對表項進(jìn)行實時檢測以保證交換機的運行時安全。

接下來針對ACL表項進(jìn)行性能測試。ACL表項用于對數(shù)據(jù)包進(jìn)行分類與過濾，相較于FIB表項，ACL表項中的分支條件更為復(fù)雜，數(shù)據(jù)包的處理過程可以由IP地址、端口號、協(xié)議類型等多種判斷條件決定。針對ACL表項的測試結(jié)果對比如圖8所示。

圖8 針對ACL表項的性能對比

在針對ACL表項的測試中，Vera算法對2200條ACL表項進(jìn)行檢測所需要的時間大約為1 min，比其對180000條FIB表項進(jìn)行檢測所需要的時間還要長。而本文所提出的算法可以在1 ms內(nèi)完成相同數(shù)量ACL表項的檢測，性能與FIB表項中的測試結(jié)果保持一致。這是因為Vera算法中只是使用了文獻(xiàn)[27]中提到的方法針對程序中的分支進(jìn)行簡單優(yōu)化，但該方法只適用于簡單分支的情況，在復(fù)雜分支的情況下提升有限，因此其執(zhí)行時間不穩(wěn)定。而本文中實現(xiàn)的檢測算法具有穩(wěn)定的線性時間復(fù)雜度，即使指令塊中包含復(fù)雜分支,也不會對算法性能造成顯著影響。

6 結(jié)束語

由于數(shù)據(jù)平面編程的場景特殊性，其對程序校驗的側(cè)重點與普通程序有所不同。本文針對POF表項中指令塊的特點，設(shè)計并實現(xiàn)了校驗方案。其針對指令合法性的檢測主要是通過規(guī)則檢測實現(xiàn)的；針對不可達(dá)指令和循環(huán)的檢測是使用一種改進(jìn)的深度優(yōu)先搜索算法實現(xiàn)的；而針對循環(huán)合法性的校驗是通過一種基于強連通分量的算法實現(xiàn)的。

本文提出的檢測方案可以快速有效地在指令塊被解釋執(zhí)行之前就檢測出其中的常見錯誤，在保證交換機的安全性的同時，也為控制平面程序開發(fā)調(diào)試帶來了便利性。

需要指出的一點是，本文中的循環(huán)合法性校驗算法中在設(shè)計中著重考慮了算法的運行效率，因此支持的循環(huán)類型有限，校驗條件也相對比較嚴(yán)格。如何支持更多循環(huán)類型可以作為下一步的研究點。