基于已有實例的Linux驅動程序前向移植接口補丁推薦

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

1(中國科學院大學 北京 100049)

2(中國科學院軟件研究所基礎軟件國家工程研究中心 北京 100190)

3(計算機科學國家重點實驗室(中國科學院軟件研究所) 北京 100190)(libin@iscas.ac.cn)

當前操作系統開發中最大的問題之一是設備驅動程序與對應操作系統版本需要保持同步演進[1].國產操作系統廠商都在開源軟件的基礎上力求提高自主可控性，以Linux為代表的開源操作系統，在我國國產操作系統產品研制中起到了不可替代的作用.Linux內核版本升級非常的頻繁，這些升級提升了內核性能、增強了安全性、增加了新特性以及修復了內核漏洞等，帶來了很多收益.然而內核版本升級后，由于內核版本的變化引入了一些內核接口服務定義的變更，使得驅動程序代碼中對應的內核接口服務調用不再適應更新后的內核接口服務定義，導致驅動程序在新的內核環境中可能出錯或者不可用.為了適配頻繁變化的內核版本并維持已有設備在新內核環境中的可用性，開發者需要對驅動程序進行前向移植.

內核版本變更對驅動程序帶來的關聯影響程度和影響范圍都很大，針對內核版本變更引入的這種驅動程序接口服務調用不一致性問題應該引起更多關注.Padioleau等人[2]通過實證分析發現，由于Linux內核版本的變更使得對應驅動程序在移植中所需的適配性修改代碼量高達35%以上.Padioleau等人[3]還進行了影響范圍分析，該研究發現內核版本中引入的單一變更可能會影響驅動程序中分布在不同文件中的數百個代碼調用點.另外，當前Linux內核版本更新速度越來越快，內核版本研發和發布周期越來越短.雖然少數集成在內核主線版本中的驅動程序會隨內核升級而得到同步更新，但是大量的其他各種類型設備驅動程序需要投入額外成本進行持續的適配性修改，而且維護這些驅動程序和內核版本的一致性更加緊迫.然而針對上述不一致性問題，開發者通常手工進行適配性修改來完成驅動移植工作，其工作量繁重且容易引入新的錯誤，手工移植具有一定技術門檻且移植效率較低.其中人工分析接口服務相關的變更信息和進一步的手工構造適配性補丁更是驅動移植開發者面臨的主要挑戰之一.

針對上述問題，研究者們在驅動移植中間庫輔助適配[4-5]和驅動移植輔助信息[6-7]等方面開展了研究，以便輔助開發者降低移植負擔.其中，Rodriguez等人[5]發現待移植驅動針對兼容庫所需的一致性修改是系統化的并且有一部分修改方式具有相似性，提出手工編寫重寫規則并利用Coccinelle的匹配及轉換技術輔助開發者移植驅動.Thung等人[6]提出遍歷分析引入錯誤提交點的方法縮小了輔助信息的檢索范圍，通過推薦示例語句的變化差異輔助提高了驅動移植的效率.Lawall等人[7]發現驅動移植中的1個錯誤問題所需的輔助信息可能來自多條歷史提交數據，從而結合編譯信息和出錯源碼信息豐富了檢索關鍵詞，相比git查詢和Google搜索提高了輔助示例信息的檢索精度和效率.上述已有研究提高了輔助信息本身的檢索精度和效率，一定程度上減輕了驅動移植開發者的負擔.但是上述輔助方法并沒有對構造適配性補丁所需的細節信息進行深入分析，因此還需要開發者進一步分析輔助信息包含的內容和出錯代碼并人工構造補丁，輔助能力依然存在限制.

相比輔助信息，如果有高質量的適配性補丁輔助驅動移植開發者，輔助效果會更好.Tao等人[8]通過實證研究指出，當開發者有高質量的補丁做輔助的時候，錯誤修復的正確率會大幅提升.和上述已有研究的輔助信息不同，本文的主要研究目標是進行驅動移植場景中高質量的補丁推薦.更具體地說，本文主要聚焦在驅動移植場景中接口錯誤的適配性補丁推薦(由于宏替換和接口性質相似，本文也將其歸為接口錯誤).從開源Linux開發情況來看，接口錯誤和條件錯誤在所有Linux程序出錯類型中占比最高[9].因此，輔助提升驅動程序移植中接口錯誤的修復效率，對降低驅動移植開發者的負擔具有重要的意義.

一般錯誤的補丁自動生成技術和驅動移植補丁推薦存在區別和聯系，除了錯誤定位和補丁質量判定存在差異，驅動移植接口補丁推薦問題和一般錯誤補丁自動生成技術中的候選補丁生成問題類似，兩者都需要將錯誤語句或者代碼片段通過某種形式的修改或者轉換形成正確的代碼[6].一般錯誤的補丁生成技術中如何提高候選補丁的質量是關鍵研究問題之一[10-14]，其通過選擇針對性模板和推測合適的補丁內容等素材提高候選補丁的質量[15].其中選擇模板的已有研究通過頻度選用模板[16]并沒有考慮待修復錯誤問題的特點，考慮上下文信息選用模板[17]相當于把錯誤問題的特點簡化為上下文的特點,而充分考慮錯誤問題的特點才能獲取針對性的素材.本文認為分析錯誤本身的特點是選擇針對性素材的另一個可能的突破口.

本文利用和出錯接口問題相似的歷史開發信息分析驅動移植接口錯誤本身的特點，根據錯誤問題特點區分針對性的細粒度素材生成待推薦補丁.觀察發現，依賴相同內核接口服務的多個不同驅動程序之間存在相同或相似的內核接口調用，如果內核版本升級一段時間之后，其他驅動的開發歷史中可能存在和出錯接口相同或相似的接口復用及變更信息，本文將這些變更代碼稱為已有實例.即已有實例中包含復用接口隨內核定義變更而演化的接口使用信息，不同驅動程序的開發歷史中針對同一接口的代碼復用和適配性變更作為一組已有實例.因此，本文通過尋找和出錯接口問題相似的一組已有實例分析錯誤問題本身的特點，即出錯接口語句和相似已有實例的共性揭示了錯誤本身的特點，借助已有實例提取和分析針對性補丁素材并生成高質量待推薦補丁.

然而相比人工對這些實例代碼片段的分析和利用，工具直接利用這些已有實例生成候選補丁并不簡單(第1節進一步詳細地舉例說明).進一步分析發現，由于內核接口定義變更的共性(變更方式由內核組統一維護)和驅動程序使用內核接口可能引入的多樣性(例如驅動在接口調用中使用私有變量作為實參)，一組已有實例中包含的內容呈現共性和個性2種特征.因此，本文將細粒度補丁素材拆分為接口修改方式(接口定義變更的共性，類似模板)和修改內容(多樣性)2類遞進素材作為入手點.但是由于接口修改方式隱含在信息量龐大、提交風格存在差異的歷史開發信息之中，而接口修改內容的多樣性又使其難以統一枚舉，因此準確地獲取2類素材并不容易.為了獲取針對性的接口修改方式，本文面臨縮小搜索空間降噪、過濾干擾獲取有效已有實例、提取針對性修改方式3個技術問題.本文首先通過分界點計算確定一個較小的有效歷史開發信息搜索區間，然后在有效區間中獲得一組候選已有實例并利用相似度計算對其排序確定有效實例，最后基于抽象語法樹(abstract syntax tree, AST)的細粒度差異比較技術[18]提取有效實例隱含的修改方式，再通過計算修改方式的頻度提高針對性.針對接口修改內容的多樣性困難，本文提出了一種基于已有實例修改內容字段差異特征的分類算法，通過區分共性和個性2類修改內容，然后根據修改內容的特點再分別從歷史開發信息和出錯點源碼上下文2種不同數據源提取.區分類型之后共性內容刻畫的共享名稱提取相對簡單，而針對個性化修改內容刻畫的私有名稱，本文具體結合局部性原則和命名規則相似計算等技術從出錯點上文源碼中提取.最后利用上述方法獲取的細粒度素材，采用編輯腳本技術[19]生成待推薦補丁并自然利用素材的優先級對補丁進行排序.

本文主要貢獻包括：

1) 針對驅動前向移植中，驅動程序接口調用和內核接口定義不相適配的錯誤問題，提出基于歷史開發信息提取細粒度素材合成候選補丁并進行推薦的方法.根據文獻調研分析，這是一種專門針對驅動前向移植中接口錯誤而設計的補丁推薦方法.

2) 面對提取有效接口修改方式的困難，本文結合驅動前向移植中內核接口復用的問題特點，提出從出錯接口問題相似的歷史解決方案(已有實例)中提取針對性的修改方式，即通過已有實例的媒介作用分析錯誤特點，結合分界點識別、相似度計算、頻度計算等技術和啟發式規則提升接口修改方式的有效性.

3) 面對修改內容的多樣性困難，本文提出了一種基于已有實例差異特征的分類方法，通過區分共性和個性內容再從不同特點的數據源分類提取；其中針對不易提取的個性化修改內容，本文結合局部性原則和命名規則相似計算等技術從出錯點上文源碼提取，實驗顯示本文的方法能夠推薦多種不同類型驅動程序中7類接口調用錯誤所需的補丁，有效補丁占比約67.4%.

1 動 機

在驅動前向移植場景中，本文定義內核版本K1的新版本為K2，驅動D1在內核K1上可正常使用，開發者希望將D1手工移植到K2上并達到可以正常使用的目的.D1中調用的內核接口服務由于在新內核版本K2環境下“定義-使用”鏈可能被打破，導致D1驅動在該環境下出錯.開發者希望引入一系列的補丁P修復D1中的錯誤后生成新的驅動D2，使得驅動D2在內核K2上正常運行.

本文的研究聚焦在驅動前向移植過程中發生的接口錯誤.圖1是實際網卡驅動程序e1000移植中根據編譯日志提取的接口錯誤，在這個實例中內核K1為Linux-3.5，內核K2為Linux-4.1，現在將驅動D1為e1000移植到內核K2版本上.-語句表示將要被替換的出錯語句，其中1個出錯接口__vlan_hwaccel_put_tag為行6語句，該接口將vlan報文信息記錄到skb中供協議棧使用；+語句表示將要更新的補丁語句，本文期望推薦行7的補丁語句給開發者修復該錯誤.

在這個示例中，我們發現內核升級一段時間之后，由于內核接口的復用其他驅動程序開發歷史中存在的和D1驅動出錯接口__vlan_hwaccel_put_tag相同的接口復用及接口變更代碼片段信息，包含這些接口復用和變更的代碼片段本文中稱之為對應接口的已有實例.針對圖1示例中的出錯接口，我們通過人工分析內核版本K1到K2區間中其他驅動的歷史開發信息，獲得了一系列和出錯接口相關的已有實例.其中2個已有實例為飛思卡爾和IBM的網卡驅動程序開發歷史中的代碼片段，圖2所示包含了__vlan_hwaccel_put_tag接口分別在上述2個驅動程序歷史開發信息中的接口使用和變更情況.

Fig.2 Existing instances in git repository of driver development history

Fig. 3 Structure of patch recommendation for driver porting interface error

進一步分析圖2的已有實例，我們發現針對出錯接口的一組已有實例語句之間存在共性的同時也存在差異性.更具體地說，由于內核接口的定義和變更由內核開發組統一維護，因此一組已有實例之間語句的共性主要體現在接口的修改方式.例如圖2實例的修改方式都是“增加出錯接口的第2個參數”.而由于驅動調用接口時調用語句可能引入差異性，導致修改內容可能呈現多樣性.例如圖2實例新的接口中第3個參數名稱分別采用vid，fcb→vlctl，cqe→vlan_tag不同的命名方式，而增加的第2個參數htons(ETH_P_8021Q)在該示例中雖然相同，但在其他情況下也可能呈現多樣性.同時，接口__vlan_hwaccel_put_tag的調用也可能存在于不同形式的語句中，例如條件、循環等不同情形或者一些復雜的語句形式中.因此，一方面，根據本文的觀察和分析，在歷史開發信息中存在類似上述示例中的已有實例，可以通過有效的方法提取并用于解決接口錯誤的補丁推薦問題；另一方面，由于調用接口所在的語句形式、參數名稱差異、上下文環境等可能存在差別，接口修改內容可能存在多樣性，因此通過簡單的匹配無法獲得有效的已有實例，更無法通過匹配等簡單操作獲得補丁.除了以上差別，由于龐大的歷史開發信息數量和提交風格等其他干擾性因素的存在，識別和提取有效的已有實例以及細粒度素材合成待推薦的高質量候選補丁并不容易.

2 方法概述

首先介紹方法的整體結構，如圖3所示，本文的方法輸入包括舊版本驅動源碼(待移植驅動)、新舊版本內核源碼(新版本內核為前向移植的目標內核版本)、新舊版本內核之間的歷史開發信息(git倉庫)，輸出內容是舊版本驅動移植到新版本內核過程中，針對驅動程序代碼中接口調用錯誤推薦的候選補丁列表.本文針對驅動移植中發生的一系列出錯接口，采用迭代方式逐個生成候選補丁列表，主要包括已有實例抽取和待推薦補丁生成2部分，生成的補丁經過排序推薦給驅動移植開發者進行補丁質量判定.本文借助已有實例提取針對性的接口修改方式和修改內容的細粒度素材合成待推薦補丁.其中，接口修改方式刻畫共性特征提供修改方式的素材，接口修改內容刻畫多樣性特征提供修改細節的素材.例如，針對驅動前向移植中的某個出錯接口，本文需要確定該接口修改方式應該采用修改接口名稱，還是增加接口參數或者修改接口類型等修改方式素材，還需要分析該接口修改內容的名稱應該使用哪個具體的新接口名稱、增加的參數應該使用哪個具體參數名稱或者接口類型需要替換為哪個具體類型等細節名稱素材.

然而，準確地提取針對性的接口修改方式和修改內容2類細粒度素材并不簡單.針對某個出錯接口，即使從龐大的歷史開發信息代碼變更片段中找到了有效的接口修改方式，由于修改內容的多樣性使得該類細節素材依然難于統一提取.進一步來說，各個驅動程序在具體調用內核接口時可能采用各不相同的命名方式或者編碼風格.例如，不同的驅動程序調用某個相同內核接口時，由于內核版本升級該接口定義的變更要求具體調用時增加某個參數.然而該參數名稱可能來自于各個驅動項目的私有局部變量，或者存在驅動程序各自定義的全局變量、常量作為實參等情形.因此，這種修改內容的多樣性情形往往難于統一提取和枚舉.

為了獲取針對性的接口修改方式，本文提出從出錯接口問題相似的歷史解決方案(已有實例)中提取針對性的修改方式素材.借助和出錯接口問題相同或者相似的一組已有實例作為媒介，通過分析接口錯誤特點提升接口修改方式提取的針對性.利用上述思路提取針對性接口修改方式并不簡單，存在3個技術問題：1)歷史信息數量龐大且提交風格迥異，如何確定一個較小的有效區間減少檢索結果的噪聲；2)有效區間中依然存在大量不相關的干擾實例，如何從中獲取針對出錯接口的一組有效已有實例；3)有效已有實例中包含的接口修改方式可能依然存在差異性，如何從中提取有效的接口修改方式.為了解決上面3個技術問題，首先，受到已有研究[6]的啟發，本文采用分界點拓展出1個包含有效已有實例的區間(3.1.1節).進一步來說，由于驅動調用內核接口而使得內核和驅動之間存在接口“定義-使用”鏈的依賴關系，而分界點提交的commit中接口定義變更打破了這種依賴，因此分界點之后驅動程序才會陸續提交對應的變更適配commit.本文將分界點commit臨近的內核版本到待移植的目標內核版本作為有效區間，該區間描述了檢索出錯接口對應已有實例的窗口邊界.其次，如何從有效區間對應的歷史開發信息中獲取有效已有實例.分析歷史開發信息發現，由于相同接口及變更代碼實現相同或相似的語義功能，來自不同驅動程序對同一內核接口復用的一組已有實例中其接口調用語句也呈現相似性特征：接口調用點具有使用形式和上下文結構的相似性.基于以上分析，本文將已有實例擇優問題轉化為排序問題.首先基于接口錯誤關鍵字等信息從有效區間提取一組已有實例候選集合(3.1.2節)；然后利用相似度計算技術對其進行排序(3.1.3節)；最后，針對某個出錯接口問題對應的top-N已有實例，為了獲得已有實例中2條語句內部隱含的變更方式，本文利用AST級別的細粒度差異比較技術比較2條語句的變化類型抽取接口修改方式，并結合top-N順序、頻度和驅動類型等多維信息計算權重對其進行排序確定有效接口修改方式(3.2.1節).

為了克服接口修改內容多樣性的困難，本文采用更加細致的方式推測有效的修改內容.本文發現接口修改內容刻畫的名稱多樣性特征可以進一步分為共性和個性2種類型，因此依據修改內容的名稱特點分別提取是一種可能的提取思路.讓我們進一步分析這個問題：1)共性修改內容更傾向于共享和全局性名稱(例如全局接口名稱)，經常1次定義或者賦值后在多個驅動項目中共享使用，因此歷史開發信息中往往包含各種共性修改內容；而個性化修改內容一般是局部和項目私有的成員名稱(例如私有變量名稱、私有參數名稱等)，往往由各個驅動程序定義并在出錯點附近的源代碼上文賦值或者初始化之后使用，呈現出定義和使用的局部性特點，因此個性修改內容更可能存在于出錯驅動程序上下文源代碼中.2)分析一系列出錯接口對應的每組已有實例，發現其中的修改內容字段呈現如下趨勢：個性化修改內容在出錯接口對應的一組已有實例中接口修改內容字段各自不同的比例更高，而對于共性修改內容往往該字段相同的比例更高.因此，本文首先基于一組已有實例修改內容字段的差異特征對其進行分類，為了獲得已有實例語句中修改內容刻畫的名稱差異，具體采用AST差異比較技術抽取2條語句修改內容字段的值并利用編輯距離比較名稱差異；然后再根據分類情況分別從歷史開發信息和驅動程序出錯點源碼上下文2種不同數據源提取修改內容(3.2.2節).區分類型之后共性內容刻畫的共享名稱提取相對簡單，而針對個性化修改內容刻畫的私有名稱，本文具體結合局部性原則和命名規則相似計算等技術從出錯點上文源碼中提取.

基于以上步驟提取的細粒度素材列表，候選補丁生成和推薦(3.2.3節)首先結合上述細粒度素材給出補丁定義，然后依據定義生成期望的候選補丁并很自然地利用素材優先級對候選補丁進行排序和推薦.綜上所述，本文的方法針對驅動前向移植中出錯接口候選補丁生成問題，采用迭代方式逐個生成候選補丁列表，最后以推薦方式輸出并通過人工判定補丁質量.

具體結合圖1和圖2示例進行說明，第1階段已有實例提取中，首先通過提取編譯日志中的錯誤分析出錯接口名稱和所在位置等信息.示例中__vlan_hwaccel_put_tag接口出錯，具體的出錯位置L是driversnetethernetintele1000e1000_main.c文件中的4012行.然后通過獲取的接口名稱關鍵字構造一組查詢，再從編譯遍歷過程確定的有效區間r(r為集合R中某個出錯接口對應的有效區間項)檢索歷史開發信息，接著利用啟發式規則清洗數據之后形成已有實例候選集合S，最后對出錯點語句和候選實例中的語句利用相似度計算獲得top-N有效已有實例.示例__vlan_hwaccel_put_tag接口對應的top-N已有實例中，其中前2個實例為Freescale和IBM的網卡驅動程序開發歷史中對該接口的使用和變更代碼片段.第2階段補丁推薦，首先對有效已有實例進行細粒度差異比較和分析提取生成候選補丁所需的素材列表.其中，通過頻度計算等技術獲得示例接口的top-1修改方式OP為對該接口“增加第2個參數”，根據本文給出的算法判定接口修改內容C即示例中增加的參數屬于公有參數且提取的唯一修改內容為“htons(ETH_P_8021Q)”全局函數.最后使用上述素材列表，利用基于AST的編輯腳本技術合成top-1候選補丁并推薦給驅動移植開發者：將driversnetethernetintele1000e1000_main.c文件中的4012行的語句修改為“__vlan_hwaccel_put_tag(skb,htons(ETH_P_8021Q),vid);”.

3 基于已有實例的補丁推薦

為了更加規范地描述已有實例以及其中包含的相關變更操作，本文首先給出已有實例的定義，具體借助抽象語法樹進行刻畫.抽象語法樹是一種源代碼語法結構的統一抽象表示，本文將代碼片段的抽象語法樹看作1棵有序的樹，每個節點代表程序語句中的1個元素.本文定義源代碼語句中的某個元素為節點n，那么Value(n)表示節點n的值，Type(n)表示節點n的類型.例如，如果節點n表示示例1語句中的出錯接口字段，那么Value(n)表示出錯接口名稱__vlan_hwaccel_put_tag，Type(n)表示該節點是函數類型.Parent(n)和Children(n)分別表示節點n的父節點和孩子節點，Index(n)表示節點n在其孩子列表中的索引號，Root(t)表示抽象語法樹t的根節點.

基于以上描述，那么本文給出如下定義.

定義1.已有實例集合S.已有實例集合S={s1,s2,…,sm}，則每個實例sk(1≤k≤m)僅包含1個語句對的遷移(-語句和+語句)，遷移可能包含1個或多個修改操作(單個修改操作是對某個葉子節點的變更；本文將多個修改操作刻畫為單個修改操作序列，結果是對1棵子樹的變更)，每個具體的修改操作來源于如下3種修改操作集合.

1)Add(n,n1,i).表示在節點n的孩子序列號為i的位置之后增加節點n1.

2)Replace(n,n1).表示使用節點n1替換節點n.

3)Delete(n,i).表示刪除節點n的孩子序列號為i的葉子節點.

定義2.接口修改方式OP.OP定義為一個或一組抽象的修改操作，即表示為單個節點或者子樹中的多個節點類型發生的變化.一種接口修改方式是一個節點類型或者一組節點類型的變化，每個變更操作為：

Add(Type(n),Type(n1),i).表示在節點類型為Type(n)的孩子序列號為i的位置之后增加節點類型Type(n1).

Replace(Type(n),Type(n1)).表示使用節點類型Type(n1)替換節點類型Type(n).

Delete(Type(n),i).表示刪除節點類型Type(n)孩子序列號為i的葉子節點.

定義3.接口修改內容C.C定義為一種接口修改方式生效后引入的節點變化內容，即修改內容表示為變化節點的值.

如果修改操作為增加和替換操作，則C=Value(n1)；如果修改操作為刪除操作，則C=Value(Index(i)).

結合圖1和圖2中的示例對定義1～3進一步說明.來自Freescale和IBM網卡驅動開發歷史的2個實例分別包含一組語句的遷移，遷移操作均為Add(n,n1,2)，表示在n節點__vlan_hwaccel_put_tag的孩子序列號為2的位置增加n1子樹htons(ETH_P_8021Q)，n1子樹包含4個元素的葉子節點.則接口__vlan_hwaccel_put_tag的修改方式OP為Add(Type(n),Type(n1),2)，表示“在接口的第2個孩子位置增加參數”(n1子樹變更序列中各葉子節點變更操作類型相同)，刻畫了圖2已有實例中的接口修改方式.接口__vlan_hwaccel_put_tag的修改內容C為Value(n1)(由于n1子樹變更序列中變更操作類型相同，變更值可以按變更操作序列順序合并)，表示待增加的參數為“htons(ETH_P_8021Q)”，刻畫了圖2已有實例中的接口修改內容.

3.1 有效已有實例提取

3.1.1 接口錯誤和有效區間識別

根據第2節所述，為了提升細粒度補丁素材的針對性，本文借助歷史開發信息中的已有實例提取補丁素材.然而整個歷史開發信息數量非常龐大，由于內核和驅動程序代碼中的接口“定義-使用”的依賴關系，驅動程序移植問題中開發人員一般使用新舊版本內核區間對應的驅動程序開發歷史分析輔助信息.然而內核和驅動開發歷史信息更新頻繁，上述區間對應的歷史信息數量依然龐大，尤其驅動移植版本區間跨度較大時對應區間的歷史信息數量更多，這種龐大的檢索空間可能會對檢索結果引入更多的噪聲.因此，本文通過提取出錯接口相關的信息用于構造檢索關鍵詞，同時確定一個較小的有效區間歷史信息窗口用于限定搜索邊界.

首先，本文需要確定出錯接口相關的信息.由于內核和驅動程序之間存在接口的“定義-使用”依賴關系，而內核升級可能打破這種接口“定義-使用”鏈.這種打破接口“定義-使用”鏈的錯誤位置，編譯器在語法檢測階段能夠給出錯誤報告，其中大部分包含準確的出錯位置行號信息.因此，本文采用編譯的方式，在新版本內核環境中編譯舊版本驅動程序并從編譯錯誤日志中提取出錯接口相關的信息.根據先驗知識，通常接口相關的編譯錯誤有3類報錯字段，具體包括：excepted，implicit and undeclared,arguments.其中excepted通常是宏定義相關的錯誤(由于宏替換和接口性質相似，本文也將其歸為接口錯誤)；implicit and undeclared是接口名稱相關錯誤，例如接口名稱變化、接口類型變化、接口聲明所在引用文件變化等；arguments通常和接口參數錯誤相關，例如參數增加、參數減少、參數類型改變等.每一類語法錯誤都具有較為豐富的信息，具體包括錯誤類型、出錯接口所在源碼文件路徑信息、出錯接口名稱、出錯接口所在源碼文件的行號位置L等.需要特別說明的是，雖然編譯過程已經可以獲取3類接口錯誤，但這種錯誤類型粒度太粗，提示的修改方式對于生成待推薦補丁的針對性依然不夠.本文使用編譯日志中提取的豐富內容，通過檢索獲取的已有實例進一步提取細粒度的補丁素材.

然后，如何獲得一個較小的有效區間歷史信息窗口.由于內核和驅動中接口“定義-使用”鏈的依賴特點和接口先定義后使用的原則，舊內核版本到新內核版本區間中引入的某個元素定義變更，導致使用該元素舊定義的驅動程序在新內核版本環境編譯報錯.分析以上過程，我們發現該元素定義變更是新舊版本內核之間的某次提交導致的.由于該元素定義變更之后，其他驅動的開發歷史中才可能變更使用該元素新的定義.因此，該元素定義變更的提交點所在版本到新內核版本之間的區間為該元素對應的有效區間r，然而如何確定該元素定義變更的提交點.本文通過遍歷內核代碼提交找出導致待移植驅動由編譯正確變為編譯出錯的內核commit提交點，本文稱之為分界點.那么針對每個出錯接口，該分界點所在內核版本到新內核版本的有效區間r組成了有效區間集合R.由于該分界點提交之后內核不一定會發布對應版本，具體方法中本文使用分界點所在的鄰近內核小版本作為有效區間的起始版本.需要說明的是，本文和已有方法[7]存在不同，該方法的潛在假設是出錯元素對應的定義變更和使用變更同時出現在該分界點所在的commit中，然后在該分界點commit尋找使用變更信息并用于分析驅動后向移植的輔助示例.該方法相當于在其假設條件下僅使用分界點所在的commit中元素的使用信息，而本文通過分界點擴展出一個有效區間，在更一般的情況下通過有效區間窗口檢索更多的和出錯接口相關的接口變更使用信息.

3.1.2 已有實例候選集

基于3.1.1節獲取的出錯接口信息和對應的有效區間集合R，針對每個出錯接口，本文通過構造git檢索關鍵字在對應有效區間r中進行檢索.具體查詢可構造為如下結構，git log--pretty=formate:“%h id HashID%s Message”-no-merges-p-S‘API name’ VKrVK2-dirdirvers>API-name-log.txt.其中API name是出錯接口名稱，有效區間在Kr和K2內核版本之間，Kr為對應分界點提交鄰近的內核版本，-dir標識待檢索的驅動項目開發歷史，出錯接口的使用變更信息來自有效區間對應的驅動開發歷史.

然而，驅動程序開發歷史中的commit提交信息可能包含缺陷修復、新特性開發或者二者的混合提交，一些不規范提交會引入大量噪聲，為已有實例的有效提取造成干擾.為此本文設計了3個啟發式規則對上述commit檢索和提取過程進行限制和過濾.為了提取符合定義1刻畫的已有實例集合S，本文設計3個啟發式規則：

1) 由于接口錯誤不同于其他類型錯誤可能引入大塊代碼變更，往往接口調用的變更僅涉及2條語句，因此本文在匹配包含出錯接口關鍵字的基礎上進一步裁剪commit片段中的其他干擾代碼，過濾后的commit代碼片段僅包含2條語句的代碼對.即代碼對僅包含減掉1條包含出錯接口名稱的語句，緊接著再增加1條變更語句的情況，具體由于長語句換行等可能是占用行2～4修改量(使用正則表達式識別有些語句因為編碼過長導致存在換行的情況).

2) 本文發現編譯日志給出的錯誤類型信息雖然粒度太粗(如宏定義錯誤、接口名稱錯誤、參數錯誤3類)，卻可以用于過濾檢索結果.因此，本文盡可能讓檢索獲得的commit代碼變更和接口對應的出錯類型信息一致，即進一步過濾掉和出錯類型不符的同名字段變更、大代碼塊變更等提交導致截取實例錯誤(例如commit中存在多行連續刪除后多行連續增加代碼的變更情形，導致-+語句的配對匹配錯位)可能類型不匹配的情況.分析發現上述不同類型的變更各有特點，例如，宏定義一般使用大寫形式，接口名稱相關代碼往往采用駝峰命名規則(如大小寫混合等)，而參數一般對應的代碼變更在括號區間中.因此，本文首先將集合S中的每個已有實例中包含的2條語句作為文本序列，分別按語句中出現的token依次分行(每個token占1行)，使用diff-c或者diff-u的輕量級比較方法識別出存在變更的token.然后再使用上述特征過濾和錯誤類型不符的實例，具體實現通過正則表達式匹配具體實例中變更token的特征.

3) 還需要去除冗余和重復的已有實例，因為驅動開發中可能存在代碼塊的復用、回滾或者冗余功能等，具體通過計算每個已有實例的散列值并進行比較后剔除冗余.使用上述啟發式規則對檢索數據進行清洗，過濾掉一些干擾和冗余信息，最后形成每個出錯接口對應的已有實例候選集合S.

3.1.3 已有實例相似度計算

針對上述步驟輸出的已有實例候選集合S，很多情況下實際提取的實例數量較多且質量存在差異.為了提高生成待推薦補丁的質量和效率，本文需要優先利用和出錯接口問題特點匹配的有效已有實例.如何從實例集合S中進一步識別出有效已有實例，本文利用相似度計算將其轉化為排序問題.具體來說，針對1個出錯接口和對應的1組已有實例候選集合S，本文通過計算出錯接口所在的語句和一系列對應已有實例中語句的相似性，對候選集合S中的已有實例進行排序并選擇top-N用于后續細粒度補丁素材的提取.本文計算2組語句內部的相似性，并依據求和函數的計算結果SUM進行已有實例的排序.

1)SUM1.表示已有實例和出錯語句之間的相似度，度量已有實例中將要刪除的語句(-語句)和出錯語句之間的相似度.如果已有實例中的減語句和出錯語句越相似，那么該已有實例的使用場景和語義越接近出錯語句的實際情況.因此本文認為已有實例中的減語句和出錯語句越相似，則表示該實例和出錯語句的錯誤問題越相似.

2)SUM2.表示已有實例中語句之間的相似度，度量已有實例中將要刪除的語句(-語句)和將要增加的語句(+語句)之間的相似度.根據已有研究[20]的啟示，出錯語句和補丁語句的相似度越高，則該補丁正確的可能性越高.事實上，已有實例中包含的加減2條語句可以認為是實例所在驅動中出錯語句和對應的補丁語句.因此2條語句的相似度越高，則表示該已有實例在其所屬驅動中的語義變更正確的概率更高.

基于本文的分析：使用相同內核接口服務的不同驅動程序存在相同或相似的接口調用，而復用相同內核接口服務的不同驅動程序在其對應接口調用點具有上下文結構和使用形式的相似性.因此，本文具體定義2種相似性度量指標：

1) 結構相似性.結構相似性關注2條語句的AST內部結構變化特征，抽取2條語句對應的AST葉子節點值特征Value(n)進行比較.

2) API usage相似性.API usage衡量2條語句中接口使用方式的變化差異，本文將2條代碼語句作為序列并關注AST葉子節點的序列特征，抽取2條語句對應的AST葉子節點類型特征Type(n)進行比較.

綜上所述，本文定義SUM=(SUM1+SUM2)2對已有實例進行排序.即綜合考慮2種相似度，通過SUM1從問題特點相似角度進行排序，同時通過SUM2從參考答案角度進行排序.由于本文在語句級別計算出錯語句和已有實例中減語句，以及已有實例中加減語句之間的相似度，為了避免格式和字符長度等因素的影響，本文不采用字符串相似度比較算法，而是通過相似度計算[21]在token粒度進行相似度比較.針對SUM1和SUM2，每種相似度綜合計算2種相似度指標取算術平均值，結構相似性特征計算2條語句值特征中葉子節點token的交集和并集之間比值作為度量值，API usage相似性特征計算2條語句類型特征中token交集和并集的元素數量比值作為度量值.

每種相似性特征的度量值計算方法為

其中，Sim表示2條語句之間相似度，取值范圍在0～1之間.分子表示2條語句分別包含的token1和token2值集合或類型集合的交集數目，分母表示2條語句所包含的token1和token2值集合或類型集合的并集數目.最后針對每個出錯接口提取的已有實例候選集合S，通過上述相似度指標計算度量值獲取對應的top-N已有實例列表，作為后續細粒度補丁素材提取的有效已有實例.

3.2 補丁推薦

3.2.1 接口修改方式提取

接口修改方式是候選補丁合成素材之一，本文從出錯接口對應的有效已有實例中提取隱含的接口變更方式，作為出錯接口候選補丁生成的指導信息.本文將已有實例top-N列表作為輸入，采用抽象語法樹級別的細粒度差異比較技術，分別提取top-N中每個已有實例的接口修改方式OP.針對每個已有實例中OP的提取，具體在抽象語法樹級別進行差異比較，本文使用GumTreeDiff框架[22]改造實現對應功能.圖4所示，基于抽象語法樹級別的差異比較包括2個步驟：節點映射和節點差異比較[19].其中在節點差異比較階段，本文比較變化節點并輸出節點類型差異(參見定義2)的變更操作.如果變化節點只有1個，則直接輸出該節點在語句遷移中的類型差異操作；如果存在多個變化節點則會對應一組語句遷移的操作序列，需要進一步將相鄰的操作和節點進行合并.具體將相鄰的相同操作合并，對應的節點合并為子樹并獲取該子樹的根節點類型，目前本文的方法實現處理操作序列僅包含相鄰節點的相同變更操作，且變化節點可以合并為子樹的情形.

Fig. 4 Comparison of fine-grained differences based on AST

然而，由于問題相似度定義的精度以及相同問題解決方案可能存在的差異性，top-N已有實例中提取的接口修改方式OP依然可能存在差異.為了提高候選補丁的生成精度，本文需要優先利用針對性更高的有效接口修改方式OP.針對同一接口，由于內核接口定義的變更范圍在確定的版本區間內是有限的，而不同驅動程序調用相同接口及其接口變更的目的是為了實現相對固定且相同或相似的語義功能.因此在top-N已有實例中，使用相同接口修改方式的多數已有實例對應的OP可能更有效.綜上所述，為了進一步提高OP的針對性，本文對OP進行字典方式排序.首先按top-N已有實例所在順序作為對應OP的基礎排序；然后計算每個OP在top-N已有實例中的頻度，并將頻度作為權重值對OP進行2次排序.具體的2次排序規則包括：權重值高的OP絕對優先，基礎排序相同的OP權重值高者優先.

進一步地，我們發現相同類型驅動的開發歷史中相同或者相似的問題對應的解決方法更接近，因此利用OP所在已有實例的驅動類型和出錯驅動的類型對OP排序的優先級再次進行調整.具體通過計算出錯接口所在文件和OP對應已有實例所在文件的路徑前綴相似度，確定兩者驅動類型的相近程度.首先分別計算出錯接口語句所在文件和各OP對應的已有實例所在驅動文件兩者的公共路徑前綴，公共路徑前綴的目錄層次越深則表示兩者具有更細粒度級別的相同驅動類型，具有更深目錄層次的公共路徑前綴對應的OP則設置更高的優先級.具體來說，Linux系統中“”符號之后的字段表示路徑中的一個目錄層次(每個目錄層次的深度記為1)，本文的方法將路徑看作字符串序列并以單個目錄作為最小比較單位計算公共路徑前綴的深度.綜上所述，本文輸出帶有權重的OP列表.針對圖4示例中的已有實例，提取的接口修改方式OP：“Update(Type(vlan_tx_tag_get),Type(C))”，表示更新接口vlan_tx_tag_get的接口名稱(此階段已知C的類型為接口名稱但具體Value值未提取，即C的值為下文待提取的接口修改內容).

3.2.2 接口修改內容提取

通過上述步驟輸出的接口修改方式OP，刻畫了候選補丁生成所需的修改方式素材，然而僅僅使用OP生成候選補丁相應素材依然不足.由于各個驅動調用接口時可能引入的參數名稱等元素的命名方式或者編碼風格的差異，接口修改內容C在現實世界中存在多樣性.為了提高補丁生成精度，需要對接口修改內容C進行細致分析.我們發現接口修改內容C可以進一步分為共性和個性2種類型，根據第2節分析，歷史開發信息數據源中傾向于包含共性修改內容，而個性修改內容往往存在于待移植驅動出錯點源碼的上下文中.為了細致地分析和提取接口修改內容C，算法1首先對C進行分類，然后根據不同情況再分別從歷史開發信息和出錯點上下文2種數據源提取相應的C.

算法1.區分共性和個性修改內容并分情況提取補丁素材列表.

輸入:接口錯誤語句代碼片段errorP、接口錯誤位置L、權重值最大OP對應的已有實例集合instanceList；

輸出:節點標簽和節點的值Node(l,v)，即C的名稱.

① IFcompare(instanceList,0.9) THEN

②commVar=getModifyNode(instanceList);

③ RETURNNode(comm,Value(commVar));

④ ELSE

⑤varSet=collectVarList(L,errorP,N);

⑥varList=rankByDistance(varSet,L);

⑦ IFcompare(instanceList,M) THEN

⑧commStr=getSubcon(getModifyNode(instanceList));

⑨tempList=varList;

⑩varList=reRank(tempList,commStr);

根據我們在驅動移植場景中的觀察，共性和個性修改內容在已有實例中呈現的趨勢為：個性修改內容在出錯接口對應的一組已有實例中接口修改內容字段各自不同的比例更高，而共性修改內容在對應的接口修改內容字段往往相同的比例更高.本文算法1中使用權重值最大的OP對應的多個已有實例組成的集合中包含的接口修改內容字段區分共性和個性修改內容C，如果該字段大部分相同則為共性C，否則為個性C.其中算法1輸入：errorP表示出錯接口所在程序片段，L表示出錯接口所在位置，instanceList表示該出錯接口對應的權重值最大的OP所在的已有實例集合；算法1輸出：Node(l,v)表示二元組，l表示接口修改內容C的類型是共享名稱還是私有名稱，v表示接口修改內容C的值或值列表(共享名稱C為1個值，而私有名稱C為1個值列表).算法1行①～③，如果權重值最大的OP對應的多個已有實例中接口修改字段90%以上相同，則該出錯接口對應的修改內容C為共性類型，直接返回對應已有實例的修改字段Value()值并設置標簽為共享名稱.行④～，否則該出錯接口對應的C為私有名稱.其中行⑤⑥，根據私有元素的先定義后使用原則，首先收集出錯點所在源碼上文的N條語句中出現的變量、表達式左值和函數實參等(實驗中根據經驗取N=5)；然后基于變量使用的局部性原理，哪些變量或者token離出錯點的距離更近，則更可能被作為候選的私有修改內容C.本文依據候選變量所在的行和出錯點的程序距離對候選C進行基礎排序，具體使用語句間的物理距離作為程序距離進行度量.由于驅動程序源代碼中駝峰命名規則等編程規范使用比較普遍，一些內涵相似的私有名稱或者token(例如，相似接口中使用的參數命名)雖然名稱不同但具有一定相似性，最常見的情形是具有相同的前綴或者后綴.例如，virtio驅動中接口vring_new_virtqueue更新后新增參數KVM_S390_VIRTIO_RING_ALIGN，而其他驅動調用該變更后的接口時新增LGUEST_VRING_ALIGN，VIRTIO_PCI_VRING_ALIGN等具有相似后綴的參數.行⑦⑧，算法1通過判斷權重值最大的OP對應的多個已有實例中接口修改字段的相似度大于M值(實驗中根據經驗取M=0.5)，則提取這些已有實例中接口修改字段的最長公共字符串，commStr表示該子串.行⑨⑩，則利用該公共子串commStr和已收集的候選私有名稱列表tempList之間的相似度對其進行2次排序.具體對字符串長度小于公共子串commStr的候選token保持原有基礎排序，而對字符串長度大于公共子串commStr的候選token依據相似性度量值進行冒泡位置調整，這里使用編輯距離進行2個字符串的相似性計算.行返回私有字段列表的值Value(varList)并設置標簽為私有類型.如果對應已有實例集合中的修改內容字段滿足大于M的相似性要求，則返回經過2次排序的候選列表Value()值，否則返回基礎排序的候選列表Value()值.

3.2.3 候選補丁生成和推薦

結合上述步驟收集的細粒度補丁素材，本文將待推薦的候選補丁定義為P=patch(L,OP,C)[14].其中L表示接口出錯的位置，也是修復該接口的打補丁位置；OP表示出錯接口補丁采用的修改方式，C表示出錯接口補丁采用的修改內容，也可以理解為修改方式OP的參數.整個待推薦候選補丁生成過程，利用已經收集的細粒度素材列表，采用編輯腳本生成技術[19]進行實例化產生推薦補丁列表.

待推薦候選補丁生成階段還需要解決2個問題.1)出錯接口所在語句內部的修改位置如何確定.L即使是準確的錯誤位置，也僅僅刻畫了出錯接口語句所在位置的行號，而接口修改方式OP中的節點及其索引號，刻畫了出錯語句對應的已有實例中引入變更的語句內部相對位置.由于出錯接口待生成的補丁和對應的有效已有實例之間，出錯接口名稱和語句內部引入變更的相對位置相同.因此，本文的方法通過錨定出錯接口名稱并利用權重最大的OP匹配出錯語句中的待修改節點，最終確定出錯接口所在語句內部的修改位置.2)生成的待推薦候選補丁如何排序.由于細粒度補丁素材從不同側面刻畫了待生成補丁的質量，本文的方法很自然地通過合成候選補丁時采用的素材列表優先級確定最終推薦補丁列表的順序.具體來說，本文采用編輯腳本生成技術，依據補丁定義在抽象語法樹級別進行出錯語句的轉換并生成候選補丁，通過補丁素材OP列表和C列表的優先級位置共同確定候選補丁列表的順序.然而上述過程中可能會合成位置錯誤或者語法錯誤的候選補丁，本文對編譯出錯的候選補丁直接拋棄.最后對輸出的順序在前n個補丁列表進行推薦，如果沒有輸出待推薦補丁，則推薦失敗.本文方法進行了細粒度的排序，在實驗中往往第1個候選補丁的質量很高，因此本文直接設置n=1.

針對推薦補丁的質量判定，本文采用人工方式確認補丁有效性.首先每款待移植驅動程序設定歷史上已經針對目標內核版本移植后的1個驅動程序版本為正確的參考程序版本Dbase，然后逐個出錯接口依次進行補丁質量判定，依據參考程序版本中相應的代碼變更片段和推薦的第1個補丁進行人工對比.需要進一步說明的是，目前程序自動修復研究中的一般錯誤補丁生成通過測試集自動判定候選補丁的質量，通過測試集中的全部測試用例的候選補丁被認為是正確的補丁[23].然而，本文研究的驅動移植錯誤補丁采用推薦方式，具體原因為：一方面驅動程序的開發一般由設備制造商主導，現實世界中很難收集充足的驅動程序相關測試集，即使有少量測試用例，驅動程序版本升級和運行環境(內核)變更也會對已有測試集帶來影響，而且還需要真實的驅動設備支持其實際執行；另一方面，程序自動修復研究中一般錯誤的補丁質量判定，由于弱測試用例導致判定結果存在過擬合問題[23-24].也就是說由于測試集并不能刻畫完整的程序規約，使得通過測試集判定的候選補丁依然可能包含錯誤的補丁，輸出的補丁還需要人工2次判定或者使用其他方法進行擇優.針對驅動移植錯誤補丁質量的自動判定，我們將在后續進行研究.

4 實 驗

本節介紹實驗數據集和實驗環境，以及相關實驗結果及其分析.總體來說，本文的實驗期望回答如下2個問題.

問題1. 本文的方法針對真實驅動移植中的接口錯誤進行補丁推薦的有效性如何？

問題2. 本文的方法針對驅動移植接口錯誤進行補丁推薦的性能如何？

4.1 數據集建立

本文的實驗在真實的前向移植場景中進行，目標是檢驗舊版本驅動程序的原有功能在新版本內核環境中復用時針對出錯接口的補丁推薦情況.為了方便檢驗方法的有效性，本文選擇實驗對象中的驅動程序和內核環境依據如下標準.

1) 內核版本從K1升級到K2，K1環境下的待移植驅動D1在升級過程中已經存在K2環境下對應的驅動程序的升級版本Dbase，從D1到Dbase的前向演化過程中引入的變化存在內核接口調用的變更，本文的研究只關注移植過程中發生的接口調用不一致問題.

2) 待移植驅動D1在前向演化過程中所發生的一些接口調用變化，在K1到K2內核區間中已經存在其他驅動對該類接口調用的使用和變更歷史開發commit提交信息.即驅動在移植過程中發生的一些接口調用錯誤，在該區間對應的git倉庫中存在其他驅動程序復用和變更該接口調用的歷史commit提交信息.

3) 待移植驅動D1在原來的舊內核版本K1上編譯正常通過，但D1在待移植的新內核版本K2上編譯產生的編譯錯誤日志包含接口調用錯誤.

通過以上標準并結合實際實驗資源的綜合考慮，篩選和收集待移植的驅動程序數據集.確定版本區間K1：Linux-3.5.4，K2：Linux-4.1.0版本，該區間總計跨越61個Linux迭代的內核小版本.最終收集了Linux-3.5.4對應的9款驅動程序，總計包含116個文件和126 097行代碼.表1展示了本文收集的待移植驅動程序數據集的具體情況.

Table 1 Dataset of Driver Porting in the Experiment

4.2 實驗設計

我們實現了本文的方法并形成了驅動移植場景中的接口補丁推薦工具DriverFix.本文采用git log-S構造檢索形成已有實例候選集合S，然后利用啟發式規則和相似度排序獲得top-N已有實例列表，實驗中設置N=5，采用git-2.7.4版本.然后基于GumTreeDiff框架進行抽象語法樹級別的差異比較并提取每個已有實例中包含的OP，通過頻度計算對其進行排序形成有效OP.其中，基于抽象語法樹的差異比較采用gumtree-2.1.2版本，抽象語法樹解析前端采用cgum-1.0.1版本.接著通過算法1區分共性和個性接口修改內容，然后從歷史信息(權重值最大的OP所在的有效已有實例組成的集合)提取共性C，基于變量使用局部性原理和命名規則相似性過濾方法從出錯點上文提取個性C列表.最后根據給出的補丁定義和GumTreeDiff編輯腳本生成算法合成候選補丁，對候選補丁列表進行去重和排序并輸出第1個補丁進行推薦并由人工判定補丁質量.實驗中，對收集的9款驅動分別進行前向移植實驗，針對驅動程序從舊內核K1：Linux-3.5.4版本移植到新內核K2：Linux-4.1.0版本過程中產生的接口錯誤進行候選補丁生成.歷史開發信息git倉庫采用Linux官方主分支信息，使用DriverFix工具依次對每個驅動移植中產生的接口調用錯誤生成待推薦補丁，最后人工確認實驗效果.本文的全部實驗使用ubuntu 16.06 64位操作系統環境，編譯環境使用gcc-5.4.0版本，硬件采用1臺PC機器，4核3.20 GHz Intel CoreTMi5處理器、8 GB內存.

4.3 實驗結果

問題1. 本文的方法針對真實驅動移植中的接口錯誤進行補丁推薦的有效性如何？

表2展示了本文的實驗結果，對4類總計9款驅動程序進行了前向移植，采用本文的方法針對其中的接口調用錯誤進行了補丁推薦.在待推薦補丁生成過程中，依據本文從已有實例中自動提取的接口修改方式OP的不同將接口錯誤自然分為7類，包括宏定義錯誤、接口名稱錯誤、接口類型錯誤、修飾符錯誤、缺少參數錯誤、多余參數錯誤和參數類型錯誤.實驗中，總計針對46個接口調用錯誤生成了34個補丁，其中31個人工確認有效，推薦正確率為67.4%，有效補丁通過和基準版本驅動程序版本Dbase中的對應代碼進行人工比較確定語義相同并進行雙人交叉確認.從各個錯誤類型角度統計補丁推薦情況，總體上修飾符錯誤(99)、多余參數錯誤(22)和函數類型錯誤(33)這3類錯誤補丁推薦準確率最高.從實驗數據分析，前2類確定了有效修改方式是修飾符錯誤和多余參數錯誤這2類錯誤，確定了有效修改方式是去除無效修飾符和無效參數即可生成補丁，而第3類函數類型錯誤在實驗數據集中主要出現的是可以強制類型轉換的情形，因此上述3類錯誤呈現較高的正確率.而函數名稱錯誤(917)從邏輯上是一類簡單錯誤，實驗中補丁生成準確率卻很低.主要原因在于實驗中總計10個錯誤問題沒有找到對應的有效已有實例，其中8個對應函數名稱錯誤，因此在歷史信息中存在對應已有實例的情況下函數名稱錯誤補丁生成正確率依然很高.相比之下，缺少參數錯誤(45)、宏定義錯誤(49)和參數類型錯誤(01)補丁生成正確率較低，主要原因在于有些宏定義需要多參數進行變換，接口修改方式很難刻畫該類復雜變換.另外，針對參數類型錯誤和缺少參數錯誤，由于需要引入新的參數等多樣性修改內容素材，補丁生成的有效性往往較低.其中，針對個性化修改內容素材(14)，本文的方法提取有效性占比25%.

Table 2 Distribution of Recommended Patches Details

表3展示了生成補丁的過程中提取的已有實例所屬的驅動程序項目和對應開發歷史信息.我們分析了實驗中提取已有實例使用到的其他驅動程序歷史開發信息，總體上網絡相關的驅動項目開發歷史占比相對較高，上述現象和本文待移植的驅動數據集中網絡設備驅動占比較高比較一致.另外，實驗中從歷史開發信息獲取已有實例，最后匯總發現使用了17款其他驅動程序包含的已有實例，這些已有實例的總數量(156個)能夠支撐實驗并且不均勻地分布在各個參考的其他驅動程序中.實驗中，有些接口錯誤對應的已有實例較多，而另一些接口錯誤的實例較少甚至沒有找到對應實例(4.4節進一步分析).

問題2. 本文的方法針對驅動移植接口錯誤進行補丁推薦的性能如何？

使用本文的接口補丁推薦工具DriverFix，在實驗中主要時間消耗包括：編譯以及編譯錯誤日志解析、有效區間識別、已有實例提取和排序、OP和C提取及排序、候選補丁生成及排序等部分.具體編譯過程需要迭代提取相應的接口出錯信息、不同驅動程序中相同的接口錯誤語句可以復用已有實例候選集合等信息.圖5統計了9款驅動程序中所包含的接口錯誤在生成對應的候選補丁時消耗的時間，橫坐標為實驗中的9款驅動程序，縱坐標為針對每個驅動程序中的接口錯誤進行補丁推薦消耗的時間，總體上針對各個驅動生成候選補丁的數量和耗時成正比.相比已有研究[7]中提取輔助信息的方法，人工利用該方法輸出的輔助信息構造每個補丁平均耗時在30 min，一方面本文的方法直接推薦候選補丁而并非輔助信息，另一方面本文的DriverFix針對實驗中每個驅動程序推薦接口補丁平均耗時大約在10 min以內，有效提高了驅動移植中錯誤處理的效率.

Table 3 Distribution of Existing Instances Used in Other Driver Development History

Fig. 5 Performance analysis of candidate patch generation

4.4 威脅分析及討論

本文方法的有效性檢測外部威脅主要來自Benchmarks.由于本文使用的數據集相對較小，可能并不能完全代表驅動移植接口錯誤的實際數據分布.但是本文所使用的實驗數據集全部都是真實的錯誤，并且來自不同類型的驅動程序，一定程度上覆蓋了一大類驅動移植錯誤.內部威脅主要來自手工判定補丁質量可能引入誤判.為了緩解這種威脅，本文通過2人分別獨立手工判定生成的候選補丁質量，如果判定結果不一致則該補丁不被計入正確的實驗結果.

以下我們進行威脅分析，同時討論相關的限制以期成為后續可能的改進方向.本文的方法在合成待推薦的候選補丁時使用編譯方式進行定位，編譯方式的靜態定位和運行測試集的動態定位不同，同時編譯報錯信息存在誤報和不準確問題，該問題我們在后續研究中進一步改進.進一步地，我們收集了實驗中的一些失敗案例，進而分析本文通過提取細粒度素材合成候選補丁過程中存在的限制.從實驗結果分析，本文的方法對7類接口調用錯誤有效，為了保證補丁生成的質量，本文的方法采取保守策略.例如，接口變化內容素材C僅考慮來自已有實例commit或者出錯點上文的內容.其中缺少參數和參數類型錯誤需要引入新的修改內容C，如果是個性素材僅考慮出錯點上文數據源有限的較小范圍，未考慮其他類型數據源或者引入新變量進行預先賦值等情形.函數類型錯誤暫未考慮類型不匹配的情況需要對其進行類型轉換等，最大限度地遵守錯誤所在項目的編程規范.函數類型錯誤在手工判定補丁有效性時，只針對接收值和接口返回值類型能夠進行默認強制類型轉換的情況認為有效(例如int型和bool型之間的轉化等).

Table 4 Analysis of Recommended Patches Generation FailureError Type

表4 待推薦補丁生成失敗錯誤類型分析

Table 4 Analysis of Recommended Patches Generation FailureError Type

補丁推薦失敗類別宏定義錯誤接口名稱錯誤缺少參數錯誤參數類型錯誤推薦失敗的補丁數量(推薦失敗補丁數量∕錯誤總數)∕%未找到已有實例28001021.7AST映射和比較出錯200024.3生成的待推薦補丁錯誤101136.5

本文的方法還存在一些不足，我們使用實驗中出現的一些案例進行分析說明.表4統計了待推薦補丁生成失敗或者補丁錯誤的具體情況，其中10個接口錯誤在歷史開發信息中沒有找到對應的已有實例，包括2個宏定義錯誤和8個接口名稱錯誤的待推薦補丁生成失敗；本文推薦補丁的質量客觀上依賴于歷史開發信息中包含的已有實例數量和質量，實驗中總計46個接口錯誤其中36個找到了對應的相似已有實例.有2個錯誤對應的有效已有實例在AST映射階段產生混亂，最終無法提取有效的修改方式OP素材導致補丁生成失敗；還有3個錯誤由于對應已有實例差異較大，或者修改方式刻畫困難等情況導致生成錯誤的待推薦補丁.

失敗案例1.已有實例AST映射失敗.

SET_ETHTOOL_OPS(netdev,&e1000_ethtool_ops);*error code*

-SET_ETHTOOL_OPS(netdev,&atl2_ethtool_ops);

+netdev→ethtool_ops=&atl2_ethtool_ops;

-SET_ETHTOOL_OPS(dev,&typhoon_ethtool_ops);

+dev→ethtool_ops=&typhoon_ethtool_ops.

失敗案例2.已有實例差異大且變換復雜.

PREPARE_DELAYED_WORK(&fd_timer,fd_watchdog);*error code*

-PREPARE_DELAYED_WORK(&old→work,fw_device_update);

+old→workfn=fw_device_update;

-PREPARE_DELAYED_WORK(&hub→init_work,hub_init_func3);

+INIT_DELAYED_WORK(&hub→init_work,hub_init_func3).

失敗案例1顯示的是網卡驅動e1000中的宏定義錯誤待推薦補丁生成失敗，通過分析可以看出找到的已有實例中包含的語句變化復雜.針對該情況，GumTreeDiff框架中的已有映射算法無法匹配正確的節點，導致AST映射失敗.我們人工分析其修改方式為“將出錯代碼中宏定義的第2個參數賦值給第1個參數的ethtool_ops成員并替換出錯的宏SET_ETHTOOL_OPS”，即使AST映射成功，其復雜的遷移語義刻畫也比較困難. 失敗案例2待推薦補丁生成錯誤的主要原因是找到的已有實例差異大且變換復雜，其中Instance1的已有實例AST映射失敗，Instance2的已有實例修改方式為“替換宏定義名稱”，但該實例在Floppy驅動中是錯誤的.另外2個生成錯誤的補丁也是類似失敗案例2的變換情況，比較復雜.綜上所述，針對上述復雜情況，本文的方法依然有待提高，具體包括AST映射和差異比較、個性化修改內容提取等方面還需要引入新的解決思路進行技術突破.

5 相關工作

5.1 補丁生成

補丁推薦和補丁生成雖然是2個不同問題，在技術上卻存在區別和聯系.在錯誤定位和補丁質量判定方面存在差異，但是補丁推薦和候選補丁生成中將錯誤語句變更為正確語句的代碼遷移或者變換兩者具有相同之處.針對一般錯誤問題，Le等人[25]假設修復補丁存在于待修復程序所在的當前項目中，提出GenProg方法利用遺傳算法對候選代碼片段進行變異和交叉組合操作生成補丁，其采用的隨機變異方式會產生很多無意義的候選補丁.Kim等人[26]假設修復補丁可以在其他項目中找到，通過人工定義的修復模板生成補丁并提出PAR方法，通過模板約束隨機變異提高了候選補丁質量.Le等人[16]認為不同模板的修復能力是不同的，通過挖掘人工修復的補丁中所使用的模板頻度，賦予修復模板權重從而進一步提高了候選補丁的質量.Wen等人[17]提出補丁生成技術CapGen，利用AST考慮出錯語句和修復模板的上下文信息選擇修復模板指導候選補丁生成，并提出3種模型獲取補丁修復的內容素材，提高了補丁質量.文獻[16-17,25-26]所述方法相關研究的問題和方法與本文都存在一些不同，文獻[16-17,25-26]所述方法面對的一般錯誤問題場景具有測試集刻畫出錯信息并用于錯誤定位和補丁質量判定，這些測試集作為程序規約可以用于構造適應度函數或者提取錯誤相關的約束條件來指導補丁生成，而本文的驅動移植場景沒有對應測試集卻具有編譯日志.文獻[16-17,25-26]所述方法由于面向的一般錯誤問題目標范圍較大，對應方法往往先預定義高頻模板集合再指導一般問題中常見的具體錯誤生成補丁.而本文的方法面向的驅動移植場景中接口出錯的問題類型相對較少，同時由于內核接口復用的特點，驅動歷史開發信息中可能存在這些接口變更的使用信息，即已有實例.因此本文結合驅動移植中接口錯誤的問題特點尋找已有實例，然后通過已有實例的媒介提升修改方式等補丁素材的針對性，本文提取修改方式的思路可以認為是一種定制模板.和文獻[16-17,25-26]已有方法先有模板集合再選擇模板的思路不同，本文的方法先有出錯接口問題再從對應已有實例中提取針對性的定制化修改方式(通過問題特征找模板).文獻[16-17,25-26]所述方法在當前項目、其他項目數據源中尋找補丁生成素材，而本文的方法和文獻[16-17,25-26]所述方法不同，通過區分修改內容類型再從不同特征的數據源中提取素材.

針對條件錯誤問題，Nopol[27-28]關注Java語言中的條件錯誤并通過測試集提取條件約束，將補丁生成轉化為約束求解問題進行定位和補丁合成.而熊英飛等人[29]提出ACS針對單變量條件類錯誤問題，基于變量間的依賴關系排序、相似上下文代碼片段所使用的謂詞頻率排序等技術，提出了針對條件錯誤的高精度補丁生成方法.針對系統構建領域的構建腳本錯誤，Hassan等人[30]提出利用失敗日志檢索歷史上相似的構建錯誤，再基于歷史修復方案提取模板并枚舉補丁細節素材生成補丁的HireBuild方法.Lou等人[31]通過補充實驗發現HireBuild方法的不足在于不靈活的補丁生成規則并提出新的方法HoBuFF，HoBuFF將構建錯誤問題聚焦在一類常見的配置錯誤(配置項和對應值).該方法提出基于數據流分析并利用構建錯誤日志進行錯誤定位，基于搜索當前項目信息(構建代碼和日志、構建依賴的外部資源)進行補丁素材提取和補丁生成.條件錯誤和構建錯誤研究與本文也具有一定差異，條件錯誤一般需要修改條件(增加減弱)或者增加刪除前置條件等對應的修改方式類型較少，主要困難在于如何合成有效的條件表達式，文獻[27-29]方法具體使用約束求解和上下文相似性計算等技術提取表達式素材.構建錯誤問題也有自身特點，一般沒有對應測試集但存在構建錯誤日志信息，構建語義往往是依賴或者版本問題甚至抽象為鍵值對的配對問題(配置項和對應值).本文中驅動移植的接口調用錯誤本質上由于打破了內核接口“定義-使用”鏈引起的不一致性問題，沒有錯誤對應的測試集信息但是具有編譯錯誤日志和歷史開發信息中的已有實例等信息可以使用.

5.2 驅動移植

Rodriguez等人[5]提出Coccinelle自動分析驅動針對兼容庫需要修改的變化內容，從而輔助驅動適配兼容庫達到移植驅動的目的.Thung等人[6]通過分析內核commit信息，以推薦系統的方式給出驅動移植輔助信息.具體通過遍歷移植區間中內核commit并找到由于內核提交使得驅動出錯的commit提交點，然后在該提交點commit中進一步分析移植錯誤相關的錯誤元素使用變更代碼片段用于輔助后向移植，主要推薦的變化示例包括更改記錄訪問、刪除函數參數、函數名的變化、常數變化和IF條件變化等類型.Lawall等人[7]發現驅動移植中的1個錯誤問題所需的輔助信息可能來自多條commit提交數據，針對該類問題，其結合編譯信息和出錯源碼信息提取檢索關鍵字，再利用補丁檢索語言(patch query language， PQL)查詢歷史開發提交數據獲得移植所需的輔助信息.相比git查詢和Google搜索，該方法通過加強檢索條件并采用補丁檢索語言進一步提高了輔助信息的檢索精度和效率.雖然文獻[5-7]已有研究和本文都使用了歷史開發信息，但兩者有所不同.文獻[5-7]方法是從歷史開發信息檢索驅動移植輔助信息本身，而本文的方法是將歷史開發信息作為輔助媒介提取針對性的細粒度補丁素材.文獻[5-7]方法僅僅提取了輔助信息本身給出了驅動移植中一般錯誤問題的參考信息和輔助示例，一定程度上減輕了驅動移植的負擔.而本文的方法針對驅動移植中的接口調用出錯問題，通過分析輔助信息提高了細粒度補丁素材的針對性，具體利用了歷史開發信息中的已有實例分析錯誤特點并提取針對性的接口修改方式和修改內容等素材進行高質量補丁推薦，進一步降低了驅動移植難度并減輕了人工負擔.

6 總結和展望

本文的特色在于利用出錯接口問題和相似已有實例的共性分析驅動移植的接口錯誤特點，通過已有實例的輔助作用提高了細粒度補丁素材提取的針對性.具體來說：一方面，本文的方法基于已有實例獲取出錯接口修改方式，針對性更強.相比已有一般錯誤候選補丁生成方法，先有模板集合而后通過策略選擇用于具體錯誤問題，本文的方法是先有具體錯誤問題并通過錯誤特征尋找定制修改方式(定制模板)；另一方面，本文的方法分析修改內容的多樣性更加細致，借助已有實例的差異性區分共享名稱和私有名稱等修改內容，區分不同情況從歷史開發信息和出錯點上文源碼2種數據源提取修改內容更加自然.最后，在真實驅動移植場景中的實驗表明，本文的方法能夠對不同類型驅動程序中7類接口調用錯誤進行補丁推薦，補丁推薦的質量較高，有效提升了驅動移植中錯誤處理的效率.

未來，我們計劃在提高驅動移植接口修改方式、個性修改內容提取的質量方面考慮語義信息進行研究，針對驅動移植補丁質量的自動判定等方面進一步開展研究工作，同時在更大規模的驅動移植接口錯誤數據集進行實驗和分析.更進一步地，我們計劃將本文的思想推廣到更一般場景的補丁推薦或者候選補丁生成問題.例如，一些通過代碼繼承關系傳播的同源錯誤修復是一個重要問題，原本相同的軟件開發分支分叉(fork)之后發展為不同定制版本，其中包含的繼承錯誤、繼承錯誤變種和相應補丁之間具有一定的共性實例，值得深入研究.