李 斌 賀也平,3 馬恒太 芮建武 李曉卓

1(中國科學(xué)院大學(xué) 北京 100049) 2(中國科學(xué)院軟件研究所基礎(chǔ)軟件國家工程研究中心 北京 100190) 3(計(jì)算機(jī)科學(xué)國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院軟件研究所) 北京 100190)

Linux驅(qū)動(dòng)程序是操作系統(tǒng)中非常重要的系統(tǒng)組件且代碼體量龐大，占據(jù)Linux內(nèi)核大約70%的代碼量[1].在實(shí)際操作系統(tǒng)研發(fā)中，如何使設(shè)備驅(qū)動(dòng)程序跟上對應(yīng)操作系統(tǒng)其他部分的版本演進(jìn)是當(dāng)前面臨的最大問題之一[2].當(dāng)Linux內(nèi)核版本升級后，由于內(nèi)核版本的升級可能引入一些內(nèi)核接口服務(wù)的變更，使得驅(qū)動(dòng)程序代碼中一些內(nèi)核接口調(diào)用不再適應(yīng)更新后的內(nèi)核版本，導(dǎo)致原有驅(qū)動(dòng)程序在新的內(nèi)核環(huán)境中由于不相適配可能產(chǎn)生不一致性錯(cuò)誤[3].為了適配頻繁變化的內(nèi)核版本并維持已有設(shè)備在新內(nèi)核環(huán)境中的可用性，開發(fā)者需要針對驅(qū)動(dòng)程序代碼進(jìn)行持續(xù)的適配性修改并完成驅(qū)動(dòng)程序移植.然而內(nèi)核版本變更對驅(qū)動(dòng)程序帶來的關(guān)聯(lián)影響程度和影響范圍都很大，由于Linux內(nèi)核版本的變更使得對應(yīng)驅(qū)動(dòng)程序在移植中所需的適配性修改代碼行高達(dá)35%以上[3]，Linux內(nèi)核版本中引入的單一變更可能會影響驅(qū)動(dòng)程序中分布在許多不同文件中的數(shù)百個(gè)代碼調(diào)用點(diǎn)[4].因此，開發(fā)者手工進(jìn)行適配性修改完成這種移植工作通常工作量繁重、效率較低，而且還可能引入新的錯(cuò)誤.

針對上述問題，研究者們在驅(qū)動(dòng)移植中間庫輔助適配[5-6]和驅(qū)動(dòng)移植輔助信息[7-8]等方面開展了研究.這些工作從提高輔助示例的檢索精度和效率角度，通過提供輔助示例在一定程度上減輕了驅(qū)動(dòng)移植開發(fā)者的負(fù)擔(dān).但是還需要開發(fā)者進(jìn)一步分析輔助示例和出錯(cuò)代碼并人工構(gòu)造適配性補(bǔ)丁，人工修復(fù)的工作量依然較大并且效率較低.為此，本文針對驅(qū)動(dòng)移植場景中接口調(diào)用不一致錯(cuò)誤，通過推薦高質(zhì)量補(bǔ)丁降低人工修復(fù)錯(cuò)誤的工作量并提高修復(fù)效率.Tao等人[9]通過實(shí)證研究也指出，相比輔助示例，如果有高質(zhì)量的補(bǔ)丁輔助開發(fā)者，錯(cuò)誤修復(fù)的正確率和效率都會大幅提升.

補(bǔ)丁推薦和程序自動(dòng)修復(fù)[10-14]雖然都要針對具體錯(cuò)誤生成補(bǔ)丁，但是二者在錯(cuò)誤定位和補(bǔ)丁質(zhì)量判定方面存在不同.補(bǔ)丁推薦[15]是針對程序中的錯(cuò)誤生成補(bǔ)丁并建議合適補(bǔ)丁的過程，最終由開發(fā)者手工判定補(bǔ)丁質(zhì)量.本文的工作主要是針對驅(qū)動(dòng)移植場景中的接口不一致錯(cuò)誤生成補(bǔ)丁并進(jìn)行補(bǔ)丁推薦.

驅(qū)動(dòng)移植場景中的接口調(diào)用不一致錯(cuò)誤實(shí)際上是一類比較有特點(diǎn)的具體錯(cuò)誤，由于不同驅(qū)動(dòng)程序通過統(tǒng)一的內(nèi)核接口服務(wù)大量復(fù)用內(nèi)核接口，因此Linux內(nèi)核版本升級引起的某個(gè)單點(diǎn)內(nèi)核接口定義變化會導(dǎo)致多個(gè)驅(qū)動(dòng)程序中該復(fù)用接口的不同調(diào)用點(diǎn)產(chǎn)生同類不一致錯(cuò)誤.針對一般的錯(cuò)誤，早期的研究[16-19]利用遺傳算法對可復(fù)用的代碼碎片進(jìn)行交叉變異生成補(bǔ)丁，然而這種隨機(jī)變異會產(chǎn)生大量無意義的補(bǔ)丁.為了提高補(bǔ)丁的質(zhì)量，研究發(fā)現(xiàn)很多錯(cuò)誤具有相同類型，一組同類錯(cuò)誤的修復(fù)實(shí)例中實(shí)際上隱含了修復(fù)模板，因此針對未修復(fù)的同類錯(cuò)誤可以在修復(fù)模板的約束和指導(dǎo)下生成補(bǔ)丁.其主要包含2個(gè)關(guān)鍵問題：1)識別同類錯(cuò)誤用于提取和選擇修復(fù)模板;2)基于修復(fù)模板生成補(bǔ)丁.修復(fù)模板抽象化了一組同類錯(cuò)誤和對應(yīng)補(bǔ)丁之間隱含的共性變更，基于修復(fù)模板生成補(bǔ)丁則是確定多樣化的代碼元素將選擇的抽象修復(fù)模板具體化的過程.由此，已有研究從提取修復(fù)模板[20-24]、選擇修復(fù)模板[25-29]和確定多樣化的具體代碼元素[30-36]這3個(gè)角度展開.

本文通過研究提取修復(fù)模板和選擇修復(fù)模板這2個(gè)角度，實(shí)現(xiàn)高質(zhì)量補(bǔ)丁推薦：

1) 傳統(tǒng)方法提取修復(fù)模板主要通過相似度聚類來識別哪些是已修復(fù)的同類錯(cuò)誤，并通過抽象化修復(fù)代碼變更的共性提取修復(fù)模板.已有研究通過刻畫錯(cuò)誤和對應(yīng)補(bǔ)丁之間的變更特點(diǎn)[20-22]、錯(cuò)誤和對應(yīng)補(bǔ)丁所在上下文特點(diǎn)[23]，從句法或者語法層面進(jìn)行相似度聚類，將代碼變更通過遷移序列、抽象語法樹(abstract syntax tree, AST)進(jìn)行刻畫，通過挖掘頻繁序列、識別等價(jià)樹提取修復(fù)模板.這些基于語法相似度的方法適合挖掘高頻的原子變更模板，但是由于缺少語義依賴關(guān)系而對于由多個(gè)原子變更組成的復(fù)合模板挖掘存在限制.還有學(xué)者研究通過數(shù)據(jù)流和控制流圖連接了從錯(cuò)誤到對應(yīng)補(bǔ)丁之間涉及的變更元素所對應(yīng)的語義依賴關(guān)系[24]，通過識別同構(gòu)圖挖掘重復(fù)的代碼變更進(jìn)行聚類，因此可以提取具有語義關(guān)聯(lián)的復(fù)合模板.但是這2類基于語法和語義相似度的方法都是通過錯(cuò)誤代碼形式識別哪些是同類錯(cuò)誤的修復(fù)實(shí)例，即錯(cuò)誤和對應(yīng)補(bǔ)丁所在語句是錯(cuò)誤的形式特征.針對一些本質(zhì)上錯(cuò)誤類型相同但表現(xiàn)形式不同的錯(cuò)誤，則文獻(xiàn)[20-24]的方法會存在識別同類錯(cuò)誤范圍狹窄的問題.本文研究的驅(qū)動(dòng)移植接口不一致錯(cuò)誤也是這樣一類具體錯(cuò)誤，該類錯(cuò)誤雖然復(fù)用相同內(nèi)核接口但是所在的調(diào)用點(diǎn)不同(所在驅(qū)動(dòng)程序不同以及源代碼文件位置不同)，不同調(diào)用點(diǎn)的同類錯(cuò)誤所在語句類型、上下文等表現(xiàn)形式可能不同[4].如果直接使用文獻(xiàn)[20-24]的傳統(tǒng)方法將出現(xiàn)把相同錯(cuò)誤區(qū)分為不同錯(cuò)誤，導(dǎo)致應(yīng)該提取1個(gè)修復(fù)模板但實(shí)際提取了多個(gè)不同修復(fù)模板的問題.

2) 選擇修復(fù)模板，要解決的主要問題是區(qū)分待修復(fù)錯(cuò)誤的特征來選擇合適的修復(fù)模板，其核心思想是同類錯(cuò)誤共享同一個(gè)修復(fù)模板.一些研究工作[25-26]通過模板頻度信息作為權(quán)重進(jìn)行傾向性選擇，相當(dāng)于假設(shè)待修復(fù)錯(cuò)誤都是常見錯(cuò)誤，并沒有考慮待修復(fù)錯(cuò)誤的具體特點(diǎn).另一些研究工作[27-29]通過錯(cuò)誤的上下文特點(diǎn)選擇合適的模板，認(rèn)為上下文相似(如錯(cuò)誤所在語句類型和修復(fù)模板附帶的語句類型信息相似)則識別為同類錯(cuò)誤，也是依據(jù)錯(cuò)誤代碼形式的特點(diǎn)識別同類錯(cuò)誤.在錯(cuò)誤相同但表現(xiàn)形式不同的驅(qū)動(dòng)移植接口不一致錯(cuò)誤中，如果直接使用文獻(xiàn)[25-29]的傳統(tǒng)方法將可能出現(xiàn)把相同錯(cuò)誤區(qū)分為不同錯(cuò)誤，導(dǎo)致應(yīng)該選擇1個(gè)修復(fù)模板卻實(shí)際選擇了多個(gè)不同修復(fù)模板的問題.

總之，將相同錯(cuò)誤識別為不同錯(cuò)誤，提取和選擇不恰當(dāng)?shù)男迯?fù)模板都會嚴(yán)重影響補(bǔ)丁的質(zhì)量[37].

與已有研究通過錯(cuò)誤代碼形式的相似性識別同類錯(cuò)誤的思想不同，本文提出通過分析錯(cuò)誤自身的原因和來源識別同類錯(cuò)誤.更具體地說，錯(cuò)誤根因信息刻畫了錯(cuò)誤發(fā)生的原因和來源，引入錯(cuò)誤變更(error-inducing changes, EIC)就是一種根因信息.本文通過分析和待修復(fù)錯(cuò)誤具有相同引入錯(cuò)誤變更信息識別同類錯(cuò)誤修復(fù)實(shí)例，從同類錯(cuò)誤修復(fù)實(shí)例提取并選擇針對性修復(fù)模板實(shí)現(xiàn)同類待修復(fù)錯(cuò)誤的高質(zhì)量補(bǔ)丁推薦.Wen等人[38]通過實(shí)證研究分析了引入錯(cuò)誤變更信息和修復(fù)補(bǔ)丁之間的關(guān)系，也指出利用引入錯(cuò)誤變更素材提高補(bǔ)丁的質(zhì)量具有一定實(shí)證基礎(chǔ).我們觀察發(fā)現(xiàn)：相同內(nèi)核接口在驅(qū)動(dòng)程序的多個(gè)不同代碼調(diào)用點(diǎn)存在接口復(fù)用現(xiàn)象，由于接口復(fù)用這些不同的接口調(diào)用點(diǎn)依賴相同的內(nèi)核接口來源.Linux內(nèi)核升級之后，在Linux內(nèi)核主線版本的驅(qū)動(dòng)程序歷史開發(fā)信息中，可能存在針對內(nèi)核版本升級引入的接口不一致問題的同類錯(cuò)誤修復(fù)實(shí)例.因此，可以通過識別這些同類錯(cuò)誤修復(fù)實(shí)例的共性信息提取并選擇修復(fù)模板，用于實(shí)現(xiàn)同類未修復(fù)錯(cuò)誤的高質(zhì)量補(bǔ)丁推薦.雖然這些復(fù)用接口的修復(fù)實(shí)例分布在不同驅(qū)動(dòng)程序的不同文件中，不同調(diào)用點(diǎn)所在的語句類型和上下文等具體表現(xiàn)形式可能不同，但是同類復(fù)用接口具有相同的錯(cuò)誤原因和來源.本文通過根因信息(即引入錯(cuò)誤變更)識別同類修復(fù)實(shí)例提取并選擇針對性修復(fù)模板的技術(shù)路線更加合理.

實(shí)現(xiàn)基于根因識別同類錯(cuò)誤的思路包含2個(gè)方面的技術(shù)困難：1)針對某個(gè)出錯(cuò)接口，在龐大的歷史開發(fā)信息中找到對應(yīng)的引入錯(cuò)誤變更信息并不容易.這些引入錯(cuò)誤變更信息可能是多樣化的并且嵌入在歷史開發(fā)的提交信息之中[39]，而且歷史信息中的混合提交又進(jìn)一步給引入錯(cuò)誤變更信息的獲取帶來了噪聲和干擾[40].2)針對同類錯(cuò)誤修復(fù)實(shí)例的識別，獲取與待修復(fù)錯(cuò)誤具有相同出錯(cuò)原因的同類錯(cuò)誤修復(fù)實(shí)例是關(guān)鍵問題.即使準(zhǔn)確找到了出錯(cuò)接口對應(yīng)的引入錯(cuò)誤變更信息，借助引入錯(cuò)誤變更信息獲取同類修復(fù)實(shí)例并不簡單.由于錯(cuò)誤表現(xiàn)形式的多樣性，一些修復(fù)實(shí)例往往包含個(gè)性化代碼元素，潛在的同類錯(cuò)誤修復(fù)實(shí)例語句與待修復(fù)錯(cuò)誤所在的語句、引入錯(cuò)誤變更語句可能并不直接相似.因此，僅僅使用簡單的匹配技術(shù)或者相似度計(jì)算并不能準(zhǔn)確地分析出待修復(fù)錯(cuò)誤、引入錯(cuò)誤變更和潛在的同類錯(cuò)誤修復(fù)實(shí)例三者之間的關(guān)系，因?yàn)樗鼈兊墓残蕴卣麟[藏在語句內(nèi)部的局部位置[41].

為了提取出錯(cuò)語句對應(yīng)的引入錯(cuò)誤變更信息，本文提出了一種基于編譯的分層檢索算法.依據(jù)引入錯(cuò)誤變更信息的分層結(jié)構(gòu)特點(diǎn)和提交時(shí)序特點(diǎn)，本文先識別引入錯(cuò)誤提交(error-inducing commits, EICommits)再分析該提交信息所包含的潛在文件變更，對文件變更包含的代碼塊進(jìn)行更細(xì)粒度切分，在切分的代碼塊變更集合中找到引入錯(cuò)誤變更信息.在獲取與待修復(fù)錯(cuò)誤對應(yīng)的同類錯(cuò)誤修復(fù)實(shí)例時(shí)，面臨歷史開發(fā)信息龐大、待修復(fù)出錯(cuò)語句和對應(yīng)引入錯(cuò)誤變更與潛在的同類修復(fù)實(shí)例共性隱含在局部位置的問題.本文首先通過出錯(cuò)接口信息和啟發(fā)式規(guī)則，在歷史開發(fā)信息中獲取一個(gè)候選修復(fù)實(shí)例集合.然后通過引用關(guān)系分析，從候選實(shí)例集合中檢索哪些實(shí)例與待修復(fù)出錯(cuò)語句引用了相同的引入錯(cuò)誤變更.因?yàn)楣餐x變更(錯(cuò)誤根因)的關(guān)聯(lián)影響產(chǎn)生了多個(gè)不同調(diào)用點(diǎn)的同類接口錯(cuò)誤及其修復(fù)實(shí)例，由此將具有相同錯(cuò)誤原因的實(shí)例確定為一組同類修復(fù)實(shí)例.最后，我們實(shí)現(xiàn)了基于錯(cuò)誤根因進(jìn)行驅(qū)動(dòng)移植接口補(bǔ)丁推薦的方法RCFix(root cause based fix)，采用迭代方式逐個(gè)接口錯(cuò)誤進(jìn)行補(bǔ)丁推薦，通過人工判定補(bǔ)丁質(zhì)量.在收集的19個(gè)真實(shí)驅(qū)動(dòng)程序數(shù)據(jù)集上進(jìn)行檢驗(yàn)，本文的方法推薦補(bǔ)丁的top-1，top-2，top-5正確率分別為58.7%，60.6%，66.1%，針對每款驅(qū)動(dòng)程序補(bǔ)丁推薦的平均耗時(shí)大約在14 min以內(nèi).相比傳統(tǒng)的方法，本文的方法有效輔助開發(fā)者降低了錯(cuò)誤修復(fù)的工作量并提高了修復(fù)效率.

本文的主要貢獻(xiàn)有3個(gè)方面：

1) 針對傳統(tǒng)方法通過錯(cuò)誤代碼形式的相似性識別同類錯(cuò)誤中存在的識別范圍狹窄的問題，提出基于錯(cuò)誤根因識別同類錯(cuò)誤的補(bǔ)丁推薦方法.相比傳統(tǒng)方法，本文通過錯(cuò)誤根因能夠更好地識別本質(zhì)是同類錯(cuò)誤但錯(cuò)誤代碼形式不相似的問題.根據(jù)現(xiàn)有文獻(xiàn)調(diào)研分析，這是一種比較新穎的思路.

2) 提出了一種基于編譯的分層檢索算法，用于獲取待修復(fù)錯(cuò)誤對應(yīng)的根因信息(即引入錯(cuò)誤變更)，其正確率達(dá)到80.7%.利用相同錯(cuò)誤根因識別同類錯(cuò)誤修復(fù)實(shí)例，進(jìn)而從同類錯(cuò)誤修復(fù)實(shí)例提取并選擇針對性修復(fù)模板實(shí)現(xiàn)同類待修復(fù)錯(cuò)誤的高質(zhì)量補(bǔ)丁推薦.

3) 檢驗(yàn)了基于錯(cuò)誤根因進(jìn)行驅(qū)動(dòng)移植接口補(bǔ)丁推薦的有效性，實(shí)驗(yàn)表明本方法推薦補(bǔ)丁的top-5正確率達(dá)到66.1%，相比傳統(tǒng)方法的補(bǔ)丁推薦正確率有顯著提高.

1 動(dòng) 機(jī)

在驅(qū)動(dòng)程序移植場景中，由于內(nèi)核版本變更引入的接口變化導(dǎo)致驅(qū)動(dòng)程序接口調(diào)用與內(nèi)核提供的接口不相適配，需要針對驅(qū)動(dòng)程序引入適配性補(bǔ)丁使其在更新后的內(nèi)核環(huán)境中維持現(xiàn)有功能可用.我們對內(nèi)核和驅(qū)動(dòng)程序開發(fā)歷史信息進(jìn)行了分析，如圖1是因特爾網(wǎng)卡e1000驅(qū)動(dòng)程序從Linux-3.5移植到Linux-4.0過程中的一個(gè)出錯(cuò)點(diǎn)，該錯(cuò)誤是宏NETIF_F_HW_VLAN_RX支持硬件操作VLAN的標(biāo)簽.代碼文件e1000_main中行818的-語句出錯(cuò)，應(yīng)該修改為對應(yīng)的+語句，即本文期望生成行819的+語句補(bǔ)丁并推薦給開發(fā)者.

drivers∕net∕ethernet∕intel∕e1000∕e1000_main.c818-if(features & NETIF_F_HW_VLAN_RX) ∕*錯(cuò)誤語句*∕819+if(features & NETIF_F_HW_VLAN_CTAG_RX) ∕*修復(fù)語句*∕??

1.1 修復(fù)實(shí)例

我們分析了移植區(qū)間(Linux-3.5至Linux-4.0)中其他驅(qū)動(dòng)程序的開發(fā)歷史信息.我們發(fā)現(xiàn)內(nèi)核版本升級之后，由于內(nèi)核接口復(fù)用，一些其他驅(qū)動(dòng)程序的歷史開發(fā)信息中包含了同類錯(cuò)誤修復(fù)實(shí)例.如圖2是宏NETIF_F_HW_VLAN_RX的修復(fù)實(shí)例，其中2個(gè)實(shí)例是瑞昱網(wǎng)卡r8169驅(qū)動(dòng)和因特爾igb驅(qū)動(dòng)程序針對Linux內(nèi)核中的宏NETIF_F_HW_VLAN_RX的使用和變更情況.

進(jìn)一步分析發(fā)現(xiàn)，出錯(cuò)語句和實(shí)例語句之間存在共性的同時(shí)也存在差異性.圖2的實(shí)例中修復(fù)了和圖1相同的宏NETIF_F_HW_VLAN_RX的錯(cuò)誤，但是出錯(cuò)語句形式不同，圖1的錯(cuò)誤是條件語句而圖2的錯(cuò)誤是賦值語句.如果從工具的角度僅僅利用錯(cuò)誤代碼形式的相似性識別同類錯(cuò)誤的修復(fù)實(shí)例，則只可能找到和出錯(cuò)語句相同或者非常接近的修復(fù)實(shí)例.然而，很多同類復(fù)用接口錯(cuò)誤和修復(fù)實(shí)例所在的出錯(cuò)語句形式和語句內(nèi)部使用的變量名稱或者表達(dá)式并不相同，這些差異性阻礙了利用相似性識別同類錯(cuò)誤修復(fù)實(shí)例的數(shù)量和質(zhì)量.例如，同類復(fù)用接口的出錯(cuò)語句類型除了賦值語句和條件語句之外，實(shí)際歷史信息中可能還包括各種循環(huán)語句、跳轉(zhuǎn)語句、表達(dá)式語句或者語句塊等更加多樣化和復(fù)雜的不同語句上下文形式.另外，同類出錯(cuò)語句內(nèi)部也可能使用各種個(gè)性化的元素，例如圖1出錯(cuò)語句使用了features字段，而圖2實(shí)例中使用了dev對象和hw_features，NETIF_F_RXCSUM，NETIF_F_HW_VLAN_CTAG_TX等宏字段.因此，通過相似性無法識別這些具有顯著差異性的同類錯(cuò)誤修復(fù)實(shí)例，這影響了潛在的同類錯(cuò)誤修復(fù)實(shí)例識別的數(shù)量和質(zhì)量.

diff--git a∕drivers∕net∕ethernet∕realtek∕r8169.c b∕drivers∕net∕ethernet∕realtek∕r8169.c修復(fù)實(shí)例1-dev→hw_features &=～NETIF_F_HW_VLAN_RX;+dev→hw_features &=～NETIF_F_HW_VLAN_CTAG_RX;diff--git a∕drivers∕net∕ethernet∕intel∕igb∕igb_main.c b∕drivers∕net∕ethernet∕intel∕igb∕igb_main.c修復(fù)實(shí)例2-dev→features|=NETIF_F_RXCSUM|NETIF_F_HW_VLAN_CTAG_TX|NETIF_F_HW_VLAN_RX;+dev→features|=NETIF_F_RXCSUM|NETIF_F_HW_VLAN_CTAG_TX|NETIF_F_HW_VLAN_CTAG_RX;

根據(jù)本文的觀察和分析，一方面，在歷史開發(fā)信息中存在和出錯(cuò)接口類型相同的修復(fù)實(shí)例，這些同類錯(cuò)誤修復(fù)實(shí)例可以通過有效的方法進(jìn)行識別并提取修復(fù)模板，用于生成未修復(fù)的同類錯(cuò)誤待推薦補(bǔ)丁；另一方面，由于復(fù)用接口所在的調(diào)用點(diǎn)語句類型、表達(dá)式或者變量名稱等差異因素使得修復(fù)實(shí)例的表現(xiàn)形式存在多樣性，利用錯(cuò)誤代碼形式的相似性計(jì)算僅可能獲得語句形式非常接近的修復(fù)實(shí)例，但是準(zhǔn)確地識別語句形式具有顯著差異性的同類錯(cuò)誤修復(fù)實(shí)例并不容易.

1.2 引入錯(cuò)誤變更

為了識別表現(xiàn)形式具有差異性的同類錯(cuò)誤修復(fù)實(shí)例，我們發(fā)現(xiàn)錯(cuò)誤根因(即引入錯(cuò)誤變更信息)是一種非常關(guān)鍵的信息.引入錯(cuò)誤變更信息提供了理解錯(cuò)誤是如何引入的重要信息并且解釋了錯(cuò)誤原因，如果出錯(cuò)語句與修復(fù)實(shí)例具有相同的錯(cuò)誤原因則二者是同類錯(cuò)誤問題.如圖3是宏NETIF_F_HW_VLAN_RX錯(cuò)誤在Linux內(nèi)核歷史開發(fā)信息中引入錯(cuò)誤變更的代碼片段，內(nèi)核在Linux-3.5之后的版本升級過程中，內(nèi)核開發(fā)組在頭文件netdev_features中對宏定義NETIF_F_HW_VLAN_RX的名稱進(jìn)行了更新.圖1中的錯(cuò)誤語句和圖2中的2個(gè)修復(fù)實(shí)例是同類錯(cuò)誤，圖3對宏定義NETIF_F_HW_VLAN_RX名稱的更新解釋了它們共同的出錯(cuò)原因.

diff--git a∕include∕linux∕netdev_features.hb∕include∕linux∕netdev_features.hindex d6ee2d0..785913b 1006441-#define NETIF_F_HW_VLAN_FILTER__NETIF_F(HW_VLAN_FILTER)2-#define NETIF_F_HW_VLAN_RX__NETIF_F(HW_VLAN_RX)3-#define NETIF_F_HW_VLAN_TX__NETIF_F(HW_VLAN_TX)4+#define NETIF_F_HW_VLAN_CTAG_FILTER__NETIF_F(HW_VLAN_CTAG_FILTER)5+#define NETIF_F_HW_VLAN_CTAG_RX__NETIF_F(HW_VLAN_CTAG_RX)6+#define NETIF_F_HW_VLAN_CTAG_TX__NETIF_F(HW_VLAN_CTAG_TX)

盡管引入錯(cuò)誤變更信息能夠提高識別同類錯(cuò)誤修復(fù)實(shí)例的數(shù)量和質(zhì)量，但提取出錯(cuò)語句對應(yīng)的引入錯(cuò)誤變更信息并不容易.引入錯(cuò)誤變更信息往往混合在其他代碼變更語句中，例如圖3的引入錯(cuò)誤變更混合在另外2個(gè)宏定義NETIF_F_HW_VLAN_FILTER和NETIF_F_HW_VLAN_TX的變更代碼塊中.而且實(shí)際歷史開發(fā)信息中引入錯(cuò)誤變更代碼塊嵌入在引入錯(cuò)誤提交信息中，引入錯(cuò)誤提交一般又包含了其他文件代碼塊變更的干擾信息，例如其他代碼塊中可能包含和出錯(cuò)字段文本相似甚至同名的變量、同名函數(shù)等干擾因素.

實(shí)例分析啟發(fā)我們利用錯(cuò)誤原因和來源識別同類錯(cuò)誤修復(fù)實(shí)例，即通過引入錯(cuò)誤變更的中間信息提高獲取同類錯(cuò)誤修復(fù)實(shí)例的數(shù)量和質(zhì)量，在識別與待修復(fù)錯(cuò)誤具有相同原因的同類修復(fù)實(shí)例的基礎(chǔ)上，通過提取并選擇針對性修復(fù)模板提高補(bǔ)丁推薦的質(zhì)量.

2 補(bǔ)丁推薦方法

2.1 補(bǔ)丁推薦方法概述

首先介紹本文方法的整體結(jié)構(gòu)，如圖4所示主要包括候選修復(fù)實(shí)例搜索、引入錯(cuò)誤變更搜索、同類修復(fù)實(shí)例識別和修復(fù)模板提取、補(bǔ)丁推薦4個(gè)部分.

Fig. 4 Driver porting interface patches recommendation by inducing error changes圖4 利用引入錯(cuò)誤變更信息的驅(qū)動(dòng)移植接口補(bǔ)丁推薦

本文的方法輸入包括舊版本驅(qū)動(dòng)程序源碼(待移植驅(qū)動(dòng)程序)、新舊版本內(nèi)核源碼(新版本內(nèi)核為前向移植的目標(biāo)內(nèi)核版本)、新舊版本內(nèi)核之間的開發(fā)歷史倉庫(git repository)；輸出內(nèi)容是舊版本驅(qū)動(dòng)程序移植到新版本內(nèi)核過程中，針對驅(qū)動(dòng)程序代碼中內(nèi)核接口調(diào)用錯(cuò)誤推薦的補(bǔ)丁列表.本文將待移植驅(qū)動(dòng)程序在新內(nèi)核版本環(huán)境下進(jìn)行編譯，針對錯(cuò)誤日志中的一系列接口調(diào)用出錯(cuò)語句，采用迭代方式逐個(gè)進(jìn)行補(bǔ)丁推薦.由于歷史信息龐大且存在混合提交，候選修復(fù)實(shí)例搜索通過啟發(fā)式規(guī)則進(jìn)行噪聲處理，結(jié)合錯(cuò)誤相關(guān)關(guān)鍵字檢索從其他驅(qū)動(dòng)程序的開發(fā)歷史信息中檢索接口調(diào)用出錯(cuò)語句對應(yīng)的候選修復(fù)實(shí)例集合.引入錯(cuò)誤變更搜索使用基于編譯的分層檢索算法，從Linux內(nèi)核的歷史開發(fā)信息中檢索出錯(cuò)語句對應(yīng)的引入錯(cuò)誤變更信息.同類實(shí)例識別和模板提取通過引用關(guān)系分析出錯(cuò)語句、引入錯(cuò)誤變更和候選修復(fù)實(shí)例三者隱含的因果依賴關(guān)系，從而確定一組和待修復(fù)錯(cuò)誤具有相同錯(cuò)誤原因的有效修復(fù)實(shí)例，使用細(xì)粒度差異比較技術(shù)分析多個(gè)有效修復(fù)實(shí)例的共性變更，進(jìn)而抽象細(xì)節(jié)提取修復(fù)模板.補(bǔ)丁推薦使用編輯腳本技術(shù)將提取和選擇的針對性修復(fù)模板進(jìn)行實(shí)例化并生成待推薦補(bǔ)丁，通過補(bǔ)丁排序并推薦給開發(fā)者進(jìn)行質(zhì)量判定.

具體結(jié)合圖1～3的實(shí)際示例進(jìn)行說明.將舊版本e1000驅(qū)動(dòng)程序(待移植驅(qū)動(dòng))在新內(nèi)核版本Linux-4.0環(huán)境下編譯，解析編譯日志發(fā)現(xiàn)其中一個(gè)接口錯(cuò)誤是圖1中/drivers/net/ethernet/intel/e1000/e1000_main.c文件中行818語句“if(features&NETIF_F_HW_VLAN_RX)”宏NETIF_F_HW_VLAN_RX錯(cuò)誤，該宏實(shí)現(xiàn)的功能是對VLAN標(biāo)簽的開關(guān)控制.針對該錯(cuò)誤語句，本文通過4個(gè)步驟最終實(shí)現(xiàn)接口補(bǔ)丁推薦：①候選修復(fù)實(shí)例搜索，針對出錯(cuò)語句“if(features&NETIF_F_HW_VLAN_RX)”在其他驅(qū)動(dòng)程序開發(fā)歷史中進(jìn)行搜索，通過該出錯(cuò)語句的接口關(guān)鍵字和啟發(fā)式規(guī)則從開發(fā)歷史倉庫中搜索其他驅(qū)動(dòng)程序的修復(fù)實(shí)例獲得候選修復(fù)實(shí)例集合，如圖2中的修復(fù)實(shí)例1和修復(fù)實(shí)例2是其中2個(gè)候選修復(fù)實(shí)例.②引入錯(cuò)誤變更搜索，針對圖1的行818錯(cuò)誤語句，通過本文基于編譯的分層檢索算法獲得圖3引入錯(cuò)誤變更信息，即該錯(cuò)誤發(fā)生的原因信息.③同類錯(cuò)誤修復(fù)實(shí)例識別和模板提取，通過引用關(guān)系分析引起錯(cuò)誤的相同依賴，通過引入錯(cuò)誤變更信息識別出錯(cuò)語句和候選實(shí)例二者有相同的錯(cuò)誤原因，從而確定同類修復(fù)實(shí)例，然后使用細(xì)粒度差異比較技術(shù)從一組同類修復(fù)實(shí)例中提取共性變更形成修復(fù)模板.④補(bǔ)丁推薦，選擇已提取的針對性修復(fù)模板，使用修復(fù)模板附帶的參數(shù)(例如變更后的宏名稱)將修復(fù)模板具體化，使用編輯腳本技術(shù)生成待推薦補(bǔ)丁.

2.2 候選修復(fù)實(shí)例搜索

2.2.1 出錯(cuò)接口語句識別

本文聚焦在驅(qū)動(dòng)移植的接口不一致錯(cuò)誤進(jìn)行補(bǔ)丁推薦，首先需要識別出錯(cuò)接口相關(guān)的語句信息.本文采用編譯的方式，在新版本內(nèi)核環(huán)境中編譯待移植驅(qū)動(dòng)程序并從編譯日志中提取出錯(cuò)接口相關(guān)的信息.通常接口相關(guān)的編譯錯(cuò)誤有3類報(bào)錯(cuò)字段：1)excepted error通常是宏定義相關(guān)的錯(cuò)誤;2)implicit and undeclared error是接口名稱相關(guān)錯(cuò)誤，例如接口名稱變化、接口類型變化、接口聲明所在引用文件變化等;3)arguments error通常和接口參數(shù)錯(cuò)誤相關(guān)，例如參數(shù)增加、參數(shù)減少、參數(shù)類型改變等.本文采用關(guān)鍵字正則匹配獲得接口錯(cuò)誤語句相關(guān)的信息，具體包括編譯錯(cuò)誤類型、出錯(cuò)接口所在源碼文件路徑信息、出錯(cuò)接口名稱、出錯(cuò)接口所在源碼文件的行號位置等.

2.2.2 歷史信息噪聲過濾

針對2.2.1節(jié)獲取的每個(gè)出錯(cuò)接口語句，本文在其他驅(qū)動(dòng)程序的開發(fā)歷史信息中搜索與出錯(cuò)接口相關(guān)的候選修復(fù)實(shí)例.然而，驅(qū)動(dòng)程序開發(fā)歷史中的commit提交信息可能包含缺陷修復(fù)、新特性開發(fā)，或者二者的混合提交，一些不規(guī)范提交也會引入大量噪聲為修復(fù)實(shí)例的檢索造成干擾，同時(shí)檢索語句中關(guān)鍵字的構(gòu)造也可能使得提取的結(jié)果包含噪聲.針對噪聲問題，本文設(shè)計(jì)了3個(gè)啟發(fā)式規(guī)則對commit檢索和提取過程進(jìn)行限制和過濾，在過濾噪聲的基礎(chǔ)上形成候選修復(fù)實(shí)例集合.

針對commit檢索過程中的噪聲過濾，本文設(shè)計(jì)3個(gè)啟發(fā)式規(guī)則：

1) 由于接口錯(cuò)誤不同于其他類型錯(cuò)誤可能引入大塊代碼變更，根據(jù)本文的分析一般接口調(diào)用的變更涉及2條語句，因此本文通過限制變更代碼行數(shù)裁剪commit片段中的其他干擾代碼，過濾后的commit代碼片段最多包含2條語句代碼塊.例如，代碼塊包含減掉1條含有出錯(cuò)接口名稱的語句，緊接著再增加1條變更語句的情況，或者只有增加或者刪除語句.具體可能是占用2行修改量或者最多占用4行修改量，使用正則表達(dá)式識別有些語句因?yàn)榫幋a過長導(dǎo)致存在換行的情況.

2) 由于commit提交中可能包含錯(cuò)位提交或者截取已有修復(fù)實(shí)例和出錯(cuò)接口無關(guān)的情況，本文對commit中變更代碼截取進(jìn)一步限制，通過編譯錯(cuò)誤類型和截取的已有修復(fù)實(shí)例的樣式進(jìn)行匹配.通過編譯日志識別3類錯(cuò)誤，包括宏定義錯(cuò)誤、接口名稱錯(cuò)誤和參數(shù)錯(cuò)誤，而這3類錯(cuò)誤各有特點(diǎn)可以用于匹配commit截取.例如，宏定義一般使用大寫形式，接口名稱相關(guān)代碼往往采用駝峰命名規(guī)則(如大小寫混合等)，而參數(shù)一般對應(yīng)的代碼變更在括號區(qū)間中.因此，本文使用特征過濾與編譯錯(cuò)誤類型不符的實(shí)例，具體通過正則表達(dá)式匹配實(shí)現(xiàn).

3) 還需要去除冗余和重復(fù)的修復(fù)實(shí)例，因?yàn)轵?qū)動(dòng)開發(fā)中可能存在代碼塊的復(fù)用、回滾、冗余功能等，具體通過計(jì)算每個(gè)修復(fù)實(shí)例的哈希值并進(jìn)行比較后剔除冗余.

2.2.3 候選修復(fù)實(shí)例集合

為了獲取候選修復(fù)實(shí)例集合，本文通過檢索包含候選實(shí)例的commit信息并從中提取候選實(shí)例代碼片段.Linux內(nèi)核和驅(qū)動(dòng)程序的歷史開發(fā)信息由git工具[42]來維護(hù)，本文通過構(gòu)造git檢索關(guān)鍵字在對應(yīng)移植區(qū)間進(jìn)行檢索.具體查詢語句構(gòu)造為：git log-no-merges-p-S ‘function name’Vold..Vnew--dir Linux/dirvers/>instances.txt.其中function name是出錯(cuò)接口名稱，移植區(qū)間在新舊內(nèi)核版本Vold和Vnew之間，--dir標(biāo)識待檢索的驅(qū)動(dòng)項(xiàng)目開發(fā)歷史，出錯(cuò)接口的使用變更信息來自移植區(qū)間對應(yīng)的驅(qū)動(dòng)開發(fā)歷史.通過2.2.2節(jié)的啟發(fā)式規(guī)則對git檢索結(jié)果進(jìn)行限制和過濾，輸出一組疑似的和出錯(cuò)接口相關(guān)的代碼變更片段.

針對輸出的一組和出錯(cuò)接口相關(guān)的代碼變更片段，選擇固定數(shù)量的實(shí)例組成候選修復(fù)實(shí)例集合.通過分析，驅(qū)動(dòng)程序類型相近的修復(fù)實(shí)例更具有參考價(jià)值.本文通過驅(qū)動(dòng)路徑匹配來確定驅(qū)動(dòng)程序類型是否相近，分析候選實(shí)例所在的驅(qū)動(dòng)路徑和待修復(fù)錯(cuò)誤所在的驅(qū)動(dòng)路徑字段的文本相似性，依據(jù)相近驅(qū)動(dòng)類型確定固定數(shù)量實(shí)例組成候選修復(fù)實(shí)例集合.

2.3 引入錯(cuò)誤變更搜索

引入錯(cuò)誤變更信息是包含在Linux內(nèi)核歷史提交信息中的代碼變更片段.為了搜索待修復(fù)錯(cuò)誤對應(yīng)的引入錯(cuò)誤變更信息，本文采用編譯的方式進(jìn)行檢索.待移植驅(qū)動(dòng)程序在該代碼片段提交之前的內(nèi)核版本中能夠編譯通過，而該引入錯(cuò)誤變更提交之后會導(dǎo)致驅(qū)動(dòng)程序中對應(yīng)的接口調(diào)用出錯(cuò)而編譯失敗.針對待移植驅(qū)動(dòng)程序中接口錯(cuò)誤語句，本文通過分層遍歷Linux內(nèi)核歷史開發(fā)信息的方式，識別哪些提交的代碼片段導(dǎo)致了該錯(cuò)誤.

2.3.1 引入錯(cuò)誤變更信息分層結(jié)構(gòu)分析

歷史commit提交信息具有時(shí)序性和分層結(jié)構(gòu)特點(diǎn).如圖5內(nèi)核開發(fā)歷史由很多分支組成，其他分支最終都合并到主分支形成對應(yīng)的Linux內(nèi)核版本.每個(gè)分支中的提交信息的時(shí)序關(guān)系可以簡化地視為線性提交形式，每個(gè)提交信息可能包含若干文件的修改和變更，而引入錯(cuò)誤變更信息嵌入在引入錯(cuò)誤提交信息之中.引入錯(cuò)誤變更在歷史開發(fā)信息中具有分層提交的特點(diǎn)，更具體地說，引入錯(cuò)誤變更是1個(gè)代碼修改片段并且包含在文件的修改中，而1個(gè)或者多個(gè)文件的修改組成1個(gè)commit提交，1個(gè)或者多個(gè)commit提交組成了不同的提交分支，而不同的分支合并形成了具體的內(nèi)核版本.

Fig. 5 Hierarchical search error-inducing changes圖5 分層檢索引入錯(cuò)誤變更信息

本文結(jié)合commit提交信息的時(shí)序性和分層結(jié)構(gòu)特點(diǎn)進(jìn)行引入錯(cuò)誤變更搜索，具體包括4個(gè)部分：1)將搜索空間縮小到2個(gè)內(nèi)核小版本之間，在驅(qū)動(dòng)移植區(qū)間(內(nèi)核新舊版本之間)對應(yīng)的搜索范圍內(nèi)通過二分查找遍歷內(nèi)核小版本，獲得包含引入錯(cuò)誤變更信息的Linux內(nèi)核版本區(qū)間.2)獲取引入錯(cuò)誤提交，在已經(jīng)確定的內(nèi)核小版本區(qū)間中所包含的提交信息，通過分層的迭代檢索(每一層是指每個(gè)分支中的提交信息是線性的，采用二分查找)獲得包含引入錯(cuò)誤變更信息的引入錯(cuò)誤提交.3)獲取文件變更，對引入錯(cuò)誤提交包含的文件變更信息進(jìn)行過濾，去除出錯(cuò)接口所在文件未引用的頭文件代碼變更，去除非源碼變更(例如注釋信息)等不相關(guān)信息.4)文件變更分割，連續(xù)的變更分割為代碼塊變更，包括連續(xù)增加、連續(xù)刪除和增加刪除混雜3種類型，引入錯(cuò)誤變更則隱含在某個(gè)代碼塊變更信息中.

2.3.2 引入錯(cuò)誤變更信息檢索算法

引入錯(cuò)誤變更是一個(gè)內(nèi)核代碼的變更片段，由于修改了驅(qū)動(dòng)依賴的接口定義而引起驅(qū)動(dòng)程序中相關(guān)調(diào)用發(fā)生不一致錯(cuò)誤.該不一致錯(cuò)誤首先會引起編譯錯(cuò)誤，即引入錯(cuò)誤變更提交之前的內(nèi)核源碼和驅(qū)動(dòng)程序中的接口調(diào)用一致，驅(qū)動(dòng)程序在該提交發(fā)生之前的內(nèi)核環(huán)境中編譯成功，而包含引入錯(cuò)誤變更的提交發(fā)生之后引入了定義變更導(dǎo)致定義和使用不一致，使得驅(qū)動(dòng)程序在提交后的內(nèi)核環(huán)境中編譯產(chǎn)生對應(yīng)編譯錯(cuò)誤.根據(jù)分層結(jié)構(gòu)和提交的時(shí)序特點(diǎn)，該算法采用編譯的方式分層查找出錯(cuò)接口對應(yīng)的引入錯(cuò)誤變更代碼片段.

算法1.基于編譯和分層的引入錯(cuò)誤變更信息檢索算法.

輸入:待移植驅(qū)動(dòng)程序源代碼oldDriver、接口錯(cuò)誤語句代碼片段errorP、包含內(nèi)核版本commit提交的開發(fā)倉庫kernelGit；

輸出:接口錯(cuò)誤語句對應(yīng)的引入錯(cuò)誤變更代碼片段EIC.

① (kernelX,kernelY)=versionBinarySearch

(oldDriver,errorP,kernelGit);

②branchCommitList=firstParent(kernelX,

kernelY);

③ IF(commitBinarySearch(branchCommit-

List))≠Null) THEN

④ RETURNEICSearch(commitBinary-

Search(branchCommitList));

⑤ ELSE

⑥ RETURN not find;

⑦ END IF

⑧ ProcedurecommitBinarySearch(branch-

CommitList)

⑨ (errInducingCommit,okParentCommit)=

BinarySearch(kernelX,commitList);

⑩ IFerrInducingCommit是一個(gè)合并提交

THEN

(errInducingCommit);

(errorParentCommit,okParentCommit);

(errorParentCommit,commonAncentor);

(nextBranchCommitList);

(errInducingCommit);

(fileChange);

根據(jù)版本提交之間分層結(jié)構(gòu)和提交的時(shí)序性特點(diǎn)，算法1的行①首先通過versionBinarySearch的二分查找獲得最小版本區(qū)間，即驅(qū)動(dòng)程序在內(nèi)核X版本編譯成功，而在下一個(gè)升級的內(nèi)核Y版本編譯失敗.行②獲取2個(gè)內(nèi)核版本區(qū)間中的第1個(gè)分支的commit列表branchCommitList，函數(shù)firstParent通過git log--pretty=format:%h--first-parent[target version..original version]獲取第1個(gè)分支的branchCommitList.行③判斷如果獲取errInducingCommit，則行④從errInducingCommit中查找獲得引入錯(cuò)誤變更EIC.否則行⑤～⑦返回未找到EIC信息.行⑧～引入錯(cuò)誤變更提交errInducingCommit查找函數(shù)commitBinarySearch通過遞歸查詢輸出引入錯(cuò)誤的提交errInducingCommit，其中，引入錯(cuò)誤提交查找函數(shù)commitBinarySearch進(jìn)行分層檢索，行⑨二分查找函數(shù)BinarySearch使用git bisect實(shí)現(xiàn)，行⑩判斷獲取的引入錯(cuò)誤提交是否為一個(gè)合并(merge)提交節(jié)點(diǎn)，如果是合并節(jié)點(diǎn)則行～繼續(xù)尋找下一層的引入錯(cuò)誤父親節(jié)點(diǎn)和祖先節(jié)點(diǎn)繼續(xù)迭代，如果不是合并節(jié)點(diǎn)則行輸出引入錯(cuò)誤提交.行函數(shù)getCommonAncentor通過git merge-base errParent okParent獲取.然后行～EIC查找函數(shù)EICSearch調(diào)用文件查找fileBinarySearch和變更代碼塊切分hunkSplit，hunkSplit實(shí)現(xiàn)連續(xù)的代碼塊變更進(jìn)行整體切分，最后由findEIC遍歷變更代碼塊并找到EIC信息進(jìn)行輸出.

2.4 同類實(shí)例識別和模板提取

2.4.1 同類修復(fù)實(shí)例識別

本文通過分析與待修復(fù)錯(cuò)誤具有相同原因的代碼塊來識別一組同類錯(cuò)誤修復(fù)實(shí)例.即針對某個(gè)確定的待修復(fù)錯(cuò)誤、對應(yīng)的引入錯(cuò)誤變更、對應(yīng)的候選修復(fù)實(shí)例集合，識別候選集合中哪些修復(fù)實(shí)例和待修復(fù)錯(cuò)誤是由于相同的引入錯(cuò)誤變更產(chǎn)生的同類錯(cuò)誤.由于引入錯(cuò)誤變更實(shí)際上是對內(nèi)核接口服務(wù)中接口定義的變更，而待修復(fù)的接口不一致錯(cuò)誤和修復(fù)實(shí)例實(shí)際上是不同的接口調(diào)用點(diǎn)，因此引入錯(cuò)誤變更與待修復(fù)錯(cuò)誤和同類修復(fù)實(shí)例之間存在引用關(guān)系.

為了方便和準(zhǔn)確地描述同類錯(cuò)誤修復(fù)實(shí)例的識別，本文給出6個(gè)定義.

定義1.引入錯(cuò)誤變更Eeic.設(shè)Eeic=(M,N)表示引入錯(cuò)誤變更代碼塊，減語句塊M={m1,m2,…,mm}，其中me表示出錯(cuò)元素字段(1≤e≤m)，M由m個(gè)token元素組成，刻畫了舊接口相關(guān)的定義，而N={n1,n2,…,nn}由n個(gè)token元素組成，刻畫了新接口相關(guān)的定義，則Eeic有3種情況：

定義2.修復(fù)實(shí)例Fefi.設(shè)Fefi=(R,S)表示修復(fù)實(shí)例的代碼塊，減語句塊R={r1,r2,…,rr}由r個(gè)token元素組成，刻畫了修復(fù)實(shí)例對舊接口的調(diào)用，而S={s1,s2,…,ss}，其中sx表示更新元素字段(1≤x≤s)，S由s個(gè)token元素組成，刻畫了修復(fù)實(shí)例對新接口的調(diào)用，則和Eeic類似，F(xiàn)efi也有3種情況：

定義3.舊引用鏈Cold.如果Eeic包含1對加減語句塊，即M≠Null&&N≠Null，則舊引用鏈Cold=me→re，表示Fefi對Eeic中更新前元素定義的使用，e表示出錯(cuò)字段對應(yīng)的元素下標(biāo)；如果Eeic僅包含減語句塊，即M≠Null&&N=Null，則舊引用鏈Cold=me→re，表示Fefi對Eeic中已刪除元素定義的使用，e表示出錯(cuò)字段對應(yīng)的元素下標(biāo)；如果Eeic僅包含加語句塊，即M=Null&&N≠Null，則Cold=Null.

定義4.新引用鏈Cnew.如果Eeic包含1對加減語句塊，即M≠Null&&N≠Null，則新引用鏈Cnew=nx→sx，表示Fefi對Eeic中更新后元素定義的使用，x為更新字段對應(yīng)的元素下標(biāo)；如果Eeic僅包含減語句塊，即M≠Null&&N=Null，則Cnew=Null；如果Eeic僅包含加語句塊，即M=Null&&N≠Null，則Cnew=nx→sx，表示Fefi對Eeic新增語句中元素定義的使用，x為更新字段對應(yīng)的元素下標(biāo).

Fig. 6 Identify similar error fix instances based on EIC圖6 基于EIC識別同類錯(cuò)誤修復(fù)實(shí)例

2.4.2 修復(fù)模板提取

為了提取針對性修復(fù)模板，本文通過計(jì)算與待修復(fù)錯(cuò)誤具有相同原因的1組修復(fù)實(shí)例之間的共性變更抽取修復(fù)模板.1組修復(fù)實(shí)例提取1個(gè)修復(fù)模板，修復(fù)模板抽象了共性變更，而修復(fù)模板參數(shù)(可能是1組或者多組)同時(shí)記錄了多樣化的操作內(nèi)容.

定義6.修復(fù)模板OP.修復(fù)模板抽象了1組同類錯(cuò)誤修復(fù)實(shí)例的共性變更，OP表示為：[操作(Update，Delete，Add)][操作內(nèi)容1@頻度，操作內(nèi)容2@頻度].

如果操作是Update，則每個(gè)修復(fù)實(shí)例包含1對操作內(nèi)容.修復(fù)實(shí)例中相同的操作內(nèi)容合并計(jì)算頻度作為權(quán)重，相互不同的操作內(nèi)容權(quán)重為1，因此提取的修復(fù)模板可能包含1對或者多對操作內(nèi)容.如果操作是Delete，則每個(gè)修復(fù)實(shí)例包含1個(gè)單獨(dú)的操作內(nèi)容，根據(jù)操作內(nèi)容的異同合并計(jì)算頻度，因此最終提取的修復(fù)模板可能包含1個(gè)或者多個(gè)操作內(nèi)容.如果操作是Add，則每個(gè)修復(fù)實(shí)例包含1個(gè)附帶相對索引位置的單獨(dú)操作內(nèi)容，根據(jù)操作內(nèi)容和附帶相對位置索引的異同合并計(jì)算頻度，最終提取的修復(fù)模板可能包含1個(gè)或者多個(gè)附帶相對索引位置的操作內(nèi)容.

如圖7所示，針對1組同類錯(cuò)誤修復(fù)實(shí)例進(jìn)行修復(fù)模板提取.具體包括2個(gè)步驟：①使用抽象語法樹刻畫每個(gè)修復(fù)實(shí)例內(nèi)部的變更差異并將變更差異輸出為編輯腳本[44]；②比較編輯腳本的共性提取修復(fù)模板.本文使用GumTreeDiff框架[45]對每個(gè)修復(fù)實(shí)例在AST級別進(jìn)行差異比較，首先將修復(fù)實(shí)例中包含的語句進(jìn)行AST樹形表示，然后進(jìn)行節(jié)點(diǎn)映射和節(jié)點(diǎn)差異比較.本文通過映射匹配語句中未修改的相同節(jié)點(diǎn)，通過差異比較計(jì)算未匹配節(jié)點(diǎn)的變更并輸出對應(yīng)編輯腳本.如果未匹配節(jié)點(diǎn)只有1個(gè)，則直接輸出該節(jié)點(diǎn)在語句遷移中的差異操作.如果存在多個(gè)未匹配節(jié)點(diǎn)則會對應(yīng)1組語句遷移的操作序列，需要進(jìn)一步將相鄰的操作和節(jié)點(diǎn)進(jìn)行合并.具體將相鄰的相同操作合并，本文僅處理未匹配節(jié)點(diǎn)可以合并為子樹的情形，輸出對應(yīng)操作針對子樹的差異變更.比較編輯腳本的共性提取修復(fù)模板，本文通過合并編輯腳本中的操作并計(jì)算操作內(nèi)容的頻度形成修復(fù)模板.

Fig. 7 Example of fix pattern extraction圖7 修復(fù)模板提取示例

2.5 補(bǔ)丁推薦

2.5.1 補(bǔ)丁生成和排序

整個(gè)補(bǔ)丁推薦過程采用迭代方式逐個(gè)接口錯(cuò)誤進(jìn)行補(bǔ)丁推薦.首先利用已經(jīng)提取的針對性修復(fù)模板生成待推薦補(bǔ)丁，然后對補(bǔ)丁進(jìn)行排序產(chǎn)生補(bǔ)丁推薦列表.其中，待推薦補(bǔ)丁生成是將針對性修復(fù)模板實(shí)例化的過程.利用2.2.1節(jié)的方法確定出錯(cuò)接口語句行的位置，然后針對該出錯(cuò)語句使用修復(fù)模板進(jìn)行代碼變更.由于2.4節(jié)中識別的同類修復(fù)實(shí)例和待修復(fù)錯(cuò)誤具有相同原因，同類錯(cuò)誤共享1個(gè)針對性修復(fù)模板，因此同類錯(cuò)誤修復(fù)實(shí)例中提取的修復(fù)模板具有指向性.

為了生成待推薦補(bǔ)丁，本文提取并選擇2.4.2節(jié)生成的修復(fù)模板，通過修復(fù)模板匹配錯(cuò)誤語句的語句內(nèi)修改點(diǎn)，使用模板附帶的操作內(nèi)容參數(shù)具體化修復(fù)模板生成待推薦補(bǔ)丁.修復(fù)模板如果是Update或者Delete，則使用操作內(nèi)容字段進(jìn)行匹配；修復(fù)模板如果是Add，則使用相對索引位置進(jìn)行匹配.生成待推薦補(bǔ)丁的過程中采用編輯腳本技術(shù)[44]，在抽象語法樹級別實(shí)現(xiàn)出錯(cuò)語句的轉(zhuǎn)換并生成待推薦補(bǔ)丁.待推薦補(bǔ)丁生成過程中可能會合成位置錯(cuò)誤或者語法錯(cuò)誤的補(bǔ)丁，本文將編譯出錯(cuò)的待推薦補(bǔ)丁直接拋棄.根據(jù)修復(fù)模板附帶的操作內(nèi)容的不同情況，本文的方法是輸出0個(gè)、1個(gè)或者多個(gè)待推薦補(bǔ)丁，如果沒有輸出待推薦補(bǔ)丁，則推薦失敗.

針對待推薦補(bǔ)丁的排序，本文采用操作內(nèi)容的頻度和相似度計(jì)算相結(jié)合的方式進(jìn)行排序.本文刻畫的修復(fù)模板提取了同類修復(fù)實(shí)例的共性變更操作，同時(shí)以參數(shù)形式記錄了修復(fù)實(shí)例中使用的操作內(nèi)容以及頻度.本文的方法很自然地使用修復(fù)模板的參數(shù)頻度對最終待推薦補(bǔ)丁列表進(jìn)行排序，對于排序位置相同的補(bǔ)丁，再依據(jù)變更字段和待修復(fù)驅(qū)動(dòng)名稱的相似度進(jìn)行二次排序.經(jīng)過排序計(jì)算，最后輸出top-N(實(shí)驗(yàn)中，N=5)的補(bǔ)丁列表進(jìn)行推薦.

2.5.2 補(bǔ)丁質(zhì)量判定

針對推薦補(bǔ)丁的質(zhì)量判定，本文采用人工方式確認(rèn)有效補(bǔ)丁.首先針對每款待移植驅(qū)動(dòng)程序設(shè)定歷史上已經(jīng)完成移植的一個(gè)驅(qū)動(dòng)程序版本為正確的參考程序版本；然后依據(jù)參考程序版本中的對應(yīng)代碼語句和推薦的補(bǔ)丁進(jìn)行人工對比語義和相似性，逐個(gè)出錯(cuò)接口和對應(yīng)的推薦補(bǔ)丁依次判定補(bǔ)丁的有效性.為了盡可能保證人工判斷的準(zhǔn)確性，本文采用2人分別進(jìn)行手工判斷的方式，如果2人判斷一致則記為正確補(bǔ)丁，如果2人判斷不一致則直接記為錯(cuò)誤補(bǔ)丁.

3 實(shí) 驗(yàn)

本節(jié)介紹實(shí)驗(yàn)數(shù)據(jù)集和實(shí)驗(yàn)環(huán)境，以及相關(guān)實(shí)驗(yàn)結(jié)果和分析.為了檢驗(yàn)方法的有效性，本文的實(shí)驗(yàn)期望回答4個(gè)問題：

1) 本文的方法針對真實(shí)驅(qū)動(dòng)移植場景中的接口不一致錯(cuò)誤進(jìn)行補(bǔ)丁推薦的正確率？

2) 本文的方法是否相比傳統(tǒng)方法的補(bǔ)丁推薦正確率有顯著提高？

3) 本文的方法針對各個(gè)驅(qū)動(dòng)程序在獲取引入錯(cuò)誤變更信息之后推薦有效補(bǔ)丁的比例？

4) 本文的方法進(jìn)行補(bǔ)丁推薦的性能？

3.1 數(shù)據(jù)集建立

本文的實(shí)驗(yàn)在真實(shí)的前向移植場景中進(jìn)行，目標(biāo)是檢驗(yàn)舊版本驅(qū)動(dòng)程序的原有功能在新版本內(nèi)核環(huán)境中復(fù)用時(shí)，針對出錯(cuò)接口的補(bǔ)丁推薦情況.為了方便檢驗(yàn)方法的性能和有效性，本文采用合并在Linux內(nèi)核主線分支中的驅(qū)動(dòng)程序歷史數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，選擇實(shí)驗(yàn)對象中的驅(qū)動(dòng)程序和內(nèi)核環(huán)境依據(jù)3個(gè)標(biāo)準(zhǔn).

1) 內(nèi)核版本從K1升級到K2，K1環(huán)境下的待移植驅(qū)動(dòng)D1在升級過程中已經(jīng)存在K2環(huán)境下對應(yīng)的驅(qū)動(dòng)程序的升級版本D2，從D1到D2的前向演化過程中引入的變化存在內(nèi)核接口調(diào)用的變更，本文的研究只關(guān)注移植過程中發(fā)生的接口調(diào)用不一致問題.

2) 待移植驅(qū)動(dòng)D1在前向演化過程中所發(fā)生的接口調(diào)用變化，在K1到K2內(nèi)核區(qū)間的commit提交信息中存在對應(yīng)引入錯(cuò)誤變更信息以及其他驅(qū)動(dòng)對該接口調(diào)用的修復(fù)實(shí)例.

3) 待移植驅(qū)動(dòng)D1在原來的舊內(nèi)核版本K1上編譯正常通過，而D1在待移植的新內(nèi)核版本K2上編譯產(chǎn)生的編譯錯(cuò)誤日志包含接口調(diào)用錯(cuò)誤.

本文通過這3個(gè)標(biāo)準(zhǔn)并結(jié)合實(shí)際實(shí)驗(yàn)資源的綜合考慮，篩選和收集待移植的驅(qū)動(dòng)程序數(shù)據(jù)集.確定版本區(qū)間K1:Linux-3.5，K2:Linux-4.0版本，該區(qū)間總計(jì)跨越43個(gè)Linux kernel的小版本.最終收集了Linux-3.5對應(yīng)的19款驅(qū)動(dòng)程序，總計(jì)包含142個(gè)文件和159 304行代碼.表1展示了本文收集的待移植驅(qū)動(dòng)程序數(shù)據(jù)集的具體情況.

Table 1 Data set of Driver to Port表1 待移植驅(qū)動(dòng)程序的數(shù)據(jù)集

3.2 實(shí)驗(yàn)設(shè)計(jì)

我們實(shí)現(xiàn)了算法1以及本文的補(bǔ)丁推薦方法，形成了驅(qū)動(dòng)移植場景中的接口補(bǔ)丁推薦工具RCFix.采用本文的EIC檢索算法獲取待修復(fù)接口錯(cuò)誤對應(yīng)的引入錯(cuò)誤變更信息，采用git log-S構(gòu)造檢索獲取候選修復(fù)實(shí)例集合，依據(jù)相同原因識別同類錯(cuò)誤修復(fù)實(shí)例.然后基于GumTreeDiff框架對修復(fù)實(shí)例進(jìn)行AST映射和差異比較，通過比較編輯腳本的共性差異提取修復(fù)模板.其中代碼倉庫采用git-2.7.4版本，基于AST的差異比較采用gumtree-2.1.2版本，AST解析前端采用cgum-1.0.1版本.由于本文提取的修復(fù)模板具有指向性，提取并選擇針對性修復(fù)模板并使用操作內(nèi)容參數(shù)進(jìn)行具體化，采用編輯腳本技術(shù)合成待推薦補(bǔ)丁，利用操作內(nèi)容的頻度對補(bǔ)丁進(jìn)行排序并推薦給開發(fā)者人工判定補(bǔ)丁質(zhì)量.實(shí)驗(yàn)中，對收集的19款驅(qū)動(dòng)分別進(jìn)行前向移植實(shí)驗(yàn)，針對以上驅(qū)動(dòng)從舊內(nèi)核K1:Linux-3.5版本移植到新內(nèi)核K2:Linux-4.0版本過程中產(chǎn)生的接口錯(cuò)誤進(jìn)行補(bǔ)丁推薦.歷史開發(fā)信息git倉庫采用Linux官方主分支信息，使用RCFix工具依次對每個(gè)驅(qū)動(dòng)移植中產(chǎn)生的接口調(diào)用錯(cuò)誤生成補(bǔ)丁并推薦補(bǔ)丁，最后人工確認(rèn)有效補(bǔ)丁并分析實(shí)驗(yàn)效果.本文的全部實(shí)驗(yàn)使用ubuntu 16.06 64位操作系統(tǒng)環(huán)境，編譯環(huán)境使用gcc-5.4.0版本，硬件采用1臺PC機(jī)器，具有4核3.20 GHz Intel CoreTMi5處理器和8 GB內(nèi)存.

3.3 實(shí)驗(yàn)結(jié)果

問題1.本文的方法針對真實(shí)驅(qū)動(dòng)移植場景中的接口不一致錯(cuò)誤進(jìn)行補(bǔ)丁推薦的正確率？

表2展示了本文的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)中針對19款驅(qū)動(dòng)程序進(jìn)行前向移植，針對移植過程中的接口不一致錯(cuò)誤進(jìn)行補(bǔ)丁推薦.實(shí)驗(yàn)中包括7類接口錯(cuò)誤：宏定義錯(cuò)誤、接口名稱錯(cuò)誤、接口類型錯(cuò)誤、修飾符錯(cuò)誤、缺少參數(shù)錯(cuò)誤、多余參數(shù)和參數(shù)類型錯(cuò)誤.實(shí)驗(yàn)總計(jì)包括109個(gè)接口調(diào)用不一致錯(cuò)誤，針對其中80個(gè)錯(cuò)誤生成了待推薦補(bǔ)丁，其中72個(gè)補(bǔ)丁人工確認(rèn)正確.推薦的正確補(bǔ)丁通過和基準(zhǔn)版本驅(qū)動(dòng)程序中的對應(yīng)代碼進(jìn)行人工比較確定語義相同并進(jìn)行雙人交叉確認(rèn).

本實(shí)驗(yàn)計(jì)算了top-1，top-2，top-5的補(bǔ)丁推薦正確率，分別為58.7%，60.6%，66.1%.本文的主要特點(diǎn)在于依據(jù)錯(cuò)誤原因和來源識別同類修復(fù)實(shí)例，然后提取并選擇修復(fù)模板實(shí)現(xiàn)同類待修復(fù)錯(cuò)誤的高質(zhì)量補(bǔ)丁推薦.其中的錯(cuò)誤原因和來源，即待修復(fù)錯(cuò)誤對應(yīng)的引入錯(cuò)誤變更信息.實(shí)驗(yàn)中包括109個(gè)接口調(diào)用不一致錯(cuò)誤，針對其中88個(gè)錯(cuò)誤獲取了有效的引入錯(cuò)誤變更信息，引入錯(cuò)誤變更信息提取的正確率達(dá)到80.7%.本文的方法推薦高質(zhì)量的適配性補(bǔ)丁，同時(shí)也會附上待修復(fù)錯(cuò)誤對應(yīng)的引入錯(cuò)誤變更信息，更方便開發(fā)者理解錯(cuò)誤原因和推薦的補(bǔ)丁.

問題2.本文的方法是否相比傳統(tǒng)方法的補(bǔ)丁推薦正確率有顯著提高？

針對驅(qū)動(dòng)移植場景中的接口不一致錯(cuò)誤，傳統(tǒng)補(bǔ)丁推薦方法DriverFix[46]通過相似度識別同類錯(cuò)誤修復(fù)實(shí)例提取和選擇修復(fù)模板，并通過區(qū)分共性和個(gè)性代碼元素生成待推薦補(bǔ)丁.本文將基于錯(cuò)誤根因的補(bǔ)丁推薦方法與基于相似度的傳統(tǒng)補(bǔ)丁推薦方法進(jìn)行對比實(shí)驗(yàn)，表3展示了本文的對比實(shí)驗(yàn)結(jié)果.

Table 3 Comparison of Experimental Results with Traditional Patch Recommendation Methods表3 與傳統(tǒng)補(bǔ)丁推薦方法的對比實(shí)驗(yàn)結(jié)果

在相同的驅(qū)動(dòng)移植場景下，通過相同數(shù)據(jù)集進(jìn)行對比實(shí)驗(yàn).相比驅(qū)動(dòng)移植接口補(bǔ)丁推薦方法DriverFix(top-5，51/109，正確率為46.8%)，本文基于錯(cuò)誤根因的方法RCFix(top-5，72/109，正確率為66.1%)推薦補(bǔ)丁的正確率有顯著提高，有效降低了人工修復(fù)錯(cuò)誤的工作量并提高了修復(fù)效率.

另外，還有一些補(bǔ)丁推薦方法針對靜態(tài)分析工具發(fā)現(xiàn)的錯(cuò)誤、commit提交的錯(cuò)誤代碼等不同場景的研究對象，本文引用這些方法的數(shù)據(jù)也進(jìn)行了比較.相比傳統(tǒng)的補(bǔ)丁推薦方法Getafix[47](top-5,526/1268,正確率為41.5%)、CLEVER[48](34/72，正確率為47.2%)和iFixR[49](top-5,8/13，正確率為61.5%)，本文的方法推薦補(bǔ)丁的正確率(top-5，72/109，正確率為66.1%)有顯著提高.

問題3.本文的方法針對各個(gè)驅(qū)動(dòng)程序在獲取引入錯(cuò)誤變更信息之后推薦有效補(bǔ)丁的比例?

圖8展示了針對各個(gè)驅(qū)動(dòng)程序在獲取引入錯(cuò)誤變更信息之后推薦有效補(bǔ)丁的比例，橫軸是19個(gè)驅(qū)動(dòng)程序，縱軸為top-N補(bǔ)丁修復(fù)錯(cuò)誤的數(shù)量、獲取有效EIC的錯(cuò)誤數(shù)量和待修復(fù)接口錯(cuò)誤的數(shù)量.

Fig. 8 Proportion of recommending effective patches for each driver 圖8 針對各個(gè)驅(qū)動(dòng)程序推薦有效補(bǔ)丁的比例

我們分析了實(shí)驗(yàn)中獲得的數(shù)據(jù)分布情況，各個(gè)驅(qū)動(dòng)錯(cuò)誤代碼、推薦的補(bǔ)丁和對應(yīng)EIC原因等詳細(xì)情況.一方面，本文通過算法1自動(dòng)獲取EIC原因信息，減少人工的工作量；另一方面，針對大多數(shù)驅(qū)動(dòng)程序獲取根因和推薦有效補(bǔ)丁的比例較高，提升了補(bǔ)丁推薦的質(zhì)量和自動(dòng)化程度.例如，圖8中針對大多數(shù)規(guī)模較小的驅(qū)動(dòng)程序，獲取根因信息和補(bǔ)丁推薦質(zhì)量相對較高.

針對少數(shù)規(guī)模較大的驅(qū)動(dòng)程序，相比規(guī)模較小的驅(qū)動(dòng)程序更不易獲取有效EIC原因信息.例如，驅(qū)動(dòng)ixgbe，bonding，nvme等規(guī)模較大的程序獲取有效EIC原因信息的比例相對較低.我們分析了其中的主要原因，這些規(guī)模較大的驅(qū)動(dòng)程序本身比較復(fù)雜，例如存在內(nèi)核導(dǎo)出符號(EXPORT_SYMBOL)、變化較大的接口不一致錯(cuò)誤等不易獲取對應(yīng)的EIC原因信息.其次，獲取有效EIC原因信息之后，還要識別同類修復(fù)實(shí)例，提取針對性修復(fù)模板和確定操作內(nèi)容具體化模板進(jìn)行有效補(bǔ)丁推薦，這些步驟最終都會影響推薦有效補(bǔ)丁的比例.例如，tun，loop等驅(qū)動(dòng)程序在獲取有效EIC原因之后補(bǔ)丁推薦的正確率依然相對較低，具體在3.4節(jié)詳細(xì)分析和說明.

問題4.本文的方法進(jìn)行補(bǔ)丁推薦的性能？

圖9統(tǒng)計(jì)了19款驅(qū)動(dòng)程序進(jìn)行適配性接口補(bǔ)丁推薦所消耗的時(shí)間，橫坐標(biāo)為實(shí)驗(yàn)中的19款驅(qū)動(dòng)程序，縱坐標(biāo)為生成待推薦補(bǔ)丁消耗的時(shí)間，總體上各個(gè)驅(qū)動(dòng)生成待推薦補(bǔ)丁的數(shù)量和耗時(shí)成正比.

使用本文的接口補(bǔ)丁推薦工具RCFix，在實(shí)驗(yàn)中主要時(shí)間消耗包括：編譯以及編譯錯(cuò)誤日志解析、引入錯(cuò)誤變更信息搜索、候選修復(fù)實(shí)例搜索、修復(fù)模板提取、待推薦補(bǔ)丁生成和排序等部分.已有研究[8]提供驅(qū)動(dòng)移植的輔助示例，人工利用該方法輸出的輔助信息構(gòu)造補(bǔ)丁平均每個(gè)錯(cuò)誤耗時(shí)在30 min左右.相比該方法，一方面本文的方法直接推薦補(bǔ)丁而并非輔助示例，能夠有效降低開發(fā)者人工修復(fù)錯(cuò)誤的工作量；另一方面本文的方法針對每個(gè)錯(cuò)誤的補(bǔ)丁推薦平均耗時(shí)大約在3 min，針對每款驅(qū)動(dòng)程序補(bǔ)丁推薦的平均耗時(shí)大約在14 min，顯著提高了輔助人工修復(fù)的效率.

Fig. 9 Performance analysis of patch recommendation圖9 補(bǔ)丁推薦性能分析

3.4 討 論

本節(jié)對本文的方法進(jìn)行討論，主要討論補(bǔ)丁推薦失敗的詳細(xì)情況.本文的方法中搜索待修復(fù)錯(cuò)誤對應(yīng)的EIC原因信息、識別同類修復(fù)實(shí)例，提取針對性修復(fù)模板和確定操作內(nèi)容具體化模板等步驟都影響補(bǔ)丁推薦的結(jié)果.本文根據(jù)實(shí)驗(yàn)結(jié)果將推薦失敗的情形分為4類：缺少有效引入錯(cuò)誤變更、缺少修復(fù)實(shí)例、修復(fù)模板提取失敗和推薦補(bǔ)丁錯(cuò)誤.如圖10所示，總計(jì)37個(gè)待修復(fù)錯(cuò)誤補(bǔ)丁推薦失敗或者推薦的補(bǔ)丁錯(cuò)誤，其中缺少有效引入錯(cuò)誤變更(21/37)占比56.7%，缺少修復(fù)實(shí)例(5/37)占比13.5%，修復(fù)模板提取失敗(3/37)占比8.1%，推薦補(bǔ)丁錯(cuò)誤(8/37)占比21.6%.

Fig. 10 Analysis of four types of patch recommendation failures圖10 補(bǔ)丁推薦失敗的4種類型分析

我們分析了補(bǔ)丁推薦失敗的4類具體情況，這4類情形是遞進(jìn)關(guān)系.缺少有效引入錯(cuò)誤變更的主要原因是一些規(guī)模較大的驅(qū)動(dòng)程序獲取對應(yīng)的引入錯(cuò)誤變更信息相對困難，因?yàn)橐?guī)模較大的驅(qū)動(dòng)程序本身比較復(fù)雜并且包含有些復(fù)雜的調(diào)用.而缺少修復(fù)實(shí)例的情形主要是一些內(nèi)核接口被驅(qū)動(dòng)程序使用的頻度較小，針對這些相對不常用的內(nèi)核接口及產(chǎn)生的不一致錯(cuò)誤，驅(qū)動(dòng)的歷史開發(fā)信息中客觀上幾乎沒有對應(yīng)的修復(fù)實(shí)例，因此在候選修復(fù)實(shí)例搜索的方法層面也難以找到.修復(fù)模板提取失敗和補(bǔ)丁推薦錯(cuò)誤這2種推薦失敗的情形，本文通過失敗案例1和失敗案例2進(jìn)行詳細(xì)說明.

失敗案例1.修復(fù)模板提取失敗.

錯(cuò)誤為(drivers/block/floppy.c,970):

PREPARE_WORK(&floppy_work,(work_func_t)handler);/*錯(cuò)誤代碼*/

floppy_workfn=handler;/*期望的正確補(bǔ)丁*/

引入錯(cuò)誤變更為(include/linux/workqueue.h):

-#definePREPARE_WORK(_work,_func)

- do{

- (_work)→func=(_func);

- }while(0)

修復(fù)實(shí)例1為(drivers/staging/fwserial/fwserial.c):

-PREPARE_WORK(&peer→work,fwserial_handle_plug_req);

+peer→workfn=fwserial_handle_plug_req;

修復(fù)實(shí)例2為(drivers/block/nvme-core.c):

-PREPARE_WORK(&dev→reset_work,nvme_remove_disks);

+dev→reset_workfn=nvme_remove_disks;

失敗案例2.推薦補(bǔ)丁錯(cuò)誤.

錯(cuò)誤為(drivers/net/bonding/bond_main.c,1245):

err=__netpoll_setup(np);/*錯(cuò)誤代碼*/

err=__netpoll_setup(np,slave→dev);

/*期望的正確補(bǔ)丁*/

引入錯(cuò)誤變更為(include/linux/netpoll.h):

-int__netpoll_setup(structnetpoll*np);

+int__netpoll_setup(structnetpoll*np,structnet_device*ndev);

修復(fù)實(shí)例1為(net/8021q/vlan_dev.c):

-err=__netpoll_setup(netpoll);

+err=__netpoll_setup(netpoll,real_dev);

修復(fù)實(shí)例2為(net/core/netpoll.c):

-err=__netpoll_setup(np);

+err=__netpoll_setup(np,ndev).

修復(fù)模板提取失敗的情形，主要原因是模板提取過程中需要進(jìn)行AST級別的細(xì)粒度映射和比較，一些情形會存在映射混亂導(dǎo)致提取失敗.在失敗案例1中，待修復(fù)錯(cuò)誤是驅(qū)動(dòng)floppy中PREPARE_WORK宏錯(cuò)誤，錯(cuò)誤原因是Linux內(nèi)核更新后該宏定義被刪除.該案例中雖然找到了有效的同類修復(fù)實(shí)例，但是提取修復(fù)模板失敗.主要原因在于修復(fù)實(shí)例中的2條語句在AST映射階段出現(xiàn)混亂，無法生成對應(yīng)的編輯腳本導(dǎo)致提取修復(fù)模板失敗.現(xiàn)有的映射方法依靠語句中元素的父子結(jié)構(gòu)相對位置和字段名稱進(jìn)行映射，而語句PREPARE_WORK(&peer→work,fwserial_handle_plug_req)和語句peer→workfn=fwserial_handle_plug_req是完全不同的2種語句結(jié)構(gòu)，并且其中包含的字段也出現(xiàn)大量變化導(dǎo)致映射失敗.

推薦補(bǔ)丁錯(cuò)誤的情形，主要是具體化修復(fù)模板的過程中需要確定正確的操作內(nèi)容，本文通過頻度和驅(qū)動(dòng)類型相似性對操作內(nèi)容的排序方式，針對驅(qū)動(dòng)程序中接口調(diào)用使用個(gè)性化參數(shù)(例如局部變量)的情形依然具有局限性.在失敗案例2中，待修復(fù)錯(cuò)誤是驅(qū)動(dòng)bonding中函數(shù)__netpoll_setup錯(cuò)誤，錯(cuò)誤原因是Linux內(nèi)核更新后該函數(shù)定義進(jìn)行了變更，增加了第2個(gè)參數(shù).該案例中雖然找到了有效的同類修復(fù)實(shí)例同時(shí)成功提取修復(fù)模板.但是由于各個(gè)實(shí)例中均使用個(gè)性化參數(shù)作為接口新增的實(shí)參，例如ndev，real_dev等私有變量作為實(shí)參的情形，針對該情形確定的實(shí)參slave→dev不正確，導(dǎo)致推薦補(bǔ)丁錯(cuò)誤.綜上所述，本文的方法依然有提升空間，例如在更復(fù)雜的模板提取和刻畫、確定個(gè)性化代碼元素等操作內(nèi)容方面還需要更進(jìn)一步的突破.

4 相關(guān)工作

4.1 程序自動(dòng)修復(fù)

程序自動(dòng)修復(fù)是一個(gè)自動(dòng)修復(fù)錯(cuò)誤的系統(tǒng)，輸出的補(bǔ)丁經(jīng)過程序規(guī)約的正確性判定，在程序規(guī)約完整的假設(shè)下保證了輸出補(bǔ)丁的質(zhì)量.針對一般錯(cuò)誤問題，基于隨機(jī)變異或者修復(fù)模板生成候選補(bǔ)丁，通過生成-檢測(generate-and-validate)結(jié)構(gòu)利用測試集自動(dòng)判定候選補(bǔ)丁的質(zhì)量,目標(biāo)是輸出通過全部測試用例的程序補(bǔ)丁.Le等人[16]提出GenProg方法，假設(shè)修復(fù)錯(cuò)誤的代碼碎片存在于待修復(fù)程序所在的源代碼中，利用遺傳算對這些代碼碎片進(jìn)行交叉變異生成候選補(bǔ)丁并使用測試集檢測輸出補(bǔ)丁的正確性.Kim等人[50]提出PAR方法，假設(shè)修復(fù)錯(cuò)誤的素材存在于其他項(xiàng)目的源代碼中，通過人工定義修復(fù)模板并隨機(jī)選擇約束變異操作生成候選補(bǔ)丁，克服了基于遺傳算法的隨機(jī)變異產(chǎn)生無意義候選補(bǔ)丁的不足.Le等人[25]認(rèn)為不同修復(fù)模板的能力并不相同，優(yōu)先選擇高頻修復(fù)模板生成候選補(bǔ)丁，相比PAR方法提高了補(bǔ)丁生成的精度.Xin等人[32]提出ssFix方法，針對規(guī)模較大的程序中包含的錯(cuò)誤問題，提出基于語法搜索提取相關(guān)代碼片段進(jìn)行變換生成候選補(bǔ)丁.Sidiroglou-Douskos等人[33]和Ke等人[34]分別提出CodePhage和SearchRepair，利用語義搜索獲取和錯(cuò)誤相關(guān)的代碼片段進(jìn)行變換生成候選補(bǔ)丁.Wen等人[27]提出CapGen方法，使用比語句級別更細(xì)粒度的素材以及利用錯(cuò)誤的上下文相似性選擇修復(fù)模板提高補(bǔ)丁的質(zhì)量.程序自動(dòng)修復(fù)和補(bǔ)丁推薦雖然在錯(cuò)誤定位和補(bǔ)丁質(zhì)量判定方面存在不同，但是二者都要生成補(bǔ)丁.程序自動(dòng)修復(fù)的對象一般是程序單一版本中的常見錯(cuò)誤，具有相應(yīng)測試集和調(diào)試報(bào)告用于錯(cuò)誤動(dòng)態(tài)定位、補(bǔ)丁適應(yīng)度檢查和補(bǔ)丁質(zhì)量自動(dòng)判定等.但是在驅(qū)動(dòng)移植場景中不易收集對應(yīng)測試集用于補(bǔ)丁正確性判定，并且驅(qū)動(dòng)移植涉及2個(gè)版本的演化場景，即使舊版本驅(qū)動(dòng)程序有測試集也可能并不適用于新版本.相比使用修復(fù)模板的已有方法，通過錯(cuò)誤代碼形式識別同類錯(cuò)誤修復(fù)實(shí)例提取和選擇修復(fù)模板，先提取修復(fù)模板再利用一些策略選擇合適的修復(fù)模板生成補(bǔ)丁.本文的方法將修復(fù)模板提取和選擇合并為一步，從待修復(fù)錯(cuò)誤原因和來源出發(fā)識別同類錯(cuò)誤修復(fù)實(shí)例，進(jìn)而提取并選擇針對性修復(fù)模板實(shí)現(xiàn)同類待修復(fù)錯(cuò)誤的補(bǔ)丁推薦.

4.2 補(bǔ)丁推薦

補(bǔ)丁推薦是針對具體錯(cuò)誤生成補(bǔ)丁并建議合適補(bǔ)丁的技術(shù).一些錯(cuò)誤修復(fù)場景適合補(bǔ)丁推薦，這些錯(cuò)誤問題沒有或者不易獲取足夠的程序規(guī)約對輸出的補(bǔ)丁進(jìn)行質(zhì)量自動(dòng)檢驗(yàn).補(bǔ)丁推薦建議的補(bǔ)丁可能完全修復(fù)了錯(cuò)誤，也可能還需要開發(fā)者進(jìn)行手工修正.盡管補(bǔ)丁推薦技術(shù)并不能完全保證有效的修復(fù)，但推薦的補(bǔ)丁仍然有助于降低人工修復(fù)的工作量并提高修復(fù)效率，因此形成了一系列補(bǔ)丁推薦的相關(guān)研究.Bader等人[47]通過學(xué)習(xí)靜態(tài)分析發(fā)現(xiàn)的錯(cuò)誤對應(yīng)的修復(fù)模板，用于推薦新發(fā)生的同類錯(cuò)誤修復(fù)補(bǔ)丁.該方法將已有修復(fù)補(bǔ)丁分割成獨(dú)立的編輯腳本，然后通過聚類算法對這些編輯腳本進(jìn)行挖掘并抽象出同類錯(cuò)誤的修復(fù)模板.最后使用獲取的修復(fù)模板上下文去匹配待修復(fù)錯(cuò)誤，并利用修復(fù)模板附帶的上下文對候選補(bǔ)丁排序完成補(bǔ)丁推薦.相比該方法通過上下文識別同類錯(cuò)誤提取修復(fù)模板，本文通過錯(cuò)誤原因和來源識別同類錯(cuò)誤修復(fù)實(shí)例提取模板.Nayrolles等人[48]針對風(fēng)險(xiǎn)commit提交進(jìn)行識別并在提交到中央倉庫之前進(jìn)行補(bǔ)丁推薦，使用克隆檢測技術(shù)對風(fēng)險(xiǎn)提交和一些已知的錯(cuò)誤提交進(jìn)行比較識別潛在的錯(cuò)誤.在潛在風(fēng)險(xiǎn)提交錯(cuò)誤識別之后進(jìn)行補(bǔ)丁推薦，該方法直接推薦匹配的已知錯(cuò)誤提交對應(yīng)的補(bǔ)丁.相比該方法推薦匹配的已有補(bǔ)丁，本文通過針對性修復(fù)模板生成待推薦補(bǔ)丁.Zhang等人[15]針對電子商務(wù)等應(yīng)用軟件中的代碼錯(cuò)誤，在長期的開發(fā)和遷移過程中這些錯(cuò)誤和對應(yīng)的修復(fù)缺少關(guān)聯(lián)關(guān)系的數(shù)據(jù)標(biāo)記，因此無法直接從已知修復(fù)實(shí)例學(xué)習(xí)修復(fù)模板并用于推薦未修復(fù)的相似錯(cuò)誤.針對這個(gè)問題，該方法利用代碼挖掘技術(shù)從歷史開發(fā)倉庫中獲取已有錯(cuò)誤和對應(yīng)修復(fù)的配對，然后使用基于API調(diào)用序列相似性識別同類錯(cuò)誤并進(jìn)行抽象形成修復(fù)模板數(shù)據(jù)庫，用于類似的未修復(fù)錯(cuò)誤的補(bǔ)丁推薦.相比該方法通過代碼挖掘和聚類算法提取修復(fù)模板，本文基于原因和來源識別同類錯(cuò)誤修復(fù)實(shí)例提取模板.Koyuncu等人[49]針對開發(fā)環(huán)境中沒有測試集的情況下，提出基于缺陷報(bào)告(bug reports)的補(bǔ)丁推薦方法.不同于很多傳統(tǒng)的補(bǔ)丁生成方法使用測試集進(jìn)行基于頻譜(spectrum-based)的缺陷定位，該方法利用缺陷報(bào)告進(jìn)行基于信息檢索(information retrieval-based)的缺陷定位確定錯(cuò)誤位置，然后在PAR[50]的基礎(chǔ)上通過人工定義的修復(fù)模板生成補(bǔ)丁并進(jìn)行推薦.

4.3 驅(qū)動(dòng)移植

Rodriguez等人[6]提出Coccinelle自動(dòng)分析驅(qū)動(dòng)針對兼容庫需要修改的變化內(nèi)容，從而輔助驅(qū)動(dòng)適配兼容庫達(dá)到移植驅(qū)動(dòng)的目的.Thung等人[7]通過分析內(nèi)核commit信息，以推薦系統(tǒng)的方式給出驅(qū)動(dòng)移植輔助信息.具體通過遍歷移植區(qū)間中內(nèi)核commit并找到由于內(nèi)核提交使得驅(qū)動(dòng)出錯(cuò)的commit提交點(diǎn)，然后在該提交點(diǎn)commit中進(jìn)一步分析移植相關(guān)的代碼變化用于輔助后向移植，主要推薦的變化示例包括更改記錄訪問、刪除函數(shù)參數(shù)、函數(shù)名的變化、常數(shù)變化和IF條件變化等類型.Lawall等人[8]發(fā)現(xiàn)驅(qū)動(dòng)移植中的一個(gè)錯(cuò)誤問題所需的輔助信息可能來自多條開發(fā)歷史提交數(shù)據(jù)，針對該類問題，其結(jié)合編譯信息和出錯(cuò)源碼信息提取檢索關(guān)鍵字，再利用補(bǔ)丁查詢語言(patch query language, PQL)查詢開發(fā)歷史提交數(shù)據(jù)獲得移植所需的輔助信息.相比git查詢和Google搜索，該方法通過加強(qiáng)檢索條件并采用PQL查詢進(jìn)一步提高了輔助信息的精度和檢索效率.已有方法給出了驅(qū)動(dòng)移植中一般錯(cuò)誤問題的參考信息和推薦示例，一定程度上減輕了驅(qū)動(dòng)移植的負(fù)擔(dān).而本文的方法針對驅(qū)動(dòng)移植中的接口調(diào)用錯(cuò)誤問題，通過原因識別同類修復(fù)實(shí)例實(shí)現(xiàn)高質(zhì)量的補(bǔ)丁推薦.相比僅提供輔助示例的方法，本文的方法推薦高質(zhì)量補(bǔ)丁進(jìn)一步降低人工修復(fù)的工作量并提高了修復(fù)效率.

5 總結(jié)和展望

本文提出了一種基于錯(cuò)誤根因的補(bǔ)丁推薦方法，通過相同的錯(cuò)誤根因和來源識別同類錯(cuò)誤修復(fù)實(shí)例，通過同類錯(cuò)誤修復(fù)實(shí)例提取并選擇針對性修復(fù)模板實(shí)現(xiàn)同類待修復(fù)錯(cuò)誤的高質(zhì)量補(bǔ)丁推薦.一方面，相比傳統(tǒng)方法通過錯(cuò)誤代碼形式的相似性識別同類錯(cuò)誤修復(fù)實(shí)例，本文針對驅(qū)動(dòng)移植場景中不同調(diào)用點(diǎn)所在同類錯(cuò)誤語句類型和上下文等具體表現(xiàn)形式不相似的問題特點(diǎn)，通過相同的錯(cuò)誤根因和來源識別同類錯(cuò)誤修復(fù)實(shí)例的思路比較新穎.另一方面，本文通過待修復(fù)錯(cuò)誤的原因識別同類修復(fù)實(shí)例，其隱含的修復(fù)模板是唯一的，從而將提取和選擇修復(fù)模板合二為一.相比傳統(tǒng)的補(bǔ)丁推薦方法，本文的方法推薦補(bǔ)丁的正確率有顯著提高，有效降低了人工修復(fù)的工作量并提高了修復(fù)效率.本文除了推薦高質(zhì)量補(bǔ)丁之外還附帶相應(yīng)的錯(cuò)誤原因信息，這些信息能夠輔助開發(fā)者更好地理解錯(cuò)誤和推薦的補(bǔ)丁.

未來，我們計(jì)劃在2個(gè)方面開展進(jìn)一步的研究，我們希望使用機(jī)器學(xué)習(xí)的方法提高相同原因的同類錯(cuò)誤修復(fù)實(shí)例識別正確率.我們還計(jì)劃針對更復(fù)雜的錯(cuò)誤進(jìn)一步研究修復(fù)模板提取和修復(fù)模板刻畫方法，例如修復(fù)實(shí)例中的語句包含多點(diǎn)修改、相互關(guān)聯(lián)的接口調(diào)用以及變化較大的接口不一致錯(cuò)誤等情形.

作者貢獻(xiàn)聲明：李斌提出研究問題，設(shè)計(jì)方法步驟以及完成實(shí)驗(yàn)，撰寫論文初稿；賀也平負(fù)責(zé)把握研究思路，組織技術(shù)討論和全文修訂；馬恒太和芮建武負(fù)責(zé)對技術(shù)路線進(jìn)行討論和分析；李曉卓負(fù)責(zé)對部分實(shí)驗(yàn)數(shù)據(jù)分析和實(shí)驗(yàn)結(jié)果整理.