データ構造と資源管理

解析コンポーネント

解析コンポーネントにおけるデータ構造は，記憶領域の使用効率と処理負荷のバランスを 考慮して構築している．図6.4は解析コンポーネントのクラス図であり，データ構造の概要を 示している．ROOKはIPv4とIPv6に対してホストとセッションを管理している．ホストは1 つのIPアドレス，セッションは2^つのIPアドレスの組み合わせをキーとしてインスタンスを 生成している．ホスト及びセッションはパトリシア木，あるいはハッシュテーブルのいずれ

Session Table (TCP) Session Table

(UDP) Host

(IPv4)

IPv4Decoder

Host Table (IPv4)

Session Table (IPv4)

Session (UDP)

Session (TCP)

Variable VarBox Session

(IPv4)

Instance Tree or Hash Table

Session Table (ICMP) 1

1 1

1

1 0..n 1

0..n 1

2 1

1 1

0,1

0,1 0,1

Host (IPv6)

IPv6Decoder

Host Table (IPv6)

Session Table (IPv6)

Session (IPv6) 1

1 1

1 2

11 1

0,1

0,1 0,1

0..n 1 1

0,1

1

0,1

Session (ICMP) 1

0...n

1 0...n

1

1 0...n

1

0,1 0...n

0..n 1

1

0,1 1

0,1

図6.4:解析コンポーネントのクラス図

かを起動時に指定でき，計算機のメモリ制約や監視範囲などに応じて変更できる．各IPセッ ションのインスタンスは必要に応じてTCP^，UDP^，ICMPセッションの管理テーブルを持ち，

これもパトリシア木かハッシュテーブルかを選択できる．一般的な監視環境ではIPセッショ ンが大量に発生し，IP^{セッション上の}TCP^，UDP^，ICMPの各セッションは平均して10^程度 と予想される．ハッシュテーブルは十分な性能を出すためには広くテーブルを持つ必要があ るため，空間計算量がテーブルのサイズに応じて線形に成長するが，検索にかかる時間計算 量は定数になる．一方，パトリシア木はノード数Nに対して，空間計算量がO(N)^{，時間計算}

量がO(logN)^になる．ROOKはある管理ネットワークに接続しているホストを監視するのが

目的であり，多くの環境において内部ホストのIPアドレスは近接している．したがって，IP アドレスをキーにした場合はパトリシア木に偏りが発生する可能性が高い．よって，IPv4^と IPv6のホスト，セッションはハッシュテーブル，UDP^，TCP^，ICMPセッションはパトリシア 木を使うのが望ましい．

変数は解析コンポーネントで管理しており，IPv4とIPv6のホスト，およびUDP，TCP， ICMPのセッションは変数用のテーブル(VarBox)を持つことができる．これは必要に応じて 各インスタンスに付与される．変数のテーブルもメモリ使用効率と検索性能を考慮してパト

RuleBook Rule

Variable Prototype

1 1...n

Trigger

Variable Table

1 1...n

1 1

1

0...n

Condition

Const

Rule Entity Filter

Variable

1 1...n 1

1...n

1

1,2 Action

Set Var

Unset Var

Alert Calc Var 1

0...n

1

1...n

1 0...n

1

0...n 1

0...n

Instance Tree or Hash Table

図6.5:ルールコンポーネントのクラス図

リシア木で実装されており，32bitのキーによって変数が管理されている．よって，1つのイ ンスタンスは最大2^{32個の変数を扱える．}

各インスタンスは生成時にタイマに登録され，資源管理される．変数の生存時間や破棄条件 はルールによって定義されるため，ルールにしたがって生成，破棄が管理される．一方，セッ ションやホストのインスタンスについては一定間隔で変数を保持しているかを確認される．入 力されたネットワークトラフィックに関連しているセッションやホストは，次回の変数保持の 確認を遅らせ，変数を保持していた場合はセッションやホストを破棄せずに，再度タイマに 登録される．

ルールコンポーネント

ルールに関する基本的なクラス図を図6.5に示す．図6.5はルールをファイルから読み込ん だ時点でのデータ構造で，ネットワークトラフィックを用いた検査に対する最適化などはさ れていない．検査のための最適化は検知コンポーネント上でおこなう．

ルールはRuleBookインスタンスが統合して管理する．RuleBookインスタンスは変数テー

ブル(Variable Table)を持っており，全てのルールに出現する変数のプロトタイプ(Variable

Prototype^{インスタンス})^{を管理し，一意な}32bit^のIDを発行する．これをキーとして解析コ

ンポーネント上のVarBoxテーブルにアクセスし，変数の読み込み，書き込みを実施する．

Detect Engine

Variable Trigger Table

Multiplex Filter 1

1

1

1

Trigger Set Rule Book

1 1

1 1...n 1

1 1

1...n

図6.6:検知コンポーネントのクラス図

ルールには1つ以上の条件式(Triggerインスタンス)があり，ネットワークトラフィックや 変数の比較条件(Condition^{インスタンス})や条件式に合致した後の処理(Action^{インスタンス}) をまとめている．Triggerインスタンスは互いに独立しているため，1^{つのトランザクション} と解釈できる．TriggerインスタンスがもつConditionインスタンスは積条件，和条件や条件 の結合に対応している．よって，ルールの記述内容次第では複雑な条件式となり，検索の最 適化が難しくなる．そのため，検査すべきTriggerの絞り込みは検知コンポーネントで実施す るが，最終的にはTriggerインスタンスによって条件式の精査をする必要がある．

Conditionインスタンスは条件検査のための項(Rule Entity)を1つあるいは2つもち，これ は変数の読み込み(Variable)，ネットワークトラフィックに含まれる情報(Filter)^，定数(Const) のいずれかによって実装されている．これらのRule Entityインスタンスは真偽値型，数値型，

データ列型，IPアドレス型のいずれかの型を持ち，Conditionインスタンスは比較方法(^一致，

大小，一部を含む）を持つ．Variable^{インスタンスは}Variable Prototype^{インスタンスから変} 数操作に必要となる情報を取得する．条件式に合致した場合は，Triggerインスタンスが保持

しているActionインスタンスにしたがって検知後の処理が実行される．実装されているのは

変数の変更(Set Var)^{，変数の削除}(Unset Var)^{，変数の計算}(Calc Var)^{，警告の発行}(Alert)^と なっている．

検知コンポーネント

検知に関するクラス図を図6.6に示す．検知エンジン(Detection Engine)が全体のルールを

Rule Bookインスタンスとして持ち，検査すべきTriggerインスタンスを絞り込む検索関数

(Multiplex Filter^{インスタンス})^を持つ．Multiplex Filter^{は検査すべき条件数}N^{に対して時間} 計算量がO(N)未満，あるいは定数になるようなアルゴリズムによってTriggerインスタンス を絞り込む．ROOK^ではAho-Corasick[71]によるペイロードの探索やIP^{アドレスやポート} 番号をキーとした木探索などを実装している．また，変数による条件式を含むTrigger^イン

スタンスをまとめて，変数のIDをキーからTriggerインスタンスを検索するためのテーブル (Variable Trigger Table)を用意した．これは．検査するTriggerインスタンスを最小限にする ために，検査中のホストやセッションが保持している変数に関連したTriggerインスタンスを 抽出するためである．

図6.7: BNFによるルール文法

<rule_set> ::= {<rule>}

<rule> ::= 'rule' '(' '"' <rule_name> '"' ')' <prototype_set> '{' <trigger_set> '}'

<prototype_set> ::= {<prototype>}

<prototype> ::= <type> <var_name> '(' <prototype_arg> ')' ';'

<prototype_arg> ::= <proto_scope> | <proto_scope> ',' 'stack'

<type> ::= 'bool' | 'int' | 'raw' | 'addr'

<var_name> ::= <alpha> { <digit> | <var_name> | '_' | '-' }

<proto_scope> ::= 'host' | 'session'

<trigger_set> ::= <trigger> | <trigger> <trigger_set>

<trigger> ::= 'trigger' '(' <condition_set> ')' '{' <action_set> '}'

<condition_set> ::= <condition> | <condition> <condition_op> <condition_set>

<condition> ::= '(' <condition_set> ')' | <entity_set>

<condition_op> ::= '&&' | '||'

<entity_set> ::= <entity_uni> | <entity_side> <entity_op> <entity_side>

<entity_uni> ::= <filter> | <var>

<entity_side> ::= <filter> | <const> | <var>

<entity_op> ::= '==' | '<' | '>' | '<=' | '>=' | '!='

<filter> ::= <filter_name> '(' <filter_arg> ')'

<filter_arg> ::= '"' <string> '"' | <int>

<const> ::= '"' <string> '"' | <int>

<var> ::= <scope> '.' <var_name>

<scope> ::= 'dst' | 'src' | 'session'

<action_set> ::= <action> | <action_set>

<action> ::= <action_name> '(' <action_arg_set> ')' ';'

<action_arg_set> ::= <action_arg> | <action_arg> ',' <action_arg_set>

<action_arg> ::= '"' <string> '"' | <int> | <var_name>

<string> ::= {<alpha> | <digit> | <symbol>}

<int> ::= <digit> {<digit>}

<symbol> ::= '!' | '#' | '$' | '%' | '&' | '(' | ')' | '*' | '+' | ',' | '-' | '.' | '/' | ':' | ';' | '<' | '=' | '>' | '?' | '@' | '[' | '\' | ']' | '^' | '_' | '`' | '{' | '|' | '}' | '~'

<alpha> ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|

a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

<digit> ::= 0|1|2|3|4|5|6|7|8|9

{}^は0回以上の繰り返し

ドキュメント内 Year 2009 Dissertation (ページ 97-101)