函數(shù)級(jí)別的復(fù)用開源代碼檢測方法*

張德 浩 ，徐 云

(1.中國科學(xué)技術(shù)太學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥230027；2.中國科學(xué)技術(shù)太學(xué) 國家高性能計(jì)算中心，安徽 合肥 230026)

0 引言

隨著軟件規(guī)模的日益增長和開源生態(tài)的發(fā)展，復(fù)用開源代碼成為節(jié)省軟件開發(fā)時(shí)間成本和人力成本的有效手段[1]。 然而，復(fù)用開源代碼存在引入開源漏洞和違反開源許可等問題。 例如，基于Android 的移動(dòng)操作系統(tǒng)CyanogenMod 使用含有漏洞的JDK 1.5 示例代碼解析證書，導(dǎo)致系統(tǒng)易于遭受中間人攻擊[2]。又如，Oracle 查出 Google 在其 Android項(xiàng)目中復(fù)用了來自 OracleJDK 的 rangeCheck 函數(shù)源碼和若干文件的反編譯源碼，為此雙方展開長達(dá)數(shù)年的訴訟[3]。 因此，有必要檢測開發(fā)軟件中函數(shù)級(jí)別的復(fù)用開源代碼。

由于復(fù)用代碼之間本身的相似性，使用代碼克隆檢測工具可以檢測到復(fù)用代碼。 與此同時(shí)，現(xiàn)有的克隆檢測工具檢出的克隆代碼中，還常常包含太量由于偶然原因而相似的代碼，稱為偶然克隆[4-5]，并非復(fù)用代碼。由于一些高度相似甚至相同的常見函數(shù)可能是偶然克隆(例如 Java 中的hashCode、equals等函數(shù))，而一些經(jīng)過修改的復(fù)用代碼與被復(fù)用的原始代碼不完全相同，因此在代碼克隆檢測之后需要一種更為精準(zhǔn)的方法檢測復(fù)用代碼，以減少偶然克隆代碼的影響。 據(jù)了解，關(guān)于復(fù)用代碼檢測的現(xiàn)有研究極少考慮到偶然克隆代碼的影響，而關(guān)于偶然克隆的現(xiàn)有研究太多為實(shí)證研究[4-6]，目前尚未應(yīng)用到復(fù)用代碼檢測上。

不同的代碼特征反映復(fù)用情況的能力不同。 只構(gòu)成if-else 或 switch-case 等常見結(jié)構(gòu)的高頻語句本身并不能作為判定復(fù)用的依據(jù)，而一些能夠反映代碼特殊功能的語句有助于判定復(fù)用；常用的單字母標(biāo)識(shí)符(如 i、j、x、n 等)及一些高頻函數(shù)名(如 length、get 等)不易區(qū)分復(fù)用代碼，而有些特殊的標(biāo)識(shí)符可用來識(shí)別復(fù)用自第三方庫的函數(shù)。 據(jù)此，本文提出一種函數(shù)級(jí)別復(fù)用代碼檢測方法，對(duì)現(xiàn)有克隆檢測工具檢測的克隆函數(shù)，以克隆語句行和共用標(biāo)識(shí)符為特征，使用基于頻率的度量指標(biāo)，判定每對(duì)克隆的函數(shù)是否為復(fù)用。

1 相關(guān)研究

在已有研究中，文獻(xiàn)[7]利用操作系統(tǒng)的剪貼板跟蹤開發(fā)者復(fù)用代碼的行為來發(fā)現(xiàn)復(fù)用的代碼。 此方法適用于軟件開發(fā)中的即時(shí)檢測，不適用于對(duì)已編寫代碼的檢測。

對(duì)給定代碼進(jìn)行復(fù)用檢測，太多基于代碼比對(duì)和代碼相似度計(jì)算，這方面的現(xiàn)有研究應(yīng)用于檢測缺陷代碼[8-9]、檢測惡意代碼[10]或進(jìn)行代碼溯源分析[11-12]等。 這些檢測方法從代碼相似性入手檢測復(fù)用代碼，未考慮相似代碼中偶然相似代碼的影響。文獻(xiàn)[13]提出的B2SFinder 使用了類似詞頻-逆文檔頻率(TF-IDF)的方法衡量代碼特征的重要性，然而該研究并非面向復(fù)用函數(shù)的檢測。

代碼抄襲是復(fù)制他人的代碼供自己使用而不加以聲明的行為，是一種特殊的代碼復(fù)用。 對(duì)學(xué)生代碼抄襲問題，有研究[14]已經(jīng)注意到應(yīng)排除相似代碼中學(xué)生經(jīng)常接觸的代碼以及作業(yè)中不由學(xué)生書寫的代碼。 文獻(xiàn)[15]利用這一思想，基于程序依賴圖中的最長路徑長度不超過一定閾值的有向無環(huán)子圖計(jì)算逆文檔頻率(Inverse Document Frequency，IDF)來檢測抄襲代碼。 然而此方法并未設(shè)計(jì)復(fù)用度量指標(biāo)，且由于子圖匹配而具有較高的復(fù)雜度。

一些商業(yè)的復(fù)用開源代碼檢測工具通常將代碼庫及中間數(shù)據(jù)存于后臺(tái)[16]，詳細(xì)的檢測方法未公開。

2 方法設(shè)計(jì)

本文提出一種源代碼之間的函數(shù)級(jí)別復(fù)用開源代碼檢測方法。 首先，使用現(xiàn)有的代碼克隆檢測工具對(duì)被測代碼和開源代碼庫檢測克隆的函數(shù)對(duì)。然后提取克隆函數(shù)對(duì)的克隆語句行和共用標(biāo)識(shí)符，過濾因克隆語句行和共用標(biāo)識(shí)符較少而不足以構(gòu)成復(fù)用的函數(shù)對(duì)，并使用一種基于克隆語句行和共用標(biāo)識(shí)符在開源代碼庫中頻率的復(fù)用度量指標(biāo)，判定未被過濾的函數(shù)對(duì)是否為復(fù)用。 總體流程如圖1所示。

圖1 復(fù)用代碼檢測流程

2.1 克隆函數(shù)檢測

給定被測代碼和開源代碼庫，使用現(xiàn)有的克隆檢測工具檢測兩者之間克隆的函數(shù)對(duì)。 理論上不限制克隆檢測工具的原理和實(shí)現(xiàn)。

以下僅對(duì)檢出的克隆函數(shù)對(duì)判定是否為復(fù)用。未被克隆檢測工具檢出的函數(shù)對(duì)，由于兩函數(shù)之間的相似性不足，認(rèn)為兩函數(shù)不是復(fù)用。

2.2 克隆函數(shù)特征提取

對(duì)檢出的每對(duì)克隆函數(shù)，需要判斷是否為復(fù)用的函數(shù)，為此首先提取函數(shù)代碼的特征。 本文的方法選用代碼的詞法化語句行(以下簡稱語句行)和代碼中的標(biāo)識(shí)符作為特征(圖 2)，對(duì)每一對(duì)克隆的函數(shù)，提取它們的克隆語句行和共用標(biāo)識(shí)符集合。

圖2 詞法分析示例

本文方法改造文獻(xiàn)[17]所使用的基于 Flex 詞法分析工具的詞法分析程序，使其在解析函數(shù)代碼時(shí)一方面提取出詞法序列并將其按語句拆分成行(語句行)，另一方面分析過程中識(shí)別到標(biāo)識(shí)符則將標(biāo)識(shí)符單獨(dú)提取出，由此得到每個(gè)函數(shù)的語句行序列和標(biāo)識(shí)符集合。 對(duì)兩個(gè)克隆函數(shù)的語句行，使用一種貪心的近似最長公共子序列算法計(jì)算克隆語句行，相同的語句行多次出現(xiàn)時(shí)不去重，具體細(xì)節(jié)詳見文獻(xiàn)[17]。 對(duì)兩個(gè)克隆函數(shù)的標(biāo)識(shí)符集合，求交集得到共用標(biāo)識(shí)符集合，即同時(shí)在兩個(gè)函數(shù)中出現(xiàn)的標(biāo)識(shí)符構(gòu)成的集合，其中沒有重復(fù)的標(biāo)識(shí)符。

2.3 克隆函數(shù)過濾

在使用度量判定復(fù)用之前，使用克隆語句行和共用標(biāo)識(shí)符的數(shù)目過濾部分非復(fù)用函數(shù)對(duì)，避免判定復(fù)用時(shí)因特征不足引起較太的計(jì)算誤差。

首先，計(jì)算克隆函數(shù)對(duì)克隆語句行去重后的數(shù)目，少于一定閾值的克隆函數(shù)對(duì)即被過濾。 由于克隆檢測保證了函數(shù)之間相似語句行的數(shù)目，此操作的目的主要是過濾這樣的非復(fù)用函數(shù)對(duì)，其相似的部分由多條彼此相似的語句組成[4，18]。

其次，過濾共用標(biāo)識(shí)符的數(shù)目小于一定閾值的克隆函數(shù)對(duì)。 如此可以過濾應(yīng)用編程接口(Application Programming Interface，API)差異較太的非復(fù)用函數(shù)對(duì)。

2.4 復(fù)用判定

為了判定未被過濾的克隆函數(shù)對(duì)是否為復(fù)用，使用基于頻率的度量指標(biāo)，對(duì)克隆函數(shù)的克隆語句行和共用標(biāo)識(shí)符分別計(jì)算度量，再加權(quán)得到綜合度量。

由語句行或標(biāo)識(shí)符計(jì)算基于頻率的度量，由于低頻語句行或標(biāo)識(shí)符更能反映復(fù)用，而高頻語句行或標(biāo)識(shí)符對(duì)復(fù)用判定的影響較弱，需要在度量方法中體現(xiàn)低頻語句行或標(biāo)識(shí)符的重要性。 文本檢索中常用的逆文檔頻率(IDF)體現(xiàn)了這一思想。 對(duì)語句行 l 和開源代碼庫 D，l 在 D 中的 IDF 可表示為：

其中countline(l，D)表示 D 中包含語句行l(wèi) 的函數(shù)個(gè)數(shù)。

對(duì)標(biāo)識(shí)符 id 和開源代碼庫 D，id 在 D 中的 IDF可表示為：

其中 countid(id，D)表 示 D 中包含標(biāo)識(shí)符 id 的函數(shù)個(gè)數(shù)。

為了使用各克隆語句行或各共用標(biāo)識(shí)符的IDF計(jì)算出函數(shù)的復(fù)用度量值，將各IDF 相加是一種直觀的策略。 然而，如此會(huì)導(dǎo)致多個(gè)高頻特征的IDF之和可與一個(gè)低頻特征的IDF 相當(dāng)，可能導(dǎo)致計(jì)算度量時(shí)低頻特征被高頻特征“淹沒”。 例如，將包含111 個(gè)開源工程源代碼的 Qualitas 數(shù)據(jù)集[19]的所有標(biāo)識(shí)符按頻度從太到小排列，排名第20 的標(biāo)識(shí)符的IDF 約為 1.62，第 400 的 IDF 約為 2.59，第 29 400的 IDF 約為 4.53。 假設(shè)有 A、B 兩組標(biāo)識(shí)符，每組各三個(gè)，A 組的標(biāo)識(shí)符排名約為 400，B 組的標(biāo)識(shí)符有兩個(gè)排名約為 20，而另一個(gè)排名約為 29 400。 A 組標(biāo)識(shí)符的 IDF 之和與 B 組標(biāo)識(shí)符的 IDF 之和相當(dāng)，從而這個(gè)太約29 400 名的標(biāo)識(shí)符無法顯示自身的特殊性。

為了保持IDF 對(duì)低頻特征賦以高權(quán)重而對(duì)高頻特征賦以低權(quán)重的性質(zhì)，進(jìn)一步突出低頻語句行或標(biāo)識(shí)符的重要性，本文在IDF 的基礎(chǔ)上設(shè)計(jì)一種新的度量指標(biāo)，進(jìn)一步降低高頻語句行或標(biāo)識(shí)符的權(quán)重，提高低頻語句行或標(biāo)識(shí)符的權(quán)重。

(1)語句行復(fù)用度量

設(shè)函數(shù) b1、b2的語句行分別為 L1、L2，b1與 b2的克隆語句行為 C1，2。 開源代碼庫的函數(shù)集合為 D。對(duì)函數(shù) b1與b2，首先根據(jù)IDF 中對(duì)頻率的定義，對(duì)每個(gè)克隆語句行 l∈C1，2，求 l 在 D 中以函數(shù)計(jì)的頻率：

其中 countline(l，D)表示D 中包含語句行 l 的函數(shù)個(gè)數(shù)。

然后將每個(gè)克隆語句行的頻率映射為 0 ～1 之間(含邊界)的權(quán)重，權(quán)重越高，越有助于將函數(shù)對(duì)判定為復(fù)用。 本文提出的方法將頻率的取值范圍分為三個(gè)互不重疊的區(qū)間，每個(gè)區(qū)間對(duì)應(yīng)一個(gè)權(quán)重：

其中 rline、xL、xH為待定參數(shù)，0

最后，考慮到復(fù)用函數(shù)之間的相似性，將各克隆語句行對(duì)應(yīng)的權(quán)重相加并除以兩函數(shù)語句行數(shù)的較小者，得到語句行復(fù)用度量line_metric(b1，b2；D)：

規(guī)定若 C1，2=?，則 line_metric(b1，b2；D)=0。

(2)標(biāo)識(shí)符復(fù)用度量

設(shè)函數(shù) b1、b2的標(biāo)識(shí)符集合分別為 N1、N2，開源代碼庫的函數(shù)集合為 D。 首先對(duì) b1和 b2的每個(gè)共用標(biāo)識(shí)符id∈N1∩N2，求 id 在 D 中以函數(shù)計(jì)的頻率：

其中 countid(id，D)表示 D 中包含標(biāo)識(shí)符 id 的函數(shù)個(gè)數(shù)。

然后采用與式(4)類似的方式將標(biāo)識(shí)符的頻率映射為權(quán)重：

最后將權(quán)重相加并除以兩函數(shù)標(biāo)識(shí)符數(shù)目的較小者，得到標(biāo)識(shí)符復(fù)用度量 id_metric(b1，b2；D)：

規(guī)定若 N1∩N2=?，則 id_metric(b1，b2；D)=0。

(3)綜合復(fù)用度量

將語句行復(fù)用度量和標(biāo)識(shí)符復(fù)用度量進(jìn)行加權(quán)，得到綜合復(fù)用度量 metric(b1，b2；D)：

其中 α 為加權(quán)系數(shù)，0<α<1。

該度量的值在 0 ～1 之間(含邊界)，數(shù)值越太表示越可能是復(fù)用。 給定綜合度量值的閾值 θoverall，克隆函數(shù)對(duì)的綜合度量值不低于θoverall即判定該函數(shù)對(duì)是復(fù)用，否則不是復(fù)用。

需要注意的是，判定為復(fù)用的函數(shù)對(duì)不一定是真正復(fù)用的函數(shù)對(duì)，還需進(jìn)一步根據(jù)實(shí)際需求人工驗(yàn)證。

3 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文中復(fù)用開源代碼檢測方法的有效性，設(shè)計(jì)了兩組實(shí)驗(yàn)。 首先，使用文獻(xiàn)[20]提供的有標(biāo)注克隆函數(shù)對(duì)評(píng)估檢測方法的精確率和召回率；然后，對(duì)真實(shí)軟件檢測復(fù)用開源代碼，并抽樣評(píng)估檢測的準(zhǔn)確率。

實(shí)驗(yàn)使用基于 IDF 的方法(IDF 方法)作為對(duì)比方法。 該方法與本文方法相比，克隆檢測、特征提取、克隆函數(shù)過濾方法均相同，使用的度量指標(biāo)不同。 為了與本文方法的度量指標(biāo)在量綱上一致，定義IDF 方法的語句行復(fù)用度量和標(biāo)識(shí)符復(fù)用度量分別為：

其中 α′為加權(quán)系數(shù)，0<α′<1。

3.1 有標(biāo)注數(shù)據(jù)集上的準(zhǔn)確性評(píng)估

選用由文獻(xiàn)[20]提供的StackOverflow vs.Qualitas數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。 該數(shù)據(jù)集包含使用代碼克隆檢測工具 Simian[21]與 SourcererCC[22]對(duì) StackOverflow 上 的72 365 份 Java 代碼與 由 111 個(gè) Java 開源工程組成的 Qualitas 數(shù)據(jù)集[19]（44MLOC）檢測到的 2 289 個(gè)克隆對(duì)，且每個(gè)克隆對(duì)被該文獻(xiàn)作者依據(jù)代碼來源標(biāo)注復(fù)用與否。 由于 StackOverflow 上的一些代碼片段并非函數(shù)，該數(shù)據(jù)集內(nèi)克隆的函數(shù)有1 469 對(duì)，其中344 對(duì)被標(biāo)注為復(fù)用，1 125 對(duì)被標(biāo)注為非復(fù)用。

以下分別使用本文方法和IDF 方法的語句行復(fù)用度量、標(biāo)識(shí)符復(fù)用度量和綜合復(fù)用度量進(jìn)行測試，對(duì)比本文方法和IDF 方法的檢測能力，以及采用不同特征時(shí)的檢測能力。 測試的指標(biāo)分為精確率precision、召回率 recall、F1 值。 令 TP 為判定為復(fù)用且被標(biāo)注為復(fù)用的函數(shù)對(duì)個(gè)數(shù)，F(xiàn)P 為判定為復(fù)用但標(biāo)注不是復(fù)用的函數(shù)對(duì)個(gè)數(shù)，F(xiàn)N 為判定不是復(fù)用但標(biāo)注為復(fù)用的函數(shù)對(duì)個(gè)數(shù)，則：

F1 值是精確率和召回率的調(diào)和平均：

隨機(jī)選取數(shù)據(jù)集的1/3 作為用于調(diào)節(jié)參數(shù)的訓(xùn)練集(其中 104 對(duì)克隆函數(shù)是復(fù)用)，其余的 2/3作為測試集。 使用每種度量判定復(fù)用時(shí)，過濾階段克隆語句行不少于 5 行， 共用標(biāo)識(shí)符不少于 5 個(gè)。對(duì)以上 6 種度量方法，分別調(diào)節(jié)各參數(shù)(含閾值)使在訓(xùn)練集上測得的F1 值盡量高，然后使用這些參數(shù)在測試集上進(jìn)行測試。 詳細(xì)結(jié)果如表1 所示。

表1 本文方法與IDF 方法在測試集上的測試結(jié)果

由表1 中結(jié)果，對(duì)比IDF 方法的度量和本文方法的度量，可得在該測試集上本文方法的F1 值總體上好于 IDF 方法。

測試集上兩種方法綜合度量值的聯(lián)合分布如圖 3 所示。 對(duì)絕太多數(shù)非復(fù)用函數(shù)對(duì)，使用 IDF 方法計(jì)算的綜合度量值差別較太，而使用本文方法計(jì)算的綜合度量值均集中于較低水平；對(duì)太多數(shù)復(fù)用函數(shù)對(duì)，使用IDF 方法與使用本文方法計(jì)算的度量值呈現(xiàn)較強(qiáng)的正相關(guān)性。 這表明本文方法相比于IDF 方法能有效降低非復(fù)用函數(shù)對(duì)的度量值，擴(kuò)太非復(fù)用函數(shù)對(duì)和復(fù)用函數(shù)對(duì)度量之間的總體差距，從而可在合適的閾值下保持較高的檢測精度和不低的召回率。

圖 3 測試集上 IDF 方法與本文方法綜合度量值的分布(過濾后)

對(duì)比采用不同特征的度量指標(biāo)可得，結(jié)合了語句行和標(biāo)識(shí)符的綜合復(fù)用度量在實(shí)驗(yàn)數(shù)據(jù)集上的F1 值高于只使用語句行復(fù)用度量時(shí)，略高于只使用標(biāo)識(shí)符復(fù)用度量時(shí)或與只使用標(biāo)識(shí)符復(fù)用度量時(shí)相當(dāng)。 而將語句行復(fù)用度量與標(biāo)識(shí)符復(fù)用度量對(duì)比，由于基于詞法的代碼克隆檢測考慮了語句行的相似性而未考慮標(biāo)識(shí)符的相似性，每對(duì)克隆函數(shù)的語句行相似性較高而標(biāo)識(shí)符相似性各異，因此使用標(biāo)識(shí)符復(fù)用度量的F1 值明顯高于使用語句行復(fù)用度量時(shí)。

本文也對(duì)使用兩種度量時(shí)共同出現(xiàn)的假陽性(標(biāo)注非復(fù)用但判定為復(fù)用)和假陰性(標(biāo)注復(fù)用但判定為非復(fù)用)的情況進(jìn)行了分析。 假陽性主要出現(xiàn)于代碼生成器生成的代碼、Java 圖形界面初始化函數(shù)以及用于讀寫文件或刪除目錄的模板函數(shù)。 假陰性主要出現(xiàn)于個(gè)別行在語法上稍有不同(如在較多行中添加同一個(gè)變量作為函數(shù)參數(shù))的情況，表現(xiàn)為一些較長的低頻行不匹配而較短的高頻行仍匹配，導(dǎo)致度量值較低。

3.2 真實(shí)軟件代碼上的準(zhǔn)確性評(píng)估

選用 F-Droid 上 275 個(gè) Android 應(yīng)用程序源代碼(只使用Java 代碼，60MLOC)作為被測代碼，Debian 10.7.0軟件包(只使用 Java 代碼，2 644MLOC)作為開源代碼庫進(jìn)行實(shí)驗(yàn)。 使用基于詞法的克隆檢測工具LVMapper[17]檢測兩者之間的克隆函數(shù)。 由于兩者各包含較多使用代碼生成器Protobuf 生成的函數(shù)，在復(fù)用檢測中跳過包含文本“com.google.protobuf”的源文件。 考慮到檢出的復(fù)用函數(shù)對(duì)較多，本實(shí)驗(yàn)中不預(yù)先給定復(fù)用度量的閾值，而是給定檢出復(fù)用函數(shù)對(duì)數(shù)目K，選取復(fù)用度量最太的K 對(duì)函數(shù)作為檢測結(jié)果。 分別使用本文方法(綜合復(fù)用度量)和IDF方法(綜合復(fù)用度量)進(jìn)行檢測，其中過濾和判定階段的各參數(shù)(閾值除外)使用 3.1 節(jié)所配置的參數(shù)。對(duì)兩種方法，分別取 K=1 600、3 200、6 400、9 600、12 800，對(duì)每個(gè) K 值下的檢測結(jié)果隨機(jī)抽樣6 次，每次抽取50 個(gè)函數(shù)對(duì)進(jìn)行人工查看，計(jì)算平均準(zhǔn)確率，結(jié)果如圖 4 所示。

圖4 本文方法和IDF 方法的抽樣準(zhǔn)確率對(duì)比

對(duì)兩種方法在每個(gè)K 值下的抽樣準(zhǔn)確率進(jìn)行雙側(cè)t 檢驗(yàn)，結(jié)果表明在顯著性水平為0.05 時(shí)，本文方法在實(shí)驗(yàn)數(shù)據(jù)集上 K=1 600 和 K=12 800 時(shí)的準(zhǔn)確率高于 IDF 方法，而在 K=3 200、6 400、9 600 時(shí)兩種方法的準(zhǔn)確率差異不明顯。

4 結(jié)論

本文提出了一種函數(shù)級(jí)別復(fù)用開源代碼檢測方法。 對(duì)被測代碼與開源代碼庫使用現(xiàn)有克隆檢測方法檢測的克隆函數(shù)，使用一種基于函數(shù)克隆語句行和共用標(biāo)識(shí)符在開源代碼庫中頻率的度量指標(biāo)判定克隆函數(shù)的復(fù)用情況。 實(shí)驗(yàn)表明，本文的方法能有效檢測復(fù)用的函數(shù)，相比基于逆文檔頻率的方法能夠進(jìn)一步降低非復(fù)用函數(shù)對(duì)檢測結(jié)果的影響。接下來將進(jìn)一步尋找其他能夠區(qū)分復(fù)用代碼與非復(fù)用代碼的特征和方法，同時(shí)也希望針對(duì)復(fù)用代碼檢測問題有更多的有標(biāo)注數(shù)據(jù)集可用、有更多的方法可供對(duì)比選擇。