程序算法識別研究綜述

摘 要：了解程序代碼所描述的算法，能幫助程序員理解程序從而開展各項軟件工程任務。由于人工理解程序算法要求程序員具備豐富的專業知識并且十分耗時耗力，程序算法識別任務以實現程序算法理解的自動化為主要研究目標，與人工理解相比更為高效、準確。系統整理了程序算法識別領域的相關工作。首先，梳理程序算法識別等相關概念，簡介基于知識表示與基于信息檢索的方法；其次，將基于代碼表征的方法劃分為基于序列、基于樹和基于圖等方法展開詳細闡述，并對三類方法作出小結與對比；最后，介紹程序算法識別任務的相關應用領域，分析該任務中尚存的問題并對未來的發展作出展望。

關鍵詞：程序算法識別； 程序理解； 程序代碼表征

中圖分類號：TP311 文獻標志碼：A 文章編號：1001-3695（2024）07-003-1940-11

doi：10.19734/j.issn.1001-3695.2023.09.0504

Review of research on program algorithm recognition

Abstract：Understanding the algorithms described in program code can help programmers grasp the program aUUoek8BNZH30HsVhpI0HLw==nd carry out various software engineering tasks. Because manual understanding of program algorithms requires programmers to have rich professional knowledge and is time-consuming and labor-intensive， the main research goal of program algorithm recognition is to achieve automation of program algorithm understanding， which is more efficient and accurate compared to manual understan-ding. This paper systematically organized the relevant work in the field of program algorithm recognition. Firstly， it combed the concepts related to program algorithm recognition and introduced methods based on knowledge representation and information retrieval. Secondly， it divided the code representation based methods into sequence based， tree based and graph based me-thods for detailed elaboration， and made a summary and comparison of the three types of methods. Finally， it introduced the relevant application fields of the program algorithm recognition task， analyzed the remaining problems and made prospects for future development.

Key words：program algorithm recognition; program understanding; program code representation

0 引言

20世紀70年代，計算機科學家Wirth［1］提出公式“programs=algorithms+data structures”，即“算法+數據結構=程序”。其中，算法（algorithm）是解決某一問題或完成某一任務時所采取的具體方法或步驟，選用某（幾）種數據結構予以實現算法就形成了程序，程序代碼是程序的具體實現，依賴于所使用的程序設計語言。

隨著信息化建設的逐步推進，程序代碼儲備越來越豐富，例如國內開源技術社區OSCHINA（https：//www.oschina.net/）中已收錄全球知名項目近5萬款，及其建立的代碼托管平臺Gitee（https：//gitee.com/）中的代碼倉庫已達2 000萬。識別程序代碼所實現的算法，開發人員可以快速了解整個代碼完成的任務與實現的功能，在此基礎上更加高效地開展代碼推薦［2］、代碼搜索［3］、逆向工程和軟件再工程等任務。例如選取性能更好的算法進行軟件復用或根據其思想進行軟件重構，發現現行程序代碼中的缺陷以更好地維護軟件等。然而，對于龐大復雜的程序代碼，其中所涉及的算法繁多，程序員如果想要了解語句級或函數級的功能必須閱讀程序源代碼，這無疑是一項非常繁重的工作。

程序算法識別作為程序理解的一項研究課題，其主要目標是從代碼中識別出相關算法的程序代碼段［4］，實現自動化地理解程序算法。相較于依賴專家先驗知識、受限于程序員自身認知水平、費用較高、時間開銷較大的人工理解程序算法，自動化理解程序算法效率更高、代價更低。因此，目前的程序算法識別方法逐步由早期的模板匹配、概念定位，向更深入利用程序代碼特征發展，即在考慮任務要求后，采用機器學習或深度學習的方法挖掘更深層次的程序代碼信息，生成特征向量以識別程序算法，不僅節省了大量的人工勞動，更進一步提高了這一任務的精確度和準確率，增強了具體模型的可擴展性。本文首先，梳理“算法”一詞的來源與含義，對“程序算法”以及“程序算法識別”進行定義與說明；其次，對基于知識表示和基于信息檢索的程序算法識別方法進行簡介，著重闡述基于代碼表征的方法，并對每種方法的優缺點展開分析；再次，總結程序算法識別任務的相關應用領域，為其應用提供一定參考；最后，根據程序算法識別研究的現狀指出其存在的局限性與不足，為未來程序算法識別任務的研究提供思路。

1 相關概念

“算法”一詞的來源可以追溯到希爾伯特提出要構建一組具有“完備性”的公理體系，盡管后來這樣的公理體系被證明并不存在，但隨著這一證明而遺留的問題推動了算法形式化定義的進程。算法得以定義有助于將其應用于計算機領域解決實際問題，程序代碼也因算法更加高效，而復用這類程序算法，能夠避免大量重復的編程任務。因此，識別程序算法具有非常重要的研究價值。

1.1 程序算法的含義

20世紀20年代，希爾伯特提出要建立一組公理體系，使得一切數學命題原則上都能憑借這組公理體系經過有限步推斷判定真偽，這被稱作這組公理體系的“完備性”。然而，庫爾特·哥德爾于1931年發表論文，提出不完備性定理，證明了任何無矛盾的包含初等數論的公理體系，必定存在一個用這組公理不能辨別其真偽的不可判定命題［5］。哥德爾不完備性定理留下了一個根本性問題，即對于一個到目前為止尚未發現任何解決方法的具體問題，是否還能找到它的求解方法？需要說明的是，一個“數學問題”是這個問題的無限多個實例的集合。也就是說，發現一種解決問題的方法，意味著能夠將這個問題的無限多樣性減少到由方法描述給出的有限大小［6］。艾倫·麥席森·圖靈希望證明存在一些問題，其無限多樣性不能簡化至有限大小。為此，圖靈將“數學方法”（希爾伯特稱為算法）一詞的含義形式化，于1936年提出了圖靈機，并提出觀點：能行可計算函數都是用圖靈機可計算的函數。這一論點與阿隆佐·丘奇的“每個能行地可計算的函數都是一般遞歸的”論點統稱為丘奇-圖靈論題［7］。文獻［8］認為算法是一組有限規則，它給出了一系列解決特定類型問題的操作。嚴蔚敏等人［9］定義算法是為解決某類問題而規定的一個有限長的操作序列。

本文將“使用程序設計語言實現求解某一問題所使用算法的程序代碼”稱為“程序算法”，程序算法識別任務則是從源代碼中找出表達某個算法的程序代碼段。算法、程序、程序算法、源代碼之間關系如圖1所示。

1.2 相關研究

在研究初期，學者們或依賴預定義的規則和知識庫，或采用搜索和匹配技術實現程序算法的識別，這兩種方法可以被概括為基于知識表示的方法與基于信息檢索的方法。

1.2.1 基于知識表示的方法

基于知識表示的方法以實現某種算法的程序代碼都有固定模式為前提，將待識別程序代碼中的概念和邏輯結構進行抽象，通過搜索、匹配和推理等手段在程序模板知識庫中尋找與之相匹配的程序描述模板，從而實現程序算法識別。其中，所使用的知識庫或由專家手工構建，或通過專家利用先驗知識制定規則，之后使用機器識別相關知識，其過程如圖2所示。

Murray［10］在Talus和Proust［11］項目中使用“框架”表示程序知識，并建立使用框架集描述的plan（程序代碼片段）庫。當識別一段程序代碼時，首先將其轉換為使用框架描述的plan，然后在plan庫中進行匹配來識別此plan的含義。這種方法存在許多不足，例如Proust識別plan能力有限，擴展調試知識困難，只能處理少數小型程序代碼等。除了利用現有的plan庫，文獻［12］通過分解技術將程序代碼分解為事件（events）和切片（slices）兩種片段，由于events和slices的表示形式不同，所以分別為這兩種片段構建相應的plan庫進行匹配，并利用5個隨機選中的Pascal代碼中的92個循環對進行評估［13］。雖然這兩種分解技術對程序算法識別任務產生了一定的積極影響，但程序切片的知識庫在結構和內容上更加復雜，與常用的自動化分解技術相比，需要更多的人力資源和專業知識以設計知識庫。

上述方法通過構建或利用已有的表示程序知識的框架實現了程序算法識別，另一方面，還可以通過程序代碼特征匹配的手段。文獻［2］提出一種基于近似子樹匹配的方法，如圖3所示。首先，遍歷源代碼建立抽象語法樹（abstract syntax tree，AST），依據樹節點功能對其進行分類，將相似節點映射為相同哈希值；其次，通過〈節點號，哈希值〉元組表示當前節點所位于子樹的信息，并以所有子樹的哈希值之和作為整棵AST的哈希值，完成樹連接；接著，以序列的形式對AST進行存儲。最后，在哈希樹中獲取相同節點號的哈希值列表，使用二進制搜索方法搜索相似哈希值完成匹配。該方法雖然具有很高的召回率，但當哈希值列表較長時，搜索耗費的時長也會隨之增長。此外，將整棵哈希樹以序列形式存儲，尤其對于大規模代碼而言，將會產生大量額外的存儲成本與計算開銷。王甜甜等人［14］也利用了特征匹配的思想，采用最大公共子序列算法對缺陷程序代碼和示例程序代碼的AST進行匹配，從而識別、定位了學生程序代碼中的缺陷。

不同于通過匹配的方式識別程序算法，Harandi等人［15］創建了一個基于知識的程序分析工具PAT。該工具使用一個面向對象的框架重新表示編程概念，并使用基于啟發式的概念識別機制從代碼中推導出高級的功能概念，從而實現了程序代碼自動分析。盡管該方法在面對庫中涵蓋程序算法不全這一問題時，能夠通過推理識別程序算法，但仍受限于啟發式知識的局限性與主觀性，導致部分功能概念依然無法被識別。

總而言之，盡管這類方法實現起來較為簡單，在數據稀疏的情況下，可以利用現有的規則與程序模板知識庫，但這就對庫中的內容提出了非常嚴格的要求，必須具備高度的準確性和完整性。然而一方面，程序模板知識庫的構建和維護需要耗費大量的人力和專業知識，使得庫中的內容具有一定的主觀性，同時限制了該方法的擴展性和適用范圍。另一方面，算法也隨著數學、計算機科學等學科的發展而在源源不斷地產生，庫中知識存在覆蓋不全面的情況，這就要求及時地對知識庫作出擴展與更新，對于精確地識別程序算法均會產生一定的影響。

1.2.2 基于信息檢索的方法

在軟件開發過程中，會隨之產生大量的文檔和源代碼注釋，能夠說明程序代碼的功能、邏輯結構和實現算法等內容，有效利用這些信息完成程序算法識別任務是基于信息檢索方法的研究目標。其流程如圖4所示，將程序員視角下代碼中的各種計算單元使用units集合表示，將用戶視角中能夠表明用戶觀點的各類說明文檔或注釋通過features集合表達，基于信息檢索完成概念定位［16］，在本文中即找到units中元素與features元素之間的關聯。在信息檢索方法中，經典模型有向量空間模型（vector space model，VSM）和主題模型。其中，主題模型主要包括潛在語義分析（latent semantic analysis，LSA；又稱為潛在語義索引，latent semantic index，LSI）和隱含狄利克雷分布（latent Dirichlet allocation，LDA）。

VSM由Salton等人［17］于1969年提出，在進行概念定位時，可利用VSM基于詞袋模型將說明文檔和程序代碼分別表征為向量，如果向量相似則可以認為這段程序代碼所實現的算法即為該說明文檔所描述的算法。但是，在將代碼的相關文本內容轉換為向量時，經典的VSM認為詞與詞之間是相互獨立的，割裂了文本本身的語義關聯，使機器理解計算機領域中的專有術語或表達方式從而識別程序代碼中所蘊涵的算法更加困難。

相較之下，主題模型假設詞與詞之間存在緊密聯系，通過抽取出若干組關鍵詞作為文檔集的主題，以表達文檔集的中心思想。Marcus等人［18］根據代碼模塊與代碼文件之間的關系生成圖，圖中的節點和邊分別表示代碼模塊以及模塊之間的關系，同時定義了兩種類型的邊。其中，語義相似邊主要利用LSI技術，從程序代碼和說明文檔中提取能夠說明代碼含義的關鍵詞向量，當兩代碼模塊對應向量之間的余弦距離低于閾值時，則邊存在。接著，基于此圖對代碼模塊進行聚類，以實現對指定模塊的識別。Poshyvanyk等人［19］認為僅基于LSI技術的概念定位所得到的結果具有不確定性，因此提出基于執行場景和信息檢索方法的概率排序進行概念定位。實驗結果表明，概念定位的有效性得到顯著提高。除此之外，還有研究者通過LDA模型［20］分別挖掘說明文檔和程序代碼的topic，再基于主題分布計算兩者之間的相似度，最終實現概念定位［21］。

相比于VSM，LSA考慮到了文本自身的語義信息，LDA模型通過挖掘文檔的topic能夠找到沒有相同詞的兩個文檔之間的聯系。此外，傳統的自然語言模型需要定義語法和詞典，但對于程序代碼而言，標識符等已形成了自己的語言，然而并沒有對其進行定義的語法或形態學規則，導致部分模型在處理程序代碼文檔時適用性較差。而LSA模型無須使用預定義的語法或詞匯表［19］，這就支持程序員在編程時能夠定義詞表之外且具有隱含意義的變量名［22］，因此LSA模型更適合處理程序代碼這類特殊的文本文檔。

基于信息檢索的方法已在文件級和函數級程序代碼中取得較為精確的定位效果，但是這種定位粒度較粗，對于語句級程序算法仍需消耗大量人力做進一步確認。對此，岳雷等人［23］提出一種語句級定位方法。首先，檢索已有的與待識別代碼的相關文檔相似度較高的說明文檔或注釋，提取對應的已識別的程序算法語句；其次，根據待識別代碼及其相關文檔的文本相似度確定可能的程序算法；最后，計算可能的程序算法與已識別的語句級程序算法的相似度并降序排列，實現語句級定位。該方法在識別更多的語句級程序算法的同時，節省了時間開銷。然而，其依賴于程序算法的相關文檔以及已識別的程序算法，可能無法有效定位新穎的程序算法或變體。

綜上，與基于知識表示的方法相比較，基于信息檢索的方法更為客觀，無須依賴領域知識先驗地構建規則或程序模板知識庫，而是利用已有的相關文檔，通過檢索的方式更快速地識別程序算法，節省了大量人力。然而一方面，自然語言與程序設計語言之間存在一定差異，即程序代碼的說明文檔與其本身具有一定的差別，這類方法沒有充分考慮到這種差異性。另一方面，該類方法的識別結果很大程度上受所使用文檔的影響，且代碼的描述文檔往往存在介紹不全、描述不準甚至缺少相關文檔的狀況，這就導致基于信息檢索的方法存在一定局限性。

2 基于代碼表征的程序算法識別方法

事實上，每種算法在具體實現時都會體現出不同的代碼特征，這些特征包括代碼行數、變量個數、循環個數、控制結構、數據流結構等，但基于知識表示與基于信息檢索的方法并沒有充分利用這部分信息。

基于代碼表征的方法在不同程序算法具有不同特征值的假設下，以代碼特征能夠體現程序功能或算法為前提，從一種或多種角度提取程序代碼中的特征并生成相應的向量，最終達到程序算法識別的目的。在利用程序代碼特征時，傳統方法常通過手工提取特征，然后基于統計學原理對其進行表征［24］。這種方法雖然能夠借助知識引導，但所提取的特征具有主觀性，還會造成信息的損失。2012年，Hindle等人［25］提出了代碼的自然性假設（natural ness hypothesis），證明了源代碼具有與自然語言相似的特性。由此機器學習方法開始被應用于代碼表征，減少了程序算法識別任務中大量的人工參與。后來，深度學習的應用使得自然語言處理取得了更好的效果，逐漸有學者嘗試將深度學習方法也應用于程序代碼表征，以挖掘其更深層次的復雜特征［26］。由于語義等價問題不可判定，是停機問題［27］的直接推論，所以在利用深度學習等方法表征程序代碼的基礎上，有學者將程序算法識別問題轉換為向量相似性判斷、向量分類和向量聚類等問題，如圖5所示。首先，提取程序代碼特征，通過序列、樹或圖對代碼予以組織，生成目標算法與待識別算法相應的特征向量［28］；其次，計算兩向量之間的距離等并設置距離閾值；最后，通過向量相似性判斷、向量分類或向量聚類完成程序算法識別任務，即當兩向量之間的距離低于閾值時，兩程序算法被判定為相似，或者在分類與聚類時被分為或聚為一類，則認為這兩段程序代碼描述的是同一算法。

2.1 基于序列的方法

隨著自然語言處理技術的發展，任意文本都可以被表示為詞序列，并生成詞序列的向量表示。程序代碼作為一種特殊的文本，被表示為詞序列時主要有兩種方式：a）不對源代碼做任何處理，直接將其轉換為詞序列；b）對源代碼進行詞法分析后得到一個詞匯序列，該序列也稱為token序列。

顯然，在獲取詞序列時，與解析源代碼相比，不對源代碼進行處理更加節省時間，但是這樣將會導致其中大量的詞法信息丟失，使得最終得到的序列特征并不夠充分。而在token化程序代碼時，使用不同的轉換規則將會產生不同的token串，對后續工作也會產生一定的影響。張冬梅等人［29］通過自定義轉換規則，規避了不同變量名和函數名對于表示結果的影響。然后，為從token中提取體現其上下文關系的深層信息，采用能夠緩解程序代碼長期依賴問題的雙向長短期記憶（bi-directional long short-term memory，Bi-LSTM）網絡提取行級與全局特征。同時，由于不同token與不同行對程序算法識別任務具有不同程度的影響，引入注意力機制調整重要token及代碼行的權重，最終將代碼相似行檢測的召回率以及精確度分別提高至91%和97%，但是由于轉換規則以自定義的方式制定，也使得該方法對于某些程序設計語言或代碼庫可能并不完全適用。

文獻［30］提出目前已知的首個大型自然語言-編程語言（natural language-programming language，NL-PL）預訓練模型CodeBERT。如圖6所示，該模型以雙峰NL-PL對和單峰數據作為輸入，并將NL-PL對設置為帶有特殊分隔符的片段，即“［CLS］，自然語言文本詞匯序列，［SEP］，程序代碼token序列，［EOS］”。接著，以掩碼語言建模（masked language modeling，MLM）和替換標記檢測（replaced token detection，RTD）為訓練目標，基于多層雙向的Transformer學習代碼中不同token之間的上下文關系以及語義信息并生成向量表示。其中，Transformer共有12層，每一層中有12個自注意力頭，這使得模型在每一層中都可以充分考慮序列中的不同位置，不僅能夠更好地學習不同token之間的上下文關系，還具備處理長依賴問題的能力。成思強等人［31］基于CodeBERT提出CBBCC模型，將CodeBERT所生成的向量表示用于POJ-104數據集進行代碼分類，是首個將BERT預訓練模型引入代碼分類任務的模型。實驗結果表明，與TBCNN、CVRNN和ASTNN等模型相比，該模型能夠保持各項分類指標都在98%以上，且在精確度上比最優模型提高了1.1%。值得一提的是，CodeBERT使用Python、Java、JavaScript等六種常用程序設計語言實現的代碼作為訓練數據，當應用該模型于C#語言時，仍能取得很好的效果，這表明CodeBERT具有很強的泛化能力，可以識別多種語言的程序算法。CodeT5［32］同樣以NL-PL對作為模型的輸入，與CodeBERT不同的是，其采用編碼器-解碼器結構，以遮蓋片段預測（masked span prediction，MSP）、標識符標注（identifier tagging，IT）和遮蓋標識符預測（masked identifier prediction，MIP）等作為預訓練任務，更加關注token中標識符所蘊涵的代碼語義信息，能夠同時支持代碼理解以及生成任務。盡管上述方法在多種語言、多項任務中都取得了不錯的效果，卻都忽視了程序代碼中所蘊涵的豐富的結構信息與數據流信息。

除token序列之外，由于程序代碼中的應用程序接口（application programming interface，API）也能體現程序代碼的功能，所以API序列也有一定的研究價值，例如總結API序列，構建API知識與程序代碼所實現功能的描述之間的映射，并將其應用于程序算法識別，但是由于具有不同特征的API序列其功能可能一致，導致這種方法的擴展性較差。Huang等人［33］提出一種API嵌入模型API2vec，使得兩個特征不同但上下文相似的API在嵌入空間中能夠更加接近，然后利用K-means算法對API2vec所生成向量進行聚類，獲取功能相近的API類簇，從而增大了功能識別對API特征變化的彈性。

如若在詞法分析的基礎上將程序代碼映射為一組二進制數，就能得到代碼的指紋。2007年，Google公司提出Simhash算法，將該算法應用于代碼相似性判定，核心思想是通過指紋判斷代碼的相似度，指紋越接近，代碼越相似。然而在實驗過程中，李玫等人［34］發現在大規模數據集中存在行覆蓋的現象，為消除高頻出現但所包含語義信息較少的代碼行對指紋生成的影響，其對基于文本的行粒度相似哈希算法進行優化，提出根據不同編程語言的特性篩選代碼行，進一步提高了代碼相似性檢測的精確度。但是該方法在程序代碼文件較小或包含語義信息較少、兩程序代碼總行數差距較大時，存在未能識別出程序算法的情況。

基于序列方法的對比如表1所示。這種方法比較簡單，能夠關注到程序代碼中token的位置信息，計算代價較低且高效，尤其是在對大規模的程序代碼進行表示時，可以應用于任意編程語言。而且經過詞法解析后所得的token序列保留了程序代碼的詞法信息，token化時所遵循的轉換規則使得代碼表示更加靈活。然而，程序代碼不同于普通文本，其具有強結構性，這種方法極容易丟失程序代碼中的結構信息，以致于無法很好地建模程序代碼。此外，對于指紋而言，盡管程序源代碼未發生變化，如果重新進行編譯，指紋也可能改變，這也為程序算法的識別帶來了很大的不便。

2.2 基于樹的方法

如果修改程序代碼但不改變其執行結構，例如修改其中的變量名、函數名、數據類型和書寫風格等，那么從結構的角度講，兩段程序代碼是一致的［35］。在結構級表征程序代碼的方法中，通過語法分析將其表示為AST，從而保留程序代碼的結構信息是較為常用的方法。如圖7所示，AST中的每一個節點及其子節點表示程序代碼中的某一代碼片段，非終結符對應其中的中間節點，如while、if等，終結符對應其中的葉子節點，如變量名a和b、常量名、方法名等。

由于傳統方法中AST關鍵節點的字面含義不同會導致匹配失敗的問題未能得到解決，比如“for”和“while”的字面意思雖不同，但都實現了循環的功能，魏敏等人［36］提出了一種基于程序向量樹和聚類的學生程序算法識別方法AR-PVTK。首先將程序代碼表示為AST，為其葉子節點賦予對應的詞向量表示，將AST轉換為程序向量樹并將其編碼為定長向量，采用K-means聚類算法將實現同一種算法的代碼映射到向量空間中相近的位置，從而完成程序算法的識別。由于在生成葉子節點的向量表示時融入了語法信息，所以能夠有效規避語法形式多樣化的問題。

將程序代碼表示為AST后，在生成相應的特征向量時，采用何種遍歷方式將會直接影響代碼表征的速度與質量。如基于結構的遍歷方法（structure-based traversal，SBT），其生成的原始序列中包含源代碼的標識符，內容上也有許多重復，且SBT使用一對括號表示樹結構，不利于結構信息的編碼。彭斌等人［37］基于SBT提出了面向約簡的抽象語法樹遍歷方法RAST，以圖7中虛線部分節點結構為例，具體方法如圖8所示。

首先，使用SBT遍歷AST生成SBT序列，然后使用先序遍歷AST所得序列號替換SBT序列中的括號，并將SBT序列劃分為序列號序列和節點序列。其次，采用駝峰式轉換拆分節點序列值（比如將“isTrue”拆分為“is”、“True”），將原始節點對應序列號賦值給每個拆分后的詞，以解決詞匯量過大的問題。最后，針對遞歸神經網絡處理程序代碼時不能很好地解決長依賴問題，利用卷積神經網絡（convolutional neural networks，CNN）中的卷積層分別中從token向量和RAST向量中提取詞法與語法特征，生成最終的向量表示，最大程度地保存了程序代碼的結構信息。

然而，在利用AST表示大規模程序代碼時，相應的AST規模亦非常龐大，此時對應的AST節點必然繁多，遍歷所有樹節點也必將耗時，同時很容易在訓練模型時出現梯度消失或梯度1爆炸的問題。為解決這類問題，龔丹等人［38］將代碼轉換為AST，選取其關鍵節點類型作為特征表示，經過后序遍歷AST得到每個節點最終的特征向量。接著引入局部敏感哈希算法，對特征向量進行哈希處理，然后采用歐氏距離度量相似度。該方法將一個在大型數據集合中尋找相似特征向量的問題轉換為在一個較小的數據集合中，大幅地降低了時間復雜度。但是這一方法受到哈希函數的限制，相似的特征向量也有可能被映射至不同的小數據集合中，導致相似性判定出現誤差。Zhang等人［39］通過證明將整棵AST切割為一系列子樹有利于表達程序代碼的語義信息，提出了一種新的基于AST與神經網絡的代碼表征模型ASTNN。首先，將整棵AST按照語句進行切割；其次，捕獲語句的詞法與句法信息，將每一棵切割所得的語句樹編碼為向量，得到語句向量序列；最后，采用雙向門控循環單元（bi-directional gated recurrent unit，Bi-GRU）生成最終的程序代碼向量表示，以提升循環層捕捉代碼長依賴信息的能力，捕獲程序代碼所蘊涵的自然性。金巖磊等人［40］參考樹切割的思想，為進一步利用程序代碼中的結構與語義信息，使用通過TBCNN改進的ASTNN模型對AST進行編碼，獲取每棵AST的向量表示，接著利用疊加的雙向循環神經網絡更全面地捕獲代碼塊之間的序列信息，通過拼接兩個時間方向隱藏單元輸出，最終得到整個程序代碼的向量表示，并通過分類識別程序代碼所描述的算法。Hua等人［41］也利用了這種思想，提出基于Transformer的代碼分類模型TBCC。首先，將子樹扁平化為序列，為顯示地區分每棵子樹，在每棵子樹對應的序列中添加特殊標記“［SEP］”；其次，由于Transformer中的自注意力模塊不包含循環或卷積單元，導致難以處理序列中的順序關系，其將代碼元素的位置信息通過嵌入的方式引入模型；最后，利用Transformer對擁有特殊標記的序列進行編碼，通過該模型中的多頭自注意力機制捕捉不同代碼元素之間的上下文關系，關注到了整個序列的各個位置。實驗結果表明，相較于基于CNN和循環神經網絡（recurrent netural network，RNN）的方法，TBCC對程序代碼中的長依賴關系更加敏感，梯度消失和梯度爆炸的問題得以有效緩解。然而與此同時，Transformer常常需要大量的計算與存儲開銷，這對于十分龐大的AST而言，幾乎是無法實現的。對此，Zhang等人［42］構建了一個由圖卷積神經網絡和注意力機制組成的代碼學習器，將大量token轉換為幾個蘊涵豐富語義信息的token，很大程度上減少了輸入的token數量。此外，在Transformer的編碼器中引入跨代碼注意力模塊來學習代碼表示，進一步捕捉代碼片段之間的相似性。實驗結果表明，該方法無須大量的計算成本，大大降低了基于Transformer的程序算法識別模型的計算開銷。

基于樹方法的對比如表2所示。這類方法關注到了程序代碼的強結構性，相較于基于序列的代碼組織方式，樹結構可以直觀地展示程序代碼的邏輯結構，準確反映其中的層次結構、控制流程等，非常利于捕捉結構信息，在生成向量表示時，還能夠將詞法與語法信息相融合。然而，對于大規模程序代碼，盡管將其切割為子樹能夠有效緩解梯度消失等問題，提高代碼表征效率，但與此同時，會隨之產生額外的計算開銷，包括分割整棵AST、遍歷子樹等。除此之外，不同于自然語言，程序代碼必須是可執行的，即其具有可執行性，而基于樹的方法雖然保存了其中的結構特征，卻并未關注到程序代碼動態運行時的語義信息，例如數據流信息和控制流信息等。

2.3 基于圖的方法

對于兩段結構相同的代碼，其執行路徑［43］可能不同，所表達的語義可能也不一樣。金芝等人［44］認為，提取程序代碼的數據流和（或）控制流信息的過程，可以看作是從問題求解視角出發的程序代碼語義理解。基于圖的代碼表征方法主要使用根據程序代碼生成的數據流圖（data flowing graph，DFG）、控制流圖（control flowing graph，CFG）、程序依賴圖（program dependence graph，PDG）等，其中，數據流表示程序代碼中數據的流向，控制流表示其中邏輯的走向，程序依賴圖主要用于表示數據和控制的依賴關系，不僅能表征語法信息，還可以表征語義信息。梁瑤等人［45］針對token和AST對代碼執行語義信息無法充分利用的缺點，使用CFG表示代碼的執行語義，并首次使用基于隨機游走的圖嵌入算法DeepWalk學習和推理代碼中的語義信息。與word2vec和doc2vec方法相比，DeepWalk作為一種針對圖結構的算法，能夠更好地學習圖結構、獲取圖中節點在上下文中的信息，但當CFG結構非常繁雜時，基于隨機游走的方法可能無法充分地學習其中復雜的語義信息。

肖添明等人［46］針對AST中缺少與控制相關信息的問題，從整合AST、CFG、PDG三種表示形式的代碼屬性圖（code property graph，CPG）中提取出AST序列和CFG序列保存代碼的結構信息，并針對Bi-LSTM模型參數較多、訓練時間較長、易發生過擬合等問題，選用其變體Bi-GRU生成特征向量。實驗結果表明，相較于單一使用AST的表征方式，該方法對于代碼相似性檢測最大可提高35%的精確率以及22%的召回率。盡管PDG中包含了程序代碼中的數據流信息，但是在初步提取特征時，更多關注的是CPG中的結構特征而忽略了數據流信息，這可能造成部分語義信息的丟失。為保留程序代碼結構特征的同時，利用其運行時產生的數據流與控制流信息，文獻［47］首先依據程序代碼的AST、CFG、DFG構建了能夠體現數據流向和控制依賴的代碼復合圖（code composite graph，CCG）；其次，在傳統的圖神經網絡中添加后向邊，構建了能夠處理前后序數據的雙向圖神經網絡（bi-directional graph neural network，BGNN），以從CCG中學習代碼的上下文特征，生成最終的節點表示；最后，考慮到程序算法或許在整體代碼中只占較小比例，從整個CCG中很難學到程序算法的語義信息，因此利用CNN進一步提取主要特征并生成代碼向量表示，通過分類器實現程序代碼分類。

對于程序設計語言來講，其種類非常豐富，不同的語言具有不同的特性，這一特點也稱為代碼語言的多樣性，為程序算法識別任務帶來了新的挑戰。在面對這一問題時，已有模型通過大量的包括多種語言的語料對模型進行預訓練以突破這一難題，例如前文所提及的CodeBERT，但與code2seq在部分任務上相比，該模型效果略低。這或許是因為code2seq使用AST作為模型輸入，體現了程序代碼的結構特征，而CodeBERT僅以源代碼作為輸入。對此，文獻［48］基于CodeBERT提出了新的預訓練模型GraphCodeBERT。首先，將程序代碼解析為AST并從中提取變量的序列；其次，利用序列和AST構建DFG，引入程序代碼的語義信息，同時避免AST的深層層次結構帶來不必要的信息；接著，基于增添了graph-guided masked attention層的Transformer對所提取的代碼特征進行編碼，以更好地將圖結構融入Transformer。與CodeBERT相比，其還增加了邊預測（edge prediction，EP）和節點對齊（node alignment，NA）兩項任務，分別學習程序代碼中數值的流向以及DFG與源代碼之間的對應關系，進一步學習代碼上下文信息。針對代碼語言多樣性這一問題，Ben-Nun等人［49］也提供了解決思路，設計了新的程序代碼分類模型，如圖9所示。首先，通過LLVM編譯器得到程序代碼的中間表示（intermediate representation，IR）；其次，將數據流和控制流信息融入IR，構建上下文流圖（conte-Xtual flow graph，XFG），為IR提供上下文表示。接著，根據XFG訓練程序代碼的向量表示空間inst2vec，從而生成代碼的向量表示并使用RNN分類程序代碼。實驗結果表明，該模型的準確率高于TBCNN模型。由于該方法在表征程序代碼時，通過LLVM編譯器將由高級程序設計語言編寫的源代碼轉換為編譯語言描述的中間碼，使得該模型可以生成不同程序設計語言實現的程序代碼的向量表示，實現了讓分類任務獨立于程序設計語言，打破了一個方法只能識別一種語言的程序算法的局限。但由于其依賴于LLVM編譯器，所以與基于CodeBERT的模型相比，該方法的遷移性較差。

基于圖方法的對比如表3所示。這類方法能夠捕捉程序代碼在動態運行時隨之產生的數據流和控制流等信息，一些方法將AST與DFG和（或）CFG相融合，既保留了語法特征又保持了語義特征，可以更好地捕獲程序代碼中的上下文依賴，例如變量的作用域、函數的調用關系等。然而一方面，盡管某類方法能夠識別多種語言的程序算法，但是這需要使用大量語料對模型進行預訓練，而依賴于PDG的基于圖的方法通常需要一個PDG生成器，對于不同程序設計語言的技術隔閡依然存在。另一方面，基于圖的方法涉及語法解析、語義分析等過程，對于復雜龐大的程序代碼而言，在表征時會消耗巨大的時間與計算資源。

2.4 其他方法

上述三類基于代碼表征的方法首先將程序代碼表示為序列、樹或圖，在此基礎上生成程序代碼最終的向量表示，其優缺點對比如表4所示。然而，這些表征方式都不是代碼詞匯的直接向量表示，對于詞向量，也是通過訓練得到標識符對應的詞向量，這同樣會造成程序代碼信息的丟失，而簡單使用統計學原理表征代碼，又無法體現其語法和語義信息。為解決此問題，謝春麗等人［50］提出了一種融合統計信息的卷積神經網絡源代碼相似性檢測方法，將程序代碼表示為詞嵌入向量，而非獲取標識符對應詞向量，然后采用CNN直接挖掘代碼中隱藏的語法及語義信息，通過余弦距離度量代碼之間的相似性，以提升相似性檢測的精度。盡管該方法融入了程序代碼中詞的統計信息，但未充分考慮其中的保留字和操作符等不同的詞匯類型。

還有學者將程序算法識別問題與圖像檢測任務相結合。文獻［51］對程序代碼使用語法高亮并將其轉換為圖像，基于圖像之間的相似度完成代碼檢測。文獻［52］將程序代碼的二進制文件轉換為灰度圖，然后利用所設計的基于灰度圖像處理的深度學習模型MalMKNet識別代碼功能。鄭玨等人［53］不僅利用灰度圖像，還將帶有API函數調用與操作碼的混合序列作為代碼特征，最終通過基于CNN的多特征分類器實現代碼分類。以上方法利用計算機視覺技術，從一定程度上規避了程序代碼語法與語義表征的復雜性，但同樣丟失了這部分信息，且與源代碼相比，利用圖像表征的結果并不易于理解和解釋。

2.5 小結

基于代碼表征方法從程序代碼本身出發，以其表征作為方法核心，能夠保持其中的強結構性、長依賴性、數據流和控制流等信息，既不依賴專家的先驗知識，又無須相關的說明文檔，節省了大量人力，降低了因此產生誤差的幾率。但是，這一類方法對于大規模異構的程序算法，當程序代碼提取后的特征非常龐大時，識別過程的計算規模與開銷也十分巨大。其次，在對程序代碼進行表征時，特征粒度的選擇具有主觀性，這會對識別結果造成影響。此外，在利用相似性判斷、分類等方法完成任務時，需要大量的有標簽數據對模型進行訓練，而且存在程序代碼被判定為相似或者被分為或聚為一類時，其對應算法并不相同的狀況，即這類方法存在誤識別的情況。總言之，上述三類程序算法識別方法（基于知識表示、基于信息檢索與基于代碼表征的方法）各有優勢與不足，其優缺點對比如表5所示。

3 相關應用領域

隨著程序算法識別技術的發展，尤其是應用機器學習、深度學習方法幫助挖掘深層次的程序代碼信息，程序算法的識別更加快速、精確，得到了廣泛的應用。不僅可以用于支撐程序理解，幫助程序員進行軟件復用、維護等軟件工程，還可以用于優化、診斷和驗證程序，輔助編程教育等。

3.1 代碼優化與變換

代碼優化是指在不改變程序代碼運行結果的前提下對其進行變換，使其占用內存更少、處理速度更快等。算法級優化作為從程序所使用算法角度出發的優化方法，是實現代碼優化的關鍵所在。

程序算法識別任務一方面可以確定當前程序所使用算法，判斷代碼實際運行的效率，如果效果較差，則可以在語義一致性的前提下，用性能更好的算法替換性能較差的算法。另一方面，在移植代碼時，所識別出的高效程序算法能夠幫助程序員快速變換和移植程序代碼［54］。例如通過識別程序代碼中的數據依賴，從而減少數據之間的依賴關系，使代碼能夠并行計算［55］，優化運行時間，降低資源消耗。

3.2 程序理解

程序算法識別作為程序理解的一項研究課題，通過識別出程序代碼所實現的算法，幫助程序員理解代碼，支撐著程序理解的發展。程序員在進行各項軟件工程任務時，例如軟件復用與維護，可以通過代碼搜索的手段獲取待實現或維護功能相應的代碼或說明文檔等。功能強大的代碼搜索引擎Krugle和Google code就通過特征定位技術實現算法識別，并據此為用戶提供所需要的代碼。CodeBERT和GraphCodeBERT也可以在代碼片段和自然語言描述之間進行相似性匹配［30，48］，從而實現代碼的搜索和推薦，輔助程序員完成各類軟件工程任務。

3.3 程序診斷及驗證

大大小小的程序代碼中都可能存在漏洞，復用這種存在軟件缺陷或漏洞的代碼很可能導致程序代碼運行低效，甚至威脅計算機系統安全。有研究數據表明，在軟件開發過程中，常包含5%～20%的重復代碼；在開源項目中，代碼復用率甚至可能超過50%［56］。

程序診斷指通過分析和調試程序，識別和定位程序中的錯誤和異常等，發掘產生這些問題的原因所在［57］。程序驗證指通過形式化方法和技術，對程序的正確性進行全面和系統的證明與檢查。通過識別程序算法，計算機能自動檢測程序代碼片段，發現其中存在的安全漏洞、缺陷和性能較差的程序算法，減少復用脆弱性代碼等行為為代碼安全帶來的致命隱患［46］。

3.4 編程教育

在編程教育方面，程序算法識別任務同樣發揮著重要作用。一方面，所識別出的程序算法可用于構建和擴充算法演示系統，例如VisuAIgo（https：//visualgo.net/zh）以及Algorithm Visualizer（https：//algorithm-visualizer.org/），教師可以通過這些系統更為形象地向學生介紹算法，讓其能夠更加直觀地理解算法的含義與具體思路。另一方面，程序算法識別技術可以識別學生程序所使用的算法，來判斷學生作業是否完成或正確，并為學生完成作業提供參考。

趙亮等人［58］構建了一個大數據算法庫教學實驗平臺，該平臺中包括分類、聚類等常用算法，用戶按系統要求實現某算法后上傳程序代碼文件，系統后臺驗證其正確性，如若正確會將其加入算法列表。文獻［15］通過輸出缺陷代碼與示例代碼相應的語法樹，對未匹配的結構和語句進行標記，從而輔助學生理解個人代碼出錯的原因。Gao等人［59］基于代碼相似性設計了一種聚類算法，可以生成針對給定編程問題的所有正確解的聚類，為教師和學生實現編程作業一題多解給予一定的啟示和幫助。文獻［42］利用所識別出的程序算法搭建了算法推薦系統，通過關鍵詞匹配為編程學習過程中遇到困難的學習者推薦算法。大部分參與者認為，這種算法推薦能夠為編程問題“一題多解”提供思路。

4 發展趨勢與展望

程序算法識別任務通過自動化地理解程序算法，既能夠高效輔助開發人員完成各項軟件工程任務，又可以助力編程教育事業的快速發展。隨著程序算法識別技術的不斷更新，所捕獲的代碼信息也更加豐富，準確率與效率也在穩步提升。盡管如此，程序算法識別任務也依然面臨著眾多問題與挑戰。

4.1 現有方法自身具有局限性

基于知識表示的方法對于程序模板知識庫中的知識有極高的要求，只有仔細分析一個算法，才能正確定義該算法的模板。如果在這個過程中出錯，識別結果自然會受到影響。同樣，基于信息檢索的方法也對代碼格式及其說明文檔提出了要求，例如需要說明文檔充分、內容正確等，但代碼說明文件常寫于設計較大規模軟件時，對于學生程序代碼，大多只有甚至沒有注釋，不便于程序算法的自動化識別。

基于代碼表征的方法在從程序代碼中提取特征時，粒度往往難以確定，常由研究人員根據任務需求選擇表征方式。基于樹和圖的方法在建模時相對復雜，識別大規模程序代碼中的算法時，時間復雜度和空間復雜度會大幅度上升。隨著深度學習技術的發展，將其應用于程序算法識別逐漸成為趨勢，但在深入挖掘程序代碼信息的同時，如何降低運算開銷也十分重要。

4.2 構造能夠保持代碼多種特性的程序算法識別大模型

相較于自然語言，程序設計語言具有更多特性。首先，程序代碼可以表示為AST，具有強結構性；其次，程序代碼具有更加明顯的環境相關性，當程序代碼中的元素脫離上下文環境時，其語義信息可能丟失；最后，程序代碼具備長依賴性，例如程序代碼中的變量，有的定義于代碼首，卻用于代碼尾，再如局部變量和方法，只用于局部區域，這也加長了上下文的直接依賴。而在表征程序代碼時可能會破壞這種特性，不利于程序語義信息的挖掘。目前，這一問題已經引起研究人員的注意，逐步將基于自注意力機制的神經網絡大模型Transformer用于代碼表征從而緩解長依賴等問題。由于大模型采用了大量程序設計語言描述的語料訓練模型，使其學到了一些有關程序設計語言的語法、語義和結構等，具備了一定的程序算法理解能力。未來，如何充分利用大模型針對程序代碼所具備的特性進一步構造適用于程序算法識別任務的代碼大模型，是一項非常值得研究的內容。

4.3 建立適用于程序算法識別任務的評估指標

在對不同的程序算法識別方法進行評估時，一方面，所采用的評估指標也各不相同，不利于橫向比較各個方法與模型的優劣。另一方面，目前常用的評估指標如精確率、召回率等主要應用于自然語言處理領域，對于程序算法識別領域是否適用還需進一步探究。此外，在使用傳統指標評價代碼大模型時，評估效果可能過高，或許難以滿足大模型的評價需求。因此，如何從反映程序算法識別結果的準確性、完整性、魯棒性等方面，深入探索這一任務的評估方向、探討現有評估指標的適用性、設立統一的評估指標是一項亟待解決的問題。

4.4 打破模態壁壘以更加高效地表征程序代碼

跨模態表征能夠通過利用多模態數據之間的互補性剔除冗余內容，獲取更有效的特征表示［60］。當前的程序算法識別任務，既能夠基于代碼文本，又能夠利用融合自然語言文本和代碼文本雙模態的數據，還可以通過代碼圖像予以實現，但尚未擴展至多模態數據。未來如何充分融合代碼文本、自然語言文本與代碼圖像等多模態資源，通過跨模態表征手段進一步捕捉更高效的代碼特征表示，在提升代碼自身特征利用率以及程序算法識別精確率的同時，降低計算資源為模態擴展能力帶來的限制是一個值得探索的方向。

針對上述問題，仍然需要研究者們付出堅持不懈的努力，打破現有方法自身局限性，減少甚至消除表征時對于程序代碼特性的破壞，采用多模態大模型學習程序代碼表征，充分利用其中所蘊涵的更深層次的信息，通過統一的評估指標對各個方法與模型展開評價，讓程序算法識別任務更好地服務于程序理解、軟件工程和編程教育等行業。

5 結束語

程序算法識別以自動化理解程序算法為主要研究目標，推動了軟件工程、編程教育等眾多領域快速發展，目前程序算法識別方法主要分為基于知識表示、基于信息檢索以及基于代碼表征的方法三類。本文首先對算法、程序算法的概念進行梳理，并且對基于知識表示和基于信息檢索的方法進行簡介；其次，將基于代碼表征的方法劃分為基于序列、基于樹和基于圖的方法展開詳細闡述，總結對比了各個方法的優勢與劣勢；接著，對程序算法識別任務在代碼變換與優化、程序診斷及驗證、程序理解和編程教育等多個方面的應用進行介紹；最后，針對程序算法識別任務中尚存的缺陷從四個方面提出展望，期待程序算法識別任務進一步推動多個領域高質量地發展。

參考文獻：

［1］Wirth N. Algorithms+data structures=programs［M］. USA： Prentice Hall PTR， 1978.

［2］Shao Yichao， Huang Zhiqiu， Li Weiwei， et al. Fast code recommendation via approximate sub-tree matching［J］. Frontiers of Information Technology & Electronic Engineering， 2022，23（8）： 1205-1216.

［3］魏敏， 張麗萍. 代碼搜索方法研究進展［J］. 計算機應用研究， 2021，38（11）： 3215-3221，3230. （Wei Min， Zhang Liping. Research progress of code search methods［J］. Application Research of Computer， 2021，38（11）： 3215-3221，3230.）

［4］魯強， 李效戀， 王智廣. 程序算法識別研究綜述［J］. 計算機應用， 2012，32（10）： 2863-2868. （Lu Qiang， Li Xiaolian， Wang Zhiguang. Survey on program algorithm recognition research［J］. Journal of Computer Applications， 2012，32（10）： 2863-2868.）

［5］唐良榮， 唐建湘， 范豐仙， 等. 計算機導論： 計算思維和應用技術 ［M］. 北京： 清華大學出版社， 2015. （Tang Liangrong， Tang Jianxiang， Fan Fengxian， et al. Introduction to computer science： computational thinking and applied technology［M］. Beijing： Tsinghua University Press， 2015.）

［6］Hill R K. What an algorithm is［J］. Philosophy & Technology， 2016，29（1）： 35-59.

［7］郝寧湘. 丘奇——圖靈論點與認知遞歸計算假說［J］. 自然辯證法研究， 1997，13（11）： 19-23. （Hao Ningxiang. Church Turing’s argument and the hypothesis of cognitive recursive computing［J］. Research on Dialectics of Nature， 1997，13（11）： 19-23.）

［8］Knuth D E. The art of computer programming［M］. ［S.l.］： Pearson Education， 1997.

［9］嚴蔚敏， 李冬梅， 吳偉民. 數據結構［M］. 北京： 人民郵電出版社： 2015. （Yan Weimin， Li Dongmei， Wu Weimin. Data structure［M］. Beijing： People’s Post and Telecommunications Publishing House， 2015.）

［10］Murray W R. Automatic program debugging for intelligent tutoring systems［M］. ［S.l.］： Morgan Kaufmann Publishers Inc.，1989.

［11］Johnson W L， Soloway E. PROUST： knowledge-based program understanding［J］. IEEE Trans on Software Engineering， 1985， SE-11（3）： 267-275.

［12］Abd-El-Hafiz S K. Effects of decomposition techniques on knowledge-based program understanding［C］//Proc of Proc International Confe-rence on Software Maintenance. Piscataway， NJ： IEEE Press， 1997： 21-30.

［13］Abd-El-Hafiz S K. Evaluation of a knowledge-based approach to program understanding［C］//Proc of Proc of International Conference on Software Maintenance. Piscataway， NJ： IEEE Press， 1996： 275-284.

［14］王甜甜， 許家歡， 王克朝， 等. 示例演化驅動的學生程序自動修復［J］. 軟件學報， 2019，30（5）： 1256-1268. （Wang Tiantian， Xu Jiahuan， Wang Kechao， et al. Example-evolution-driven automatic repair of student programs［J］. Journal of Software， 2019，30（5）： 1256-1268.）

［15］Harandi M T， Ning J Q. Knowledge-based program analysis［J］. IEEE Software， 1990，7（1）： 74-81.

［16］Wang Shaowei， Lo D， Xing Zhenchang， et al. Concern localization using information retrieval： an empirical study on Linux kernel［C］//Proc of the 18th Working Conference on Reverse Engineering. Pisca-taway， NJ： IEEE Press， 2011： 92-96.

［17］Salton G， Wong A， Yang C S. A vector space model for automatic indexing［J］. Communications of the ACM， 1975， 18（11）： 613-620.

［18］Marcus A， Maletic J I， Sergeyev A. Recovery of traceability links between software documentation and source code［J］. International Journal of Software Engineering and Knowledge Engineering， 2005，15（5）： 811-836.

［19］Poshyvanyk D， Gueheneuc Y G， Marcus A， et al. Feature location using probabilistic ranking of methods based on execution scenarios and information retrieval［J］. IEEE Trans on Software Enginee-ring， 2007，33（6）： 420-432.

［20］唐煥玲， 衛紅敏， 王育林， 等. 結合LDA與word2vec的文本語義增強方法［J］. 計算機工程與應用， 2022，58（13）： 135-145. （Tang Huanling， Wei Hongmin， Wang Yulin， et al. Text semantic enhancement method combining LDA and word2vec［J］. Computer Engineering and Applications， 2022，58（13）： 135-145.）

［21］李政亮， 陳翔， 蔣智威， 等. 基于信息檢索的軟件缺陷定位方法綜述［J］. 軟件學報， 2021，32（2）： 247-276. （Li Zhengliang， Chen Xiang， Jiang Zhiwei， et al. Survey on information retrieval-based software bug localization methods［J］. Journal of Software， 2021， 32（2）： 247-276.）

［22］Maletic J I， Marcus A. Using latent semantic analysis to identify similarities in source code to support program understanding［C］//Proc of the 12th IEEE Internationals Conference on Tools with Artificial Intelligence. Piscataway， NJ： IEEE Press， 2000： 46-53.

［23］岳雷， 崔展齊， 陳翔， 等. 基于歷史缺陷信息檢索的語句級軟件缺陷定位方法［J/OL］. 軟件學報. （2023-09-08）. https：//kns.cnki.net/kcms/ detail/11.2560.TP.20230906.1508.001.html. （Yue Lei， Cui Zhanqi， Chen Xiang， et al. Statement level software bug localization based on historical bug information retrieval［J/OL］. Journal of Software. （2023-09-08）. https：//kns.cnki.net/kcms/detail/11.2560. TP.20230906.1508.001.html.）

［24］Jiang Lingxiao， Misherghi G， Su Zhendong， et al. DECKARD： sca-lable and accurate tree-based detection of code clones ［C］//Proc of the 29th International Conference on Software Engineering. Pisca-taway， NJ： IEEE Press， 2007： 96-105.

［25］Hindle A， Barr E T， Gabel M， et al. On the naturalness of software［J］. Communications of the ACM， 2016， 59（5）： 122-131.

［26］White M， Tufano M， Vendome C， et al. Deep learning code fragments for code clone detection［C］//Proc of the 31st IEEE/ACM International Conference on Automated Software Engineering. Pisca-taway， NJ： IEEE Press， 2016： 87-98.

［27］Nievergelt J. On the time required for timing： the halting problem rephrased［J］. IEEE Trans on Computers， 1970，100（5）： 458-459.

［28］張祥平， 劉建勛. 基于深度學習的代碼表征及其應用綜述［J］. 計算機科學與探索， 2022，16（9）： 2011-2029. （Zhang Xiangping， Liu Jianxun. Overview of deep learning-based code representation and its applications［J］. Computer Science and Exploration， 2022，16（9）： 2011-2029.）

［29］張冬梅， 陳永樂， 楊玉麗. 基于分層特征的代碼克隆檢測方法［J］. 計算機工程， 2021，47（10）： 125-131. （Zhang Dongmei， Chen Yongle， Yang Yuli. Code clone detection method based on hie-rarchical feature［J］. Computer Engineering， 2021，47（10）： 125-131.）

［30］Feng Zhangyin， Guo Daya， Tang Duyu， et al. CodeBERT： a pre-trained model for programming and natural languages［EB/OL］. （2020-09-18）. https：//arxiv.org/abs/2002.08155.

［31］成思強， 劉建勛， 彭珍連， 等. 以CodeBERT為基礎的代碼分類研究［J］. 計算機工程與應用， 2023，59（24）： 277-288. （Cheng Siqiang， Liu Jianxun， Peng Zhenlian， et al. CodeBERT based code classification method［J］. Computer Engineering and Applications， 2023，59（24）： 277-288.）

［32］Wang Yue， Wang Weishi， Joty S， et al. Codet5： identifier-aware unified pre-trained encoder-decoder models for code understanding and generation ［EB/OL］. （2021-09-02）. https：//arxiv.org/abs/2109.00859.

［33］Huang Lu， Xue Jingfeng， Wang Yong， et al. EAODroid： Android malware detection based on enhanced API order［J］. Chinese Journal of Electronics， 2023， 32（5）： 1169-1178.

［34］李玫， 高慶， 馬森， 等. 面向代碼相似性檢測的相似哈希改進方法 ［J］. 軟件學報， 2021，32（7）： 2242-2259. （Li Mei， Gao Qing， Ma Sen， et al. Enhanced simhash algorithm for code similarity detection［J］. Journal of Software Science， 2021， 32（7）： 2242-2259.）

［35］謝春麗， 梁瑤， 王霞. 深度學習在代碼表征中的應用綜述［J］. 計算機工程與應用， 2021，57（20）： 53-63. （Xie Chunli， Liang Yao， Wang Xia. Survey of deep learning applied in code representation［J］. Computer Engineering and Applications， 2021， 57（20）： 53-63.）

［36］魏敏， 張麗萍， 閆盛. 基于程序向量樹和聚類的學生程序算法識別方法［J］. 計算機工程與設計， 2022，43（10）： 2790-2798. （Wei Min， Zhang Liping， Yan Sheng. Student program algorithm recognition based on program vector tree and clustering［J］. Compu-ter Engineering and Design， 2022， 43（10）： 2790-2798.）

［37］彭斌， 李征， 劉勇， 等. 基于卷積神經網絡的代碼注釋自動生成方法［J］. 計算機科學， 2021，48（12）： 117-124. （Peng Bin， Li Zheng， Liu Yong， et al. A method for automatica code comments generation method based on convolutionalneural networks［J］. Computer Science， 2021， 48（12）： 117-124.）

［38］龔丹， 王甜甜， 蘇小紅， 等. 基于軟件歷史倉庫和抽象語法樹的相似缺陷識別方法［J］. 系統工程與電子技術， 2020，42（10）： 2399-2408. （Gong Dan， Wang Tiantian， Su Xiaohong， et al. Identification method of similar bugs based on software repository and abstract syntax tree［J］. Systems Engineering and Electronic Technology， 2020， 42（10）： 2399-2408.）

［39］Zhang Jian， Wang Xu， Zhang Hongyu， et al. A novel neural source code representation based on abstract syntax tree［C］//Proc of the 41st International Conference on Software Engineering. Piscataway， NJ： IEEE Press， 2019： 783-794.

［40］金巖磊， 秦冠軍， 姜凱， 等. 基于結構和語義的代碼分類以及聚類方法［J］. 計算機應用與軟件， 2023，40（7）： 1-6，33. （Jin Yanlei， Qin Guanjun， Jiang Kai， et al. Code classification and clustering methods based on structure and semantics information［J］. Computer Applications and Software， 2023，40（7）： 1-6，33.）

［41］Hua Wei，Liu Guangzhong.Transformer-based networks over tree structures for code classification［J］. Applied Intelligence， 2022，52： 8895-8909.

［42］Zhang Aiping， Fang Liming， Ge Chunpeng， et al. Efficient Transformer with code token learner for code clone detection［J］. Journal of Systems and Software， 2023， 197： 111557.

［43］楊克， 賀也平， 馬恒太， 等. 精準執行可達性分析： 理論與應用［J］. 軟件學報， 2018， 29（1）： 1-22. （Yang Ke，He Yeping，Ma Hengtai，et al. Precise execution reachability analysis：theory and app-lication［J］. Journal of Software， 2018，29（1）： 1-22.）

［44］金芝， 劉芳， 李戈. 程序理解： 現狀與未來［J］. 軟件學報， 2019， 30（1）： 110-126. （Jin Zhi， Liu Fang， Li Ge. Program comprehension： present and future［J］. Journal of Software， 2019， 30（1）： 110-126.）

［45］梁瑤， 謝春麗， 王文捷. 基于圖嵌入的代碼相似性度量［J］. 計算機科學， 2022，49（S2）： 801-806. （Liang Yao， Xie Chunli， Wang Wenjie. Code similarity measurement based on graph embedding［J］. Computer Science， 2022， 49（S2）： 801-806.）

［46］肖添明， 管劍波， 蹇松雷， 等. 基于代碼屬性圖和Bi-GRU的軟件脆弱性檢測方法［J］. 計算機研究與發展， 2021，58（8）： 1668-1685. （Xiao Tianming， Guan Jianbo， Jian Songlei， et al. Software vulnerability detection method based on code property graph and Bi-GRU［J］. Computer Research and Development， 2021， 58（8）： 1668-1685.）

［47］Cao Sicong， Sun Xiaobing， Bo Lili， et al. BGNN4VD： constructing bidirectional graph neural-network for vulnerability detection［J］. Information and Software Technology， 2021， 136： 106576.

［48］Guo Daya， Ren Shuo， Lu Shuai， et al. GraphCodeBERT：pre-training code representations with data flow［EB/OL］.（2021-09-13）.https：//arxiv.org/abs/2009.08366.

［49］Ben-Nun T， Jakobovits A S， Hoefler T. Neural code comprehension： a learnable representation of code semantics［C］//Proc of the 32nd International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2018： 3589-3601.

［50］謝春麗， 藺疆旭， 劉小洋， 等. 改進的卷積神經網絡源代碼相似性度量方法［J］. 應用數學和力學， 2019， 40（11）： 1235-1245. （Xie Chunli， Lin Jiangxu， Liu Xiaoyang， et al. Improved convolutional neural network source code similarity measurement method［J］. Applied Mathematics and Mechanics， 2019， 40（11）： 1235-1245.）

［51］Ragkhitwetsagul C， Krinke J， Marnette B. A picture is worth a thousand words： code clone detection based on image similarity［C］//Proc of the 12th International Workshop on Software Clones. Pisca-taway， NJ： IEEE Press， 2018： 44-50.

［52］張丹丹， 宋亞飛， 劉曙. MalMKNet： 一種用于惡意代碼分類的多尺度卷積神經網絡［J］. 電子學報， 2023， 51（5）： 1359-1369. （Zhang Dandan， Song Yafei， Liu Shu. MalMKNet： a multi-scale convolutional neural network used for malware classification［J］. Journal of Electronic Science， 2023， 51（5）： 1359-1369.）

［53］鄭玨， 歐毓毅. 基于卷積神經網絡與多特征融合惡意代碼分類方法［J］. 計算機應用研究， 2022，39（1）： 240-244. （Zheng Jue， Ou Yuyi. Malware classification method based on convolutional neural network and multi-feature fusion［J］. Application Research of Computers， 2022， 39（1）： 240-244.）

［54］張學令. 程序優化與程序變換方法的研究［D］. 合肥： 中國科學技術大學， 2014. （Zhang Xueling. The research on program optimization and program trans94ec4def9f404eeebaa44f1713c7fc7919c1ef93c6004adcef67e9705c805919formation methods［D］. Hefei： University of Science and Technology of China， 2014.）

［55］Alluru K， Jeganathan L. Code optimizations for parallelization of programs using data dependence identifier［J］. International Journal of Advanced Computer Science and Applications， 2021，12（10）： 837-846.

［56］陳小全， 薛銳. 程序漏洞： 原因、利用與緩解——以C和C++語言為例［J］. 信息安全學報， 2017， 2（4）： 41-56. （Chen Xiaoquan， Xue Rui. Cause， exploitation and mitigation of program vulnerability—C and C++ language as an example［J］. Journal of Information Security， 2017， 2（4）： 41-56.）

［57］徐俊潔. 多故障程序的概率診斷方法研究［D］. 大連： 大連海事大學， 2016. （Xu Junjie. Probabilistic diagnosis methods for multi-fault programs［D］. Dalian： Dalian Maritime University， 2016.）

［58］趙亮， 陳志奎. 大數據算法庫教學實驗平臺設計與實現［J］. 實驗技術與管理， 2020，37（6）： 197-201，206. （Zhao Liang， Chen Zhikui. Design and realization of teaching and experimental platform for big data algorithm library［J］. Experimental Technology and Management， 2020， 37（6）： 197-201，206.）

［59］Gao Lei， Wan Bo， Fang Cheng， et al. Automatic clustering of diffe-rent solutions to programming assignments in computing education［C］//Proc of ACM Conference on Global Computing Education. New York： ACM Press， 2019： 164-170.

［60］劉華峰， 陳靜靜， 李亮， 等. 跨模態表征與生成技術［J］. 中國圖象圖形學報， 2023， 28（6）： 1608-1629. （Liu Huafeng， Chen Jingjing， Li Liang， et al. Cross-modal representation learning and generation ［J］. Chinese Journal of Image and Graphics， 2023， 28（6）： 1608-1629.）