先日、ある研究者のチームが、ファイル内の大きなn-gramを処理することによってマシンラーニングによるマルウェア検出を改善する、新たなアルゴリズムであるKiloGramの論文を発表した。新アルゴリズムは、従来のものよりも60倍高速で、n = 1024以上のn-gramを処理することができる。nの値が大きいことは、解釈可能なマルウェア分析や署名生成において、新たな適用対象を持つことになる。
KDD 2019 Workshop on Learning and Mining for Cybersecurityで発表された論文では、メリーランド大学とサイバーセキュリティ企業Endgameの研究者グループが、大規模なファイルのデータセット内で最も頻度の高いn-gramを検出するアルゴリズムについて説明している。従来の方法では、nのサイズを大きくするとメモリとランタイムに"指数的コスト"が発生するため、数十万を超えるファイルを含むデータセットを分析する場合には、nの値が8未満に制限されていた。対照的にKiloGramアルゴリズムでは、数百万ファイルからなる5GBのデータからn-gramを抽出することができる。この時のRAM使用量は9GBに過ぎず、"ランタイムはnによって増加しない"。これによって同アルゴリズムでは、nの大きな値に対するn-gramを抽出し、それらのn-gramがマシンラーニングアルゴリズムの精度を高めるかどうかをテストすることが可能になる。
n-gramとはn個のアイテムの一意のシーケンスである。この考え方は多くのマシンラーニングタスク、特に自然言語処理(NLP)において使用されている。マルウェア検出の場合のn-gramは、マルウェアまたは良性のいずれかに分類されるファイルのバイトシーケンスである。マルウェア検出の初期の研究において、n = 15あるいは20といった大きなn-gramが検出システムのトレーニングに理想的であることが示唆されていたが、近年のデータセットのサイズのため、nの値が6を超えるとコストがかかり過ぎていた。KiloGramアルゴリズムでは、これらの大きな値を処理可能であるため、研究チームは、ｎの値が大きいほど望ましい、という考えをテストすることができたのだ。
研究者チームは、実行可能ファイルとAdobe PDFドキュメントで構成されたいくつかのデータセットを使用して、Elastic-Net正規化ロジスティック回帰分類子をトレーニングし、マルウェアを検出した。回帰における入力フィーチャには、KiloGramアルゴリズムを使用したn-gram抽出を採用した。その結果、文献の示唆とは異なり、"予測精度はn = 8を超えても増加しない"ことが分かった。 n-gramを大きくすると、モデルの精度が低下するためだ。ただし、解釈可能性(interpretablity)の面ではメリットはある。すなわち、小さいn-gramが"ブラックボックス"モデルを生成するのに対して、より大きいn-gram機能セットには、コードのスニペットやテキスト文字列といった、アナリストにとって意味のあるバイトのシーケンスが含まれる可能性があるのだ。
研究者らによると、大きなn-gramを使用した回帰モデルはそれほど正確ではない。特定のマルウェア攻撃に固有なものになるため、実際には過剰適合(overfitting)を引き起こすからだ。その一方で、Yaraなどの署名モデルで使用した場合には、偽陽性率が低いというメリットがある。つまりYaraモデルでは、ファイルを誤って良性としてマークする可能性が高い一方で、マルウェアであるとマークした場合には、それが間違いであることがほとんどないのだ。このことからKiloGramアルゴリズムは、マシンラーニングモデルと署名ベースモデルを組み合わせた階層化システムの構築に有効であるといえる。
Hacker News上のディスカッションでは、主執筆者であるdward Raff氏が、アルゴリズムに関するいくつかの質問に答えている。現時点でソースが公開されていない点については、"政府がコードを所有しているため"だ、と氏は説明した。さらに氏は、KiloGramsが他の問題領域でも役立つかも知れない、とも述べている。
バイオインフォマティクスは、このアルゴリズムが役立つと思われるアプリケーション分野のひとつです。何人かと会話しましたが、この種のアプリケーションは、完全一致が必要なため、現時点では制限が多いようです。これは将来的に考えていることですが、有効かもしれない、とは思っています。NLPにも、このアルゴリズムが有用なアプリケーションがいくつかあるかも知れません。これまでスケールアップを阻んでいた、古いアルゴリズムをいくつかスピードアップする上で、KiloGramが役に立つのではないかと考えている教授と、話をしています。