日本ソフトウェア科学会第 39 回大会 (2022 年度) 講演論文集

記号実行を利用したセマンティックコードクローン検出
機構
武元 憲将

高田 眞吾

コードのシンタックスの類似度によりコードクローンを検出する手法は多く提案されているが，このような手法ではセマンティックコードクローンの検出は難しい．テスト実行の結果の入出力を比較する手法はセマンティクスを比較する事ができるが，セマンティクスを網羅的に比較するためには適切にテストケースを生成する必要がある．またテ
スト実行の結果の入出力を比較する手法では入出力の比較にあたって引数，返り値の型が異なるような場合への対応，さらに入出力以外のセマンティクスへの対応も課題となる．そこで，それらの課題への対応のための工夫を行う
ことに加え，記号実行を用いて実行パスを考慮したテストケースを生成し入出力の比較を行うことでセマンティックコードクローンを検出する手法を提案する．

シンタックスの類似度によりコードクローンを検出す

1 はじめにるが，セマンティックコードクローンの検出にあたっ

ソフトウェアを開発するにあたってコード中に類似ては誤検知や抜け漏れが発生してしまう．

したコード片（コードクローン）が存在すると保守

本研究では，機能が同一の場合，同一の入力に対しに当たって必要のないコストがかかってしまう．しかて同一の出力を返すという点に着目する．入出力を比し，コードクローンを手作業で検出するのは非常に時較することによりセマンティクスを比較する事ができ間がかかる．そこでコードクローンを検出するためのるが，セマンティクスを網羅的に比較するためには，手法が複数提案されている．そうした手法の多くは，適切な入力の集合を生成する必要がある．そこで，本字句単位の比較を行う手法や，コードの構造をグラフ研究では，入力の生成をテストケース生成と解釈し，で表現しそのグラフを比較するような手法である．そ生成するために記号実行を用いる．また比較にあたっのようなコードクローンの中でも，異なるシンタックては異なる型を持つコードクローンへの対応や返りスで実装されているが機能が同一のコード片は Type値以外の機能にも対応する必要がある．そこで，本研

4 と分類される [5]．この Type 4 に分類されるコード

究では型の違いや返り値以外の機能をも考慮し，記クローンはセマンティックコードクローンとも呼ばれ号実行を用いたテスト実行の結果を利用してテストる．このようなセマンティックコードクローンは実際ケース（入出力の対）を生成し，実行パスごとに入出のソフトウェア開発の現場においても確認されており力の比較を行うことでセマンティックコードクローン[1]，対応が必要である．ところが，字句単位の比較をを検出する手法を提案する．

用いることによりセマンティックコードクローンを検出することは難しい．またコードの構造をグラフで表2 関連研究

現しそのグラフを比較するような手法ではコードの2. 1 CFG，PDG 等のグラフを比較する手法
Wu ら [6] は CFG，Zou ら [7] は PDG を用いて各This is an unrefereed paper. Copyrights belong to theauthors.
Kazusa Takemoto, Shingo Takada, 慶應義塾大学, Keio
University.

コードの構造をグラフで表現し，グラフの構造を比較することによりコードクローンの検出を行う手法を提案した．構造の比較を行うことにより，構造が類似しているようなコードクローンは検出が可能だが，きる．

アルゴリズムが異なり，構造自体が大きく異なるよう•ペア同士の実行パスを網羅するように比較すなセマンティックコードクローンに対応することは難るため完全一致しているかどうかや一部の違い

しい．

も検出（課題 A, B に対応）

•る場合はその値も出力としてみなすことで返り2. 2 実行パスを比較する手法

値以外の機能も考慮（課題 C に対応）

Krutz ら [2] は各コードから実行パスを抽出し，実行パスの比較によりコードクローンの検出を行う手法を提案した．しかし，実行パスの比較のみでは誤検知や抜け漏れが発生する可能性がある．

引数に配列，ポインタ，構造体が含まれてい•型の分類により型が異なるセマンティックコー
ドクローンを検出（課題 D に対応）

次にこれらの特徴について述べる．

3. 2. 1 ペア同士の実行パスを網羅するように比較するため完全一致しているかどうかや一部

2. 3 テスト実行を用いた手法
Li ら [3] はターゲットとなるコードを設定し，返りの違いも検出（課題 A, B に対応）

値と引数の型でマッチング，メソッド名の類似度でセマンティックコードクローンを検出するにあたっマッチングを行い，入出力の比較によりターゲットのては，適切にテストケースを生成する必要がある．そ

コードと機能が同じセマンティックコードクローンのこで，提案手法では記号実行を用いて各関数ごとに検出を行う手法を提案した．テストケース（入出力の実行パスを考慮してテストケースを生成する．また，対）はターゲットとなるコードに対してブランチカバ比較する際にはペア同士でお互いのテストケースをレッジベースのテストを実行することで生成する．

交換してテスト実行を行い，出力の比較を行うことで[3] の課題としては次の A〜D の 4 つの課題を挙げることができる．

網羅的にセマンティクスの比較を行う．

3. 2. 2 引数に配列，ポインタ，構造体が含まれて課題 A 全ての実行パスを網羅的に比較できない．

いる場合はその値も出力としてみなすこ

課題 B 全てのメソッドの網羅率を考慮していない．とで返り値以外の機能も考慮（課題 C に課題 C 明示的な出力以外の副作用を考慮してい対応）ない．
課題 D 引数，返り値の型の違いに対応していない．

セマンティックコードクローンを検出するにあたっては，関数の返り値以外への操作にも対応する必要がある．C 言語においては引数に配列，ポインタ，構造3 提案手法の概要と特徴体が含まれている場合，関数内でそれらへの操作が行

3. 1 提案手法の概要

われた結果，値が変更される可能性がある．その関数

本節では本研究での提案手法について説明する．提呼び出し以降で，その配列，ポインタ，構造体にアク案手法は C 言語を対象とし，入力には関数の集合，出セスした場合，中身が変更されている可能性があるた

力にはセマンティックコードクローンのペアを返す．

め，明示的な出力ではないものの，プログラムに対し提案手法の概要としては記号実行を用いて実行パスて副作用を与えている可能性がある．そこで提案手法ごとのテストケース（入出力の対）を生成し，関数のにおいては引数に配列，ポインタ，構造体が含まれてペアごとにお互いのテストケースを実行し，実行の出いる場合はその値も出力としてみなすことで対応を

力結果を比較することによりセマンティックコードク行う．

ローンの検出を行う．

3. 2. 3 型の分類により型が異なるセマンティックコードクローンを検出（課題 D に対応）

3. 2 提案手法の特徴
提案手法の特徴として次の 3 つを挙げることがでセマンティックコードクローンを検出するにあたっては，引数，返り値の型が異なるような場合にも対応する必要がある．そこで提案手法では型を分類することにより異なる型を持つセマンティックコードクローンの対応を行う．

4. 1. 2 構造体の情報抽出
構造体の情報抽出においては，次の 3 つの情報を抽出する．

•構造体の名前

4 提案手法の実行手順•

各要素の名前提案手法は次の 4 ステップで実行される．

•各要素の型

1.

ターゲット（対象コード）の解析

2.

グループ分け3.

テストケース生成•構造体の名前：B

4.

テストケースの実行結果の比較•

要素 1 の名前：x

次にこれらのステップについて述べる．

•要素 1 の型：int•要素 2 の名前：y•要素 2 の型：long

例えば，構造体 B（ソースコード 2）の情報として次が抽出される．

4. 1 ターゲット（対象コード）の解析
ターゲットの解析を行う．このステップでは次の3 つの情報 を 抽出す る ．情 報 の 抽 出 に あ たって は
CTAGS†1 を利用する．
•関数の情報抽出•構造体の情報抽出•

typedef の情報抽出

ソースコード 2123
4

構造体 B

struct B {int x ;
long y ;};4. 1. 3 typedef の型の情報抽出

次にこれらについて述べる．

typedef の情報抽出においては，次の 2 つの情報を

4. 1. 1 関数の情報抽出
関数の情報抽出においては，次の 3 つの情報を抽出する．

抽出する．

•型の名前型

•

関数の名前

••

返り値の型

例えば，typedef C（ソースコード 3）の情報とし•引数の型て次が抽出される．

例えば，関数 A（ソースコード 1）の情報として次が抽出される．

•関数の名前：A•

返り値の型：int•

引数の型：int
ソースコード 11
2
3
456

•

型の名前：C•型：int
ソースコード 3

1

typedef Ctypedef i n t C

関数 A

int A ( int x ) {i f ( x < 0) {x ∗= −1;}
return x ;}†1 http://ctags.sourceforge.net

4. 2 グループ分け
グループ分けのステップでは引数と返り値の型で関数のグループ分けを行う．この時に引数は順不同とする．グループ分けにあたっては次の 2 種類のグループ分けを行う．

•完全一致したグループ•

型を分類して一致したグループ

生成

次にこれらのグループ分けについて述べる．

4. 2. 1 完全一致したグループ

2.の型が一致した関数が含まれる．関数 A, D, E（ソー生成した入力値をもとにテスト実行を行い入出力のペアを記録

完全一致したグループには引数の個数と型，返り値4. 3. 1 記号実行を行い，実行パスごとの入力値を生成

スコード 1, 4, 5）を比較する例を考えると，引数の個数と型，返り値の型が一致した関数 A, D（ソースそれぞれの関数に対して記号実行を行うことで，各コード 1, 4）が同一のグループにグループ分けされる関数の実行パスごとの入力値を生成する．記号実行でことになる．

は対象のコードを解析し，実行パスを網羅するように，各実行パスに対応するテストケースの入力値を生ソースコード 41234
5
6int D ( int x ) {i f ( x < 0) {x ∗= −1;}
return x ;}ソースコード 5

123456関数 D

KLEE-Float [4] を利用する．また記号実行の結果の解析にあたっては KLEE 2.2†2 に含まれる ktest-toolを利用する．

ソースコード 6関数 E

i n t E ( long x ) {i f ( x < 0) {x ∗= −1;}
return x ;}4. 2. 2 型を分類して一致したグループ
引数，返り値の型が異なるが機能が同一のセマン
ティックコードクローン検出のため，型を分類してグループ分けを行う．型を分類して一致したグループには，次の 2 種類の型の分類を行った後，引数の個数と型，返り値の型が一致した関数が含まれる．

•

int, long, ﬂoat などの数値→ num•

配列，ポインタ→配列とポインタを同じものとして扱う

関数 A, D, E（ソースコード 1, 4, 5）を比較する
例を考えると，int および long が num に分類される
ため，関数 A, D, E（ソースコード 1, 4, 5）が同一のグループにグループ分けされることになる．

4. 3 テストケース生成
テストケース生成のステップでは次の手順を実行することにより，関数ごとにテストケースを生成する．

1.

成することができる．記号実行を行うツールとしては

記号実行を行い，実行パスごとの入力値を123456789関数 F

int F ( int x , int y ) {i f ( x < 0) {x ∗= −1;}i f ( y < 0) {y ∗= −1;}
return x ∗ y ;}関数 F（ソースコード 6）の例を考えると，if 文が2 つあり，それぞれの if 文の分岐の組み合わせとして4 つの実行パスが存在する．記号実行では，それぞれの実行パスに対応する if 文の条件を解き，4 つの実行パスに対応するテストケースの入力値が生成される．ここでは生成された入力値の例を (-1,3), (3,-1),(-1,-1), (3,3) とする．
4. 3. 2 生成した入力値をもとにテスト実行を行い入出力のペアを記録

4. 3. 1 節で生成した入力値を使ってテスト実行を行い，対応する出力を記録することでテストケースを生成する．引数に配列，ポインタ，構造体が含まれている場合はその値も出力とする．
関数 F（ソースコード 6）の例を考えると，4. 3. 1
節で生成した入力値 (-1,3), (3,-1), (-1,-1), (3,3) を用いてテスト実行を行いその出力を記録することで，表†2 https://klee.github.io

表1

表2

関数 F のテストケース例

関数 G のテストケース例

入力値

出力値

入力値

出力値

(-1,3)

3(-1,1)1(3,-1)3(1,1)

1(-1,-1)

1(3,3)

9

表3

関数 F のテスト実行例

入力値

出力値

1 に示すような 4 つの実行パスに対応するテストケー(-1,1)1スが生成される．

(1,1)

1

4. 4 テストケースの実行結果の比較

表4

このステップでは，次の手順を実行することによりセマンティックコードクローンを検出する．

1.

グループ内で全てのペアごとにそれぞれの実行パスに基づくテストを実行

2.

完全一致及び一部のみ異なるペアをセマン

関数 G のテスト実行例

入力値

出力値

(-1,3)

3(3,-1)

3(-1,-1)

1

(3,3)

9

ティックコードクローンとして検出
引数に配列，ポインタ，構造体が含まれている場合は4. 4. 1 グループ内で全てのペアごとにそれぞれのその値も出力とする．また，引数の対応関係も考慮

実行パスに基づくテストを実行

し，全ての引数の対応関係のパターンごとに出力結果

4. 3 節で生成したテストケースを全てのペアごとを比較し，最も一致した出力が多かった引数の対応関にお互いに交換してテスト実行を行う．関数 F，G係をそのペアの引数の対応関係とする．

（ソースコード 6，7）の例では，関数 F（ソースコード 6）が G のテストケース（表 2）を実行し，関数

ソースコード 7

1234567

関数 G

int G ( int x , int y ) {i n t ans = x ∗ y ;i f ( ans < 0 ) {ans ∗= −1;}
return ans ;}G（ソースコード 7）が F のテストケース（表 1）を実行する．関数 F（ソースコード 6）が G のテストケース（表 2）を実行した結果が表 3，関数 G（ソースコード 7）が F のテストケース（表 1）を実行した
結果が表 4 のようになる．

4. 4. 2 完全一致及び一部のみ異なるペアをセマンティックコードクローンとして検出

ここでは，セマンティックコードクローンである関4. 4. 1 節でのテスト実行を行った結果を比較し，セ数 F, G（ソースコード 6, 7）の例を考える．関数 F，マンティックコードクローンのペアを検出する．関数

G（ソースコード 6，7）では引数に int が 2 つありそF, G（ソースコード 6, 7）の例では，表 1 と表 4，表の対応関係としては 2 パターン考えられるが，これら2 と表 3 を比較すると全てのテストケースにおいて出の関数においては出力が引数の順番によらないため，力が一致するため，関数 F，G（ソースコード 6, 7）

ここでは 1 つの対応関係のみを用いて説明する．なはセマンティックコードクローンとして検出されるこお，表 2 は，関数 G（ソースコード 7）に対して, 4. 3とになる．

節で述べた手順で生成されたテストケースとする．

初期評価の結果比較結果を示す．総実行時間は 287 秒であった．表関数 1

関数 2一致 TC/全 TC5 に示す関数のうち cocktailSort の引数のみが（intbubbleSort

cocktailSort

943/943型の配列，int 型）であり，それ以外の関数の引数はbubbleSort

cycleSort

1279/1279（int 型のポインタ，int 型）であった．このことから，bubbleSort

insertionSort

1385/1385

異なる引数の型を持つ cocktailSort もそれ以外の関

bubbleSort

bubbleSort(r)815/815数と同じグループにグループ分けされており，型のbubbleSort

display

12/775違いにも対応することに成功している．表 5 では 1,

cocktailSort

cycleSort

746/746

2 列目に関数のペアの名前，3 列目にその比較で利用

cocktailSort

insertionSort

908/908

された全テストケース（分母），一致したテストケー

cocktailSort

bubbleSort(r)726/726

ス（分子）が示されている．表 5 に示すようにソート

cocktailSort

display

10/217を行う 5 つの関数においては全てのテストケースがcycleSort

insertionSort

1243/1243

一致しているが，機能が異なる display に関しては一cycleSort

bubbleSort(r)1063/1063

部のテストケースのみしか一致せず，セマンティック

cycleSort

display

9/553

insertionSort

bubbleSort(r)1166/1166

insertionSort

display

10/713

bubbleSort(r)display

12/553

表5

コードクローンの検出に成功している．

6 まとめと今後の課題
引数，返り値の型が異なるような場合への対応，さらに入出力以外のセマンティクスへの対応のための工夫を行うことに加え，記号実行を用いて実行パスを考

5 初期評価慮したテストケースを生成し，入出力の比較を行うソートを行う関数に対して初期評価を行った．評

ことでセマンティックコードクローンを検出する手法

価対象としてはさまざまなアルゴリズムの C 言語でを提案し，初期評価を行った．今後は実際のプロジェの実装が示されている GitHub 上のプロジェクトである TheAlgorithms/C†3 内のソートを行う関数としクトなどを対象にセマンティックコードクローン検出能力や実行時間などの評価を行う予定である．て分類されているものから 5 つのソートを行うアルゴリズムを対象とした．評価対象は bubble sort.c,

参 考 文 献

cocktail sort.c, cycle sort.c, insertion sort.c, bub-

[1] Käfer, V., Wagner, S., and Koschke, R.: Are
there functionally similar code clones in practice?,2018 IEEE 12th International Workshop on Software Clones (IWSC), 2018, pp. 2–8.
[2] Krutz, D. E., Malachowsky, S. A., and Shihab,
E.: Examining the Eﬀectiveness of Using Concolic
Analysis to Detect Code Clones, Proceedings of the30th Annual ACM Symposium on Applied Computing, 2015, pp. 1610–1615.
[3] Li, G., Liu, H., Jiang, Y., and Jin, J.: Test-Based
Clone Detection: an Initial Try on Semantically
Equivalent Methods, IEEE Access, Vol. 6(2018),
pp. 77643–77655.
[4] Liew, D., Schemmel, D., Cadar, C., Donaldson,
A. F., Zähl, R., and Wehrle, K.: Floating-Point
Symbolic Execution: A Case Study in n-Version
Programming, Proceedings of the 32nd IEEE/ACM
International Conference on Automated Software
Engineering, 2017, pp. 601–612.
[5] Roy, C. K., Cordy, J. R., and Koschke, R.: Com-ble sort recursion.c に含まれる関数とした．ただし，各要素の表示を行う display が bubble sort.c と cy-cle sort.c において重複していたため，cycle sort.c にある display を排除した．実行にあたって，各テストケース生成の際の記号実行の制限時間は 5 秒とした．
表 5 では同じグループに分類されたソートを行う 5 つの関数 bubbleSort (bubble sort.c), cock-tailSort (cocktail sort.c), cycleSort (cycle sort.c),insertionSort (insertion sort.c), bubbleSort (bubble sort recursion.c, 以降は bubbleSort(r) と呼ぶ．)と，各要素の表示を行う display (bubble sort.c) の†3 https://github.com/TheAlgorithms/Cparison and evaluation of code clone detection techniques and tools: A qualitative approach, Scienceof Computer Programming, Vol. 74, No. 7(2009),pp. 470–495.
[6] Wu, Y., Zou, D., Dou, S., Yang, S., Yang, W.,Cheng, F., Liang, H., and Jin, H.: SCDetector:Software Functional Clone Detection Based on Semantic Tokens Analysis, 2020 35th IEEE/ACM In-ternational Conference on Automated Software Engineering (ASE), 2020, pp. 821–833.
[7] Zou, Y., Ban, B., Xue, Y., and Xu, Y.: CCGraph: a PDG-based code clone detector with approximate graph matching, 2020 35th IEEE/ACM
International Conference on Automated SoftwareEngineering (ASE), 2020, pp. 931–942.