基於抽象內存模型的非數值型數據的計算方法
2023-04-26 04:21:06
專利名稱：基於抽象內存模型的非數值型數據的計算方法
技術領域：
本發明涉及軟體測試技術，尤其涉及基於抽象內存模型的非數值型數據的計算方 法，屬於單元測試中對含非數值型數據程序的語義模擬和約束提取技術領域。
背景技術：
軟體測試分為動態測試和靜態測試兩種。動態測試是通過運行軟體來檢測軟體的 動態行為和運行結果的正確性；靜態測試是收集、查找程序的信息，對被測程序進行特徵分 析，其主要優點是在程序運行之前就可以收集程序的語義信息。在實際的軟體測試中，實際 的程序邏輯可以非常複雜的。基於靜態分析的測試用例生成方案可以很好的支持數值型的 程序，對非數值類型的程序，該方案不能很好的記錄程序的語義信息，導致自動生成非數值 類型的測試用例困難。尤其是指針的別名問題和數組的變下標引用，是符號執行的難點問 題。發明內容
有鑑於此，本發明的主要目的在於提供一種基於抽象內存模型的非數值型數據的 計算方法，其採用抽象內存建模技術存儲路徑分析過程中變量相關語義信息，在抽象內存 中為每個變量分配一個抽象內存單元，並將與該變量相關的指令操作映射為對抽象內存的 操作，精確記錄變量的結構語義和操作語義。
為達到上述目的，本發明的技術方案是這樣實現的
本發明所提供的基於抽象內存模型的非數值型數據的計算方法，具有以下優點
靜態分析和符號執行相結合的測試用例自動生成技術，是自動化單元測試常用的 測試用例自動生成技術，但該技術的缺點是對非數值型的程序支持不完善，生成測試用例 困難。而本發明則屬於基於路徑的單元測試中為非數值類型(含非數值型數據程序的語義 模擬和約束提取)自動生成測試用例的方法，其使用抽象內存建模的技術存儲路徑分析過 程中變量相關語義信息，在抽象內存中為每個變量分配一個抽象內存單元，並將與該變量 相關的指令操作映射為對抽象內存的操作，精確記錄變量的結構語義和操作語義。採用該 方法能夠彌補傳統的基於靜態分析的測試用例生成方法無法精確支持非數值型變量(結構 體、指針和數組等)程序語義的缺憾，以及能夠克服傳統的符號執行和靜態分析相結合測試 用例生成方法無法精確支持非數值型變量(結構體、指針和數組等)程序語義的不足，實現 為包含非數值型的程序自動生成測試用例的目的。
圖1為本發明基於抽象內存模型的非數值型數據的計算方法的流程圖2本發明中抽象內存的結構示意圖。
具體實施方式
下面結合附圖及本發明的實施例對本發明的方法作進一步詳細的說明。
本發明的基本思想為首先從被測函數的控制流圖上得到一條路徑作為被測路徑，然後為被測函數的輸入域參數分配抽象內存單元；之後逐個對路徑上的節點進行語義模擬，將每條指令映射為對應的抽象內存操作，提取語義信息存入抽象內存中，將符號間的數值型約束關係存入約束集中；在路徑分析結束後，從抽象內存中提取各個輸入域參數的結構信息，從約束集中提取和該參數相關的數值型約束，按測試用例生成算法為該參數構建測試用例。
圖1為本發明基於抽象內存模型的非數值型數據的計算方法的流程圖，如圖1所示，其方法主要包括
步驟1:設計抽象內存模型用於模擬數值型變量和非數值型變量的內存結構，以及存儲變量操作中包含的語義信息和約束關係。其具體包括
使抽象內存主要用於存儲變量的語義信息，按C數據類型將抽象內存模型分為四個區數值區、數組區、結構體區和指針區。
這裡，由於數據類型的特徵不同，每個區都設有特有的數據結構，以便能夠記錄相關變量足夠的語義信息。抽象內存中的每一條數據稱之為一條記錄，每條記錄有唯一的地址標示，通過地址標示，訪問對應的抽象內存單元，該設計類似於資料庫的層次化存儲。以指針變量int*p為例，在抽象內存的指針區和數值區將會分別生成一條記錄。
表I抽象內存模型核心屬性
權利要求
1.一種基於抽象內存模型的非數值型數據的計算方法，其特徵在於，該方法包括 A、設計抽象內存模型用於模擬數值型變量和非數值型變量的內存結構，以及存儲變量操作中包含的語義信息和約束關係； B、提取數值型變量和非數值類型變量的類型操作中包含的語義信息，並將語義信息映射到抽象內存模型中； C、提取數值型變量和非數值類型變量的類型操作中包含的變量間約束和變量內約束，並將約束關係映射到抽象內存模型中； D、從抽象內存模型中提取變量的語義信息和約束關係，使用測試用例構建算法和第三方的約束求解器構建測試用例。
2.根據權利要求1所述基於抽象內存模型的非數值型數據的計算方法，其特徵在於，步驟A進一步包括使抽象內存主要用於存儲變量的語義信息,按C數據類型將抽象內存模型分為四個區數值區、數組區、結構體區和指針區。
3.根據權利要求1所述基於抽象內存模型的非數值型數據的計算方法，其特徵在於，所述步驟B包括 B1、對於數值類型的變量進行的語義操作包括使用變量名索引抽象內存是否存在對應的抽象內存記錄，若存在則返回抽象內存地址，若不存在，則在抽象內存中為該變量分配一個新的抽象內存單元，分配新的符號S表示該變量的取值域； B2、對於結構體類型變量的語義操作包括訪問結構體變量和訪問結構體變量的成員； B3、對於數組類型變量的語義操作包括訪問數組變量和通過數組下標訪問數組成員； B4、對於指針類型變量的語義操作包括訪問指針變量和訪問指針變量的指向域*，對於結構體指針變量，通過_>訪問變量成員，賦值操作改變指針的指向。
4.根據權利要求3所述基於抽象內存模型的非數值型數據的計算方法，其特徵在於，所述步驟B2具體為 B21、訪問結構體類型變量的語義操作包括使用變量名索引抽象內存是否存在對應的抽象內存記錄，若存在則返回抽象內存地址，若不存在，在抽象內存中為該變量分配一個新的抽象內存單元，返回該抽象內存的地址； B22、訪問結構體變量的成員的語義操作包括獲取結構體變量的抽象內存單元Ms，按成員變量名查找Ms中的成員屬性區，查看是否已為該成員分配抽象內存單元，若存在，返回該成員抽象內存單元，若不存在，按成員類型新建新的抽象內存單元，返回新建抽象內存單元的地址。
5.根據權利要求3所述基於抽象內存模型的非數值型數據的計算方法，其特徵在於，所述步驟B3具體為 B31、訪問數組變量的語義操作包括使用變量名索引抽象內存是否存在對應的抽象內存記錄，若存在則返回抽象內存地址，若不存在，則在抽象內存中為該變量分配一個新的抽象內存單元,返回該抽象內存的地址； B32、通過數組下標訪問數組成員的語義操作包括獲取數組變量的抽象內存單元Ma，按下標表達式查找Ma中的成員屬性區，查看是否已為該成員分配抽象內存單元，若存在，返回該成員抽象內存單元，若不存在，則按成員類型新建新的抽象內存單元，返回新建抽象內存單元的地址。
6.根據權利要求3所述基於抽象內存模型的非數值型數據的計算方法，其特徵在於，所述步驟B4具體為 B41、訪問指針變量的語義操作包括使用變量名索引抽象內存是否存在對應的抽象內存記錄，若存在則返回抽象內存地址，若不存在，則在抽象內存中為該變量分配一個新的抽象內存單元,返回該抽象內存的地址； B42、訪問指針的指向域的語義操作包括獲取指針變量的抽象內存單元Mp,查看Mp的指向域是否已經分配抽象內存單元，如果已經分配，返回該指向域的抽象內存單元，若不存在，按成員類型新建新的抽象內存單元，返回新建抽象內存單元； B43、訪問結構體指針的成員獲取指針變量指向域，如結構體類型的抽象內存地址Ms，獲取結構體的成員對應的抽象內存單元； B44、指針的賦值操作的語義操作包括獲取左指針的抽象內存地址，判定p是否是第一次被重定義，如果是則將其當前指向域Pt和指針狀態state分別存儲到初始指向域initPT和初始狀態initState中；然後獲取右指針的抽象內存地址,左指針的當前指向域Pt和指針狀態state分別被賦值為右指針的當前指向域pt和指針狀態state,表示它們指向相同的抽象內存單元； B45、指針的條件判斷操作，獲取左右指針指向域的抽象內存地址，取真值時，左右指針指向相同的指向域，合併左右指針的指向域為同一個；如果合併中出現矛盾，則此次測試用例生成失敗；如果取假值，則添加左右指針不可以相同抽象內存單元的約束； B46、指針的算術運算操作的語義操作包括，獲取指針指向域的抽象內存單元，在抽象內存模型中查找該指向域抽象內存單元是否在數組抽象內存區某一抽象內存單元的成員，如果存在返回該數組抽象內存單兀，如果不存在，則新建一數組抽象內存單兀；新建符號S表示指向域抽象內存單元在數組中的下標，添加下標成員到數組中，返回該數組抽象內存單元和下標符號S ;通過符號S進行指針的算術運算操作，然後添加運算後的下標對應的下標成員到數組中；再改變指針的指向到新的抽象內存單元； B47、指針的比較操作的語義操作與上述步驟B46類似。
7.根據權利要求1所述基於抽象內存模型的非數值型數據的計算方法，其特徵在於，所述步驟C具體包括 Cl、數值類型的操作包含算術運算+、_、*、/ ;邏輯運算 &&、||、！；條件判斷>、>=、〈、〈=、==;賦值語句=，+=, _，* =，/=;獲取表示數值類型取值的符號表達式，將符號表達式代入到操作表達式中，生成約束關係，存入數值抽象內存區的約束集中； C2、數組類型的操作包含取值操作[]，下標為常量或變量； C3、指針的賦值操作=;指針的條件判斷操作==，!=;指針的算術運算操作++、一、+、-;指針的比較操作>、>=、〈、〈=。
8.根據權利要求7所述基於抽象內存模型的非數值型數據的計算方法，其特徵在於，所述步驟C2具體為 C21、獲取數組變量的抽象內存單元，如果下標是常量const，建立數組長度len>=const的約束關係，為數組抽象內存單元添加下標為const的成員元素； C22、下標是變量var,為下標分配一塊數值型抽象內存，用var>=0初始化，並和數組長度Ien建立約束len>=Var，為數組抽象內存單元添加下標為const的成員元素。
9.根據權利要求7所述基於抽象內存模型的非數值型數據的計算方法，其特徵在於，所述步驟C3具體為 C31、對於指針的賦值f呆作=;添加左右指針互為別名的約束； C32、對於指針的條件判斷操作==，!=;取真值時，添加左右指針互為別名的約束，取假值時，添加左右指針不可以相同抽象內存單元的約束； C33、指針的算術運算操作++、一、+、-;添加指針變量與算術運算後的指針變量的地址偏移約束； C34、指針的比較操作>、>=、〈、<=;添加左右指針的地址偏移約束。
10.根據權利要求1所述基於抽象內存模型的非數值型數據的計算方法，其特徵在於，所述步驟D具體為 D1、路徑分析結束後，變量的非數值型約束和數值型約束都保存在抽象內存模型中，測試用例生成算法就是從抽象內存中按一定規則分別提取變量的數值型約束和非數值型約束，構建測試用例；其包括 D11、如果變量var是數值類型，獲取約束集中域中域變量var相關的約束關係，利用第三方約束求解器求解出滿足約束的值；如果求值失敗則此次測試用例生成過程失敗； D12、如果變量var為結構體類型，逐個為結構體的成員域遞歸調用測試用例構建算法，然後組裝成結構體變量var的值； D13如果變量var為數組類型，首先調用約束求解器求解下標和數組長度之間的約束，生成合適的長度和具體的下標，構建數組的形狀，然後逐個為下標對應的元素遞歸調用buildTestCase生成測試用例； D14、如果變量var為指針類型，獲取對應的抽象內存，若指針變量的狀態為空或不確定，則指針變量var為NULL ;指針變量的狀態為非空，獲取指向域，若指向域的inputFlag屬性取值為F，表明其指向的內存單元是在函數內存分配的，不屬於測試用例的一部分，因此指針變量var為NULL ;如果取值為T，則指針變量var不為空；獲取指針的指向域，按其類型遞歸調用測試用例構建算法。
全文摘要
本發明提供了一種基於抽象內存模型的非數值型數據的計算方法，包括A、設計抽象內存模型用於模擬數值型變量和非數值型變量的內存結構，以及存儲變量操作中包含的語義信息和約束關係；B、提取數值型變量和非數值類型變量的類型操作中包含的語義信息，並將語義信息映射到抽象內存模型中；C、提取數值型變量和非數值類型變量的類型操作中包含的變量間約束和變量內約束，並將約束關係映射到抽象內存模型；D、從抽象內存模型中提取變量的語義信息和約束關係，使用測試用例構建算法和第三方的約束求解器構建測試用例。採用本發明，可以克服現有技術無法精確支持非數值型變量程序語義的不足，實現包含非數值型的程序自動生成測試用例的目的。
文檔編號G06F11/36GK102999426SQ201210506230
公開日2013年3月27日 申請日期2012年11月30日 優先權日2012年11月30日
發明者王雅文, 宮雲戰, 金大海, 黃俊飛, 唐榮, 蔡敏 申請人:北京郵電大學