【論文紹介】[2019] A novel neural source code representation based on abstract syntax tree


原論文 

[223, P82], 2019
[Cited by 618 (when 2024/2)]
メモ:ソースコード表現のための新しい抽象構文木(AST)ベースのニューラルネットワーク(ASTNN)を提案。


概要

・機械学習技術を活用してプログラムを分析することが注目される中で、コード断片を適切に表現して後続の解析を行うことが1つの重要な問題となる。従来の情報検索ベースの方法では、プログラムを自然言語テキストとして扱うことが一般的であり、これによりソースコードの重要な意味情報が見落とされる可能性がある。

・最近の研究では、抽象構文木(AST)ベースのニューラルモデルが、ソースコードをよりよく表現できることが示されている。ただし、ASTのサイズは通常大きく、既存のモデルは長期依存の問題に対して脆弱である。

・本論文では、ソースコード表現のための新しいASTベースのニューラルネットワーク(ASTNN)を提案。

・従来のモデルが全体のAST上で動作するのに対し、ASTNNはそれぞれの大きなASTを小さな文ツリーのシーケンスに分割する。

・文のレキシカル(字句的)および構文的知識を捉えることで、分割した文ツリーをベクトルにエンコードする。

・文のベクトルのシーケンスに基づいて、双方向RNNモデルが文の自然さを活用するために用いられ、さらに最終的にコード断片のベクトル表現を生成する。

・本論文の手法を、2つの一般的なプログラムを理解するためのタスクである、ソースコード分類とコードクローン検出に適用した。これらの2つのタスクの実験結果は、本論文のモデルが最先端のアプローチに優れていることを示している。


導入

・ソフトウェア開発とメンテナンスの向上のために、ソースコード分類、コードクローン検出、欠陥予測、およびコード要約などの多くのソフトウェアエンジニアリング手法が提案されている。これらのすべての手法に共通する主な課題は、ソースコードを効果的に表現し、ソースコードに埋め込まれた構文的および意味的情報を捉える方法である。

・情報検索(IR)などの従来のアプローチでは、コード断片を自然言語テキストとして扱い、トークンに基づいてモデル化する。たとえば、プログラムはコードクローン検出、バグのローカライズ、コード著者分類などのためにトークンのシーケンスまたはトークンの袋で表現される。さらに、多くの研究者がソースコードを分析するために潜在的意味索引(LSI)や潜在ディリクレ配分(LDA)を使用している。

・ただ、これらのアプローチの共通の問題は、基礎となるコーパス(つまり、ソースコード)が自然言語テキストで構成されていると仮定していることである。コード断片はプレーンテキストと何か共通点があるかもしれないが、それらはより豊かで明示的な構造情報を持っているため、単純なテキストベースまたはトークンベースの方法で扱うべきではない。

・最近の研究では、構文知識がソースコードのモデリングにおいて従来のトークンベースの方法よりも大きな寄与をし、より良い表現を得られることを強力に示している。これらのアプローチでは、抽象構文木(AST)と再帰型ニューラルネットワーク(RvNN)、木構造CNN、またはTree-LSTMを組み合わせて、レキシカル(つまり、識別子などのASTの葉ノード)と構文的(つまり、WhileStatementなどのASTの非葉ノードの文法構造)情報の両方を捉える。

・このようなASTベースのニューラルモデルは効果的であるが、主に2つの制約がある。第一に、NLPの長いテキストと同様に、これらの木構造のニューラルモデルは、トレーニング中に勾配が極小化してしまう勾配消失問題にも弱い。たとえば、共通のCおよびJavaのコード断片のASTの最大ノード数/深さは、それぞれ7,027/76および15,217/192である。結果として、AST全体を下から上に走査してエンコードする方法またはスライディングウィンドウ技術を使用する方法は、長期的なコンテキスト情報を失う可能性がある。第二に、これらのアプローチはASTを変換するか、ASTを簡素化して効率化するためにASTを直接フルバイナリツリーとして扱いますが、これによりソースコードの元の構文構造が破壊され、ASTがさらに深くなる。変換された深いASTは、ニューラルモデルがより現実的で複雑な意味を捉える能力を弱める。

・上記のASTベースのニューラルネットワークの制限を克服するための1つの解決策は、明示的な(長期的な)制御フローとデータ依存グラフを導入し、ソースコードを表現するためにグラフ埋め込み技術を利用することである。たとえば、最近の研究では、遠隔の場所で同じ変数や関数によって引き起こされる長距離依存関係を考慮している。別の研究では、コード断片の制御フローグラフ(CFG)を直接構築している。しかし、上記の研究に示されているように、正確で手順間のプログラム依存グラフ(PDG)(つまり、制御フローとデータフローの依存関係)は通常、コンパイルされた中間表現またはバイトコードに依存しており、コンパイルできないおよび不完全なコード断片には適用できない。このような制限は、任意のコード断片を含む多くの領域でコード表現の応用を妨げる。

・本論文では、コンパイル可能でなくてもよいコード断片を表現するための新しいアプローチを提案する。このアプローチはASTベースのニューラルネットワーク(ASTNN)と呼ばれ、1つのコード断片の大きなASTを文レベルで一連の小さな木に分割し、すべての文ツリーにツリーベースのニューラル埋め込みを行う。これにより、文のベクトルが生成され、レキシカルおよび文レベルの構文的知識を表現できる。ここでの文とは、プログラム言語仕様で定義された文ASTノードを指す。また、MethodDeclarationも特別な文ノードとして扱う。
・たとえば、図1はオープンソースプロジェクトからのコード断片を示しています。行7から行15までのコードスニペットには完全なTry文が含まれており、行5から行6までのコードスニペットには変数sbを初期化するLocalVariable文のみが含まれています。Try文のようなヘッダーとボディ内の他の文を含む文の場合、ヘッダーとすべての含まれる文を分割します。この方法で、大きなASTが短い一連の小さな文ツリーに分解されます。文をエンコードし、文間の順次依存関係をベクトルに変換するために再帰型ニューラルネットワーク(RNN)を使用します。このようなベクトルはソースコードの自然さを捉え、ニューラルソースコード表現として機能します。具体的には、まず、コード断片からASTを構築し、AST全体を小さな文ツリー(1つの文のASTノードで構成され、Statementノードをルートとするツリー)に分割します。次に、文ツリー上の多方向ステートメントを再帰的にエンコードして、文レベルのレキシカルおよび構文的情報を捉え、文ベクトルで表現します。最後に、文ベクトルのシーケンスに基づいて、双方向ゲート型再帰ユニット(GRU)を使用して、文の順次的自然さを活用し、最終的にコード断片のベクトル表現を得ます。

・要約すると、私たちが提案するニューラルソースコード表現は、最先端のASTベースのニューラルモデルよりもソースコードに関する構文的および意味的情報を学習することを目指している。このソースコードの表現方法は汎用的であり、ソースコード分類やコードクローン検出などの多くのプログラム理解に関連するタスクに使用できる。
・我々は、公開されているベンチマークでこれらの2つのタスクに関する実験を行い、最先端の手法と比較しました。実験結果は、我々のモデルがより効果的であることを示しています。たとえば、ソースコード分類では、我々の手法により、精度が94%から98.2%に向上しました。クローン検出では、我々の手法により、F1値が82%から93.8%、および59.4%から95.5%に向上しました。

・私たちの主な貢献は次のとおりです:

私たちは新しいニューラルソースコード表現を提案し、文のレベルでのレキシカル、構文的知識、および文の自然さを捉えることができます。
私たちはこの表現を2つの一般的なプログラム理解タスク(コード分類およびクローン検出)に適用しました。実験結果は、私たちの手法が最先端の方法を改善できることを示しています。
この論文の残りの部分は次のように構成されています。セクションIIでは背景を紹介します。セクションIIIでは私たちのアプローチを説明します。セクションIVでは、私たちのニューラルソースコード表現の応用について説明します。セクションVでは実験結果を提供します。関連する研究と信頼性に関する議論はそれぞれセクションVIとセクションVIIで行われます。最後に、セクションVIIIで私たちの研究をまとめます。


背景

抽象構文木(AST)

・抽象構文木(AST)は、ソースコードの抽象的な構文構造を表現するための木の一種であり、プログラミング言語やソフトウェアエンジニアリングツールで広く使用されている。

・図1(b)に示されているように、ASTのノードはソースコードの構成要素や記号に対応している。プレーンなソースコードと比較して、ASTは抽象的であり、句読点や区切り文字などのすべての詳細を含んでいないが、ASTはソースコードのレキシカル情報や構文構造、例えば図1(b)のmethod name readTextや制御フロー構造WhileStatementを記述するのに使用できる。

・一部の研究では、ソースコード検索、プログラム修復、およびソースコードの差分検出などのために、ASTをトークンベースの方法で直接使用している。ただ、トークンベースのアプローチの限界により、これらの方法はソースコードの構文情報をほとんど捉えることができない。

木ベースのニューラルネットワーク

・最近、木ベースのニューラルネットワーク(TNNs)が提案され、ASTを入力として受け入れるようになった。与えられた木に対して、TNNsはボトムアップの再帰的なノード埋め込みを計算することでそのベクトル表現を学習する。
・AST向けの最も代表的な木ベースのモデルには、再帰型ニューラルネットワーク(RvNN)、木ベースのCNN(TBCNN)、および木ベースの長短期記憶(Tree-LSTM)がある。

1) 再帰型ニューラルネットワーク(RvNN):

・RvNNは、自然言語や画像解析の再帰構造向けに最初に提案された。具体的には、与えられた木構造において、1つの親ノードy1が2つの子ノード(c1、c2)を持つものとする。ここで、c1とc2は単語埋め込みまたはノードの中間ベクトル表現である。ノードy1のベクトルは次の式で計算される。
p = f(W(1)[c1; c2] + b(1))
ただし、W(1)はパラメータ行列であり、fは要素ごとの活性化関数、b(1)はバイアス項である。

このベクトル表現の品質を評価するために、復号層が使用され、子ノードを再構築する:

[1;2]=(2)+(2)

その後、訓練損失は、()=1^122+2^222で測定されます。この方法で、RvNNは木全体にわたって再帰的にパラメータを計算し最適化し、根ノードの最終的なベクトルは与えられた木を表します。RvNNに基づいて、コードクローンを検出するためにASTを自動的にエンコードする再帰オートエンコーダ(RAE)が組み込まれています。ここでは、入力の固定サイズのためにASTが完全なバイナリ木に変換されます。

2) 木ベースの畳み込みニューラルネットワーク:

TBCNNは、ソースコード分類などの教師あり学習のために木構造上で畳み込み演算を行います。そのコアモジュールは、ASTベースの畳み込み層であり、固定深度の特徴検出器をAST全体にスライドさせて適用します。この手順は次のように定式化されます:

=tanh(=1conv,+conv)

ここで、1,,は各スライドウィンドウ内のノードのベクトルであり、conv,はパラメータ行列であり、convはバイアスです。TBCNNは、局所性を向上させるためにいくつかのグローバル情報を統合するためのボトムアップエンコーディング層を採用しています。元のASTのノードには2つ以上の子がある場合がありますが、畳み込みの固定サイズのため、TBCNNはASTを連続した完全なバイナリ木として扱います。

3) 木ベースの長期・短期記憶モデル(Tree-LSTM):

ツリー構造のトポロジーをモデル化するためのLSTMの一般化です。通常のLSTMとは異なり、Child-Sum Tree-LSTMは現在の入力を再帰的に子ノードの状態と組み合わせ、木構造全体での状態更新を行います。CDLHは、コード断片の表現を学習するためにTree-LSTMを使用し、コード断片がASTに解析されるクローン検出に使用されます。子ノードの数が可変である場合、ASTは完全なバイナリツリーに変換されます。ボトムアップの計算の後、ASTのルートノードベクトルがコード断片を表すために使用されます。


これらの3つの木ベースの方法には、2つの主な制限があります。まず、木のトポロジーに基づいた勾配ベースのトレーニング中に、勾配は構造を通じて逆伝播によって計算されます。しかし、プログラムの複雑さ、特に入れ子の構造により、ASTの構造は通常大きく深くなります。したがって、葉ノードからルートノードへのボトムアップの計算は、勾配の消失問題を経験し、長距離の依存関係を捉えるのが難しくなります。これにより、葉ノードの識別子など、ルートノードから遠いノードが持つ一部の意味が失われる可能性があります。第二に、既存の木ベースの方法では、ASTをバイナリツリーとして扱います。これは、親ノードの3つ以上の子ノードを新しい部分木に移動して簡略化することにより、ソースコードの元の意味が変わり、長期の依存性問題がより深刻になります。たとえば、CDLHは、クローン検出の1つの公開ベンチマークで57%のF1値しか持つことができず、NLPの研究では、木のサイズと深さが重要であり、性能に大きな影響を与えることが示されています。

本論文の手法

このセクションでは、ASTベースのニューラルネットワーク(ASTNN)を紹介します。ASTNNの全体的なアーキテクチャは図2に示されています。まず、ソースコード断片をASTに解析し、各ASTをステートメントツリーのシーケンス(STツリー、ステートメントノードをルートとし、それに対応するASTノードを含むツリー)に分割するための前順序走査アルゴリズムを設計します(図1参照)。すべてのSTツリーはステートメントエンコーダによってベクトルにエンコードされ、それぞれをe1、···、etと表します。次に、Bidirectional Gated Recurrent Unit [35](Bi-GRU)を使用して、ステートメントの自然さをモデル化します。Bi-GRUの隠れ状態はプーリングによって単一のベクトルにサンプリングされ、これがコード断片の表現です。

A. ASTの分割とSTツリーシーケンスの構築

最初に、既存の構文解析ツールによってソースコード断片を大きなASTに変換することができます。各ASTについて、ステートメントの粒度で分割し、プリオーダー走査によってステートメントツリーのシーケンスを抽出します。

形式的には、ASTのTとステートメントASTノードの集合Sが与えられた場合、AST内の各ステートメントノードs ∈ Sはソースコードの1つのステートメントに対応する。MethodDeclarationを特別なステートメントノードと見なし、したがってS = S∪{MethodDeclaration}とする。

・図1に示すように、ネストされたステートメントの場合、ヘッダーと本体を分割するためのブロックとしてP = {block, body}のセットを定義する。ここで、blockはTryやWhileステートメントなどのネストされたステートメントのヘッダーと本体を分割するために使用され、bodyはメソッド宣言のために使用される。ステートメントノードs ∈ Sのすべての子孫をD(s)で示します。s ∈ Sの任意のd ∈ D(s)について、sからdへの1つのパスに1つのノードp ∈ Pが存在する場合、ノードdはステートメントsの本体の1つのステートメントに含まれていることを意味します。ノードdをsのサブステートメントノードと呼びます。次に、ステートメントノードs ∈ Sによって根付けられたステートメントツリー(STツリー)は、ノードsとそのサブステートメントノードを除くすべての子孫からなるツリーです。たとえば、図1(b)のMethodDeclarationによって根付けられた最初のSTツリーは、点線で囲まれており、"static"、"public"、"readText"などのヘッダーパートを含み、ボディ内の2つのLocalVariable、1つのTry、および1つのReturnステートメントのノードを除外します。1つのSTツリーのノードには3つ以上の子ノードがある場合があるため、バイナリツリーと区別するために、それを多方向STツリーとも呼びます。このようにして、1つの大きなASTは、重複せず、多方向のSTツリーのシーケンスに分解されます。
ASTの分割とSTツリーシーケンスの構築は、トラバーサーとコンストラクタによって簡単に行われます。トラバーサーは、ASTを深さ優先で前順序のウォークで各ノードを訪れ、コンストラクタは再帰的にSTツリーを作成し、それをSTツリーシーケンスに順次追加します。このような方法を用いることで、新しいSTツリーがソースコードの順序に従って追加されることが保証されます。このようにして、ASTNNの生の入力としてSTツリーのシーケンスを取得します。
ASTの分割の粒度の選択は簡単ではありません。この作業ではステートメントツリーを選択しました。ステートメントはソースコードの意味を運ぶための基本的な単位であるためです。また、ASTのノードレベル、中括弧ペア内のコードブロック、および完全なASTなど、他の粒度も試行しました。これらの実験についてはセクションVで議論します。選択された粒度が大きすぎる場合(たとえば、完全なASTの場合)、関連する研究[5]、[6]と同様に、第II節で言及した勾配消失問題が発生する可能性があります。ただし、粒度が小さすぎる場合(例:ASTのノードレベル)、モデルはステートメントの構文的な知識を少なく捉えることができるトークンベースのRNNになる可能性があります。提案されたステートメントレベルの粒度が、STツリーのサイズと構文情報の豊かさの間で良いトレードオフを持つため、実験結果ではこれが最適であることが示されています。

B. Encoding Statements on Multi-way ST-trees

1)ステートメントベクトル:
STツリーが与えられた場合、ステートメントのベクトル表現を学習するために使用されるRvNNベースのステートメントエンコーダーを設計します。
ASTにはさまざまな特別な構文記号があるので、コーパスに対する学習としてASTの前順序走査によってすべての記号を取得する。

記号の教師なしベクトルを学習するためにword2vec [42]を使用する。記号のトレーニング済みの埋め込みは、ステートメントエンコーダーの初期パラメータとして使用される。ASTのすべての葉ノードは識別子などのレキシカル情報を表し、これらはすべてSTツリーの葉ノードにも含まれているため、私たちの記号の埋め込みはレキシカルな知識をよく捉えることができる。

・図1のMethodDeclarationノードによって根付けられた最初のSTツリーを例に取ると、エンコーダーはSTツリーを走査し、現在のノードの記号を新しい入力として再帰的に取り、子ノードの隠れた状態と一緒に計算します。これは図3に示されています。ここでは最初の2つのレベルのみを表示しています。STツリーでは、2つの子ノードであるreadText(つまり、メソッド名)とFormalParameter(つまり、メソッドのパラメータを定義する文法構造)と他の兄弟ノードがMethodDeclarationの意味を豊かにします。[5]、[6]で説明されているように、STツリーをバイナリツリーに変換すると、例えば、readTextのノードを1つの子ノードまたはFormalParameterノードの子孫に移動すると、元の意味が破壊される可能性があります。代わりに、元の多方向STツリーを入力として使用します。

・具体的には、STツリーtが与えられた場合、nを非葉ノード、Cをその子ノードの数とします。最初に、事前に学習された埋め込みパラメータWe ∈ R|V|×d(ここでVは語彙サイズ、dはシンボルの埋め込み次元です)を使用して、ノードnのレキシカルベクトルは次のように得られます: vn = We * xn (1) ここで、xnはシンボルnのワンホット表現であり、vnは埋め込みです。次に、ノードnのベクトル表現は次の式で計算されます: h = σ(Wn * vn + Σi∈[1,C]hi + bn) (2) ここで、Wn ∈ Rd×kは符号化次元kの重み行列であり、bnはバイアス項、hiは各子ノードiの隠れた状態、hは更新された隠れた状態、σはtanhや恒等関数などの活性化関数です。この論文では恒等関数を使用します。同様に、STツリーt内のすべてのノードのベクトルを再帰的に計算し最適化することができます。 さらに、ノードベクトルの最も重要な特徴を決定するために、すべてのノードがスタックにプッシュされ、その後max poolingによってサンプリングされます。つまり、STツリーと対応するステートメントの最終的な表現を式3で得ます。ここで、NはSTツリー内のノードの数です。 et = [max(hi1), ··· , max(hik)], i = 1, ··· , N (3) これらのステートメントベクトルは、ステートメントのレキシカルおよびステートメントレベルの構文情報の両方を捉えることができます。

2)バッチ処理:
大規模データセットでのトレーニング効率を向上させるために、複数のサンプル(つまり、コードフラグメント)を同時にエンコードするバッチ処理アルゴリズムを設計する必要があります。ただし、一般的に、複数のノードを持つSTツリーでのバッチ処理は難しい場合があります。なぜなら、同じバッチ内の親ノードの子ノードの数が異なるためです。例えば、図4のns1が3つの子ノードを持ち、ns2が2つの子ノードを持つ場合、式2を1つのバッチ内で直接計算することは不可能です。この問題を解決するために、アルゴリズム1でバッチサンプルを動的に処理するアルゴリズムを設計しています。
直感的には、親ノードが異なる数の子ノードを持っていても、アルゴリズムは動的に検出し、同じ位置にある可能性のあるすべての子ノードをグループ化し、次に行列演算を利用して各グループの式2の計算をバッチ方式で高速化することができます。アルゴリズム1では、STツリーのLサンプルをバッチ処理し、ルートノード(行4)から幅優先探索を開始します。バッチ内の同じ位置の現在のノードnsに対して、まずバッチで式1を計算し(行10)、次にノードの位置によってすべての子ノードを検出してグループ化します(行12-16)。図4に示されているように、子ノードをその位置に応じて3つのグループに分け、これらのグループを配列リストCとCIに記録します。これらのグループに基づいて、すべての子ノードに対して再帰的にバッチ処理を行います(行17-21)。すべての子ノードの結果を取得した後、バッチで式2を計算し(行22)、バッチ処理されたSTツリーのすべてのノードベクトルをスタックSにプッシュします(行24)。最後に、式3で説明されているプーリングによって、STツリーサンプルと対応するステートメントのベクトルを取得できます(行5)。

C. Representing the Sequence of Statements

STツリーベクトルのシーケンスに基づいて、私たちはGRU [34] を利用して文の自然さを追跡します。また、LSTMの使用とLSTMとGRUの比較の選択肢も、実験で議論されます。 あるコード断片が与えられた場合、そのASTから抽出されたT個のSTツリーがあるとします。Q ∈ RT ×k = [e1, ··· , et, ··· , eT ]で、t ∈ [1, T]は、シーケンス内のエンコードされたSTツリーのベクトルを示します。時刻tにおいて、遷移方程式は以下のようになります: rt = σ(Wret + Urht−1 + br) zt = σ(Wzet + Uzht−1 + bz) h˜t = tanh(Whet + rt  (Uhht−1) + bh) ht = (1 − zt)  ht−1 + zt  h˜t (4) ここで、rtは前の状態の影響を制御するリセットゲート、ztは過去と新しい情報を組み合わせる更新ゲート、h˜tは候補状態であり、前の状態ht−1と線形補間を行って現在の状態htを決定します。Wr、Wz、Wh、Ur、Uz、Uh ∈ Rk×mは重み行列であり、br、bz、bhはバイアス項です。すべての時間ステップの隠れた状態を反復的に計算した後、これらの文の連続的な自然さが得られます。

再帰層の依存情報をより効果的に捉えるために、双方向GRU [34] を採用し、両方向の隠れ状態を連結して新しい状態を形成します。具体的には、以下のようになります: −→ht = −−−→ GRU(et), t ∈ [1, T] ←−ht = ←−−− GRU(et), t ∈ [T, 1] ht = [−→ht , ←−ht ], t ∈ [1, T] (5) 文のエンコーダと同様に、これらの状態の最も重要な特徴は、最大プーリングまたは平均プーリングによってサンプリングされます。異なる文の重要性が直感的に等しくないことを考慮して、例えば、MethodInvocation文内のAPI呼び出しにはより多くの機能情報が含まれる可能性があります[43]、そのため、デフォルトで最大プーリングを使用して最も重要な意味を捉えます。モデルは最終的に、コード断片のベクトル表現として扱われるベクトルr ∈ R2mを生成します。

結論

・本論文で提案したASTベースのニューラルネットワーク(ASTNN)は、文レベルのレキシカルな情報、文レベルの構文的知識、および文の自然さを捉えることができる。

・このモデルは、コード断片の大きなASTを小さな文ツリーのシーケンスに分解し、多方向ステートメントツリーを再帰的にエンコードして文ベクトルを取得し、最終的に文の自然さを活用してコード断片のベクトル表現を学習する。

・ASTNNを2つの一般的なプログラムを理解するためのタスク、つまりソースコード分類とコードクローン検出にて評価した。実験結果は、私たちのモデルが既存の手法を大幅に上回っていることを示している。本論文のコードと実験データは、https://github.com/zhangj1994/astnn で公開されている。今後は、提案されたモデルを異なるプログラミング言語の大規模なデータセットやさまざまなソフトウェアエンジニアリングタスクでさらに評価する。また、ソースコードのより深い意味を捉えるために他のニューラルモデルも検討する。



コメント

このブログの人気の投稿

【論文メモ】A systematic literature review on source code similarity measurement and clone detection: techniques, applications, and challenges

【論文メモ】<2022>コードクローン検索手法の調査

【論文】A Survey on Causal Inference<2021>