Log of the Security

The main topic of this blog is computer science such as Security, Operating System, and Other

今更ながらセキュリティキャンプ 全国大会2017でやったことを書きます

f:id:yottiii:20180501195622p:plain

1.introduction

 よっちです!今日は今更ながらセキュリティキャンプ2017で何をやったかというのを書きます!

 なぜ今更?wやおせーよ!と思う人も多いと思います!なぜか!それはただ単に、めんどくさくて更新しなかったのです笑 ではつらつらと書いてきたいと思います。

 

2.セキュリティキャンプとは??

 まずセキュリティキャンプ全国大会に関して知らない人も多いでしょう。説明するのが大変なので以下のURLを参照してください!

www.security-camp.org

 

そこで私は集中Zというコースを選択しました。5日間同じものを作り続けるというコースです。ま集中Zは、Linuxアンチウイルスソフトを作ろうというコースです。集中Zでも5つの分野に分かれていました。

 

・Z1: 高品質なELFマルウェアシグネチャ(yara)の作成

・ Z2: 高精度なELFマルウェア分類

Z3: yaraシグネチャマッチングの高速化

・ Z4: 圧倒的高速なIDS(パケットフィルタ)の作成

・Z5: 圧倒的高速なマルウェアスキャンクラウドストレー ジの作成

 

私はこのZ3のyaraシグネチャマッチングの高速化をやりました。

f:id:yottiii:20180501195048p:plain

ちなみに受講生は私一人だったので、生徒一人に対し、講師一人というめっちゃ濃密でした笑

またこの講師の新屋さんという方がとてもすごい人でした^^;twitteと本は最後に貼っておきます!とにかく講師とのレベルの違いに驚きました。

 

3.yaraの高速化

f:id:yottiii:20180501195622p:plain

 で何をやったかというとyaraというマルウェア検知ツールの高速化を行いました!

具体的にyaraについて説明しますと。。。。

こんな感じです。

 

次にyaraルールについて説明します!

f:id:yottiii:20180501195805p:plain

どのようなものかというと、上の文字列の$test1と$test2の取りかがマルウェアの中に入ってたらExampleRuleと表示されます。ようは自分で独自のルールを書き、マルウェアを検知できるというものです。

またパターンの記述には正規表現も書くことができます!Yara2.0からは自前の正規表現エンジンを搭載しています!

それで今回の高速化の対象はyara3.6.3です。

githubのURLを載せておきます!!!

github.com

yaraシグネチャの要は固定文字列探索にあります。現在yaraは文字列の探索に、固定文字列探索を採用しています。なので以下のようなデメリットメリットが挙げれます。

正規表現探索は表現豊かだが遅い

・固定文字列探索は文字列だけなので速い

 

ここでmiraiのyararulesを見てみます

f:id:yottiii:20180501200606p:plain

https://github.com/Yara-Rules/rules/blob/master/malware/MALW_Mirai.yar

上記のURLにマルウェアのルールがまとめてあります。

 

4.高速化の検討

 セキュリティキャンプではこのyararulesの高速化をやったというのは先ほど話しました!ではどのように高速化したのかというのを説明してきます。高速化の方針としては

 

・YARAの固定文字列探索部分を高速化

  Quick Search と呼ばれるアルゴリズムを実装

 

ここで文字列探索についての説明をしておきます

 

単純な固定文字列探索

f:id:yottiii:20180501201108p:plain

              図 1.固定文字列探索例

 

あかさかさかすからさかすを探索する場合は、図1のような手順で1文字ずつずらして探索していくわけです。

次にQSアルゴリズムを見てみましょう!

f:id:yottiii:20180501201331p:plain

            図2.QSアルゴリズム探索

 

このアルゴリズムは図2を見てもらえばわかるように、キーワード末によって次にシフトする長さを決めています!

ちなみに計算量に関していかに示しておきます!!

 

 検索対象の文字列の長さを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/

 

vimeo.com

 

 

vimeo.com

 

 

このように限定的なケース(固定文字列探索で済む場合)において4倍ほどの高速化に成功しました!!!!!

※実装が不完全なため、シグネチャ正規表現などを含む場合は正しく動かない。

コードに関してはgithubに公開します!!

github.com

 

ここも参考にしてみてください!

speakerdeck.com

6.感想

・quick search アルゴリズムの理解

・膨大なソースコード読む

・書いたコードは六十行程度

・データ構造の理解

・高速化できたけどソースはまだ未完成(本家にマージできるレベルでは到底ない)

 

まずQSアルゴリズムが難しかったです!講師の新屋さんは、正規表現の研究者でもありとても計算量などに関して詳しく説明してくださいました!

二つ目に膨大なソースコードを読むのが初めてだったので、ここまで膨大5万行ほどのコードを読んだのは初めてだったので大変でした^^;またgdbというデバッカを使ってコードを読んだのですが、gdb使ったのもその時が初だったのでかなり覚えるのが大変でした。

ただそれ以上に得るものも多かったです!!このキャンプに参加して、自分もまだまだ修行が足りないので、もっともっと勉強しなくてはいけないと改めて感じることができました。またセキュリティ好きの同志もでき、今でも連絡を取り合ったりする人もいるので、とても良い機会だと思いました!!

悩んでいる人は是非とも参加するべきだと思います!!!!

 

7.最後に

セキュリティキャンプ2017で担当してくださった新屋さんはじめ、Zチームの講師のみなさん、その他講師のみなさんに深く感謝申し上げます。

 

参考文献

[1]新屋 良磨 ,鈴木 勇介,高田 謙 "正規表現技術入門 --最新エンジン実装と理論的背景",2015

twitter

新屋さん@sinya8282

 

 様子

https://pbs.twimg.com/media/DHPbSaGUAAAD8By.jpg

https://pbs.twimg.com/media/DHZVxi7VoAIM6Fl.jpg

https://pbs.twimg.com/media/DHQoizUUIAA7Apz.jpg