Run-Based Trieを用いたパケットフィルタリングアルゴリズム

はじめに

本研究の目的は，パケットフィルタリングにおける遅延を減らすための，フィルタリングルールのルール数に依存しない，データ構造やフィルタリングアルゴリズムの開発である．

パケットフィルタリングとは，下図のように，外部ネットワークから入ってくるパケットと，ポリシーに基づいて生成したルールリストのルールとを比較することにより，不正アクセスを防ぐための仕組みである．

なお，本研究に関しては，現時点では，田中先生のページ（教員紹介のページ）に置いている論文 "Run-Based Trie Involving the Structure of Arbitrary Bitmask Rules" を読むのが一番良いです．

田中研のフィルタリングモデル

田中研究室のフィルタリングモデルについてはこちらを参照下さい．

↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 工事中 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

パケットフィルタリングアルゴリズム

パケットフィルタリングにおいて発生する遅延（パケットをどのルールで評価するかを決定するためにかかる時間），を減らす為の方針は大きく分けて次の二つある．

線型探索における比較回数を減らす（合致するパケットの数が多いルールをルールリストの上位に配置する等）
与えられたルールリストから決定木などのデータ構造を構築し，そのデータ構造を用いることにより，比較するルールを減少させる（適当に決定木を構築して，決定木を辿るだけでパケットに与える評価を決定する等）

Run-Based Trie

下記にルールリストの例と，例に示したルールリストから構成した Run-Based Trie を示す．

	$F$
$r_{1}$	$$ $0$ $$ $1$
$r_{2}$	$0$ $0$ $0$ $0$
$r_{3}$	$0$ $*$ $0$ $0$
$r_{4}$	$0$ $$ $1$ $$
$r_{5}$	$1$ $1$ $0$ $0$
$r_{6}$	$0$ $1$ $$ $$
$r_{7}$	$$ $$ $1$ $0$
$r_{8}$	$0$ $1$ $$ $$
$r_{9}$	$$ $1$ $1$ $$
$r_{10}$	$*$ $0$ $0$ $0$
$r_{11}$	$$ $1$ $$ $1$
$r_{12}$	$$ $$ $*$ $1$

Simple Search

決定木

集合族

\begin{align*} S_{1} &= \{ \{ r_{3}^{1}, r_{4}^{1} \}, \ \{ r_{3}^{1}, r_{4}^{1}, \underline{r_{2}^{1}} \}, \ \{ r_{3}^{1}, r_{4}^{1}, \underline{r_{8}^{1}} \}, \ \{ \underline{r_{5}^{1}} \}, \ \phi \} \\ S_{2} &= \{ \{ r_{1}^{1} \}, \ \{ r_{1}^{1}, \underline{r_{10}^{1}} \}, \ \{ r_{1}^{1}, \underline{r_{6}^{1}} \}, \ \{ r_{11}^{1} \}, \ \{ r_{11}^{1}, \underline{r_{9}^{1}} \} \} \\ S_{3} &= \{ \{ \underline{r_{3}^{2}} \}, \ \{ \underline{r_{4}^{2}} \}, \ \{ \underline{r_{4}^{2}}, \underline{r_{7}^{1}} \}, \ \phi \} \\ S_{4} &= \{ \{ \underline{r_{1}^{2}}, \underline{r_{11}^{2}}, \underline{r_{12}^{1}} \}, \ \phi \} \end{align*}

このページの先頭へ ▲