[發(fā)明專利]一種基于程序合成的C/C++程序缺陷自動修復(fù)方法

有效

• 申請?zhí)枺?/td>: 201711394256.5
• 申請日: 2017-12-21
• 公開（公告）號: CN108170466B
• 公開（公告）日: 2019-09-20
• 發(fā)明（設(shè)計）人: 王林章;陳天驕;李宣東
• 申請（專利權(quán)）人: 南京大學(xué)
• 主分類號: G06F8/72
• 分類號: G06F8/72;G06F8/30
• 代理公司: 南京知識律師事務(wù)所 32207
• 代理人: 張?zhí)K沛

1.一種基于程序合成的C/C++程序缺陷自動修復(fù)方法，其特征在于，該方法包括以下步驟：

步驟1)輸入帶有缺陷的C/C++程序，該程序在測試集S₁S₂...S_n上發(fā)現(xiàn)缺陷，存在缺陷d₁d₂...d_k；

步驟2)根據(jù)常見的C/C++程序缺陷和缺陷程序的類型，設(shè)定若干重寫規(guī)則，重寫規(guī)則包括缺陷模式和修復(fù)選項，其語法結(jié)構(gòu)為：expr->expr₁|expr₂…，箭頭前的表示缺陷模式，箭頭后的表示可能的修復(fù)選項，對于缺陷d_i，可能存在多種修復(fù)選項，分別記為c_i1c_i2...c_iu；

步驟3)將重寫規(guī)則的缺陷模式與缺陷程序進行匹配，找出所有匹配的重寫規(guī)則；

步驟3.1)將帶有缺陷的C/C++程序和重寫規(guī)則解析為抽象語法樹；

步驟3.2)將缺陷程序的抽象語法樹中的每顆子樹與重寫規(guī)則的缺陷模式進行匹配；

步驟3.3)若存在部分重寫規(guī)則與缺陷程序匹配，則表明該缺陷程序存在可能的修復(fù)選項；

步驟3.4)若不存在任何重寫規(guī)則與缺陷程序匹配，則表明本方法無法修復(fù)該程序的缺陷；

步驟4)若存在匹配的重寫規(guī)則，則將匹配的語法樹子樹替換為選擇表達式；

步驟5)將該程序需要滿足的規(guī)約記為f，規(guī)約約定了程序在特定輸入下需要滿足的輸出，使用程序合成方法，根據(jù)該程序的規(guī)約f，得到每個選擇表達式的選項；

步驟6)若步驟5)有解，則代入每個選擇表達式的選項，得到修復(fù)后的程序。

2.根據(jù)權(quán)利要求1所述的基于程序合成的C/C++程序缺陷自動修復(fù)方法，其特征在于：所述步驟4)若存在匹配的重寫規(guī)則，則將匹配的語法樹子樹替換為選擇表達式，具體步驟如下：

步驟4.1)對于每一個重寫規(guī)則，將每個匹配的語法樹子樹替換為選擇表達式，原始語法樹子樹作為該選擇表達式的第一顆子樹；

步驟4.2)將該重寫規(guī)則的若干個修復(fù)選項作為選擇表達式的后續(xù)子樹；

步驟4.3)將每個選擇表達式分別記為e₁e₂…e_m，若e_i取0則表明該選擇表達式的選項為第一顆子樹，即原始程序代碼，若e_i取1則表明該選擇表達式的選項為第二顆子樹，即該缺陷模式的第一個修復(fù)選項c_i1，依次類推。

3.根據(jù)權(quán)利要求1所述的基于程序合成的C/C++程序缺陷自動修復(fù)方法，其特征在于：所述步驟5)將該程序需要滿足的規(guī)約記為f，規(guī)約約定了程序在特定輸入下需要滿足的輸出，使用程序合成方法，根據(jù)該程序的規(guī)約f，得到每個選擇表達式的選項，具體步驟如下：

步驟5.1)將帶有選擇表達式的程序和該程序的規(guī)約轉(zhuǎn)化為邏輯表達式，格式如下：

S₁S₂...S_n為程序的測試用例，e_i表示每個選擇表達式的選項，f′為帶選擇表達式的程序，f為該程序需要滿足的規(guī)約；

步驟5.2)使用約束求解器，在設(shè)定的時間t內(nèi)，對上述的邏輯表達式進行求解，若對S₁S₂...S_n存在e₁e₂...e_n使得公式成立，則表明對于該程序的缺陷，本方法可以修復(fù)，若無解或超時，則本方法無法修復(fù)該程序的缺陷。

4.根據(jù)權(quán)利要求1所述的基于程序合成的C/C++程序缺陷自動修復(fù)方法，其特征在于：所述步驟6)若步驟5)有解，則代入每個選擇表達式的選項，得到修復(fù)后的程序，具體步驟如下：

步驟6.1)對于每個選擇表達式，將選項表示的子樹代替選擇表達式，得到修復(fù)后的語法樹；

步驟6.2)將語法樹輸出為C/C++代碼，得到修復(fù)后的程序。

5.根據(jù)權(quán)利要求1至4之一所述的基于程序合成的C/C++程序缺陷自動修復(fù)方法，其特征在于：本方法在多項式的時間復(fù)雜度內(nèi)實現(xiàn)缺陷修復(fù)。