Intel製の機械学習でプログラムの問題を検知するOSSをPHP対応した

ControlFlag

Twitterを見ていると面白そうなニュースが飛び込んできました。

機械学習でコードの問題を自動検出、オープンソース化されたインテルの「ControlFlag」 https://t.co/1Cwlhn0alP

— ZDNet Japan (@zdnet_japan) October 25, 2021

　ControlFlagは、機械学習を利用してソフトウェアやファームウェアのコードに存在するバグを自動的に検出するツールで、書いているプログラムのデバッグを開発者が手動で行うという、時間がかかる作業を軽減してくれる。

　2020年末に発表されたControlFlagは、これまでIntelの社内でだけ、自社のソフトウェア開発で異常を発見するために使われてきた。Intelは、このツールを社外の開発者に解放して、それを元に開発を行えるようにすることで、コーディングのプロセスを合理化するためにできることが広がるのを期待している。

というわけでIntelの社内で使われていたソフトがOSSとして公開されたらしいです。
では、実績としてはどうなんだ？と思われるかもしれませんが、curlのバグを見つけたそうです。

curlは古くからあるソフトですし、だいぶ枯れていても良いものですが、機械学習でバグが見つけられるものなんですね。そのような目覚ましい成果を上げている中で、日本では動かしている人がとても少ないようで、Qiitaにも1件ぐらいしか見つかりません。

そんななか、たまたま時間があったため使ってみました。

違和感

githubのリポジトリはこれです。
記事では書かれていませんが、対応してるのはC言語とVerilogのようです(なぜVerilog?)
リポジトリに書いてある手順通りにビルドします。

$ cd control-flag
$ cmake .
$ make -j
$ make test

あとは学習済みデータで解析をしてみる。という手順を行いました。
@ruiuさんのmoldというリンカを解析してみました。

結果を言いますと、あまりバグは検知されずthird-partyのtbbのライブラリ内でのバグが検知されたぐらいでした。

ログ出力結果

$ grep "Potential anomaly" -C 5 *
thread_0.log-Expression is Okay
thread_0.log-[TID=140016457996032] Scanning File: ../../mold/third-party/tbb/src/tbbmalloc/shared_utils.h
thread_0.log-Level:ONE Expression:(parenthesized_expression (binary_expression ("*") (identifier)(binary_expression ("=") (identifier)(call_expression (identifier)(argument_list (identifier)(string_literal)))))) not found in training dataset: Source file: ../../mold/third-party/tbb/src/tbbmalloc/shared_utils.h:112:7:(FILE *f = fopen(file, "r"))
thread_0.log-Expression is Okay
thread_0.log-Level:TWO Expression:(parenthesized_expression (binary_expression ("*") (identifier) (non_terminal_expression))) not found in training dataset: Source file: ../../mold/third-party/tbb/src/tbbmalloc/shared_utils.h:112:7:(FILE *f = fopen(file, "r"))
thread_0.log:Expression is Potential anomaly
thread_0.log-Did you mean:(parenthesized_expression (binary_expression ("*") (identifier) (non_terminal_expression))) with editing cost:0 and occurrences: 0
thread_0.log-Did you mean:(parenthesized_expression (binary_expression (">") (identifier) (non_terminal_expression))) with editing cost:1 and occurrences: 1504
thread_0.log-Did you mean:(parenthesized_expression (binary_expression ("<") (identifier) (non_terminal_expression))) with editing cost:1 and occurrences: 1445
thread_0.log-Did you mean:(parenthesized_expression (binary_expression ("&") (identifier) (non_terminal_expression))) with editing cost:1 and occurrences: 800
thread_0.log-Did you mean:(parenthesized_expression (binary_expression ("=") (identifier) (non_terminal_expression))) with editing cost:1 and occurrences: 76
--
thread_0.log-Level:TWO Expression:(parenthesized_expression (identifier)) found in training dataset: Source file: ../../mold/third-party/tbb/test/common/fp_control.h:51:7:(checkConsistency)
thread_0.log-Expression is Okay
thread_0.log-Level:ONE Expression:(parenthesized_expression (true)) found in training dataset: Source file: ../../mold/third-party/tbb/test/common/fp_control.h:65:7:(true)
thread_0.log-Expression is Okay
thread_0.log-Level:TWO Expression:(parenthesized_expression (true)) found in training dataset: Source file: ../../mold/third-party/tbb/test/common/fp_control.h:65:7:(true)
thread_0.log:Expression is Potential anomaly
thread_0.log-Did you mean:(parenthesized_expression (true)) with editing cost:0 and occurrences: 1
thread_0.log-Did you mean:(parenthesized_expression (identifier)) with editing cost:1 and occurrences: 34682
thread_0.log-Did you mean:(parenthesized_expression (call_expression)) with editing cost:2 and occurrences: 26023
thread_0.log-Did you mean:(parenthesized_expression (number_literal)) with editing cost:2 and occurrences: 126
thread_0.log-Did you mean:(parenthesized_expression (non_terminal_expression)) with editing cost:2 and occurrences: 109
--
thread_2.log-Level:TWO Expression:(parenthesized_expression (call_expression)) found in training dataset: Source file: ../../mold/third-party/tbb/include/oneapi/tbb/detail/_flow_graph_impl.h:464:7:(is_graph_active(g))
thread_2.log-Expression is Okay
thread_2.log-Level:ONE Expression:(parenthesized_expression (binary_expression ("*") (identifier)(binary_expression ("=") (identifier)(call_expression (identifier)(argument_list (identifier)(identifier)))))) not found in training dataset: Source file: ../../mold/third-party/tbb/include/oneapi/tbb/detail/_flow_graph_impl.h:468:10:( task* gt = prioritize_task(g, arena_task) )
thread_2.log-Expression is Okay
thread_2.log-Level:TWO Expression:(parenthesized_expression (binary_expression ("*") (identifier) (non_terminal_expression))) not found in training dataset: Source file: ../../mold/third-party/tbb/include/oneapi/tbb/detail/_flow_graph_impl.h:468:10:( task* gt = prioritize_task(g, arena_task) )
thread_2.log:Expression is Potential anomaly
thread_2.log-Did you mean:(parenthesized_expression (binary_expression ("*") (identifier) (non_terminal_expression))) with editing cost:0 and occurrences: 0
thread_2.log-Did you mean:(parenthesized_expression (binary_expression (">") (identifier) (non_terminal_expression))) with editing cost:1 and occurrences: 1504
thread_2.log-Did you mean:(parenthesized_expression (binary_expression ("<") (identifier) (non_terminal_expression))) with editing cost:1 and occurrences: 1445
thread_2.log-Did you mean:(parenthesized_expression (binary_expression ("&") (identifier) (non_terminal_expression))) with editing cost:1 and occurrences: 800
thread_2.log-Did you mean:(parenthesized_expression (binary_expression ("=") (identifier) (non_terminal_expression))) with editing cost:1 and occurrences: 76

この辺りでフーンと思っていましたが、解析をしているうちに少し変な感じがしました。

あまりにもビルドがうまくいきすぎている

機械学習を"たまに"しかやらない人は分かるかもしれませんが、ちょっと界隈から離れただけでライブラリのトレンドが変わっていたり新手法が発表されていたりします。そのため、環境構築が大変で、すぐに動かなくなったり、動かし続けるように開発環境を保守し続けるのが難しい印象があります。
そんな中でControlFlagは一発でビルドが通りましたし、ビルド自体も10分もかからない短時間で終わりました。これは、なんかおかしいな。 と思い始めました。

ControlFlagの内部実装を調べる

違和感を調べるために、単純にソースコードの量を調べてみました。

$ find src/ -type f | grep -v src/tree-sitter | xargs cat | wc -l
2747

めっちゃ短いですね。なんでこんな短いコードで、出来たのでしょう？
上で話した通り、C言語やVerilogのコードが解析できます。そのためには、C言語やVerilogのパースが必要になるはずです。パースはどうしているのでしょうか？

それが、上のコマンドにもあるtree-sitterです。

Tree-sitterはパーサ生成ツールであり、インクリメンタルなパーシングライブラリである。ソースファイルに対して具体的な構文木を構築し、ソースファイルの編集に伴って構文木を効率的に更新することができる。Tree-sitterは次のようなことを目指しています。

あらゆるプログラミング言語を解析するのに十分な汎用性
テキストエディタのキーストロークごとに解析できるほどの高速性
構文エラーがあっても有用な結果を提供できる堅牢性
ランタイムライブラリ（純粋なC言語で書かれている）をあらゆるアプリケーションに埋め込むことができるよう に、依存関係がない。

このtree-sitterが良く出来ているようで、40種類程度のプログラミング言語をパース出来るそうです。スゴイ。
ここで実装を省力化出来ているようです。
しかし、それにしても短すぎるな。と思い始めた私はコードを読んでいました。
そうするとCollectCodeBlocksOfInterestといういかにもそれっぽい関数を見つけました。

// For C and PHP language,
// we are looking for control structures such as if statements.
template <Language L>
void CollectCodeBlocksOfInterest(const TSNode& node,
    code_blocks_t& code_blocks) {
  if (ts_node_is_null(node)) { return; }

  uint32_t count = ts_node_child_count(node);
  for (uint32_t i = 0; i < count; i++) {
    auto child = ts_node_child(node, i);
    if (ts_node_is_null(child)) continue;
    if (IsIfStatement<L>(child)) {
      auto if_condition = GetIfConditionNode<L>(child);
      if (!ts_node_has_error(if_condition)) {
        code_blocks.push_back(if_condition);
      }
    }
    CollectCodeBlocksOfInterest<L>(child, code_blocks);
  }
}

これを見てあれっ？と思った方は正しいです。

Q. if文の条件式の中身しか解析してなくね？　
A. はい。そうです。

なので、

if(i % 3 == 0) {
  puts("Fizz");
}

というコードがあった場合、解析対象のコードはi%3==0の部分のみ。ということです。

PHP対応と考察

えぇ。。。と思いながらも、curlのバグを見つけられたんだし、しかもコードは短い。そして、コード見ても中身は簡単そう。だったら、PHP対応してみよう。と思って、対応したのが以下のPRでした。

土日にちょろっと触るぐらいで出来ました。それで、2/5にPR出して、忘れた頃にPRを見に行ったらレビューしていただいてマージとなりました。
業務ではPHPを書くことが多く、コードのクオリティにも気を付けているため、自動でバグを見つけてくれるならばうれしいことは無いです。では、その結果はどうだったか？というと、微妙です。

論文にこのようなコードがあります。

if (x = 7) y = x;

これはxが7と等しいとき、yにxを代入する。という意図があります。しかし、これは正しくなく、

if (x == 7) y = x;

と書くのが正解です。これはC言語特有のミスで、このようなバグがC言語だと作りこみやすい。という面があります。
ここでcurlのバグの件について論文で書かれている場所を見てみます。curlのバグ修正のPRは以下のURLです。

http_connect_stateという構造体にkeeponという値が定義されていました。

lib/urldata.h

struct http_connect_state {
  int keepon;
  ...

これはs->keepon = TRUEやs->keepon = FALSEのようにフラグのような振る舞いをしていました。
しかし、

lib/http_proxy.c

if(s->keepon > TRUE) {
  ...
}

という謎の表記があります。このif文をControlflagが検知したようです。これはコード内でs->keepon = 2という代入をしている部分があり、それを分岐するために作られたif文のようです。
このようにkeeponはTRUE/FALSEによるフラグ的な振る舞いをしているにも関わらず、s->keepon = 2という代入をしたり、s->keepon > TRUEを行っています。bool的な動きを求めてるように見えて、keeponへ数字を入れてみたり、不等号で比較してみたり、曖昧な記述をしています。それを直して、enumにした。というのが、このPRです。バグか？と言われたらちょっと違う気がします。どちらかというと臭いのするコード。という感じです。

その辺の流れを議論したのが以下のMLです。

https://curl.se/mail/lib-2020-11/0026.html
https://curl.se/mail/lib-2020-11/0028.html
https://curl.se/mail/lib-2020-11/0031.html

という形で、C言語のboolの実装や型に関する概念が曖昧であるために起こった内容です。
今回、例に挙げた2つの事例はどちらも"C言語特有"の内容で、"C言語自体の仕様の曖昧さや間違えやすさ"が原因の様に思います。では、似たようなことがPHPで起こるのか？ということです。
サンプルコードを書くと、

<?php

$a = 3;
if($a > false){
	var_dump("hoge");
}

は確かにValidなPHPとして動きはしますが、C言語ほど頻出はしないので、さすがにレビュー時に分かるんじゃないか・・・という気持ちはあります。一方で、型が厳密な言語であれば、ほぼこのようなバグは無いと思います。
で、実際にProductionで動いているPHPのコードも解析しましたが、指摘事項は的を外しており、偽陽性しかありませんでした。
ただ、PHPの検証に関しては、私が自前で用意した学習データで、2,000スター以上のGithubのリポジトリ、500件程度を学習データとしているので、学習が足りない面はあります。Controlflag公式は6,000リポジトリのデータを学習データとしており非常に膨大です。しかし、最大のモデルだと学習モデルの容量が9GB、推論に必要メモリが13GBとかなりヘビーなモデルになっているので、CI上で動かすのは無理そうです。

所感

• ControlFlagはif文の条件式しか判断しない
• 実用的にCIで動かすのは厳しそう
• curlのバグを見つけたとは言いにくい
• ControlFlagをPHP対応した
• 後発な言語(型制約の厳しい言語)はC言語ほど曖昧性が少ないので、言語的な仕様の問題で検知されなさそう

という感じでした。では、端的に「ControlFlagは役立たずなのか？」と言われると、色々考えた結果「Intelでは意味があるかも」という結論に行きつきました。Intelだとおそらくハードに組み込んだC言語もまだ現役なのではないか。と思います。そういう組み込み系の場合、プログラムにバグがあり、製品の回収やリコールなどが起こると甚大な損害を受けることがあります。そういうバグゼロを求められるような分野、バグがクリティカルに利益につながる分野では、高価なマシンで機械学習でバグを見つけるインセンティブがあるのではないか。とは思いました。だから初期で対応していたプログラミング言語が、組み込み寄りのC言語やVerilogだったのではないか。とは考えられます。
ControlFlagの良いポイントとしては、"ビルドが不要"な点があります。静的解析ツールによってはプログラムのビルドを要求されるものもあります。しかし、残念ながらCI上でビルドをするのが難しいプロダクトも多々あります。そういった中で、仕組み的にもプログラムのパースだけでビルド要らずで解析できるのは、導入のハードルが低く、ありがたいです。
方法を知ってしまえばどうというわけではないのですが、手法のアプローチとしては面白いなぁとは思いました。機械学習においては、基本的には教師データを必要とします。今回の"バグ"という概念を教師データとして集めるのは至難の業です。あまり詳しくは解説しませんが、Controlflagは異常検知的なアプローチをとっており、Githubのリポジトリをクロールし、その中から"頻出でない構造"≒バグとすることで検知する。というのはなかなか面白い手法だと思いました。そうすることで、教師データ(ラベル情報)が不要で、多数のリポジトリを学習するだけで済みます。
ただこの方法にも問題があって、これは局部的な構造しか見ていません。当たり前ですがプログラムと仕様がずれているバグには無力です。そして、ControlFlagは"書き方としてよくない"レベルのコードの匂い程度のものの検知にとどまりそうである。という予感がしています。ただこの後者においては結構いいな。と思う面もあって、今の静的コード解析はルールを人間が作っているので、そのようなルールを人手で作らず、コンピューターが勝手に学習して指摘してくれるのであれば、それは割と有用なのではないか。と思います。例えば、関数の引数は8つ以下に抑えなさい。というのは、リポジトリからの学習でなんとなく検知できるようになる予感がしています。
あとなんかメディアに踊らされたな・・・感は若干あります。プログラムの"問題"というタイトルのつけ方だったり、記事によってはcurlの"バグ"という言葉に踊らされてやってみましたが、バグじゃないじゃん・・・と。まぁこの辺は、よくある話ではあります。まぁ私もタイトルに"問題"って入れてるしな・・・
ControlFlagはまだ実用には厳しい印象がありますが、私としてはバグ検知というより、機械学習によるコードのベストプラクティスの抽出であったり、"コードの匂い"を検知できるようなソリューションだと面白いな。と思いました。