今更ながらセキュリティキャンプ 全国大会2017でやったことを書きます
1.introduction
よっちです！今日は今更ながらセキュリティキャンプ２０１7で何をやったかというのを書きます！
なぜ今更？wやおせーよ！と思う人も多いと思います！なぜか！それはただ単に、めんどくさくて更新しなかったのです笑 ではつらつらと書いてきたいと思います。
2.セキュリティキャンプとは？？
まずセキュリティキャンプ全国大会に関して知らない人も多いでしょう。説明するのが大変なので以下のURLを参照してください！
そこで私は集中Zというコースを選択しました。５日間同じものを作り続けるというコースです。ま集中Zは、Linuxのアンチウイルスソフトを作ろうというコースです。集中Zでも５つの分野に分かれていました。
・Z1: 高品質なELFマルウェアシグネチャ(yara)の作成
・ Z2: 高精度なELFマルウェア分類
・Z3: yaraシグネチャマッチングの高速化←
・ Z4: 圧倒的高速なIDS(パケットフィルタ)の作成
・Z5: 圧倒的高速なマルウェアスキャンクラウドストレー ジの作成
私はこのZ３のyaraシグネチャマッチングの高速化をやりました。
ちなみに受講生は私一人だったので、生徒一人に対し、講師一人というめっちゃ濃密でした笑
またこの講師の新屋さんという方がとてもすごい人でした＾＾；twitteと本は最後に貼っておきます！とにかく講師とのレベルの違いに驚きました。
３.yaraの高速化
で何をやったかというとyaraというマルウェア検知ツールの高速化を行いました！
具体的にyaraについて説明しますと。。。。
こんな感じです。
次にyaraルールについて説明します！
どのようなものかというと、上の文字列の$test1と$test2の取りかがマルウェアの中に入ってたらExampleRuleと表示されます。ようは自分で独自のルールを書き、マルウェアを検知できるというものです。
またパターンの記述には正規表現も書くことができます！Yara2.0からは自前の正規表現エンジンを搭載しています！
それで今回の高速化の対象はyara3.6.3です。
githubのURLを載せておきます！！！
yaraシグネチャの要は固定文字列探索にあります。現在yaraは文字列の探索に、固定文字列探索を採用しています。なので以下のようなデメリットメリットが挙げれます。
・正規表現探索は表現豊かだが遅い
・固定文字列探索は文字列だけなので速い
ここでmiraiのyararulesを見てみます
https://github.com/Yara-Rules/rules/blob/master/malware/MALW_Mirai.yar
上記のURLにマルウェアのルールがまとめてあります。
4.高速化の検討
セキュリティキャンプではこのyararulesの高速化をやったというのは先ほど話しました！ではどのように高速化したのかというのを説明してきます。高速化の方針としては
・YARAの固定文字列探索部分を高速化
⇨Quick Search と呼ばれるアルゴリズムを実装
ここで文字列探索についての説明をしておきます
単純な固定文字列探索
図 1.固定文字列探索例
あかさかさかすからさかすを探索する場合は、図１のような手順で１文字ずつずらして探索していくわけです。
次にQSアルゴリズムを見てみましょう！
図２.QSアルゴリズム探索
このアルゴリズムは図２を見てもらえばわかるように、キーワード末によって次にシフトする長さを決めています！
ちなみに計算量に関していかに示しておきます！！
検索対象の文字列の長さをn、キーワードの長さをsとする
- native な方法だと :最良O(n),最悪O(n*k)
- オートマトン: 最良 ・最悪O(n)
- Quick Search;最良O(n/k)最悪O(n*k)
5.結果
今回全国大会では、このyara内部のアルゴリズムを高速化することをしました。では肝心の結果を見てましょう。
今回の検索対象はwikipediaの全て文字データ(1GB近くあるtextデータ）の中から
abcdefghigklmnという固定文字列を検索しました。
wikipediaデータ
https://dumps.wikimedia.org/enwiki/20170601/
このように限定的なケース(固定文字列探索で済む場合)において4倍ほどの高速化に成功しました！！！！！
※実装が不完全なため、シグネチャが正規表現などを含む場合は正しく動かない。
コードに関してはgithubに公開します！！
ここも参考にしてみてください！
6.感想
・quick search アルゴリズムの理解
・膨大なソースコード読む
・書いたコードは六十行程度
・データ構造の理解
・高速化できたけどソースはまだ未完成(本家にマージできるレベルでは到底ない)
まずQSアルゴリズムが難しかったです！講師の新屋さんは、正規表現の研究者でもありとても計算量などに関して詳しく説明してくださいました！
二つ目に膨大なソースコードを読むのが初めてだったので、ここまで膨大５万行ほどのコードを読んだのは初めてだったので大変でした＾＾；またgdbというデバッカを使ってコードを読んだのですが、gdb使ったのもその時が初だったのでかなり覚えるのが大変でした。
ただそれ以上に得るものも多かったです！！このキャンプに参加して、自分もまだまだ修行が足りないので、もっともっと勉強しなくてはいけないと改めて感じることができました。またセキュリティ好きの同志もでき、今でも連絡を取り合ったりする人もいるので、とても良い機会だと思いました！！
悩んでいる人は是非とも参加するべきだと思います！！！！
7.最後に
セキュリティキャンプ２０１7で担当してくださった新屋さんはじめ、Zチームの講師のみなさん、その他講師のみなさんに深く感謝申し上げます。
参考文献
[1]新屋 良磨 ,鈴木 勇介,高田 謙 "正規表現技術入門 --最新エンジン実装と理論的背景",2015
新屋さん@sinya8282
様子
