フィルタリングルール最適化問題の解法ル最適化問題の解法 神奈川大学理学部情報科学科 田中研究室
インターネットの仕組み IP アドレス - パケット 00 送り先 IPアドレス発信元 IPアドレスを含む 確実に相手に届く ルータ ルータ 00 IP アドレス ルータ自宅.55.5. ルータ 大学.7.5.0
インターネットの仕組み パケット - ルータ 00 00 ルータ パケット 00 000 00 00 00 00 00 ルータ ルータ 00 ルータ ルータ 自宅 00 000 大学 00
インターネットの仕組み - ルータ - ルータ 00 IXP 00 ルータ 00 00 00 00 プロバイダ 00 ルータ プロバイダ ルータ ルータ ルータ 自宅 大学
インターネットの仕組み ポート - ルータ ポート番号 自宅 ルータ 大学 5 電子メール送信 ポート番号でサービスを識別 80 web 0 電子メール受信
インターネットは危険! インターネット 00 から 000 00 国から 大学から 官庁, 企業, 家庭 感染 クラッカー 侵入 破壊ウィルス プログラムに寄生するプログラムワーム ネットワークを通じて増殖するウィルス 感染すると
際限ない増殖 インターネット アタック 官庁, 企業, 家庭 次々と他のマシンを攻撃 ネットワーク経由なので感染の広がりが速い 数時間で世界中へ蔓延!
フィルタリングルール最適化問題 00 から 発信元を見て危険な通信をブロック! インターネット ルータ 000 国から 官庁, 企業, 家庭 ルータ上のフィルタ規則 大学から : 許可 会社から : 拒否 国から : 拒否 規則が多いと遅延が発生回線速度アップでは対応できない 問題! 遅延を最小にするルールルの書き方は?
パケットフィルタリングのモデル パケット ルール ルールル ルール パケットの通過を許可 パケットの通過を拒否 パケットの通過を拒否 パケットの通過を許可 ルール n デフォルト評価
フィルタリングルールの形式 i 番目のルール : v i b b 0 b m ( {0,, } v {, }) b i ビット列 ビット列 : 例 ) 送信元のIPアドレス送り先の IP アドレス.7.59.0 9.8..8 ポート番号 80 プロトコル TCP 000000.000. 000.0000000
例 ) 許可 0000000000- - - - - - - - - - - - - - - - 発信元は神奈川大学 0000000000000000000 送信先は 大学
パケットフィルタリングのイメージ 許可 b 拒否 0 b 0 b 空間のカラーリング 許可( 拒否 ) の裏側が常に拒否 ( 許可 ) になるわけではない
ルールの適用の順序 注意 : 各々のルールに置いては 直前のルールまでに評価が決まらなかったパケットのみが評価の対象に 順序を考慮しながらルールを決める必要あり 単純な論理式の組み合わせの問題の問題にはならない
評価パケット数 ルールル ルール パケット 定義 ( 評価パケット数 ) ルールル i によって評価が決まるパケット数 ルール 総パケット数 = i v i v i ルール n n i は到着パケットの頻度分布によって変化
ネットワーク機器の遅延 パケット ルール ルールル ルール i 番目のルールによって評価が決まるパケットは i 回の評価を受けている 回の評価を遅延 考え ネットワーク機器への遅延を 定義 ルール n n n L ( ) i i i 遅延はルールセットルセット の関数である点に注意 v
L() を最小にするような を求めよ! 最適フィルタリングルール構成問題ル構成問題
最適化の方針 ) 複数のルールを つにまとめる ( 併合 ) ルール ルール ルールル 併合 ルール ルール ルール n ルールル n 各 v i が減少
) ルールを入れ替える ( 入替 ) ルール ルールル ルール 入替 ルール ルールル ルール ルール n ルール n 上位のルールで評価が決まるパケットが増加し i v i が減少
ルールの併合法 評価が同じで連続するルールを併合例 ).7.59..7...5.. 論理関数の簡単化の問題に帰着 カルノー図図 クワイン マクラスキー法など
クワイン マクラスキー法 論理関数の積和標準形からその最簡形を求める手法 ) 関数の積和標準形を求める 例 ) 00-000 00 0 00 個々のビットの積 ( 最小項 ) として展開 全てのルールについて最小項を求める
) 最小項を 進数の順に整列 例 ) 000 0 00 0 00
) 各項を比較して対応するビットがビットだけ異なる項を選び圧縮 例 ) 000 00 0 00 00 - -00 0 -
) 残った項 ( 主項 ) 最小項なる表を作成し 主項が最小項を含むなら を記入例 ) 00 - 最小項 0 000 00 00-00 主項 0 -
5) 全ての最小項が少なくともつの を含むような主項の組み合わせを求める最小項例 ) 0 000 00 00 00 - -00 主項 0 - つだけの を含む最小項に注目
6) 選んだ主項の和が最簡形となる 例 ) 000 00 最小項 0 00 00 - -00 主項 0 - の部分はに含まれ はを含む つの主項で つの最小項と同等
併合結果 00-00 0 00-00 0-00 ) ( L ) ( L 7 ) ( L 6 ) ( L 遅延は 86% 程度に
ルールの入替法 併合の場合 評価が同じで連続するルールを併合 入替の場合 評価が異なる連続するルールをどう扱うか? 例 ) 00 0 - - < なので入れ替えたいが 入れ替えると評価が変わってしまうどんな場合に入替が可能かつ有効か?
定義 : 重複 i で評価が決まり i+ を i の手前に移動したとき i+で評価が決まるようなパケットが存在するとき i i+ は重複しているといい 重複しているパケット重複しているパケットの数を i i+ で表す 例 ) 00 00 =00- =0-- =0-- =00- =
入替の条件 命題 : 評価が等しい連続する つのルールル i i+ を入れ替えて L() が減少するための必要十分条件は i <i++i i++i i+ である 命題 : 評価が異なる連続する つのルールi i+を入れ替えて L() が減少するための必要十分条件は i i+=0 かつ i < i+ である
最適化手順 併合と入替を交互に適用して L() を減少 重複がないか 評価型が同じなら入替可能, 評価の等しいフィルタリングルールが連続するようルールを入替, クワイン マクラスキー法によりルールを併合,,, を繰り返し ルール数を最小にする, 上位のルールの評価パケット数が多くなるようルールをルの評価パケルを入替
最適化の例 着目 5 6 7 8 9 000-0 0000 - - 0-0 - 0 - - - -- - - - - L() 9 重複がないので入替
最適化の例 着目 5 6 7 8 9 0000 000-0 - - 0-0 - 0 - - - -- - - - - L() 9 重複し評価が異なるので入替せず
最適化の例 着目 5 6 7 8 9 0000 000-0 - - 0-0 - 0 - - - -- - - - - L() 9 重複するので入替せず
最適化の例 着目 5 6 7 8 9 0000 000-0 - - 0-0 - 0 - - - -- - - - - L() 9 重複するので入替せず
最適化の例 着目 5 6 7 8 9 0000 000-0 - - 0-0 - 0 - - - -- - - - - L() 9 併合してリナンバ
最適化の例 5 6 7 000 - - 0 - - 0-0 - 0 - - - -- 8 - - - - L() 7
最適化の例 5 6 7 000 - - 0 - - 0-0 - 0 - - - -- 000 - 上位のルールからルから 0 順に繰り返し 5 0 - - - 0 - - - - - - - L() 5 8 - - - - L() 7
最適化の例 0-000 - 0 0 - - 6 - - - - - - - 5 5 L() 5
最適化の例 0-000 - 0 0 - - 6 - - - - - - - 5 5 L() 5 重複な ) = 0 ( 重複なし ) かつ < より入替
最適化の例 000 0 - - - 0 000-6 - - - - - - - 5 5 その他のルールは入替の条件を満たさないため終了 L() 5 条件を満たさないため終了
応用の可能性 論理式のリストによってフィルタリングする問題全般に適用可能 例 ) ブリッジ スイッチの効率化 SPM メールの選別 パターン分類 通信速度と安全性の両立に貢献
今後の展望 クワイン マクラスキー法は計算量的に膨大 ルールが複雑になったときにどう対応するか? 頻度の変化にどう対応するか? 頻度を観測して動的にルールを変更 ( 適応型 )