一種改進的基於符號執行的軟體靜態測試方法及工具的製作方法
2023-05-06 22:38:56
專利名稱：一種改進的基於符號執行的軟體靜態測試方法及工具的製作方法
技術領域：
本發明涉及一種改進的基於符號執行的軟體靜態測試方法及工具，屬於軟體的靜態測試技術領域。
背景技術：
軟體測試技術通常分為靜態測試和動態測試。動態測試就是執行程序，再觀察其行為是否滿足要求。既可由用戶直接觀察，也可以使用一定的輔助工具。靜態測試是不執行程序代碼而尋找程序代碼中可能存在的缺陷或評估程序代碼的過程，程序靜態測試的目標不是證明程序完全正確，而是作為動態測試的補充，在程序運行前儘可能多的發現其中隱含的錯誤，提高程序的可靠性和健壯性，靜態測試在更高的抽象層次上對程序的某些屬性進行考察，而不是對程序的某一個特定輸入的考察。現在國內對於靜態測試中的符號執行方法方面的研究並不是很充分，國內比較著名的是北京航空航天大學軟體研究所開發的Mfeftx) C/C++, SafePro C/C++提供多選窗口單驅動的用戶工作環境，支持若干種測試信息的快速關聯分析，提供了圖文並茂的軟體測試結果報告，同時支持靜態和動態測試。在這些已有的軟體靜態測試理論和測試工具中，一般仍然或多或少存在以下不足(1)對符號執行功能模塊沒有得到充分重視和實現；(2)對隱含的代碼錯誤測試效果不好，如果再次測試將花費大量的人力物力。
發明內容
本發明目的是針對現有技術存在的缺陷提供一種改進的基於符號執行的軟體靜態測試方法及工具。本發明公布了一種改進的基於符號執行的軟體靜態測試方法，已經開發包含該方法的面向宿主的軟體自動化測試工具。其特徵在於包括如下步驟1、第一階段分析。其中包括1. 1)將被測代碼輸入測試工具中；1. 2)根據C語言文法自定義一個關鍵詞列表，並對照關鍵詞列表對被測試代碼進行詞法分析；1. 3)根據C語言文法自定義函數結構模塊、構造抽象語法樹的生成算法，並對照詞法分析的結果，利用「自下而上」的方法(即從從語法樹的末端開始，步步向上「歸約」)， 對被測代碼進行語法分析，最終得到程序靜態分析樹(PAT)作為一個中間表示形式，並且利用文檔進行存儲；2、第二階段分析。其中包括2. 1)根據第一階段分析步驟(1. 2)中的詞法分析結果，以特定結構體的形式(包含變量名稱及變量的符號值)建立變量列表、以鍊表的形式存儲當前路徑條件(便於回溯)；2. 2)根據第一階段分析步驟(1. 3)中的語法分析結果，對程序靜態分析樹進行中序遍歷，同時對變量列表中變量的符號值進行替換；將步驟(2. 1)中存儲的路徑條件進行約束求解得到可執行路徑，並且依照算法得到每個變量最終的符號執行結果，最終以文本的格式保存。本發明出了可以進行傳統符號執行得到相應的結果之外，還可以根據C語言的文法，對於程序中潛在的錯誤進行報錯，例如whileO語句中若循環條件為空，則會自動報錯，因此通用性比較強的。
圖1:本發明工作流程圖；圖2 本發明語法分析過程流程圖；圖3 本發明符號執行過程流程具體實施例方式下面結合附圖1、圖2、圖3對本發明的工作流程進行詳細說明。基於符號執行的軟體靜態測試方法，有如下軟體測試步驟1、第一階段分析，具體步驟如圖2所示，其中包括1. 1)將被測代碼輸入測試工具中；1. 2)根據C語言文法自定義一個關鍵詞列表，並對照關鍵詞列表對被測試代碼進行詞法分析；1. 3)根據C語言文法自定義函數結構模塊、構造抽象語法樹的生成算法，並對照詞法分析的結果，利用「自下而上」的方法(即從從語法樹的末端開始，步步向上「歸約」)， 對被測代碼進行語法分析，最終得到程序靜態分析樹(PAT)作為一個中間表示形式，並且最終用樹形控制項進行顯示；其中，步驟(1.2)進一步包括(1.2.1)建立一個關鍵詞列表，該關鍵詞列表包含有C語言文法中的大部分關鍵詞；(1.2. 2)將被測代碼保存於臨時文件中，以讀文件的方式，將被測代碼讀入詞法分析模塊；(1. 2. 3)根據所讀出字符的不同類型，進入相應的掃描狀態(例如若讀取字符為a-z或A-Z中的一個，則進入INID掃描狀態，繼續讀取下一個字符，以此類推直至遇到終結符為止)；(1.2. 4)若詞法分析的返回值是關鍵詞列表中的成員，則調用替換函數返回相應的替換值；詞法分析直至文件中內容被全部讀完方才結束；其中，步驟(1.3)進一步包括(1. 3.1)根據C語言的文法，定義相應的函數模塊(順序模塊、循環模塊、分支模塊等)，比如在程序中預先定義if模塊iretatement、 while 模塊 WhileStatement、Switch. . . case 模塊 SwitchStatement 等等；(L 3. 2)根據詞法分析的返回值，判斷屬於已定義的函數模塊中的那一項，並進入相應的靜態語法樹構造函數(以下步驟都是以if模塊iretatement為例)；(1. 3. 3)讀取if語句的條件，並且判斷是否有合取範式(CNF)、析取範式(DNF)，按照設計沿著函數嵌套調用，此過程依次為 Boolean - > T2 - > F2 ，在函數F2中我們可以得到具體的條件約束符(大於、小於、等於等等)，並且創建相應的抽象語法樹Ftree然後將F2 的抽象語法樹Ftree作為返回值返回給T2函數，並且判斷條件中是否存在合取範式(CNF)。若存在合取關係，則首先創建 「and」類型的抽象語法樹Ttree (這裡將之前返回的Ftree作為其左節點)，將同時再次調用 F2 0返回下一棵抽象語法樹；若不存在合取關係，則直接將抽象語法樹Ftree作為T2 0函數的返回值，返回給BooleanO函數，並且判斷若條件中是否存在析取範式(DNF)，若不存在析取關係，則直接返回Ftree作為最終的描述if模塊中條件部分的語法樹；若存在析取關係，則首先創建「or」類型的抽象語法樹Booltree，將T2 0函數返回的語法樹作為其左節點，並且再次調用T20- > F2 0，返回下一棵抽象語法樹作為其右節點，依次類推，最終可以規約出一顆總的抽象語法樹B00Itree來完成將if模塊中條件部分進行正確描述；採用相類似的函數嵌套調用的語句塊，我們可以順利地讀取滿足if條件後的代碼段(即所謂的 then子抽象語法樹)，並且建立相應的抽象語法子樹，對其進行正確描述；同理可以得到不滿足if條件的代碼塊(即else子抽象語法樹)，也可以為空；(1.3. 4)建立If^tatement模塊抽象語法樹，並且將通過(1. 3. 2)建立的抽象語法子樹作為其左節點，將通過(1. 3. 3)建立的抽象語法子樹作為其右節點；(1. 3. 5)將被測代碼中所有的抽象語法子樹(可能包含順序模塊、循環模塊、分支模塊等)通過C語言語法進行整合，最終利用「自下而上」的語法分析方法(即從從語法樹的末端開始，步步向上「歸約」)生成一顆總的抽象語法樹(PAT)；2、第二階段分析。具體步驟如圖3所示，其中包括2. 1)根據第一階段分析步驟(1. 2)中的詞法分析結果，建立變量列表(包含變量名稱及變量的符號值)、以鍊表的形式存儲當前路徑條件(便於回溯)；2. 2)根據第一階段分析步驟(1. 3)中的語法分析結果，對程序靜態分析樹進行遍歷，同時對變量列表中變量的符號值進行替換；依照程序的可執行路徑得到每個變量最終的符號執行結果，最終可以與預期的結果進行比較。其中步驟(2. 1)進一步包括(2. 1. 1)通過第一階段分析步驟(1. 2)中的詞法分析的返回值建立變量列表Syn^taCk(用棧的方式進行存儲)，我們知道C語言中變量的類型一般包括char (字符型)，double (雙精度)，float (單精度)，int (整形)，long (長整形)等，這裡我們通過詞法分析返回的單詞符號(根據C語言中定義變量時，先定義變量的類型這一語法來查找到所有的變量)建立變量列表Syn^tack，變量列表包括變量名和變量的符號值(初始化變量的符號值時，默認為與變量名相同)；(2. 1.2)通過第一階段分析步驟(1.2)中的詞法分析的結果存儲當前的路徑條件(使用了一個用鍊表表示的棧cur_pC 來存儲，鍊表的節點是一個轉換條件，條件之間是合取關係)；其中步驟(2. 進一步包括(2. 2.1)通過第一階段分析步驟(1. 得到建立的抽象語法子樹，利用中根遍歷的方法對其進行遍歷(每當遍歷到一個變量結點時，在 Syn^tack表中查找相應的變量名，並將找到的變量相應的符號值賦給語句中各個變量，對其所得到的符號表達式進行運算，得到了執行賦值語句後的變量的符號值)；(2. 2. 通過第二階段步驟(2. 1)得到當前的路徑條件，並且求解工具lp_S0lVe對於路徑約束條件進行求解，來判斷是否為可執行路徑)，之後將變量列表Syn^tack中屬於可執行路徑的變量賦值記錄進行處理(即將該節點進行入棧處理)，以此類推，依照程序的可執行路徑得到每個變量最終的符號執行結果，可以通過與預期結果的比較來驗證本符號執行工具的可靠性。3、優勢與創新本發明對現有技術有以下的改進和創新
(1)根據本發明的技術，我們已經開發了基於符號執行的軟體靜態測試工具；(2)通用性強，對於以C語言編寫的代碼有具有一定的適用性；(3)根據C語言的文法，對於程序中潛在的錯誤進行報錯，可以說具備了小型編譯器的一些特點；(4)利用約束求解工具完成了對於可執行路徑的自動判別，從而可以最終得到程序按可執行路徑運行後的符號執行結果。
權利要求
1. 一種改進的基於符號執行的軟體靜態測試方法及工具，已經開發包含該方法的面向宿主的軟體自動化測試工具，其特徵在於包括如下步驟1、第一階段分析。其中包括1.1)將被測代碼輸入測試工具中；1. 2)根據C語言文法自定義一個關鍵詞列表，並對照關鍵詞列表對被測試代碼進行詞法分析；1.3)根據C語言文法自定義函數結構模塊、構造抽象語法樹的生成算法，並對照詞法分析的結果，利用「自下而上」的方法(即從從語法樹的末端開始，步步向上「歸約」)，對被測代碼進行語法分析，最終得到程序靜態分析樹(PAT)作為一個中間表示形式，並且利用文檔進行存儲，且利用樹型控制項進行顯示；2、第二階段分析。其中包括2. 1)根據第一階段分析步驟(1. 2)中的詞法分析結果，以特定結構體的形式(包含變量名稱及變量的符號值)建立變量列表、以鍊表的形式存儲當前路徑條件(便於回溯)；2.2)根據第一階段分析步驟(1.3)中的語法分析結果，對程序靜態分析樹進行中序遍歷，同時對變量列表中變量的符號值進行替換；將步驟(2. 1)中存儲的路徑條件進行約束求解得到可執行路徑，並且依照算法得到每個變量最終的符號執行結果，最終以文本的格式保存。
2.根據權力要求1所述的改進的基於符號執行的軟體靜態測新技術，其特徵在於增加了判斷可執行路徑的模塊(利用了約束求解工具lp_solVe對於路徑約束條件進行求解，來判斷是否為可執行路徑)。
全文摘要
本發明公布了一種改進的基於符號執行的軟體靜態測試方法及工具，有如下步驟1、第一階段分析。其中包括1.1)將被測代碼輸入測試工具中；1.2)根據C語言文法自定義一個關鍵詞列表進行詞法分析；1.3)根據C語言文法自定義函數結構模塊及算法對代碼進行語法分析得到程序靜態分析樹；2、第二階段分析。其中包括2.1)根據步驟(1.2)中詞法分析結果，以結構體的形式(包含變量名稱及變量的符號值)建立變量列表、以鍊表的形式存儲當前路徑條件；2.2)根據步驟(1.3)中語法分析結果，對程序靜態分析樹進行中序遍歷，將步驟(2.1)中存儲的路徑條件進行約束求解得到可執行路徑，得到變量最終的符號執行結果。本發明能夠克服在其他靜態測試中不能確定程序中變量的值的問題。
文檔編號G06F11/36GK102262580SQ201010180129
公開日2011年11月30日 申請日期2010年5月24日 優先權日2010年5月24日
發明者劉久富, 婁堅波, 李金奎, 王偉, 蘇青琴, 陳魁 申請人:南京航空航天大學