劉 鵬 胡文超 劉德啟 韓曉霞* 劉揚帆
①(浙江大學信息與電子工程學院 杭州 310027)
②(合芯科技有限公司 廣州 510725)
處理器被廣泛應用在信息系統(tǒng)中,處理器硬件安全是信息系統(tǒng)能被安全使用的前提。隱藏在處理器中的功能性缺陷會導致處理器功能異常、信息被篡改和泄露,嚴重威脅處理器的硬件安全。處理器的功能性缺陷泛指因設計規(guī)范或硬件描述語言的局限性,或者設計人員考慮不周等情況,導致集成電路內部部分電路出現(xiàn)錯誤[1]。在處理器眾多功能性缺陷中,基于指令集架構的指令缺陷是其中最為關鍵的缺陷之一。指令缺陷是指處理器硬件實現(xiàn)中存在的設計缺陷,其導致指令集架構規(guī)范中明確定義行為的指令被錯誤的執(zhí)行。指令缺陷會給處理器系統(tǒng)帶來嚴重的安全威脅,甚至造成巨大的經濟損失[2]。為了使處理器免受指令缺陷的威脅,需要一種方法和工具輔助設計人員快速準確地檢查處理器中可能存在的指令缺陷。由于RISC-V(Reduced Instruction Set Computer-Five)開源、簡潔以及模塊化的特性,RISC-V指令集架構成為自主設計處理器的新方向[3]。因此,本文以RISC-V處理器為例闡述測試序列生成方法用于檢測指令缺陷,其他指令集架構的處理器指令缺陷檢測可借鑒RISC-V的方案實現(xiàn)。
模擬仿真是檢測指令缺陷的主要方式,由驗證人員向處理器注入測試指令序列,將處理器執(zhí)行結果與預期結果進行對比,對不一致的結果進行分析,檢測存在的指令缺陷[4]。因此,檢測指令缺陷的關鍵就是高效獲得高覆蓋率的測試指令序列[5],以快速觸發(fā)指令缺陷。目前存在基于指令格式的約束隨機生成和基于指令格式的覆蓋率驅動隨機生成的兩類測試指令序列生成方法,指令格式保證生成的指令符合指令集架構規(guī)范[6]。
根據(jù)不同指令驗證需求自定義各種指令的功能覆蓋約束是基于指令格式的約束隨機生成方法的一個研究方向, Herdt等人[7]提出了基于約束規(guī)范的隨機生成方法,在指令格式約束基礎上遍歷預定義的各種功能覆蓋約束情況得到測試指令序列。Chupilko等人[8]提出基于執(zhí)行路徑的約束生成模型,通過預定義指令的生成順序以獲取測試指令序列。譚堅等人[9]預先對結果操作數(shù)、操作數(shù)之間、指令內部以及浮點操作數(shù)類型進行功能覆蓋約束定義,再對定義的每種約束情況進行求解,生成測試指令序列。上述方法都需要依賴預定義的功能覆蓋約束,然后對每種約束情況進行遍歷求解,以獲得測試指令序列,雖然可以對已定義的約束實現(xiàn)全覆蓋,但是缺少對功能覆蓋約束的歸納,隨著指令數(shù)量的增多,預定義各種指令的功能覆蓋約束愈加困難,同時人為定義各種約束易造成約束遺漏,而且缺少已生成指令的覆蓋統(tǒng)計,存在指令覆蓋率收斂速度慢的問題。
基于指令格式的約束隨機生成方法的另一個研究方向就是問題映射,IBM公司設計的針對POWER處理器的Genesys-Pro隨機指令生成器[10]將測試指令序列生成問題映射為約束滿足問題(Constraint Satisfaction Problem, CSP),然后根據(jù)指令驗證需求,通過維持弧相容(Maintaining Arc Consistency,MAC)算法進行約束求解。該方法依賴于指令驗證需求生成測試指令序列,在不了解指令驗證需求情況下,無法自動生成高覆蓋率的測試指令序列,同時也存在由于缺乏覆蓋統(tǒng)計導致收斂速度慢的問題。
基于指令格式的覆蓋率驅動隨機生成方法不需要定義功能覆蓋約束,而是隨機生成一段測試指令序列,直接送入待驗證處理器中測試執(zhí)行,再利用機器學習等技術對待驗證處理器的執(zhí)行結果進行分析學習,根據(jù)反饋得到的已覆蓋指令信息對未覆蓋到的指令驗證需求進行檢測,以指導后續(xù)指令生成。Braun等人[11]采用貝葉斯網絡、Pfeifer等人[12]采用強化學習以及Herdt等人[13]采用模糊測試,實現(xiàn)了測試指令序列的在線生成。這類方法可以針對性地提高某一款具體處理器的指令覆蓋率,但是無法保證對指令驗證需求的全覆蓋,同時由于需要依賴待驗證處理器的執(zhí)行結果,無法獨立使用。
針對上述方法的不足,本文以RISC-V指令集架構為研究對象,提出了基于指令生成約束的RISC-V測試序列生成方法,并構建了測試指令序列生成框架,能夠自動生成高覆蓋率的測試指令序列,用于RISC-V處理器的指令缺陷檢測。本文主要貢獻如下:
(1)定義了指令生成約束,通過對指令集架構規(guī)范和指令驗證需求進行歸納定義指令生成約束,具體包括指令格式約束和功能覆蓋約束。其中功能覆蓋約束又分為通用覆蓋約束和特殊覆蓋約束。通用和特殊覆蓋約束的組合不僅克服了隨著指令增多預定義指令約束的困難,避免了約束遺漏,還增強了約束的可復用性。
(2)提出了基于指令生成約束的求解算法,實現(xiàn)測試指令序列的高效生成。該算法的核心是啟發(fā)式搜索策略,利用集成的指令集模擬器收集已覆蓋的指令生成約束的信息,反饋引導后續(xù)指令生成,以實現(xiàn)對指令生成約束進行全覆蓋,同時加快覆蓋率的收斂速度,提升測試指令序列生成的效率。
(3)構建了測試指令序列生成框架,實現(xiàn)測試指令序列自動生成到處理器指令缺陷檢測的完整過程,從而實現(xiàn)對處理器中可能存在的指令缺陷進行高效準確定位。
加州大學伯克利分校推出的第五代開源指令集架構RISC-V的核心是RV32I基礎指令集[14],其余功能可以通過模塊化的標準擴展或自定義擴展實現(xiàn)。RISC-V指令集架構定義的模塊化擴展指令集包括M(整數(shù)乘/除法指令),A(內存原子操作與加載保留/條件存儲指令),F(xiàn)(單精度浮點指令),D(雙精度浮點指令),C(壓縮指令)等。RV32I是固定不變的,處理器設計者可以自由選擇硬件設計包含的模塊化擴展指令集。RV32I支持32位地址空間,包括6種(R, I, S, B, U, J)指令格式,具有32個通用整數(shù)寄存器(X0~X31),其中X0為硬連線零[14]。RV32I中的指令分為運算指令、訪存指令、分支指令以及系統(tǒng)指令。前面3種指令通過訪問寄存器和立即數(shù)實現(xiàn)指令功能,系統(tǒng)指令用于獲取處理器當前的系統(tǒng)狀態(tài)并對系統(tǒng)狀態(tài)進行控制(包括中斷、異常處理等)。
CSP模型,即約束滿足問題模型,用3元組(V ,D , C)進行表示[15],V={v1,v2,...,vn}表示變量的集合,D={d1,d2,...,dn}表示每個變量對應的值域,C={c1,c2,...,cm}表示變量之間的約束集合,作用于變量從而限制變量的取值。例如v1變量對應值域d1,c1可 以表示為限制v1取值為零的取值約束。利用CSP模型可以將測試指令序列生成問題用一個標準的數(shù)學模型進行表示,便于指令生成。
基于CSP模型定義,將其與測試指令序列生成問題進行結合,定義指令CSP模型。
定義1:單條指令CSP模型。每條指令構造一個CSP模型,V表示單條指令下寄存器變量和立即數(shù)變量的集合;D表示寄存器變量和立即數(shù)變量的值域;C表示寄存器變量和立即數(shù)變量的取值約束。例如:生成一條add加法指令需要完成兩個加數(shù)相加,并保存加法結果。構造的加法指令CSP模型(V, D, C)中V={rs1,rs2,rd},寄存器變量r s1,rs2分 別表示源操作數(shù)1和2, rd表示目的寄存器用于保存加法結果。D={d1,d2,d3}(d1=d2=d3∈{0,31})表示3個寄存器變量對應的值域,在32個整數(shù)寄存器中進行選擇。C={?}表示該加法指令沒有約束限制,設計者亦可增加取值約束,生成所需的加法指令,例如限制 rd的取值不為零。
定義2:指令序列CSP模型。生成多條指令的CSP模型,V包括各指令操作碼變量、寄存器變量和立即數(shù)變量;D表示上述3個變量的值域;C表示3個變量的取值約束。
為了檢測處理器硬件實現(xiàn)中的指令缺陷,解決測試指令序列自動生成的問題,本文提出了測試指令序列生成通用框架。如圖1所示,一個完整的測試指令序列生成周期分為輸入、生成、輸出和檢測4個階段。
圖1 測試指令序列生成通用框架
輸入階段,驗證人員自定義測試模板,初始化寄存器值,指定生成的指令及數(shù)量,同時可以修改配置文件和指令宏文件。其中配置文件定義存儲空間和指令地址空間范圍,指令宏文件定義一系列指令操作碼組合。在生成階段,解析測試模板及相應文件,調用基于指令生成約束的求解算法,保證生成符合指令集架構規(guī)范和指令驗證需求的測試指令序列。在生成過程中,集成指令集模擬器對生成的指令進行實時模擬,記錄指令模擬的結果,反饋給求解算法引導后續(xù)指令生成。最后,在輸出和檢測階段,將生成的測試指令序列送入待驗證處理器中測試執(zhí)行,獲取執(zhí)行結果,并和指令集模擬器的模擬結果進行對比,通過確定缺陷范圍,定位缺陷指令,確定設計缺陷3個步驟,逐步縮小范圍直到定位到處理器中的指令缺陷。
為了高效生成高覆蓋率的測試指令序列,本文提出基于指令生成約束的求解算法,實現(xiàn)測試指令序列自動生成。指令生成約束包括指令格式約束和功能覆蓋約束,用于構造CSP模型的變量集合V 、值域D和約束集合C。通過對指令驗證需求進行分析,將功能覆蓋約束分為通用覆蓋約束和特殊覆蓋約束,以增強指令生成約束的可復用性。通用覆蓋約束是所有指令生成時的共性約束,特殊覆蓋約束是對個別指令(如訪存、分支指令等)生成時在遵守通用覆蓋約束基礎上,還需額外遵守的特殊約束。在提出的啟發(fā)式搜索策略基礎上進行指令約束求解,利用集成的指令集模擬器收集已覆蓋指令生成約束的信息,反饋引導后續(xù)指令生成,實現(xiàn)測試指令序列的自動生成。所提出求解算法具有以下優(yōu)勢:第一,明確需要覆蓋的指令生成約束,避免遺漏,實現(xiàn)全覆蓋;第二,根據(jù)覆蓋率信息反饋引導生成未覆蓋指令,加快收斂速度;第三,定義通用和特殊功能覆蓋約束可以復用到其余擴展指令約束定義中。
指令格式約束用于保證對CSP模型求解生成的指令符合指令集架構規(guī)范,表1列出了RV32I的指令格式約束內容,用于構造單條指令或指令序列CSP模型。表1中的指令操作碼、寄存器及立即數(shù)變量的數(shù)值約束用于構造變量集合V和值域D,不同訪存粒度的約束用于構造寄存器變量和立即數(shù)變量之間的約束集合C。其中指令操作碼值域僅考慮用戶級指令,由于系統(tǒng)指令隨機生成時會影響處理器正常狀態(tài),所以本文暫時不考慮RV32I中的系統(tǒng)指令。
表1 RV32I指令格式約束
以RISC-V為例,功能覆蓋約束用于構造CSP模型的約束集合C,定義如下:
(1)通用覆蓋約束
(a)指令操作碼覆蓋約束,覆蓋所有指令操作碼以及指令操作碼的依賴情況。約束表達式如式(1)所示:
其中, I nstri是 指令序列中任意一條指令。min(cnt(opi))用于統(tǒng)計指令操作碼數(shù)量,下標Q是指令操作碼總數(shù),通過統(tǒng)計最小值大于等于1表明是否覆蓋所有指令操作碼; I nstri和 I nstri+1是相鄰的指令,通過選擇相鄰指令操作碼相同或相異,覆蓋指令操作碼的依賴結構。
(b)寄存器變量覆蓋約束。約束表達式如式(2)所示,其中 r eg 表示寄存器,下標M是數(shù)量,Read和W rite表示寄存器讀和寫數(shù)量,下標N是指令數(shù)量,約束讀寫的最小值表明覆蓋所有寄存器的讀寫。rd是目的寄存器, rs1 , r s2分別是源寄存器1和2,I1.r1sign I2.r2用于約束指令序列間寄存器的依賴結構,通過選擇不同的I1, I2, r1, r2覆蓋單條指令內源寄存器和目的寄存器相同或相異,相鄰指令或指令序列之間寄存器寫后寫、寫后讀、讀后寫、讀后讀4種寄存器依賴結構。
(c)立即數(shù)變量覆蓋約束。立即數(shù)變量需要覆蓋特殊數(shù)值,即最大值,最小值,–1, 0, 1,同時需要均勻覆蓋取值空間。約束表達式如式(3)所示,其中, Imm.min 和 I mm.max分別是立即數(shù)變量的最小值和最大值, U(Imm.min,Imm.max)表明立即數(shù)在最小值和最大值之間服從均勻分布。
(2)特殊覆蓋約束
(a)訪存指令覆蓋約束。訪存指令不僅需要遵守通用覆蓋約束,還需要覆蓋對同一地址連續(xù)訪存、連續(xù)地址進行訪存、均勻訪存存儲空間的特殊約束。約束表達式如式(4)所示,其中,memAccess.addr是訪存地址,下標i和i+1是當前訪存指令及下一條訪存指令的訪存地址,min和max分別表示訪存空間范圍的最小值和最大值,與實際處理器設計相關,根據(jù)實際處理器的設計進行修改。S表示訪存粒度,選擇不同的S覆蓋連續(xù)地址的訪存。
(b)分支指令覆蓋約束。分支指令需要覆蓋分支跳轉的各種情況,同時應避免在指令序列中出現(xiàn)死循環(huán)的分支跳轉。其約束表達式如式(5)所示,其中, Instri.pc表示當前指令的程序計數(shù)器(Program Counter, PC)地址。通過控制下一條指令的PC地址范圍可以覆蓋跳轉的各種情況,同時保證下一條指令的PC地址與已生成指令的PC地址不同,以避免出現(xiàn)死循環(huán)。
(c)擴展指令或自定義指令。驗證人員可以基于上述約束定義對擴展指令或自定義指令定義特殊覆蓋約束。
為了實現(xiàn)對上述約束進行全覆蓋并加快收斂速度,本文提出啟發(fā)式搜索策略,通過統(tǒng)計已生成指令的覆蓋信息,引導后續(xù)指令生成,具體包括指令操作碼搜索策略、寄存器搜索策略和立即數(shù)搜索策略。
根據(jù)式(6)定義的指令操作碼搜索策略生成滿足指令操作碼覆蓋約束定義的指令操作碼。
指令操作碼搜索策略包括3種搜索路徑。其中,RAND(UInstr)表示在未覆蓋到的指令操作碼集合UInstr中 利用R AND隨機函數(shù)隨機生成指令操作碼;opi和o pi-1分別表示當前指令操作碼和上一條指令操作碼; WInstr 表示所有指令操作碼集合,WInstr-opi-1表示與上一條指令操作碼相異的集合。P1,P2及P3表示3種搜索路徑的概率,滿足概率之和等于1。生成第1條指令時,P2及P3的取值為零,僅P1為 1;生成第1條指令后且U Instr值域不為空時,P1,P2及P3的取值相同,因為3種情況均需要被覆蓋到,也可以根據(jù)具體驗證需求調整概率取值;當 U Instr為 空時,P1的 取值為零,P2及P3的取值各為0.5。寄存器搜索策略和立即數(shù)搜索策略中的搜索路徑概率的選擇類似,可根據(jù)實際需求進行調整。
式(7)為滿足寄存器變量覆蓋約束定義下的寄存器搜索策略,包括4種搜索路徑。其中, U reg是未覆蓋到的寄存器集合; o pi.reg是當前指令已覆蓋寄存器集合;o pi-1.reg是上一條指令覆蓋的寄存器集合;H reg 是生成多條指令后已覆蓋寄存器集合。與指令操作碼搜索類似,在生成第1條指令的第1個寄存器變量時,只在 U reg 搜索,即P1為1;在生成第1 條指令的第1 個寄存器變量后,在 Ureg和opi.reg 中進行搜索,即P1及P2各為0.5;在生成第1條指令后,在U reg , o pi.reg 和o pi-1.reg搜 索,即P1,P2及P3的 取值相同;在生成多條指令后,P1,P2,P3及P4的取值為0.25。當任一集合為空時,相應搜索路徑概率為零。
根據(jù)立即數(shù)變量覆蓋約束和特殊覆蓋約束定義立即數(shù)搜索策略,包括運算指令立即數(shù)、訪存指令立即數(shù)和分支指令立即數(shù)搜索策略。根據(jù)3種不同指令類型的立即數(shù)驗證要求,可以進一步定義搜索策略,即運算指令立即數(shù)搜索策略如式(8)所示,包括2種搜索策略,其中U niform是均勻分布函數(shù),Special為特殊數(shù)值集合,包括最大值,最小值,–1, 0, 1,也可根據(jù)驗證需求添加其他數(shù)值。
訪存指令和分支指令的立即數(shù)搜索策略與式(8)類似,其余擴展指令或自定義指令的立即數(shù)搜索策略也可在式(8)的基礎上進行擴展。
為了能夠自動生成滿足驗證需求的測試指令序列,提出了基于指令生成約束的求解算法,執(zhí)行流程如圖2所示。首先,根據(jù)指令生成需求構建指令序列CSP模型;然后,調用指令操作碼搜索策略構建單條指令CSP模型,再調用寄存器和立即數(shù)搜索策略,完成單條指令的生成;之后,對生成的指令進行格式約束檢查,若不符合則丟棄,若符合則送入指令集模擬器進行模擬,記錄覆蓋信息和模擬結果,用于引導后續(xù)指令生成;最后,根據(jù)指令生成數(shù)量判斷是否終止算法,輸出測試指令序列及模擬結果。算法偽代碼如圖3所示。
圖2 指令約束求解流程
圖3 指令約束求解算法偽代碼
圖4(a)為測試模板中自定義指令生成需求及數(shù)量的示例,Macro為指令宏標志,RV32I_Alu表示RV32I指令集中屬于運算類型的一系列指令,Num表示需要生成的指令數(shù)量,圖4(b)是利用本文所提出的求解算法按照測試模板要求生成的測試指令序列。
圖4 測試模板及生成的測試指令序列示例
以RV32I為目標指令集,官方的RISC-V Tests[16]測試集作為基準,選擇維持弧相容算法[17]、Herdt等人[7]提出的基于約束規(guī)范隨機生成方式與本文提出的基于指令生成約束的求解算法進行測試指令序列生成的比較。采用Herdt等人提出的結構覆蓋率和數(shù)值覆蓋率進行評估[18],結構覆蓋率是指令操作碼和寄存器變量的依賴結構,此外還需要增加目的寄存器等于和不等于X0寄存器的兩種情況,對RV32I而言共174種情況。數(shù)值覆蓋率是指指令操作碼、寄存器變量和立即數(shù)變量的覆蓋情況,立即數(shù)僅覆蓋最大值,最小值,1, 0, –1,對RV32I而言共2 684種情況。用已覆蓋情況與所有覆蓋情況之比評估生成的測試指令序列質量。
5.2.1 指令覆蓋率數(shù)量統(tǒng)計
圖5給出了RISC-V Tests官方測試集、維持弧相容算法、基于約束規(guī)范隨機生成方式和基于指令生成約束的求解算法在生成相同數(shù)量的測試指令序列下,結構覆蓋率(a)和數(shù)值覆蓋率(b)的比較。官方測試集由加州伯克利定向編寫,指令內容固定,所以結構和數(shù)值覆蓋率不隨數(shù)量的增加而增大。維持弧相容算法對變量隨機賦值缺乏相應的約束條件,雖然可以獲得較高的覆蓋率,但是無法保證對所有情況進行覆蓋?;诩s束規(guī)范隨機生成方式,預定義各種約束情況進行遍歷求解,覆蓋率隨數(shù)量的增加而增大,可以實現(xiàn)對所有情況的覆蓋,但是該方法由于在對每種情況求解中會得到所有滿足約束的指令,即某些覆蓋點存在冗余生成指令。實驗結果表明,基于指令生成約束的求解算法相較于其他生成方法,在生成相同指令數(shù)量下可以得到更高的覆蓋率。在生成30 000條指令時,基于指令生成約束的求解算法相較于官方測試集結構覆蓋率提升了13.64%,數(shù)值覆蓋率提升了85.06%;相較于維持弧相容算法結構覆蓋率提升了8.45%,數(shù)值覆蓋率提升了6.90%;相較于約束規(guī)范隨機生成方式結構覆蓋率一致,數(shù)值覆蓋率多覆蓋到了JALR指令中RS1=X0的情況,這是因為指令約束求解算法對生成指令實時模擬,可以實時獲取PC地址,通過反饋控制PC地址可以覆蓋JALR指令中RS1=X0的情況。此外,基于約束規(guī)范隨機生成和基于指令生成約束的求解算法在數(shù)值覆蓋率統(tǒng)計時,未覆蓋到的情況是訪存指令LW, LH, LB, LBU, LHU, SB,SH, SW的基址寄存器等于X0的情況,這是因為X0寄存器恒為零值。
圖5 相同數(shù)量下結構和數(shù)值覆蓋率比較
5.2.2 指令覆蓋率收斂時間
圖6給出了維持弧相容算法、基于約束規(guī)范隨機生成方式以及基于指令生成約束的求解算法在固定時間內的結構覆蓋率(a)和數(shù)值覆蓋率(b)的收斂時間統(tǒng)計。
圖6 結構和數(shù)值覆蓋率收斂時間比較
維持弧相容算法缺乏相應約束無法保證在有限時間內對所有情況進行覆蓋?;诩s束規(guī)范隨機生成方式必須對預定義的約束情況進行遍歷求解,缺少覆蓋率統(tǒng)計所以無法快速收斂。實驗結果表明,基于指令生成約束的求解算法的收斂時間明顯優(yōu)于其他兩種算法,相較于基于約束規(guī)范隨機生成方式結構覆蓋率收斂時間減少85.62%,數(shù)值覆蓋率收斂時間減少57.64%,加快收斂速度,提高測試指令序列生成的效率。
5.2.3 指令類型和寄存器數(shù)量分布
圖7進一步給出了基于指令生成約束的求解算法生成30 000條指令時指令類型數(shù)量分布(a)和寄存器數(shù)量分布(b)。實驗結果表明,利用該算法可以均勻覆蓋RV32I中所有的37條指令類型(圖7(a)中橫坐標僅列部分類型名稱),并可以均勻訪問X0~X31所有寄存器。
圖7 指令類型和寄存器生成分布
為了避免處理器受到指令缺陷的威脅,本文以RISC-V指令為例,提出基于指令生成約束的測試序列生成方法,構建測試指令序列生成框架,實現(xiàn)對RISC-V處理器的指令缺陷檢測,本文方法也適用于其他指令集架構的處理器。首先,結合所需的指令集架構,定義指令生成約束,區(qū)分通用和特殊功能覆蓋約束,可以增強約束定義的可復用性;然后,構造啟發(fā)式搜索策略,完成對指令生成約束的求解,以實現(xiàn)測試指令序列的自動生成。實驗結果表明,該方法在滿足所有覆蓋要求的前提下,可以降低覆蓋率的收斂速度,實現(xiàn)RISC-V測試指令序列的高效生成。
基于所提出的測試指令序列生成框架,在Linux環(huán)境下開發(fā)了一款指令生成工具GTIR(Generate Test Instructions for RISC-V),利用開發(fā)的GTIR工具對第三方引入指令缺陷后的開源RISCV處理器SweRV-EH2[19]進行檢測。實驗表明,該工具可以定位到7條指令(SLT, XORI, LW, SW,BGE, AUIPC, JAL)在譯碼、執(zhí)行階段由第三方引入的指令缺陷,可以幫助設計人員對處理器硬件設計缺陷進行檢測。后續(xù)研究結合處理器微結構信息構造指令生成約束,考慮對處理器微結構進行缺陷檢測。