重慶郵電學(xué)院碩士論文 摘要 通信協(xié)議測試是通過實(shí)驗(yàn)的方法發(fā)現(xiàn)通信協(xié)議實(shí)現(xiàn)在功能和性能方面的錯(cuò) 誤。由于各國都在開展第三代移動通信系統(tǒng)( 3 g ) 的研究，通信協(xié)議一致性測試 趨顯其在理論和現(xiàn)實(shí)上的重要性。通信協(xié)議的一致性測試采用較多的是f s m ( f i n i t es t a t em a c h i n e ，有限狀態(tài)機(jī)) 模型，但該模型只能刻畫協(xié)議的控制行為， 不包括協(xié)議的數(shù)據(jù)行為，具有很大的局限性。3 g 的測試文檔對非接入層采用的 一致性測試方法是分布式測試法，該方法要使用上、下兩個(gè)測試器，因此需要上 下測試器之間的協(xié)調(diào)過程。 本文的主要貢獻(xiàn)在于： 運(yùn)用c e f s m ( c o m m u n i c a t i o ne x t e n s e df s m ，通信擴(kuò)展有限狀態(tài)機(jī)) 模型，成功的對t d p r s 的l l c ( l o g i c a ll i n kc o n t r o l ，邏輯鏈路控 制) 模塊進(jìn)行了仿真。 同時(shí)用基于c e f s m 模型的算法，實(shí)現(xiàn)了l l c 模塊的一致性測試， 包括異步平衡模式的建立、釋放，證實(shí)和非證實(shí)數(shù)據(jù)的傳送，x i d 的協(xié)商等。 采用遠(yuǎn)程測試法，對3 g 測試文檔非接入層測試結(jié)構(gòu)進(jìn)行了簡化。 采用本文所述方法，實(shí)現(xiàn)了對t d p r s 終端2 、3 層的協(xié)議仿真和一致性測 試，糾正了協(xié)議開發(fā)中的錯(cuò)誤。同時(shí)，該方法對其他通信協(xié)議的仿真和測試有重 要的參考價(jià)值和實(shí)用意義。 關(guān)鍵詞： 第三代移動通信系統(tǒng)，t d p r s ，l l c 模塊，c e f s m 模型，協(xié)議一致性測試， 測試方法 重慶郵電學(xué)院碩士論文 a b s t r a c t t h ec o m m u n i c a t i o np r o t o c o lt e s tl st h ew a yt of i n do u tt h ee t r o r so ff u n c t i o n a n dp e r f o r m a n c eo fc o m m u n i c a t i o np r o t o c o li m p l e m e n t a t i o n u n t i ln o w , a l lc o u n t r i e s a l ec a r r y i n gt h r o u g ht h er e s e a r c ho nt h et h i r dg e n e r a t i o nm o b i l ec o m m u n i c a t i o n s y s t e m ( 3 g ) ，f o l l o w e db yt h ed i s c o v e r yo fi m p o r t a n c ei nt h es t u d yo fc o m m u n i c a t i o n p r o t o c o l c o n f o r m a n c et e s ti n t h e o r ya n dr e a l i z a t i o n c o m m t m i c a t i o np r o t o c o l c o n f o r m a n c et e s tm o s t l yu s e st h ef s m ( f i n i t es t a t em a c h i n e s ) t om o d e lr e a ls y s t e m s ， b u tt h e r ei sl i m i t a t i o ni nf s mt h a ti tc a no n l yd e p i c tt h ec o n t r o lb e h a v i o ro ft h e p r o t o c o l ，n o ti n c l u d et h ed a t ac o u n t e r p a r t i n3 g - t e s td o c u m e n t ，d i s t r i b u t e dt e s t m e t h o di su s e dt ot e s tt h ec o n f o r m a n c eo fn o n - a c c e s ss t r a t u m t h i sk i n do ft e s tn e e d s t w ot e s t e r s ，t h eu p p e ro n ea n dt h el o w e ro n e ，i m p l y i n gt h er e q u i r e m e n to fc o o r d i n a t e p r o c e d u r eb e t w e e nt h et w o t e s t e r s t h em a i nc o n t r i b u t i o n sm a d ei nt h i sp a p e ra r es u m m a r i z e da sf o l l o w s ： s u c c e s s f u l l ys i m u l a t e dt h el l c ( l o g i c a ll i n kc o n t r 0 1 ) m o d u l eo f t d p r sw i t hc e f s mm o d e l a tt h es a l l l et i m e ，c o n f o r m a n c et e s to fl l cm o d u l ei sr e a l i z e du s i n g a l g o r i t h mb a s e do nt h ec e f s mm o d e l ，i n c l u d i n gt h ee s t a b l i s h m e n ta n d r e l e a s eo fa b m ( a s y n c h r o n o u sb a l a n c e dm o d e ) ，a c k n o w l e d g e da n d u n a c k n o w l e d g e dd a t at r a n s f e r ；x i dn e g o t i a t i o n , e t c t h et e s ts t r u c t u r eo ft h en o n - a c c e s ss t r a t u mi n3 g _ t e s td o c u m e n ti s s i m p l i f i e db ym e a n so fr e m o t et e s t w ec o m p l e t et h ep r o t o c o ls i m u l a t i o na n dc o n f o r m a n c et e s ti nl a y e r2a n d3o f t d p r st e r m i n a lu s i n go u rp r o p o s e ds c h e m ei nt h i sp a p e r ，w h i c hr e c t i f i e st h eb u g so f t h ep r o t o c o li m p l e m e n t a t i o n t 1 1 i ss c h e m ei sa l s ov a l u a b l ef o rr e f e r e n c eo ru t i l i t yi n t h es i m u l a t i o na n dt e s to fo t h e rc o m m u n i c a t i o np r o t o c o l s k e y w o r d s ：t h et l ：l i l dg e n e r a t i o nm o b i l ec o m m u n i c a t i o ns y s t e m ，t d p r s ，l l c m o d u l e ，c e f s mm o d e l ，p r o t o c o lc o n f o r m a n c et e s t ，t e s tm e t h o d 重慶郵電學(xué)院碩士論文 1 1 論文背景 第一章緒論 在通信系統(tǒng)之間，為了使來自不同廠家的系統(tǒng)能夠成功地進(jìn)行通信，必須有 標(biāo)準(zhǔn)化的協(xié)議，它規(guī)定了通信系統(tǒng)上各部件之間進(jìn)行通信時(shí)應(yīng)遵守的規(guī)則。但標(biāo) 準(zhǔn)化的協(xié)議并不能確保通信的成功。這是因?yàn)橥ㄐ艆f(xié)議標(biāo)準(zhǔn)基本上是在 r f c ( r e q u e s tf o rc o m m e n t ) 中以自然語言描述，實(shí)現(xiàn)者對于協(xié)議的不同理解會導(dǎo) 致不同的協(xié)議實(shí)現(xiàn)，有時(shí)甚至?xí)清e(cuò)誤的實(shí)現(xiàn)。因此，我們需要一種有效方法對 協(xié)議實(shí)現(xiàn)進(jìn)行判別，這種方法便是“協(xié)議測試”( p r o t o c o lt e s t ) 。 測試是一個(gè)試圖通過驗(yàn)證的方法找出錯(cuò)誤的過程。隨著通信技術(shù)的發(fā)展，特 別是移動通信的迅猛發(fā)展，協(xié)議測試?yán)碚摵图夹g(shù)的研究越來越重要，已經(jīng)成為國 際上通信工程研究的熱點(diǎn)之一。協(xié)議測試?yán)碚撌菂f(xié)議工程學(xué)的一個(gè)重要分支。協(xié) 議測試是在軟件測試的基礎(chǔ)上發(fā)展起來的。根據(jù)對被測軟件的控制觀察方式，軟 件測試分為三種：白箱測試、黑箱測試和灰箱測試。協(xié)議測試是一種黑箱測試， 它依據(jù)協(xié)議標(biāo)準(zhǔn)來控制、觀察被測協(xié)議實(shí)現(xiàn)的外部行為，對被測協(xié)議實(shí)現(xiàn)進(jìn)行測 試。協(xié)議測試有三種類型的測試：一致性測試、互操作性測試和性能測試。一致 性測試是基礎(chǔ)，是通過觀察具體實(shí)現(xiàn)在不同的環(huán)境和條件下的反應(yīng)行為來驗(yàn)證協(xié) 議實(shí)現(xiàn)與相應(yīng)的協(xié)議標(biāo)準(zhǔn)是否一致。要保證不同的協(xié)議實(shí)現(xiàn)在實(shí)際網(wǎng)絡(luò)中能成功 的通訊，還需要檢測某一協(xié)議實(shí)現(xiàn)與其它系統(tǒng)之間的交互過程是否正常，這是互 操作性測試。另外還要對協(xié)議的性能進(jìn)行測試，如健壯性( r o b u s t n e s s ) 、吞吐量 等。大致說來，這些工作都是用一種形式化描述語言來描述協(xié)議，并使用一種生 成機(jī)制來自動生成對應(yīng)該協(xié)議的測試集，這些描述語言包括s d l 、l o t o s 、e s t e l l e 等。當(dāng)今，用戶對可靠性的要求越來越高，一致性測試和互操作性測試變得尤為 重要。因此，本人認(rèn)為協(xié)議測試也是一個(gè)重要研究領(lǐng)域。 現(xiàn)在移動通信發(fā)展越來越快，各國都在研究第三代移動通信 1 】【2 】。基于p 技 術(shù)的第四代移動通信( 蜂窩寬帶無線接入技術(shù)) 也早已被提上日程，如i t s 、 h a p s 。因此對移動通信軟件的測試也越來越關(guān)鍵。3 g 測試分為三個(gè)階段：物理 層參數(shù)測試、互操作性測試、現(xiàn)場性能測試。測試方法主要有單元測試、驗(yàn)收測 重慶郵電學(xué)院碩士論文 試、互操作性測試、穩(wěn)固性測試、系統(tǒng)測試、一致性測試、集成測試等。 0 s i 協(xié)議一致性測試方法和結(jié)構(gòu)規(guī)范是在1 9 8 7 年提出的，后又在1 9 9 4 年由 r i c h a r dj l i n na n dm o m i tu y a r 撰寫出版該書，已經(jīng)成功應(yīng)用在互連網(wǎng)協(xié)議如 h t l p 、s m t p ( 簡單郵件傳輸協(xié)議) 以及通信網(wǎng)絡(luò)a t m b i s d n 協(xié)議等。s d l 3 】 主要應(yīng)用在工業(yè)領(lǐng)域；l o t o s i 4 】主要用在復(fù)雜的分布式處理系統(tǒng)中進(jìn)行設(shè)計(jì)、 驗(yàn)證和證實(shí)；e s t e l l e 5 】主要用在實(shí)際生活系統(tǒng)中，著重于實(shí)現(xiàn)，而不是驗(yàn)證和設(shè) 計(jì)o o s t g ( o p t i m a lt e s ts e q u e n c eg e n e r a t i o n ，最佳測試序列生成) 問題是協(xié)議測 試的重要研究領(lǐng)域，也就是找出一個(gè)長度最小的測試序列。a h o 等人在1 9 8 8 年提出一個(gè)叫s u i o r c p t ( r i 瓜a i c h i n e s ep o s t m a nt o u r ) 算法，該算 法是在第一階段給每個(gè)狀態(tài)采用最小長度的u i o 序列，在第二階段找出一個(gè)鄉(xiāng) 村郵遞員旅行【6 1 。s h e n 等人在1 9 8 9 年提出一個(gè)叫m u i o r c p t 的算法，該算 法是通過在第一階段為每個(gè)狀態(tài)采用多個(gè)最小長度u i o 序列來達(dá)到對 s i o 瓜c p t 算法的改進(jìn)，序列長度可減少4 3 7 。這兩種算法都是采用非重疊 的方式來最小化測試序列長度。1 9 9 3 年r a y m o n d 等人提出基于重疊的多個(gè) u o 生成測試序列的算法。 本課題主要對通信協(xié)議一致性測試方法進(jìn)行研究及第三代移動通信標(biāo)準(zhǔn) t d s c d m a 的終端高層進(jìn)行協(xié)議測試方法的研究和測試。 1 2 測試發(fā)展過程 測試一般來說都分為硬件測試和軟件測試；軟件測試是使用為發(fā)現(xiàn)錯(cuò)誤所選 擇的輸入和狀態(tài)的組合而執(zhí)行代碼的過程。測試按測試范圍可以分為單元( 塒t ) 測試、集成( i n t e g a r t i o n ) 測試、系統(tǒng)( s y s t e m ) 測試。單元測試的范圍通常由一個(gè) 相對小的可執(zhí)行體組成；集成測試的范圍是軟件和硬件單元的一個(gè)完整系統(tǒng)或子 系統(tǒng)；系統(tǒng)測試的范圍是一個(gè)完全集成了的應(yīng)用。測試就其應(yīng)用領(lǐng)域又可以分為 電子組裝測試、芯片測試、聲學(xué)測試及幾何、力學(xué)、熱工中使用的測試技術(shù)等， 其中發(fā)展最快的要算通信領(lǐng)域的測試技術(shù)。 目前在電子組裝測試領(lǐng)域中使用的測試技術(shù)種類繁多，常用的有手工視覺檢 查 i ) 、在線測試( i c t ) 、自動光學(xué)測試( a o i ) 、自動x 射線測試( a x i ) 、功能測 2 重慶郵電學(xué)院碩士論文 試( f t ) 等。 1 2 1 通信測試儀表 通信領(lǐng)域測試發(fā)展較快的是通信測試儀表，通信測試儀表在通信產(chǎn)品研制、 生產(chǎn)和應(yīng)用的各個(gè)過程中，用于測試相關(guān)的通信器件、設(shè)備、系統(tǒng)、網(wǎng)絡(luò)的特性， 使之符合相關(guān)規(guī)范、標(biāo)準(zhǔn)的要求，以確保網(wǎng)絡(luò)和業(yè)務(wù)運(yùn)行的可靠和暢通。 通信測試儀表作為尖端的高技術(shù)產(chǎn)品，在很大程度上反映了一個(gè)國家的通信 技術(shù)水平。世界通信強(qiáng)國都具有很強(qiáng)的通信測試儀表研發(fā)能力，也具有較大的應(yīng) 用規(guī)模。 隨著光纖通信、移動通信和以為代表的網(wǎng)絡(luò)技術(shù)和應(yīng)用的飛速發(fā)展，其 相應(yīng)的測試技術(shù)也呈現(xiàn)高速發(fā)展的態(tài)勢，光纖通信儀表、移動通信儀表和網(wǎng)絡(luò)測 試儀表成為當(dāng)今通信測試儀表研制、開發(fā)和應(yīng)用熱點(diǎn)。 1 光纖通信測試儀表 光纖通信的發(fā)展始于8 0 年代初，是電信核心網(wǎng)和接入網(wǎng)的主要傳輸方式， 也是有線電視網(wǎng)、計(jì)算機(jī)數(shù)據(jù)網(wǎng)主干段的主要傳輸方式。近年來，光纖通信干線 傳輸容量越來越大，光纖接入向最終用戶越來越接近，應(yīng)用的覆蓋面也越來越廣。 因此，不斷有支持s d h 、d w d m 、光放大器的新的光纖通信測試儀表面世，滿 足光纖通信研發(fā)、生產(chǎn)、檢測等環(huán)節(jié)的測試要求?；镜墓鉁y試儀表，例如光源、 光功率計(jì)等，在測試精度、操作簡單性和智能化程度方面都得到了大幅度提高， 非常適用于工程和維護(hù)測試的需要，有力地促進(jìn)了光纖化發(fā)展。 2 移動通信測試儀表 在移動通信測試領(lǐng)域，伴隨著模擬移動通信的淘汰和數(shù)字移動通信的應(yīng)用普 及，數(shù)字化測試技術(shù)逐漸取代了模擬技術(shù)。g s m 系統(tǒng)和c d m a 系統(tǒng)測試在移動 通信的發(fā)展建設(shè)中產(chǎn)生了重要作用。由于移動通信發(fā)展迅速、潛力巨大，再過若 干年，移動通信用戶規(guī)模將超過固定網(wǎng)，因此移動通信測試儀表市場也隨之?dāng)U大。 另外移動通信技術(shù)新概念不斷提出，從2 g 到3 g ，以及中間的2 5 g 等，移動通 信新儀表也是層出不窮，甚至相關(guān)技術(shù)是否應(yīng)用和什么時(shí)候應(yīng)用還沒有確定，測 試儀表的廣告已先入為主，移動通信測試儀表市場的熱度可見一斑。 3 網(wǎng)絡(luò)測試儀表 重慶郵電學(xué)院碩士論文 以口為代表的網(wǎng)絡(luò)技術(shù)的發(fā)展速度前所未有，口網(wǎng)絡(luò)被認(rèn)為是三網(wǎng)融合的 最佳結(jié)合點(diǎn)，用于m 網(wǎng)絡(luò)互聯(lián)的設(shè)備越來越多，采用的技術(shù)也更加復(fù)雜。如何 設(shè)計(jì)符合客戶需求的網(wǎng)絡(luò)、如何在設(shè)備選型時(shí)比較各廠家設(shè)備的性能、如何在網(wǎng) 絡(luò)實(shí)際運(yùn)行之前判斷網(wǎng)絡(luò)是否符合設(shè)計(jì)的要求、如何在網(wǎng)絡(luò)運(yùn)行中發(fā)現(xiàn)網(wǎng)絡(luò)性能 瓶頸和故障原因等一系列問題就成為網(wǎng)絡(luò)運(yùn)營商和網(wǎng)絡(luò)用戶必須面對和解決的 問題。所有這一切都需要疋網(wǎng)絡(luò)測試儀表的應(yīng)用和口網(wǎng)絡(luò)測試技術(shù)的支持。 通信測試儀表與通信技術(shù)、計(jì)算機(jī)及軟件技術(shù)、網(wǎng)絡(luò)技術(shù)、集成技術(shù)的發(fā)展 息息相關(guān)。近些年來，通信測試儀表的技術(shù)走向主要表現(xiàn)為計(jì)算機(jī)化、綜合化、 智能化和網(wǎng)絡(luò)化。通信及通信測試儀表將相互促進(jìn)，共同快速發(fā)展。 1 2 2 移動通信測試技術(shù) 隨著通信技術(shù)的發(fā)展，發(fā)展迅速的移動通信測試技術(shù)具有如下新的特點(diǎn)： 1 、從技術(shù)層面看：移動通信技術(shù)經(jīng)歷了從模擬到數(shù)字技術(shù)的轉(zhuǎn)變。從窄帶 的數(shù)字技術(shù)( g s m 、c d m a ) 向?qū)拵?shù)字通信技術(shù)i m t 2 0 0 0 的發(fā)展，從單一語 言通信向以數(shù)據(jù)通信為主的移動互聯(lián)網(wǎng)、移動多媒體的發(fā)展。從硬件測試和低層 協(xié)議( 1 3 層協(xié)議) 測試為主向以軟件為核心和高層協(xié)議測試過渡。 2 、從測試方式層面看：移動通信設(shè)備制造商和網(wǎng)絡(luò)運(yùn)營商對測試儀器供應(yīng) 商的要求也正在經(jīng)歷從單臺儀器一多儀表組合測試系統(tǒng)一自動( 程控) 測試診斷系 統(tǒng)的過渡，從離線測試實(shí)時(shí)在線測試一實(shí)時(shí)測試診斷、校準(zhǔn)系統(tǒng)的過渡。 3 、從市場關(guān)系看：移動通信測試方案供應(yīng)商與移動通信設(shè)備制造商和系統(tǒng) 運(yùn)營商的關(guān)系也發(fā)生了性質(zhì)上的變化。由純粹的商業(yè)關(guān)系變成了一種合作伙伴關(guān) 系，即測試儀表設(shè)備測試系統(tǒng)測試服務(wù)。 1 2 3 第三代移動通信測試系統(tǒng) 第三代移動通信( 3 g ) 的測試可以分為三個(gè)階段：第一階段，移動設(shè)備基 本性能測試；第二階段，移動設(shè)備n 絡(luò)間互操作性測試；第三階段，移動現(xiàn)場 測試。 第一階段，物理層參數(shù)測試。移動設(shè)備的物理層性能參數(shù)。這一規(guī)范通過一 系列空中接nn 試來評估移動通信發(fā)射機(jī)和接收機(jī)的性能。這些測試通常是在利 4 重慶郵電學(xué)院碩士論文 用實(shí)驗(yàn)室設(shè)備搭建的有線測試環(huán)境中進(jìn)行的。可初步歸納出以下幾個(gè)關(guān)鍵測量項(xiàng) 目：鄰道功率l 匕( a d j a c e n tc h a n n e lp o w e rr a t i o ，a c p r ) 、接收信號編碼功率限 e c e i v e ds i g n a lc o d ep o w e r ，r s c p ) 、干擾信號編碼功率( i n t e r f e r e n c es i g n a lc o d e p o w e r ，i s c p ) 、塊誤碼率( b l o c ke r r o rr a t e ，b l e r ) 、位誤碼率( b i te r r o rr a t e ， b e r ) 、接收信號強(qiáng)度指示( r e c e i v e ds i g n a ls t r e n g t hi n d i c a t o r ，r s s i ) 、誤差向量值 ( e r r o rv e c t o rm a g n i t u d e ，e v m ) 、靈敏度測試( s e n s i t i v i t y ) 。 第二階段，互操作性。完成第一階段的測試后，移動設(shè)備要接受第二階段的 測試，這一階段的測試是通過一系列移動基站信號發(fā)送和呼叫處理測試來評估移 動設(shè)備的協(xié)議層性能。與第一階段測試類似，第二階段測試也是在有線環(huán)境中進(jìn) 行的。真正的第二階段測試是在配備有主要通信體系設(shè)備制造商產(chǎn)品的互操作性 i o 測試實(shí)驗(yàn)室中進(jìn)行的，測試由一系列通過實(shí)際系統(tǒng)設(shè)備產(chǎn)品進(jìn)行的試驗(yàn)構(gòu)成。 第三階段，現(xiàn)場性能測試。第一階段和第二階段的測試是在實(shí)驗(yàn)室中有線的 環(huán)境下對移動設(shè)備的物理層和協(xié)議層性能進(jìn)行驗(yàn)證，而第三階段測試的目標(biāo)則是 驗(yàn)證移動設(shè)備在真實(shí)環(huán)境中在這兩個(gè)層次上的性能。移動設(shè)備的制造商一般情況 下要與購買其產(chǎn)品的服務(wù)商合作進(jìn)行測試。這些測試在一組確定的行駛路徑上進(jìn) 行，要用到一系列呼叫處理操作。 1 3 論文安排 本論文共分為五章，第一章介紹了開展通信協(xié)議測試研究的意義、測試的發(fā) 展過程、本論文的主要工作和論文的組織結(jié)構(gòu)。第二章介紹了協(xié)議工程學(xué)、形式 化方法、協(xié)議測試?yán)碚?、協(xié)議一致性測試的基本概念和方法、協(xié)議測試通常采用 的數(shù)學(xué)模型( 有限狀態(tài)機(jī)理論) 和基于c e f s m 模型的測試?yán)詣由煞椒?。?三章論述基于e f s m 的開發(fā)工具s d l 和采用c e f s m 對3 g 雙模終端t d p r s 的 u c 的s d l 設(shè)計(jì)實(shí)現(xiàn)。第四章介紹一致性測試生成工具t t c n ，及采用基于 c e f s m 測試?yán)煞椒▽? g 雙模終端的t d p r s 的l l c 的測試。第五章總結(jié) 全文，并探討了進(jìn)一步的研究工作。 重慶郵電學(xué)院碩士論文 第二章通信協(xié)議測試?yán)碚撆c方法 2 1 形式化方法 通訊協(xié)議( c o m m u n i c a t i o np r o t o c 0 1 ) 就是用在通信系統(tǒng)中，將各個(gè)不同部 分連接起來的通信管理規(guī)則。為了使得來自不同廠家的系統(tǒng)能夠成功地進(jìn)行通 信，必須有標(biāo)準(zhǔn)化的協(xié)議。 協(xié)議工程( p r o t o c o le n g i n e e r i n g ) 的研究范圍包括協(xié)議綜合、協(xié)議說明、 協(xié)議證實(shí)與驗(yàn)證、協(xié)議轉(zhuǎn)換、性能分析、自動實(shí)現(xiàn)和協(xié)議測試( p r o t o c o lt e s t ) 。 在協(xié)議工程領(lǐng)域里，協(xié)議綜合是根據(jù)協(xié)議標(biāo)準(zhǔn)文本說明設(shè)計(jì)出正確的形式化協(xié)議 說明的過程；協(xié)議說明是指對協(xié)議標(biāo)準(zhǔn)文本的形式化說明；協(xié)議證實(shí)與驗(yàn)證主要 是對形式化協(xié)議說明的語法語義正確性的證實(shí)和驗(yàn)證；協(xié)議轉(zhuǎn)換主要研究如何 實(shí)現(xiàn)不同協(xié)議的進(jìn)程之間的互操作問題；性能分析是指根據(jù)已設(shè)計(jì)完成的協(xié)議說 明來評價(jià)其所具有的特性；自動實(shí)現(xiàn)是指由機(jī)器對形式化協(xié)議說明直接進(jìn)行編譯 處理，產(chǎn)生協(xié)議實(shí)現(xiàn)的主體部分；協(xié)議測試是通過實(shí)驗(yàn)的方法發(fā)現(xiàn)協(xié)議實(shí)現(xiàn)在功 能和性能方面的錯(cuò)誤。 形式化方法可以分為兩類：數(shù)學(xué)邏輯法( m a t h e m a t i c a ll o g i cf o r m a li s m ) 和描述法( d e s c r i p t i o nf o r m a l i s m ) 。數(shù)學(xué)邏輯法提供了形式化的語法，嚴(yán)謹(jǐn)?shù)?數(shù)學(xué)語義和一組推導(dǎo)規(guī)則。有限狀態(tài)機(jī)f s m ( f i n t es t a t em a c h i n e ) 屬于這種 方法。描述法也有形式化的語法和數(shù)學(xué)語義。與邏輯法不同的是，描述法不是為 形式化操作而特別設(shè)計(jì)的，所以它沒有推導(dǎo)規(guī)則。這類方法的一個(gè)例子是抽象語 法表示法a s n 1 ( a b s t r a c ts y n t a xn o t a t i o no n e ) 。它雖然具有形式化的語法， 但并沒有推導(dǎo)規(guī)則。 2 2 一致性測試 2 2 1 一致性測試概念 一致性測試是一種“功能測試，它依據(jù)一個(gè)協(xié)議的描述對協(xié)議的某個(gè)實(shí)現(xiàn) 6 重慶郵電學(xué)院碩士論文 進(jìn)行測試，判別一個(gè)協(xié)議的實(shí)現(xiàn)與所對應(yīng)的協(xié)議標(biāo)準(zhǔn)是否相一致。一致性評價(jià)過 程是評估某實(shí)現(xiàn)或系統(tǒng)與一個(gè)或多個(gè)i t u - t 建議或國際標(biāo)準(zhǔn)相一致的所有一致 性測試活動的全過程。它分三個(gè)階段：測試準(zhǔn)備、測試操作、測試執(zhí)行。圖2 1 給出了協(xié)議一致性測試的過程框圖口兒引。 2 2 2 測試生成技術(shù) 圖2 1 協(xié)議一致性測試的過程框圖 測試生成即測試準(zhǔn)備，是協(xié)議一致性測試的第一步。測試生成的目的是從協(xié) 議描述中生成獨(dú)立于協(xié)議實(shí)現(xiàn)的，用嚴(yán)格的測試表示語言描述的抽象測試集。測 試集自動生成依賴于被測協(xié)議的形式化描述，其過程大致可以分為兩步：首先， 根據(jù)協(xié)議標(biāo)準(zhǔn)文本給出協(xié)議的形式化描述；第二步，采用一定的測試集自動生成 算法產(chǎn)生出抽象測試集。測試集自動生成技術(shù)有很多算法，下面著重對基于有限 狀態(tài)機(jī)f s m 的測試集生成方法進(jìn)行介紹。 基于有限狀態(tài)機(jī)f s m 的測試集自動生成方法可以分為以下幾種策略：變遷 遍歷、t - 方法、u 方法、d 方法、w 二方法【9 】 1 0 i 等。 在變遷遍歷方法中，經(jīng)常使用中國郵遞員算法或鄉(xiāng)村中國郵遞員算法來找到 一條遍歷路徑。中國郵遞員問題是由我國數(shù)學(xué)家管梅谷教授首先提出的。設(shè)郵遞 員從郵局出發(fā)，遍歷他所管轄的每一條街道，將信件送到后返回郵局，要求路徑 最短。用圖論的術(shù)語描述就是從一個(gè)強(qiáng)連通的有向圖里找一個(gè)代價(jià)最小的路徑， 7 重慶郵電學(xué)院碩士論文 該路徑是包括每條邊至少一次的回路。對于所有的有限狀態(tài)機(jī)f s m 都存在著郵 遞員遍歷路徑，此路徑對f s m 中的各個(gè)變遷至少訪問一次，郵遞員算法很容易 在計(jì)算機(jī)上實(shí)現(xiàn)，變遷遍歷法并不能檢測出f s m 的輸入輸出序列中的所有錯(cuò) 誤。 t - 方法假定圖是強(qiáng)連通的；完全規(guī)定的，也就是任一個(gè)狀態(tài)對所有的輸入均 有變遷；最小的，也就是不能再化簡的圖。該方法是對任一個(gè)隨機(jī)輸入，直到把 所有的變遷遍歷一次為止，然后用化簡的方法把環(huán)去掉。例圖2 2 的有限狀態(tài)機(jī) 有五個(gè)狀態(tài)：0 、1 、2 、3 、4 ，0 為初始狀態(tài)，輸入是a 、b ，輸出0 、1 。t - 方法 的測試序列為： bababa a a aaa ab b o03340342l4212 u - 方法為每個(gè)狀態(tài)產(chǎn)生一個(gè)唯一的輸入輸出序列( u o 序列) ，用來識別該 狀態(tài)，每個(gè)狀態(tài)的u i o 序列不唯一。圖2 2 的f s m 的u i o 序列如表2 - 1 所示， 入是空的輸出。例如要測試從s i 到s j ，r 為復(fù)位，要先生成每個(gè)狀態(tài)的u i o ， 然后用r ，使?fàn)顟B(tài)機(jī)f s m 到達(dá)初始狀態(tài)s o ；找一個(gè)最短的從s 0 到s i 的路徑，連 接上s i 到s j 的變遷以及s j 的u i o 序列，就是生成的測試序列。 圖2 2u - 方法、d - 方法、w - 方法舉例 表2 - 1f s m 的u i o 序列 狀態(tài) u i o 0b 入 1 a 1a 1 2 b o 3 b 1b 1 4 a 1a o 重慶郵電學(xué)院碩士論文 圖2 2 的f s m 的u 一方法的測試序列為： r a a a a a a r a a a a b b r a a a b b b r a a a a r a a b b ( 2 - l - 2 - 3 4 ，0 ) 。 表2 2輸入d s - 序列船后每個(gè)狀態(tài)的輸出 狀態(tài)輸出 0 入入 11 0 20 1 31 1 41 入 d 一方法是用d s 序列驗(yàn)證尾狀態(tài)，此方法依據(jù)輸出序列識別狀態(tài)；d s 序列 ( d i s t i n g u i s h i n gs e q u e n c e ) 是輸入序列，對不同的開始狀態(tài)，輸出是不同的；因此 可以用輸出來判斷當(dāng)前所處的狀態(tài)。圖2 2 的f s m 的d s 序列為b b ，對每個(gè)狀 態(tài)輸入b b 后的輸出如表2 2 所示。d 一方法跟u 一方法有點(diǎn)象，不過是把末狀態(tài) 的u o 序列換為d s 序列而已。圖2 2 的f s m 的d 方法的測試序列為： r a a 從b b r a a 從b b b r k 4 a b b b b r 從b b r 從b b b ( 2 一l 一2 3 4 一o ) 。 w _ 方法在識別變遷尾狀態(tài)時(shí)使用了特征集w ，一個(gè)狀態(tài)的特征集中往往會 有多個(gè)特征序列。特征集是一些輸入集合，用在不同的狀態(tài)上，產(chǎn)生的最后輸出 是不相同的。圖2 2 的f s m 的w 集合為為 a ，a a ，b ，使用w 集合后的f s m 輸出如表2 3 所示。w 方法先構(gòu)造w 一集合，跟u - 方法類似，不過在末狀態(tài)用 w 集合換掉u i o 一序列。圖2 2 的w 方法測試序列為： r a a a a a a a b r 從從b a a a b r a a a b b a a a b r a a a a a b r a a b a a a b ( 2 - - 1 - 2 3 4 - 一0 ) 表2 - 3f s m 使用w - 集合后的每個(gè)狀態(tài)輸出 狀態(tài)a a ab oo0 入 1l1l 2o10 301l 4 lo1 四種方法中，u 方法、d 方法、w 二方法的一致性測試錯(cuò)誤覆蓋比t - 方法的 一致性測試好，因?yàn)榍叭叨紝δ顟B(tài)和邊測試，分別采用u i o 序列、d s 序列 和w - 序列；后面的t - 方法不對狀態(tài)進(jìn)行檢查，只能檢查協(xié)議機(jī)的哪些變遷存在， 9 重慶郵電學(xué)院碩士論文 哪些變遷不存在，并不能檢測出f s m 的輸入輸出序列中的所有錯(cuò)誤；與其他三 種方法比較，t - 方法的容錯(cuò)最差，不能檢查狀態(tài)錯(cuò)誤，生成的測試序列最短；u - 方法相對來講較易于實(shí)現(xiàn)，而且它所生成的測試?yán)L度較短；對有的狀態(tài)機(jī)來說 不一定有d s 序列：、肌方法最復(fù)雜，生成的測試?yán)铋L。唯一輸入輸出序列( u i o ) 顯然優(yōu)于有區(qū)別的序列( d s 序列) 和特征序列( w - 序列) ，因此廣泛采用u i o 來進(jìn)行測試序列的生成。 2 3 有限狀態(tài)機(jī)理論 i n 、- it 一1 1 i f l l 一、一，一、一，。一、一， m r ， l r ， 圖2 3信號轉(zhuǎn)換器 考察上圖2 3 的信號轉(zhuǎn)換器，假設(shè)機(jī)器m 在時(shí)間t = t o ，t l ，t 2 ，工作，其中 初始時(shí)間t o 及時(shí)間間隔x t i - - - t i - t i 1 都是任意的。為了簡化起見，常把它們表示為 t = 0 ，1 ，2 ，。在t = 0 時(shí)，將已知的初始條件作為初值，在以后每一瞬間t ，通 過輸入信道，機(jī)器m 收到一個(gè)輸入信號i ( t ) ，它就產(chǎn)生一個(gè)輸出信號o ( t ) ，通過 輸出信道輸出。提供給機(jī)器的一串輸入信號i ( 1 ) ，i ( 2 ) i ( t ) 稱為一個(gè)激勵(lì)，所產(chǎn) 生的輸出符號串稱為m 對此激勵(lì)的響應(yīng)。 所有輸入符號組成的集合稱為輸入符號集，記為i ，所有輸出符號組成的集 合稱為輸出符號集，記為o ?，F(xiàn)實(shí)世界中的機(jī)器都可以認(rèn)為由有限個(gè)部件組成， 且每個(gè)部件都有有限個(gè)狀態(tài)。假設(shè)機(jī)器m 由n 個(gè)部件組成，s ( j ( t ) 表示第j 個(gè)部 件在瞬間t 的狀態(tài)，那么在時(shí)間t ，m 的狀態(tài)是一個(gè)n 有序組 故m 總狀態(tài)的最大可能數(shù)是所有部件狀態(tài)數(shù)的積。若每一部件的狀態(tài)數(shù)不 超過k ，則m 的狀態(tài)數(shù)不超過k n 。用s ( t ) 表示m 在時(shí)間t 的狀態(tài)，即s ( t ) = ，所有不同的s ( t ) 組成的集合稱為狀態(tài)集，記作s 。機(jī)器m 在t = 0 時(shí)所處的狀態(tài)稱為初始狀態(tài)，記作s o ，即s l _ s ( 0 ) 。機(jī)器m 在接收到輸入信號 l o 重慶郵電學(xué)院碩士論文 s ( t ) 時(shí)，它將產(chǎn)生一個(gè)輸出o ( t ) ，同時(shí)，狀態(tài)s ( t 1 ) 轉(zhuǎn)換到s ( t ) ，o ( t ) 和s ( t ) 不僅與i ( t ) 有關(guān)，而且與機(jī)器在前一瞬間的狀態(tài)s ( t 1 ) 有關(guān)。因此存在一個(gè)函數(shù)6 ，用它來描 述機(jī)器的狀態(tài)： s ( t ) - - 6 ( s ( t - 1 ) ，i ( t ) ) ，份= 1 6 稱為狀態(tài)轉(zhuǎn)換函數(shù)，它的定義域是狀態(tài)集s 與輸入符號集i 的笛卡爾積，值 域是狀態(tài)集合的子集，即： 6 ：s x i s 還有一個(gè)函數(shù)用它來描述機(jī)器的輸出： o ( t ) = 九( o ( t - 1 ) ，i ( t ) ) ，t = l 它稱為輸出函數(shù)，定義域也是s x i ，值域是輸出集合0 ，即： 九：s x i - - 0 狀態(tài)數(shù)有限的機(jī)器稱為有限狀態(tài)機(jī)f s m ( f i n i t es t a t em a c h i n e s ) b h 1 2 】【13 1 ，描 述狀態(tài)機(jī)可以采用狀態(tài)圖。如果遷移函數(shù)6 和輸出函數(shù)九定義于所有的狀態(tài)輸入組 合，我們稱這種有限狀態(tài)機(jī)是完全描述的( 或完全定義的) 。狀態(tài)圖是一個(gè)有向 圖，其中每一個(gè)結(jié)點(diǎn)表示機(jī)器的一個(gè)狀態(tài)，每一個(gè)有向弧指出從一個(gè)狀態(tài)到另一 個(gè)狀態(tài)的轉(zhuǎn)換，此有向弧上加以起始標(biāo)記洳，其中i 、0 分別表示相應(yīng)的輸入符 號和輸出符號，對于初態(tài)s o ，用一個(gè)指向它的箭頭來標(biāo)明，如圖2 4 。 圖2 4狀態(tài)圖 根據(jù)應(yīng)用的需要，人們對有限狀態(tài)機(jī)作不同的約束和擴(kuò)展，產(chǎn)生不同的狀態(tài) 機(jī)模型，常用的為有限狀態(tài)機(jī)模型f s m 、擴(kuò)展有限狀態(tài)機(jī)e f s m ( e x t e n d e df s m ) 、 通信有限狀態(tài)機(jī)c f s m ( c o m m u n i c a t i n gf i n i t es t a t em a c h i n e s ) 、通信擴(kuò)展有限狀 態(tài)機(jī)c e f s m ( c o m m u n i c a t i n ge x t e n d e df i n i t es t a t em a c h i n e s ) 1 4 】【1 5 】【1 6 】【17 1 。 一個(gè)有限狀態(tài)機(jī)f s m 是一個(gè)6 元組。f 司，o ，s ，s o ，6 ，九 ，每個(gè)元素 的含義說明如下： i 是輸入符號集，為一個(gè)有限集合； 重慶郵電學(xué)院碩士論文 o 是輸出符號集，為一個(gè)有限集合： s 是內(nèi)部狀態(tài)集，為個(gè)有限集合； s o s ，是初始狀態(tài)： 6 ：sx i s ，遷移函數(shù)( 也叫做次態(tài)函數(shù)) ； 九：sxi 專o ，輸出函數(shù)。 遷移函數(shù)和輸出函數(shù)一起刻畫f s m 的行為。 例如圖2 2 的f s m ，輸入i - - a ，b ，輸出o = o ，1 ) ，狀態(tài)s = 0 ，1 ，2 ，3 ， 4 ) ，初始狀態(tài)s o = o ) ，狀態(tài)跳變函數(shù)和輸出函數(shù)分別如表2 4 和表2 5 所示。 表2 - 4 狀態(tài)跳變函數(shù)6 表2 5 輸出函數(shù)九 基于f s m 的測試序列生成方法一般分為兩個(gè)階段： 為每個(gè)狀態(tài)確定和導(dǎo)出一些特定的輸入輸出序列( i os e q u e n c e ) ，狀 態(tài)由s i ( s t a t ei d e n t i f i c a t i o n ) 來表示確定和區(qū)分。 把子測試序列連接起來，生成測試序列。 有限狀態(tài)機(jī)f s m 模型主要用在模擬時(shí)序電路、程序的語義分析、模式匹配、 通信協(xié)議等方面。f s m 不能很好描述大的復(fù)雜系統(tǒng)，缺點(diǎn)在于兩方面：不能很 好的描述變量操作，不能模仿任意數(shù)值的轉(zhuǎn)變能力，也就是它的缺點(diǎn)是f s m 固 有的順序性和不分級的平面性?；趂 s m 模型的測試方法主要針對被測實(shí)現(xiàn)的 1 2 重慶郵電學(xué)院碩士論文 控制部分進(jìn)行的，這種測試可以發(fā)現(xiàn)變遷錯(cuò)誤和傳輸錯(cuò)誤。但一個(gè)系統(tǒng)通常有兩 部分組成，一個(gè)是控制部分，還有一個(gè)是數(shù)據(jù)部分，采用e f s m 模型能較好的實(shí) 現(xiàn)對這類系統(tǒng)的描述。 f s m af s m b 邊2 到3 的測 試序列 r ( a x ) b y ( b z ) f s m a x b 邊2 到3 的測 試序列 r ( c a ) y u ( c w ) r ( c aa x ) b y y ub zc w 圖2 5 計(jì)算【2 ，2 1 到【3 。3 】的測試序列 對控制流部分測試采用的傳統(tǒng)方法是t - 方法、u 方法、d 方法、w 二方法， 這也是f s m 模型采用的方法；對數(shù)據(jù)部分測試是采用數(shù)據(jù)流圖。數(shù)據(jù)流圖是一 個(gè)有向圖，結(jié)點(diǎn)表示程序的功能單元，邊代表數(shù)據(jù)對象流。功能單元可以是一個(gè) 狀態(tài)、變遷、過程或程序。通過測試所有的輸入變量的值來完全描畫系統(tǒng)，測試 系統(tǒng)的數(shù)據(jù)部分，但是要對輸入變量的所有可能的取值進(jìn)行測試是不現(xiàn)實(shí)的，通 重慶郵電學(xué)院碩士論文 常都是按照一定的條件來選擇輸入變量的一個(gè)子集進(jìn)行測試，也就是只對一部分 數(shù)據(jù)行為進(jìn)行測試。對e f s m 的測試同時(shí)要考慮數(shù)據(jù)流和控制流部分，因此要比 單純的對f s m 的測試復(fù)雜，采用的方法有上下文相關(guān)依賴的唯一序列c i u s ( c o n t e x ti n d e p e n d e n tu n i q u es e q u e n c e ) ( c i u s 比傳統(tǒng)的控制特征序列d s - 序列、 u i o 序列、w 序列的控制流覆蓋好) 或者把e f s m 分為數(shù)據(jù)流圖d f g 和控制流 圖c f g 來測試等。 f s m 一般是描述比較簡單的系統(tǒng)，有時(shí)候許多通信協(xié)議規(guī)范需要用通信f s m 來描述，因此就有了c f s m 。對c f s m 的測試有兩種方式，一種方法是先作出狀 態(tài)機(jī)a 和狀態(tài)機(jī)b 的測試?yán)齮 1 、t 2 ，然后將t 1 和t 2 連接【1 8 】，例圖2 5 。另一 個(gè)方法是對狀態(tài)機(jī)a 和狀態(tài)機(jī)b 先做向量積，生成新的狀態(tài)機(jī)在用u - 方法來生 成測試?yán)?e f s m 模型不能描述系統(tǒng)內(nèi)部的依賴關(guān)系，有時(shí)候系統(tǒng)大的話，要考慮系統(tǒng) 內(nèi)部的通信；而c f s m 沒有考慮系統(tǒng)的數(shù)據(jù)行為部分，因此要描述這類系統(tǒng)， 就要采用c e f s m 模型。 2 4 基于c e f s m 模型的測試方法 通信擴(kuò)展有限狀態(tài)機(jī)c e f s m ( c o m m u n i c a t i n ge x t e n d e df i n i t es t a t em a c h i n e s ) 是一個(gè)二元組，c e f s m = ) e f s m 是一個(gè)擴(kuò)展有限狀態(tài)機(jī)的集合； ) , c h a n n e l 是信道的集合； 擴(kuò)展有限狀態(tài)機(jī)e f s m 定義類似與上述2 5 的定義。每個(gè)信道有三個(gè)元素， 源設(shè)備、目的設(shè)備和可以通過該信道傳送的信號列表。 對一個(gè)軟件系統(tǒng)來說，測試?yán)淖詣由墒潜容^耗費(fèi)時(shí)間和重要的。目前有 兩種生成測試?yán)姆椒ǎ阂粋€(gè)是基于規(guī)范的測試?yán)煞椒?，另外一個(gè)是基于代 碼的測試?yán)煞椒āＧ罢呤歉鶕?jù)規(guī)范，生成測試?yán)?；而后者必須在代碼完成后 再做測試?yán)?。?dāng)然基于規(guī)范的測試?yán)煞椒ň哂泻艽蟮膬?yōu)越性，一是它可以獨(dú) 立于規(guī)范的實(shí)現(xiàn)；二是可以提前發(fā)現(xiàn)錯(cuò)誤，代價(jià)低；三是它適于做系統(tǒng)級測試， 而且可以在代碼實(shí)現(xiàn)之前做出測試?yán)?。因此本文論述的c e f s m 是基于規(guī)范的測 試?yán)杉夹g(shù)。 1 4 重慶郵電學(xué)院碩士論文 基于規(guī)范的測試?yán)詣由杉夹g(shù)的焦點(diǎn)在于采用的測試?yán)詣由赡Ｐ?，?兩類模型：數(shù)據(jù)和行為。采用數(shù)據(jù)模型的是t e s t e r m a s t e r 和a t e g ，采用行為模 型的是使用統(tǒng)一建模語言u m l 或者s d l 1 9 】【2 0 】【2 l 】【2 2 1 。這些模型都要求為生成測 試?yán)⑿碌哪Ｐ?，這就增加了測試?yán)傻膹?fù)雜度；同時(shí)它們都要求覆蓋所 有的狀態(tài)空間；另外對實(shí)時(shí)系統(tǒng)不能很好的處理。 一般的對c e f s m 的測試，一種方法是把c e f s m 分為幾個(gè)單獨(dú)的e f s m ， e f s m 還可以轉(zhuǎn)變?yōu)閒 s m ，然后分別進(jìn)行測試。對f s m 的測試，是采用u - 方法， 首先把規(guī)范描述為f s m ；然后把f s m 轉(zhuǎn)變?yōu)橛邢驁D，狀態(tài)代表圖的頂點(diǎn)，邊代 表變遷，也就是輸入輸出對，從任意一個(gè)頂點(diǎn)s i 到另一個(gè)頂點(diǎn)s j 的測試( 也就 是從一個(gè)狀態(tài)s i 到另一個(gè)狀態(tài)s j 的測試) ，就是鄉(xiāng)村郵遞員問題。這種方法會 遇到狀態(tài)爆炸( e x p l o s i o n ) 問題，因此有時(shí)候難以實(shí)現(xiàn)。另外一種方法是采用向 量積的方式，有兩種向量積方式【l 引，一個(gè)是對狀態(tài)機(jī)a 和狀態(tài)機(jī)b 先做向量積， 生成新的狀態(tài)機(jī)再用u 方法來生成測試?yán)?；另一個(gè)是先作出狀態(tài)機(jī)a 和狀態(tài)機(jī) b 的測試?yán)齮 1 、t 2 ，然后做t 1 和t 2 連接。上述兩種方法都要求為新的測試目 的重新生成新的狀態(tài)機(jī)模型，都存在一定的局限性。 本文論述的c e f s m 1 6 】不需要為生成測試?yán)康亩匦陆⒛Ｐ?，它使用現(xiàn) 有系統(tǒng)的模型，包括數(shù)據(jù)和行為來生成測試?yán)Ｊ褂胒 s m 表示模型的行為和事 件，f s m 的擴(kuò)展變量表示模型數(shù)據(jù)，交互信道表示模型的通信，因此該方法是 數(shù)據(jù)、行為和通信規(guī)范三者的結(jié)合。c e f s m 解決了分支覆蓋問題，包括行為判 決覆蓋和跟數(shù)據(jù)相關(guān)的決策覆蓋。這種測試?yán)煞椒ǖ男阅茉u價(jià)是用基于代碼 的分支覆蓋語言s d l ，而不是通常的c 、c + + 、j a v a 等編程語言。該方法采用 假定的優(yōu)先級和支配分析法來高效生成測試?yán)?，?jīng)過一個(gè)測試遍歷后重新修改各 個(gè)節(jié)點(diǎn)的權(quán)值，從而減少生成測試?yán)臄?shù)目，減少了維護(hù)測試?yán)蛨?zhí)行測試?yán)?代價(jià)，重復(fù)該過程直到所有的節(jié)點(diǎn)至少遍歷一次。 例圖2 6 要遍歷結(jié)點(diǎn)8 ，就要經(jīng)過結(jié)點(diǎn)1 、2 、3 、4 ( 該測試?yán)秊閠 1 ) ，也就 是結(jié)點(diǎn)8 被結(jié)點(diǎn)1 、2 、4 支配；只要對結(jié)點(diǎn)8 做了測試，結(jié)點(diǎn)2 就被遍歷過了， 所以說結(jié)點(diǎn)8 的權(quán)值( 3 ) 高于結(jié)點(diǎn)2 的權(quán)值( 1 ) ，結(jié)點(diǎn)8 的優(yōu)先級高于結(jié)點(diǎn)2 。 如果要測試經(jīng)過結(jié)點(diǎn)6 的遍歷，要經(jīng)過結(jié)點(diǎn)1 、2 ( 該測試?yán)秊閠 2 ) ，結(jié)點(diǎn)6 被結(jié) 點(diǎn)1 、2 支配；由于結(jié)點(diǎn)1 、2 已經(jīng)在測試?yán)齮 l 中遍歷過，所以新增加的結(jié)點(diǎn)是 重慶郵電學(xué)院碩士論文 6 ，因此在經(jīng)過t 1 遍歷后，結(jié)點(diǎn)6 和結(jié)點(diǎn)3 有相同的權(quán)值( 1 ) ；也就是在經(jīng)過 t 1 后，覆蓋結(jié)點(diǎn)6 的測試?yán)透采w結(jié)點(diǎn)3 的測試?yán)邢嗤膬?yōu)先級。 圖2 6優(yōu)先級、支配、權(quán)值的修改舉例 在按最大覆蓋優(yōu)先級較高的方法選擇了測試?yán)?，采用后向跟蹤策略把測試 遍歷映射到結(jié)點(diǎn)集，如t 1 的結(jié)點(diǎn)是4 、2 、1 ，依次倒推；然后再用前向檢查的 方法來驗(yàn)證該測試遍歷，前向驗(yàn)證有三種情況，一是所需要的外部輸入或者變量 初始化；二是需要的內(nèi)部信號；三是發(fā)向環(huán)境的外部信號。 c e f s m 有四個(gè)主要特征：采用已經(jīng)有的系統(tǒng)規(guī)范模型，該模型包括數(shù)據(jù)和 行為信息；每生成一個(gè)測試?yán)笾匦掠?jì)算所有未被覆蓋結(jié)點(diǎn)的權(quán)值；采用后向跟 蹤來構(gòu)造遍歷路徑；采用前向驗(yàn)證把遍歷路徑轉(zhuǎn)變?yōu)闇y試?yán)?。具體的操作方法如 下：1 采用s d l 用形式化方法描述規(guī)范；2 生成流圖；3 按優(yōu)先級、支配的方 法生成最大分支覆蓋；4 每生成一個(gè)覆蓋后重新計(jì)算所有沒有被覆蓋的結(jié)點(diǎn)的權(quán) 值；5 采用后向跟蹤的方法( 若結(jié)點(diǎn)不唯一，則采用深度優(yōu)先搜索算法) 構(gòu)造變 遷路徑，該路徑覆蓋了有最大權(quán)值的分支；6 重復(fù)3 、4 、5 直到所有的結(jié)點(diǎn)至少 被遍歷一次；7 把變遷路徑轉(zhuǎn)變?yōu)闇y試?yán)?，采用前向?yàn)證，生成帶有外部輸入、 輸出和任務(wù)的測試步。 2 5 本章小結(jié) 本章主要介紹了協(xié)議一致性測試方法、測試?yán)煞椒ǎ缱冞w遍歷、t