杜婉瑩,王雅文

(北京郵電大學 網絡與交換技術國家重點實驗室，北京 100876)

0 引言

如今，信息產業(yè)的蓬勃發(fā)展離不開信息技術的發(fā)展，涉及到了通信設備、計算機、軟件等一系列領域。隨著市場對軟件質量要求和軟件自身復雜度的不斷提高，軟件測試的重要性和軟件測試在軟件工程中所占的比例越來越大[1]。據統(tǒng)計，隨著對軟件可靠性要求的提高，軟件測試會占用40%乃至60%的總開發(fā)時間[2]，其中，單元測試作為軟件測試的重要環(huán)節(jié)，其目的是檢測各個單元模塊的故障缺陷，會占用60%左右的測試工作所花費的時間。與手工測試相比，自動化測試能降低系統(tǒng)測試和維護等階段的成本、有效提高測試的效率和質量，同時能夠顯著提高測試覆蓋率、大大擴展測試深度[3]，自動化測試工具的研發(fā)正逐漸受到重視。

目前已有的自動化測試工具有Logiscope、PRQA、Macabe、DevPartner、Purify等[4]，這些測試工具要么分析代碼的語法漏洞、要么統(tǒng)計程序執(zhí)行時的數據，又或者是對功能的可行性和效率進行檢測等。在這之中，單元測試工具有CppUnit、C++ Test、VectorCAST、Visual Unit等，它們能對程序進行靜態(tài)分析、也能生成測試框架代碼，然而大部分都不支持測試用例自動生成功能，需要依賴人工來完成測試用例生成操作，因此，對測試用例生成方法的研究具有重要的理論和實踐價值[5]。

面向對象程序具有封裝、繼承、多態(tài)三大特性。其中，繼承使子類可以直接擁有父類定義的屬性和操作，減少代碼冗余，增強代碼的復用性和可擴展性；多態(tài)能使同一操作在不同子類中有不同的具體實現，讓對象以適合自己的方式響應事件[6]。當子類重寫父類函數，并讓父類的指針或引用指向子類對象時觸發(fā)。多態(tài)的存在令程序的編寫僅需指明要執(zhí)行的操作，在實際執(zhí)行時編譯器會根據對象所屬的具體類型來調用相應的方法，從而表現出不同的行為，靈活性更高[7]。對于包含存在于繼承體系中的類對象的源程序，僅憑靜態(tài)分析，編譯器無法判斷程序中類型轉換語句的結果以及被調用函數所屬的類[8]。

在測試用例生成時，如果需要對類對象進行實例化，對象類型的選取是用例生成效率和有效性的一個影響因素。靜態(tài)生成測試用例開銷更小，也具有一定的挑戰(zhàn)性，而面向路徑的測試用例生成在白盒測試中非常常見。其中，符號執(zhí)行使用符號來表示程序的輸入數據，模擬執(zhí)行被分析程序，用符號表達式操作代替程序中對變量和參數的操作，是路徑分析的一種常用手段。在這一方面，國內外都有不少研究人員參與了研發(fā)工作，例如，Euclide定義了內存動態(tài)管理的操作語義模型[9]，許中興等人提出了虛擬數組建模內存[10-11]，趙云山等人設計實現了針對數值型變量的符號執(zhí)行系統(tǒng)[12]。在單元測試中，當被測函數的輸入變量中含有父類引用時，如何選擇類進行實例化，當被調用函數是某個基類的成員函數時，應該選擇哪個類中的該函數進行摘要提取，通過靜態(tài)分析來解決這些問題是本課題研究的重點。

本文第1節(jié)對類的抽象內存表示模型進行概述；第2節(jié)介紹類的操作語義模擬算法；第3節(jié)介紹基于抽象內存模型的單元測試用例生成方法；第4節(jié)通過一個實例演示路徑分析中抽象內存的變化過程；第5節(jié)對提出的模型和算法進行實驗并分析實驗結果；第6節(jié)總結全文。

1 類的抽象內存表示模型

為了明晰函數中類對象的可取類型，以便確認單元測試的輸入變量類型集合以及在函數調用點的函數摘要提取操作[13]，可以在路徑生成后，通過構建類的抽象內存模型并配合符號執(zhí)行技術提取出路徑上與類對象有關的約束，縮小類對象實際類型的可選范圍，在精簡測試用例集合的同時保證覆蓋率，提高單元測試的效率。

抽象內存模型是存儲變量語義和約束的靜態(tài)存儲介質，用于記錄變量在符號執(zhí)行中的動態(tài)變化[14]。對程序執(zhí)行自動測試，需要先通過靜態(tài)分析得到測試所需的代碼信息，為此需要構建符號表，它也是類的抽象內存模型的基礎。

1.1 類的符號表

在靜態(tài)建模中，抽象語法樹是最重要的中間結構，它是源程序的一種抽象表現，也是提取程序信息的入手點。源程序的每行代碼以及每個關鍵字都有對應的抽象語法樹節(jié)點[15]。

對面向對象程序執(zhí)行單元測試需要先通過靜態(tài)分析得到被測函數模塊的輸入變量。這就需要遍歷程序的抽象語法樹，正確并完整地識別出程序中各個類、函數和變量的信息以及它們之間的關聯(lián)關系，將其記錄于符號表中，在隨后生成測試用例時便能快速獲取所需信息。本課題的研究重點是類，由類在組成結構方面的特點可以歸納出其基本信息，由此可得類對應符號表的結構如表1所示。

表1 類對應符號表的屬性

面向對象程序中不同的類可能存在于不同的繼承體系中，同一繼承體系中類的屬性也存在差異。如果該類存在于繼承體系中，就將它的父類和子類對應的符號表項和繼承類型存儲起來[16]，由于面向對象程序的繼承特性，子類無需聲明便可擁有父類的成員，在記錄了類的繼承情況后，就可以通過符號表快速獲取從父類繼承下來的屬性和特征。C++支持多繼承；Java中的類雖然只能單繼承，但是可以實現多個接口，因此parents是一個列表[17]。

在類的成員變量中，靜態(tài)變量需要單獨標注，因為它們?yōu)樵擃惖乃袑嵗蚕恚诔橄髢却婺Ｐ偷臉嫿ê蜏y試用例生成中都需要單獨處理。不論是通過哪個實例對靜態(tài)變量進行訪問，實際效果和通過類名調用是相同的，影響的都是同一個成員[18]。

在類的成員函數中，構造函數、靜態(tài)函數、沒有函數體的函數(例如Java的抽象方法和C++的純虛函數)、有函數體但可以重寫的函數(例如Java中除構造方法、靜態(tài)方法、final和private修飾的方法以外的其他方法以及C++的虛函數)以及其他函數需要分開記錄，可以通過這些列表的存儲情況來判斷類是否為抽象類。

isAbstract用于說明該類對象能否直接實例化。因為抽象類和接口不能直接實例化，需要通過實例化子類并向上轉型的方式來間接完成，所以這里需要被區(qū)分。本課題將接口與抽象類同等處理。在C++中，抽象類的子類只要沒有重寫父類的全部純虛函數，就仍為抽象類；在Java中，抽象類通過abstract顯示聲明。

1.2 抽象內存模型分類

在面向對象程序中，針對不同的數據類型，可以將抽象內存模型分為基本抽象內存模型、數組抽象內存模型、指針抽象內存模型和類的抽象內存模型，其中類的抽象內存模型也適用于記錄結構體變量的內存情況。不同類別的抽象內存模型存在一些公共屬性，如符號值、抽象內存單元地址、符號表項等。除了公共屬性以外，不同的數據類型還有不同的語言特性，比如數組類型需要記錄數組長度、指針類型指向的是內存單元地址、類的成員在內存中離散存放[19]。每個變量都對應一個抽象內存模型，類對象也是如此，但是同一個類的多個對象之間共享一部分屬性，即靜態(tài)變量，任意對象都可以對這部分屬性進行訪問和修改。

本課題將類的抽象內存模型中與類結構相關的屬性提取出來，這部分屬性與類本身相對應，構成類類型的抽象內存模型；剩下的屬性則與具體對象有關，構成類對象的抽象內存模型。類類型的抽象內存模型與類對象的抽象內存模型之間的關系如圖1所示。

圖1 類的兩種抽象內存模型之間的關系

1.3 類類型的抽象內存模型

以Java為例，在使用某個類時，首先要將該類加載到內存中，通過類加載器創(chuàng)建相應的Class對象。類的靜態(tài)變量在內存中僅有一份，隨著類的加載在方法區(qū)中分配內存，所以類的每個靜態(tài)變量的抽象內存模型也應該只有一份。在路徑分析中，即使是通過不同的類實例來訪問和修改靜態(tài)成員，影響的也只是同一個變量。因此，為每個初次遇見的類的Class對象構建類類型的抽象內存模型，其結構如表2所示，隨著路徑分析建立類類型的抽象內存模型與靜態(tài)變量之間的關聯(lián)關系。雖然C++的這一過程與Java不同，但是在符號執(zhí)行中可以同等處理。

表2 類類型的抽象內存模型屬性

不同類別的抽象內存模型放在對應的抽象內存區(qū)中，并通過地址來定位。針對不同的抽象內存區(qū)，地址使用不同的前綴，基本抽象內存模型所在區(qū)的前綴為Mn，數組抽象內存模型所在區(qū)的前綴為Ma，指針抽象內存模型所在區(qū)的前綴為Mp，類的抽象內存模型所在區(qū)的前綴為Mc。

符號表項和抽象內存模型是一一對應的，被測函數中的每個類、變量以及復雜變量的成員變量都有這兩項信息。為了提高運行效率，members初始為空，只有在初次遇到靜態(tài)變量時，才為其創(chuàng)建抽象內存模型，并將映射關系添加進去，下一節(jié)中類對象的抽象內存模型同理。

1.4 類對象的抽象內存模型

在路徑分析中，對于首次遇到的類對象，要為其構建類對象的抽象內存模型。類對象離不開它所屬的類，每個類對象都可以訪問所屬類的靜態(tài)成員，這就需要指向對應的類類型的抽象內存模型的指針。由于面向對象程序的多態(tài)性，類對象的所屬類需要進一步分為引用所屬類和實際所屬類，以便對類型轉換語句和函數調用點進行分析，兩者的意義不同，引用所屬類從指向對象的指針或引用處獲取，實際所屬類記錄于類對象的抽象內存模型中。類對象的抽象內存模型的結構如表3所示。

表3 類對象的抽象內存模型屬性

name要么為變量聲明時的名字，要么為復雜變量的成員變量名，如數組變量array的第一個成員變量的變量名為array[0]。

source指明該變量是輸入參數、局部變量、全局變量還是類成員變量，又或者是上述某個復雜變量的成員變量。其中，輸入參數、全局變量、類成員變量均是測試用例的組成部分，局部變量則不需要放在測試用例中。

realCType是類對象的抽象內存模型中最重要的屬性，這是提取類型約束的關鍵，每個類對象的抽象內存模型都有指向所屬類對應的類類型的抽象內存模型的指針。即使存在父類引用指向子類對象的情況，類對象能訪問的靜態(tài)成員也只與當前引用所屬類有關，不會受實際所屬類影響。例如，類Apple繼承了類Fruit，定義變量Apple a，將其向上轉型為Fruit，此時它的引用所屬類為Fruit，實際所屬類為Apple，可以訪問Fruit的靜態(tài)成員，而無法訪問Apple的特有屬性。然而，類對象的實際所屬類在對路徑的語義模擬和可達性分析、以及作為后續(xù)測試用例生成的參考中有很大作用。

2 類的操作語義模擬算法

類對象作為非數值類型變量，在符號執(zhí)行中僅僅使用一個符號[20]對其進行表示是不夠的，也不利于使用約束求解器[21]對其求解，需要在路徑分析中通過動態(tài)地抽象內存建模來描述它的語義和約束。使用抽象內存模型對非數值型變量的約束進行處理，從中提取出數值型約束，并將剩余部分轉化為抽象內存中的存儲結構。操作語義模擬算法能夠在符號執(zhí)行時根據某個程序點之前各個變量的語義和約束信息，以及當前語句的語義信息來更新相關變量的抽象內存模型，模擬出抽象內存中的狀態(tài)變化。在符號執(zhí)行中，當被測函數含有類對象時，構建類的抽象內存模型，配合操作語義模擬算法，提取出路徑中的約束，對類對象的具體類型進行限定，從而生成滿足路徑條件的測試用例或者得到函數調用點處調用方法所屬的類。與類有關的操作有對象創(chuàng)建、成員訪問和類型轉換，接下來以C++語言為例，分析每種操作對應的操作語義模擬算法，并用形式化語言進行描述。

2.1 對象創(chuàng)建

如表4所示，在C++中，創(chuàng)建對象有兩種方式——直接定義(見①)和通過指針創(chuàng)建(見②)。前者與基本數據類型變量的定義格式類似，對象在棧上分配內存，不會體現面向對象程序的多態(tài)性；后者定義一個指向對象的指針，后續(xù)可以使用指針訪問對象的成員變量和成員函數，對象本身是匿名的，在堆上分配內存，可能存在父類指針指向子類對象的情況，此時會出現多態(tài)[22]。使用new創(chuàng)建的對象需要配合delete及時刪除，以防止無用內存堆積。

表4 對象創(chuàng)建的兩種方式

對形如①的語句，直接為變量var創(chuàng)建類的抽象內存模型，首先判斷是否已經創(chuàng)建了類ClassName對應的類類型的抽象內存模型，如果沒有就進行構建；隨后為變量var本身創(chuàng)建類對象的抽象內存模型，指定變量來源，變量的實際所屬類為ClassName。無論是初次創(chuàng)建類類型的抽象內存模型還是初次創(chuàng)建類對象的抽象內存模型，都需要為其指定一個符號，在類的抽象內存區(qū)中新建一塊抽象內存單元，并與對應的符號表項進行關聯(lián)，且members初始均為空。

對形如②的語句，先為指針p創(chuàng)建指針抽象內存模型，指定指針來源，定義指針狀態(tài)為非空，再按上述步驟為指針p指向的類對象創(chuàng)建類的抽象內存模型，建立兩者之間的聯(lián)系。綜上所述，對象創(chuàng)建的操作語義模擬算法的形式化語言描述如表5所示。如果只是聲明ClassName類的指針p，沒有對其賦值，那么它的初始狀態(tài)為不確定，此時暫不需要創(chuàng)建類的抽象內存模型；如果約束指針狀態(tài)為非空，但指針指向對象的類型尚不確定，那么類對象的實際所屬類為空；如果類對象的引用所屬類和實際所屬類不同，還要判斷兩者是否存在繼承關系。

表5 對象創(chuàng)建的操作語義模擬算法

2.2 成員訪問

如表6所示，在C++中，根據創(chuàng)建對象方式的不同，訪問成員的方式也有兩種——直接訪問(見③)和通過指針訪問(見④)。

表6 成員訪問的兩種方式

訪問對象的mem成員時，如果已經為其構建了抽象內存模型，則判斷是否需要建立對象和成員之間的關聯(lián)關系，并根據成員類型和語義信息提取約束即可，否則為其構建抽象內存模型。對形如③的語句，構建var和var.mem之間的關聯(lián)關系；對形如④的語句，構建*p和p->mem之間的關聯(lián)關系。如果mem是靜態(tài)變量，關聯(lián)關系建立在類類型的抽象內存模型中；如果mem是非靜態(tài)變量，關聯(lián)關系建立在類對象的抽象內存模型中。綜上所述，以形如③的語句為例，成員訪問的操作語義模擬算法的形式化語言描述如表7所示。

表7 成員訪問的操作語義模擬算法

值得注意的是，如果子類Apple繼承了父類Fruit的靜態(tài)成員color，在抽象內存中同時存在類Fruit的抽象內存單元和類Apple的抽象內存單元，且兩個類類型的抽象內存模型的members都包含color，那么它們存儲的color理應指向同一個抽象內存模型，為便于查找，類的靜態(tài)成員的完整變量名統(tǒng)一為定義所在類的類名+變量名，比如，在這個例子中，類成員color在抽象內存模型中存儲的變量名為“Fruit::color”。

2.3 類型轉換

類型轉換是類的操作語義模擬算法關注的重點，只有當路徑中存在對類對象的類型判斷或者類型轉換語句時，才能根據不同分支或是能使程序繼續(xù)執(zhí)行所需的轉換條件對類對象的類型進行約束。對象的向上轉型會自動完成，因為向上轉型一定是安全的，但是一旦轉型為父類對象，就無法再調用子類原本特有的方法；對象的向下轉型需要進行強制類型轉換，且必須先發(fā)生過向上轉型、才能成功向下轉型，否則會報錯。在編譯時，編譯器無法判斷對象實例化時傳遞的是什么數據類型，因此不會對強制類型轉換進行檢查。

C++有4種強制類型轉換函數，分別為const_cast、static_cast、dynamic_cast和reinterpret_cast。其中，static_cast和dynamic_cast均可以用于類層次結構中基類和派生類之間指針或引用的轉換。static_cast類似C語言中的強制轉型，不提供運行時類型檢查，因此在進行類的向下轉型時具有一定的安全隱患；而dynamic_cast會在運行時對類型信息進行檢查，對于無法強制轉型的變量會返回nullptr，從而保證類型轉換的安全性。由于這兩個函數的特點，C++中的所有隱式類型轉換都會調用static_cast；而在編碼時，對于顯式類型轉換則常常通過dynamic_cast來實現[23]。在Java中，通常使用instanceof關鍵字來判斷某個實例是否是某個類的對象。

如果出現類型判斷語句或者類型轉換語句，判斷類對象是否已經確定實際所屬類，如果沒有且待轉換類型與引用所屬類存在繼承關系，用位于更底層的類型更新實際所屬類，繼續(xù)執(zhí)行；如果有，判斷待轉換的類型是否處于引用所屬類與實際所屬類所在的繼承體系中，如果在，用三者中位于更底層的類型更新實際所屬類，繼續(xù)執(zhí)行，否則說明路徑不可達。綜上所述，類型轉換的操作語義模擬算法的形式化語言描述如表8所示。

表8 類型轉換的操作語義模擬算法

3 基于抽象內存模型的測試用例生成

對函數模塊執(zhí)行單元測試可以采用基于輸入域的隨機測試、邊界值測試和基于路徑的隨機測試等。提取出函數的輸入變量，根據每個變量的數據類型生成多個隨機值并組合成測試用例。其中，基于輸入域的隨機測試是指在變量的取值區(qū)間內生成隨機值；邊界值測試指的是在變量的取值范圍的邊界處生成隨機值，除此之外還要考慮某些特殊值，例如對于整型變量，要特別考慮取值為0的情況。這兩種測試方式簡單高效，無需考慮函數內部的實現細節(jié)，可以很快生成大量測試用例，但是也很容易造成過多的冗余測試用例，并且生成的測試用例很難能夠執(zhí)行到函數內部某些條件苛刻的語句[24]。此時可以根據函數的控制流圖提取出未覆蓋元素集合，使用基于路徑的隨機測試來生成覆蓋到這些元素的測試用例。

當被測函數的輸入變量含有基類的指針或引用且函數中出現了類型轉換語句時，如果不對路徑信息進行分析，就無法判斷對變量進行初始化時應該傳遞哪種類型的實例。就算先不考慮基類為抽象類的情況，如果直接對該基類對象實例化，很有可能在類型轉換時出錯、或者在類型判斷時無法執(zhí)行到相應分支；如果對該基類的所有底層子類創(chuàng)建實例化對象，再以父類引用指向子類對象的方式進行賦值，很有可能會生成眾多冗余的隨機值，使最終得到的測試用例集合非常龐大，且測試的復雜程度會隨著代碼和繼承體系復雜程度的提高而成倍增長，然而這其中很多都是沒有必要的，會大大降低測試效率。這時，通過構建類的抽象內存模型，對類對象的具體類型進行約束，就能使生成的測試用例以較少的數量覆蓋到盡可能多的語句。

分析被測函數，提取類的類型判斷語句和類型轉換語句對應的覆蓋元素，從下往上逐個分析。對于當前覆蓋元素，判斷其是否為未覆蓋元素，若為未覆蓋元素，生成經過該覆蓋元素的路徑，從函數入口開始，為輸入變量中的類對象構建類的抽象內存模型，通過符號執(zhí)行提取出路徑上類相關的約束，得到變量的類型信息。當獲得的類型信息中對象的實際所屬類與之前不同時，如果分析得到的類是非抽象類，直接為其生成隨機值對象；如果分析得到的類是抽象類，為其距離最近的非抽象子類生成隨機值對象。將各個輸入變量的隨機值組合成多組測試用例并代入執(zhí)行，根據執(zhí)行后的插裝信息更新已覆蓋元素集合和未覆蓋元素集合[25]，如此反復。直到全部類型判斷語句及其分支和類型轉換語句均已被覆蓋，若覆蓋率已達到100%，結束測試；否則考慮變量的實際類型為基類本身的情況，如果基類為非抽象類，直接對其實例化，不然就對距離基類最近的非抽象子類生成實例化對象。

對類對象的類型信息進行提取，除了在測試用例生成中起到了很大作用之外，在函數摘要的提取中也能派上用場。通過路徑分析得到函數調用點處對象的實際所屬類，從而得知動態(tài)執(zhí)行時可能會調用哪些子類的方法，進而提取相應函數的函數摘要。先通過引用所屬類對應的符號表項獲取到方法的相關信息，如果該方法不能被重寫，說明調用的就是引用所屬類中的方法；如果方法可以被重寫，就需要根據對象的實際所屬類來判斷。從實際所屬類開始，由下往上查找該方法，直到找到該方法最新被重寫的地方，即為后面會被調用執(zhí)行的位置。

現如今，許多研究人員都在思考具有更高測試用例利用率的自動測試用例生成方法，如通過約束求解來提高測試用例命中率。在面向過程程序的單元自動化測試領域，北京郵電大學的唐榮對C語言中非數值類型變量的抽象內存模型和約束提取算法進行了研究和設計，實現了支持非數值型測試用例自動生成的面向路徑的約束求解測試。在面向對象程序的自動化測試領域，類雖然是重點研究對象，然而大部分研究工作都局限于單個類內部一個或多個函數間的測試，沒有考慮到由于類的繼承和多態(tài)等特性所導致的多個類之間的相互影響，也沒有對函數內部的類型轉換語句進行處理。北京郵電大學的陳江南在研究面向路徑的類測試方法時，提出了類成員方法擴展控制流圖生成算法，根據被調用函數所屬類所在的繼承體系，將完整路徑分為基本子路徑和實例化子路徑兩部分，所有可能的函數調用情況都作為實例化子路徑配合分支節(jié)點添加到原有的控制流圖中，兩部分路徑分別生成后再進行組合。陳江南的研究默認基本子路徑不會涉及對類對象實際類型的約束，相當于為所有派生類對象生成取值。在這一方面，中國科學技術大學的黃雙玲在研究C++程序中函數調用關系的靜態(tài)分析方法時，考慮到了函數內部的類型轉換語句，在記錄變量的類型信息時，會分別記錄變量的聲明類型和動態(tài)類型，以便對后續(xù)出現的函數調用語句進行解析。

目前已有的面向對象自動化單元測試工具，如針對C/C++語言的Parasoft C++ Test和針對Java語言的Randoop，其研發(fā)的重心并不在函數輸入變量中類對象的具體類型。當出現類的指針或引用變量時，很多都只為基類對象生成取值。只為基類對象生成取值、為所有派生類對象生成取值，以及對變量類型進行約束后生成取值，這三種測試用例生成方式的結果對比見下文中第五節(jié)。

4 實例分析

為了驗證前兩節(jié)中介紹的操作語義模擬算法和基于路徑的隨機測試算法的可行性，接下來以圖2中的被測函數為例，演示路徑分析中抽象內存的變化過程，展示如何通過類的抽象內存建模提高函數的覆蓋率。

圖2 商店進貨的代碼片段

函數stock()的輸入參數包含Goods類的指針goods，且函數體內存在對變量的類型轉換語句L2，它也是一條判斷語句。初始時，已覆蓋元素集合為空，L2尚未被覆蓋，生成一條經過該條件表達式真分支的路徑Path：L1->L2->L3。在路徑的起始節(jié)點處，為指針goods在指針抽象內存區(qū)分配抽象內存單元Mp0，指針來源為輸入參數，此處指針取值還無法確定，所以指針狀態(tài)為NOT_SURE，處理完畢后抽象內存的狀態(tài)如表9所示。

表9 指針抽象內存區(qū)狀態(tài)一

分析L1語句的語義——將指針goods所指對象的兩個成員weight和ratio相乘，并將乘積與全局變量totalWeight相加的結果賦值給totalWeight。由指針的約束提取算法可知，應為指針添加非空約束，且需要為指針指向的類對象創(chuàng)建類的抽象內存模型。類Goods對應的類結構抽象內存模型尚未被創(chuàng)建，為其在類的抽象內存區(qū)中分配抽象內存單元Mc0。為類對象創(chuàng)建類實例抽象內存模型，分配內存單元Mc1，變量名為*goods，變量來源為參數成員，其實際所屬類為Goods。為類對象*goods添加成員goods ->weight和goods->ratio，它們的數據類型分別為整型和浮點型，在基本抽象內存區(qū)中新建抽象內存單元Mn0和Mn1。由于weight為實例變量，只與*goods這個具體實例有關，將其添加到Mc1的成員域中；而ratio為靜態(tài)變量，與類有關，且在類Goods中定義，因此抽象內存模型中存儲的變量名為Goods::ratio，將其添加到Mc0的成員域中。最后，為整型變量totalWeight新建抽象內存單元Mn2，變量來源為全局變量，并根據表達式信息更新其符號值。執(zhí)行完這些操作后，抽象內存的狀態(tài)如表10～12所示。

表10 指針抽象內存區(qū)狀態(tài)二

表11 類的抽象內存區(qū)狀態(tài)二

表12 基本抽象內存區(qū)狀態(tài)二

分析L2語句的語義——將Goods類的指針變量goods向下轉型為Food類的指針并賦值給局部變量food，判斷food是否為空指針，不為空指針的真分支繼續(xù)執(zhí)行L3。為指針變量food在指針抽象內存區(qū)中新建一塊抽象內存單元Mp1，指針來源為局部變量。要使條件表達式結果為真，應使變量goods能夠成功進行類型轉換，對指針food添加不為空的約束。類對象*goods的引用所屬類和實際所屬類均為Goods類，類Food是類Goods的子類，約束*goods的實際所屬類為位于更底層的Food類。為Food類在類的抽象內存區(qū)中分配一塊抽象內存單元Mc2，Mc1的實際所屬類指向它。對指針goods的類型轉換不會改變它的取值，即所指類對象的地址，因此指針food應指向同一個類對象，Mp0和Mp1的指針域均為Mc1。執(zhí)行完這些操作后，抽象內存的狀態(tài)如表13～15所示。

表13 指針抽象內存區(qū)狀態(tài)三

表14 類的抽象內存區(qū)狀態(tài)三

表15 基本抽象內存區(qū)狀態(tài)三

分析L3語句的語義——將指針food所指對象的兩個成員weight和ratio相乘，并將乘積與全局變量totalFoodWeight相加的結果賦值給totalFoodWeight。指針food指向的類對象為*goods，檢查它的兩個成員weight和ratio是否已經被添加。其中，weight為實例變量，已經被添加進類實例抽象內存模型Mc1的成員域中；ratio為靜態(tài)變量，在類Goods中定義，完整變量名為Goods::ratio，在基本抽象內存區(qū)中已經創(chuàng)建了相應的抽象內存單元Mn1，然而它并沒有與*goods的實際所屬類Food對應的類結構抽象內存模型Mc2建立關聯(lián)關系，將其添加進Mc2的成員域中。最后，為整型變量totalFoodWeight新建抽象內存單元Mn3，變量來源為全局變量，并根據表達式信息更新其符號值。執(zhí)行完這些操作后，抽象內存的狀態(tài)如表16～18所示。

表16 指針抽象內存區(qū)狀態(tài)四

表17 類的抽象內存區(qū)狀態(tài)四

表18 基本抽象內存區(qū)狀態(tài)四

對路徑Path：L1->L2->L3分析完畢后，得到對函數stock()的輸入參數goods的約束信息，即指針所指向對象的類型應為Food類或其子類。此處Food類為非抽象類，直接對其隨機生成多個實例化對象，并將對象的地址傳遞給指針goods。將輸入變量goods、totalWeight和totalFoodWeight的隨機值組合成多組測試用例，代入并動態(tài)執(zhí)行后，根據探針函數的返回值更新已覆蓋元素集合和未覆蓋元素集合，計算覆蓋率。發(fā)現可以達到100%，可知當前測試用例集合已滿足測試需求，結束測試。

5 實驗結果及分析

代碼測試系統(tǒng)(CTS,code testing system)是一款面向C語言程序的自動化單元測試工具，它采用動靜結合的方式，支持以函數模塊為單元執(zhí)行基于輸入域的隨機測試、邊界值測試和面向路徑的測試。CTS已經完善了對C語言類型系統(tǒng)的符號表、抽象內存模型和操作語義模擬算法的設計與實現。CTS-CPP是CTS的C++版本，在其基礎上提供了對類的支持。本課題對CTS中的符號表和抽象內存模型進行擴展，將類的操作語義模擬算法和基于路徑的隨機測試算法應用于面向C++程序的自動化測試工具CTS-CPP中，使CTS-CPP能夠提供基于輸入域的隨機測試和基于路徑的隨機測試功能。

5.1 實驗環(huán)境

本課題在CTS-CPP中完成測試用例生成模塊，其運行于CentOS 7系統(tǒng)中，JDK版本為1.8，使用Java語言在Eclipse平臺中開發(fā)，虛擬機最大內存設置為2G。

5.2 實驗內容

為了驗證本課題提出的模型和算法的可行性和有效性，本章對表19中的5個函數進行了基于路徑的隨機測試，記錄測試過程中生成的路徑和約束提取情況，并將測試結果同基于輸入域的隨機測試作比較。

表19 5個被測函數屬性

5.3 實驗結果

為了展示類的抽象內存模型結合操作語義模擬算法是否能夠成功提取路徑中類相關的約束，得到類對象的實際所屬類，以choose()函數為例，執(zhí)行基于路徑的隨機測試。choose()函數的輸入變量有函數參數coffee、balance、time和所屬類Shop的成員變量sales、bean、milk、choco，其中變量coffee是Coffee類的指針，Coffee類存在于繼承體系中，是Instant、Latte、Mocha、White等眾多類的公共基類。在函數內部有5個類型轉換節(jié)點，對應4個覆蓋元素，根據coffee指向的子類類型不同，會執(zhí)行不同分支。其路徑生成和約束提取情況如表20所示。

同理，5個被測函數的路徑生成和約束提取情況如表21所示。

對程序進行靜態(tài)分析，將變量、函數和類的基本

表20 choose()函數路徑生成和約束提取情況

表21 5個被測函數路徑生成和約束提取情況

信息存入符號表中，生成路徑后，在符號執(zhí)行中根據類的操作語義模擬算法構建并更新類的抽象內存模型，對被測函數的輸入變量中類對象的實際類型進行約束，根據分析結果為各個輸入變量在其取值區(qū)間內生成隨機值并由此得到測試用例集合，在動態(tài)執(zhí)行后統(tǒng)計函數的覆蓋情況，這就是基于路徑的隨機測試的主要流程。其通過對對象的實際所屬類進行限定來避免生成無意義的測試用例，從而提高測試效率。如果不采取這一舉措，也就是采用傳統(tǒng)的基于輸入域的隨機測試的話，對于輸入變量中的類對象，可以選擇只為引用所屬類生成實例化對象，也可以選擇為引用所屬類的所有子類生成隨機值對象，使用這一方式雖然可以快速生成大量測試用例，但是其中的冗余對測試效率的影響不可小覷。

為了更好地說明在對類的抽象內存模型進行研究后，提出的基于路徑的隨機測試相比于基于輸入域的隨機測試在提高測試效率方面的優(yōu)越性，分別采用兩種方式對5個被測函數執(zhí)行自動測試，測試結果如表22所示。

表22 測試結果

5.4 結果分析

由實驗結果可知，如果執(zhí)行基于輸入域的隨機測試，只對引用所屬類的對象生成隨機值得到的測試用例數量和覆蓋率均不高；對引用所屬類的所有子類對象生成隨機值雖然能夠得到較高的覆蓋率，然而其生成的測試用例數量同樣很高。與此相比，基于路徑的隨機測試通過對類對象的具體類型進行限定，能夠以更少的測試用例達到更高的覆蓋率。在大型程序中，測試效率的提高將會更為明顯。

綜上所述，本課題提出的類的符號表能夠提取出測試用例生成所需的類的基本信息，類的抽象內存模型和操作語義模擬算法能夠成功記錄路徑中類對象的語義和約束信息，將它們應用于基于路徑的隨機測試中，能夠得到滿足需求的結構和內容均正確的測試用例，并且提高了對面向對象程序單元測試的測試效率。

6 結束語

本課題基于面向對象程序特性，對類的抽象內存模型進行研究，并由此提出了類的操作語義模擬算法以及針對單元測試的基于路徑的隨機測試算法的概念。類的抽象內存模型能夠記錄類對象的類型信息及其與各個成員之間的關聯(lián)關系，考慮到多個實例可能對同一個靜態(tài)變量產生影響，將類的靜態(tài)成員與非靜態(tài)成員區(qū)別開，分別存儲在類類型的抽象內存模型和類對象的抽象內存模型中。使用類的抽象內存模型，不僅能夠在符號執(zhí)行中提取類型約束，縮小類對象實際類型的可選范圍，還能在今后配合其他類別的抽象內存模型獲取其各個成員變量的約束信息[26]，結合約束求解實現更為精確的面向路徑的測試。