「Deductive System によるCプログラムのポインタ解析」 ［論文誌Vol.47, No.SIG2(PRO28), pp.1-17 (2006)］

［論文概要］
　ポインタ解析とはプログラム中のポインタの指示先を静的に求める解析である。解析結果はコンパイラの行う最適化や各種静的解析に広く利用されている。大規模な実プログラムに対してポインタ解析を行う場合、解析時間の爆発が問題になる。解析効率を高めるために様々な工夫が提案されているが、解析時間や精度、適用範囲、実装の容易性などの面で実用上十分とは言えなかった。本論文では、解の計算をdeductive systemを媒介として関係代数演算に帰着させることで、関係データベースの分野で確立された手法を適用し、これらの問題を統一的に解決する方法を示している。

［推薦理由］
　本論文は、Cプログラムに対するflow/context-insensitive、inclusion-based、field-sensitiveなポインタ解析の新しい定式化および実現方法を提案している。具体的にはポインタ解析を式の構造に基づきdeductive systemにより定式化することで、解析精度に加え、高い解析効率と実現の容易性を可能にしている。また、定式化された解析規則を関係代数演算として書き換えることで既知のRDBの最適化手法が利用できる。厄介でバグを生みやすいプログラム解析の問題を、シンプルな定式化に基づく分かりやすい表現で実現する本提案手法は、性能的な実用性も十分で、今後同様のプログラム解析を実装しようとするプログラマに大いに参考になる。また、同著者による既存の研究成果を組み合わせ、実際的なプログラムに対してもきちんとした解析が実現できている。以上の理由により、本論文を論文賞に推薦する。