Clam AntiVirus といちゃいちゃする -005-

ClamAVの挙動を追う
ClamAVにはソースコードがいっぱい。
そこで、clamscanが実行された時に呼ばれる関数とその順序を追うことにした。

まず、資料としてこんなものを用意した。

The Document of Clam AntiVirus

まあ、ぶっちゃけた話この資料がすべてなので、これ以上考えることはなにもないのだが。

お腹が空いたので、意味のあるソースコード解読は次回に回すこととする。


ドキュメントの生成方法
このドキュメントは、Doxygenを使って生成した。
インストール方法の説明は他のサイトに任せるとして、ここでは具体的に行ったことをメモ。

$ cd clamav-0.97.8/libclamav
$ doxygen -g
$ vim Doxygen
$ doxygen

vim Doxygen で編集している箇所は次の通り。

< EXTRACT_ALL            = NO
> EXTRACT_ALL            = YES    # .hだけでなく.cも含める
< GENERATE_LATEX         = YES
> GENERATE_LATEX         = NO     # LaTeXソースは生成しない
< HAVE_DOT               = NO
> HAVE_DOT               = YES    # dotを使ってグラフ生成
< CALL_GRAPH             = NO
> CALL_GRAPH             = YES    # 呼び出しグラフを生成
< CALLER_GRAPH           = NO
> CALLER_GRAPH           = YES    # 呼び出し元グラフを生成

※ 奇数行を偶数行に、それぞれ変更した。

ドキュメントにはソースコード自体も含まれているので、大きく言えばこのドキュメントはソースコードを改変したものとなる。したがって、配布形態は元のライセンスと同じGPLである。

Clam AntiVirus といちゃいちゃする -004-


ACオートマトンのキー長変更実験
ClamAVは、ACオートマトンとハッシュテーブルの二つで候補シグネチャを絞り込んでいるが、ここではそのACオートマトンのみに着目する。
ACオートマトンにシグネチャを登録する際のキー長には、最小値と最大値を設定することができる。
前回の記事では、その値の変更方法を示した。

今回は、実際にキー長を変化させたときに、

  • clamdの起動時間
  • 占有メモリ量
  • スキャン時間

がどのように変化するかを調べた。

 


実験環境
以下の環境で実験した。

  1. マシン: [memo - enoz.jp] http://enoz.jp/memo.html
  2. Clam AntiVirus: Version 0.97.3

 


実験方法
以下の手順で実験を行った。
1. キー長の最小値を1とする。
2. nを1とする。
3. キー長の最大値をnとする。
4. ソースファイルを書き換える。
6. コンパイル、インストールする。
7. clamdを起動(起動時間・占有メモリ量を測定)。
8. clamdを使ってスキャンする(スキャン時間を測定)。
9. clamdを終了させる。
10. nが50未満なら、nに1足して3へ。

# ソースファイルの書き換え箇所は、./libclamav/default.h の定数部分である。
# コンパイル、インストールは make, make install で行う。
# clamdの起動時間、占有メモリ量の測定は、timeコマンドを使用する。
# スキャン対象には、ClamAVのソースコードの一部を用いる。
# スキャン時間は現実時間とし、clamdscanの出力するSUMMARYの値を信じる。
# pkillでclamdを終了させる。
# 今回はメモリの都合上50までとする。
# 最小値と最大値を同じ値にしたほうがtightな測定ができるはずだが、
最小値が大きすぎると、キーを確保できないシグネチャが出てきて、
clamdの起動自体が失敗する。

 


実験結果
測定結果から、以下の3つのグラフを作成した。


[Fig.1: Startup Time]


[Fig.2: Memory]


[Fig.3: Search Time]

 


考察01 -Startup Time-
ACオートマトンの構築方法は、Failure関数の作成を除けば基数探索木と同じである。
したがって、構築にかかる時間は最悪の場合でもキー長に対して線形である。
Fig.1を見ても、それが正しいことが分かる。

現実に即した評価をしても、これは問題にならない。
clamdの起動は、時間のかかるACオートマトン・ハッシュテーブルの構築をスキャン前に一度で済ませるために行う。
だから、元々2秒で終わっていた構築が3倍になったところで、問題にはなり得ない。
スペックが1/10のマシンだったとしても、同様だろう。

 


考察02 -Memory-
ACオートマトンの空間計算量は基数探索木とほぼ同じである。
したがって、空間計算量が最悪となる場合、そのオーダーはキー長に対して指数である。
しかし、Fig.2を見ると実際には線形に増加しているように見える。
キー長が1から3までのグラフは指数にも見えるが、その後はどう見ても線形である。

これは、ACオートマトンに置ける受理状態の数(気数探索木として見たときの葉の数)がシグネチャ数で頭打ちになっているからだと考えられる。
例えば、全受理状態における候補シグネチャ集合の要素数が1になったと仮定する。
すると、受理状態の数がシグネチャ数より多くなることはないので、キー長を1バイト長くするとノード数はシグネチャ数(定数)分増えることになる。
実際のACオートマトンにもこの様な現象が起きているのではないかと思う。
だいたい、1バイトで256通りの文字が表現できるとして、256^4 = 4,294,967,296 と余裕でシグネチャ数を越えちゃうし。

 


考察03 -Seartch Time-
一番おもしろいグラフになったのがスキャン時間だった。
Fig.3を見ると、キー長は3から5くらいのときが良さそうだと分かる。
それより長いと、メモリを食うばかりで対して速くならないのでなんかもったいない。

基本的にはキー長を長くすれば長くするほどAC法の効果が上がり、探索時間は短くなるはずである。
今回の実験では、キー長が5, 6の辺りでもう頭打ちになっている感がある。
これは、占有メモリ量の増え方が線形だったのと同じ理由によるものだと思われる。

キー長19で一度跳ね上がっているのは、偶然だと思われる。
今回の計測はCPU時間ではなく現実の時間で測定しているので、別のプロセスが割り込んで来てしまった可能性がある。

また、キー長35から40の増加、その後の再びの安定の原因についてはさっぱり見当がつかない。
いたずらにノード数が増えればリストになってしまい、探索時間が増えるのは自明だが、こんな上がり方はしないはずだ。
CPUかメモリを食う別のプロセスが存在した可能性もある。

 


考察04
以上のように、原因がさっぱりわからない現象もあったが、いたずらにキー長を増やしても仕方ないということがわかった。

この時点での最適なキー長はおそらく3から5であることが分かった。

私はClamAVで使われているAC法への理解が低いので、そこを勉強しない限りこれ以上の大きな知見は得られなさそうだ。
また、細かい評価を行いたければ、実際にACオートマトンがどのような形をしているかを直に見るのがよいと思われる。

Clam AntiVirus といちゃいちゃする -003-


Clam AntiVirus のチューニング
ClamAVは、入力ファイルとシグネチャのマッチングを行うことで、ウィルス検出を行っている。
しかし、すべてのシグネチャとのマッチングを行うと膨大な時間がかかる。
そこで、ClamAVはマッチする可能性のある候補シグネチャをあらかじめ二つのアルゴリズムで選別している。

二つのアルゴリズム(外部ハッシュ法とAho-Corasick法)は、二つのデータ構造(ハッシュテーブルとACオートマトン)で候補シグネチャを管理している。
ここへのシグネチャの登録は、シグネチャ中の3バイトのみを見て行われている。

ここでは、このバイト数(キー長)を変える方法をまとめておく。

 


Clam AntiVirus キー長の変更方法
今回使用するClamAVのバージョンは0.97.3である。
clamav-0.97.3.tar.gzを解凍してできた、clamav-0.97.3ディレクトリをカレントディレクトリとして説明を行う。

キー長は、ACオートマトンとハッシュテーブルで別に定義されており、それぞれ最低長と最大長がある。

たとえば、ACオートマトンのキー長の定義は

  • libclamav/default.h: #define CLI_DEFAULT_AC_MINDEPTH
  • libclamav/default.h: #define CLI_DEFAULT_AC_MAXDEPTH

でなされている。
実装では、それぞれ2と3が定義されている。

これらの値を書き換えて、make、make install すればよい。

# ハッシュ法はlibclamav/matchar-hash.cだと思ったのだが、ハッシュ関数の定義はlibclamav/matchar-bm.cのほうでされている。
# したがって、どれがハッシュテーブルのキー長なのか分からない。

Clam AntiVirus といちゃいちゃする -002-


シグネチャファイルとは
ClamAVは、シグネチャと呼ばれるウィルスパターンを持っている。
これと入力ファイルのマッチングを行うことで、ウィルス検出を行っている。
シグネチャは、拡張子がcvdであるデータベースファイルに圧縮された状態で格納されている。
これをシグネチャファイルと呼ぶ。

 


シグネチャファイルの見方
ClamAVのシグネチャファイルは以下の二つである。

  • database/main.cvd
  • database/daily.cvd

日々更新されるウィルス定義はdaily.cvdに追記され、数日経つとmain.cvdへ移動されるらしい。
これらのcvdファイルは、「COPYRIGHT(512バイト) + 可変長のデータ」という風にできている。
また、可変長のデータはtar+gzで圧縮されている。

そこで、ddなどのコマンドを使うなどして初めの512バイトを除いたファイルを作り、それをtarで展開するとシグネチャを見ることができる。
展開後のファイルはテキストファイルなので、テキストエディタなどで簡単に見ることができる。
楽しいよね。