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

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

關(guān)鍵詞：健壯性測試;邊界網(wǎng)關(guān)協(xié)議;場景模型;規(guī)范變異

中圖分類號：TP393文獻(xiàn)標(biāo)志碼：A

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

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

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

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

1RI－Pro分析與場景模型

1．1 RI－Pro分析

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

當(dāng)協(xié)議實現(xiàn)時，由于協(xié)議實現(xiàn)者只需保證實現(xiàn)與標(biāo)準(zhǔn)保持外部可觀察的一致性，協(xié)議實現(xiàn)者往往依據(jù)自身對協(xié)議的理解和實際需要，對處理過程進(jìn)行修改。例如Cisco就對RI－Pro規(guī)定的最佳路由選擇進(jìn)行了較大修改。

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

1．2RI－Pro建模

所有的會話、輸入、輸出和控制信息構(gòu)成了該更新過程的應(yīng)用環(huán)境。所謂RI－Pro的場景模型，是指刻畫路由更新處理和決策過程應(yīng)用環(huán)境的模型。該模型重新對RI－Pro進(jìn)行描述，不再研究RI－Pro的內(nèi)部過程和實現(xiàn)方法，只研究在控制參數(shù)設(shè)定的應(yīng)用環(huán)境下，在特殊選定的激勵下，RI－Pro的行為表現(xiàn)和結(jié)果輸出。圖2為BGP的RI－Pro的場景模型。

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

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

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

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

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

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

(4)數(shù)據(jù)的環(huán)境變量類——RIB(Routing Information Base)、 RT(Routing Table)等。

2協(xié)議規(guī)范變異

協(xié)議規(guī)范本質(zhì)上來說是協(xié)議限定關(guān)系的描述文本。基于場景模型，重新表述RI－Pro后，元素與元素之間的制約關(guān)系δ被準(zhǔn)確嚴(yán)謹(jǐn)?shù)囟x和表示出來。筆者希望從這些制約關(guān)系δ出發(fā)，最終獲得健壯性測試所需要的矛盾制約關(guān)系δ′。本文使用協(xié)議規(guī)范變異的方法實現(xiàn)了這個轉(zhuǎn)換過程。

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

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

2．1場景單元變異

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

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

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

2．2表達(dá)式變異

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

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

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

3測試案例生成和實際測試結(jié)果

使用規(guī)范變異方法對RI－Pro進(jìn)行變異，筆者獲得了213個矛盾沖突關(guān)系。其中有97 個沖突關(guān)系在協(xié)議規(guī)范中已經(jīng)包含或者不能與正常限定關(guān)系相區(qū)分，有61個沖突關(guān)系是不可執(zhí)行、不可測試或重復(fù)的沖突關(guān)系，最終只有55個沖突關(guān)系可以用于構(gòu)造異常場景進(jìn)行健壯性測試。

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

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

4結(jié)束語

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

參考文獻(xiàn)：

［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.

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