南京大學智能軟件工程實驗室
iselab.cn
引言
一直以來，代碼克隆檢測在軟件維護、安全和質量保證的領域都是一個重要的關注點。儘管目前已經有一些方法結合了語法和語義的特徵，但是它們忽略了函數之間的調用關係，這可能會對功能代碼克隆檢測產生不利的影響。本文提出了一個功能的代碼克隆檢測工具 FCDetector。FCDetector 首先繪製了函數調用關係圖，然後通過分析抽象語法樹和程序控制流圖來獲取代碼的語法、語義特徵。最後，基於這些特徵的結合，FCDetector 使用深度神經網絡模型來進行代碼克隆檢測。我們將 FCDetector 用於一個大型的真實數據集 OJClone 進行實驗，實驗證明 FCDetector 可以有效檢測功能的代碼克隆。關於 FCDetector 的視頻解說可以在https://youtu.be/woZuOOIZ3Ms進行觀看，工具的應用可以在https://github.com/shiyy123/FDetector.獲取。
1 介紹
代碼克隆也被稱為重複的代碼。重複代碼是源代碼片段，該代碼片段在一個程序中或在同一實體擁有或維護的不同程序中多次出現。自動識別重複代碼的過程就是代碼克隆檢測。
代碼克隆在很多方面都是有害的，可能會對軟件維護、安裝、質量產生負面影響。如果一段有缺陷的代碼被克隆到其他系統中，可能會產生潛在威脅。因此，代碼克隆檢測在軟件工程領域吸引了越來越多研究者的關注，也得到了廣泛的應用。
代碼克隆檢測有四種基本類型：類型一：除了空格、換行和註釋，完全相同的代碼片段；類型二：除了變量和參數，基本相同的代碼片段；類型三：除了有部分新增或刪減的代碼段，其他部分完全相同的代碼片段；類型四：代碼片段實現的功能相同，但語義結構不相同。其中針對類型四的代碼克隆檢測被視為功能的代碼克隆檢測，它是最為複雜的一種克隆檢測類型。
FCDetector 主要針對類型四的代碼克隆檢測，即功能性的代碼克隆檢測，此類檢測在軟件工程領域有著廣泛的用戶場景。比如，如果發現某個功能的代碼段會導致系統出現漏洞缺陷，那麼檢測出來的克隆代碼也很可能存在類似的缺陷，通過代碼克隆檢測可以快速定位代碼缺陷。在代碼推薦相關的應用場景下，代碼克隆也有著關鍵性的應用，比如有大量代碼需要給專家進行評審，可以根據 FCDetector 挑選出功能類似的代碼，推薦同一個專家，這樣可以使專家更好的理解代碼，提高評審效率。
儘管目前已經有了許多代碼克隆檢測的技術，但是大部分都不能很好的檢測“功能”的代碼克隆。因為針對功能的代碼克隆較為複雜，通過比較類似標識符的基本特徵相似度很難檢測出功能代碼克隆。除此之外，目前可以檢測功能代碼克隆的方法，嘗試在函數級別上解析語法和語義特徵，但是他們沒有很好的分析函數之間的調用關係，這可能使得克隆檢測的效果不佳。為了解決這一問題，本文提出 FCDetector 這一工具，FCDetector 首先繪製函數調用圖（(Function Call Graph，FCG）來分析函數之間的調用關係，然後使用抽象語法樹（Abstract Syntax Tree，AST）和控制流圖（Control Flow Graph，CFG）來分別抽取語法和語義的特徵。最後 FCDetector 使用一個深度神經網絡模型來檢測代碼克隆。基於 OJClone 數據集的實驗結果表明，FCDetector 可以有效的檢測功能的代碼克隆。
2 FCDetector 工具
FCDetector 的整體流程圖如圖 1 所示。FCDetector 的流程圖主要包含 5 個主要部分：（1）解析 FCG，（2）解析 AST 和 CFG，（3）使用嵌入技術生成特徵向量，（4）訓練 DNN 分類模型，（5）功能代碼克隆檢測。
為了識別具有功能性克隆的代碼片段，FCDetector 首先分析 FCG 來獲取函數之間的調用關係，然後將函數級別的 AST 和 CFG 進行結合，分別生成整段代碼的 AST 和 CFG。為了將這些特徵轉換為向量，FCDetector 使用嵌入技術來解析這些特徵，在組合了特徵向量之後，FCDetector 訓練了一個 DNN 模型來檢測功能代碼克隆。
圖 1 系統流程圖
2.1 解析 FCG
像 C++這樣的高級程序設計語言是靈活多變的。不同的代碼結構可以實現同樣一個功能，這使得功能的代碼克隆檢測變得複雜和困難。對於機器而言，理解函數之間的關係是十分困難的。所以非常有必要解析代碼結構特徵，來映射函數之間的調用關係。
FCG 是一種圖結構，它可以很有效的體現出函數之間的調用關係，從而分析出代碼段中的函數結構。FCDetector 使用一個 C/C++代碼分析工具 Joern 來解析 FCG，函數調用關係使用一個三元組來表示：，其中調用函數 id 是調用函數的標識符，被調用函數 id 是被調用函數的標識符。
我們根據真實的開源代碼數據集，總結了 6 種常見的函數調用圖，如圖 2 所示。關於使用不同函數調用圖來實現同一功能的具體例子，將在第三章中展示。使用 FCG 連接函數的 CFG 的相關規則，在 2.2 章節闡述。
圖 2 六種函數調用關係圖
2.2 解析 AST 和 CFG
FCDetector 首先使用 Joern 工具解析每個函數的 AST 和 CFG。每個函數的 AST 可以被視為一個樹的結構。假設我們有一段代碼 C，和它的 AST 根節點 Nroot。對於每個樹形結構，我們可以使用先序遍歷的方法，將 AST 的葉子節點排成一串節點，每個函數的語法特徵可以表示為 Tm = {node1,node2,...,noden}，其中 node1 是 Tm 中的每個子節點。
每個函數的 CFG 可以表示為一個圖的結構 Gm = (V,E)，其中 V 是節點的集合，E 是邊的集合。
根據圖 2 展示的函數調用關係，FCDetector 可以將函數的 CFG 鏈接起來，形成整段代碼的 CFG。具體鏈接規則如下。對於第一種情況，整段代碼的 CFG 和函數的 CFG 是一樣的；對於第二種情況，調用語句的節點需要增加一條邊到入口節點；對於第三種情況，A 函數的父節點要指向 B 函數的入口節點，而且所有的孩子節點都要指向 B 函數的出口節點；第四、五種情況和第三種相似，除了鏈接另一個函數調用語句的邊需要重新調整。第六種情況是兩個單獨的函數，所以需要分別處理各自的功能對應的 CFG。
根據 2.1 章節種提到的函數連接方法，對於每個代碼片段，FCDetector 會將函數的 AST/CFG 連接成整個代碼段對應的 AST/CFG。通過使用 FCG 來獲取函數之間的調用關係，FCDetector 可以準確地描述每個代碼段對應地功能。
2.3 使用嵌入技術生成特徵向量
為了將特徵轉換為特徵向量，並用於機器學習模型，FCDetector 使用詞嵌入技術來編碼 AST 以獲取語法特徵，使用圖嵌入技術來編碼 CFG 以獲取語義特徵。
詞嵌入是一種提取有意義的語法語義特徵的強大的方法，詞嵌入技術可以將一個詞轉換成一個固定長度的向量，這對於數學處理運算是非常有幫助的。因為函數抽象語法樹 Tm 的每個節點 nodei 都可以被視為一個單詞，所以 FCDetector 使用詞嵌入來編碼 Tm，從而獲取語法特徵。
通過使用詞嵌入 Word2vec 方法，Tm 中的每個節點都可以被簡化為一個單詞，進而計算出它們對應的特徵向量 Vnode。然後每個函數的語法特徵可以被表示為一個固定長度的向量 Vm=averge(Vnodei),i={1,2,...,Nm}。其中 Nm 是每個函數中所有的節點個數。
圖形嵌入旨在在保持儘可能多的圖形信息的同時，在低維空間中表示圖形。通過使用圖嵌入技術，圖中的每個節點可以表示為一個向量，FCDetector 用圖嵌入 HOPE 技術來轉化 CFG 為語義特徵向量。通過使用 HOPE，每個節點可以被表示為一個固定長度的向量 Vvertex。
最後，語法和語義特徵向量可以被表示為
V1 = average(Vmi),i = {1, 2, ..., Nf}
V2 = average(Vvertexi),i = {1,2,...,Nf}
其中 Nf 是每個代碼片段中函數的總數。
2.4 訓練 DNN 分類模型
FCDetector 將語法和語義特徵向量的結合做為前向神經網絡的輸入。DNN 模型的結構如圖 3 所示。FCDetector 將 V1，V2 用兩種不同的順序進行結合，分別為[V1,V2]和[V2,V1]，這是為了消除輸入數據對稱性的影響。
圖 3 DNN 模型圖
DNN 模型將語法語義特徵的結合做為輸入，每個語法和語義的特徵用 16 維度的向量表示。總共的輸入向量維度是 33（16+16+1），增加的這 1 維度向量是標籤，標籤有兩個值：0 或 1，代表是否是代碼克隆。
為了將輸入轉換為神經節點，隱藏層使用線性變換，然後壓縮非線性。DNN 模型使用反向傳播，根據訓練集調整權重矩陣 W。 最後有一個 softmax 層，它將功能克隆檢測轉換為分類問題。
2.5 功能代碼克隆檢測
假設有兩個代碼段的特徵向量 V1 和 V2，特徵之間的關聯性可以視為兩者之間的距離 d=|V1-V2|，然後我們以此視為他們相似程度的輸出。
在訓練好所有參數後，訓練好的模型會存儲下來。下一次，源代碼的特徵向量可以直接被用於神經網絡進行克隆檢測，無需再訓練神經網絡模型。輸出的結果是 0 或 1，表示是否有功能的代碼克隆。
3 實驗評價
FCDetector 的實驗評價包含 3 個部分。我們首先介紹實驗的環境，然後將 FCDetector 與另外五種現有的克隆檢測工具進行比較。最後，我們展示了一個功能的克隆檢測例子，來說明 FCDetector 的效果。FCDetector 具體的用法和實驗結果在視頻中展示。
3.1 實驗配置
我們使用了一個開源的 C++數據集 OJClone 來對 FCDetector 進行實驗和評估。OJClone 包含 104 個算法任務，每個算法有 500 個不同學生提交的不同版本的代碼。對於同一個算法題目，不同版本的代碼就可以被視為功能的代碼克隆。我們隨機選擇了 35 個題目，每個題目隨機選取 100 個代碼片段做為數據。我們使用 Intel i7 4.0GHz 4 核 CPU 和 GTX1060GPU 進行實驗。
3.2 與其他代碼克隆檢測工具的比較結果
我們將 FCDetector 與其他 5 中現有的代碼克隆檢測工具進行比較，指標為精確率（Precision，P），召回率（Recall，R），和 F1 分數。因為 OJClone 數據集主要屬於功能的代碼克隆檢測，克隆檢測的效果可以體現這些工具在功能代碼克隆檢測的能力。表 1 展示了這 6 種工具的精確率、召回率和 F1 分數。初步的實驗結果表明，FCDetector 可以有效的檢測功能性的代碼克隆。
表 1 不同代碼克隆檢測工具在 OJClone 上的效果
3.3 使用 FCDetector 進行功能性的代碼克隆檢測示例
圖 4 展示了三個代碼片段示例，因為示例 1 和示例 2 的函數調用關係完全不一樣，他們可能看起來不像是克隆的代碼，但他們實現的功能是完全一樣的，因此他們是功能性的代碼克隆。示例 1 的函數調用可以與圖 2 中的（1）匹配，而示例 2 的函數調用可以與圖 2 中（2）匹配。對於示例 1 來說，整個代碼段的 CFG 就是函數的 CFG，而對於示例 2，整個代碼段的 CFG 就是圖 4（d）展示的樣子。不同的函數調用關係可能會導致常見的克隆檢測工具產生誤報。因為 FCDetector 考慮到了函數之間的調用關係，它可以準確的檢測出這兩段代碼之間存在功能性的克隆。
單獨依靠 CFG 不足以檢測功能性的代碼克隆，示例 1（求和方法）和示例 3（求乘積方法）的代碼文本基本是一樣的，他們的 CFG 在結構層次上也是一樣的，但是他們表示完全不同的功能，這兩種代碼段的區別潛藏在循環體的 AST 中。這兩個 AST 的區別在於一個符號的不同，如圖 4（e）所示，FCDetector 會判定示例 1 和示例 3 不是功能性的克隆檢測，是因為它結合了源代碼語法和語義的特徵。
圖 4 代碼克隆檢測示例
5 總結
在這篇文章中，我們提出了一個功能性的代碼克隆檢測工具 FCDetector，它運用 FCG 來結合了函數的 AST/CFG，生成出每個代碼段的 AST/CFG。然後我們使用嵌入技術來解析語法和語義特徵。最後，我們訓練了一個 DNN 模型來進行功能性的代碼克隆檢測。在 OJClone 數據集上的初步實驗結果表明，FCDetector 可以有效地檢測功能性的代碼克隆。基於 FCDetector，我們可以在代碼質量管理、代碼重構等領域展開更加長遠的研究和探索。
致謝
本文由南京大學軟件學院 2020 級碩士劉子夕翻譯轉述。
感謝國家自然科學基金（61932012，61802171，61772014）支持！
閱讀更多 慕測科技 的文章
