独自の方式でバグに挑む：米Coverity社Chief Technology Officer Ben Chelf氏

ソフトウエアにはバグがつきものだとはいうものの、バグが残ったまま市場に出すわけにはいかない。バグを修正するにはそれを見つける必要があるが、バグを発見するにもまた多くの手間が掛かる。米Coverity社は、ソースコードに潜むバグを検出するソフトウエアツールを手掛ける企業だ。同社は「静的解析」というものの、既存の静的解析とは一線を画す手法を採り、動的解析ツールと同等の高い検出率と、低い誤検出率が特徴である。なぜ多くのバグを正しく検出できるのか。その秘密を、同社の基礎技術を開発したBen Chelf氏に聞いた。

[山口哲弘，EE Times Japan]

EE Times Japan（EETJ）　動的解析と静的解析の違いは何か。

Chelf氏　動的解析は、ソフトウエアを実際に実行させて、そのときの振る舞いを調べる手法である。実際に動いている状態を調べるので、確保したメモリ領域の解放し忘れ（メモリリーク）のような見つけにくいバグも検出できる。ただし、解析のための特別な命令を埋め込むので、厳密には、通常実行させたときと異なる振る舞いをしていることになる。また、ソフトウエアの中には必ず条件分岐があるので、全てのコードを漏れなく実行させるようなテストシナリオを作成する必要がある。

　静的解析は、ソースコードそのものを調べる手法だ。ソースコード全体をくまなく調べられるが、主にパターンマッチングによるこれまでの静的解析ツールでは、メモリリークのようなバグの検出は難しく、さらに誤検出率が高かった。当社の「Prevent」は、静的解析手法を採りながら、動的解析手法並みにバグ検出率が高く、誤検出率が低い。静的解析なので、ソースコード全体を調べられる。

EETJ　どのように解析するのか。

Chelf氏　解析対象のソースコードから、当社独自の「ソフトウエアDNAマップ」を作り、それを解析するのがポイントだ。ソフトウエアDNAマップは、当社の解析手法の鍵を握る技術である。当社のツールでは、まず、ソフトウエアDNAマップを生成するために、ソースコードをコンパイルする。そのときに使うのは当社独自のコンパイラである。

　通常のコンパイラは、ソースコードからオブジェクトコードを生成するのに対して、当社のコンパイラは「アブストラクトシンタックスツリー（AST：Abstract Syntax Tree）」を生成する。通常のコンパイラが一般にコンパイル処理時に踏む2段階の処理のうち、ソースコードから中間表現を生成する第1段階の処理に相当する。

　その際、ユーザーが利用しているコンパイラの処理内容を模倣する。なぜなら、コンパイラの種類やコンパイラに与えるオプションによって、生成されるオブジェクトコード（機械語命令）が変わるからである。当社のツールは、ユーザーが利用しているコンパイラの種類とコンパイラオプションを調べ、実際に生成されるオブジェクトにできるだけ近い状態のASTを生成する。静的解析でもビルドシステムが関与する点が重要である。

　ASTはソースファイルごとに作られる。ソフトウエアDNAマップは、それら複数のASTと各ソースファイルに加え、幾つかの追加情報を含んでいる。追加情報とは、ソースファイル同士の依存関係や、コールグラフ（関数の呼び出し関係）、各関数のコントロールフローグラフ（条件分岐の様子など関数内部での制御の流れ）だ。

EETJ　ASTは、具体的にはどのような情報を含んでいるのか。

Chelf氏　解析に適するようツリー構造にしたバイナリ形式のソースコード表現である。

　例えば「if(x==0) printf("Hello");」という単純なコードであれば、次のようなツリーを描く。

　まず「if」ブロックを書き、その下に3つのパス（制御の流れ）を出す。1つのパスは、「条件」ブロックにつなげ、このブロックは「==」という表現になる。残りの2つは「真」と「偽」のパスである。

　「==」ブロックの下には、「変数」と「定数」の2つのパスを出し、それぞれ「x」ブロックと「0」ブロックにつなげる。

　一方、「真」のパスにはprintf関数のツリーが続く。「偽」のパスの下には何もない。ソースコード上にelse句がないからだ。

　このようなツリー構造から、コールグラフやコントロールフローグラフを生成する。

EETJ　何をよりどころとして、どこにどのようなバグがあると判断するのか。

Chelf氏　まずコールグラフに注目する。関数の呼び出し関係を、main関数から始まるツリーで表し、ツリーの末端の関数から解析を始める。ここでは、各関数の振る舞い――どのような引数を取り、引数に対してどのような処理をしているか、そしてどのような値を返しているのかを調べる。この関数が持っている潜在的な副作用――メモリ領域の確保や、メモリ領域の解放、メモリ領域に対するロックやアンロックといった内容も調べる。

　次にコントロールフローグラフを使って、各関数の中身を解析する。例えば次のようなコードを考える（変数の宣言などは省略した）。関数hでは、malloc関数によってメモリ領域を確保し、その先頭アドレス（ポインタ）を単純に返しているとする。

if (p==0) a=h();
if (p==0) free(a);

　まずパスのシミュレーションを実行する。

　最初のif文では、条件が真のときと偽のときの2つのパスに分かれる。真のパスでは関数hを呼び出し、偽のパスでは何もしない（else句がない）。2つのパスは、次のif文のブロックに接続する。このif文でも2つのパスに分かれ、真のパスではfree関数を呼び出し、偽のパスでは何もしない。

　当社のツールは、全てのパスを解析する。各パスで、変数の値がどのように変更されるのかを調べる。例えば、最初のif文の真のパスに突入したときのpの値は0である。そして、関数hを呼び出す。この時点ですでに関数hの解析は終わっているので、メモリが確保され、変数aにそのポインタが格納されることが分かる。

　真のパスが終了すると、次のif文の分岐になる。このif文に到達した時点の変数pの値が0であると分かっているから、この場合、2つ目のif文では真のパスしか絶対に通らないと判断する。一方、最初のif文で偽のパスを通った場合は、pの値は0ではないと分かっている。従って、2つ目のif文では偽のパスしか通らないことが分かる。これをブール式の充足可能性（Boolean Satisfiability）と呼ぶ。つまり、このコード全体ではパスを通る可能性として4通りが考えられるが、ブール式の充足可能性を適用すると、最初のif文が真のときは必ず次のif文も真になり、最初のif文が偽のときは必ず次のif文も偽になる。このコードは、メモリリークや、確保していない領域の解放は起こさない。バグはないと判断する。

　もしも、2つ目のif文の条件式が「q==0」だった場合は、4通りのパスを通る可能性がある。すなわち、最初のif文の真のパスでメモリを確保しながら、2つ目のif文では偽のパスを通ってメモリを解放しないままこの関数を抜ける場合がある。このときは、メモリを確保したまま解放していないことを認識するので、バグがあると指摘する。当社の手法は、一種のシミュレーションである。ただし、実行時の全ての値を保持しているわけではない。

　先日発表した「Software Readiness Manager」や「Architecture Analyzer」も、その根本にあるのはソフトウエアDNAマップである。

　Software Readiness Managerは、ソフトウエアの複雑度やバグの量、コメントの少なさといった、ソフトウエアに潜むリスクを調べるツールである。例えば複雑度に関しては、コントロールフローグラフの複雑度（パスの混雑度合い）を可視化して画面に表示する。

　Architecture Analyzerは、ソフトウエアを構成するモジュール間の依存関係や複雑度を調べるツールである。コントロールフローグラフの複雑度やコールグラフを可視化して画面に表示する。ソフトウエアDNAマップが備える情報を、目的に応じた形式で表示する。当社のツールには全て、ソフトウエアの完全性を高める補助ツールという基本方針がある。

---

Ben Chelf（ベン・シェルフ）氏

1999年、米Stanford Universityの修士課程在籍中にコンピュータサイエンスの研究チームに属し、ソフトウエアのソースコードの静的解析技術に関する研究を始める。2003年に米Coverity社を、同社CEOのSeth Hallem氏らと共同で設立した。Stanford Universityで、コンピュータサイエンスの学士号と修士号を取得している。