CRCLA編譯前端中代碼檢測(cè)與DFG生成技術(shù)研究

楊晨光，李 偉，杜怡然

戰(zhàn)略支援部隊(duì)信息工程大學(xué) 密碼工程學(xué)院，鄭州 450001

粗粒度可重構(gòu)處理器具有豐富的計(jì)算資源和互連資源，能夠適用于密集型計(jì)算，同時(shí)兼具高能效與靈活性的特點(diǎn)使其受到了學(xué)者的廣泛關(guān)注。粗粒度可重構(gòu)密碼邏輯陣列（coarse-grained reconfigurable cipher logical array，CRCLA）作為一種面向密碼算法的專用可重構(gòu)處理器，在運(yùn)算單元中添加了適用于密碼運(yùn)算的模塊，并在互連以及控制方面做了針對(duì)性設(shè)計(jì)，但這也導(dǎo)致傳統(tǒng)的通用可重構(gòu)陣列編譯架構(gòu)已不解決的問題。

對(duì)于面向CRCLA 的編譯技術(shù)來說，其可分為前端設(shè)計(jì)與后端劃分、映射。首先不同的編譯前端因優(yōu)化方式的不同將生成不同的數(shù)據(jù)流圖，從而造成編譯后端映射性能的差異。那么為充分發(fā)揮本文CRCLA的執(zhí)行效率，需結(jié)合CRCLA 結(jié)構(gòu)與密碼算法運(yùn)算特征對(duì)前端的編譯框架、編譯技術(shù)進(jìn)行研究，構(gòu)建面向CRCLA的前端分析。同時(shí)為了擴(kuò)展CRCLA 的可用性，本文采用高級(jí)語言C++來編寫密碼算法代碼，雖然開發(fā)人員無需理解硬件實(shí)際結(jié)構(gòu)，但也增加了前端生成中間格式的難度。

可重構(gòu)陣列編譯器的支持，不僅能最大程度發(fā)揮出陣列的性能還可以降低開發(fā)難度。REmus II可重構(gòu)處理器編譯器[1]，以帶有標(biāo)注信息的代碼作為輸入，通過預(yù)處理與模板調(diào)用模塊進(jìn)行識(shí)別，并對(duì)識(shí)別成功的模塊調(diào)用模板進(jìn)行代碼宏替換，最終進(jìn)行配置信息的生成，但該編譯器對(duì)輸入代碼的語法具有極大的限制，且不支持跨循環(huán)的輸入輸出依賴。Spatial[2]編譯器支持在可重構(gòu)架構(gòu)上實(shí)現(xiàn)的加速器，使用專門的領(lǐng)域特定語言Spatial允許領(lǐng)域?qū)＜铱焖匍_發(fā)、優(yōu)化硬件加速器，但Spatial 語言只支持加速器，無法適應(yīng)粗粒度可重構(gòu)陣列的開發(fā)。TIRAMISU[3]是一個(gè)多面體編譯器框架，引入了一種命令式的調(diào)度語言，允許進(jìn)行細(xì)粒度的優(yōu)化，從而生成高性能的代碼，但命令式調(diào)度語言的編寫需熟悉具體的硬件結(jié)構(gòu)。TPA-S[4]編譯器基于眾核處理器結(jié)構(gòu)，以CUDA 編程語言為輸入，主要專注于控制流程序，但在面對(duì)密碼算法這種計(jì)算復(fù)雜的程序時(shí)無法發(fā)揮較好的性能。

上述編譯器基本采用專門的領(lǐng)域?qū)Ｓ谜Z言進(jìn)行開發(fā)，同時(shí)針對(duì)硬件結(jié)構(gòu)進(jìn)行了優(yōu)化，沒有統(tǒng)一的編譯框架與結(jié)構(gòu)模型，因此在面對(duì)其他可重構(gòu)結(jié)構(gòu)時(shí)具有不確定性。由于本文的可重構(gòu)密碼邏輯陣列針對(duì)密碼算法的實(shí)現(xiàn)進(jìn)行了特殊設(shè)計(jì)，上述編譯器在實(shí)現(xiàn)密碼算法代碼映射時(shí)不能達(dá)到較好的性能。因此，為發(fā)揮本文可重構(gòu)密碼邏輯陣列的高性能與靈活性的特點(diǎn)，本文設(shè)計(jì)以C++編寫的代碼作為輸入，以FLEX、BISON編譯框架進(jìn)行自動(dòng)化識(shí)別的前端。

設(shè)計(jì)過程中，由于密碼算法眾的特殊運(yùn)算如S盒等可用C++代碼以不同的方式實(shí)現(xiàn)，但在可重構(gòu)密碼邏輯陣列中可用單個(gè)算子運(yùn)行，因此本文以基于注意力機(jī)制的圖嵌入模型進(jìn)行檢測(cè)識(shí)別，以較高的分類精度精簡(jiǎn)數(shù)據(jù)流圖。同時(shí)，基于可重構(gòu)密碼邏輯陣列結(jié)構(gòu)特點(diǎn)對(duì)數(shù)據(jù)流圖進(jìn)行優(yōu)化，提高了映射性能。

1 基于C++的密碼算法代碼識(shí)別與分析

本文采用FLEX、BISON 編譯框架來設(shè)計(jì)編譯器，以高級(jí)語言C++編寫的代碼作為輸入，該語言能夠忽略底層結(jié)構(gòu)，從而方便非專業(yè)人員無障礙使用可編程密碼邏輯陣列[5-6]。FLEX、BISON編譯框架源代碼公開，且免費(fèi)使用，同時(shí)默認(rèn)生成C 語言程序，相對(duì)其他框架在面對(duì)C++工程項(xiàng)目時(shí)更易維護(hù)。

編譯前端的分析器設(shè)計(jì)中，F(xiàn)LEX 將具有輸入的程序分割成有意義的單元，這些單元可以是變量名、操作名、字符串等，F(xiàn)LEX使用一系列的標(biāo)記描述產(chǎn)生一個(gè)能識(shí)別程序的詞法分析器。定義一系列能夠理解的規(guī)則列表，將這些標(biāo)記進(jìn)行連接，即為語法分析器。提取出語法樹中的關(guān)鍵信息，即為語義分析器。

1.1 基于FLEX、BISON編譯框架的詞法、語法分析

詞法分析將順序地讀入輸入源程序的有限字符序列，根據(jù)分析器中的詞法規(guī)則進(jìn)行匹配[7]，匹配采用的方法為正則表達(dá)式法。通過詞法規(guī)則可以識(shí)別簡(jiǎn)單的字符、運(yùn)算符號(hào)、變量名、變量類型的匹配，還可識(shí)別自定義的函數(shù)名。同時(shí)采取匹配優(yōu)先級(jí)的方法來解決規(guī)則沖突，具體指的是在前面的優(yōu)先級(jí)較高，如匹配函數(shù)名“matrix”，只需將函數(shù)名的定義放在變量名的定義之前即可。

詞法分析器將輸入的字符流識(shí)別為有意義的單詞符號(hào)，語法分析程序根據(jù)語法規(guī)則，采用遞歸下降、移進(jìn)規(guī)約的思想識(shí)別單詞符號(hào)構(gòu)建語法樹[8-9]。自葉子節(jié)點(diǎn)進(jìn)行語法匹配并逐步規(guī)約到根節(jié)點(diǎn)，其中語法規(guī)則的設(shè)置需要依據(jù)編程語言的文法而確定的。

以常規(guī)運(yùn)算“Value=Msg^Key”作為推導(dǎo)示例，從語法規(guī)則逐步遞進(jìn)進(jìn)行語法匹配，每個(gè)詞素都將被識(shí)別到對(duì)應(yīng)的標(biāo)識(shí)符，最后逐步歸約，并將每一步歸約的節(jié)點(diǎn)信息存入節(jié)點(diǎn)鏈表中。其中目的操作數(shù)“Value”經(jīng)“Exp-＞VAR-＞Value”匹配規(guī)則可遞歸到“Exp”，并經(jīng)由“Exp ASSIGN EXP -＞DefList”將整條語句規(guī)約到根節(jié)點(diǎn)“DefList”，那么將每次遞歸到的節(jié)點(diǎn)存入鏈表中，就會(huì)得到完整的語法樹鏈表。

1.2 語義分析

語義分析主要是對(duì)構(gòu)建的語法樹進(jìn)行分析，通過相應(yīng)的子程序進(jìn)行語義檢查提取出關(guān)鍵信息[10-12]。本文以生成數(shù)據(jù)流圖為目標(biāo)，因此需提取有關(guān)運(yùn)算語句間數(shù)據(jù)傳遞的關(guān)鍵信息，將其以相應(yīng)的數(shù)據(jù)格式保存起來，并最終生成運(yùn)算操作表。操作表中的運(yùn)算操作需按順序存放，以指示密碼算法代碼中運(yùn)算的執(zhí)行順序。同時(shí)為存儲(chǔ)密碼算法中的輸入數(shù)據(jù)供可重構(gòu)密碼邏輯陣列的使用，將定義的變量名存入變量表中。

本文針對(duì)數(shù)據(jù)流圖生成的需求，設(shè)計(jì)了語義分析程序。該程序根據(jù)語法樹的格式編寫代碼，從語法樹根節(jié)點(diǎn)出發(fā)，逐條語句進(jìn)行分析，識(shí)別密碼算法中的運(yùn)算語句的關(guān)鍵信息，具體語義分析流程圖如圖1所示。

圖1 語義分析流程圖Fig.1 Semantic analysis flow chart

圖1中語義分析流程從語句鏈表開始，將循環(huán)結(jié)構(gòu)展開。然后依據(jù)等號(hào)標(biāo)志ASSIGN、操作符與函數(shù)名取出定義語句、運(yùn)算語句、賦值語句的關(guān)鍵信息，并將操作對(duì)應(yīng)的源操作數(shù)、目的操作數(shù)與運(yùn)算符存入操作表oper中，將變量名與值存入變量表vartable中，逐條語句進(jìn)行分析直到語句鏈表為空。

2 數(shù)據(jù)流圖自動(dòng)化生成

編譯前端需要將密碼算法代碼生成可被后端使用的中間形式，而可重構(gòu)密碼邏輯陣列運(yùn)行密碼算法，是通過分析算法中的運(yùn)算及數(shù)據(jù)依賴生成配置數(shù)據(jù)，數(shù)據(jù)流圖形式符合編譯后端需求，因此采用數(shù)據(jù)流圖作為中間代碼格式。針對(duì)數(shù)據(jù)流圖的生成，本文對(duì)1.2 節(jié)經(jīng)語義分析后得到的操作表oper 和變量表vartable 進(jìn)行分析，oper 中順序存放著密碼算法運(yùn)算操作，單條運(yùn)算包含源操作數(shù)、目的操作數(shù)、操作符，vartable 中存儲(chǔ)著密碼算法代碼中所有的變量名，通過分析可得運(yùn)算節(jié)點(diǎn)間的依賴關(guān)系。

2.1 數(shù)據(jù)流圖生成

本文針對(duì)數(shù)據(jù)流圖的生成設(shè)計(jì)了算法，如下所示為數(shù)據(jù)流圖生成算法的偽代碼，算法輸入為1.2 節(jié)得到的運(yùn)算操作表Operate，輸出為數(shù)據(jù)流圖Graph，整體過程為構(gòu)建操作表中各操作的父子節(jié)點(diǎn)關(guān)系，具體生成過程如下。

2.2 基于注意力與圖嵌入的代碼檢測(cè)

本文采用高級(jí)語言C++，屏蔽掉了可重構(gòu)密碼邏輯陣列的內(nèi)部結(jié)構(gòu)，便于非專業(yè)人員使用以編寫代碼，但為了使得代碼更好地在可重構(gòu)密碼陣列上運(yùn)行，在編譯前端時(shí)還需進(jìn)行具體的分析和優(yōu)化。從密碼算法特征和陣列內(nèi)部結(jié)構(gòu)來看，密碼算法中某些特殊運(yùn)算如S盒替換運(yùn)算、比特置換等運(yùn)算在可重構(gòu)密碼陣列中可當(dāng)作單步算子進(jìn)行計(jì)算，而在C++編寫的代碼中，因編寫人員的不同，可能會(huì)有多種方式編寫代碼來實(shí)現(xiàn)上述算子的功能。那么在生成中間格式時(shí)，需對(duì)上述得到的數(shù)據(jù)流圖進(jìn)行檢測(cè)，以識(shí)別相應(yīng)子圖所對(duì)應(yīng)的功能。

本文對(duì)于代碼相似性檢測(cè)問題，提出一種以圖嵌入與注意力機(jī)制結(jié)合的方法。圖嵌入方法將代碼轉(zhuǎn)化的數(shù)據(jù)流圖轉(zhuǎn)化為低維embedding降維，并提取出特征向量[13-15]，圖注意力可對(duì)周圍鄰居節(jié)點(diǎn)的特征進(jìn)行聚合[16-18]。為提高子圖識(shí)別的準(zhǔn)確度，在圖嵌入的基礎(chǔ)上，加入圖注意力機(jī)制構(gòu)建節(jié)點(diǎn)與其鄰接節(jié)點(diǎn)的注意力系數(shù)，然后聚合鄰居節(jié)點(diǎn)的特征以優(yōu)化當(dāng)前節(jié)點(diǎn)的特征向量，最后對(duì)子圖所含節(jié)點(diǎn)的向量使用加權(quán)平均得到整張圖的向量。

2.2.1 基于注意力的圖嵌入模型

圖嵌入的目的就是將高維的圖數(shù)據(jù)轉(zhuǎn)化為低維稠密向量，并且保留原圖的結(jié)構(gòu)特征。圖嵌入預(yù)定義一個(gè)嵌入維數(shù)D（D遠(yuǎn)小于節(jié)點(diǎn)數(shù)量N），使得G轉(zhuǎn)換到D維空間[19]。在圖2 所示的基于GAT 和注意力機(jī)制的圖嵌入模型中，首先將數(shù)據(jù)流圖數(shù)輸入GAT 網(wǎng)絡(luò)中進(jìn)行運(yùn)算以獲得有依賴關(guān)系的節(jié)點(diǎn)對(duì)間注意力權(quán)重與節(jié)點(diǎn)特征向量，再根據(jù)權(quán)重采取隨機(jī)游走策略生成多個(gè)節(jié)點(diǎn)路徑，并輸入deepwalk 圖嵌入模型中生成節(jié)點(diǎn)特征向量，最后使用Attention注意力機(jī)制獲得圖嵌入向量展示。

圖2 基于注意力機(jī)制的圖嵌入模型Fig.2 Graph embedding model based on attention mechanism

在進(jìn)行運(yùn)算之前，需明確圖的輸入。給定一個(gè)圖G=(V,E)，其中V為圖中節(jié)點(diǎn)集合，E代表圖中所有邊，可以對(duì)每個(gè)節(jié)點(diǎn)采用一個(gè)D維的特征向量表示。為了使得節(jié)點(diǎn)特征參與運(yùn)算，需提取出圖中節(jié)點(diǎn)的特征表示。數(shù)據(jù)流圖中節(jié)點(diǎn)主要由AG、BP、NBF、LG、LT等不同運(yùn)算類型組成，圖3（a）中不同類型節(jié)點(diǎn)具有不同的屬性，圖3（b）則表示由不同的節(jié)點(diǎn)屬性所組成的圖，且采用one-hot編碼。

圖3 圖輸入示例Fig.3 Figure input example

2.2.2 GAT網(wǎng)絡(luò)模塊

在獲得圖的輸入形式后，就可以通過GAT 圖注意力網(wǎng)絡(luò)獲得節(jié)點(diǎn)對(duì)間的注意力權(quán)重。注意力權(quán)重需同時(shí)考慮兩個(gè)節(jié)點(diǎn)的影響，那么其表達(dá)公式如下所示：

其中，公式（1）中顯示節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i的影響，hi和hj分別代表節(jié)點(diǎn)i和j的特征表示，W為投影矩陣，用于對(duì)節(jié)點(diǎn)進(jìn)行特征維度的變換，||表示向量拼接操作，在這個(gè)過程中特征向量進(jìn)行了可學(xué)習(xí)的線性映射。

公式（2）中LeakyReLU為激活函數(shù)，使公式（1）中得到的向量映射為一個(gè)標(biāo)量，最后使用公式（3）中的softmax進(jìn)行歸一化操作，其中Ni為節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)。公式（4）利用歸一化后的注意力權(quán)重，計(jì)算與鄰居節(jié)點(diǎn)特征的加權(quán)平均，從而優(yōu)化當(dāng)前節(jié)點(diǎn)的特征向量。后續(xù)GAT中將以公式（3）和公式（4）不斷優(yōu)化注意力權(quán)重系數(shù)與特征向量。

2.2.3 圖嵌入網(wǎng)絡(luò)模塊

獲得權(quán)重系數(shù)后，本文采用基于隨機(jī)游走的deepwalk 進(jìn)行圖嵌入，在進(jìn)行隨機(jī)游走時(shí)采用AliasTable 方法。本文的數(shù)據(jù)流圖為有向數(shù)據(jù)流圖，采用C_Table 列表存儲(chǔ)每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)，那么游走的節(jié)點(diǎn)就從子節(jié)點(diǎn)中進(jìn)行隨機(jī)選取，最終組成多條路徑，并生成節(jié)點(diǎn)的嵌入向量。

如圖4中所示，為AliasTable轉(zhuǎn)移策略。假設(shè)有A、B、C、D四個(gè)轉(zhuǎn)移節(jié)點(diǎn)，把轉(zhuǎn)移概率想象成等長(zhǎng)度的線段，并且根據(jù)可轉(zhuǎn)移節(jié)點(diǎn)想象成N份，那么優(yōu)化時(shí)采取多缺少補(bǔ)的策略逐步轉(zhuǎn)化為圖4（b）所示的等長(zhǎng)度轉(zhuǎn)移表。為使得選取過程更快，AliasTable 方法用1 表示轉(zhuǎn)移表的長(zhǎng)度，隨機(jī)選擇一個(gè)[0，1]的隨機(jī)數(shù)random，以圖4（b）為例，若0＜random＜1/6就選擇節(jié)點(diǎn)A轉(zhuǎn)移，1/6＜random＜1/4就選擇節(jié)點(diǎn)B轉(zhuǎn)移。經(jīng)過隨機(jī)游走后將產(chǎn)生的多條路徑輸入到deepwalk 圖嵌入網(wǎng)絡(luò)中將生成K條特征向量。

圖4 AliasTable轉(zhuǎn)移策略Fig.4 AliasTable migration policy

2.2.4 注意力機(jī)制模塊

由上述GAT網(wǎng)絡(luò)模塊與圖嵌入模塊分別得到節(jié)點(diǎn)特征向量Gi、Di，為充分利用從不同方面得到的向量，則利用公式（5）進(jìn)行相加得到最終向量xi，但由于不同的向量對(duì)整張圖的影響是不同的，因此需求得向量xi對(duì)應(yīng)的權(quán)重，則這K向量的權(quán)重可由下式得到：

公式（6）中b為偏置向量，W為權(quán)重矩陣，為注意力向量，計(jì)算過后將得到該向量的注意力分?jǐn)?shù)。那么為與其他進(jìn)行比較，公式（7）用softmax進(jìn)行歸一化的操作，顯然當(dāng)計(jì)算出的αi越大時(shí)，該向量對(duì)整張圖的影響越大，最后如公式（8）利用αi計(jì)算出圖特征向量Z。最后采用余弦相似度度量代碼片段之間的相似值[20-22]，并進(jìn)行分類。

2.3 數(shù)據(jù)流圖優(yōu)化

在代碼識(shí)別并替代后得到的數(shù)據(jù)流圖，還存在著冗余節(jié)點(diǎn)及節(jié)點(diǎn)并行度不足的缺點(diǎn)[23]，其中冗余節(jié)點(diǎn)增加了數(shù)據(jù)流圖的長(zhǎng)度，節(jié)點(diǎn)并行度決定著運(yùn)算的性能。密碼算法代碼中可能存在函數(shù)，在進(jìn)行語義分析時(shí)函數(shù)體與主代碼是分別進(jìn)行分析的，因此為保證密碼算法數(shù)據(jù)流圖的完整，需用函數(shù)數(shù)據(jù)流圖替換對(duì)應(yīng)的函數(shù)節(jié)點(diǎn)，獲得完整數(shù)據(jù)流圖后。本節(jié)采用函數(shù)展開、冗余節(jié)點(diǎn)消除與數(shù)據(jù)流圖分層的順序?qū)?shù)據(jù)流圖進(jìn)行優(yōu)化。

2.3.1 函數(shù)展開

對(duì)密碼算法代碼進(jìn)行分析可能會(huì)得到多個(gè)數(shù)據(jù)流圖，分別為主代碼和函數(shù)體生成，而函數(shù)在主代碼數(shù)據(jù)流圖Graph中為一個(gè)運(yùn)算節(jié)點(diǎn)，因此為得到完整的數(shù)據(jù)流圖，需將函數(shù)代表的運(yùn)算填補(bǔ)到該函數(shù)節(jié)點(diǎn)，即函數(shù)展開方式。函數(shù)展開是用相應(yīng)的數(shù)據(jù)流圖替代函數(shù)節(jié)點(diǎn)，并不會(huì)影響函數(shù)體數(shù)據(jù)流圖內(nèi)的連接關(guān)系，關(guān)鍵是主代碼中函數(shù)節(jié)點(diǎn)的源操作數(shù)、目的操作數(shù)如何替代函數(shù)體的參數(shù)與返回值，并建立運(yùn)算節(jié)點(diǎn)間的連接關(guān)系。

圖5（a）展示了函數(shù)在代碼中的使用方式，即可將返回值直接賦值，也可直接參與運(yùn)算。進(jìn)行函數(shù)展開主要包括如下三個(gè)方面：

圖5 函數(shù)展開方式Fig.5 Function expansion

（1）構(gòu)造函數(shù)操作數(shù)、參數(shù)連接關(guān)系

將函數(shù)節(jié)點(diǎn)分為兩個(gè)賦值節(jié)點(diǎn)，兩節(jié)點(diǎn)間為函數(shù)體。具體過程如圖5（b）所示，將源操作數(shù)與函數(shù)體參數(shù)構(gòu)成賦值語句A1；函數(shù)節(jié)點(diǎn)為運(yùn)算節(jié)點(diǎn)，直接將返回值替代函數(shù)參與運(yùn)算，構(gòu)成語句A2。

（2）消除編號(hào)、變量名沖突

對(duì)函數(shù)體數(shù)據(jù)流圖中的節(jié)點(diǎn)標(biāo)志Tag 進(jìn)行重新編號(hào)，同時(shí)若定義的變量名存在于主代碼中需重新構(gòu)造，這是為避免編號(hào)值、變量名重復(fù)，造成數(shù)據(jù)流圖混亂。

（3）構(gòu)造A1、A2 父子節(jié)點(diǎn)

根據(jù)原函數(shù)節(jié)點(diǎn)的父子節(jié)點(diǎn)，重新構(gòu)造A1 與其父節(jié)點(diǎn)，A2 與其子節(jié)點(diǎn)的連接關(guān)系，展開后主代碼數(shù)據(jù)流圖填補(bǔ)完整。

2.3.2 冗余節(jié)點(diǎn)消除

目前數(shù)據(jù)流圖Graph 中還存在著許多不影響運(yùn)算結(jié)果的節(jié)點(diǎn)，也就是冗余節(jié)點(diǎn)。冗余節(jié)點(diǎn)主要是由賦值語句，及可計(jì)算的運(yùn)算語句構(gòu)成的。運(yùn)算語句目的操作數(shù)可經(jīng)由計(jì)算得到值，賦值語句作為中轉(zhuǎn)節(jié)點(diǎn)，連接不同運(yùn)算節(jié)點(diǎn)。冗余節(jié)點(diǎn)的兩種形式如圖6所示。

為簡(jiǎn)化數(shù)據(jù)流圖Graph，需消除冗余節(jié)點(diǎn)。對(duì)于圖6（a）運(yùn)算冗余，由于其可計(jì)算性，依據(jù)循環(huán)變量值進(jìn)行計(jì)算得到目的值，并替換此次循環(huán)內(nèi)部所有目的值，如圖6所示“keys[index-1]”，若當(dāng)前s為0可得目的值index為4，替換后可得“keys[3]”，經(jīng)由簡(jiǎn)化后不僅去除了冗余節(jié)點(diǎn)，還優(yōu)化了循環(huán)內(nèi)部運(yùn)算。

對(duì)于循環(huán)中的賦值語句冗余節(jié)點(diǎn)如圖6（b）中所示，r是由tmp2 進(jìn)行賦值的，因此r可用tmp2 代替。那么為消除循環(huán)內(nèi)的賦值語句，可構(gòu)建其父節(jié)點(diǎn)與子節(jié)點(diǎn)兩者間的連接，以簡(jiǎn)化數(shù)據(jù)流圖。

2.3.3 數(shù)據(jù)流圖分層

本文為提取數(shù)據(jù)流圖間節(jié)點(diǎn)的并行性，設(shè)計(jì)了數(shù)據(jù)流圖分層算法。如下所示為數(shù)據(jù)流圖分層的偽代碼，算法利用數(shù)據(jù)流圖Graph作為輸入，以分層后的數(shù)據(jù)流圖Graph_Level為輸出。

若節(jié)點(diǎn)中源操作數(shù)為外部輸入，數(shù)據(jù)流圖生成的Graph不考慮其連接關(guān)系。若父節(jié)點(diǎn)為空即運(yùn)算數(shù)據(jù)都為外部輸入，則為無前驅(qū)節(jié)點(diǎn)。本文算法以無前驅(qū)節(jié)點(diǎn)作為并行的依據(jù)，將無前驅(qū)的節(jié)點(diǎn)作為一層，此后刪除該層節(jié)點(diǎn)與其子節(jié)點(diǎn)的連接關(guān)系，從剩余的節(jié)點(diǎn)中選擇新的無前驅(qū)節(jié)點(diǎn)作為一層，直到數(shù)據(jù)流圖為空。

3 實(shí)驗(yàn)與分析

為驗(yàn)證可重構(gòu)密碼處理器編譯前端的有效性，將從詞法、語法、語法分析器功能測(cè)試，以及數(shù)據(jù)流圖生成與優(yōu)化兩大部分進(jìn)行測(cè)試。本文使用C++在VSCODE 平臺(tái)上編寫代碼，并基于QT 圖形用戶界面開發(fā)框架綜合所研究?jī)?nèi)容，設(shè)計(jì)一款CRCLA 前端測(cè)試平臺(tái)。本節(jié)選取典型的密碼算法在測(cè)試平臺(tái)上進(jìn)行中間格式生成實(shí)驗(yàn)，實(shí)驗(yàn)運(yùn)行環(huán)境為Intel Core i5-6300HQ@ 2.30 GHz內(nèi)存。

3.1 分析器功能測(cè)試

詞法分析器對(duì)輸入的密碼算法源代碼進(jìn)行分析，得到所有字符串對(duì)應(yīng)的標(biāo)識(shí)，語法分析器依據(jù)語法規(guī)則識(shí)別出字符串間的關(guān)系，通過語義分析提取出關(guān)鍵信息。使用測(cè)試用例在軟件平臺(tái)上進(jìn)行詞法、語法分析測(cè)試，所得結(jié)果如圖7所示。從圖中可知，分析器將輸入的詞素流，轉(zhuǎn)換成對(duì)應(yīng)的標(biāo)識(shí)，并依據(jù)語法規(guī)則生成語法樹，經(jīng)過比對(duì)語法樹與對(duì)應(yīng)的語句完全對(duì)應(yīng)。

圖7 詞法、語法分析結(jié)果Fig.7 Results of lexical and grammatical analysis

通過對(duì)測(cè)試結(jié)果的分析，可以發(fā)現(xiàn)字符流可以被正確識(shí)別，如圖中左側(cè)的for 循環(huán)，其循環(huán)變量“s”與循環(huán)值“9”在右圖中被正確識(shí)別為變量ID與整數(shù)INT。循環(huán)內(nèi)部的第一條運(yùn)算語句其目的操作數(shù)“Msg”、等號(hào)“=”被正確識(shí)別為ID、ASSIGNOP。該測(cè)試表明無論是循環(huán)、運(yùn)算語句都能識(shí)別正確。

對(duì)于語法樹結(jié)構(gòu)，可以看到按照語法規(guī)則識(shí)別從標(biāo)志Statement 開始，以SEMI 結(jié)束，中間為語句中提取出的關(guān)鍵信息，相鄰兩行不對(duì)齊表父子節(jié)點(diǎn)，對(duì)齊為兄弟節(jié)點(diǎn)。分析結(jié)果顯示提取出了用例中的所有關(guān)鍵信息，語法樹結(jié)構(gòu)正確。

將圖7中的語法樹作為識(shí)別對(duì)象，根據(jù)語法樹結(jié)構(gòu)編寫語義分析器，目的是從中提取出語句的關(guān)鍵信息，如運(yùn)算操作符、函數(shù)名，以及源操作數(shù)、目的操作數(shù)等，并組成操作表。操作表可為后面數(shù)據(jù)流圖的生成提供必要信息，語義分析后得到的操作表如圖8所示。

圖8 語義分析結(jié)果Fig.8 Semantic analysis results

圖8 中的操作表與圖7 左側(cè)的for 循環(huán)對(duì)比對(duì)可以看到循環(huán)已被展開，且圖8 中的每條操作存儲(chǔ)著操作符、變量名及數(shù)組位置。經(jīng)過比對(duì)可發(fā)現(xiàn)操作表中操作的順序及其存儲(chǔ)信息存放正確，接下來可依據(jù)該操作表進(jìn)行數(shù)據(jù)流圖的生成與優(yōu)化。

3.2 數(shù)據(jù)流圖生成與優(yōu)化測(cè)試

從操作表與測(cè)試用例對(duì)比中可以看到循環(huán)已被展開，那么以存儲(chǔ)正確的操作表為輸入，接下來可進(jìn)行數(shù)據(jù)流圖的生成與優(yōu)化，根據(jù)本文設(shè)計(jì)的數(shù)據(jù)流圖生成算法得到數(shù)據(jù)流圖Graph。

如圖9（a）所示測(cè)試采用DES加密密碼算法中的單次循環(huán)，經(jīng)過數(shù)據(jù)流圖生成后將會(huì)得到如圖9（b）所示的數(shù)據(jù)流圖Graph，Graph中的元素包括節(jié)點(diǎn)標(biāo)志、父母節(jié)點(diǎn)、子節(jié)點(diǎn)與運(yùn)算類型FU，從數(shù)據(jù)中可以分析出節(jié)點(diǎn)間的連接關(guān)系。與測(cè)試用例進(jìn)行比對(duì)，數(shù)據(jù)流圖生成正確。

圖9 數(shù)據(jù)流圖生成流程Fig.9 Data flow chart generation process

3.2.1 代碼檢測(cè)實(shí)驗(yàn)與分析

為研究本文基于注意力的圖嵌入模型對(duì)代碼識(shí)別的效果，本文將其與deepwalk、GAT 網(wǎng)絡(luò)在同樣的實(shí)驗(yàn)條件下進(jìn)行對(duì)比，并進(jìn)行分析。實(shí)驗(yàn)使用BigClone-Bench代碼克隆數(shù)據(jù)集，從中提取出克隆代碼片段及克隆對(duì)的類別，并且將提取出的數(shù)據(jù)以8∶2的比例分割為訓(xùn)練集和測(cè)試集，在進(jìn)行測(cè)試前先對(duì)相應(yīng)的代碼片段預(yù)處理，生成數(shù)據(jù)流圖。接著對(duì)數(shù)據(jù)集進(jìn)行標(biāo)注，功能相似的標(biāo)注為1，反之為0。測(cè)試結(jié)果為相似功能測(cè)試，從同功能測(cè)試數(shù)據(jù)集中抽取5個(gè)代碼對(duì)，進(jìn)行排列組合后生成10 組測(cè)試用例，并送入上述3 個(gè)模型中進(jìn)行測(cè)試，測(cè)試結(jié)果如表1所示。

從表中可以看出本文提出的代碼檢測(cè)模型，對(duì)同種類代碼檢測(cè)的相似度都在80%以上，高于單獨(dú)deepwalk、GAT 網(wǎng)絡(luò)的檢測(cè)結(jié)果。deepwalk 采取隨機(jī)游走的策略雖然可以盡可能地探知上下文結(jié)構(gòu)，但是代碼中存在許多不重要的節(jié)點(diǎn)，從而產(chǎn)生了許多不必要的噪聲影響結(jié)果，在GAT 網(wǎng)絡(luò)中，當(dāng)前節(jié)點(diǎn)聚合了鄰居節(jié)點(diǎn)的特征，但只能獲得相鄰的一階鄰居，而無法影響過長(zhǎng)的N階鄰居節(jié)點(diǎn)，影響了對(duì)整體結(jié)構(gòu)特征的聚合。

本文的基于注意力的圖嵌入模型，結(jié)合了兩者的特點(diǎn)，首先提取出當(dāng)前節(jié)點(diǎn)對(duì)其鄰居節(jié)點(diǎn)的注意力權(quán)重，并在圖嵌入網(wǎng)絡(luò)中以此注意力權(quán)重構(gòu)建有價(jià)值的節(jié)點(diǎn)序列，從而生成節(jié)點(diǎn)特征向量，最后聚合了GAT和圖嵌入的特征向量能夠充分代表當(dāng)前代碼片段的特征，模型較高的識(shí)別相似度有利于功能分類的正確性。

為測(cè)試對(duì)功能進(jìn)行分類性能，將與deepwalk、node2vec、GAT經(jīng)典算法進(jìn)行分類性能的比較實(shí)驗(yàn)。實(shí)驗(yàn)中采取10折交叉驗(yàn)證（10-fold cross validation，10-CV）來對(duì)分類性能的準(zhǔn)確率（Precision）、召回率（Recall）、F1等結(jié)果進(jìn)行全面評(píng)估，具體的計(jì)算公式如下所示：

公式中TP為真值與預(yù)測(cè)值為正值1；FP為真值為假值0，預(yù)測(cè)值為正值1；FN為真值為1，預(yù)測(cè)值為0；TN為真值與預(yù)測(cè)都為0；公式（9）針對(duì)預(yù)測(cè)結(jié)果而言，預(yù)測(cè)正例的樣本中有多少是真正正例的；公式（10）針對(duì)原來樣本而言，代表正例有多少被預(yù)測(cè)成功了；F1 為考慮Precision與Recall影響的運(yùn)算結(jié)果。最終的實(shí)驗(yàn)結(jié)果如表2所示。

表2 分類性能對(duì)比Table 2 Classification performance comparison

從表中可以看出，本文的方法取得了較好的分類性能，在Precision、Recall、F1 三個(gè)指標(biāo)均取得了性能的提升，以上實(shí)驗(yàn)結(jié)果表示本文提出的模型可以很好地提取出節(jié)點(diǎn)之間的隱含關(guān)系特征，很大程度提升了功能分類預(yù)測(cè)的效果。

3.2.2 數(shù)據(jù)流圖優(yōu)化測(cè)試

在數(shù)據(jù)流圖初始生成后，會(huì)存在各種缺陷，若不進(jìn)行優(yōu)化，會(huì)對(duì)后續(xù)的映射產(chǎn)生各種不利影響，因此需對(duì)生成后的數(shù)據(jù)流圖進(jìn)行相應(yīng)優(yōu)化。數(shù)據(jù)流圖首先展開函數(shù)節(jié)點(diǎn)，消除冗余節(jié)點(diǎn)，最后采用數(shù)據(jù)流圖分層算法進(jìn)行并行化，具體的優(yōu)化過程如圖10所示。

圖10 數(shù)據(jù)流圖優(yōu)化流程Fig.10 Data flow diagram optimization process

如圖10（a）所示采用包含函數(shù)和循環(huán)的一段代碼作為測(cè)試用例，將循環(huán)體展開，經(jīng)數(shù)據(jù)流圖生成后可得到圖10（b）所示的數(shù)據(jù)流圖，虛線框中包含有可展開的函數(shù)節(jié)點(diǎn)，與函數(shù)體對(duì)應(yīng)的數(shù)據(jù)流圖。經(jīng)函數(shù)展開后得到圖10（c）所示的數(shù)據(jù)流圖，虛線框中為展開后的函數(shù)節(jié)點(diǎn)，框中ASSIGN 節(jié)點(diǎn)為函數(shù)參數(shù)賦值語句，在測(cè)試用例中對(duì)應(yīng)的為“W1，W2=tmp0，tmp1”，函數(shù)體的返回參數(shù)W直接參與運(yùn)算。

由于數(shù)據(jù)流圖中的ASSIGN語句為冗余節(jié)點(diǎn)，進(jìn)行優(yōu)化可縮減數(shù)據(jù)流圖的規(guī)模，同時(shí)為提取出節(jié)點(diǎn)間的并行性，采用數(shù)據(jù)流圖分層算法進(jìn)行分層，運(yùn)行后可得到圖10（d）所示的數(shù)據(jù)流圖。經(jīng)數(shù)據(jù)流圖優(yōu)化過后，不僅提取出節(jié)點(diǎn)間的并行性，還精簡(jiǎn)了數(shù)據(jù)流圖，并且數(shù)據(jù)流圖與測(cè)試用例相對(duì)應(yīng)。

3.3 性能測(cè)試

為檢驗(yàn)本文提出的CRCLA 編譯前端的優(yōu)勢(shì)，本節(jié)從優(yōu)化后的數(shù)據(jù)流圖長(zhǎng)度，以及最終映射在CRCLA 上的密碼算法執(zhí)行性能上進(jìn)行對(duì)比。如表3所示，在處理相同的以高級(jí)語言C++編寫的密碼算法代碼時(shí)，以前面介紹的面向可重構(gòu)結(jié)構(gòu)的編譯器REmus、Spatial、TIRAMISU 與面向眾核結(jié)構(gòu)的TAP-S 編譯器作為比較對(duì)象，本文生成的DFG長(zhǎng)度只占其他編譯器的十分之一左右。

表3 不同密碼算法下的DFG長(zhǎng)度Table 3 Length of DFG under different password algorithms

這是因?yàn)樵趯?shí)際編寫密碼算法程序的過程中，高級(jí)語言C++可以不同方式實(shí)現(xiàn)密碼算法中的特殊函數(shù)運(yùn)算如S盒、比特置換，但這些特殊功能在本文的CRCLA中可用單算子進(jìn)行實(shí)現(xiàn)。其他編譯器沒有對(duì)此進(jìn)行相應(yīng)優(yōu)化，在對(duì)源代碼進(jìn)行分析時(shí)依然采用原有的數(shù)據(jù)結(jié)構(gòu)，而本文的編譯器采取代碼識(shí)別的方法對(duì)特殊功能結(jié)構(gòu)進(jìn)行識(shí)別并替代，因此其他編譯器獲得的DFG 長(zhǎng)度遠(yuǎn)大于本文。

此外，本文取得的數(shù)據(jù)流圖由于將特殊功能結(jié)構(gòu)進(jìn)行替換，從而避免了大量非必要的運(yùn)算節(jié)點(diǎn)映射在CRCLA 中。因此在面對(duì)特殊功能如S 盒等，本文用單條運(yùn)算映射，而其他編譯器則需用一串運(yùn)算節(jié)點(diǎn)進(jìn)行映射。在這種情況下，本文映射密碼算法到CRCLA上時(shí)，CRCLA 可用更少的計(jì)算步驟與時(shí)間進(jìn)行運(yùn)行，從而提高了映射性能。

為精確展示本文前端的有效性，以其他編譯器前端分析產(chǎn)生的數(shù)據(jù)流圖作為輸入，將其映射到本文的CRCLA 硬件上進(jìn)行仿真測(cè)試，最終得到的執(zhí)行性能如表4所示。相比于其他編譯器，本文前端獲得的數(shù)據(jù)流圖在CRCLA上執(zhí)行的性能平均提高了約37%。

表4 不同密碼算法下的映射性能對(duì)比Table 4 Comparison of mapping performance under different password algorithms 單位：Mbit/s

4 結(jié)束語

本文針對(duì)粗粒度可重構(gòu)密碼邏輯陣列，設(shè)計(jì)了一款自動(dòng)化編譯前端工具。該前端設(shè)計(jì)包含詞法、語法、語義分析器，可提取出源代碼中的關(guān)鍵信息并生成數(shù)據(jù)流圖。利用基于注意力機(jī)制的圖嵌入模型識(shí)別圖結(jié)構(gòu)，并用同功能的算子進(jìn)行替換，解決如S 盒替換函數(shù)在CRCLA中可用單算子代替實(shí)現(xiàn)的問題。最終使用內(nèi)聯(lián)替換、冗余移除、數(shù)據(jù)流圖分層算法等技術(shù)解決數(shù)據(jù)流圖并行度不足與過長(zhǎng)問題。該編譯前端具有自動(dòng)化生成適用于CRCLA 的數(shù)據(jù)流圖，為可重構(gòu)密碼邏輯陣列的使用提供強(qiáng)有力的支持。實(shí)驗(yàn)結(jié)果驗(yàn)證了該編譯前端工具自動(dòng)化與高性能的優(yōu)點(diǎn)。