基于Petri網(wǎng)可達分析的代碼搜索方法

丁雪兒 鈕 俊,2 張開樂 毛昕怡

1(寧波大學信息科學與工程學院 浙江寧波 315211)2(嵌入式系統(tǒng)與服務計算教育部重點實驗室(同濟大學) 上海 201804)

隨著計算機技術的發(fā)展和應用的逐漸深入，出現(xiàn)大量復雜大規(guī)模軟件系統(tǒng).軟件系統(tǒng)功能的不斷增強與完備等也正導致軟件復雜度急劇增加，給設計、開發(fā)和部署、運維等帶來新的挑戰(zhàn).通過代碼復用來構造軟件系統(tǒng)可提高軟件開發(fā)效率，且對已被成功使用的各種代碼的復用還可提高軟件質量、降低軟件風險[1].隨著開源運動的興起，互聯(lián)網(wǎng)上已聚集大量開放代碼可被學習和使用[2]；同時，企業(yè)組織內部也存在大量已被成功實踐的程序代碼[3]，為基于復用的高效率、低成本軟件開發(fā)提供了基礎和條件.

為了復用已有代碼，首先需對已有代碼進行有效組織管理，而快速、準確地搜索到期望代碼則是代碼復用的關鍵.當前已存在大量針對代碼復用的代碼搜索方法，從程序接口、語義、語法等角度去匹配候選代碼[4].其中基于語義的代碼搜索方法主要從用戶期望程序的功能或行為的角度去搜索代碼，能夠更為快速、準確地定位用戶所需代碼，近年來獲得學術界、工程界重點關注[5].代碼、語句的功能或行為一般體現(xiàn)為對輸入數(shù)據(jù)進行處理并獲得輸出結果，故基于輸入/輸出匹配的代碼搜索是一種典型的基于語義的代碼搜索方法.該方法[6-8]需要用戶用多組輸入輸出對的形式給出自己期望代碼的模糊功能描述，通過靜態(tài)分析或符號執(zhí)行等技術判斷候選代碼能否對給定輸入獲得期望輸出.2014年，美國愛荷華州立大學的Stolee等人[6]提出一種基于輸入/輸出值匹配的代碼搜索方法，該方法通過符號分析技術將順序結構程序代碼的語義轉換為邏輯表達式，同時將用戶提供的輸入/輸出值對轉換為語義約束，借助于可滿足性模理論(satisfiability modulo theories, SMT)求解器對二者的組合進行求解，進而判斷是否匹配.2016年，文獻[7]對該方法進行擴展，使其能夠支持對分支結構代碼的分析，并通過執(zhí)行路徑覆蓋度排序等手段解決多路徑代碼的匹配.該方法能在一定程度上提高搜索準確度和效率，但也存在一些局限性：1)由于計算過程的復雜性，部分程序代碼的輸出值難以直接給出；2)用戶只能提供有限的輸入/輸出值，且難以給出一些特殊的邊界值；3)該方法難以應對如連接數(shù)據(jù)庫等不具有顯式輸入/輸出值的代碼片段.

為了彌補上述不足，一種有效做法是用戶在以輸入/輸出對形式進行功能描述時，不必給出具體值，僅給出輸入輸出數(shù)據(jù)的類型即可，從而提出基于輸入/輸出類型匹配的代碼搜索方法[9-12].該類方法一般將代碼功能行為表示為數(shù)據(jù)對象之間的類型轉換圖，基于用戶提供的輸入/輸出類型，通過對圖進行遍歷以搜索從輸入類型到輸出類型的子圖，每個子圖所對應代碼序列則構成一個解.這種方法忽略具體數(shù)值，從數(shù)據(jù)類型出發(fā)，在較高語義層次搜索代碼，具有較好實用性，但已有工作也存在不足.首先，在查詢形式上已有方法僅能處理單個輸入類型，缺乏對多個輸入類型匹配問題的研究.其次，在類型分析過程中，對具有多個同類型輸入?yún)?shù)的情形缺乏分析.

針對上述問題，本文提出一種基于Petri網(wǎng)可達分析的代碼語義搜索方法，整個搜索過程如圖1所示.首先，借助程序分析技術解析候選代碼，構建候選代碼數(shù)據(jù)類型轉換過程的Petri網(wǎng)模型.其次，對于用戶提供輸入/輸出類型對，利用改進后的Petri網(wǎng)可達分析算法在Petri網(wǎng)上搜索從輸入類型到輸出類型的可達路徑，并返回該路徑所對應代碼片段.最后采用路徑長度和代碼復用率2個評價指標對返回結果進行重排序.注意本文以“函數(shù)”粒度源代碼作為分析對象.

本文的主要貢獻有2個方面：

1) 提出一種基于Petri網(wǎng)的代碼行為建模方法，以描述代碼對數(shù)據(jù)類型的加工變換過程.與已有工作中所采用的圖模型不同，本文基于Petri網(wǎng)對代碼行為過程作進一步解析，采用Petri網(wǎng)有向弧表示類型間的轉換，有向弧權重表示轉換過程中參數(shù)類型個數(shù)，能夠準確表達代碼語句及數(shù)據(jù)對象依賴關系.

2) 提出一種基于Petri網(wǎng)可達分析的代碼搜索方法.采用Petri網(wǎng)輸入/輸出標識表示用戶提供查詢中輸入/輸出數(shù)據(jù)對象的類型及個數(shù)，利用Petri網(wǎng)可達算法匹配由輸入標識到輸出標識的目標代碼，能夠有效地解決多種形式輸入/輸出類型的搜索問題；同時在基礎Petri網(wǎng)可達算法上引入誘發(fā)網(wǎng)分析，以提高搜索效率.

1 相關工作

目前，基于輸入/輸出匹配的代碼搜索方法大致分為2類：基于輸入/輸出測試值的代碼匹配方法[6-8]和基于輸入/輸出類型的代碼匹配方法[9-12].這2種方法的相同之處在于都是通過給定的輸入/輸出信息樣例從語義角度描述用戶搜索需求；區(qū)別則在于前者基于符號執(zhí)行技術挖掘數(shù)據(jù)對象值的變化過程，后者則一般使用圖模型描述數(shù)據(jù)對象類型的轉換過程.實踐表明，基于輸入/輸出測試值的代碼語義搜索方法能夠有效提高代碼搜索的準確性，而基于輸入/輸出類型的代碼匹配方法則適用更普遍的代碼搜索問題.

根據(jù)圖模型的不同，將基于輸入/輸出類型匹配的代碼搜索方法分為基于全局圖模型的方法和基于局部圖模型的方法.其中，前者對所有源代碼的行為過程進行統(tǒng)一建模，后者則對單個函數(shù)進行建模.為了更直觀地描述現(xiàn)有方法的各種圖模型，以圖2(a)所示的數(shù)據(jù)庫連接及表數(shù)據(jù)查詢代碼為例進行說明，圖2(b)給出代碼對應的類型變化過程.文獻[9]根據(jù)類庫和源代碼中的函數(shù)依賴關系構建全局圖模型，如圖3(a)所示，節(jié)點表示數(shù)據(jù)對象類型，邊表示實現(xiàn)類型間轉換的函數(shù)調用，采用最短路徑搜索算法求取輸入類型到輸出類型的函數(shù)序列.

文獻[10-12]根據(jù)特定單元源代碼中的函數(shù)依賴關系構建局部圖模型.這些局部圖模型具有各自的特點，文獻[10]的圖模型區(qū)別于文獻[9]的圖模型，增加了專門指向函數(shù)參數(shù)的邊，如圖3(b)所示；文獻[11]的圖模型將節(jié)點分為數(shù)據(jù)節(jié)點和動作節(jié)點，其中數(shù)據(jù)節(jié)點表示數(shù)據(jù)對象類型，動作節(jié)點表示函數(shù)調用，同時使用數(shù)據(jù)依賴邊和控制依賴邊描述數(shù)據(jù)節(jié)點以及動作節(jié)點間的關系，如圖3(c)所示；在文獻[12]的圖模型中，節(jié)點表示語句，邊表示語句次序，如圖3(d)所示.同時上述工作的搜索策略也具有差異.文獻[10,12]采用標準的圖搜索算法查找輸入類型到輸出類型的最短函數(shù)序列.文獻[11]則使用Grouminer工具挖掘常用的序列使用模式，然后匹配與查詢相似的使用模式.總的來看，局部圖模型能夠縮小問題空間，相較于全局圖模型有助于提升搜索的準確性，然而此類圖模型缺乏考慮函數(shù)間的數(shù)據(jù)依賴關系(參數(shù)類型個數(shù))，導致其描述的代碼行為不完整，準確率仍有提升空間.同時，已有研究無法滿足多個輸入類型查詢，適用性較低.

此外，文獻[13-17]基于數(shù)據(jù)對象的類型來進行代碼搜索，是與本文較為相關的工作.文獻[13]結合靜態(tài)分析將源代碼構建成有限狀態(tài)自動機，并基于自動機，通過對象類型查找語義相關的代碼片段.但是該方法的查詢形式不支持輸入/輸出類型，因此不能匹配滿足要求的程序代碼或序列.文獻[14]允許用戶使用盡可能準確的規(guī)格描述，包括關鍵字、類型、方法簽名、測試用例等，通過一組程序轉換規(guī)則將用戶要求的內容映射到候選方法或類.文獻[15-16]將類型、函數(shù)、接口、成員等代碼結構信息組織為有向圖結構，然后通過圖搜索算法查找與用戶提供的自然語言查詢相關的代碼圖.然而由于自然語言與代碼存在較大差異，難以準確地定位正確解.文獻[17]提出基于神經(jīng)網(wǎng)絡的深度學習方法，首先以向量形式語義關聯(lián)自然語言查詢與代碼，然后通過計算二者的余弦距離返回與查詢語義相近的代碼段.但是其訓練過程過于復雜和耗時，難以被推廣使用.

2 程序代碼的語義描述

2.1 基于類型轉換的代碼語義描述

程序代碼為由若干程序語句所構成的語句序列，每個語句代表1個執(zhí)行數(shù)據(jù)加工的操作，包括操作名以及被加工數(shù)據(jù)對象2個部分.這些操作的具體功能通常為讀取或修改對應的數(shù)據(jù)對象，其具體表現(xiàn)形式為基本運算符的運用或函數(shù)(或方法)調用，數(shù)據(jù)對象可能為常量、變量及數(shù)組、結構體、對象等擴展數(shù)據(jù)類型所對應數(shù)據(jù)實例.本文暫不考慮與程序結構、流程控制等有關結構語句、預編譯指令等不涉及顯式數(shù)據(jù)加工的語句.注意，為了方便描述，本文將融合多個數(shù)據(jù)加工的復雜語句劃分為原子操作后進行討論，比如，將語句“inta=b+c；”看作“算術求和”操作及“賦值”操作的復合.

定義1.數(shù)據(jù)對象.程序語句的數(shù)據(jù)對象定義為二元組(type,value)，其中type為數(shù)據(jù)類型，value為該數(shù)據(jù)對象的值.

定義2.原子操作.程序語句中的原子操作定義為三元組(c,I,o)，其中c為操作符，I為該操作輸入數(shù)據(jù)對象集合，o為輸出數(shù)據(jù)對象.

定義1,2中暫未考慮能夠攜帶多個輸出值的函數(shù)調用語句，比如C#語言中聲明為out類型的函數(shù)參數(shù).一般地，一段程序代碼的功能或行為由其數(shù)據(jù)加工序列體現(xiàn).具體來說，代碼中所有數(shù)據(jù)對象的值的變化過程對應著代碼功能，比如程序分析技術就主要通過符號化手段從值變化過程來模擬代碼行為[18].事實上，忽略數(shù)據(jù)對象的值的具體變化過程，單純從被加工數(shù)據(jù)對象的個數(shù)、類型的動態(tài)變化過程也能從某種程度上去考察代碼的功能行為[19-20].

本文用程序代碼的操作序列所體現(xiàn)的數(shù)據(jù)對象的個數(shù)及其類型的動態(tài)變化過程來刻畫代碼行為，以應對諸如連接數(shù)據(jù)庫、模擬HTTP響應等不具有顯式數(shù)據(jù)對象值的程序代碼.Petri網(wǎng)作為一種經(jīng)典的并發(fā)建模語言，能夠很好地刻畫并發(fā)系統(tǒng)的資源加工變化過程.本文將程序代碼中的數(shù)據(jù)對象看作資源，用Petri網(wǎng)來刻畫程序代碼對數(shù)據(jù)對象的動態(tài)加工過程，并借助Petri網(wǎng)對應的分析方法來解決代碼匹配問題.

2.2 Petri網(wǎng)基本概念

Petri網(wǎng)為由德國計算機科學家Carl Adam Petri于20世紀60年代提出的一種描述離散事件并發(fā)系統(tǒng)的形式化模型，具有嚴格數(shù)學定義和圖形表達能力.Petri網(wǎng)由庫所、變遷、有向弧3種基本元素組成，庫所和變遷由有向弧連接.采用Petri網(wǎng)對系統(tǒng)進行分析時，將庫所看作系統(tǒng)資源，變遷看作引起資源變化的事件或者操作[21].庫所能夠容納一定數(shù)量的令牌，表示所代表資源的數(shù)量.為了方便描述，先給出Petri網(wǎng)的形式定義及簡單實例.

定義3.Petri網(wǎng).Petri網(wǎng)為五元組PN=(P,T,F,L,W)，其中：

1)P={p1,p2,…,pm}是庫所的有限集合；

2)T={t1,t2,…,tn}是變遷的有限集合；

3)F?(P×T)∪(T×P)是連接庫所和變遷的有向弧集合；

4)L:P→是庫所集合上的標記函數(shù)，用于指定庫所P所對應的令牌數(shù)量；

5)W:F→+是F的權函數(shù)，表示令牌傳遞中的加權系數(shù)，W(f)表示W(wǎng)中弧f∈F所對應的分量.

在變遷的觸發(fā)過程中，各個庫所的令牌數(shù)量會發(fā)生變化.各個庫所對應的令牌數(shù)量所構成的向量稱為標識M,記初始標識為M0.在標識M中，庫所p所對應的分量記作M[p].

對?x∈P∪T，記*x{y∈P∪T|(y,x)∈F}和x*{y∈P∪T|(x,y)∈F}，稱*x和x*分別為x的前集或輸入集和后集或輸出集.如果?p∈*t:M[p]≥W(*t)時，稱變遷t在標識M下是使能的，記作M[t.如果狀態(tài)標識M下t是使能的，表示資源的數(shù)量滿足觸發(fā)條件，稱t可以觸發(fā).觸發(fā)后得到的后繼標識為M′，記作M[tM′，且有:

定義4.可達標識集.如果Petri網(wǎng)PN=(P,T,F,L,W)中存在t∈T，使M[tM′，稱M′是從M一步可達的.如果存在變遷序列t1,t2,…,tk和標識序列M1,M2,…,Mk，使得M0[t1M1[t2…Mk-1[tkMk，稱Mk是從M0多步可達的.從M0可達的標識集合稱為可達標識集，記作R(M0)，且滿足M0∈R(M0).

定義5.Petri網(wǎng)的可達圖.Petri網(wǎng)PN的可達圖為二元組GR(PN)=(S,E)，其中S=R(M0)是節(jié)點集，代表Petri網(wǎng)PN中所有的可達標識或者狀態(tài)；E={(M,t,M′)|M,M′∈R(M0),M[tM′}是有向弧集，代表不同可達狀態(tài)之間的使能變遷.

例1.Petri網(wǎng)是一種直觀的圖形化建模工具，一般用實心矩形“”表示變遷，庫所用圓圈“○”表示，令牌用實心圓點“?”表示.為便于理解，以圖4為例給出Petri網(wǎng)的數(shù)學形式化定義的圖形表示.圖4(a)為1個簡單Petri網(wǎng)，其初始標識為M0=[p1|→2,p2|→0,p3|→1,p4|→0]，記作向量(2,0,1,0)T，表示庫所p1的令牌數(shù)量為2，庫所p3的令牌數(shù)量為1，其余為0；變遷t∈T的前置集為:*t1={p1}，*t2={p2}等；?p∈*t1:M0[p]≥W(*t1)=2，故M0[t1，記作M0[t1M1，其中M1=(0,1,1,0)T為可達標識.圖4(b)為該Petri網(wǎng)的狀態(tài)可達圖.

3 基于Petri網(wǎng)的代碼行為建模

由2.1節(jié)可知，程序語句一般為執(zhí)行數(shù)據(jù)加工的操作組成，而程序代碼的功能行為則表現(xiàn)為數(shù)據(jù)對象類型及個數(shù)的轉換過程.本文將操作的數(shù)據(jù)對象看作資源，程序操作則為導致資源流動的事件.根據(jù)定義3的Petri網(wǎng)定義，數(shù)據(jù)對象的類型和語句可以通過庫所和變遷表示，數(shù)據(jù)對象的個數(shù)可以通過有向弧權重表示.基于Petri網(wǎng)的代碼行為過程描述為：通過Petri網(wǎng)中有向弧的指向表示語句中數(shù)據(jù)對象間的類型轉換關系，通過有向弧的權重表示語句中不同類型數(shù)據(jù)對象的個數(shù).本節(jié)給出一種基于Petri網(wǎng)的代碼行為過程建模方法.首先闡明基于Petri網(wǎng)的代碼行為建模機制，制定Petri網(wǎng)元素與代碼元素之間的對應關系；其次基于該對應關系，利用靜態(tài)分析技術對程序代碼進行分析處理，完成代碼到Petri網(wǎng)的轉換.

3.1 基于Petri網(wǎng)的代碼行為模型

單個程序語句包括有關操作以及被加工的輸入數(shù)據(jù)對象集和加工后所生成的輸出數(shù)據(jù)對象.比如，函數(shù)調用語句由函數(shù)名、調用該函數(shù)的主動調用數(shù)據(jù)對象(caller)、作為參數(shù)的被調用數(shù)據(jù)對象(callee)以及返回數(shù)據(jù)對象組成，其中函數(shù)名為操作符，調用和被調用數(shù)據(jù)對象均為輸入數(shù)據(jù)對象，返回數(shù)據(jù)對象為輸出數(shù)據(jù)對象.

定義6.程序語句為三元組(Sc,Si,O)，其中Sc代表操作符集合，Si代表輸入數(shù)據(jù)對象集合，O代表輸出數(shù)據(jù)對象.對于?c∈Sc，語句輸入數(shù)據(jù)對象I?Si對應于操作c輸入數(shù)據(jù)對象，語句輸出數(shù)據(jù)對象o對應于優(yōu)先級最低操作c的輸出數(shù)據(jù)對象.

比如，語句“inta=b+c；”包括算術、賦值2個運算符，其中算術運算符優(yōu)先級高于賦值運算符，顯然整個語句功能應體現(xiàn)為賦值運算的最終結果，故將變量a作為最終輸出對象.數(shù)據(jù)對象個數(shù)及類型變化過程可簡單概括為：通過語句對數(shù)據(jù)對象進行加工處理，將一定數(shù)量的特定類型的輸入數(shù)據(jù)對象轉換為特定類型的輸出數(shù)據(jù)對象.該過程在Petri網(wǎng)中可描述為：通過語句變遷的輸入/輸出弧的指向及權重，表示語句中輸入數(shù)據(jù)對象到輸出對象的轉換過程，其中弧由輸入數(shù)據(jù)對象類型指向輸出數(shù)據(jù)對象類型，輸入、輸出弧的權重分別表示轉換過程需要消耗的輸入數(shù)據(jù)對象、生成的輸出數(shù)據(jù)對象個數(shù).

對于語句s∈S，用ts表示該語句變遷，對于其輸入數(shù)據(jù)對象類型i∈Si，用pi表示輸入數(shù)據(jù)對象類型庫所，對于其輸出數(shù)據(jù)對象類型o，用po表示輸出數(shù)據(jù)對象類型庫所.為了方便描述，連接語句變遷與輸入數(shù)據(jù)對象類型庫所的輸入弧表示為(pi,ts)，輸入弧權重表示為W(pi,ts)，即為語句s中類型為i的輸入數(shù)據(jù)對象個數(shù).連接語句變遷與輸出數(shù)據(jù)對象類型的輸出弧表示為(ts,po)，輸出弧權重表示為W(ts,po)，且W(ts,po)=1.

在Petri網(wǎng)中用輸入數(shù)據(jù)對象的消耗和輸出數(shù)據(jù)對象的產(chǎn)生來建模程序語句，容易出現(xiàn)代碼語義描述的不一致.比如，對于需要執(zhí)行多次調用的某個主動對象x，當x執(zhí)行一次方法調用后，在對應Petri網(wǎng)的語句描述上消耗了該數(shù)據(jù)對象x，從而導致不能準確描述將來其他涉及x調用的程序語句.因此，對于被多次重復使用的數(shù)據(jù)對象，用Y表示這類數(shù)據(jù)對象的類型.針對這類數(shù)據(jù)對象y∈Y，本文引入一個特殊的復制變遷Cy.連接復制變遷和數(shù)據(jù)對象類型庫所的輸入弧和輸出弧分別表示為(py,Cy)和(Cy,py)，其中py表示類型庫所.輸入弧權重表示為W(py,Cy)，且W(py,Cy)=1.輸出弧權重表示為W(Cy,py)，即為該類型的數(shù)據(jù)對象在程序代碼中被重復使用的次數(shù).本文給出程序代碼元素與Petri網(wǎng)元素之間的對應關系，如表1所示:

此外，對于沒有明顯輸入或者輸出類型的語句，為了充分保留語句中的語義信息，用void來表示這類語句的輸入或者輸出數(shù)據(jù)對象類型，比如new語句的輸入類型、close語句的輸出類型等.

3.2 程序代碼的Petri網(wǎng)構建過程

為了匹配程序代碼，首先需要將所有候選代碼轉換成對應Petri網(wǎng)形式.代碼片段到Petri網(wǎng)的轉換過程如圖5所示.本文以Java語言編寫的程序代碼為研究對象，首先借助已有代碼分析工具解析候選代碼片段，從而提取各個代碼元素，如語句、操作、參數(shù)個數(shù)和類型等.其次基于3.1節(jié)所述代碼元素到Petri網(wǎng)元素之間的映射關系，將候選代碼構建成對應Petri網(wǎng)模型，存儲于圖數(shù)據(jù)庫中，為后期代碼匹配做準備.

為了便于與Java代碼的無縫銜接及效率因素考慮，本文選擇輕量級的Eclipse JDT代碼解析組件ASTParser.該組件可以快速將Java語言程序代碼解析成基于文檔對象模型(document object model,DOM)結構的抽象語法樹表示，代碼中的每個元素對應于抽象語法樹上某個節(jié)點.采用深度優(yōu)先搜索策略并借助相關API便可獲取代碼元素如語句、操作、參數(shù)等以及彼此之間的上下文語義關系，即特定語句、操作、參數(shù)之間的對應，其中重復對象集的確定是通過判斷抽象語法樹上不同操作節(jié)點是否具有相同的輸入變量.在此基礎上，利用3.1節(jié)描述的代碼元素與Petri網(wǎng)元素之間的映射關系，完成候選代碼到Petri網(wǎng)模型的轉換，詳細步驟見算法1.

① https://neo4j.com/

算法1.Petri網(wǎng)構建算法constructPN.

輸入：代碼片段code_Func;

輸出：Petri網(wǎng)PN.

①PN←{P,T,F,W,L};

②P←?,T←?,F←?,W←?,L←?;

/*初始化Petri網(wǎng)*/

③S←parseStatement(code_Func);

/*將代碼片段中的語句序列放入到語句集S中*/

④ whileS≠? do

⑤ 選擇s∈S;

⑥S←S-{s};

⑦T←T∪{s};/*將語句添加到Petri網(wǎng)的變遷集中*/

⑧T_in←parseInputType(s);

/*將語句的輸入數(shù)據(jù)對象類型放入集合T_in中*/

⑨ whileT_in≠? do

⑩ 選擇t∈T_in;/*選擇集合T_in中1個輸入類型*/

/*解析語句中該類型輸入數(shù)據(jù)對象的個數(shù)*/

/*解析語句中該類型輸出數(shù)據(jù)對象的個數(shù)*/

需要指出，行③函數(shù)parseStatement()用以分析并確定代碼操作，包括程序語句以及本文針對程序代碼中重復使用對象設置的復制變遷；行⑧函數(shù)parseInputType()和行函數(shù)parseOutputType()用以分析某個具體操作的輸入對象和輸出對象，包括語句操作的輸入類型和輸出類型，以及復制變遷對應的重復使用對象類型；行函數(shù)parseInputNum()和行函數(shù)parseOutputNum()用以分析某個具體輸入對象和輸出對象在其操作語句中的數(shù)量，包括特定語句操作的某個輸入類型個數(shù)和輸出類型個數(shù)，以及特定復制變遷對應重復使用對象類型輸入個數(shù)和輸出個數(shù)(對象重復使用次數(shù)).

程序代碼所對應的Petri網(wǎng)描述具有明顯的網(wǎng)式結構化特征.為了提高后期代碼匹配效率，本文采用高效的Neo4j①來存儲程序代碼所對應的Petri網(wǎng)信息.Neo4j具有與Petri網(wǎng)類似的數(shù)據(jù)組織方式和結構，即通過節(jié)點和邊來構成圖，并提供類似SQL的語言Cypher以方便用戶執(zhí)行查詢、編輯等操作.

例2.圖6中為數(shù)據(jù)庫連接的Java代碼，該代碼對應Petri網(wǎng)如圖7所示.為了方便描述，將類型標記于對應庫所，語句標記于對應變遷，其中Class，String類型庫所為該代碼片段的起始庫所，void類型庫所為終止庫所，其余類型庫所為類型轉換過程中的過渡或中間庫所.由庫所指向變遷的輸入弧代表類型庫所是語句變遷的輸入數(shù)據(jù)對象，輸入弧權重代表該類型的輸入數(shù)據(jù)對象個數(shù).由變遷指向庫所的輸出弧代表類型庫所是語句變遷的輸出數(shù)據(jù)對象，輸出弧權重代表該類型的輸出數(shù)據(jù)對象個數(shù).此外，每個重復對象存在其相應的克隆變遷，由重復對象庫所指向克隆變遷的輸入弧權重為1，由克隆變遷指向重復對象庫所的輸出弧權重為對象重復使用的次數(shù).比如，在函數(shù)getConnection調用語句中，輸入數(shù)據(jù)對象包括3個類型為String的參數(shù)以及1個類型為DriverManager的調用者，因此輸入弧由String庫所和DriverManager庫所指向語句變遷，且輸入弧權重分別為3和1；輸出數(shù)據(jù)對象是1個類型為Connection的返回者，因此輸出弧由語句變遷指向Connection庫所，且輸出弧權重為1.Connection對象在程序片段中被重復使用2次，因此Connection庫所處存在Cc克隆變遷，且Cc輸入弧權重為1，輸出弧權重為2.出于空間的考慮，在圖6中采用函數(shù)名來表示函數(shù)調用語句.需要指出，示例中的異常處理及迭代僅作數(shù)據(jù)流分析.

Table 1 Mapping of Program Code Elements to Petri Net Elements

Table 2 Steps of Reachability Graph Generation Algorithm

Table 3 Experimental Query Test Set

Table 4 Experimental Results

try{Class.forName(dbClass);

Connectionconnection=DriverManager.getConnection(dbUrl,username,password);

Statementstatement=connection.createStatement();

ResultSetresultSet=statement.executeQuery(query);

while(resultSet.next()) StringtableName=resultSet.getString(1);

connection.close();}

catch(ClassNotFoundExceptione){e.printStackTrace();}}

Fig. 1 Overview of code search method based on the reachability analysis of Petri Nets

Fig. 2 Code example and its type representation

Fig. 3 Example of graph models in related work

Fig. 4 Formal definition and graphical representation of Petri Net

Fig. 5 Flow chart of Petri Nets construction process

圖6 “Java數(shù)據(jù)庫連接”代碼示例

Fig. 7 Petri Net based on the example code of Fig.6

Fig. 8 Flow chart of method for matching code based on the reachability analysis of Petri Nets

Fig. 9 Induced Net of Petri Net in Fig. 7

Fig. 10 P@5 of each question under different methods

Fig. 11 P@10 of each question under different methods

Fig. 12 Trend diagram of Petri Nets construction time and code scale

Fig. 13 Influence of cloned transition on search precision

Fig. 14 Influence of reachability graph pruning on search time

4 基于Petri網(wǎng)可達分析的代碼匹配方法

本節(jié)引入一種基于Petri網(wǎng)可達分析的代碼匹配方法.該方法根據(jù)用戶提供的輸入數(shù)據(jù)對象個數(shù)、類型信息及期望輸出數(shù)據(jù)對象類型，從候選代碼所對應Petri網(wǎng)模型中搜索存在功能行為滿足將輸入類型轉換為輸出類型的代碼片段.整個過程分為3個階段，如圖8所示.首先，在各個候選代碼Petri網(wǎng)中，根據(jù)輸入、輸出數(shù)據(jù)對象信息在候選Petri網(wǎng)中確定初始標識M0和目標標識M*；然后基于初始標識M0，對Petri網(wǎng)進行可達分析，生成反映標識轉換的可達圖；最后通過分析候選Petri網(wǎng)可達圖中是否存在目標標識M*來判斷Petri網(wǎng)對應的程序代碼是否為用戶所期待代碼片段.

4.1 確定初始標識與目標標識

為了分析Petri網(wǎng)的可達性，首先需借助用戶提供的輸入、輸出數(shù)據(jù)對象信息確定Petri網(wǎng)PN=(P,T,F,L,W)的初始標識M0和目標標識M*.

定義7.查詢類型對.查詢類型對為二元組T=(I,o)，其中I代表輸入數(shù)據(jù)對象的數(shù)據(jù)類型集，o代表輸出數(shù)據(jù)對象的數(shù)據(jù)類型.

初始標識是指T中輸入類型在Petri網(wǎng)對應庫所的等量令牌數(shù)，用來表示需要消耗的數(shù)據(jù)對象資源.

定義8.初始標識.設在查詢類型對T中，類型為i∈I的輸入數(shù)據(jù)對象個數(shù)為n，如果在Petri網(wǎng)中存在庫所p∈P的標記為i，則M0[p]=n，M0[void]=1，對于其他類型p′∈P，M0[p′]=0.

考慮到T中通常不包含void輸入類型，為了保證無明顯輸入類型程序語句的匹配過程不受影響，因此設置void類型庫所的令牌數(shù)為1.目標標識是指T中輸出類型在Petri網(wǎng)對應庫所中的等量令牌數(shù)，用來表示需要生成的數(shù)據(jù)對象資源.

定義9.目標標識.對于查詢類型對T中輸出數(shù)據(jù)對象o，如果在Petri網(wǎng)中存在庫所p∈P的標記為o，則M*[p]=1，M*[void]≥0，對于其他類型p′∈P，M*[p′]=0.

void庫所令牌數(shù)可能大于0的原因為：部分代碼包含1個或多個無明顯輸出類型的語句，導致生成1個或多個void令牌；部分代碼僅包含明顯輸入類型的語句，導致初始標識void庫所中的令牌沒有被消耗.

4.2 Petri網(wǎng)可達圖生成與剪枝

為了判斷Petri網(wǎng)中是否存在由初始標識可達的目標標識，需對Petri網(wǎng)進行可達分析，生成所有標識間可達關系圖.對于較為復雜的Petri網(wǎng)，為了提高分析效率，還需進行可達圖修剪，即去除不影響分析結論的多余庫所或變遷.

4.2.1 可達圖的生成

可達性分析是研究Petri網(wǎng)動態(tài)行為的重要手段[22].對已確定初始、目標標識的Petri網(wǎng)PN，其可達圖生成過程如算法2所示.

算法2.Petri網(wǎng)可達圖生成算法reachGraph.

輸入：Petri網(wǎng)PN、初始標識M0、輸出類型p*;

輸出：PN的可達圖GR*.

①GR*←(N,E);

②N←{M0};E←?;/*初始化可達圖*/

③Φ←{M0};

④ whileΦ≠? do/*當未處理標識集不為空時*/

⑤ 選擇M∈Φ;/*選擇未處理標識集中的1個標識*/

⑥Φ←Φ-{M};

⑦ for所有T∈enabled(M) do/*狀態(tài)標識M下所有使能的變遷T*/

⑧ (M′,p)←fire(M,T);/*計算M的后繼標識M′以及變遷T的輸出庫所p*/

⑨ ifpathExists(p,p*,α(PN)) then

/*判斷α(PN)中是否存在p到p*的路徑*/

⑩ Continue；

例3.以圖4為例，假設輸出類型為p4，表2說明Petri網(wǎng)可達圖生成算法的執(zhí)行過程.

4.2.2 可達圖的修剪

隨著代碼規(guī)模的擴大，狀態(tài)空間的組合爆炸將使可達性分析變得非常困難，基于Petri網(wǎng)的可達分析的復雜度呈指數(shù)增加[23].為了應對可能的狀態(tài)爆炸問題或提高分析效率，本文通過分析Petri網(wǎng)對應有向網(wǎng)中的路徑對可達圖GR(PN)進行剪枝，使可達圖GR(PN)得到化簡，同時保證化簡后的可達圖GR*也足以反映給定輸入/輸出類型轉換過程.

如果在PN中沒有從某類型庫所到輸出類型庫所的路徑，則不需分析從該類型庫所到輸出類型庫所的路徑是否可達，即沒有必要對該類型庫所分配非零數(shù)量的令牌.本文基于這個觀察來修剪GR(PN)冗余節(jié)點.為了分析PN類型庫所間的路徑存在的問題，本文定義誘發(fā)網(wǎng)α(PN)的概念，α(PN)忽略變遷及有向弧權重，僅用無權有向弧表示類型庫所間可達關系.

定義10.誘發(fā)網(wǎng).誘發(fā)網(wǎng)α(PN)是由Petri網(wǎng)PN=(P,T,F,L,W)誘發(fā)的表示為(V,E′)的有向網(wǎng)，其中V=P，(P,P′)∈E′，并且存在變遷t∈T使得(P,t)∈E，(t,P′)∈E.

例4.圖7中Petri網(wǎng)的誘發(fā)網(wǎng)α(PN)如圖9所示.出于空間考慮，長單詞用縮寫表示.

命題1.令α(PN)為Petri網(wǎng)PN的誘發(fā)網(wǎng)，設α(PN)中沒有從某庫所p到目標庫所p*的路徑，設M為PN中庫所p內令牌數(shù)大于0的標識，M*為庫所p*內令牌數(shù)為1的目標標識，則GR(PN)中沒有從M到M*的路徑.

定理1.約簡模型中標識可達性是一致的.

證明.設PN的化簡前可達圖GR(PN)=(SM,SL)，化簡后可達圖GR*(PN)=(SM*,SL*)，其中SM和SM*表示可達標識，SL和SL*表示連接相鄰標識的有向邊.GR*(PN)滿足：

1) ?M∈SM，其中M[P]>0，P={p1,p2,…,pn}，若?p∈P，α(PN)中都存在p到p*的路徑，則M∈SM*.

2) ?M,M′∈SM，M,M′∈SM*，若?l(M,t,M′)∈SL，則l(M,t,M′)∈SL*.

上述描述表明GR*(PN)保留GR(PN)中所有可能到達目標標識M*(M*[p*]=1)的標識M及M→M*的路徑，即約簡模型中標識可達性是一致的.

證畢.

4.3 基于可達圖的代碼匹配算法

Petri網(wǎng)可達圖反映了Petri網(wǎng)在初始標識M0下可達的標識空間.因此對于生成的可達圖GR*，若GR*存在目標標識M*，則Petri網(wǎng)上存在從M0到M*的可達路徑，表明該Petri網(wǎng)匹配.算法3描述了Petri網(wǎng)匹配的整個過程：首先初始化匹配Petri網(wǎng)集合、搜索次數(shù)(行①②)；其次，依次獲取Petri網(wǎng)進行分析，生成其對應的可達圖(行③～⑤)；然后，判斷可達圖是否存在目標標識，若存在，則將對應Petri網(wǎng)添加到匹配Petri網(wǎng)集(行⑥～⑧)；最后，當所有Petri網(wǎng)分析完畢，則循環(huán)結束，返回匹配Petri網(wǎng)集合(行⑨⑩).對于返回的匹配Petri網(wǎng)集，其對應的代碼片段存在將輸入類型轉換為輸出類型的語句序列，這些代碼片段匹配，將其納入候選代碼片段集合.

算法3.Petri網(wǎng)匹配算法matchPN.

輸入：待搜索的Petri網(wǎng)庫PN_database、輸出類型p*、初始標識M0、目標標識M*、搜索最大次數(shù)(Petri網(wǎng)個數(shù))n_max;

輸出：匹配Petri網(wǎng)集合Ok_PNs.

①Ok_PNs←?;

②searchCount←0;

③ while(one_PN←nextFile(PN_database) andsearchCount≤n_max) do /*獲取Petri網(wǎng)*/

④searchCount←searchCount+1;

⑤GR*←reachGraph(one_PN,M0,p*);

/*生成Petri網(wǎng)可達圖*/

⑦Ok_PNs←Ok_PNs∪{one_PN};

/*若存在，Petri網(wǎng)匹配成功，添加到匹配Petri網(wǎng)集*/

⑧ end if

⑨ end while

⑩ returnOk_PNs.

4.4 候選代碼排序

對于候選代碼片段集合，本文使用2種代碼質量評價指標對代碼片段進行排序，幫助程序員快速識別所需的代碼片段.

基于程序員經(jīng)常傾向于使用較短序列而不是較長序列來實現(xiàn)其任務的現(xiàn)象[9-10,24]，本文采用序列長度作為評價代碼質量的指標，越短的序列優(yōu)先級越高.本文將代碼片段中功能序列的長度作為序列長度，功能序列指將輸入類型轉換為輸出類型的方法序列.

本文還采用代碼復用率作為評價代碼質量的指標.在許多代碼搜索工作如PARSEWeb[10],DERECS[25]中都用到了復用率對結果進行排序，其基本考慮是代碼的復用率(代碼片段在軟件開發(fā)過程中重復使用的頻率)越高，參考價值越高，但計算方式各有差異.本文考慮相似代碼片段在候選代碼庫中出現(xiàn)的頻率.采用已有代碼克隆檢測方法CCFinderSW[26]來識別候選代碼庫中的相似代碼，并將相似代碼聚成一類，計算每一類集合中代碼段個數(shù)作為此類代碼段的復用率.CCFinderSW的源代碼可以在GitHub上找到，本文用Java語言重新實現(xiàn)了此算法.

5 實驗以及分析

為了驗證本文所提出方法的有效性，本文進行了2個實驗.在第1個實驗中，我們驗證了本方法的有效性，即能否解決多種形式的類型轉換問題，并與其他檢索方法的準確率進行對比；第2個實驗則討論了本方法中涉及的技術點對搜索效率的影響.

5.1 實驗建立

5.1.1 實驗準備

為了確保所收集源代碼的真實性和可靠性，本文選擇從軟件項目托管平臺GitHub上收集源代碼.根據(jù)托管項目的Most Stars排序，本文選擇了200個用戶評價較高的Java語言開源項目，將項目以函數(shù)為粒度進行切分，得到函數(shù)級代碼片段189 442個.

為了構建客觀的用戶真實查詢測試集，我們從Stack Overflow中找到帶有Java標簽的問答對，并選取票數(shù)為正、答案中含有代碼片段的熱門的20個問題，同時提取答案代碼示例中的輸入/輸出類型作為代碼搜索工具的查詢輸入如表3所示.需要指出，我們將數(shù)組視為特殊的數(shù)據(jù)對象，其類型為元素類型.

5.1.2 評估指標

為了評價代碼搜索的準確度或效率，本文采用P@n[27-28]，MAP(mean average precision)[7,29]，MRR(mean reciprocal rank)[7]作為評價指標.P@n表示返回前n個結果的準確率，計算公式為

(1)

其中，n表示返回的前n個結果，relk表示第k個結果的相關性，如果相關，relk=1，否則relk=0.MAP表示平均準確率，該指標對出現(xiàn)在列表中較高位置的相關結果給予較高的權重，計算公式為

(2)

(3)

其中，AveP表示單個查詢的準確率，num表示相關結果的個數(shù)，P(k)表示對于查詢Qi相關結果列表中排名為k的權重，例如結果列表共有2個相關代碼段位于排名1和3，則P(1)=1，P(3)=0.67.MRR表示第1個相關結果排名的倒數(shù)，計算公式為

(4)

其中，ranki表示對于查詢Qi第1個相關結果的排名.

5.1.3 比較對象

為了檢測搜索方法的有效性，我們與2種典型的代碼檢索方法進行對比.第1種為基于文本匹配的方法.該方法源于大多源代碼搜索引擎，通過相似度計算模型[30]計算查詢與代碼片段的文本相似度.第2種為基于類型匹配的方法.該檢索方法只考慮有向圖中是否存在一條路徑以輸入/輸出類型作為起點和終點節(jié)點，不考慮路徑的可達問題.

5.2 實驗結果及分析

5.2.1 搜索結果對比分析

針對表3中的20個查詢問題，本文對比了5.1.3節(jié)中2種方法檢索結果的P@5，P@10評價指標，如圖10和圖11所示.

從圖10和圖11中可以看出，相比于基于輸入/輸出值的方法，本方法適用于更普遍的代碼搜索問題，例如較好地解決了無法用具體值描述的查詢4，6，7等編程任務.同時，本方法還能夠有效地解決多種形式的類型轉換問題，在已有類型匹配工作已解決的單個輸入類型轉換的基礎上，解決了多個輸入類型轉換.為了能夠更直觀地驗證本方法的有效性，針對單個輸入/輸出類型的查詢，對比了2種方法檢索結果的MAP和MRR這2種評價指標，實驗結果如表4所示：

從表4中可以看出，本方法的搜索準確率要優(yōu)于基于文本匹配和已有類型匹配的方法.基于文本匹配的方法獲得了最低的準確率，表明僅利用文本相似性解決代碼匹配問題，而忽略代碼的語義信息，難以獲得理想的結果.本文結合靜態(tài)分析技術挖掘代碼的行為過程，并采用Petri網(wǎng)將其整合起來，添加到搜索中，使檢索的準確性得到了顯著提升.已有類型匹配的方法在搜索過程中只是遍歷路徑的存在問題，而本文在此基礎上將參數(shù)類型個數(shù)作為新的約束條件，利用Petri網(wǎng)可達分析挖掘更全面的代碼行為，從而匹配到更多相關的代碼片段.

5.2.2 Petri網(wǎng)構造過程分析

設單個代碼片段中操作數(shù)為m，每個操作的輸入數(shù)據(jù)對象類型數(shù)為n，則構建代碼片段Petri網(wǎng)的時間復雜度為O(m×n+m).本文設計實驗分別從參數(shù)、語句、函數(shù)調用數(shù)目及重復使用對象集4個方面對Petri網(wǎng)的構造時長進行考察，如圖12所示.實驗結果表明，Petri網(wǎng)的構造時間與語句數(shù)量、函數(shù)調用數(shù)量及重復使用對象數(shù)量均成正比關系，與參數(shù)數(shù)量大約為正比關系(除參數(shù)為0的情況).原因分析為：由時間復雜度可知，構造時長取決于代碼操作與輸入數(shù)據(jù)對象類型，且構造時長隨二者數(shù)量的增加而增加，其中代碼操作涉及代碼語句及本文針對重復對象集設置的相應復制變遷；從語句內部分析，運算符操作通常對同類型數(shù)據(jù)對象加工，而函數(shù)調用往往需要處理多個不同類型的輸入數(shù)據(jù)對象，因此代碼中函數(shù)調用數(shù)量越多，涉及輸入數(shù)據(jù)對象類型越復雜，導致構造時長增加；此外，在一般情況下參數(shù)數(shù)量與語句輸入數(shù)據(jù)對象存在一定關聯(lián)，參數(shù)數(shù)量越多，語句輸入數(shù)據(jù)對象越多，但當參數(shù)為0時，輸入數(shù)據(jù)對象與參數(shù)無直接關系，比如圖6代碼示例.

5.2.3 技術點分析

1) 復制變遷

為了表明在Petri網(wǎng)構建過程中增加復制變遷的重要性，本文針對表3的查詢集進行檢索實驗，如圖13所示.從圖13中可知，復制變遷對提高搜索準確率起關鍵作用.原因分析為：傳統(tǒng)Petri網(wǎng)模型難以蘊含程序片段中數(shù)據(jù)對象的重復使用過程，導致Petri網(wǎng)可達分析過程中重復使用對象的資源數(shù)不夠，對應操作變遷無法觸發(fā)，可達圖生成不完整，進而影響搜索匹配結果.

2) 可達圖修剪

圖14說明了分析Petri網(wǎng)可達時設置可達圖修剪的必要性.總的來看，在標準可達圖生成算法的基礎上，增加可達圖修剪的操作能夠明顯減少搜索時間.

6 總結及未來工作

為了幫助程序員更好地檢索以及復用已有代碼，本文提出了一種基于Petri網(wǎng)可達分析的代碼搜索方法.該方法基于已有代碼庫，結合靜態(tài)分析技術分析、提取代碼元素，構建代碼的Petri網(wǎng)模型；根據(jù)給定輸入/輸出類型，通過Petri網(wǎng)可達分析匹配將輸入類型轉換為輸出類型的代碼片段，并采用序列長度和復用率代碼質量評價指標對結果進行排序.使用真實的查詢測試集，驗證了本文方法的有效性.

在未來的工作中，我們將針對搜索結果的多種情況，完善該方法.例如對于返回代碼段過少的問題，采取對查詢進行一定程度的放松與收縮(如父類、子類替換)；對于返回代碼段過多的問題，采用測試用例(具體的輸入/輸出值)進一步篩選代碼段.此外，我們將進一步全方面探討代碼Petri網(wǎng)模型的可覆蓋性、安全性、結構有界性等行為性質，增強代碼Petri網(wǎng)模型的完備性.

作者貢獻聲明：丁雪兒負責論文思路的提出、論文寫作、論文算法和論文實驗；鈕俊負責論文思路的把關、論文寫作和實驗監(jiān)督；張開樂負責數(shù)據(jù)收集和論文寫作完善；毛欣怡負責結果驗證和論文寫作完善.