基于規范變異的ＢＧＰ－４健壯性測試研究

摘要：提出了一種系統實現協議健壯性測試的新方法。該方法通過深入分析BGP的路由信息處理過程，提出場景模型來描述決策過程和更新過程的應用環境和控制參數，基于該模型通過定義場景單元、表達式、謂語、接口、行為和功能重新表述了RI－Pro過程，并提出了適用于BGP的RI－Pro的變異操作集合，通過規范變異方法構建了用于構造健壯性測試案例的關系集合。實驗表明，使用該方法生成案例數目相對單純依靠協議文本生成的反向測試案例在數量上提高24%，其檢錯能力是正向測試集的2.3倍。

關鍵詞：健壯性測試;邊界網關協議;場景模型;規范變異

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2007)07－0234－04

健壯性是描述一個系統或組件在高強度輸入環境下或者在無效數據輸入時，其各項功能能夠保持正確運行的程度[1]。Internet協議的健壯性原則[2]要求協議實現要寬容地接收外部信息，同時對自身發出信息要謹慎和嚴格。目前，BGP－4(Border Gateway Protocol 4)[3]已成為Internet域間路由的事實標準，是Internet體系結構中的核心控制組件。復雜、開放式的Internet環境對BGP的健壯性提出了巨大挑戰，協議實體的任何實現缺陷[4]以及錯誤使用[5]都將直接影響到Internet的連通性、可靠性和安全性[6，7]。在BGP應用到Internet之前，除了進行一致性和互操作測試以外，必須對BGP實現進行健壯性測試。

RI－Pro是路由協議的核心，其主要功能是路由信息的計算和路由表的更新，以及新路由信息的生成和傳播。RI－Pro是協議測試的主要內容，文獻[8]定義了RIPTS(Routing Information Processing Test Script)來替代傳統的TTCN(Tree and Tabular Combined Notation)用于RI－Pro的測試描述。而文獻[9]提出了生成RI－Pro反向測試案例的指導性范圍，給出了健壯性測試框架。 

本文提出了一種實用的健壯性測試案例的生成方法。該方法首先使用RI－Pro場景模型對RI－Pro的外部行為進行描述，通過定義變異操作（Mutation Operators，MO）集合對基于場景模型描述的協議規范變異，構建出沖突關系集合。最后利用沖突關系集合中的矛盾關系重新構造出用于RI－Pro健壯性測試的應用場景。

1RI－Pro分析與場景模型

1．1 RI－Pro分析

Internet標準化組織（Internet Engineering Task Force，IETF）制定了BGP的標準[3]。在該標準中，RI－Pro的功能是根據接收到的 Update消息中的路由項進行新路由的計算、決策和發布。圖1為BGP路由更新的處理過程。

當協議實現時，由于協議實現者只需保證實現與標準保持外部可觀察的一致性，協議實現者往往依據自身對協議的理解和實際需要，對處理過程進行修改。例如Cisco就對RI－Pro規定的最佳路由選擇進行了較大修改。

RI－Pro的實現與標準規定可以差別很大。盡管RI－Pro具有千差萬別的內部實現，但是它們依然可以非常好地實現在Internet上的協作。這是由于它們的外部行為與協議標準是一致的。筆者要依據外部行為建立RI－Pro的新模型，使得新模型保持原協議標準規定的必須統一遵守的交互規則和外部表現形式，同時丟棄一些對于測試沒有價值的內部細節描述。

1．2RI－Pro建模

所有的會話、輸入、輸出和控制信息構成了該更新過程的應用環境。所謂RI－Pro的場景模型，是指刻畫路由更新處理和決策過程應用環境的模型。該模型重新對RI－Pro進行描述，不再研究RI－Pro的內部過程和實現方法，只研究在控制參數設定的應用環境下，在特殊選定的激勵下，RI－Pro的行為表現和結果輸出。圖2為BGP的RI－Pro的場景模型。

該場景模型對協議規定的RI－Pro進行了較大改造，對外部不可見的所有內部計算和決策都不予考慮，但是對協議規定的外部輸入、輸出和外部動作不僅予以全部保留，并且重新歸類。該模型中關系集合的提出，賦予了該模型以靈魂，使得該模型不是對RI－Pro外部行為的簡單重復描述，更不是把RI－Pro的處理過程退化為只能從外部觀察的黑盒；該模型是從外部所有可利用資源的關系上重新審視路由處理過程。該模型是研究RI－Pro的所有可控資源的關系，深層次地重新演繹了該過程。

1．3基于場景模型的RI－Pro表述

建立場景模型和場景的概念之后，基于該模型重新審視RI－Pro。該過程將不再是路由信息處理具體功能的過程描述，而轉換為場景元素各種關系表達式的集合以及在特定關系下的行為定義。場景單元（A Scenario Unit）：由場景模型定義，并且被協議規范引用的對象。場景單元必須具有明確的定義和清晰的對象類型。場景單元包括四類： 

(1)數據類。路由可達信息（Network Layer Reachability Information，NLRI）。

(2)數據的屬性類——ORIGIN、 AS_PATH、 NEXT_HOP、 MULTI_EXIT_DISC、 LOCAL_PREF、 ATOMIC_AGGREGATE 和 AGGREGATOR。

(3)數據的控制變量類——控制參數 （如各類計時器）、策略等。

(4)數據的環境變量類——RIB(Routing Information Base)、 RT(Routing Table)等。

2協議規范變異

協議規范本質上來說是協議限定關系的描述文本。基于場景模型，重新表述RI－Pro后，元素與元素之間的制約關系δ被準確嚴謹地定義和表示出來。筆者希望從這些制約關系δ出發，最終獲得健壯性測試所需要的矛盾制約關系δ′。本文使用協議規范變異的方法實現了這個轉換過程。

規范變異測試是通過給出一組變異因子對規范進行變異，使用變異后的規范對實現實體進行測試；規范變異測試是提高實現可信度的有效方法。規范變異要基于變異操作集合，變異操作集合中的每一個變異操作均關聯著一種可能出現的錯誤類型。在過去的十年中，變異測試從最初的代碼測試已經應用到其他的一些測試領域[10]， Delamaro[11]提出了接口變異（Interface Mutation）概念；Paul Black[12] 將變異測試應用到規范測試中；特別是Simone等人[13]對形式化描述 (Formal Description Techniques，FDT) 協議的變異問題進行了研究。

定義有效的變異操作集合MO是規范變異成功的關鍵。依據文獻[14，15]對錯誤類型的歸類，本文給出了適于BGP協議健壯性測試的變異操作集合。RI－Pro的MO分為以下三類。

2．1場景單元變異

（1）無效場景單元替代操作 (Invalid Scenario Unit Operator，ISUO)。用語法正確但是超出定義域的值替代場景元素的值，包括使用無效數據、數據的無效屬性、數據的無效控制變量和數據的無效環境變量等。

（2）變量取反操作(Variable Negation Operator，VNO)。用變量x替代變量x。

（3）布爾取反操作(Boolean Negation Operator，BNO)。用布爾變量p替代布爾變量p。

2．2表達式變異

（1）關系運算替代操作(Relational Operator Reference Ope－rator，RORO)。用其他的關系運算符替代原關系運算符。

應用以上給出的變異操作集合，可以實現對RI－Pro的變異。ISUO、VNO和BNO變異實現了對場景單元的變異，通過變異可以生成各種報文格式錯誤。RORO和CPNO變異實現對RI－Pro的執行條件的變異，通過變異可以生成制約、匹配、控制和時序等關系組的沖突關系。IMO變異實現了對RI－Pro的行為和功能的變異。

與文獻[11~13]提出的變異操作相比，本文擴展了變異對象，變異對象從單純的數據擴展到數據的屬性、數據的控制變量和數據的環境變量。針對健壯性測試筆者提出一些新的變異操作，如 G！emutateG?e就是健壯性測試所特有的。

3測試案例生成和實際測試結果

使用規范變異方法對RI－Pro進行變異，筆者獲得了213個矛盾沖突關系。其中有97 個沖突關系在協議規范中已經包含或者不能與正常限定關系相區分，有61個沖突關系是不可執行、不可測試或重復的沖突關系，最終只有55個沖突關系可以用于構造異常場景進行健壯性測試。

IXIA公司的ANVL[16]（Automated Network Validation Library）測試系統被 250多家公司（3Com、Cisco、Lucent、 Nortel 和Intel等）用于協議一致性和互操作性測試。依托該測試系統整體框架，為了方便地向DUT注入錯誤，筆者擴展了BGP的參考實現[17]，并實現了反向測試集，形成BGP健壯性測試套。

BGP規范[3]中規定了錯誤處理相關內容，為協議實現者采用統一的錯誤處理方式提供了依據，也為反向測試案例生成提供了有價值的參考。表1列出了ANVL依據本章內容生成的RI－Pro測試案例集和基于場景模型生成的反向測試案例集的對比結果。表2列出了ANVL生成的RI－Pro正向測試集和基于場景模型生成的反向測試集的檢錯能力對比(IUT: Cisco 7200， IOS 版本 11.3)。

4結束語

本文給出了適于描述RI－Pro的場景模型，提出了基于該模型的健壯性案例的生成方法。通過實際應用可以獲得以下結論：本文方法生成的測試案例針對性強。健壯性測試應用于核心路由器的BGP開發后，對實現中脆弱環節的查找、定位和修正起到了重要作用，提高了實現實體的健壯性。下一步的工作將研究如何把該方法應用到其他協議的健壯性測試中。

參考文獻：

［1］IEEE Std. 610.12—1990 IEEE standard glossary of software engineering terminology[S].[S.l.]:[s.n.]，1990.

［2］RFC 1123 Requirements for Internet hosts:application and support[S].[S.l.]:[s.n.]，1989.

［3］RFC1771 A border gateway protocol 4 (BGP－4)[S].[S.l.]:[s.n.]，1995.

［4］LABOVITZ C，MALAN G R，JAHANIAN F.Origins of Internet routing instability[C]//Proc of the 2002 IEEE INFOCOM. New York:[s.n.]，2002:218－226.

［5］MAHAJAN R，WETHERALL D，ANDERSON T.Understanding BGP misconfiguration[C]//Proc of the 2002 ACM SIGCOMM.Pittsburgh， PA， USA:[s.n.]，2002:33－47.

［6］MISEL S A W. AS7007 NANOG mail archives[EB/OL].[2006－03].http://www.merit.edu/mail.archives/nanog/1997－04/msg00340.html.

［7］FARRAR J C，INSTABILITY W R.NANOG mail archives[EB/OL].[2006－01].http://www.merit.edu/mail.archives/ nanog/2001－04/mes00209.html.

［8］WU Jianping，LI Zhaojie，YIN Xia.Towards modeling and testing of IP routing protocols[C]//Proc of the 15th IFIP International Conference， TestCom 2003.Sophia Antipolis， France:[s.n.]，2003:49－62.

［9］WANG Lechun， ZHU Peidong， GONG Zhenghu. Systematic robustness－testing RI－Pro of BGP[C]//Proc of ISPA2004.Hong Kong:[s.n.]，2004:463－468.

［10］WOODWARD M R.Mutation testing: its origin and evolution[J].Information and Software Technology， 1993，35(2):163－169.

［11］DELAMARO M E，MALDONADO J C，MATHUR A P.Interface mutation:an approach for integration testing[J].IEEE Transactions on Software Engineering， 2001，27(3):228－247.

［12］BLACK P，OKUN V，YESHA Y.Mutation operators for specifications[C]//Proc of the 15th Annual Software Engineering Conference.Grenoble， France:IEEE Computer Society，2000:81－88.

［13］ROCIO doS，SOUZA de S.Mutation testing applied to estelle specifications[C]//Proc of the 33rd:International Conference on System Sciences.Maui Hawaii:[s.n.]，2000:1－10.

［14］KUHN D R.Fault classes and error detection in specification based testing[J].ACM Transactions on Software Engineering Methodology， 1999，8 (4): 411－424.

［15］WANG Lechun，ZHU Peidong，GONG Zhenghu. Robustness analysis and robustness models of BGP[J].Computer Engineering Science，2004，26(11):4－8.

［16］[EB/OL].[2006－02].http://www.ixiacom.com/products/caa/anvl_testsuitedesc.php.

［17］WANG Lechun，GONG Zhenghu，CHEN Jianrong. The architecture of testing protocol implementation robustness based on fault injection[J].Computer Engineering and Applications， 2003，39(22):139－142.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”