Comments
Description
Transcript
ReBucket を用いた Linux カーネルバグの分類
Vol.2014-OS-130 No.11 2014/7/28 情報処理学会研究報告 IPSJ SIG Technical Report ReBucket を用いた Linux カーネルバグの分類 佐久間 亮1,a) 菊池 伸郎1 吉村 剛1 河野 健二1 概要：オペレーティングシステムカーネルには多くのバグが存在している．Windows や Linux にも多く のバグが存在しており，Microsoft では Windows Error Reporting (WER) と呼ばれるシステムを用いて クライアントからバグによって障害が起きた際の情報を集めている．集めたクラッシュログを WER シス テムを用いてバグごとに分類し，多くのユーザで発現するバグからデバッグを行っている．バグの分類に はコールスタックに注目して類似度を計算する事によって分類を行う ReBucket が知られている．しかし， Linux では ReBucket のようなバグの分類を行っていない．Linux で ReBucket が適用できれば，開発者 がクラッシュレポートを分類する負担を軽減することができる．しかし，Linux ではフレームポインタの 最適化によりコールスタックが正確ではない場合があり，バイナリが多様なため同じバグでも異なる情報 を出力することがある．本研究は ReBucket を Linux に適用した場合の効果について，定量的に評価を 行った． 調査はフォールトインジェクタを用いて挿入したバグによってクラッシュした際のクラッシュロ グ，850 種類，全 10294 件を用いて ReBucket を行う．調査の結果，全体の 69% のバグはバグごとに同 じグループに分類されていた．また，全体の 46% のグループには一種類のみのバグが分類されていた． 1. はじめに ポートが送付されることとなる．たとえば，RedHat 社の リポジトリでは，ひと月に約 1 万件 のクラッシュレポー 近年オペレーティングシステムのカーネルは多機能，複 トを受信している [6]．このように多数のクラッシュレポー 雑化しており，ソースコードの量も膨大になっている. た トが送付されてくるため，送付されたクラッシュレポート とえば，Linux カーネルのバージョン 3.15.2 のコード量 をひとつひとつ人手で解釈・分類していくことは現実的で を SLOCCount (2.26) で調べたところ，約 1200 万行にも はない．そのため，クラッシュレポートを何らかの基準で なっている [1]．さらに，市場競争力のために開発期間も 分類・整理し，対応するべきクラッシュレポートに優先順 短縮される傾向にあり，出荷前にソフトウェアの品質検査 位をつけて対処できるようにしていく必要がある．特に， を完璧に行うことは難しくなっている．Palix らの調査で 同一の原因（root cause）によって発生したクラッシュレ も Linux カーネルに多くのバグがあることが示されてい ポートをひとつにまとめ，クラッシュの発生頻度の高いバ る [2]． グから優先的に対処できるようにすることが重要である． そのため，開発者はソフトウェアのリリース後にも， 対応するクラッシュレポートの優先度付けを行うため，ク ユーザからソフトウェアの不具合についての情報を集め ラッシュレポートを自動的に分類する手法には Bucketing る必要がある．実際，ソフトウェアの不具合（バグ）を収 [3] や ReBucket [7] といった手法が知られている．これら 集するためにさまざまなクラッシュログやバグレポート の手法を用いることで，クラッシュレポートを root cause のリポジトリが運用されている．たとえば，Microsoft 社 ごとに分類することができるため，クラッシュ頻度の高い の Windows Error Report (WER)[3]， Mozilla の Mozilla バグからデバッグを行うことが可能になっている． crash report[4]， Apple の Apple crash report[5] などが 本稿は， Linux に ReBucket を適用してクラッシュレ 知られている．こうしたバグ・リポジトリを用いる事によ ポートの分類をした場合の精度について調査を行う．調査 り，ユーザの遭遇したクラッシュなどの情報を自動的に収 で用いるクラッシュログの収集にはソフトウェアフォー 集し，効率的にデバッグ等のメンテナンス作業を行うよう ルトインジェクタの SAFE [8] によってソースコードレベ になっている． ルでバグを挿入した Linux カーネルを用いた．SAFE で このようなバグ・リポジトリには多量のクラッシュレ 生成した約 7700 種類のバグをひとつずつ挿入したカーネ ル上で，ワークロードを走らせてクラッシュした際のク 1 a) 慶應義塾大学 [email protected] c 2014 Information Processing Society of Japan ラッシュログを基に ReBucket を適用する．本調査では全 1 Vol.2014-OS-130 No.11 2014/7/28 情報処理学会研究報告 IPSJ SIG Technical Report 10294 件のクラッシュログに ReBucket を適用した． Linux には多くのバージョンやディストリビューション がある上，カーネルコンパイル時のコンフィグレーション も多岐にわたっており，同一のバグによるクラッシュが あってもコールトレースに違いが出てくる可能性が高い． また，Linux ではフレームポインタがスタックに積まれてい ないことを前提にコールトレースが生成されるため，コー ルトレースが不正確なものとなっている．このような原因 から Windows では有効に機能する ReBucket が Linux で も有効に機能するかどうかは必ずしも自明ではない． 今回の調査では 2 つの評価基準によって ReBucket の効 図 1 Distance to the Top Frame と Alignment Offset 果を評価した．一つ目は同種のバグがいくつのグループに 分類されたか，というものである．この評価の最善の結果 てバグの分類を行うが，ReBucket はエラーレポートのコー は同種のバグは全て同じグループに分類されるというもの ルスタックのみに注目してバグの分類を行う．ReBucket である．この評価の結果では，850 種類のバグの内 72% が を用いて既知の Microsoft 製品のエラーレポートを分類し 一つのグループに分類されていた．二つ目の評価方法は， たところ，Bucketing に比べ約 10 % の精度向上が示され バグが分類された各グループ内に存在するバグの種類の数 ている． である．この評価の最善の結果は，各グループには 1 種類 のバグのみが存在するというものとなる．この評価の結果 2.2 ReBucket では，全体の 50% のグループはグループ内には一種類の ReBucket はエラーレポート間のコールスタックに注目 みのバグを分類していた．また，最大で一つのグループに して root cause ごとに分類を行う．類似しているコールス 70 種類のバグを分類しているケースが存在した．これら タックを持つエラーレポートは同 Bucket へ，類似してい の結果は Windows に ReBucket を適用した場合に比べて ないコールスタックを持つエラーレポートは異なる Bucket 精度の低下が見られ，Linux 特有のコールトレースの生成 へ分類する．ReBucket の分類は 2 つの段階に分けること 方法やバイナリの多様さが原因であると考えられる． ができ 1) エラーレポート間のコールスタックの類似度の 本論文の構成を以下に示す．2 章では WER と ReBucket 計算を行い，2) 類似度を基にクラスタリングを行う．本研 について，また Windows と Linux におけるクラッシュレ 究で用いる ReBucket のアルゴリズムについての簡単な説 ポートの違いを説明する．3 章では Linux における Re- 明を行う． Bucket の有用性を示す．4 章ではまとめと今後の課題につ 2.2.1 類似度 いて述べる．5 章では本研究の関連研究について述べる． コールスタックの類似度はふたつのコールスタックの最 大共通部分列と二つのメトリックを基にした重み付けに 2. Windows Error Reporting と ReBucket よって計算する．ひとつ目のメトリックはコールスタッ 2.1 Windows Error Reporting の概要 どバグに関係のあるものであるというものであり，ふた Windows では WER によってカーネルやソフトウェア クのトップ（クラッシュを起こした関数）に近い関数ほ つ目はコールスタック間で一致する関数の位置が近い程， がクラッシュした際の情報を Microsoft 社のサーバへ集め 二つのコールスタックは類似しているという考え方であ ている．WER で集められたエラーレポートは Bucketing る．このメトリックを基に Distance to the Top Frame と と呼ばれるアルゴリズムによってクラッシュの原因のバ Alighnment Offset というパラメータから重み付けを行う． Mi−1,j−1 + cost(i,j) Mi,j = max (1) Mi−1,j M グごとにグループ (Bucket) に分類される．Bucketing に よって分類された グループ （Bucket） には 1 種類のバグ （root cause）に対応するエラーレポートが分類され，同じ i,j−1 { root cause によるエラーレポートは 1 つの Bucket に分類 されることが理想的である．Microsoft ではこの Bucketing を用いてエラーレポートの分類を行うことで 10 年間で 数 十億件のエラーレポートに対応している． バグの分類手法として Bucketing とは別に Microsoft の cost(i,j) = e−c∗min(i,j) e−o∗abs(i−j) 0 Mm,n sim(C1 ,C2 ) = ∑l −cj j=0 e if fi of C1 = fj of C2 (2) otherwise (3) Dang らが提案した ReBucket が知られている．Bucketing 図 1 に Distance to the Top Frame と Alignment Offset は Windows 特有のさまざまなヒューリスティックを用い の例を示す．Distance to the Top Frame はコールスタッ c 2014 Information Processing Society of Japan 2 Vol.2014-OS-130 No.11 2014/7/28 情報処理学会研究報告 IPSJ SIG Technical Report クのトップからの位置を示し，たとえば f1 では Distance to the Top Frame は 1 となる．Alignment Offset はふた つのコールスタック間で共通する関数同士の位置の差を表 し，f5 と f70 では Alignment Offset は 2 となる． 具体的な計算方方法を式 (1) - (3) に示す．コールスタッ ク間の最大共通部分列問題を解く方法として知られる動的 計画法を用いてコールスタック C1 ，C2 の最大共通部分 列を式 (1) のように解く．通常の最大共通部分列問題とは 異なり，式 (2) で表す cost(i,j) によって重み付けを行い 計算する．式 (2) で用いる min(i,j) と abs(i − j) はそれ ぞれ共通する関数の Distance to the Top Frame の最小値 図 2 oops メッセージのサンプル と Alignment Offset にあたる．また，c ，o は Distance to the Top Frame と Alignment Offset に対するパラメータ で??で説明するようにその製品に対して最適なパラメータ ジョンとマシンモデルを示している．ディストリビュー を用いることができる．最終的なコールスタック間の類似 ションによってはカーネルバージョンが正確に出力されな 度 sim(C1 ,C2 ) は式 (3) で求めることができる． いことがある． 2.2.2 クラスタリング コールトレース: コールトレースはカーネルがクラッ 計算されたコールスタック間の類似度をもとにクラスタ シュに至るまでの関数呼び出しの実行履歴を示している． リングし，クラッシュレポートの分類を行う．ReBucket 8 行目から 18 行目までがコールトレースになっており， では凝集型階層的クラスタリングを使う．これは，始めに 関数名の “+” 以降はバイナリでのオフセットを表してお 各クラッシュレポートを一つのクラスタとし，一番類似度 り，8 行目の最後にある “[ext3]” はモジュール名を表して が高いものから階層的に併合していくクラスタリングであ いる．また，18 行目の RIP はクラッシュが起こった関数 る．ReBucket では各クラスタ間の距離を決める方法は最 なので，この関数がコールスタックのトップにあたる． 長距離法を取っており，各クラスタ同士の最大距離が閾値 2.3.2 コールストレースと “?” d より大きくなった場合クラスタリングを終了し，その結 oops メッセージのコールトレースには，図 2 の 9 行目 果が分類結果となる． にある “? 2.2.3 パラメータ 名の前に “ ? ” が付いているものがある．この “ ? ” の ReBucket では 2.2.1 で説明した二つのパラメータ c，o とクラスタリングの閾値 d に対して最適な値を用いること ext3 journal dirty metadata()” のように関数 付いた関数は実際に呼び出された保証の無いものであり， Linux 特有のコールトレースの生成方法によって出力され によって分類の精度を高めることができる．パラメータの るものである．Linux のコールトレース生成の仕組みを， 決定方法は，root cause が分かっているクラッシュレポー スタックフレームとフレームポインタとともに解説をし， トのデータセットに各パラメータ c，o，d を変化させて分 どのようにコールスタックをトレースしているのか，ま 類を行い，一番精度の高かった場合のパラメータの組み合 たどのような関数が “ ? ” 付きで出力されるのかを解説 わせを用いるというものである． する． スタックフレーム: コールスタックは各関数ごとのス 2.3 Linux におけるクラッシュレポート タックフレームから構成される．通常一つのスレッドには Linux カーネルはクラッシュした際に，クラッシュログ 一つのスタックが対応して存在し，関数呼び出しの際に関 にあたる oops メッセージを出力する．oops メッセージ 数のフレームをスタックにプッシュしていき，処理が終了 にはカーネルがクラッシュした際の情報が含まれており， すると積んだフレームをポップすることによって，関数を 開発者はデバッグの際にユーザから送付された oops メッ 呼び出す前の情報を取り出すことができる． セージを用いてデバッグを行う． 2.3.1 oops メッセージ oops メッセージの簡単な解説をする．図 2 に oops メッ セージの簡単なサンプルを示す． スタックフレームの簡単な構造を図 3 に示す．新しい関 数のスタックフレームをプッシュする際は，最初に現在の スタックフレームの上に関数への引数をプッシュする．次 に，呼び出した関数の処理が終わった後に，戻るべきアド 原因 : 1 行目にはクラッシュの原因が記述される．図 2 レスを記憶するために実行中の関数の命令アドレスをス の場合は NULL ポインタを参照したことによってクラッ タックにプッシュする．最後に，ローカル変数などに必要 シュしている． な分だけローカル領域にプッシュを行う． カーネルバージョン: 3 行目は Linux カーネルのバー c 2014 Information Processing Society of Japan フレームポインタ: スタックフレーム内に格納されてい 3 Vol.2014-OS-130 No.11 2014/7/28 情報処理学会研究報告 IPSJ SIG Technical Report らデータをひとつずつプッシュしていきシンボルテーブル を参照し，カーネル内の有効なアドレスを指しているなら その関数名を 2 の 9 行目のように “ ? ” 付きで出力する （有効でないなら出力は行わない）． フレームポインタを有効にしている場合もこの処理が行 われ，フレームポインタの隣のアドレスに格納されている リターンアドレスのみを “ ? ” の付かない通常のコールト レースとして出力するが，それいがいの関数は “ ? ” 付き 図 3 stack frame で出力される． 図 4 frame pointer このため，フレームポインタを最適化した場合コールト レースで出力される全ての関数が “ ? ” 付きで出力される る変数や引数を参照する際にはスタックポインタやフレー こととなる． ムポインタを用いる．スタックポインタは最も最近参照さ 2.3.3 Windows と Linux におけるクラッシュレポー れた位置のアドレスを指しており，例えば図 3 のローカル 領域に変数をプッシュしていくと，その分スタックポイン タもインクリメントされていく． トの違い Linux の oops メッセージを Windows の ReBucket に 適用する場合，Windows で用いた場合のようにうまく分 フレームポインタはスタックフレームのベースアドレス 類できない可能性がある．これは Windows と Linux では を記憶しておくためのものである．ベースアドレスはス コールトレースの生成方法に違いがあることや，Linux は タックフレームの底，正確にはフレーム内のリターンアド Windows に比べてカーネルバージョンやディストリビュー レスとローカル領域の間のアドレスを示している．通常 ション，コンフィグレーションが多く存在しバイナリが多 ベースアドレスは EBP レジスタに保存されているが，関 様であることが理由となる． 数呼び出しを行う際に呼び出し元の関数のベースアドレス コールトレースの生成方法: Windows で生成されるコー をフレームポインタとしてスタックにプッシュして記憶し ルトレースはコールスタックにフレームポインタを積んで ておくようになっている． フレームポインタはカーネルを いるため，正確な情報が期待できる．しかし，Linux の場 ビルドする際にコンパイルオプションで最適化することが 合フレームポインタを最適化した場合，表示されるコール できるため，環境によっては用いられない場合が存在する． トレースは全て “ ? ” 付きの関数なので実際には呼び出し フレームポインタはコールトレースを生成する際に重要 を行っていない関数がコールトレースにまぎれる可能性が な役割を持っている．フレームポインタを用いる場合，ス ある．このため，Linux のコールトレースは Windows の タックフレーム内のフレームポインタを辿ることによっ コールトレースに比べて正確でない場合がある． て，コールトレースを生成する． カーネルバージョンやディストリビューション: Linux 図 4 にフレームポインタを辿っていく流れを示す．ス には多くのカーネルバージョンやディストリビューショ タックには関数 A，B，C のスタックフレームに積まれて ン，コンフィグが存在する．また，[6] で見ることができ いる．スタックフレームにはそれぞれ，呼び出し元の関数 るように，ディストリビューションが不明な “ unknown ” のフレームポインタが積まれている．関数 C から関数 A のクラッシュログが多数送られてくる．このようなクラッ までフレームポインタを辿る場合，スタックフレーム C は シュログはユーザ自身がカーネルをビルドしている場合が レジスタに保存してあるベースポインタを見ることによっ あり，カーネルのバージョンが同じでもコンフィグやパッ て，呼び出しもとの関数 B のベースポインタを知ること チレベルによって多様なバイナリが存在し，それぞれが異 ができる．さらに，関数 B のベースポインタに隣接する なる動作をすることがあるため同じ原因のバグでクラッ アドレスに関数 A のフレームポインタが格納されている シュした場合でも，異なる oops メッセージを出力する可 ため，関数 B の呼び出しもとである関数 A のベースポイ 能性がある． ンタを知ることが出来る．この赤い矢印の順番にフレーム 図 5 にカーネルバージョンが同じでも，バイナリが異 ポインタを辿る事によってコールスタックをトレースする なるために異なるコールトレースを出力してしまう例を示 ことができる． す．5 (a) は vanilla カーネルを通常のコンフィグでビルド Linux のコールトレース: Linux のコールトレースの生 したもので，図 5 (b) はカーネルコンフィグの “ Spinlock 成はフレームポインタがスタックに積まれていないこと and rw-lock debugging: basic checks ”，“ Mutex debug- を前提にしているため，少し異なる方法で行われている． ging: basic checks ”，“ Lock debugging: detect incorrect Linux のコールトレースでは実行中の関数を取得した後は， freeing of live locks ”，“ Lock debugging: prove locking フレームポインタを辿ることができないため，スタックか correctness ”，“ Lock dependency engine debugging ” を c 2014 Information Processing Society of Japan 4 Vol.2014-OS-130 No.11 2014/7/28 情報処理学会研究報告 IPSJ SIG Technical Report 図 5 異なるバイナリのカーネルによって生成されるコールトレース 有効にしてロックを取る際にログを取るように設定したも のである．このようにコンフィグなどが異なるため，同じ db カーネルバージョンでも多様なバイナリが存在し，同じバ 1897 表 1 収集したクラッシュログ fb iz ltp ub total 1864 10294 1664 3095 1774 グでもコールトレースが異なってしまうことがある． 3. Linux における ReBucket の有用性 本研究はバグの分類方法である ReBucket を Linux に ログを収集した．5 つのマシンで異なるワークロードを用 いる理由は，現実のクラッシュログは同じバグでもユーザ によって異なるワークロードによってクラッシュを引き起 適用してその効果を定量的に評価する． こすためである． 3.1 調査方法 3.2 調査環境 Linux での ReBucket の効果を調査するためにひとつの 調査に用いたカーネルは，vanilla カーネルのバージョン root cause に対応する複数のクラッシュログと，異なる 2.6.32.60 で，バグの挿入はファイルシステムの ext3 に行っ root cause によってクラッシュした際の複数のクラッシュ た．クラッシュログを集めるために使用したワークロード ログが必要となる．しかし，実際の Linux カーネルバグに は UnixBench (ub) ver.5.1.3 [10]，FileBench (fb) ver.1.4.9 よって生成されたクラッシュログから調査をすることは難 [11]，DBench (db) ver.4.0 [12]，IOzone (iz) ver.3.420 [13]， しい．なぜなら，Redhat の提供する [6] のように実際に Linux Test Project (ltp) [14] であった．また，同じワーク ユーザから送付されたクラッシュログを用いることは可能 ロードでもクラッシュした際に生成されるクラッシュログ だが，その root cause を判別できないため，分類した結果 が異なる可能性があるため，ひとつの root cause に対して が正しいか判断できないためである．また Bugzilla のよ 同じワークロードを 5 周実行させた（5 回の内全ての場合 うなバグ管理システムに報告されたバグを再現して，複数 でクラッシュするわけではない）． のクラッシュログを集めることも困難で現実的ではない． クラッシュログ: 上記の方法で収集したクラッシュログ そのため，本研究では Linux カーネルにソフトウェア の数をワークロードごとに表 1 に示す．5 つのワークロー フォールトインジェクションを行うことにより，Linux カー ドを用いて収集したクラッシュログは全てで 10294 件で， ネルバグの再現を行う．フォールトインジェクタには，実 それらに対応する root cause は全てで 850 種類であった． 在するソフトウェアバグを調査 [9] して作られたバグモデ パラメータ: 2.2.3 節で解説した最適なパラメータの決定 ルを基に作成された SAFE [8] を用いた． 方法を用いてパラメータ c, o, d を決定した．本調査では 本調査では SAFE によって生成された 7096 種類のバグ 400 件のクラッシュログをデータセットとして，最適なパ をひとつずつ挿入し，そのカーネル上でワークロードを実 ラメータを求めた．本調査ではパラメータをそれぞれ c = 行してクラッシュした際に生成されるクラッシュログを用 0.4，o = 0.4，d = 0.3 として ReBucket を行った． いて分類を行った．分類を行うためにひとつのバグ (root cause) に対して複数のクラッシュログが必要であるため， 3.3 調査結果 5 つのマシンで異なるワークロードを実行してクラッシュ 3.3.1 評価方法 本調査では ReBucket の結果を評価するために，ふたつ c 2014 Information Processing Society of Japan 5 Vol.2014-OS-130 No.11 2014/7/28 情報処理学会研究報告 IPSJ SIG Technical Report の評価方法を用いて評価を行った．(1) ひとつ目は，同じ シュログが同じようなコールトレースを持っていた場合， root cause に対応するクラッシュログがいくつの bucket これまでの実行履歴を表す “ ? ” 付きの関数があることに に分類されたか，というものである．これは，ベストケー よって正しく分類ができるためである． スでは同じ root cause に対応するクラッシュログは全て フォールトインジェクタの SAFE では同じ関数内に複 同じ bucket に分類される．(2) ふたつ目は，同じ bucket 数のバグを挿入する．たとえば，最大で一つの関数の中に の中に何種類の root cause に対応するクラッシュログが 63 個のバグを挿入している．このように，同じ関数内に存 分類されたか，というものである．これは，ベストケース 在するバグは同じような関数の実行順序を辿るものが多い ではひとつの bucket には一種類の root cause に対応する とため，同じ bucket 内に同じ関数内のバグが分類されて クラッシュログのみが分類される．また，2.3.3 に挙げた しまうことがある．そのため，実際には一つの関数に何個 ような問題があるため，コールトレース中の “ ? ” が付い もバグが存在する可能性は低いということと，デバッグの た関数を使って分類した場合と，取り除いて分類した場合 際には同じ関数のバグごとに纏まるだけでも負担がかなり で以上のふたつの評価を行う． 減り，関数の特定が容易になることから，同じ関数内に挿 3.3.2 評価方法 1 入されたバグは同じバグという考えによって評価方法 2 を 同じ root cause に対応するクラッシュログがいくつの 関数ごとに評価したものを図 7 に示す． bucket に分類されたかを図 6 に示す．“ ? ” 付きの関数を “ ? ” を有効にして分類した場合では，ひとつの bucket 有効にした場合，ひとつの bucket に集まったバグは全体 に一種類のバグのみが分類されたものは全体の約 72 % と の約 73 % であった．それに対して， “ ? ” 付きの関数を なり，同じ関数へのバグを異なるバグと考えて評価した 取り除いた場合，ひとつの bucket に集まったバグは全体 ものよりも，約 22 % 増加した．“ ? ” なしの場合でも， の 約 78 % であった．“ ? ” が付いた関数は関数が引数 約 68 % が一種類のバグのみが分類された bucket となり， に取る関数ポインタや，前にスタックに積んであった関数 前の評価のものよりも約 23 % 増加した．また，“ ? ” あ のリターンアドレスによって表示されるため，実際は同じ りの場合，なしの場合でもひとつの bucket に分類された コールトレースでも環境や実行履歴などによって出力され root cause は最大でも 11 種類に減少していた． るコールトレースが異なる場合がある．そのため，“ ? ” 3.3.4 うまく分類されなかったケース を有効にして分類を行った場合，同じコールトレースでも 評価方法 1 について，同じ種類のバグが複数の bucket 実行履歴などによって別々の bucket に分類されている場 に分類されてしまったクラッシュログについて調査し，そ 合がある．“ ? ” を取り除いて分類した場合，このような の原因についての分析を行った．その結果，複数の bucket 理由によって別々の bucket へ分類されていたクラッシュ に分類されてしまった原因として 2 つのパターンを確認す ログが同じ bucket へ分類されるため，“ ? ” を取り除い ることができた．2 つのパターンについて例を示して説明 て分類した場合の方が精度が高くなっている． する．また，ひとつの bucket に複数のバグを分類してし 3.3.3 評価方法 2 - “ ? ” あり場合 - まった理由についても考察を行う． 同じ bucket の中に何種類の root cause に対応するク 原因 1: ひとつ目の原因は “ ? ” の有無によって複数の ラッシュログが分類されたかを図 7 に示す． “ ? ” 付き bucket に分類されているものであった．具体的な例を図 8 の関数を有効にして分類した場合，bucket の中に一種類の に示す．コールトレースの横に “ * ” がある関数がふたつ root cause に対応するクラッシュログのみが分類されたも のコールトレース間で共通しているものである．図 8 の場 のは全体の約 50 % であった．図 7 ではひとつの bucket 合，“ ? ” が付いた関数のみが異なっており，“ ? ” の付い に 10 種類のバグが分類されたものまで示しているが，最 た関数を除去すると全く同じコールトレースになるが，こ 大ではひとつの bucket に 70 種類のバグが分類された．ま の二つのクラッシュログは異なる bucket へ分類されてい た，図 7 に示している 1 から 10 種類のバグが分類された た．このように，ReBucket では共通する関数がトップの bucket は全体の 95 % であった． 位置に近いほど，または共通する関数の位置が差が近いほ “ ? ” 付きの関数を取り除いて分類した場合， bucket の ど重み付けをするため，トップに近い位置やコールトレー 中に一種類のバグのみが分類されたものは全体の約 45 % ス間で別の位置に “ ? ” のついた関数がある場合，誤って であった．また，ひとつの bucket には最大で 74 種類の 分類してしまう場合がある． root cause に対応するクラッシュログが分類されていた． 原因 2: ふたつ目の原因はコールトレース間のトップに 図 7 に示している 1 から 10 種類のバグが分類されていた 近い位置の関数のみが共通していて，下のコールトレース bucket は，全体の 91 % であった． は異なる関数であるというものであった．具体的な例を図 “ ? ” 付きの関数を有効にして分類した場合，取り除い 9 に示す．“ * ” がついている関数の str2hashbuf sgned() て分類した場合よりも精度が高くなった．これは，評価方 と ext3fs dirhash() が共通しているが，それより下の関数 法 1 の場合とは逆に，異なる root cause に対応するクラッ は共通していないことが分かる．このようにクラッシュを c 2014 Information Processing Society of Japan 6 Vol.2014-OS-130 No.11 2014/7/28 情報処理学会研究報告 IPSJ SIG Technical Report 図 6 評価方法 1 図 7 評価方法 2: 起こした関数の直近のみが共通するコールトレースの場 は “ ? ” を除いて分類した場合，有効にして分類した場合 合，ReBucket では異なるの bucket へと分類されてしまう よりも異なる bucket に分類されるバグの割合が低くなっ 可能性がある． ていた．これは 3.3.4 節の原因 1 で示したように “ ? ” が し か し ，こ の 例 で 示 す よ う な コ ー ル ト レ ー ス を 生 原因で同じバグが別々の bucket へ分類されてしまう，と 成するバグは現実に即したバグでない可能性がある． いうことがなくなったためである．評価方法 2 では “ ? ” こ の 例 の 場 合 ，SAFE に よ っ て 挿 入 し た バ グ は 関 数 を有効にして分類した場合，除いて分類した場合よりも異 ext3fs dirhash() へのものであり，クラッシュを起こし なるバグが同じ Bucket に分類される割合が低くなってい た RIP の str2hashbuf sgned() との距離が近い．このよう た．これは，別々のバグでも “ ? ” がない場合類似してい に多くのシステムコールで共通して呼ばれるような関数で， るコールスタックが “ ? ” つきの関数の違いによって異な その関数に入ったらすぐクラッシュするバグは，リリース る bucket に分類されたためであると考えられる． 前のデバッグによって取り除かれているようなバグである 2.3.3 節で “ ? ” のついている関数は実際のコールトレー 可能性があるため，テストケースとしてあまり良いバグと スではないと述べた．しかし，“ ? ” のつく関数は関数へ は言えない．本調査ではフォールトインジェクタを用いた の引数や以前にスタックに積まれたリターンアドレスのよ ためこのようなバグが生成されてしまったと考えられる． うな実行履歴なので有用な情報を示していると言える．そ その他の原因: 上に挙げた 2 つの原因以外では，コール のため，異なるバグのコールトレースが類似している場合 トレースが全く異なるものや，全て “ ? ” つきの関数に でも実行履歴の違いによって別々の bucket に分類される なっているものなどが挙げられる．このような例はコール ことがある．また，“ ? ” を無くしてしまうことによって トレースのみで分類を行う ReBucket では分類を行う事が 極端にコールトレースが短くなってしまうものもあり (“ ? 困難である． ” を除いた場合コールトレースが 2 つになってしまうもの bucket に複数のバグが分類された理由: ひとつの bucket に複数のバグが分類された理由の一つは，バグを挿入した システムが ext3 だけであるため，似たようなコールトレー スのクラッシュログが集まってしまったと言うことが挙 を確認した)，そのようなバグの分類にも実行履歴を示して いる “ ? ” は有効であると言える． 4. 関連研究 げられる．本来開発者に送付されるクラッシュレポートは Microsoft 社 は Windows Error Reporting を用いてユー 様々なシステム (e.g. デバイスドライバ，ネットワークな ザからクラッシュログを集めており，そのクラッシュログ ど) のバグが原因でクラッシュした際に生成されるものな を Bucketing[3] によって root cause ごとに分類している． ので，コールトレースもその分異なるものが多いと考えら しかし，Bucketing は Windows に固有のさまざまな知識 れる．しかし，本研究では ext3 という限られたシステム を利用したアドホックな手法となっており，Linux などの のバグによるクラッシュログを対象にしているため，コー 他の基盤ソフトウェア上のシステムに適応できるものでは ルトレースが類似しているものが多く，複数のバグが同じ ない． bucket に分類されてしまうということが起こってしまった また，Bucketing ではうまく分類できなかったクラッ と考えられる．ふたつ目の原因は，同じプロセスでクラッ シュログを分類するために提案された方法として，Crash シュをしているとコールスタックも類似してしまう，とい Graph [15] と 本研究で用いた ReBucket が知られている． う点である．実際に図 7 の関数ごとで見た場合の 10 種類 Call Graph は Bucketing の分類で同じ root cause のク のバグが分類されている bucket では，分類されたクラッ ラッシュログが複数のグループに分類されてしまう問題に シュログのプロセスは全て umount であった． 対処している．これは，分類されたグループ内のコールト 3.3.5 “ ? ” の影響について レースを集約してグラフにすることで，他のグループとの コールトレース中の “ ? ” の影響は評価方法 1 の場合で c 2014 Information Processing Society of Japan 比較を行い同じ root cause に対応するグループを判別す 7 Vol.2014-OS-130 No.11 2014/7/28 情報処理学会研究報告 IPSJ SIG Technical Report 図 8 原因 1 の例 図 9 原因 2 の例 るというものである． ものは全 850 種類のバグの内，73% ，“ ? ” を取り除いた 一方，本研究で用いた ReBucket は，クラッシュレポート コールスタックの場合では 78% であった．一つの bucket のコールスタックの部分に注目し，類似したコールスタッ に一種類のバグのみが分類されたものは，全体の bucket クを持つクラッシュレポートを同グループに分類する．[7] の 50% で，“ ? ” を取り除いたコールスタックの場合で によれば ReBucket は Bucketing に比べ 9 % の精度の向 は，45% であった．異なるバグでも同じ関数内のバグを同 上が示されている．この二つのバグ分類方法は Windows じバグとしてみた場合は，全体の 72% の bucket は一種類 製品のバグを対象にしているが，本研究では Linux カーネ のバグのみが属する bucket であった．また， “ ? ” を取 ルのバグを対象に分類を行った． り除いたコールスタックの場合では，68% であった． Palix らは Linux カーネルバグの時系列による変化を調 同じ種類のバグが複数の bucket に分類されてしまった べている．Linux カーネルバグは 10 年間で殆ど変わらな 原因についての分析を行ったところ，“ ? ” 付きの関数が い件数を維持しており，これらのバグが原因でユーザから 異なるために異なる bucket に分類されたものと，バグを 送付されるクラッシュログの分類が ReBucket で可能なら 挿入した関数とクラッシュを起こした関数が近いため異な ば，開発者の負担を軽減することができる．また，Palix る bucket に分類されてしまったケースを確認した． らは Linux カーネルバグはファイルシステムのバグが多い 調査結果から，Windows のバグ分類手法である ReBucket こと示しており，本研究もファイルシステムのバグを対象 は Linux で用いる場合，Windows で用いる場合よりも有 にバグの分類を行っている． 効ではないことが分かった．Windows ほど分類が有効で 5. まとめ は無い理由としては Linux 特有のコールトレースの生成方 法が挙げられる．Linux ではフレームポインタがないこと 本稿では，Windows Error Reporting で用いられるバグ を前提にコールトレースを生成しているため，実際のコー の分類方法である ReBucket を Linux カーネルバグに適用 ルトレースとは異なる関数が “ ? ” つきで出力されること した場合の効果について調査し，定量的な評価を行った． になる．このため，Linux では Windows のように効果的 ソフトウェアフォールトインジェクタの SAFE を用い にバグの分類が行えないと考える． てカーネルコード中にバグを挿入し，クラッシュした際の クラッシュログを収集した．集まったクラッシュログ全 5.1 今後の課題 10294 件，850 種類に ReBucket を適用してバグの分類を 本稿では vanilla カーネル ver.2.6.32.60 の ext3 にバグ 行った．分類結果から同じ種類のバグがいくつのバグに分 を挿入して生成されたクラッシュログを対象に調査を行っ 類されたか，一つの bucket に何種類のバグが分類された た．しかし，実際に開発者には，さまざまなディストリ か，についての評価を行った． ビューション，カーネルバージョン，コンフィグレーショ 同じ種類のバグが一つの bucket に集まって分類された c 2014 Information Processing Society of Japan ン，システムでクラッシュした際のクラッシュログが送付 8 情報処理学会研究報告 IPSJ SIG Technical Report Vol.2014-OS-130 No.11 2014/7/28 されるため，ReBucket の効果を評価するためには様々な シチュエーションでのクラッシュログを対象にする必要が ある． 参考文献 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] D. Wheeler. SLOCCount. http://www.dwheeler.com/. Nicolas Palix, Gaël Thomas, Suman Saha, Christophe Calvès, Julia Lawall, and Gilles Muller. Faults in linux: Ten years later. In Proceedings of the Sixteenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XVI), pages 305–318, 2011. Kirk Glerum, Kinshuman Kinshumann, Steve Greenberg, Gabriel Aul, Vince Orgovan, Greg Nichols, David Grant, Gretchen Loihle, and Galen Hunt. Debugging in the (very) large: Ten years of implementation and experience. In Proceedings of the 22nd Symposium on Operating Systems Principles (SOSP ’09), pages 103–116, 2009. MoZilla: Crash Stats. http://crash-stats.mozilla.com. Apple: Technical Note TN2123: CrashReporter. http://developer.apple.com/library/mac/#technotes/. Linux Kernel Oops. http://www.kerneloops.org. Yingnong Dang, Rongxin Wu, Hongyu Zhang, Dongmei Zhang, and Peter Nobel. Rebucket: A method for clustering duplicate crash reports based on call stack similarity. In Proceedings of the 2012 International Conference on Software Engineering (ICSE ’12), pages 1084–1093, 2012. Marcello Cinque, Domenico Cotroneo, Roberto Natella, and Antonio Pecchia. Assessing and improving the effectiveness of logs for the analysis of software faults. In Dependable System and Networks (DSN ’10), pages 457– 466, 2010. João Durães and Henrique Madeira. Emulation of software faults: A field data study and a practical approach. IEEE Transactions on Software Engineering (TSE ’06), 32(11):849–867, 2006. UnixBench. http://code.google.com/p/byteunixbench/. Filebench. http://sourceforge.jp/projects/sfnet filebench/. DBENCH. http://dbench.samba.org/. IOzone. http://www.iozone.org/. Linux Test Project. http://ltp.sourceforge.net/. Nachiappan Nagappan Sunghun Kim, Thomas Zimmerman. Crash graphs: An aggregated view of multiple crashes to improve crash triage. pages 486–493, 2011. c 2014 Information Processing Society of Japan 9