Soot を使って Java プログラムを解析する

石尾 隆 (ishio .AT. ist.osaka-u.ac.jp)
December 6, 2007 last updated
July 12, 2006 created

このメモは，Windows 環境で Soot を使って Java プログラムを解析する方法について 経験に基づいて記述しています． このメモは書きかけです．内容は随時変更される可能性があります． もし，誤りや疑問などありましたら，ご指摘いただけると幸いです．

このメモでは，Soot の機能全体を網羅するつもりはありませんが， プログラム解析処理を実装するにあたっての Soot から提供されるデータとか， 使っていて得られた経験を随時蓄積していくつもりです．

目次

Soot とは

Soot: a Java Optimization Framework は，McGill 大学のプロジェクトとして開発されている Java バイトコードの解析系です．Aspect Bench Compiler "abc" なんかで利用されていたりします．

Soot は，Javaのバイトコードを解析して Jimple と呼ばれる 中間表現に変換します．他にも，もっと生バイトコードよりの Baf， SSA 形式である Shimple など，別の表現も用意されています． Java Optimization Framework という名の通り，一度バイトコードを中間表現に落として 開発者が定義した最適化処理などを適用した後， 再びバイトコードに戻すというのが本来の用途だと思われます． しかし，中間表現に落とされたものには制御フロー，データフローなどの 最適化以外のプログラム解析にとっても有用な情報が載っていますので， それをうまく利用することができれば，プログラム解析ツールの 開発コストを下げることができます．

Soot の特徴は，処理が複数のフェイズ（内部では「パック (pack)」と呼ばれています）に 分割されており，任意のフェイズに新たな処理を追加することができることにあります． また，フェイズごとに固有のオプションを取ることができ， 様々な設定を制御することができるようになっています． 何も用意しなくてもバイトコードからその中間表現を取り出すことはできますが， 途中にコード変換や最適化処理を挿むことで，様々な出力を獲得することができます．

Soot のインストール

Soot は，いくつかのライブラリに依存しています．

安定版を使う:

安定版の Soot を実行するには，以下のパッケージを使います．現在の安定版は 2.2.4 です．

Paddle の Nightly-Buildを使う: Soot 用の points-to analysis の実装である paddle フレームワークの nightly-build の最新版を実行するには， Nightly Build ページにある にある以下のものが必要です．ページでは，微妙にリンクが分散していますし， 良く似た名前のものもいくつかあるので注意してください （コンパイル用と実行用でパッケージが違ったりしているようです……何が違うのか，いまいち分かっていませんが）．

Paddle のページに配置されている soot などのクラス群は， soot 自身の nightly-build とはバージョンが違います． Paddle のオプションの定義は paddle パッケージに入っていますが， そこから自動生成されるコードが soot パッケージに入っているので， paddle と soot のバージョンが違うと，オプション処理を誤るので注意が必要です．

ただし，Eclipse などからソースコードを少しは参照したいときは， Soot の nightly-build 版（soot-2327 など）のソースを割り付けておくとそれなりにうまく読めます （Soot の安定版からは，いくらか構成が変わっているようです）．

Soot の実行

実行時は，必要なファイル一通りにクラスパスを通す必要があります． 数が多いので，あらかじめバッチファイルなり， シェルスクリプトなり，Eclipse 実行環境を整える必要があります．

以下は，stable 版の soot を Cygwin から実行するときのコマンドを整形したものです． target ディレクトリに解析対象であるtest.HelloWorldクラスが入っているものとします．

java -Xss30m -Xms400M -Xmx900M 
     -Djava.library.path=. 
     -classpath "sootclasses-2.2.4.jar;polyglot.jar;jasminclasses-2.2.4.jar" 
     soot.Main 
     -cp "target;
          C:\Program Files\Java\j2re1.4.2_12\lib\charsets.jar;
          C:\Program Files\Java\j2re1.4.2_12\lib\jsse.jar;
          C:\Program Files\Java\j2re1.4.2_12\lib\rt.jar;
          C:\Program Files\Java\j2re1.4.2_12\lib\jce.jar" 
     -whole-program -f jimple 
     -p cg.cha enabled:false 
     -p cg.spark verbose:true,enabled:true,propagator:iter
     --app test.HelloWorld

Main の後ろにある "-cp" オプションは，Soot が 解析する対象のクラス群のパス（JDK 含む）を指定しています． 筆者が利用している環境では，1.4 のクラス群を明示的に指定しています．

-whole-programオプションは，コールグラフ生成などの 「全体を解析する」タイプの解析系を有効にしています． 今回は特に意味がありませんが，points-to set analysis などを有効にしたいときには 必ず指定する必要があるオプションです． -f jimpleは，出力が Jimple であることを指定しています．

-pがフェイズオプションと呼ばれるもので， ここでは paddle フレームワークによる context-insensitive points-to set analysis を 有効にしています． 詳細については Soot Phase Options を参照してください．

最後の HelloWorld が，解析対象クラスです．-appオプションは， HelloWorld から直接・間接的に参照しているクラス群も 解析対象であることを指定しています．どれがライブラリクラス（解析対象外）であるかなどは， 別途指定可能です．これについては， Soot command-line optionsを参照してください．

これを実行すると，test.HelloWorld クラスを読み込み，sootOutputディレクトリに test.HelloWorld.jimpleという名前のファイルが生成されます． この中身が，soot によってバイトコードから変換された jimple コードとなります．

このほかに使うオプションとしては，ソースコードでの行番号情報を保存する-keep-line-number， 動的に生成されるために普通の利用関係では到達できないクラス （jEdit 4.2 なら org.gjt.sp.jedit.options. のクラス群など）を 解析対象に加える-dynamic-package オプションなどがあります．

Soot の大まかな構造

フェイズの概念

Soot の特徴は，処理が複数のフェイズに 分割されており，任意のフェイズに新たな処理を追加することができることにあります． Soot は，各フェイズで実行すべき処理を Pack というオブジェクトに管理させています． たとえば Jimple コードの各種最適化のためのコード変換を 「Jimple Optimization Pack」に格納しています．

開発者は，自分が追加したい解析処理を Transformer クラスのサブクラスとして実装し， 実行したいタイミングに対応するパックに登録します． フェイズは全体解析用とメソッド単位解析の二種類に区分されており， 全体解析用フェイズには SceneTransformer を， 単体解析用フェイズには BodyTransformer を追加します． 使用する種類を間違うと，実行時に ClassCastException が発生します （少なくとも Soot の現時点のバージョンは，登録時にチェックは行われません）．

以下に，Soot が バイトコードから Jimple 表現を取り出した後に 適用するパックの順序を示します．

Jimple 命令を取り出した「後」しか書いていませんが， これは Jimple を抽出する最初のパック，jb および jj の振る舞いが固定（ハードコーディング） されており，これらのパックに自作の BodyTransformer を追加できないためです．

各フェイズの詳細は， Soot Phase Optionsに記述されています． また，実際に Soot で利用可能になっているフェイズの種類は，-phase-list オプションで知ることができます．

生成するデータの形式によって，有効になるフェイズが違います． Grimp 形式なら gop が有効とか，baf 形式なら bop が有効とか， ある程度は名前から識別できます． しかし，現在の Soot では，たとえば tag (Tag Aggregator) フェイズは baf を生成するときにのみ有効といった， あまり直観的ではない振る舞いもあるようです． ドキュメントを十分に確認するのも大切ですが， soot.PackManagerクラスのrunPacks()メソッドや runBodyPacks(SootClass)メソッドのコードを 直接確認したほうが早いこともあります．

「コード変換オブジェクト」の雛形

以下に，メソッドごとの解析を実現するための BodyTransformer のサブクラスの雛形を示します． BodyTransformer は， internalTransform(Body b, String s, Map m)というメソッドを持っているので， それをサブクラス側でオーバーライドし，任意の処理を記述します． Body はそのメソッドの命令列などの情報を格納しています．文字列は現在のフェイズ名を， Map はオプション群を格納しています． 

public class TestBodyTransformer extends BodyTransformer {

  public void internalTransform(Body b, String s, Map m) {
    // ここで変換処理や，必要な解析を実行
  }

  // シングルトンパターンとして実装する
  static private TestBodyTransformer theInstance = null;

  private TestBodyTransformer() {
  }
  
  public static TestBodyTransformer v() {
    if (theInstance == null) {
      theInstance = new TestBodyTransformer();
    }
    return theInstance;
  }
}

Soot に機能を追加して実行する

この作成した Transformer クラスを，Soot に登録して実行することになります． 以下のように Transformer を追加してから Soot 本体の処理を実行するような main メソッドを定義することができます． 

// "jtp" Java Transformation Pack に
// TestBodyTransformer を追加して Soot 本体を起動するプログラム
// "jtp" はコールグラフ構築などの処理より後，
// 最適化を実行するより前に適用される．
public static void main(String[] args) {
  if (args.length == 0) {
    System.out.println("Syntax: java "+
         "soot.examples.instrumentclass.Main --app mainClass "+
         "[soot options]");
    System.exit(0);
  }            
  // TestBodyTransformer クラスのインスタンスを追加
  // 注: TestBodyTransformer.v() はシングルトンを返す
  PackManager.v().getPack("jtp").add(
    new Transform("jtp.test", TestBodyTransformer.v()));
  soot.Main.main(args);
}

パックに処理を追加するとき，Transform クラスの第一引数の 文字列の先頭が Pack の名前と一致しないと， 実行時にエラーが起きるようです （現在の Soot では，追加時のエラーチェックはないようです）．

プログラム解析の実装方法

メソッドの解析は，基本的に Body クラスの中身を調べることになります． あまり詳しく調べたわけではありませんが， 少なくとも以下のような方法で，情報にアクセスできるようです．

points-to set 解析のためのオプション

共通のオプション

必須オプション: points-to set 解析のような「全体解析」を有効にします． これが指定されない場合，soot は個別のメソッド単位だけの解析を適用します．

-whole-program

JDKなど，ライブラリを含むすべてのクラスを解析対象とする場合は，以下のオプションも指定します．

-include-all

コールグラフ解析のオプション

コールグラフの作り方は，points-to set analysis の結果に影響を与えます．

通常のコールグラフ解析では，forName メソッドや newInstance メソッドを処理しないため， コールグラフが不完全となります． その結果，エントリメソッド（main）から到達できないと判定されたメソッドにおいて points-to set の値が手に入らなかったり， CallGraph オブジェクトに「実行されうるメソッド」を要求しても何も得られなかったりします．

GUI ベースのプログラムやスレッド処理を使っているプログラムを解析する場合は， forName や newInstance を処理するよう，call graph フェイズに，以下のようにオプションを指定します． 

-p cg verbose:true,jdkver:4,safe-forname:true,safe-newinstance:true

また，JDK メソッドを解析対象に加えるために，-include-allオプションをさらに追加する

spark フレームワークを使用する場合

現時点では，spark フレームワークのほうが高速かつ安定している（クラッシュしない）ようです． 細かい設定はいくらかありますが，とりあえず有効にするだけで十分なようです． spark は context-insensitive analysis です．context-sensitive な結果が必須の場合は，paddle を使います． 

-p cg.spark verbose:true,enabled:true

paddle フレームワークを使用する場合

paddle フレームワークでは，かなり細かく解析方法を指定することができます．

context-insensitive analysis でよければ，以下のような構成が考えられます．

-p cg.paddle enabled:true,verbose:true,context:insens,bdd:false

このとき，JavaVM の引数として，-Xss30m -Xmx800Mというように，大きな値をセットしておきます．

bdd オプションは，true に設定すると， 内部表現を BDD に切り替えることでメモリを節約します． insensitive analysis の場合，false で十分実行可能で， BDDを使うと逆に実行時間が遅くなるようです．

context-sensitive analysis については， とりあえず，文献[1]で良いトレードオフであると指摘されている object-sensitive analysis についてだけ調査しています．

object-sensitive analysis では，メモリが足りないので， BDDの指定はほぼ必須なようです． で，backendオプションでどのBDDを指定するのかが問題となりますが， Windows 上では，javabdd を指定するのが無難なようです．

buddy，cudd は，同 DLL を JNI を用いたラッパーで 包んで使えるようにしているようです． 標準では，Windows 版と Linux 版のバイナリが提供されています． FreeBSD 上では DLL ロード時のシンボル名の解決とかに失敗してエラーとなるので， そのままのバイナリを持ってきても動きません．

私の手元の Windows 上では，buddy を指定しても動きませんでした． 色々(jeddを手元でbuild試みたりとか)してみましたが，結局放り出しました．

Linux 版は，buddy を使っての object-sensitive analysis が動きました （テスト動作は VMWare 上の Vine Linux でやりました）． 逆に，この環境では，javabdd 版のほうがメモリ不足で動かず， javabdd vs. buddy でのパフォーマンス比較はできていません．

object-sensitive analysis は，context-insensitive analysis に比べて，かなり時間がかかります． Pentium 4 3.0GHz + DDR 2GB の PC 上で， 解析対象を10ファイル841行の Java プログラムにしたとき， paddle nightly build / bdd 使用せずでの object-insensitive analysis （context:insens,bdd:false）が２分20秒程度で完了したのに対して， JavaBDD を使っての object-sensitive analysis （context:objsens,bdd:true,backend:javabdd）は実行に約90分かかりました．

文献[1]では， object-sensitive analysis や 1H-object-sensitive anlaysis の 結果が優れているという言及がありますが， 1H のほうは，context-heap:trueというオプションをさらに 追加したもののようです（説明を読んだ限りでは）． ただ，私の手元の環境ではメモリの不足のためか，処理が完了しませんでしたので， 実行時間その他の評価も行えていません．

現段階での私の結論は，「context-insensitive なら BDD なし」 「object-sensitive なら Windows 上では javabdd を使う」というところに落ち着いています． 

[1] Ondrej Lhotak and Laurie Hendren: 
"Context-Sensitive Points-to Analysis: Is It Worth It?"
Proceedings of the 15th International Conference on Compiler Construction, 
pp.47-64, Vienna, Austria, March 2006.

Soot の細かい情報

ソースコードからの Jimple 生成

Soot は，Java ソースコードから Jimple 命令列を生成するためのコードを持っていますが， いくつかの Java のコードを食わせてもクラッシュしてしまったので， 筆者は使用をあきらめました．

ソースコード解析をやりたい人には， WALA のほうが有望かもしれません（試していませんが……）．

例外処理

Soot は，すべての例外を RuntimeException あるいは そのサブクラスとしてスローします． 例外に関するドキュメントはありません．

ログをフィルタする

jb パックのようにカスタマイズできないパックの処理がどこまで終わってるかを調べるには， Soot の "-v" オプションを使って， Applying phase フェイズ名 to クラス名:メソッド名.という形式の メッセージを出力させます． 

例：
Applying phase jb.a to <sun.nio.ch.NativeObject: void putInt(int,int)>.

このメッセージは G.v().out に設定されている PrintStream に出力されますが， 放っておくと大量に出てくるので， 次のようにして，ログメッセージをフィルタする作戦が選べます． 

// Soot.main の呼び出し前に，出力先ストリームを自作クラスに差し替える
G.v().out = new ProgressObserver();
Soot.main(args);

// 自作クラスでは，println の中で進行状況を獲得する
class ProgressObserver extends PrintStream {
  public ProgressObserver() {
    super(System.out); // 文字列は標準出力に出すことにする
  }
  public void println(String s) {
    if (s.startsWith("Applying phase ")) {
      // 処理中のクラス名，メソッド名を得て覚えておくとか
      // ここでフェイズ適用を認識
    }
    // データ自体を System.out へ素通しするなら，
    // 次の呼び出しを行う．この呼び出しをしなければ，
    // 出力がなかったことになる．
    super.println(s);
  }
}

Java バイトコードに関する情報源

Soot が使用する中間表現である Jimple などは， Java バイトコードの仕様に依存している部分があります． ある程度 Java バイトコードと仮想マシンの振る舞いについて 知らないと，どうにもならないことがありますので， いくつか，情報源を列挙しておきます．