[發明專利]一種基于序列結構的程序代碼聚類方法

有效

• 申請號: 201810083403.5
• 申請日: 2018-01-29
• 公開（公告）號: CN108399193B
• 公開（公告）日: 2022-03-04
• 發明（設計）人: 李海波;童俊成;孫映川;林湯權
• 申請（專利權）人: 華僑大學
• 主分類號: G06F16/35
• 分類號: G06F16/35
• 代理公司: 廈門市首創君合專利事務所有限公司 35204
• 代理人: 張松亭

1.一種基于序列結構的程序代碼聚類方法，其特征在于，包括：

步驟1，基于序列結構計算不同程序代碼間任意兩函數的相似度；

步驟2，根據所述兩函數的相似度計算任意兩程序代碼的相似度；

步驟3，根據所述兩程序代碼的相似度計算任意兩程序代碼的距離；由全部程序代碼兩兩之間的距離構建距離方陣；

步驟4，根據所述距離方陣使用凝聚型層次聚類算法對整個程序代碼樣本空間進行聚類分析；

所述任意兩程序代碼的距離的計算方式如下：

D_a,b＝(1-Sim_a,b)×100 (3)

其中，D_a,b表示程序代碼W_a與W_b的距離；

所述步驟4，包括：

步驟4.1，根據輸入的距離方陣求出語法格式有誤的代碼作為無效點，此類代碼在距離方陣中，與除自身外的其它代碼的距離全為100；

步驟4.2，根據輸入的距離方陣計算所有有效數據樣本的平均距離avgDis；

步驟4.3，開始采用均鏈接方法的層次聚類，均鏈接的方法是在每一次聚類過程中，將簇與簇之間平均距離最小的兩個簇歸為一簇，求出距離方陣中最小平均距離所在行列；

步驟4.4，設置聚類終止條件：判斷任意簇簇內距離是否大于avgDis，若否，直接進行步驟4.5；若是，判斷最小平均距離所在行列的兩個樣本所在的簇是否都滿足簇內元素數目小于等于2，若滿足則進行步驟4.5，否則計算此時這兩個簇的簇內距離方差和var與兩個簇所有元素間距離的方差newvar，若newvar的值大于var，則整個聚類算法終止，否則進行步驟4.5；

步驟4.5，將最小平均距離所在行列對應樣本所在的簇歸為一簇；

步驟4.6，求此時簇與簇之間平均距離，更新存儲著樣本間兩兩距離的距離方陣；

步驟4.7，重復步驟4.3到4.6步直到聚類終止。

2.根據權利要求1所述的基于序列結構的程序代碼聚類方法，其特征在于，所述步驟1，包括：

步驟1.1，去除程序代碼注釋；去除程序代碼中控制臺輸入輸出函數名、運算符號和變量類型；

步驟1.2，計算一個函數中每一個變量的相對位置數值序列；其中，變量的相對位置為同一變量在該函數中相鄰位置之差，由變量的相對位置有序形成的序列為變量的相對位置序列；

步驟1.3，基于Levenshtein距離，計算兩個函數間任意兩個字符的相似度；字符相似度公式如下所示：

Sim(S₁,S₂)＝1-Dis(S₁,S₂)/max(|S₁|,|S₂|) (1)

其中，(S₁,S₂)為兩變量相對位置序列，Dis(S₁,S₂)為兩序列的編輯距離，max(|S₁|,|S₂|)為兩序列間長度的最大值；

步驟1.4，在兩函數之間，求出使得相似度和最大的一組字符對；包括：

字符對對數為兩函數經步驟1.2處理后所含有字符數的較小值，且任意一個字符最多只能出現一次；

將所求出的最大相似度和除以字符對對數，獲得不同程序代碼間兩個函數的相似度Sim_f。

3.根據權利要求1所述的基于序列結構的程序代碼聚類方法，其特征在于，所述步驟2，包括：

假設程序代碼W_a包括F₁,F₂,...,F_m(1≤m)個函數塊，程序代碼W_b包括F₁,F₂,...,F_n(1≤n)個函數塊；則由步驟1求得兩程序代碼間任意兩函數的相似度；

步驟2.1，找出使得兩程序代碼之間函數相似度之和最大的一組函數對；求解過程規則如下：

獲得函數對對數N；其中，N為兩程序代碼中函數數目的較小值min(n,m)，任意兩對函數間不包括重復函數塊；

步驟2.2，計算兩份程序代碼的相似度；由步驟2.1可求得使兩程序代碼之間函數相似度之和最大的N對函數對，其相似度記為sim₁,sim₂,...,sim_N；求得每一對函數對中兩函數塊經步驟1.1處理后字符數目和為l₁,l₂,...,l_N；求得程序代碼W_a與程序代碼W_b經步驟1.1處理后字符總數目和為l_a,b，則由如下公式(2)可求得程序代碼W_a與W_b的相似度Sim_a,b: