蒲卿路,王月波, 劉 濤,孫 云,李繼秀

(西南電子技術(shù)研究所，成都 610036)

0 引言

目前，隨著科技的進(jìn)步，軟件的發(fā)展。各式各樣的軟件融入人們的日常生活中。購物，游戲，銀行轉(zhuǎn)賬等活動都成為日常生活的一部分[1]。優(yōu)秀的軟件能夠吸引大量的客戶，為公司取得收益。同時在大量軟件出現(xiàn)的今天，也對軟件本身提出更高的安全性和穩(wěn)定性。一款軟件在上線前夕，需要進(jìn)行大量的測試，以便提升軟件的質(zhì)量[2-3]。因此，對軟件測試的方法，測試工具的研究為軟件測試的質(zhì)量帶來了保證[4]。如何快速、高效地進(jìn)行測試也是每一個測試人員及開發(fā)人員都必須重視的問題[5-7]。

目前大部分的測試用例都是由測試人員或者開發(fā)人員手工錄入。針對同一類型的測試用例，其區(qū)別僅在于數(shù)據(jù)取值的不同。大量并且重復(fù)的測試用例設(shè)計，導(dǎo)致測試用例質(zhì)量不高，不能夠發(fā)現(xiàn)軟件深層次的異常。同時，測試對軟件開發(fā)的介入，往往需要有一定的代碼基礎(chǔ)才能開展。在軟件需求驗證階段，傳統(tǒng)的測試則不具有可行性。因此，有研究人員提出了基于模型的測試、優(yōu)化和指導(dǎo)測試工作以及加速軟件開發(fā)過程。

基于模型的測試，就是使用工作流程圖、判定表、狀態(tài)轉(zhuǎn)換圖描述出被測對象的實現(xiàn)邏輯。通過對上述模型進(jìn)行路徑的遍歷，即可得出測試點。如果測試人員按照依據(jù)文檔，建立模型時，發(fā)現(xiàn)模型不完整，邏輯混亂。也就代表軟件的設(shè)計邏輯出現(xiàn)錯誤。使得軟件開發(fā)過程與測試活動相結(jié)合[8]。在軟件開發(fā)的后期，模型中各個路徑的條件逐漸完整，使用參數(shù)定義，以及取值明確時，就可以在路徑遍歷的基礎(chǔ)上，加入邊界值與等價類的思想[9]，將參數(shù)實例化，從而得出一個完整的測試用例。

目前測試行業(yè)主要存在以下問題：

1)測試與開發(fā)脫節(jié)。測試的開展需要有一定的代碼基礎(chǔ)才能進(jìn)行，因此測試被至于軟件開發(fā)周期的后半段。同時，大部分軟件開發(fā)更新過程較快，測試人員開展測試工作時，被測對象的功能與測試需求已經(jīng)嚴(yán)重不符。測試工作難以開展。

2)測試用例需要手動錄入，如果一個測試項包含多個參數(shù)，測試用例的設(shè)計則需要對每一個參數(shù)的取值情況進(jìn)行全組合。在沒有用例自動生成工具的幫助下，測試人員的工作效率極為低下。

3)開展測試任務(wù)時，通常由多個測試人員同時開展測試分析與設(shè)計，容易造成測試數(shù)據(jù)的混亂。測試數(shù)據(jù)的可追蹤性和恢復(fù)性也沒有保障。

針對以上問題，本文基于模型測試，實現(xiàn)了測試用例的自動生成。有效地解決了上述軟件測試中的種種問題，提高了測試人員的工作效率與被測軟件的質(zhì)量。本文后續(xù)內(nèi)容主要對各個典型模型的生成測試用例的算法與數(shù)據(jù)結(jié)構(gòu)的設(shè)計進(jìn)行講述。

1 測試需求模型構(gòu)建

測試需求分析是進(jìn)行軟件測試的前提和基礎(chǔ)。測試需求是指依據(jù)軟件需求，根據(jù)測試目標(biāo)而確定的被測軟件的測試屬性。測試屬性是指軟件測試人員結(jié)合測試意圖和被測軟件本身的特點分析得到的測試對象、范圍和內(nèi)容等要素。測試意圖是通過軟件的測試類型加以實現(xiàn)的，從不同角度驗證軟件的質(zhì)量屬性[10]。系統(tǒng)測試需求建模是指依據(jù)軟件需求規(guī)格說明，從測試的角度出發(fā)，確定被測軟件的測試屬性，明確被測系統(tǒng)的輸入輸出及其映射關(guān)系[11]，建立被測系統(tǒng)的工作流程，判定表，狀態(tài)轉(zhuǎn)換等模型[12-13]。

如圖1所示，傳統(tǒng)的系統(tǒng)開發(fā)由一系列的文檔構(gòu)成，因此需要分析被測軟件的相關(guān)文檔，明確軟件的測試屬性并劃分測試項[14]。軟件文檔作為軟件的主要產(chǎn)品之一，為軟件測試提供了主要的信息。從需求文檔中可以提煉出系統(tǒng)的組成、功能、性能，軟件的運(yùn)行狀態(tài)、運(yùn)行時序，接口信息以及顯性和隱性的軟件質(zhì)量屬性等。依據(jù)軟件功能進(jìn)行測試項的劃分，確定測試類型，并創(chuàng)建相對應(yīng)的模型。

圖1 條件解析后生成的二叉樹

2 基于工作流程圖的測試用例生成方法

2.1 模型的創(chuàng)建

首先，將流程圖中的不同節(jié)點類型統(tǒng)一劃分為：開始節(jié)點、結(jié)束節(jié)點、動作節(jié)點、判定節(jié)點。所有流程圖必須具有開始節(jié)點和結(jié)束節(jié)點，代表流程的開始與結(jié)束。動作節(jié)點，代表流程進(jìn)行到此處時，需要完成指定的內(nèi)容，例如設(shè)置參數(shù)A為True，參數(shù)B自增1等。該內(nèi)容的定義需要測試人員根據(jù)需求文檔或者使用說明書，設(shè)計方案等進(jìn)行創(chuàng)建。如果軟件處于需求分析階段，則該節(jié)點可不需要與具體參數(shù)掛鉤，使用一段文字描述即可。判斷節(jié)點，代表流程進(jìn)行到此處時，需要根據(jù)某參數(shù)的具體取值，從而走向不同的下一個節(jié)點。

節(jié)點與節(jié)點之間的連線稱為邊。當(dāng)該邊的起點為判斷節(jié)點時，則需要為邊添加條件，代表該條件滿足時，才可經(jīng)過該邊。這里與傳統(tǒng)的流程圖中的真假分支有一定區(qū)別。因為在軟件實現(xiàn)中，邏輯的分支不一定為’if’和’else’，還需要考慮包括使用’else if ’的多個可選邊存在的情況。因此在判斷節(jié)點本身不存儲具體的參數(shù)判定邏輯，而是在邊上進(jìn)行聲明。

通過使用上述4種類型的節(jié)點的組合與邊，即可完成模型的創(chuàng)建。

2.2 模型的路徑遍歷

工作流模型測試的核心思想是遍歷從開始節(jié)點至結(jié)束節(jié)點的每一條路徑，一條路徑也就對應(yīng)著一個測試點。如果工作流程中出現(xiàn)環(huán)的情況下，生成的路徑中還需要覆蓋到該環(huán)或者多個環(huán)組合的情況[15-16]。

為解決上述問題，決定采用有向圖的數(shù)據(jù)結(jié)構(gòu)，對用戶創(chuàng)建的工作流進(jìn)行底層數(shù)據(jù)的存儲。每一個節(jié)點代表圖中的頂點，節(jié)點到節(jié)點的路徑中為圖中的邊。這樣，就把用戶畫出的流程圖轉(zhuǎn)換為數(shù)據(jù)結(jié)構(gòu)中的有向圖。通過對圖的遍歷，即可完成工作流的路徑遍歷。

遍歷路徑時，首先使用深度遍歷的算法思想，使用一?；蜿犃写鎯β窂街械墓?jié)點。從起點開始，遍歷其下一個可到達(dá)的節(jié)點，并將其入隊，再遍歷該節(jié)點的下一個可達(dá)節(jié)點。并判斷該節(jié)點是否為結(jié)束節(jié)點，或者沒有下一個節(jié)點時，則返回，并將棧頂?shù)墓?jié)點出棧。如果已經(jīng)到達(dá)結(jié)束節(jié)點，則將棧中的節(jié)點存儲在最后的結(jié)果中，代表一條完整的路徑。如此循環(huán)。利用上述思想能夠得出圖中的所有簡單路徑[17-18](沒有重復(fù)節(jié)點出現(xiàn)的情況)。但此方法不能將有環(huán)的路徑遍歷得到。因此還需要找出圖中的所有環(huán)，遍歷所有簡單路徑與環(huán)，查看路徑中是否包含環(huán)的起點。如果有則將環(huán)放入一個臨時的數(shù)組中，這樣，就會把該簡單路徑中涉及到的所有相關(guān)環(huán)進(jìn)行記錄。最后使用排列組合的思想，將多個環(huán)組合后，插入至簡單路徑中。那么一條包含環(huán)的復(fù)雜路徑即可生成完畢。其流程如圖2所示。

圖2 路徑遍歷算法

2.3 條件的解析與測試用例生成

通過上述的路徑遍歷方法即可得出測試點。而對于測試點，對測試點中不同參數(shù)的進(jìn)行取值，則可得出完整的測試用例。因此用例的生成需要將路徑中的參數(shù)實例化，而在實例化時則需要運(yùn)用邊界值與等價類的思想。

為解決上述問題，決定采用二叉樹與棧對條件進(jìn)行解析。在解析具體的條件前，首先需要確定符號之間的優(yōu)先級。本方法采用C語言的語法，用全局變量的形式存儲兩個符號間的優(yōu)先級關(guān)系。在這里要注意的是，不同語言之間的優(yōu)先級關(guān)系可能不一致，如‘a(chǎn)&1==1’，在python中會優(yōu)先計算‘a(chǎn)&1’，但在C語言中會優(yōu)先判斷‘1==1’，因此為避免上述問題帶來的干擾，建議測試人員在輸入條件時加上括號，轉(zhuǎn)變?yōu)椤?a&1)==1’。這樣，不管任何語言，都會優(yōu)先計算‘a(chǎn)&1’。同時，同一個符號在不同語句中的意義不同，優(yōu)先級的關(guān)系也就不同。例如‘a(chǎn)-b>0’，‘-a>0’?！?’號在第一個表達(dá)式中代表減號的意義，第二個代表取反的意義，兩個的符號的優(yōu)先級在C語言中是不同的。又比如，‘*a’，‘a(chǎn)*b’，‘*’號，在第一個表達(dá)式中是指針的含義，第二個表達(dá)式則是乘號。

使用括號，對條件的語義進(jìn)行限制后，即可開展條件的解析。本文采用兩個棧完成條件的解析。

第一個棧用于存儲操作符，第二個棧用于存儲除開操作符的變量名或者數(shù)字。首先對條件表達(dá)式進(jìn)行循環(huán)，依次判斷該字符是不是操作符。如果是則將其入至操作符棧。并且在入棧之前判斷是否為空，以及當(dāng)前棧頂?shù)牟僮鞣膬?yōu)先級是否大于即將入棧的操作符。如果大于，則出棧當(dāng)前棧頂?shù)脑?，?chuàng)建一個新的二叉樹節(jié)點，并將操作數(shù)棧中的數(shù)據(jù)連續(xù)出棧兩次，將其作為該二叉樹的左右節(jié)點。最后再將新節(jié)點入操作數(shù)棧。如果該字符不是操作符，則將其先加入一個臨時變量中，并進(jìn)入下一次循環(huán)。直到字符為操作符時，先把臨時變量中的數(shù)據(jù)存入數(shù)據(jù)棧，并清空臨時變量。再繼續(xù)操作符的操作流程。因為用戶定義變量名時可能是多個字符，例如time，count等，并不是簡單的a，b的形式。所以需要一個臨時變量，來獲取完整的變量名，或者是變量的取值。

圖3 條件解析后生成的二叉樹

由上述算法及圖1可知，所有的參數(shù)只會出現(xiàn)在樹的葉子節(jié)點上，參數(shù)節(jié)點的父節(jié)點即為判斷的條件。參數(shù)節(jié)點的左右同級節(jié)點則為具體取值。得到具體取值后，則可通過邊界值與等價類的思想，生成數(shù)據(jù)，也即為生成測試用例。

3 基于判定表的測試用例生成方法

3.1 模型的創(chuàng)建

基于工作流的測試模型分析完畢后，判定表的分析則顯得稍微簡單，但也有不同之處。判定表由參數(shù)，規(guī)則，動作組成。使用表格的方式完成對參數(shù)，規(guī)則，與動作的定義。表格中的列可分為參數(shù)與動作。每一列中的不同單元格(cell)存儲著參數(shù)的條件與動作的結(jié)果。

表格中的行，即為規(guī)則(rule)?？梢岳斫鉃槎鄠€參數(shù)判定條件的組合。同工作流程圖，在使用該模型時，也需要對參數(shù)的類型，步進(jìn)等信息進(jìn)行定義。測試人員在創(chuàng)建模型時，和工作流構(gòu)建時相同，需提取文檔中的相關(guān)信息后，構(gòu)建判定表。

3.2 判定表測試用例生成

最后將上述表達(dá)式使用同工作流條件解析的思想，將其解析為二叉樹后，再提取參數(shù)及其取值，并利用邊界值與等價類的思想，生成測試數(shù)據(jù)后，再使用eval函數(shù)去除不合適的數(shù)據(jù)。那么一條rule的測試數(shù)據(jù)即可自動生成完畢。

4 基于狀態(tài)轉(zhuǎn)換圖的測試用例生成方法

4.1 模型的創(chuàng)建

狀態(tài)轉(zhuǎn)換圖與工作流類似，可將狀態(tài)視為工作流中的節(jié)點，狀態(tài)至狀態(tài)之間的轉(zhuǎn)換，可以理解為節(jié)點至節(jié)點的邊。但是狀態(tài)轉(zhuǎn)換圖中并沒有起始節(jié)點和結(jié)束節(jié)點的概念，只存在一個初始狀態(tài)的節(jié)點[19]。并且狀態(tài)轉(zhuǎn)換圖中測試點的概念也與工作流的的概念不同[20]。在工作流程中，從起始節(jié)點至結(jié)束節(jié)點的一條路徑即為一個測試點。而在狀態(tài)轉(zhuǎn)化圖中，測試的目的是測試不同狀態(tài)之間是否按照規(guī)定的條件進(jìn)行轉(zhuǎn)換，并且可以存在狀態(tài)之間的多次循環(huán)轉(zhuǎn)換，循環(huán)轉(zhuǎn)換次數(shù)需要由測試人員憑經(jīng)驗決定。往往在實際測試項目中，簡單的從狀態(tài)一轉(zhuǎn)換至狀態(tài)二并不會出現(xiàn)問題。但在循環(huán)轉(zhuǎn)換時，狀態(tài)一至狀態(tài)二，狀態(tài)二再轉(zhuǎn)換至狀態(tài)一，狀態(tài)一再轉(zhuǎn)換至轉(zhuǎn)二時，會出現(xiàn)錯誤。其他情況同理。

4.2 模型的路徑遍歷

通過上述分析，直接使用狀態(tài)轉(zhuǎn)換圖模型，采用深度遍歷的算法，不能得出的正確的測試路徑。本方法提出將狀態(tài)轉(zhuǎn)換圖轉(zhuǎn)換至狀態(tài)轉(zhuǎn)換樹，得出狀態(tài)轉(zhuǎn)換樹后再使用深度遍歷的思想。因為狀態(tài)之間可以循環(huán)轉(zhuǎn)換，所以該樹可以無限衍生下去。因此需要定義一個深度的概念，該概念與二叉樹的深度不同，當(dāng)所有狀態(tài)都遍歷到，所有狀態(tài)至狀態(tài)的邊都遍歷到時，此時生成的樹，稱為深度為1的樹。如果測試人員想對循環(huán)狀態(tài)轉(zhuǎn)換進(jìn)行測試，則可以繼續(xù)對該樹進(jìn)行拓展，如進(jìn)行帶有一次循環(huán)狀態(tài)測試，則該樹需要向下再拓展一層。因此最后的測試點需要由用戶決定深度后再去生成。一個典型的狀態(tài)轉(zhuǎn)換圖如圖4所示。

圖4 某典型狀態(tài)轉(zhuǎn)換圖

定義狀態(tài)1為初始狀態(tài)。將狀態(tài)圖轉(zhuǎn)換至狀態(tài)樹后，可得如圖5所示。

圖5 深度為1的狀態(tài)轉(zhuǎn)換樹

將狀態(tài)轉(zhuǎn)換圖轉(zhuǎn)換為狀態(tài)樹后，則可開始測試用例的生成，生成方法與工作流類似。

在實際測試過程中，某復(fù)雜功能的實現(xiàn)，其夠成的模型可能是狀態(tài)轉(zhuǎn)換圖與工作流模型的組合。假如，上圖中狀態(tài)1轉(zhuǎn)換至狀態(tài)2的條件為某工作流。因此需要將工作流與狀態(tài)轉(zhuǎn)換圖進(jìn)行關(guān)聯(lián)。最后生成的測試點是狀態(tài)圖本身測試點與工作流本身測試點的乘積。

5 實驗結(jié)果與分析

為驗證基于模型的測試用例生成方法的正確性與完整性，將該方法應(yīng)用于實際項目中。某型號項目具有如下處理流程：

1)電臺向顯控盒發(fā)送工作參數(shù)。

2)顯控盒是否收到ACK/NAK。

3)如果收到ACK，則判斷是否收到工作參數(shù)。

4)如果收到NAK或者未收到ACK,則電臺重新發(fā)送。超過兩次未收到ACK，或者收到NAK，則流程結(jié)束。

5)收到ACK，并且收到工作參數(shù)，則進(jìn)行合法性校驗。校驗成功，則保存至FLASH，并修改參數(shù)，流程結(jié)束。校驗不成功則回退參數(shù)，流程結(jié)束。

6)未收到參數(shù)，并且未超時，則繼續(xù)等待接收參數(shù)。超時后，回退參數(shù)，流程結(jié)束。

5.1 實驗步驟

1)測試人員根據(jù)上述流程繪制模型。并檢查模型是否完整。

2)如果模型完整，則使用基于工作流的測試用例生成方法，生成測試用例。

3)測試人員根據(jù)自動生成的測試用例，執(zhí)行測試。

4)測試人員采用手動設(shè)計測試用例的方法，進(jìn)行用例的設(shè)計并執(zhí)行。

5)將自動生成的用例與手動生成的用例進(jìn)行對比，檢查自動生成用例的完整性與正確性。

5.2 結(jié)果分析

上述流程經(jīng)過建模后結(jié)果如圖6所示。

圖6 基于工作流建立的測試模型

模型建立完成，不缺少模型的必須組件，每個判定都具有相應(yīng)的分支。則可得出設(shè)計流程正確。運(yùn)用測試用例生成方法后，可得出簡單路徑4條，環(huán)2個。最終算法運(yùn)用排列組合的思想，得出完整路徑14條。也即為14個測試用例。其中一個測試用例為：開始→發(fā)送工作參數(shù)→是否接收ACK/NAK(期望結(jié)果，收到ACK) →是否收到工作參數(shù)(期望結(jié)果，收到參數(shù))→合法性校驗(期望結(jié)果，校驗成功)→修改參數(shù)，保存至FLASH→結(jié)束。其他用例不一一列舉。測試人員根據(jù)上述用例，并按照流程執(zhí)行，即可驗證對應(yīng)軟件邏輯是否按照預(yù)期進(jìn)行編寫。

測試人員不借助算法，運(yùn)用常用的用例設(shè)計方法手動設(shè)計用例14個。并將用例與自動生成的用例進(jìn)行詳細(xì)對比，每個手動設(shè)計的用例都與自動生成的用例內(nèi)容相同。因此，該算法能夠正確生成測試用例，并且在用例完整性，正確性上都得到了保證。

其他現(xiàn)有的測試用例自動生成方法，不能夠用于判定表，狀態(tài)轉(zhuǎn)換圖等模型的用例生成，并且，只對路徑的遍歷進(jìn)行算法研究，沒有對路徑中判定分支的具體取值進(jìn)行計算，不能給出經(jīng)過邊界值與等價類過濾后得出的可選取值。而在上述實驗中，重傳次數(shù)小于2(count<2)，通過對表達(dá)式的解析，會獲取出2的左右邊界及自己(1，2，3)，并將其作為分支的可選取值對自動生成的用例進(jìn)行實例化，使得用例不再抽象。

當(dāng)然，該流程在實際項目中屬于簡單的處理邏輯。當(dāng)流程較為復(fù)雜，分支較多時，采用基于模型的用例生成方法，能夠快速地生成完整的測試用例，不會因為人為的因素，或多或少地生成用例。并且整個測試的時間也會大幅度減少，并有助于理清測試人員的測試思路。提高測試效率。

6 結(jié)束語

隨著面向?qū)ο蟮能浖_發(fā)技術(shù)的不斷發(fā)展和廣泛應(yīng)用，基于模型的軟件測試，不僅可以把軟件測試工作提前到開發(fā)過程，因此能夠較早的參與測試，并發(fā)現(xiàn)系統(tǒng)設(shè)計的不足，減少了后期的維護(hù)成本與軟件測試的成本。

本文分別針對工作流，判定表，狀態(tài)轉(zhuǎn)換圖3種模型的測試用例生成進(jìn)行了詳細(xì)的說明。為解決測試行業(yè)當(dāng)前主要問題提供一定的幫助與貢獻(xiàn)。

后期將進(jìn)一步對算法進(jìn)行深入優(yōu)化。如存在并發(fā)場景的測試模型，該如何進(jìn)行測試用例的生成等。