[發明專利]用于符號執行的復雜類型輸入變量懶符號化方法及系統

在審

• 申請號: 202210453325.X
• 申請日: 2022-04-27
• 公開（公告）號: CN114896145A
• 公開（公告）日: 2022-08-12
• 發明（設計）人: 陳睿;楊帆;江云松;劉亞威;賈春鵬;施蘭蘭;車小鵬
• 申請（專利權）人: 北京軒宇信息技術有限公司
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 中國航天科技專利中心 11009
• 代理人: 馬全亮

一種用于符號執行的復雜類型輸入變量懶符號化方法及系統，包括生成輸入驅動文件，通過入口函數指定輸入變量和驅動被測函數；分配符號內存；當執行到一條語句時，解釋執行和符號執行分別對同一地址上的實際值和符號值進行操作；在執行過程中對內存地址訪問時，解釋執行直接讀寫實際值映射表內容；符號執行先檢查符號值映射表中該地址上是否存在符號值，存在則直接讀寫；不存在則創建一個新符號值，符號值映射表中新增一條地址與符號值的映射，再進行正常讀寫；一次符號執行結束后對收集的約束取反以及求解，最終得到表達式與值的映射關系，生成用例數據文件。本發明針對復雜類型的輸入變量，采用懶符號化策略，提升用例的生成速度和降低內存開銷。

技術領域

本發明涉及用于符號執行的復雜類型輸入變量懶符號化方法及系統，屬于程序測試技術領域。

背景技術

目前，符號執行技術由于其自動化、精確的特點已經被廣泛應用在各類測試用例生成方法和工具中。其基本原理是，對一個被測軟件或模塊的輸入變量符號化，并根據被測代碼的邏輯結構符號化地對代碼進行執行，執行過程中的程序狀態都采用有關輸入變量的符號表達式來刻畫，收集當前執行路徑的約束條件，并按照一定策略選擇該路徑上的一個分支點，將路徑約束條件中對應的約束取反，再對新產生的路徑約束條件進行求解，即可以產生一組關于輸入變量的解，也就是一個能夠覆蓋到指定路徑的用例；通過不斷迭代搜索，就可以生成覆蓋率很高的測試用例。

在此過程中，輸入變量的符號化決定了后續符號執行中約束條件符號表達式的準確性和復雜程度。特別是，當輸入變量為結構體、指針等復雜類型時，輸入變量的符號化涉及到根據具體的實際內存形態展開。例如，一個輸入變量為結構體指針，可能指向的是一個長度為N的鏈表，則對其最準確的符號化是對N個鏈表結點的具體數據和next成員進行符號化。

現有技術存在主要的問題是，在進行符號執行之前無法知道這個輸入變量的具體形態，因此一般的方法會要求用戶指定具體的符號化輸入，或提前按照給定展開深度來對變量進行符號化。通過用戶指定的方法自動化程度低，使用繁瑣。

發明內容

本發明的技術解決問題是：克服現有技術的不足，提供了用于符號執行的復雜類型輸入變量懶符號化方法及系統，針對復雜類型的輸入變量，采用懶符號化策略，有針對性地對輸入變量進行符號化，從而提升用例的生成速度和降低內存開銷。

本發明的技術解決方案是：

一種用于符號執行的復雜類型輸入變量懶符號化方法，包括：

(1)生成輸入驅動文件，通過入口函數指定輸入變量和驅動被測函數；

(2)分配符號內存：通過解釋執行驅動符號執行的方式從入口函數開始執行，先進行內存分配，記錄如下3個映射關系：變量分配地址映射表var_addr_map、實際值映射表value_map和符號值映射表sym_map；

(3)當執行到一條語句時，解釋執行和符號執行分別對同一地址上的實際值和符號值進行操作；一個變量或表達式在實際值映射表value_map和符號值映射表sym_map中的地址完全一致；

(4)在執行過程中對內存地址訪問時，解釋執行直接讀寫實際值映射表value_map中的內容；符號執行需先檢查符號值映射表sym_map中該地址上是否存在符號值，若存在則直接讀寫；若不存在則創建一個新符號值，符號值映射表sym_map中新增一條地址與符號值的映射，然后進行正常讀寫操作；當執行到分支節點時由解釋執行決定下一個待執行語句，符號執行把該分支節點判定語句的符號值添加到約束中；

(5)一次符號執行結束后對收集的約束取反以及求解，得到符號值對應的值，進一步得到內存地址與值的對應關系，然后轉換為輸入表達式與值的映射關系，生成用例數據文件；

(6)執行過程結束。

進一步的，生成輸入驅動文件時，直接把變量整體指定為輸入，復雜類型變量不展開為子表達式。