ASTgrep — 手軽に使えるバグ発見器

プログラムに間違い(バグ)があると,場合によっては誤動作します.その結果,ソフトウェアの脆弱性になったり,経済的な損失につながったり,時として人命が奪われることもあります.バグの厄介なのは,「場合によっては」誤動作するところです.テストではうまく動作していたのに,本番で誤動作してしまったという経験はありませんか?通用は,想定されるあらゆる入力に対する動作をテストすることはできませんので,テストしていない入力で誤動作する可能性は残ります.

プログラムを実行して動作を確認するのではなく,ソースコードを解析してバグを探せば,テストをすり抜けてバグが残るということはありません.ソースコードを解析して,バグの疑いがある箇所を探すためのツールASTgrepを作っています.

プログラムの特定のパタンはバグであることが多いということがよく知られています.例えば,C言語のif文の条件部に代入があるプログラム「if(x=y)」は「if(x==y)」の誤りである場合がほとんどです.ASTgrepでは,このようなバグのパタンを探します.このようにバグのようなパタンを探すツールをlintツールと呼びます.

バグのパタンは無数にあります.新しい脆弱性が発見されると,その脆弱性の原因となるパタンが発見されることがあります.この場合,同じようなパタンを含むプログラムは一刻も早く修正する必要があり,そのために一刻も早く新しいバグのパタンに対応したlintツールが必要になります.新しいライブラリを作ると,そのライブラリを誤用をチェックするlintツールも必要になります.このように,lintツールは素早く進化する必要があります.

ASTgrepは,一般のプログラマが手軽にバグのパタンを作成し進化させることができるlintツールです.その秘密は,バグの例からバグを構成している部分を選択するだけでバグのパタンを作ることができるところです.ユーザはバグの例となる小さなソースコードを作り,構文木作成モードでASTgrepを実行します.出力される構文木からバグの構成要素を選択すると,それがバグのパタンになっています.こうして作ったバグのパタンを検査対象のソースコードに適用して,ソースコード中のバグを探すことができます.

ASTgrep-overview

この研究は京都大学の馬谷誠二先生と共同で研究しています.

発表

  • 中村 真也, 鵜川 始陽, 馬谷 誠二: 規則違反コードの構造を反映した木パタンを用いるコード検査器.情報処理学会論文誌 プログラミング, Vol.9, No.4, pp.1–15 (2016) Permalink: http://id.nii.ac.jp/1001/00174565/
  • Tomoharu Ugawa, Seiji Umatani, Shinya Nakamura: A Source Code Checker Using Declarative Patterns to Represent Rule Violations.FLOPS 2016 ポスターセッション, March 4-6, 2016. [ポスター]
  • 谷口 力斗, 馬谷 誠二, 鵜川 始陽: データフロー解析結果を付加した構文木に対するパターンマッチによるコード検査.情報処理学会プログラミング研究会, 東京都東京大学, 2017年3月3日〜4日
  • 粕谷 彪人, 松田 直諒, 鵜川 始陽: 意味的誤り検出ツールASTgrepのAST生成部の設計と実装, PPL 2017 ポスターセッション, 山梨県石和温泉, 2017年3月8日〜10日