技術書典7にて『RustではじめるOpenGL』を頒布します

来る2019年9月22日、サンシャインシティ 文化会館ビル 展示ホールで開催される技術同人誌イベント「技術書典7」にて、書籍『RustではじめるOpenGL』を頒布いたします。

f:id:toyamaguchi:20190907231432p:plain:w300
『RustではじめるOpenGL』表紙
f:id:toyamaguchi:20190907231520p:plain:w300
『RustではじめるOpenGL』裏表紙

書籍の情報

  • 書籍名: RustではじめるOpenGL
  • サイズ: B5版
  • ページ数: 92ページ
  • 価格: 1000円
  • サークル名: Team Jackalope (リンク)
  • 販売ブース: 「こ32D」(池袋サンシャインシティ 文化会館ビル 展示ホール 2F ホールD) (マップ)

書籍執筆に寄せて

本書は、プログラミング言語のRustでOpenGLを扱うための入門書です。

私はこれまで、OpenGLを使ってネットワーク上のデータの流れを3Dで可視化させるソフトウェアを作成してきました。 まったくOpenGLを知らないところからスタートして、様々なところにつまづきながら、4年間で多くのことを学ぶことができました。 本書はその集大成として、入門者向けの内容をまとめたものです。

Rustを使うメリット

本を執筆していることを周りの人に伝えると、よく「なぜRustからOpenGLを使うのですか?」という質問を受けることがありました。 本書では、RustからOpenGLを使ったときの3つのメリットを挙げています。

  1. 処理速度が速い
    • C/C++にも負けない処理速度を出せるRustならば、多少の処理でも60 FPSを維持することができるはず。
  2. ガベージコレクションがないので、画面がカクつかない
  3. モダンなプログラミング言語が持つ、便利な特徴・環境を使用できる
    • 様々なプラットフォームでの動くバイナリファイルが簡単に作成できたり、新しいライブラリの導入が楽だったりするのは、モダンなプログラミング言語ならではです。

これらのメリットもあって、RustからOpenGLを使う方法を執筆しようと思いました。

GUIからパラメータを操作できるサンプルコード付き

また、本書の特徴的なところとして、OpenGLに簡単にGUIを追加できるライブラリ「Dear ImGui 」(通称、ImGui)を導入しているところが挙げられます。 もともと、OpenGLチェックボックスやスライダーなどのウィジェットを追加するのは、とてつもなく面倒です。初心者には無理です。 しかし、このライブラリを導入することで、OpenGL特有のパラメータをON・OFFできるGUIを簡単に追加することができます。

例えば、照明の位置や強さを変えたり、カメラの視点を変えたり、ワイヤーフレームに切り替えたりするような作業をGUIから操作することで、より直感的にその効果を把握できるようになります。

次のスクリーンショットは、書籍のサンプルコードを実装すると動作するサンプルアプリです。

f:id:toyamaguchi:20190908095847p:plain
3Dオブジェクトを制御するGUI

LinuxでもWindowsでも動作可能な独自OpenGLコンソールが作れる

本書のプログラムが採用しているフレームワークとして、SDLというものがあります。 これは多くのゲームにも採用されている、クロスプラットフォームなマルチメディアフレームワークです。 また、OpenGLも多くの環境で動作する3DプログラミングのためのAPI規格です。 そして、さらに、それらを呼び出すRust自体も、様々な環境で動作できるプログラムをコンパイルできます。

これらをすべて合わせると、自分だけのクロスプラットフォームOpenGL製コンソールが作成できるのです。(バイナリファイルは各プラットフォームごとに必要です。)

例えば、データベースから得た情報を元にグラフをぐいぐい動かしたり、映画『アイアンマン』に出てくるカッコいいビジュアルのコンソールを作り出せます。

f:id:toyamaguchi:20190908105031p:plain
Dear ImGuiのサンプル画像

どうです。ワクワクしませんか!

私はカッコいいGUIを作りたくてしょうがないです!

そんな情熱から本書を執筆いたしました。

紙版・電子版

紙版は技術書典7で150部頒布し、残った場合はBOOTHに委託しようと考えています。

また、電子書籍版もこちらに公開します。電子書籍版は部数に制限はないです。

toyamaguchi.booth.pm

現在は、準備中ですが上記のリンクの場所に公開する予定です。

書籍の表紙について

先日、書籍の表紙の完成をTwitterでつぶやいたところ、多くの人から「いいね」をいただけましたので、この表紙について少し解説いたします。

タイトルデザインの方針

f:id:toyamaguchi:20190908084446p:plain:w300
表紙のロゴ

私は大学時代の美術サークルに入っていたこともあり、このようなデザインの作成はすごく好きです。 せっかく自分の書籍を作るのだから、表紙を凝らないでどうする、という気持ちから、いろいろ悩みました。

OpenGLがテーマでしたので、よく見るポリゴンスタイルの背景壁紙のような案や、立方体や正八面体をモチーフにした案なども考えていました。 いろいろ考えていた中で、OpenGLのシェーダの中でも、わざと画面にノイズを加えた表現方法である「グリッチ」のアイデアが浮かびました。 しかし、グリッチの度合いを強くし過ぎると視認性が悪くなるので、グリッチ効果をより抽象的にして、グリッチの度合いを弱めた表現に変更しました。

フォント

また、画像の中で使用させていただいたフォントは、「851ゴチカクット」です。 昔の松下電器の「ナショナル」の文字にインスパイアしてできたフォントで、このカクカクしたところが近未来的でポップな印象を与えてくれます。 素晴らしいです。ありがとうございます。作者に感謝します。

f:id:toyamaguchi:20190908102114p:plain
851ゴチカクット

フォントが与える印象は大きいです。 最近のコミックやライトノベルの表紙に使われているロゴを見てもわかりますが、コミカルでポップなストーリーと、世界観が確立されたシリアスなストーリーとでは、使っているフォントの傾向が違います。 自分の書籍の印象をどういう雰囲気にするのかを考慮して、フォントをしっかり決めましょう。

私のやり方としてはそれほど難しくなく、「日本語 フリーフォント」などで検索して、良さそうなフォントの画像をダウンロードします。 その中から、最も表紙に似合うフォントを選んでいます。

ただ、すでにお気に入りのフォントというのもあって、今回はチームロゴと裏表紙の英語ロゴで使用しました。

ちなみに、チームロゴで使っているフォントは、丸い文字がかわいい「Comfortaa」です。

f:id:toyamaguchi:20190908091744p:plain:w200
チームロゴ

裏表紙の英語ロゴは、サイバーな雰囲気を与えてくれる「Orbitron」です。

f:id:toyamaguchi:20190908092821p:plain:w400
裏表紙のロゴ

目次

本書の内容を箇条書きでここに記しますので、参考にしていただけたらと思います。

  • ギャラリー
  • はじめに
    • 想定読者
    • 使用するライブラリとプラットフォーム
    • ソースコードのダウンロード
    • 免責事項
  • 第1章 開発環境の準備
  • 第2章 SDL
    • 2.1 準備
      • 2.1.1 Cargo.tomlの編集
      • 2.1.2 Linuxの場合
      • 2.1.3 Windowsの場合
    • 2.2 プログラムの作成
      • 2.2.1 ソースコードの全体
      • 2.2.2 初期化
      • 2.2.3 ウィンドウ
      • 2.2.4 キャンバス
      • 2.2.5 イベントループ
    • 2.3 プログラムの完成
  • 第3章 OpenGL
    • 3.1 準備
    • 3.2 プログラムの作成
      • 3.2.1 ソースコードの全体
      • 3.2.2 初期化
      • コラム : OpenGL 3.1
      • 3.2.3 OpenGLによる描画の仕組み
      • 3.2.4 シェーダ
      • 3.2.5 Vertex Array ObjectとVertex Buffer Object
      • コラム : ソースコードの整形を回避する
      • 3.2.6 三角形の描画
  • 第4章 Dear ImGui
    • 4.1 準備
    • 4.2 プログラムの作成
      • 4.2.1 初期化
      • 4.2.2 イベント処理
      • 4.2.3 ウィンドウの作成
      • 4.2.4 ウィジェットの生成
    • 4.3 プログラムの完成
    • 4.4 効果的な使い方
    • コラム : 自分専用プログラムの楽しみ
  • 第5章 3Dオブジェクト
  • 第6章 テクスチャ
    • 6.1 準備
    • 6.2 プログラムの作成
      • 6.2.1 ソースコードの全体
      • 6.2.2 テクスチャの準備
      • 6.2.3 頂点座標、法線ベクトル、テクスチャ座標
      • 6.2.4 テクスチャと照明を追加したシェーダ
      • 6.2.5 ユニフォーム変数
      • 6.2.6 テクスチャの描画
    • 6.3 プログラムの完成
    • 6.4 光の効果
  • おわりに
  • 著者紹介

最後に

技術書典7は9/22 (火)にて、サンシャインシティ 文化会館ビル 展示ホールで開催されます。

他にも面白い書籍がたくさんありますので、サークルリストで確認してから足を運ぶと良いと思います。

techbookfest.org

また、私のサークルはこちらになります。

techbookfest.org

RustのCrate調査 (better-panic)

Rust製の実行ファイルが異常終了した際に出力されるスタックトレースを、見た目の良いものに置き換えてくれるcrateを発見し、さっそく使ってみました。

crateの名前は「better-panic」です。 作者はPythonのflaskで有名な「mitsuhiko」ことArmin Ronacher氏。

github.com

コンパイラのバージョンは「rustc 1.35.0」、「better-panic = "0.1.1"」で試してみたいと思います。

better-panic適用前

例えば、次のようなソースコードを用意して、実行したら必ずpanicになるようにします。

fn main() {
    println!("Hello, world!");
    panic!("Encounter Panic!");
}

通常ですと、次のようなエラーメッセージが表示され、環境変数としてRUST_BACKTRACE=1をセットしないといけないな、となります。

Hello, world!
thread 'main' panicked at 'Encounter Panic!', src/main.rs:3:5
note: Run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

環境変数をセットしてから再び実行した結果が、次の内容です。

Hello, world!
thread 'main' panicked at 'Encounter Panic!', src/main.rs:3:5
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:39
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:59
             at src/libstd/panicking.rs:197
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:211
   4: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:474
   5: std::panicking::begin_panic
             at /rustc/3c235d5600393dfe6c36eeed34042efad8d4f26e/src/libstd/panicking.rs:408
   6: try_better_panic::main
             at src/main.rs:3
   7: std::rt::lang_start::{{closure}}
             at /rustc/3c235d5600393dfe6c36eeed34042efad8d4f26e/src/libstd/rt.rs:64
   8: std::panicking::try::do_call
             at src/libstd/rt.rs:49
             at src/libstd/panicking.rs:293
   9: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:87
  10: std::rt::lang_start_internal
             at src/libstd/panicking.rs:272
             at src/libstd/panic.rs:388
             at src/libstd/rt.rs:48
  11: std::rt::lang_start
             at /rustc/3c235d5600393dfe6c36eeed34042efad8d4f26e/src/libstd/rt.rs:64
  12: main
  13: __libc_start_main
  14: _start

自分が作成したソースコード以外のスタックが、こんなにも積まれていたことに気づいた瞬間です。

全部出力されると、余計な部分も多く、自分のコードがどこなのかわからないですね。

better-panic適用後

プログラムの最初に、better_panic::install()を追加します。

fn main() {
    better_panic::install(); // add better-panic!
    println!("Hello, world!");
    panic!("Encounter Panic!");
}

これによって、置き換えられたスタックトレースがこちらになります。

f:id:toyamaguchi:20190621191837p:plain

カラフルになり、自分のソースコードの箇所だけスタックトレースが表示されるようになりました。

また、スレッド情報も書いてあるようなので、マルチスレッドのプログラムが異常終了した場合でも、どのスレッドで問題があったのかがわかるかもしれません。

実行した環境にソースファイルを見つけた場合、そのソーススニペットを表示してくれるそうです。

まとめ

今回はbetter-panicについて調査をしました。

GitHubにも書かれていますが、これはPythonのtracebackからインスパイアされて作ったそうです。

また、気になるcrateがあったら調査していこうと思います。

論文メモ: Visualizing Compiled Executables for Malware Analysis

はじめに

絵画や陶芸などは目で見ることで良し悪しがわかるものですが、ソフトウェアは良し悪しが目で見えづらいです。

目では見えないため、ソフトウェアにバグがあったり、さらにはアドウェアが入っていても気づきづらいです。

マルウェア解析の分野においては、悪意あるソフトウェアに難読化処理が施されていることも多いため、どのような処理が行われるのか推測が難しいです。

もしソフトウェアがもっと見えたなら、様々な問題が緩和されるのではないかでしょうか。

私は、日頃、3D CGによる可視化技術の調査や実装を行っているのですが、これをセキュリティの分野に適応できないかと模索しています。

既存研究を探してみたところ、今回取り上げる「Visualizing Compiled Executables for Malware Analysis」[Quist+09]という論文を発見しました。

ieeexplore.ieee.org

この論文では、ソフトウェアの挙動を3Dで可視化し、特にそれをマルウェア分析に役立てようという内容です。

2009年の「6th International Workshop on Visualization for Cyber Security」で発表された論文なので、かなり古い論文です。

古い論文なので、一般的なPC環境として「Windows XP」、仮想化システムとして「Xen」が登場してきて、時代を感じさせます。

それでも、ソフトウェアの挙動を可視化する手法について学べることもあるはずなので、ここにまとめていきます。

本論文の貢献

本論文では、リバースエンジニアリングの作業を助けるための、ソフトウェアの挙動を可視化するツールを提案しています。

仮想マシンにEtherというハイパーバイザーフレームワークを適用し、動的解析によってプログラム全体のフローを可視化します。

プログラムの挙動を可視化したサンプル画像をここに引用します。

f:id:toyamaguchi:20190601111930p:plain
[Quist+09] Figure 1

可視化することで、パックや圧縮処理が施されたプログラムの、本来のエントリーポイントを発見しやすくします。

また、プログラム全体の構成の理解を促すようにします。

こうして、リバースエンジニアリングにかかる時間を短縮できるようにします。

リバースエンジニアリングのワークフロー

まず、リバースエンジニアリングはとても難しいです。

あるときは様々なツールを使って、あるときはアセンブリ言語を読んで、プログラムの目的が何なのかを探ります。

様々なスキルをマスターするのにも時間がかかりますし、一回一回の解析にも忍耐が必要です。

一方で、マルウェア側も常に進化しており、デバッガーを検知したり、プログラムの圧縮や難読化を施したりして、解析を妨害してきます。

そんな困難なマルウェア解析ですが、この論文では最初に効率的な解析のワークフローを提案しています。

  1. 隔離環境を用意する。
  2. ターゲットのプログラムを起動し、そのプログラムが行う出力 (プログラムが与えた影響)を探す。ツールを使ってOSへの変更をモニターする。
  3. IDA Proのようなツールでプログラムをロードして、リバースエンジニアリング作業を始め、必要なら難読化解除を行う。
  4. 似たような処理を行う部分や、興味深い部分を特定し、分析する。

ここで著者は、特に隔離環境の重要性を説明していました。

VMWareVirtual PCのような仮想化システムは、システムの現在の状態のスクリーンショットを撮れます。

分析する前にスクリーンショットを取っておくことで、実行後のシステムの状態を比較できます。

また、実行プロセスの理解のために、感染前の状態に素早くリストアすることもできます。

マルウェアの感染被害を仮想化環境内に閉じ込めることで、安全に解析ができます。

提案ツールの構成

f:id:toyamaguchi:20190601134643p:plain
[Quist+09] Figure 2

Etherを使った仮想マシンでのモニタリング

Etherは、Xenの仮想化フレームワークに追加する一連のパッチと、アプリケーションで構成されています。

このパッチにより、Xenは実行中のプログラムにアタッチして、マルウェアに検出されることなく監視できるようになります。

(この論文は古いので、現在のマルウェアに効果があるかは定かではありません。)

ちなみに、このようなEtherによるプログラム実行のモニタリングは、[Dinaburg+08]にて発表されたものです。

このEtherによって、いくつかの利点が得られるそうです。

  1. マルウェアによる検証やデバッグ回避などを起動させず、正常動作をさせることができる。
  2. デバッガーやトレースシステムを破ることを目的とした難読化は、仮想化フレームワーク側からプロセスを監視してしまうEtherシステムには効果がない。
  3. 仮想化システムの全体の構造は安全に維持される。

さらに、プログラムの分析・視覚化のためにEther自体を拡張して、プログラム内での書き込み処理、読み込み処理、別プログラムの実行処理を記録できるようにしました。

これによって、プログラムのフローグラフを作成するために必要なデータが得られます。

さらに、追加された機能によって、プログラム内のパッカーや難読化を回避するために、実行中のプログラムの現在の状態をダンプする適切な時期が決定されます。

DLLの分析をするための新しいインポートツールも実装されました。

最終的に、Etherからすべてのステートメント実行、メモリの読み書き、実行された命令の逆アセンブリを含むトレースファイルが出力されます。

VERAによる可視化

基本ブロックと実行遷移

Etherはトレースファイルを生成し、それをVERAに渡します。

処理の流れを制御文(ジャンプ命令など)で区切ると、処理のまとまりがいくつもできあがりますが、この処理のまとまりのことを「基本ブロック」と呼びます。

VERAは、トレースファイルを元にして、一連の処理を基本ブロックに分け、基本ブロック間の遷移関係を調べます。

これらの結果をもとに可視化が行われ、基本ブロックがグラフ中のノードに、基本ブロック間の遷移がグラフ中のエッジになります。

実行回数の多いエッジは、より太く描かれます。

Open Graph Drawing Framework (OGDF)

ノードとエッジのデータが揃ったら、Open Graph Drawing Framework (OGDF)を使用してグラフのレイアウトを決定します。

他のライブラリではうまくできなかったことも、このライブラリを使用したことで、大きなグラフを素早く効率的にレンダリングすることができたそうです。

ここでweighted symmetric layoutのオプションを選択しました。

circular layoutなどの他のグラフ作成方法では、適切な情報が効果的に伝達されないことがわかりました。

レイアウトが解決すると、そのデータは再びVERA側に渡されます。

グラフの色

  • 黄色: ディスク上のプログラムとメモリ内のプログラムの両方に存在するコードの実行
    • 2つの領域のコードが同じであることを示している。
  • 赤色: エントロピーの高いセクション
    • ほとんどのパッカーと難読化ツールは、プログラムを圧縮して、データが均等に分散されるようにする。
  • 緑色: 存在しないコードセクションへの実行
    • 実行された命令がディスク上のプログラムに存在しない場合、これはコードが動的に生成せれたか、自己修正型であることを示す。
  • 薄紫: セクションがディスク上に存在するが、ランタイム実行ファイルには存在しない場合の実行
    • データがPEセクションヘッダに割り当てられているが、実行時までしようされていない場合に最もよく見られる。
  • ネオングリーン: メモリ内およびディスク上のプログラムとは異なる命令
    • 自己改変型コードの実行を示す。

プログラムの機能の特定

この可視化ツールを使うことで、プログラムの処理段階を特定できるようになります。

特に、アンパックコードの特定、初期化部分の特定、メインループの特定は、マルウェア解析でよく確認されます。

アンパックコードの特定

アンパックコードを特定することは、比較的簡単です。

プログラムのエントリーポイントの直後にある、いくつかのループが結合された部分です。

Figure 3では、MEWパッカーのアンパックループが示されています。 (Figure 1の右側部分を拡大したものが、Figure 3です。)

f:id:toyamaguchi:20190601192735p:plain
[Quist+09] Figure 3

この図から、もとのプログラムの難読化解除には複数のループが関係していることがわかります。

アンパックコードの終わりは、ループが終わり、直線的に薄紫のノードが伸びているところを探すことでわかります。 (Figure 1の中央部分あたり。)

この領域の最初の基本ブロックは、プログラムのオリジナルのエントリーポイントである可能性が高いです。

初期化部分の特定

初期化コードは、入口と実行が1つしかない基本ブロックの長い連鎖として見ることができます。

Figure 1では、これは元の入り口点から始まり、3つの分岐が発生する左側で終わる中央部分です。

プログラムの初期化では、メモリの割当、使用するファイルとリソースのオープン、およびネットワークリソースへのアクセスを処理します。

ただし、初期化はこの領域だけに限定されるものではないので、注意が必要です。

初期化処理を特定することで、この後に使われるリソースを特定し、プログラムの意図を絞りこめるため、大きなステップとなります。

メインループの特定

Figure 1で、メインループは左半分のうちの、中央に位置しています。

頻繁に実行されるループは、より太いエッジで描かれます。

この部分を特に分析することで、このシステムで利用されるバックドアを見つけることができたりします。

Figure 1の場合、自分自身をアクティブにしてから、最初のコールバックを実行し、着信接続を待ちます。

Applicatoin of Analysis: Mebroot

実際のデータセットでVERAを使用することで実用性を示します。

トロイの木馬であるMebroot (MD5:1f7fed180237ed352d274c69012a4717)の初期ロードポイントを分析するために、VERAを使用しました。

Mebrootは、マスターブートレコードに感染し、(当時の)最新のOS上で実行されます。

その主な目的は、被害者からクレジットカード番号やその他の財務情報を盗むことです。

感染したマシン上で、他の悪質なコードを起動するためのダウンロードエージェントとしても使用されます。

悪意のある機能のほとんどはカーネルモードで実装されています。

ユーザーモードのロード機能を分析するためにVERAを使用します。

最初の実行分析

Mebrootを約5分間実行して実行しました。

結果はFigure 5に示されており、挙動は非常に限定されたものでした。

f:id:toyamaguchi:20190601192938p:plain
[Quist+09] Figure 5

表示される情報は非常に少ないため、プログラムのこの部分は、迅速な分析を妨げるためのビジーなループである可能性が高いです。多くの場合、アナリストを誤った道へと導きます。

分析を12時間継続

実行を12時間継続することで、トロイの木馬の実行について、より広い視野を得ることができました。

f:id:toyamaguchi:20190601193000p:plain
[Quist+09] Figure 6

Figure 5は、このFigure 6の左上の部分になります。

Mebrootの困難な分析

Mebrootは最初に約45分間のビジーループに入ることによって、自分自身が分析されるのを防ぎます。

この間、興味のあることは何も起こりません。

このループが完了すると、Mebrootはホストのマスターブートレコードに感染します。

マスターブートレコードには、ブートプロセスが発生した後に実行中のWindowsカーネルに、後で挿入される初期化コードが含まれています。

また、Mebrootには、mid-instruction point jumpとして知られるテクニックが使われていました。

この難読化手法は、Intel命令セットのデータ密度に依存しています。

IDA Proなどの静的逆アセンブラがコードを分析するとき、命令は実行されるものと同じではありません。

Nick Harbourはこの問題を[Harbour08]で論じており、これがまさにMebrootの内部に存在しているのです。

Mebrootに関するこの事実を知ることで、IDAに逆アセンブルされたコードの見方を修正させることができます。

Mebrootの残りの部分は権限を与えられたカーネル空間の内部で実行され、今回の分析では明らかにすることはできません。

このトロイの木馬は、ネットワークログと、Mebrootの感染を識別するIDSシグネチャーに基づいて、正常に実行されたことがわかりました。

ユーザー調査

このツールとアプローチがプログラムの分析にどれほど効果的かを評価するために、予備的なユーザー調査を行いました。

ユーザーは、前の週に行われたリバースエンジニアリングレーニングコースに参加しました。

リバースエンジニアリングのワークフローについて一通り学び、すべてのテストに合格しました。

ユーザーは今回のツールの使用方法をさらに学び、2つのマルウェアサンプルについて、VERAの可視化ツールの評価を実行するように求められました。

この2つのマルウェアサンプルは、UPXとMewの異なるパッカーで暗号化されています。

ここでユーザーはいくつかの質問を受けました。

  • 標準の評価プロセスの各ステップで、彼らの使っていたツールのどのような側面が役立つのか
  • プロセスの各段階で、ユーザーは各ステップの主なタスクをどのように達成したか、また、そのステップで何が発見されたのか
  • 分析段階の終わりに、ユーザーはVERAを使用することの利点と欠点、VERAを使用することで分析のスピードが上がるかどうか、そして従来の手法では見当たらないと思ったことや、伝統的な技術を使っていたら見つけたであろう物事を見逃していたことについて
  • 最後に、VERAを再び使用する可能性があるかどうか、および同僚にVERAを推奨するかどうか

コードの特定のセクションを見つけたユーザーの成功をFigure 7に示します。 (全員で6人)

f:id:toyamaguchi:20190601213530p:plain
[Quist+09] Figure 7

特定のセクションというのは、具体的にはオリジナルのエントリポイント (OEP: Original Entry Point)を見つけたユーザーの数、初期化コード、およびメインループのことです。

さらに、図に示されているように、すべてのユーザーは再びVERAを使う可能性があり、それを推奨するだろうと述べていました。

まとめと将来の研究

VERAフレームワークは、リバースエンジニアリングをスピードアップするためのツールです。

このツールによって、作業の合計時間を短縮することができました。

今後検討されている機能については、次のようなものが挙げられています。

  • プログラム内のループの強調表示
  • カーネルベースのプログラム分析方法
  • 3D可視化環境の強化

雑感

論文の内容に関する雑感。

  • 仮想化環境にのみ存在するライブラリを探索して、それが存在したら仮想化環境上で実行している、と判定するマルウェアもいます。そのため、この古い論文に紹介されているEtherも、マルウェアに検知されてしまうかもしれないです。
  • マルウェアに検知されない状態で動的解析をしないと、マルウェアが本来の処理をしてくれないため、良い可視化ができません。そのため、検知されずに動的解析する方法は、常に最新の手法に置き換える必要がありそうです。
  • 可視化したグラフの赤色の部分は、パッカーや難読化ツールなどによってプログラムを圧縮されているため、データが均等に分散されるようになります。圧縮されているか、否かを判断する材料として、エントロピーが役に立つらしいです。興味深いです。
  • Mebrootの解析のように、12時間プログラムを監視し続けなくても良い手法が欲しいですね。
  • 説明を読む限り、mid-instruction point jumpは静的解析ツールを誤らせるテクニックに読めるため、あとで調査したいです。
  • 可視化技術は見た目の良し悪しを判断する必要もあるためか、ユーザー調査が行われていた点が興味深かったです。(ただ、ユーザーの皆さんがたくさん褒めてて、逆に疑ってしまいますが。)

参考文献

  • [Quist+09] D. A. Quist and L. M. Liebrock: Visualizing Compiled Executables for Malware Analysis, 2009 6th International Workshop on Visualization for Cyber Security, pp.27–32 (2009).
  • [Dinaburg+08] A. Dinaburg, P. Royal, M. Sharif, and W. Lee: Ether: Malware Analysis via Hardware Virtualization Extensions, Proceedings of the ACM Conference on Computer and Communications Security, pp.51-62 (2008).
  • [Harbour08] N. Harbour: Advanced Software Armoring and Polymorphic Kung-Fu. Defcon 16. (2008).

論文メモ: Bubble Treemaps for Uncertainty Visualization

はじめに

2018年の「IEEE Transactions on Visualization and Computer Graphics」の中に、「Bubble Treemaps」という面白いデザインのグラフを提案している論文を見つけました。

f:id:toyamaguchi:20190505153057p:plain
[Görtler+18] Figure 1

この「Bubble Treemaps」という手法は、木構造のデータを空間的に効率よく表現できるもので、関連性の高いノードはより近くに配置でき、同じ階層のノードは等高線を使ってグルーピングすることができます。

特徴

力学モデルのグラフ描画

ノード間に余計な空間が無く、ギュッとコンパクトに配置できるのは、力学モデルのグラフ描画を利用しているからです。

f:id:toyamaguchi:20190505160912p:plain
[Görtler+18] Figure 2

力学モデルによるグラフ描画は様々な手法で使われていますが、今回の「Bubble Treemaps」では、ノード間にバネの力が働き、お互いに近づこうとしたり、反発し合ったりして、位置関係が決定されます。

具体的には、それぞれノードがお互いに与える力を計算する処理、それを元にノードの位置を更新する処理を繰り返して、力が均衡したところで処理を終えます。

そのため、このような力学的なグラフ描画は、ノード数が多くなるほど計算量が大きくなってしまうのが欠点です。

この論文によると、「Bubble Treemaps」の計算量はO(n2)らしいです。

木構造データの階層を等高線でグルーピングしつつ、ノード間の距離を考慮して配置できるのは面白いですね。

「不確かさ」の可視化

この論文の著者によると、これまでの木構造のグラフでは、さらに追加で新しい要素を表現することは難しかったようです。

例えば、どのような要素かというと、この論文のタイトルにもある「不確かさ (Uncertainty)」です。

ノードや階層構造が持つ「不確かさ」のような追加要素を可視化するために、この「Bubble Treemaps」上では、ノードや等高線を波線・破線・点線などで表すようにしています。

f:id:toyamaguchi:20190505164759p:plain
[Görtler+18] Figure 6

この「不確かさ」のような新しい要素を使うシチュエーションがあまり浮かばなかったのですが、見つけたときには有効利用したいものです。

実装

力学モデルによるグラフ描画手法を自力で実装した場合には、定常状態の判定部分を工夫しないと、バネの振動が止まらなくなって苦労します。

しかし、GitHubにグラフ描画ライブラリとして有名な「D3.js」を用いたJavaScriptの実装が公開されていますので、これを使うことですぐに「Bubble Treemaps」を試すことができます。

github.com

また、この実装を使ったサンプルページも公開されているので、こちらのページにデータを入れて、素敵なグラフを取得しても良いかもしれません。

f:id:toyamaguchi:20190505174844p:plain
Bubble Treemaps Generator

適用例

論文内では、いくつかのデータセットを使って、「Bubble Treemaps」と従来のグラフ描画手法の比較をしていました。

下に表したのは、データの可視化ソフトである「Flare」のパッケージ情報に、「Bubble Treemaps」と従来の「Squarified Treemaps」を適用したグラフです。

f:id:toyamaguchi:20190505171320p:plain
[Görtler+18] Figure 8

2つの手法を比較しても、随分印象が違うことがわかります。

お互いに良い点はあると思いますが、「Squarified Treemaps」は整然と整理されて、与えられた面積を使い切ることができ、「Bubble Treemaps」のほうはグループ間の近さと階層構造を表現するのが上手いように思います。

まとめ

今回の論文メモは、斜め読みした内容でしたので、簡単なご紹介となりました。

もし実際に使ってみたい方は、論文の中にLimitationsなどの項目もありますので、用法・用量を守って、正しくお使いください。

また、このようなデータの可視化技術は、データマイニング技術と共に研究・利用されてきました。

このようなグラフを紹介しているページを覗くと、他にも面白いグラフを見つけることができるので、ぜひチラ見して行ってほしいです。

f:id:toyamaguchi:20190505183827p:plain
treevis.net

f:id:toyamaguchi:20190505183919p:plain
Xenographics

参考文献

今回紹介した論文

Bubble Treemapsの実装とサンプルページ

その他のグラフを紹介しているサイト

RustでMicrosoft製SMTソルバ「z3」を使う

「記号実行」で利用される「SMTソルバ」

私は興味のある分野がいろいろあるのですが、プログラムの解析技術もその中の一つです。

プログラム解析技術の中には、「記号実行 (シンボリック実行)」というものがあります。

これは、「どのような入力を与えられたとき、どの経路を実行するのか」を特定する技術です。

これを使うことで、プログラム上の多くの経路を通るような、高いテストカバレッジのテストケースを作成できるようになったりします。

一般的に、経路は条件分岐によって行き先が変わるので、分岐における条件式とそこに含まれる変数の関係を解き明かす必要があります。

そこで、登場するのが、「SMTソルバ」というプログラムです。

今回使う「z3」は、Microsoft Researchが開発しているSMTソルバです。

これを使えば、条件式がtrueになる可能性があるのかを特定したり、条件式がtrueになる変数の例を挙げることができます。

Rustのcrateの中にも、すでに「z3」を使うためのcrateがいくつか存在するようです。

今回は、その中でも最もメジャーそうなcrate「z3」(crateの名前もそのままでした)を使ってみます。

「z3」を使ったサンプルコード

私の実行環境はDebian Linux 9.8。

Rustのバージョンは、1.34.0 (91856ed52 2019-04-10)、crateの「z3」のバージョンは、0.3.2。

crateの「z3」を使うためには、Linux環境にz3の機能を持つlibz3が必要なので、apt-getなどで先にインストールしておく必要があります。

内部的にはこのライブラリを呼び出しているようです。

そして、サンプルコードはこちらになります。

use z3;

fn main() {
    let cfg = z3::Config::new();
    let ctx = z3::Context::new(&cfg);

    let x = ctx.named_int_const("x");
    let y = ctx.named_int_const("y");

    let zero = ctx.from_i64(0);
    let two = ctx.from_i64(2);
    let seven = ctx.from_i64(7);

    let solver = z3::Solver::new(&ctx);
    solver.assert(&x.gt(&y));
    solver.assert(&x.gt(&zero));
    solver.assert(&y.gt(&zero));
    solver.assert(&y.rem(&seven)._eq(&two));
    solver.assert(&x.add(&[&two]).gt(&seven));

    println!("solver: {}", solver);
    println!("check: {}", solver.check());

    let model = solver.get_model();
    let x_value = model.eval(&x).unwrap().as_i64().unwrap();
    let y_value = model.eval(&y).unwrap().as_i64().unwrap();

    println!("x: {}", x_value);
    println!("y: {}", y_value);
}

これを実行すると、次のように出力されました。

solver: (declare-fun y () Int)
(declare-fun x () Int)
(assert (> x y))
(assert (> x 0))
(assert (> y 0))
(assert (= (rem y 7) 2))
(assert (> (+ x 2) 7))

check: true
x: 6
y: 2

解説

少しずつ追って見ていきます。

    let cfg = z3::Config::new();
    let ctx = z3::Context::new(&cfg);

まず、ここでz3の環境を整えるため、ConfigとContextを新たに作ります。

ここにいろいろな変数、数値、条件式などが格納されていくようです。

    let x = ctx.named_int_const("x");
    let y = ctx.named_int_const("y");

    let zero = ctx.from_i64(0);
    let two = ctx.from_i64(2);
    let seven = ctx.from_i64(7);

変数xとyを定義し、他にも数値データである0、2、7についても定義します。

    let solver = z3::Solver::new(&ctx);
    solver.assert(&x.gt(&y));
    solver.assert(&x.gt(&zero));
    solver.assert(&y.gt(&zero));
    solver.assert(&y.rem(&seven)._eq(&two));
    solver.assert(&x.add(&[&two]).gt(&seven));

ここではSolverを新たに作成し、条件式を追加していきます。

ここで入力した条件式は、次のようになります。

  • x > y
  • x > 0
  • y > 0
  • y%7 == 2 (yを7で割った余りが2に等しい)
  • x + 2 > 7
    println!("solver: {}", solver);
    println!("check: {}", solver.check());

solver自体を出力すると、入力した条件式を見ることができます。

solver.check()をすることで、入力した条件式が成立する変数x、yが存在するかがわかります。

実際、trueが返されたので、この式が成立する値があるようです。

    let model = solver.get_model();
    let x_value = model.eval(&x).unwrap().as_i64().unwrap();
    let y_value = model.eval(&y).unwrap().as_i64().unwrap();

    println!("x: {}", x_value);
    println!("y: {}", y_value);

ここでは、このSolverからModelを取得し、さきほどの式が成立する、具体的なxとyを取得しています。

結果的に、x = 6、y = 2となり、確かに当たっているようですね。

今回は、適当なxとyを取得しましたが、線形計画問題のように「x + yが最大(または最小)になるような値」なども取得することができます。

まとめ

SMTソルバ「z3」を使うことで、プログラム中にある条件式がtrueになる条件を調べることができます。

これによって、「どのような入力を与えられたとき、どの経路を実行するのか」を特定することができるようになります。

実際、有名なCTFチームの一つである「Shellphish」が開発している「angr」という記号実行ツールでも、「z3」が使われています。

SMTソルバを使えば、パズルを解いたり、線形計画問題を解いたりすることもできるので、記号実行以外にも使える場面はいろいろありそうです。

論文メモ: Convolutional Networks on Graphs for Learning Molecular Fingerprints

情報処理学会 第81回全国大会に参加した際、熊谷将也さんの発表「疎構造学習およびグラフ畳み込みニューラルネットワークによる異常検知」のアイデアに影響を受け、論文「Convolutional Networks on Graphs for Learning Molecular Fingerprints」を読みました。

不慣れな化学系の内容も含まれているので、間違いや、読みの浅いところもあると思います。また、いくつか内容を端折ったり、論文の直訳っぽいところも見受けられると思いますが、ここに内容のメモを残します。

また、論文中で使われている参考文献の番号 ([4]とか[5]とか)はそのまま使っておりますので、気になる方はオリジナルの論文のほうをご覧ください。

arxiv.org

概要

この論文では、任意のサイズ・形をしたグラフを入力にすることができる、畳み込みニューラルネットワークを紹介しています。

この畳み込みニューラルネットワークは、circular fingerprintsをベースとした一般的な分子特性の抽出手法を一般化したものです。

グラフデータから得られたニューラルネットワークが出力する特徴量は、より解釈性が高く、より良い予測性能を持っています。

これによって、分子構造のグラフを畳み込みニューラルネットワークに入力し、その特徴ベクトルを得ることができるようになります。

既存技術とその問題

材料設計の分野では、分子の性質を予測するために、ニューラルネットワークを使って既知の分子データのサンプルを一般化し、新しい分子の性質を予測しているそうです。

この作業で問題となっていることは、判別器に入力する分子のサイズ・形にバリエーションがあることです。

現在の最新の技術では、既製品のfingerprintソフトウェアを使って、固定次元の特徴ベクトルを計算し、全結合のdeep neural networkか、他の機械学習手法へ入力します。 学習の間も、分子のfingerprintベクトルは固定値として扱われてます。

入力が固定長ですと、すべてのありうる部分構造をエンコードできるようにするために、fingerprintのサイズを極端に大きくしなくてはなりません。また、サイズが大きくなったせいで、その後の計算量も大きくなるでしょう。

この論文では、そのfingerprintソフトウェアの部分(分子からfingerprintベクトルの計算を行う部分)を、畳み込みニューラルネットワークに置き換えます。

提案手法の良い点

このneural fingerprintsは、固定のfingerprintsよりもいくつかの点でアドバンテージがあります。

予測性能

溶解度、薬の効能、有機薄膜太陽電池効率のそれぞれのデータセットにおいて、標準のfingerprintsの予測性能と同等かそれ以上の結果を示すことができました。

節約

既存のfingerprintソフトウェアは入力が固定長なので、様々な分子に対応するためには、fingerprints自体のサイズを極端に大きくなくてはいけませんでした。

しかし、提案手法は、関連性のある特徴のみをエンコードするように最適化でき、その後の計算などを軽減できます。

解釈性

標準のfingerprintsは、fragments (分子の特徴的な部分構造のこと)間の類似性という概念を持たず、それぞれのfragmentsを完全に分けてエンコードしていました。

一方で、neural graph fingerprintsのそれぞれの特徴は、類似しているが異なるmolecular fragmentsによってactivatedすることができ、特徴表現をより意味深いものにします。

(ちなみに、この後もactivatedという言葉がたくさん出てきます。特徴ベクトルはビットフラグのようになっており、ある特定の特徴が存在すれば、特定のビットフラグが立ちます。そのフラグが立ったことを、activatedと言っています。)

分子構造のグラフ

ここで入力として扱う分子構造のグラフは、頂点を原子、エッジを結合として表しています。

イメージがしやすいので、ここに論文のFigure 1の画像を引用します。

f:id:toyamaguchi:20190406150548p:plain
[Duvenaud15] Figure 1

既存技術であるcircular fingerprintsの手法も、提案手法であるneural graph fingerprintsの手法も、手法の流れを表す図は似ているようです。

ある原子は近傍と接続され影響を受け合い、その情報が上の層のレイヤーに流れ、それらのレイヤーが幾重にも積み重なっているという点で、両方共convolutionalな構造になっています。

そして、最終的にglobal pooling stepで、すべての原子からの特徴量が合わせられます。

現在の最新技術(既存技術)「Circular Fingerprints」

分子構造のfingerprintsの最新技術 (既存技術)は、extended-connectivity circular fingerprintsです。(ECFP) [21]

circular fingerprints [6]は、Morgan algorithm [17]の改良版で、atom-relabeling (原子の再ラベル付け)に対して不変の方法で、分子内にどの部分構造が存在するかをエンコードするように設計されています。

(直訳気味な説明でした。言い換えると、分子構造を入力した際に、グラフデータ内の原子の位置情報のようなものが少し変わっただけで、その部分構造の認識が変わってしまうようでは困ってしまいます。例え話ですが、90度回転したグラフ情報を入力しても同じ結果が得られる、という意味かと思われます。)

circular fingerprintsは、1つ前のレイヤーの近傍の連結された特徴に、固定長のハッシュ関数を適用することによって、それぞれのレイヤーの特徴を生成します。

これらのハッシュの結果は、先程触れた特徴ベクトル (ビットフラグの配列)のインデックスとして使われます。

このインデックスがactivatedな状態 (フラグが立ってる状態)は、分子内に特定の部分構造が存在していることを示しており、言い換えると、分子が特定の性質を持っていることを示唆しています。

インデックスによって表現された部分構造のサイズは、ネットワークの深さに依存しています。それゆえに、レイヤーの数は、fingerprintsの「半径」と呼ばれるそうです。

(「半径」と呼んでいるようですが、私はcircular fingerprintsの実物を見たことがないので、これが本当に円形 (circular)のようになっているのか知らないです。(笑))

新しいニューラルネットワークのFingerprintsを作る

circular fingerprintsのそれぞれ個別の操作を、differentiable analogに置き換えます。

(うまく訳せないですが、個別の操作を連続な数値と重み付けで処理を行うニューラルネットワーク構造に置き換える、という意味。)

Hashing

circular fingerprintsのそれぞれのレイヤーに適用されるハッシュ関数の目的は、それぞれの原子とその近傍の部分構造についての情報を組み合わせること。

これは、fragments上に微妙な変化があったときでも、きちんと異なる特徴量がactivatedになることを保証しています。

提案手法では、このハッシュ操作をシングルレイヤーのneural networkに交換します。

smooth functionというものを使うことで、分子構造の一部があまり重要でないような変化が起きたときに、activation (フラグビットの活性化)が似たようなものになることを可能にします。

Indexing

circular fingerprintsは、すべてのノードの特徴ベクトル (特徴ビットの集まり)を、最終的に分子全体の1つfingerprintへ組み合わせます。

提案手法では、このインデックス付けの作業をsoftmax operationを使用する。

これにより、それぞれの原子は一つのカテゴリーに属されるようになり、これらのすべてのラベルのベクトルを合わせたものが、最終的なfingerprintになります。

この操作は、標準的なconvolutional neural networkのpooling operationに似ています。

Canonicalization (正規化)

circular fingerprintsは、近傍における原子の順番によらず、同じものになります。

この不変性は、隣接原子の特徴と結合の特徴に従って、隣接原子を分類することで達成されています。

この正規化の代替手段は、summation (足し合わせ、総和)のような、permutation-invariant function (置換不変関数、順列を変えても不変な値を返す関数)を適用することです。

単純さと、スケーラビリティのために、提案手法ではsummationを選択しています。

置き換え作業を行う上でのcircular fingerprintsとneural graph fingerprintsの類似性

circular fingerprintsは、大きなランダムな重みを持ったneural graph fingerprintsの特別なケースだと解釈できるそうです。

これは、大きな入力の重みの限界において、tanh非線形性がステップ関数に近づくため、とのこと。

ステップ関数は連結されると単純なハッシュ関数を形成します。

また、大きな入力の重みの限界においては、softmax演算子は、one-hot-codedされたargmax演算子に近づき、これはインデックス付けの操作に似ているとのこと。

実験

大きなランダムな重みを持ったneural fingerprintsがcircular fingerprintsと同じように動作することを実証するために、2つの実験を行いました。

また、neural fingerprints単体を単体で見たとき、学習できた分子の特徴がどのようなものだったのか、予測性能はどうだったのかに触れていきます。

生成した特徴ベクトルの比較

最初に、circular fingerprintsで作った特徴ベクトル間の距離が、neural fingerprintで作った特徴ベクトル間の距離と似ているかどうかを調べました。

Figure 3 (左)は、circular vs. neural fingerprintsのscatterplot。

f:id:toyamaguchi:20190407110913p:plain
[Duvenaud15] Figure 3

fingerprintsの長さは2048で、solubility dataset (溶解度のデータセット) [4]から分子のペアを使って計算を行っています。

距離は、Tanimoto (a.k.a. Jaccard) similarityの指標の連続値の正規化手法を使って計測。

距離間には、r = 0.823の相関があったようです。

図の右側に点が並んでしまっているのは、binary ECFP fingerprintsが0になってしまったものがあったようです。 (この点においても、neural graph fingerprintsのほうはきちんと計算できている、というアドバンテージを主張できるかもしれません。)

予測性能の比較

2番目に、大きなランダムな重さを持つneural fingerprintsの予測性能 vs. circular fingerprintsの予測性能を調査しました。

先程のFigure 3 (右)に、solubility dataset上での平均予測性能を示しています。

これは、fingerprintsに線形回帰を使っています。

両方の手法の性能は似たようなカーブに従っています。

対照的に、小さいランダムな重みを持つneural fingerprintsの予測性能は、異なるカーブに沿っており、それは実質的に良い結果を示すものでした。

これは、ランダムな重みがあったとしても、neural fingerprintsのほうが比較的smooth activationが一般化性能を助けることを示唆しています。

Neural Graph Fingerprintsが学習できた特徴

Figure 4と5は、neural graph fingerprints単体で見たとき、最大限にactivateした最も予測性能の高い特徴のfragments (分子構造の特徴的な部分構造)を表しています。

Figure 4は、溶解度のデータセットを利用して得られたものです。

私は化学的な素養が無いのでピンときませんが(笑)、標準的な溶解度の指標となっている親水性R-OH基を含むfragmentsが最もactivateされたようです。

また、下段は、不溶性を強く示したものです。非極性復環構造というものがactivateされているそうです。

f:id:toyamaguchi:20190407113005p:plain
[Duvenaud15] Figure 4

Figure 5は、毒性のデータセットを利用して得られたものです。

f:id:toyamaguchi:20190407113024p:plain
[Duvenaud15] Figure 5

[27]は似たような可視化をしているようですが、半自動半マニュアルな方法だったようです。

毒性fragmentsによって発火するneuronを決定するために、彼らは毒性の部分構造を手作業でリスト上を調べ、最も関連しているものを1つ選択していたそうです。

対照的に、この論文では可視化も自動で生成したそうです。あらかじめ、検出しそうな毒性fragmentsをリストアップしておくようなこともしていないそうです。

予測性能

neural graph fingerprintsの予測性能と、標準設定をしたstate-of-the-artの予測性能を比較するために、いくつかの実験を行いました。

state-of-the-artは、circular fingerprintsを全結合neural networkに入力しました。

論文の中では、学習方法、neural networkの構造、ハイパーパラメータの最適化についても触れられていますが、少し端折ります。

データセット

予測性能比較のため、3種類のデータセットを用いたようです。

  • Solubility (溶解度)
    • [4]によって測定された、1144の分子の水溶解度。
  • Drag efficacy (薬の効能)
    • [5]によって測定された、マラリアを引き起こす寄生虫である熱帯マラリア原虫 (P. falciparum)の耐硫酸塩性株に対する、50%効果濃度に関するデータ。1000の分子。
  • Organic photovoltaic efficiency (有機薄膜太陽電池効率)
    • The Harvard Clean Energy Project [8]では有機化合物の太陽光発電効率の見積もりのために高価なDFT (Density Functional Theory: 分子動力学) simulationを使用している。このデータセットから20000の分子のサブセット。

予測精度

2つの条件下で、circular fingerprintsとneural graph fingerprintsのパフォーマンスの比較をしました。

最初の条件では、fingerprintsを入力として使うlinear layerによって予測をしました。

2つ目の条件では、fingerprintsを入力として使うone-hidden-layer neural networkによって予測をしました。

すべての実験において、neural graph fingerprintsは、circular fingerprintsの精度と同じか、それ以上でした。

fingerprintsを入力として使うneural networkは、linear layerを使ったときよりも精度が上がりました。

f:id:toyamaguchi:20190407115100p:plain
[Duvenaud15] Table 1

実装

Theanoのような自動微分のパッケージは、自動で勾配を提供することによって、著しく開発時間が向上しますが、制御構造やインデックス付けに制限がありました。

比較的複雑なコントロールフローや、アルゴリズムの改良版を実装するためにインデックス付けが必要だったため、よりフレキシブルなPythonの自動微分パッケージである「Autograd」を使いました。

このパッケージはNumpyのコードをハンドルし、while loop、branches、indexingを含んだコードを微分できるそうです。

neural fingerprintsを計算するコードや可視化するコードは、次の場所にあります。

github.com

制限事項

計算コスト

neural fingerprintsは原子数とネットワークの深さにおいて、circular fingerprintsと同じ漸近的複雑度を持っています。

しかし、各ステップにおける特徴ベクトルの変換をするのに必要な行列乗算があるため、追加の項を持っています。 (つまり、余計に計算する箇所がある、ということ。)

深さRのneural fingerprintで、各レイヤーで特徴数Fを持つ、molecular convolutional netを使って、N個の原子を持つ分子の長さLのfingerprintを計算するのに、O(RNFL + RNF2)のコストがかかります。

実際には、circular fingerprintsの上位にあるneural networksを学習するのに、普通数分かかる。fingerprint自体の学習と上位のneural networksを両方学習するのに、より大きなデータセットを使うと1時間程度かかります。

各レイヤーでの計算における制限

ネットワークのあるレイヤーから次へ進む関数をどれほど複雑にするべきか。この論文では、とても単純で実現可能性が高いneural networkのシングルレイヤーを選びました。

しかし、これを別なものに置き換えることで、情報のやりとりを効果的にでき有益だろう、と言っています。

グラフ全体への情報伝達における制限

この論文で開発したlocal message-passingアーキテクチャは、グラフのサイズを縮小することができます。

しかし、グラフ全体に情報を伝達する能力は、ネットワークの深さによって制限されます。 (原子とその近傍が影響を与えあって、徐々にレイヤーを上がって行くため、全体にその影響が渡るまでに数レイヤーかかります。)

この論文で使用した小さな有機分子を表すような小さなグラフにとっては問題ないですが、最悪の場合、サイズNのグラフを区別するために、深さN/2のネットワークが必要になります。

この問題を避けるために、[2]はグラフ部分構造の階層的クラスタリングを提案しています。木構造ネットワークでlog(N)レイヤーだけ使用して、グラフ全体の構造を調べることができます。

しかし、これは分子をパースするために学習が必要でした。

自然言語処理からの技術 [25]をこのドメインに適用することで、良い結果が期待できるかもしれません。

立体異性体を区別できない制限

エナンチオマー (鏡像異性体)(分子の鏡像)や、シス/トランス異性体 (二重結合周りの回転)を含む立体異性体を区別するために、特別な処理が必要となります。

たいていのcircular fingerprint実装は、これらの区別を行うオプションを持っています。

neural fingerprintsは立体異性体に対してsensitiveになるよう拡張できるが、これはfuture workとして引き続き取り組みます。

まとめ

このように、分子構造の特徴抽出の作業がニューラルネットワークによって置き換えることができました。

この新しいfingerprintsの性能や、解釈性の向上をデモンストレーションすることができました。

すでに、音声認識、画像認識、自然言語処理などの分野では、手作業で作られた特徴量からdata-drivenな特徴量に置き換わっております。

バーチャルスクリーニング (コンピュータを使った化学構造を評価する技術の一つ)、材料設計、薬の開発などに適用されていくことも、自然な流れなのでしょう。

雑感

論文の内容に関する雑感。

  • 分子構造・性質が似ている場合には同じ特徴フラグがactivateしてほしい。分子構造にあまり重要でない変化があった場合にも、同じような特徴フラグがactivateしてほしい。一方で立体異性体のような分子のそっくりさんを別物と判断することが、なかなか難しそう。
  • 「グラフ全体への情報伝達における制限」は、扱うグラフの大きさに依存してくるため、要注意。

論文メモを残すという作業に関する雑感。

  • ぼんやりわかったことを、きちんと説明するのが難しかったです。(笑)
  • 化学の知識はほぼ無いに等しいですが、取り急ぎ提案手法の貢献が理解できたので良し。
  • 「differentiable fingerprints」という言葉は、ニューラルネットワークを適用した、連続な数値と重み付けの足し合わせによって得られるfingerprintsなわけですが、「微分可能な」fingerprintsと訳すのは違う感じがして、良い日本語が思いつかない。もっと他の論文を読めば、何か答えが見つかるかも。

参考文献

  • 熊谷将也, 松本亮介, 侵入検知システムのためのグラフ構造に基づいた機械学習および可視化, 情報処理学会研究報告インターネットと運用技術(IOT), No.2019-IOT-44, Vol.52, pp.1-8, 2018年3月.
  • D. Duvenaud, D. Maclaurin, J. Aguilera-Iparraguirre, R. Gomez-Bombarelli, T. Hirzel, A. Aspuru-Guzik, R. P. Adams: Convolutional Networks on Graphs for Learning Molecular Fingerprints, NIPS'15 Proceedings of the 28th International Conference on Neural Information Processing Systems Vol. 2, pp.2224-2232 (2015).

RustのCrate調査 (version_check, ryu, unicode-width, fnv)

先日、Rust言語でよく使われているcrateをいくつか調べました。

toyamaguchi.hatenablog.com

今回は、version_check、ryu、unicode-width、fnvについて調査をしました。

コンパイラのバージョンは「rustc 1.33.0」です。

version_check : コンパイラのバージョンをチェック

version_checkは、現在の開発環境にあるコンパイラのバージョンチェックを行うcrateです。

注意しなくてはいけないことは、コンパイル時のコンパイラのバージョンではないところです。

このcrateの内部では、コマンドで「rustc --version」のプロセスを起動して、そこからバージョン情報を得ています。

Rustの開発ツールを作るときなど、コンパイラのバージョンに依存したコードを書くときに利用できますね。

サンプルコードは次のようになります。

crateのバージョンは、「version_check = "0.1.5"」です。

use version_check;

pub fn run() {
    println!("##### version_check #####");
    println!("{}", match version_check::is_nightly() { // nightly or not
        Some(true) => "running a nightly",
        Some(false) => "not nightly",
        None => "couldn't figure it out"
    });
    println!("{}", match version_check::is_min_version("1.13.0") { // compare by version
        Some((true, version)) => format!("Yes! It's: {}", version),
        Some((false, version)) => format!("No! {} is too old!", version),
        None => "couldn't figure it out".into()
    });
    println!("{}", match version_check::is_min_date("2016-12-18") { // compare by date
        Some((true, date)) => format!("Yes! It's: {}", date),
        Some((false, date)) => format!("No! {} is too long ago!", date),
        None => "couldn't figure it out".into()
    });
}

出力は次のようになります。

##### version_check #####
not nightly
Yes! It's: 1.33.0
Yes! It's: 2019-02-28

ryu : 浮動小数点数を高速に文字列に変換

ryuは、浮動小数点数を高速に文字列に変換するcrateとのことです。

そんなことにわざわざcrateが必要なのか、と思ってしまいますが、情報工学の素養がある方は、浮動小数点数の扱い方が少しやっかいなことをご存じの方も多いはずです。

どうもドキュメントによると、こちらの論文の技術を利用することで、高速に正確に浮動小数点数を文字列に直すことができるらしいのです。 (Google GermanyのUlf Adams氏の論文のようです。)

ryuの使い方は次のようになります。

use ryu;

pub fn run() {
    println!("##### ryu #####");
    let mut buffer = ryu::Buffer::new();
    println!("{}", buffer.format(1.234));
    println!("{}", buffer.format(0.000001));
    println!("{}", buffer.format(-0.000001));
    println!("{}", buffer.format(std::f32::INFINITY));
    println!("{}", buffer.format(std::f32::NAN));
}

出力は次のようになります。

##### ryu #####
1.234
1e-6
-1e-6
1.0737418e40
1.6106127e40

ドキュメントにも書いてありますが、無限 (std::f32::INFINITY)、NaN (std::f32::NAN)には対応していないので、気にする場合は直前にis_finite()やis_nan()で確認が必要です。

unicode-width : Unicode文字列の文字幅を計算

Unicode文字列の表示幅を計算してくれるcrateです。

Unicode文字列の場合、実際の表示幅とバイト数が異なるため、このようなcrateが必要になります。

サンプルコードは次のようになります。

UnicodeWidthStrはstrに対するのtraitになっています。

use unicode_width::UnicodeWidthStr;

pub fn run() {
    println!("##### unicode_width #####");
    let teststr = "ハローワールド";
    println!("{}", teststr);
    println!("The above string length is {}.", teststr.len());
    println!("The above string is {} columns wide.", teststr.width());
    println!("The above string is {} columns wide (CJK).", teststr.width_cjk());

    let teststr = "Hello, world!";
    println!("{}", teststr);
    println!("The above string length is {}.", teststr.len());
    println!("The above string is {} columns wide.", teststr.width());
    println!("The above string is {} columns wide (CJK).", teststr.width_cjk());
}

出力は次のようになります。

##### unicode_width #####                 
ハローワールド
The above string length is 21.
The above string is 14 columns wide.
The above string is 14 columns wide (CJK).
Hello, world!
The above string length is 33.
The above string is 23 columns wide.
The above string is 23 columns wide (CJK).

日本語を画面に表示するときの、レイアウトの調節に使えそうですね。

fnv : Fowler–Noll–Vo ハッシュ関数

このcrateは、Fowler–Noll–Vo ハッシュ関数の実装(HashMap、HashSet)が含まれているcrateです。

Fowler–Noll–Voというのは、このハッシュ関数を作った3人の名前 (Glenn Fowler、Landon Curt Noll、Kiem-Phong Vo)が由来だそうです。

どうもデフォルトのHashMapは、integer型のような小さいデータ型をキーとして使った場合、処理が遅いようです。

たいていの場合、キーはそれほど大きくないと思います。そのような場合には、このfnvを使ったほうが高速に処理ができるらしいです。

ただし、キーが大きい場合には、fnvはとても遅いらしいので、使い分けに注意して使いましょう。

crates.ioのfnvのページにリンクが貼ってあった、ハッシュ関数の比較ページの中にグラフが貼ってあったので、そちらを参考にしてください。

f:id:toyamaguchi:20190403133336p:plain
Comparison of Hash Function

サンプルコードはシンプルです。

use fnv::FnvHashMap;

pub fn run() {
    println!("##### fnv #####");
    let mut map = FnvHashMap::default();
    map.insert(1, "one");
    map.insert(2, "two");
    println!("{} {}", map.get(&1).unwrap(), map.get(&2).unwrap());
}

出力は次のようになります。

##### fnv #####
one two

使い方は普通のHashMapと変わりませんね。

まとめ

今回は、version_check、ryu、unicode-width、fnvについて調査を行いました。

また、気になるcrateがあったら調査していこうと思います。

参考文献