2019-2-(8): 情報処理学会プログラミング研究会 発表資料 2019 年 7 月 26 日

精確なガーベージコレクションのための局所変数登録誤りの発見
鵜川 始陽1,a)

藤本 太希1,†1

概要：精確なガーベージコレクション（GC）は，ルート集合となるポインタを精確に発見する必要がある．
C 言語で実装された仮想機械（VM）では，C 言語の局所変数にもポインタが格納されている．そこで，GCがそれらを発見できるように，局所変数の値やアドレスを GC から参照できる表に登録する VM がある．
しかし，VM のソースコード全体で間違いなく局所変数を登録したり解除する必要があり，間違いを起こしやすい．本研究では，局所変数が登録や解除できているかを VM のソースコードの制御フローグラフに対するパタンマッチによって検査した．検査は，我々が開発している JavaScript のサブセットの VM に対して行った．その結果，多くの登録漏れや冗長な登録を発見でき，この方法が有用であることが分かった．
キーワード：ごみ集め，バグ発見，プログラム解析

Finding Errors in Registrations of Local Variables for
Accurate Garbage Collection
Tomoharu Ugawa1,a)Taiki Fujimoto1,†1

Abstract: Accurate garbage collection (GC) has to find all pointers belonging to the root set. In a virtual
machine (VM) implemented in C language, local variables of C language may have pointers. Thus, some VM
registers the values or the addresses of local variables to a table that is visible to GC. However, this approachis error-prone because it requires to register and unregister local variables correctly though the entire sourcecode of the VM. In this research, we checked if local variables are registered and unregistered correctly by
pattern matching against control flow graphs of source code of the VM. We applied this check to the VMof a subset of JavaScript that we are developing. As a result, we found this approach is eﬀective because it
found many registrations missing and redundant registrations.
Keywords: garbage collection, bug finding, program analysis

1. はじめにコンパクションやコピー方式のガベージコレクション

を C 言語で実装する場合，ルート集合にはヒープ中の GCで管理されたデータへのポインタ（以下，単にヒープへのポインタ）を持つ局所変数も含まれる．

（GC）のようにオブジェクトを移動させる GC では，オブ

しかし，このような局所変数を精確に列挙できるようにジェクトを移動させた時，そのオブジェクトを指している

プログラミングするのは手間がかかり，間違いも生じやす

ポインタを全て移動先を指すように更新する．そのため，

い．局所変数は実行スタック上に作られるが，GC は実行

GC のルートのアドレスを精確に特定する必要がある．通スタックのどこに局所変数があるかや，その値がヒープ

常，GC を持つ高級言語のインタプリタや仮想機械（VM）

へのポインタかどうかは判断できない．そこで，スタック

1
†1
a)

高知工科大学
Kochi University of Technology
現在，株式会社トスコ
Presently with TOSCO Corp.
ugawa.tomoharu@kochi-tech.ac.jp

マップのようなコンパイラによる支援の仕組みを作るか，

VM のプログラム自身で明示的に局所変数をルート集合に登録，登録を解除する方法がとられる．
我々は組込みシステム向けの JavaScript VM である1

2019-2-(8): 情報処理学会プログラミング研究会 発表資料 2019 年 7 月 26 日

1 get_object_prop

1 get_object_prop

2 (Context *ctx, JSValue o, JSValue p) {2 (Context *ctx, JSValue o, JSValue p) {3

3

JSValue ret = NULL;
GC_PUSH(o);GC_PUSH(p);GC_PUSH(ret);if (!is_string(p))
p = to_string(ctx, p);do {if (get_prop(o, p, &ret) == SUCCESS) {GC_POP(ret);GC_POP(p);GC_POP(o);return ret;}
} while (get___proto__(o, &o) == SUCCESS);GC_POP(ret);GC_POP(p);GC_POP(o);return JS_UNDEFINED;

4
5
6
7
8
9
10
11
12
13
14

JSValue ret;if (!is_string(p)) {GC_PUSH(o);p = to_string(ctx, p);
GC_POP(o);}do {if (get_prop(o, p, &ret) == SUCCESS)
return ret;
} while (get___proto__(o, &o) == SUCCESS);
return JS_UNDEFINED;

4
5
6
7
8
9
10
11
12
13
14 }

15 }
図 2
図 1 素朴に GC PUSH と GC POP を挿入した eJSVM のソースコード

eJSVM のソースコード

Fig. 2 Source code of eJSVM.

Fig. 1 Source code of eJSVMinserted GC PUSH and GC POP
straightforwardly.

通常のテストによるバグの発見やデバッグは難しい．

eJSVM [1], [2] を開発している．現在の eJSVM にはオブ

そこで，GC PUSH と GC POP が正しく追加されているかを

ジェクトを移動しないマークスイープ GC を実装している検査する方法を検討した．その中で，Coccinelle [3], [4] とが，将来オブジェクトを移動する GC を実装することを計いう，プログラムの制御フローグラフに対してパタンマッ

画している．そのために，VM のソースコードの中でヒーチするツールを使ったところ，高い精度で GC PUSH 漏れをプへのポインタを持つ局所変数のアドレスを個別にルー発見できた．Coccinelle は Linux カーネルのリファクタリ

ト集合に登録，解除している．例えば，図 1 は eJSVM のングやバグ発見に用いられているツールで，ユーザがドメ

ソースコードの一部を説明用に改変したものである．ここ

イン特化言語（DSL）で書いた制御フローグラフのパタン

で，GC PUSH は引数のアドレスをルート集合に登録するマを使ってパタンマッチする．

クロ，GC POP は解除するマクロであり，JSValue 型の変数検査の精度を調べるために，これまで開発者が手動でがヒープへのポインタを持つ．関数の先頭で引数を含む全追加していた GC PUSH と GC POP を全て取り除き，検査にての JSValue 型の局所変数を登録し，関数を抜ける直前でよって取り除いた箇所を指摘できるか実験した．その結果，全て解除している．return 文の直前でも解除する必要が本来は不要であった箇所を除いて全て指摘することができある．

た．また，手動で GC PUSH が追加されていなかった箇所もしかし，GC PUSH と GC POP を正しく追加しながらプロ
グラミングするというのは，通常のプログラミングにはな指摘され，これらは 1 箇所を除いて全て本来は GC PUSH が必要な箇所だった．

い規則に従ってプログラムを書くことであり，間違いを起

本論文では，局所変数の登録と解除の処理を忘れるバグ

こしやすい．そのうえ，以下のような理由で，間違いの余を Coccinelle を使って探し，効率的にデバッグが行えた経地は大きくなっている．

験を，システムの開発経験として報告する．さらに，本手• プログラマは不要と思った処理を省いたりしがちで，特に eJSVM では VM のフットプリントを小さく抑えるという不要な処理を省く動機もある．例えば
実際の eJSVM のソースコードでは図 2 に示す位置に GC PUSHGC_POP が挿入されている（詳細は 2.3 節
参照）．

• プログラムを修正する際にも GC PUSH と GC POP が正
しく行なわれるように修正する必要がある．

法を別のプロジェクトのソースコードにも適用した実験の結果も報告する．

2. eJSVM でルート集合への登録と解除
2.1 基本的な仕組み
eJSVM は，ルート集合として登録された局所変数のア
ドレスを，スタック（以下，GC ルートスタック）で管理している．図 3 はある関数 f が関数 g を呼び出した時の• eJSVM では，VM 開発者以外もハードウェアにアクセ

制御スタックと GC ルートスタックの様子を示している．

スするための組込み関数を C 言語で記述して追加する

局所変数は制御スタック中の関数フレームに割り当てられことを想定している．

る．そのため，ルート集合として登録される局所変数もス

さらに，GC PUSH と GC POP が正しく追加されていなかったとしても，実行時に誤動作する頻度やその再現性は低く，タック構造で管理すると効率ががよい．

GC やコンパクションによってオブジェクト A が A′ に22019-2-(8): 情報処理学会プログラミング研究会 発表資料 2019 年 7 月 26 日

2.3 無駄のない GC PUSH と GC POP の追加

gx

図 1 では，関数の入口で三つある全ての JSValue 型の全yての変数を GC PUSH し，2 箇所ある関数の出口の両方で，A

全てを GC POP している．さらに，関数内で宣言された局
所変数 ret は，プッシュの前に NULL で初期化している．

A’

f
z

NULL

これで正しく動作するが，無駄に GC PUSH や GC POP をしCBている箇所がある．これらの無駄な GC PUSH や GC POP は実行のオーバヘッドになるだけでなく，VM のフットプリ
ントが大きくなる．組込みシステム向けの eJSVM では，

GC root stack

control stackheap

このような無駄は避けたい．

図 3 GC ルートスタック

JavaScript のプログラムはシングルスレッドなので，マFig. 3 GC root stack.

ルチスレッドのプログラムのように，他のスレッドによって GC が起動されるということはない．eJSVM では GC

移動すると，GC は変数 A を指していた変数（図では x）のをするには VM の実行コンテキストが必要になる．そのた

値を移動先を指すように更新する．これが可能なように，

め，GC が起こる可能性がある箇所は，Context 型のポイ

GC ルートスタックには局所変数のアドレスをプッシュ

ンタを引数として渡している関数呼出しに限られる．GCする．

ルート集合は，GC の時に精確であればよいので，変数のGC は GC ルートスタックから指される変数をデリファ

生存区間を考えて GC PUSH や GC POP を削ることができる．

レンスする．そのため，未初期化の変数は GC ルートス

例えば図 1 では，6 行の to string 関数の呼出ししかタックにプッシュしてはいけない．例えば，この先実行がGC を起こす可能性がない．この呼出しをまたいで生存区

進んで変数 y にポインタが代入されることが分かっていた

間がある変数は o だけである．ret に最初に値が格納されとしても，y が未初期化の状態で y のアドレスをプッシュるのは，8 行目なので，GC PUSH する必要はない．8 行目ですると，GC が起こった時にたまたま入っていた値をポイ

は，get prop 関数にポインタ引数として渡して値を格納ンタとしてデリファレンスしてしまう．変数 z のようにしている．

NULL で初期化しておけば，GC はそれをデリファレンスしない．

p についてはもう少し複雑である．p には引数として値が渡ってきて，例えば 8 行目などで使う．しかし 6 行目のVM のプログラムは，GC PUSH と GC POP マクロを使って，

to string の戻り値を書き込んでいるため，生存区間はこ

局所変数を GC ルートスタックにプッシュしたり GC ルー

こで分かれている．仮に 6 行目の中で GC が起こり，p に

トスタックからポップしたりする．eJSVM には GC PUSH

引数として渡ってきたポインタが指すオブジェクトが移と GC POP の対応がとれているかを実行時にチェックする

動していたとしても，p は to string の戻り値（有効なオ

デバッグ用のビルドオプションがあり，そのために GC POP

ブジェクトを指すはず）で上書きされる．そのため，p を

も変数を引数として受け取る．この変数はデバッグビルド

GC PUSH しておく必要はない．

でしか使われない．

変数 o を GC PUSH するのは，関数の入口でなくともよい．

6 行目の to string が実行されるのは p が文字列データで2.2 ヒープへのポインタを持つ変数ない時に限られる．この if 文の then 節の中で GC PUSH とeJSVM では，ヒープへのポインタを持つかどうかは型

GC POP をすれば，GC POP を 1 箇所にまとめられる．さらで判断できる．具体的には，JavaScript の値を格納するに，図 1 で定義している get object prop 関数はオブジェ

JSValue 型と，hidden class [5] など，いくつかの VM が内クトのプロパティを取得する関数であり，プロパティ名の部的に使う構造体へのポインタ型だけがヒープへのポイン

p には文字列データが与えられる可能性が高い．したがっタを持つ．JSValue 型の変数は整数値などポインタ以外のて，この if 文の条件が成立する可能性は低く，実行速度値を保持することもあるが，下位ビットに付けたタグで GCの面でもメリットがある．

がポインタかどうかを判定できるようになっている．VMが内部的に使う構造体については，型によってヒープに作以上のことを考慮すると，無駄なく GC PUSH と GC POPを追加したプログラムは図 2 のようになる．

られるか，それ以外のアドレスに作られる（例えば静的に確保される）かを区別できるようになっている．coccinelle

2.4 実行経路を考慮した GC PUSH の追加を使った検査では，JSValue 型とヒープに作られる構造体

GC PUSH が 必 要 か ど う か は ，プ ロ グ ラ ム の 実 行 経 路は完全に同じように扱うため，以降ではこれらをまとめてによって判断しなければならない．図 4 に組込み関数

単に JSValue 型と書く．

Array.prototype.concat のプログラムを示す．このプロ

32019-2-(8): 情報処理学会プログラミング研究会 発表資料 2019 年 7 月 26 日

1 JSValue e;2 ...
3 e = args[i];4 ...
5 while (k < len) {6

if (has_array_element(e, k)) {subElement =get_array_prop(ctx, e,
cint_to_fixnum(k));
set_array_prop(ctx, a, cint_to_fixnum(n),subElement);
}
n++;
k++;

7
8
9
10
11
12
13
14

@MissingPush depends on use && !falseuse && !immass@
identifier pre.push, decl.v;
expression e, gc.gc_fun;
position gc.gc_p, decl.decl_p;
type decl.T;@@(
T v@decl_p;|
T v@decl_p = e;)... when != push(&v)
when exists
gc_fun@gc_p
図 5

GC PUSH 漏れを探すルール

Fig. 5 Rule to find missing GC PUSH.

15 }
図 4 実行経路を考える必要があるプログラムの例

図 5 のルールを例に SmPL の文法を説明する．ルール

Fig. 4 Example of program that we need to consider executionの動作は 4 章で説明するが，このルールは GC PUSH 漏れのpath.

グラムで JSValue 型の変数 e は，8 行目の GC を起こす可能性がある関数呼出しより前にルート集合に登録しておく必要がある．なぜなら，その直前の 6 行目で使っているからである．この行はプログラムテキストでは上の行になっているが，while 文の中にあり，8 行目よりも後にも実行される可能性がある．

3. Coccinelle
プログラムの実行経路に対するパタンマッチをするために，Coccinelle [3], [4] というツールを使った．Coccinelle
は，SmPL という DSL で記述されたルールを受けとり，プ
ログラムの制御フローグラフに対してパタンマッチする．
さらに，パタンマッチした箇所を書き換える機能もあり，
ルールはセマンテックパッチと呼ばれている．Linux カー
ネルの開発プロジェクトではソースコードのリファクタリ
ングやバグの発見に使われている．

SmPL では C 言語のプログラムの断片や「...」といった省略の記号を使ったパタンでルールを記述する．Coc-

cinelle はこのパタンを，メタ変数で拡張された計算木論
理式（CTL-V 式）に変換し，制御フローグラフをクリプ
キ構造とみなしてモデル検査によってパタンマッチする．

Coccinelle のクリプキ構造では，状態はプログラムの文（statement）であり，その属性はルール記述した文の条件に合致するかどうかになっている．文の条件には，メタ変数を含む文や，ある式を含む文という条件が指定でき
る．内部表現が CTL なので，「...」などの省略記号にはexists や forall を指定できる．
SmPL では複数のルールを記述し，先行するルールのパタンがマッチした変数を後続のルールのパタンマッチで利用することができる．この機能を使ってマッチする条件を追加したり，偽陽性を取り除いたりできる．

検査のためのルールである．ルールの先頭には，ルール名

MissingPush と，このルールが依存しているルール use，
falseuse，immass を書く．これによって，use にマッチ
し，falseuse と immass にマッチしないようなメタ変数の組合わせについて，このルールのパタンマッチが試みられる．
以降の「@@」までの行はメタ変数を定義している．decl.vのような記述で，先行するルールのメタ変数を利用できる．
メタ変数には，プログラムの構文要素の他に，プログラム
中の出現位置を持つ position 型がある．
「@@」以降ではパタンの本体を定義する．「( | )」は選択を，「...」は途中に任意の数の文を含むことを表す*1 ．
「...」には条件を付けることができ，「when != push(&v)」は，push(&v) を含む文が存在しないことを表す．「whenexists」は先行する文に続くいずれかの実行経路で，以降のパタンが満たされることを表す*2 ．exists は実行経路の「...」に対応する部分だけに対して存在することを指定しているのではなく，関数の最後までの実行経路に対して以降のパタンにマッチする経路が存在することを指定している．例えば図 6 のプログラムように複数の実行経路がある場合に，そのいずれか一つ以上の実行経路
で「gc fun@gc p」のパタンにマッチすることを指定しており，一つの実行経路でしかマッチしない図 6 のプログラ
ムにも図 5 のルールはマッチする．exists の指定がなけ
れば，図 6 のプログラムにはマッチしなくなる．
各構文要素には「@decl p」のように，出現位置を表す
メタ変数を付けることができる．例えば，「gc fun@gc p」
は，メタ変数の宣言と合わせると，gc ルールで発見した関数 gc fun を，gc ルールで発見した位置で呼び出している文を表すことになる．なお，セミコロンを付けると文を表*1*2「...」がなければ，後続の文は時相演算子 X（next）で連結されるが，「...」があれば U（until）で連結される．
時相演算子 EU に変換される．

4

2019-2-(8): 情報処理学会プログラミング研究会 発表資料 2019 年 7 月 26 日

1 JSValue x = NULL;/∗T v@decl p = e; にマッチ∗/

2 if (flag == 1)
3cause_gc(context);/∗gc fun@gc p にマッチ∗/

1
2
3
4

図 6

JSValue x, y;y = cause_gc(ctx);
x = arg[1];return x == y;片方の経路でしか GC しないプログラム

Fig. 6 Program that causes GC on one path but the other.

図 7 JSValue 型変数への代入があるプログラム

Fig. 7 Program that has assignment to JSValue-type variable.

すことになり，セミコロンを付けなければ，その式を含む文を表すことになる．

Coccinelle は，OCaml や Python を使ってルールの一部を記述できる．本研究では，この機能を使ってメタ変数の条件を Python で記述したり，ルールの本体を Python で記述して，バグを発見した際の画面出力したりしている．

4. パグ検出ルールの作成
本研究では，Coccinelle を利用して次のバグを探すルールを作った．

あること．この位置を gc p とする．

• decl: JSValue 型の変数 v が宣言されていること．この位置を decl p とする．

• use: v は gc fun の呼び出し後のどこかの位置 use p で利用されていること．
この条件が全て満たされていると，decl p と gc p の間で vの GC PUSH が必要になることがある．例えば図 4 では，条件 gc には 8 行目や 10 行目が，条件 decl には 1 行目が該当する．そして，条件 gc にどちらの行が該当した場合でも，条件 use に 6 行目が該当する．したがって，gc，decl，• GC PUSH 漏れ

use の条件の全てに該当しており，decl p は 1 行目，gc p• JSValue 型変数のアドレスの取得と変数への保存は 8 行目や 10 行目になる．実際，このプログラムでは 8• 二重の GC PUSH

行目が実行されるより前に GC PUSH が必要になる．

• GC POP 漏れ

しかし，例えば，図 7 のプログラムでは実際には GC PUSH

• GC PUSH 前の GC POP

は必要ないが，gc，decl，use の条件には全て該当してし• 早過ぎる GC POP

まう．変数 x の GC PUSH が必要ないのは，2 行目の GC 後，• 二重の GC POP

4 行目で変数 x を使うまでに 3 行目で変数 x に代入してい• JSValue 型以外の変数の GC PUSH

るからである．また，変数 y は，2.3 節で説明した図 2 の「JSValue 型変数のアドレスの取得と変数への保存」は，そ変数 p と同じ理由，つまり，2 行目の代入は関数呼出しよ

れ自身はバグではない．しかし，取得したアドレスを変数

りも後で行われるため，GC PUSH する必要がない．これらに保存しておき，その変数が GC POP された後に使う可能の場合を無視するために，次の条件を追加を満たす場合は性があり，そうなるとバグになる．現在の eJSVM のソー

バグとして検出しない．以降，このように否定的に用いらスコードには，JSValue 型変数のアドレスを取得して他のれる条件には肩にマイナス記号を付ける．

変数の初期値にしたり代入している箇所はなく，今後もこ• assign− : gc p と use p の間には v への代入がある．

のようなプログラムを禁止しても不都合はなさそうなの• immass− : gc p の呼び出しと同じ文で，gc p より後で，保守的で単純なルールにした．

に v への代入がある．

「早過ぎる GC POP」は，それ以降で GC が起こる可能性

eJSVM には図 2 の 10 行目のように，変数 ret のアドレが残っているのに，GC 後に使われる変数を GC POP してスを関数に渡して，その変数経由で関数から値を戻すようしまうバグである．

なプログラムもある．これも効果は代入だが，呼び出され以降では，最も複雑な GC PUSH 漏れを探すルールの設計と実装を説明する．他のルールの設計と実装も同様の手順

る関数が変数に値を代入しない可能性もあるので，保守的に GC PUSH 漏れのバグとして扱う．

で行った．また，GC PUSH 漏れを探すルールは変数が引数の場合と局所変数として宣言されている場合でルールを分けて作ったが，この二つは本質的には同じなので，変数が局所変数として宣言されている場合に絞って説明する．

4.2 GC PUSH 漏れを探すルールの設計
GC PUSH 漏れを探すルールは図 8 に示す小さなルールに分けて実現した．

4.1 節で列挙した条件 gc，decl，use，immass− はそれ4.1 GC PUSH 漏れバグの条件

ぞれ個別のルールで実現した．さらに，これらのルールで

図 2 から GC PUSH を消したプログラムや図 4 のプログ検出した変数宣言の位置 decl p と GC を起こす可能性がラムにマッチするようなルールを作った．まず，GC PUSH

ある関数呼出し gc p の間に GC PUSH がない場合にバグをが必要になるような条件を列挙した．

検出するルール MissingPush を作った．assign− の条件• gc: GC を起こす可能性のある関数 gc fun の呼出しがは，use の条件を実現するルールに実行経路の条件として

52019-2-(8): 情報処理学会プログラミング研究会 発表資料 2019 年 7 月 26 日

gc

decl
v, decl_p

gc_fun, gc_p

use
use_p
falseuseimmass MissingPush
図 8 パタンの依存関係

Fig. 8 Depenency of patterns.

加えた．

use のルールを作る際に，「変数 v への代入以外の変数 vの利用」を精確に表現できず，変数 v に代入している箇所も利用として use が検出してしまった．また，GC PUSH や

GC POP の引数に変数 v を渡す文も v の利用として検出してしまった．これらの偽陽性を取り除くために，次のルー
ルを追加した．

• falseuse− : use p の利用は考慮する必要がない．
4.3 GC PUSH 漏れを探すルールの実装
この節では我々が作ったルールを説明する．まず Miss-

ingPush 以外のルールを図 9 に示して説明する．その後，
図 5 で示した MissingPush のルールを図 10 に再掲して説明する．

gc のルールは，コンテキストを引数にとる関数の呼出しにマッチする．メタ変数の定義中にある

type pre.Context;
Context ctx;

@gc@
expression gc_fun;
position gc_p;type pre.Context;
Context ctx;@@
gc_fun@gc_p(..., ctx,...)@decl@
identifier v;
expression e;
position decl_p;
type T:script:python(){is_pointer(T)};@@(T v@decl_p;|
T v@decl_p = e;)@use depends on gc && decl@
identifier decl.v;
expression e, gc.gc_fun;
position gc.gc_p, use_p;@@
gc_fun@gc_p... when != v = ewhen exists
v@use_p@falseuse depends on use@
identifier pre.push, pre.pop, decl.v;
expression e;
position use.use_p;@@(v@use_p = e|push(&v@use_p)|pop(&v@use_p))は，まず，Context*型にマッチするように pre ルールの中で Python で定義した型 Context を，メタ変数として利用することを宣言している．それを使って，その型を持つメ
タ変数 ctx を導入している．gc のルールは，この ctx を引数にとる関数呼出しにマッチする．関数ポインタを使った場合でもマッチするように，gc fun は識別子にマッチする identifier 型ではなく，式にマッチする expression@immass depends on use@
identifier decl.v;
expression gc.gc_fun;
position gc.gc_p;@@
v = <+... gc_fun@gc_p ...+>
図 9 GC PUSH 漏れを発見するルール

Fig. 9 Rules to find missing GC PUSH.

型にしている．

decl のルールは，JSValue 型やヒープ中に作られる VM

期化子はオプショナルなので，両方のパタンを書いている．

内部の構造体へのポインタ型の変数宣言にマッチする．

use のルールは gc と decl のルールで発見した変数 v とtype T:script:python(){is_pointer(T)};関数呼出し gc p に対して，関数呼出し gc p の後に v が使は，メタ変数 T に Python のプログラム is pointer(T);われるプログラムにマッチする．gc p と v の利用の間のが真になるような型だけにマッチするという条件を付けて「...」には「when != v = e」の条件を付けて，assign−

いる．is pointer は，引数が JSValue 型か，VM 内部のの条件を満たす場合はマッチしないようにしている．な構造体へのポインタ型のときに真になる．decl のルール

お，関数呼出し gc p の後に分岐がある場合，そのいずれかは，このような型の変数宣言にマッチする．変数宣言の初の実行経路上で使われている変数は全て見つけたいので，

6

2019-2-(8): 情報処理学会プログラミング研究会 発表資料 2019 年 7 月 26 日

@MissingPush depends on use && !falseuse && !immass@
identifier pre.push, decl.v;
expression e, gc.gc_fun;
position gc.gc_p, decl.decl_p;
type decl.T;@@(
T v@decl_p;|
T v@decl_p = e;)... when != push(&v)
when exists
gc_fun@gc_p
図 10

GC PUSH 漏れを探すルール（再掲）Fig. 10 Rule to find missing GC PUSH (same as Fig. 5).

1 GC_PUSH(nexth); GC_PUSH(oh);2 r = hash_put_with_attribute(
3
4
5
6
7
8
9
10
11
12
13
14

hidden_map(nexth),
name, index, attr);
if (r != HASH_PUT_SUCCESS) {GC_POP(oh); GC_POP(nexth);
return FAIL;}
hidden_n_entries(nexth)++;hash_put_with_attribute(hidden_map(oh), name,(HashData)nexth,
ATTR_NONE | ATTR_TRANSITION);
GC_POP(oh); GC_POP(nexth);
図 11 不要な GC PUSH

Fig. 11 Redundant GC PUSH.

「...」には「when exists」も付けている．

falseuse− のルールは，use のルールで発見した変数 vの利用が変数 v への代入や，変数 v を GC PUSH や GC POPには GC PUSH が必要ない箇所だった．実際には必要がなに渡しているときにマッチする．

かった GC PUSH を含むプログラムを図 11 に示す．1 行目−

immass のルールは gc p の関数呼出しと同じ文の中で，gc p の関数呼出しより後に変数 v に代入されるプログラムにマッチする．

v = <+... gc_fun@gc_p ...+>の左辺は gc fun@gc p を含む式を表している．
図 10 に再掲した MissingPush のルールでは，これまで nexth と oh が GC PUSH されているが，対応する GC POPまでの間に GC が起きる可能性はない．
以上のように，開発者が追加していた GC PUSH のうち必要な GC PUSH は全て発見することができ精度が高いことが確認できた．
本研究で探したバグのうち GC PUSH 漏れ以外のバグ以外

でに説明したルールを図 8 のように組合わせるために，は GC PUSH か GC POP がなければ成立しない．そのため，こdepends on use && !falseuse && !immassの実験では GC PUSH 漏れ以外のバグは見つからなかった．

という依存関係を書いている．gc と decl は use を介して間接的に依存しているので，ここには書いていない．

5.2 eJSVM のバグの発見

MissingPush のルールは，宣言から GC を起こす関数呼4 章で作成したルールを eJSVM に適用し，バグを探し出しの間に GC PUSH を含まない文だけからなる経路が存た．その結果を表 1 に示す．「手動」は開発者が追加して在するプログラムにマッチする．これを表現するために，いた GC PUSH のうち本当に必要だったものの数，「漏れ」「...」には「when != push(&v)」の条件と exists を付け

は 4 章で作ったルールで発見した本当の GC PUSH 漏れの箇ている．

所の数，「偽陽性」は 4 章で作成したルールで検出された

5. 実験と事例研究

ものの，本当は不要だった箇所の数を示している．なお，

GC PUSH 漏れ以外のバグは発見されなかった．

4 章で作ったルールを使って eJSVM のソースコードを4 章で作成したルールは，かなりの数の GC PUSH 漏れを検査した．eJSVM のソースコードにはマクロが使われて報告した．報告された箇所を全て確認したところ，1 箇所いるので，プリプロセッサで処理した後のソースコードをを除いて全て，本当に必要な GC PUSH が漏れていたことが検査した．このとき，GC PUSH や GC POP は関数呼出しと分かった．その中には図 4 に示した箇所も含まれる．

して残るようにした．

1 件の偽陽性は制御変数の値により 2 箇所ある if 文の分
岐先の組合わせが制限されるようなプログラムだった．該

5.1 精度の調査

当箇所を図 12 に示す．このプログラムの lowerValue

4 章で作成したルールの精度を調べるために，eJSVM にと upperValue が JSValue 型 で あ る ．検 査 で は ど ち ら開発者が追加していた GC PUSH と GC POP を全て取り除いも GC PUSH 漏れとして報告された．しかし，実際にはて，取り除いた箇所を指摘できるか調べた．

upperValue は GC PUSH する必要がない．upperValue が

eJSVM のソースコードでは合計で 32 箇所で GC PUSH が報告された理由は使われていた．4 章で作成したルールでは，このうち 26• 3 行目の set array prop 関数の呼出しが GC を起こ

箇所を，GC PUSH 漏れとして発見した．残る 6 箇所は実際す可能性がある関数として gc の条件に適合し，

7

2019-2-(8): 情報処理学会プログラミング研究会 発表資料 2019 年 7 月 26 日

表 1

局所変数は，eJSVM の GC PUSH と同様のマクロを使って，GC PUSH 漏れの数

Table 1 Number of missing GC PUSH.

アドレスを GC ルートスタックにプッシュする．このプログラムでは，デバッグ用の関数以外の全ての関数呼出しの

ファイル

行数

手動

漏れ

偽陽性

allocate.c

228

3

0

0

builtin-array.c

797

3

23

1

実験の結果を表 2 に示す．この結果には，開発者が追builtin-boolean.c

73

0

3

0

builtin-global.c

277

0

2

0

加していた GC PUSH のうち実際には不要だった 10 箇所は

builtin-math.c

257

0

1

0

builtin-number.c

175

0

3

0

GC PUSH が保守的に挿入されていた．それにもかかわらず，

builtin-object.c

110

0

2

0

7 箇所の GC PUSH 漏れを検出した．これら 7 箇所は，開発

builtin-regexp.c

273

0

0

0

者に確認したところ全て必要な GC PUSH が漏れていたもの

builtin-string.c

692

6

6

0

と分かった．

call.c

251

0

0

0

codeloader.c

761

0

0

0

context.c

168

1

0

0

conversion.c

669

0

6

0

gc.c

1066

0

0

0

Coccinelle では，制御フローグラフに対してパタンマッ

hash.c

474

0

0

0

チする．そのため，式の値に依存して実行経路が制限されinit.c

114

0

0

0

るような場合にはバグを誤検出する可能性がある．eJSVM

main.c

429

0

0

0

object.c

1030

14

18

0

に対する適用では，このような例は図 12 の 1 箇所だけだっstring.c

189

0

0

0

unix.c

10

0

0

0

れる．他にも，ループの継続条件とヒープへのポインタを

vmloop.c

1426

0

0

0

持つ変数が使われるかどうかが関連している場合なども考

合計

9469

27

64

1

えられる．

中で GC が起こる可能性がある．

含んでいない．この実験で用いたプログラムには，多くの

6. 議論
6.1 制御フローグラフに対するパタンマッチの限界

た．この例では二つの if 文の分岐先の組合わせが制限さ

eJSVM ではデバッグ用に GC POP にも GC ルートスタッ
表 2 AVL 木のプログラムに対する GC PUSH 漏れの数

クの先頭にあることが期待される変数を渡している．デ

Table 2 Number of missing GC PUSH in AVL-tree program.

バッグビルドすると実行時にはこれを使って GC PUSH と

ファイル

行数

手動

漏れ

偽陽性

GC POP の対応を検査する．Coccinelle でこの検査をするこ

avltree.c

638

28

7

0

とは難しい．例えば，変数 a，b の順で GC PUSH され，同じ順で GC POP されている場合はバグとして検出したいが，• 9 行目の upperValue の利用が use の条件に適合し，そのようなルールを一般化して作ることはできない．

さらに• その間に upperValue への代入が存在しない経路（56.2 GC PUSH の自動挿入

行目の if 文の条件が成立しない場合）が存在する

Coccinelle ではパタンにマッチした箇所のプログラムをからである．しかし，5 行目の if 文の条件が成立しないの書き換えるようなルールも使える．それを使えば，例えばは upperExsits が偽の場合で，その場合はその後に 9 行目

変数宣言の直後に GC PUSH を自動的に挿入することもできなどの upperValue を使う分岐には入らない．Coccinelle

る．しかし，それでは冗長な変数の初期化が行われる可能は制御フローグラフに対するパタンマッチを行うので，こ性がある．

のようにデータに依存した制御は保守的に扱うしかなく，最適な GC PUSH の挿入位置は，そのプログラムの意味ま

偽陽性の可能性がある．しかし，そのようなプログラムはで踏み込んで考える必要があり，それを自動化することはプログラマにとっても見通しが悪く，あまり書かれること

難しい．意味まで考えなくとも，例えば「制御フローグラはないと考えている．

フ上で，GC を起こす可能性がある関数呼出しの全てを支配する節点のうち，関数の入口から遠いものの中から選ぶ」

5.3 eJSVM 以外のプログラムの検査
eJSVM 以外のプログラムに対しても，4 章と同様の方法で Coccinelle のルールを作り，GC PUSH 漏れのバグを探という規則でもかなり効率のよいプログラムは作れるかもしれない．しかし，このような複雑なルールを SmPL で記述すると，ルールのバグの可能性が増える．

した．対象には，他の研究グループが開発している GC ラ

本研究では Coccinelle を用いたが，コンパイラの内部表

イブラリの，テスト用のプログラムを用いた．このプログ

現の上で GC PUSH 漏れを探したりを自動挿入するという方

ラムは C 言語で書かれた AVL 木のプログラムで，節点を法も考えられる．しかし，既存ツールを利用するのに比べGC で管理されたヒープに起く．節点へのポインタを持つると手間がかかる．

8

2019-2-(8): 情報処理学会プログラミング研究会 発表資料 2019 年 7 月 26 日

1 for (lower = 0; lower < mid; lower++) {2

if (lowerExists)
lowerValue = get_array_prop(context, args[0], cint_to_fixnum(lower));
upperExists = has_array_element(args[0], upper);if (upperExists)
upperValue = get_array_prop(context, args[0], cint_to_fixnum(upper));

3
4
5
6
7
8

if (lowerExists && upperExists) {set_array_prop(context, args[0], cint_to_fixnum(lower), upperValue);
set_array_prop(context, args[0], cint_to_fixnum(upper), lowerValue);} else if (!lowerExists && upperExists) {set_array_prop(context, args[0], cint_to_fixnum(lower), upperValue);delete_array_element(args[0], upper);} else if (lowerExists && !upperExists) {set_array_prop(context, args[0], cint_to_fixnum(upper), lowerValue);delete_array_element(args[0], lower);} else {/∗ No action i s required ∗/
}

9
10
11
12
13
14
15
16
17
18
19
20 }

図 12 偽陽性の箇所

Fig. 12 Program causing a false positive.

6.3 eJSVM の開発への利用

変数をまとめた構造体を作り，それをスタックに置く方

5.1 節で行ったように GC PUSH と GC POP を全て消して検法を提案している．その構造体をリストつないでおけば，査すると GC PUSH が必要が箇所が分かる．eJSVM の開発

GC はそのリストをたどって構造体を探すことができる．

プロジェクトでは，本研究の後，実際に全ての GC PUSH とHenderson はプログラム変換によってこのような構造体を

GC POP を消して検査し，必要な GC PUSH と GC POP だけを導入することを提案している．開発者が手でこのような構追加した．このとき，GC PUSH の挿入箇所は開発者が考え造体を導入するのは，関数毎に構造体定義を作る必要があながら挿入したが，本論文の著者ではない教員 1 名と，著り，現実的ではない．

者を含む学生 3 名で作業して 3 時間程度で終わった．

この他にも，ヒープへのポインタは制御スタックとは別

eJSVM では，本研究で開発したルールを適用するメイのスタックにも積んでおくシャドウスタックと呼ばれる技

クファイルのターゲットを作って，ソースコードを変更し法も知られている．また，Java Native Interface（JNI）やたらすぐにバグを検査できるようにしている．これによっ

V8 JavaScript エンジンでは，局所変数がヒープへのポイて，本研究でのデバッグ後にも，追加されようとしたバグンタを保持する必要があるときはハンドルに変換するといを発見した．検査には通常のデスクトップ計算機でも 1 分う方法をとっている．この方法では，ハンドルを解放する

程度かかるが，これは eJSVM で使っている回帰テストののを忘れるバグの可能性がある．ただし，C++ではスコー

時間より短かい．そのため，実用上，検査時間が問題にな

プを抜ける際にデストラクタで解放するという技法を使う

ることはない．

ことができ，V8 ではそのようにしている．

7. 関連研究7.1 ルート集合の管理
eJSVM では局所変数のアドレスを明示的に GC ルート
スタックにプッシュする方法でルート集合を特定したが，最後に，スタック上の全てのワードの値の中で，オブジェ
クトの先頭へのポインタのように見えるものは全てポイン
タだとして扱う保守的 GC もよく知られている [7]．しかし，保守的 GC ではオブジェクトを移動させることはできない．

GC ルートとなる局所変数を探す方法として，いくつか他の方法も知られている．コンパイラを変更できる場合は，

7.2 C 言語を対象にしたパタンマッチによるバグ発見

VM のコンパイル時に，関数フレームのどこにポインタがCoccinelle は Linux カーネルプロジェクトのために開発あるかを記録したスタックマップを生成する方法が一般的されていた．主に Linux のバグ発見やリファクタリングに行われている．

に使われている [8], [9]．OS 以外のオープンソースソフト

Henderson [6] は，関数毎にヒープへのポインタを持つウェアにも利用されており，OpenSSL のバグ発見に使っ9

2019-2-(8): 情報処理学会プログラミング研究会 発表資料 2019 年 7 月 26 日

た研究もある [10]．また，Coccinelle の開発プロジェクト
は，NULL ポインタの参照を発見するルールなど，多くの例を紹介している*3 ．しかし，GC のバグ発見に応用した[6]

例は我々の知る限り存在しない．

Nishiwaki ら [11] は，JNI の参照の扱いに関するバグを発見するために，SEAN という C 言語のパタンマッチに[7]

よるバグ発見ツールを開発した．SEAN は，構文木の特定のパタンにマッチする．中村ら [12] は，それを一般化して[8]

C 言語のソースコードからユーザが指定した構文木のパタンを探すツール ASTgrep を開発した．Quinlan ら [13] のRose コンパイラインフラストラクチャを使った構文木の[9]

パタンマッチもバグ発見を目的にしている．

8. まとめ[10]

本研究では，eJSVM に精確な GC を実装するために，ヒープへのポインタを持つ局所変数をルート集合に登録したり解除したりするコードのバグを探した．そのため[11]に，制御フローグラフに対するパタンマッチを行うツール

Coccinelle を利用した．この方法の精確さを調べるために，開発者が追加していたルート集合への登録処理を全て取り[12]除いたソースコードに対してこの方法を適用したところ，取り除いたうち必要な登録処理を全て見つけることができた．さらに，多くの登録処理の漏れを発見し，eJSVM のデバッグに役立った．また，他の研究プロジェクトが作ったソースコードに対しても同様の方法を適用し，いくつか[13]

oriented Language Based on Prototypes, Proc. on
Object-oriented Programming Systems, Languages andApplications (OOPSLA ’89), ACM, pp. 49–70 (1989).
Henderson, F.: Accurate Garbage Collection in an Uncooperative Environment, Proceedings of the 3rd international symposium on Memory management (ISMM’02), ACM, pp. 150–156 (2002).
Boehm, H.-J. and Weiser, M.: Garbage Collection in
an Uncooperative Environment, Software – Practice andExperience, Vol. 18, No. 9, pp. 807–820 (1988).
Lawall, J. L., Muller, G. and Palix, N.: Enforcing theUse of API Functions in Linux Code, Proceedings of the
8th Workshop on Aspects, Components, and Patterns
for Infrastructure Software, ACM, pp. 7–12 (2009).
Palix, N., Thomas, G., Saha, S., Calvès, C., Muller,
G. and Lawall, J.: Faults in Linux 2.6, ACM Transactions on Computer Systems, Vol. 32, No. 2, pp. 4:1–4:40(2014).
Lawall, J., Laurie, B., Hansen, R. R., Palix, N. andMuller, G.: Finding Error Handling Bugs in OpenSSL
Using Coccinelle, 2010 European Dependable Computing Conference, pp. 191–196 (2010).
Nishiwaki, H., Ugawa, T., Umatani, S., Yasugi, M. andYuasa, T.: SEAN: Support Tool for Detecting Rule Violations in JNI Coding, IPSJ Transactions on Programming, Vol. 5, No. 3, pp. 23–28 (2012).
中村真也，鵜川始陽，馬谷誠二： 規則違反コードの構造を反映した木パタンを用いるコード検査器，情報処理学会
論文誌プログラミング（PRO），Vol. 9, No. 4, pp. 1–15
(2016).
Quinlan, D. J., Vuduc, R. W. and Misherghi, G.: Techniques for Specifying Bug Patterns, Proceedings of the2007 ACM Workshop on Parallel and Distributed Systems: Testing and Debugging, ACM, pp. 27–35 (2007).

のバグを発見した．偽陽性はほとんどなかったが，制御フ
ローグラフに対するパタンマッチを行っているため，式の値に依存して実行経路が制限されるようなプログラムでは偽陽性があった．
参考文献
[1]

[2]

[3]

[4]

[5]

*3

Ugawa, T., Iwasaki, H. and Kataoka, T.: eJSTK:
Building JavaScript virtual machines with customized
datatypes for embedded systems, Journal of Computer
Languages, Vol. 51, pp. 261–279 (2019).
Kataoka, T., Ugawa, T. and Iwasaki, H.: A Framework
for Constructing JavasSript Virtual Machines with Customized Datatype Representations, In Proc. SAC 2018,
ACM, pp. 1238–1247 (2018).
Brunel, J., Doligez, D., Hansen, R. R., Lawall, J. L.
and Muller, G.: A Foundation for Flow-based Program
Matching: Using Temporal Logic and Model Checking, Proceedings of the 36th Annual ACM SIGPLANSIGACT Symposium on Principles of Programming
Languages (POPL ’09), ACM, pp. 114–126 (2009).
Padioleau, Y., Lawall, J., Hansen, R. R. and Muller,
G.: Documenting and Automating Collateral Evolutionsin Linux Device Drivers, Proceedings of the 3rd ACM
SIGOPS/EuroSys European Conference on Computer
Systems 2008 (Eurosys ’08), ACM, pp. 247–260 (2008).
Chambers, C., Ungar, D. and Lee, E.: An Eﬃcient
Implementation of SELF a Dynamically-typed Objecthttp://coccinelle.lip6.fr/rules/

10