第２回地域連携公開セミナー

インターネットの数学～ハッシュ関数の応用を中心に～2006. 6. 30
富山県立大学
工学部情報システム工学科
太田 聡

本日のアウトライン
9 準備• インターネットについて• ハッシュ関数とは
9 研究動向紹介• 攻撃の逆探知技術（IPトレースバック）• 測定パケットのサンプリング技術• 分散ハッシュテーブル技術
9 講師の研究成果• インターネットのパッシブ性能測定とハッシュ関数

第１部 準備
9 数学のこと（講演題名について）
9 インターネットについて
9 ハッシュ関数とは

数学はお好き？
9 数学：工学の基礎
9 意外と多い「数学嫌い」なエンジニア
9 数学：役に立つ場合も多い• 直接役に立たなくても，論理的な考えを養う道具
9 本日の講演内容：本当は数学というよりは「ソフトウェア工学」のテクニックなのだけれど．．．
• 数学的感覚はある話

インターネットと数学
9 インターネット• 基本的な方式：さほど高度な数学的手法は使ない
9 最先端の研究：様々な数学的手法• リアルタイム，高信頼度のストリーミング（映像等）で使われる，損失補償符号化方式• 攻撃の逆探知技術• 性能解析手法，性能観測手法

全部が実用に供されるわけではない
それでも着想の面白さだけでも知る価値インターネットの基本
9 「IPパケット（データグラム）」による情報伝送「アドレス」を付与

ルータ
ルータ

ルータ

送り先アドレスを見て行き先判断
IPパケット・送りたい情報データ・送り先アドレス，送り元アドレス他の付加情報

本日の話題：ハッシュ関数の利用
9 インターネットで何の役に立つのか？
• ネットワークの管理• IPパケットの通過経路の把握：攻撃の逆探知• 記録対象パケットのサンプリング• ネットワークの性能パラメタの測定• ネットワーク上の高性能な分散データ管理• 暗号ハッシュ関数とは何か？（１）9 ハッシュ関数：計算機のソフトウェアで常套的に使用
9 入力 x：任意の大きさの整数値
9 出力 h(x)：A個の整数値0, 1, 2, …, A – 1のいずれか１つ
入力 x22759556112020

01・・・

1939
3

演算

出力h(x)

A–1
範囲が決まっていない数

範囲が決まった数

ハッシュ関数とは何か？（２）9 ハッシュ関数の入力• 計算機や，ディジタル通信のデータはすべてビット列→ あらゆるデータを２進整数として解釈可能→ ハッシュ関数の入力として使える• 任意の文字列，実数を含めた数値，インターネットのパケットの内容，などを入力にできる．
・文字列「本日は地域連携．．．」

・インターネットのパケット(01101…)2

・・・

・絵

演算

出力h(x)
01
A–1

範囲が決まった数

ハッシュ関数を理解するための例（１）9 桁数の多い整数を入力して，0以上６未満の整数を出力

入力値 x

数値演算

出力値 h(x)032481922

1916783278369932

34447771

45ハッシュ関数を理解するための例（2）9 アルファベット文字列を入力して，0以上６未満の整数を出力

入力値 x整数として解釈

数値演算

出力値 h(x)0toyama(01110100・・・)2niigata(01101110・・・)2

2

gifu

(01100111・・・)231

4
文字列「gifu」のビット列表現
２進整数と見なす5

ハッシュ関数：出力の一様性（１）9 重要な性質：特定の出力値y = h(x)が出力される確率・・・1/A
発生確率

全部同じ確率1/A

・ ・ ・012

A–2 A–1
出力値

ハッシュ関数：出力の一様性（２）9 異なる入力値x1，x2から同じ出力yが発生する確率： 1/A
9Aが大きな値なら，確率 1/Aは小さく，無視できる

入力 xx1x2

演算

出力h(x)
h(x2)

異なる入力

h(x1)

範囲は決まっていて異なる出力

ハッシュ関数：出力の一様性（３）9 A個の出力値のうち，n個の値のいずれかをとる確率： n/A
h(x)
演算
入力 x…

A–1

0からn – 1までのn個の値のどれか・・・

…

01
n–1n

確率 n/A

沢山のデータから，一定の確率n/Aでサンプルを選ぶのに使えるハッシュ関数の実現方法
9 方法１：入力された整数値xを，整数Aで割ったときの余りを出力する．
例：
A = 5の場合
x=1→ h(x) = 1h(x) = x mod A
x=0→ h(x) = 0x = 193477 → h(x) = 2x = 43219999 → h(x) = 4
9 方法２：入力された整数値に，ある数値aを掛けて，その小数部分をある桁数取り出す．
9 方法３：入力値を２進数表示したときの，各桁の値を係数とする多項式を考え，これを一定の多項式で割り，余りの多項式の係数を２進数の各桁とする値を出力とする．

ソフトウェアでの使用法
9 例：学生のデータを表から学生の名前をキーとして検索
番号
１２
３
４

氏名
何野誰子
何屋何兵衛
大山昇太．．．

データｘｘｘｘｘｘｘｘｘｘｘｘｘｘｘ

方法１ 名前を表の１番上から順に，検索キーと一致するまで調べて行く
最悪の場合，検索キーと学生全員の名前を比較する必要
表が大きいと恐ろしく時間が掛かる
方法２ 名前をハッシュ関数に入力したときの出力がyならばy番目のデータ
キーをハッシュ関数に入力すれば，その出力から直ちに表の何番目かが分かる
非常に高速に表検索できる ・・・「ハッシュテーブル」の技術

ハッシュ関数：まとめ
9 ハッシュ関数

特徴１
範囲の決まっていないデータ → 一定の範囲の整数
桁数の多いデータを，桁数の少ない整数に結び付ける

特徴２
出力値： どの値も同じ確率で発生（一様に分布）
入力が違えば，出力値も高い確率で異なる出力値を基準に，一定の確率でデータを選択できる

第２部 研究動向紹介
9 DoS攻撃の逆探知技術（IPトレースバック）• 一定の範囲の整数を出力する性質，出力値が一様に分布する性質を利用
9 記録パケットのサンプリング技術• 出力値が一様に分布する性質を利用
9 分散ハッシュテーブル技術• 出力値が一様に分布する性質を利用

DoS攻撃とIPトレースバック（１）9 DoS (Denial of Service) とDDoS (Distributed Denial ofService)攻撃
機能停止
DoS攻撃・・・ 大量のトラヒック
サーバの欠陥DDoS攻撃
・・・

攻撃者

サーバ

サーバ多数のホスト↓
大量のトラヒック

一般ユーザ攻撃プログラム

DoS攻撃とIPトレースバック（２）9 DoS/DDoS最近の事例• 2006/6/19：「2ちゃんねる」がDDoS攻撃で障害• 2006/5/31：「島根県ホームページ」にDoS攻撃• 2006/1/1：「靖国神社ホームページ」にDoS攻撃
9 対策と問題点• 対策：攻撃パケットの発生元を正しく突き止めて，攻撃パケットを遮断する必要• 難しさ：パケットのヘッダに記された「送信元アドレス」は簡単に偽装できる→パケットを見ても発生元は分からない

DoS攻撃とIPトレースバック（３）9 Snoeren他，Hash-Based IP Traceback, ACM
SIGCOM’01, 2001年8月．
9 サーバに攻撃があったとき，攻撃元を逆探知（IPトレースバッ
ク）する技術の一つ．
9 方法• インターネットのルータの中で，パケットを記録．
• 攻撃パケットと同じパケットが記録されたルータをたどっていけば，攻撃元が分かる• 問題点：インターネットを流れるパケット数は膨大→ パケットの記録 ＝ 巨大な記憶領域

DoS攻撃とIPトレースバック（４）9 パケットの不変部分をハッシュ関数に入力
9 出力：入力より桁数小（さらにパケット通過の有無をビットベクトルで記録，記憶領域を削減）

攻撃パケット

記録あり

記録あり

記録あり

問合せ
サーバ

DoS攻撃とIPトレースバック（５）9 ハッシュ関数による記憶領域の削減
IPパケット
ハッシュ関数h(x)決まった範囲の整数：桁数小
ほぼパケット毎に異なる値→ 攻撃パケット通過の証拠
出力y → 第yビットの値が１のビットベクトルを記録
・・・記憶領域をごく小さくできる記録パケットのサンプリング（１）9 例えば，N.G. Duffield and M. Grossglauser, Trajectory
sampling for direct traffic observation, IEEE/ACM Trans.
On Networking, 9, pp.280-292, June 2001.
9 実現したいこと：• パケットの経路を知るためにパケットの記録をとりたい• 全パケットを記録する必要はない• 一定の割合のパケットをサンプリングし，記録• あるノードで記録されたパケット→他のノードでも記録（サイコロ的に記録の要否を決めてはいけない）
9 方法• パケットの不変部分をハッシュ関数に入力，出力値がある値rより小さければ記録．そうでなければ記録しない．

記録パケットのサンプリング（２）9 イメージ図
X%のパケット：ルータで記録したい
ルータb
ホスト

ルータaで記録→ルータcでも記録したい

ルータa
ルータc

ルータd

ルータe

残りのパケット：記録しなくてよいホスト記録パケットのサンプリング（３）9 ハッシュ関数で記録するかどうかを判断・・・パケット
不変部分（TTL，チェックサムは転送中に変化）
ハッシュ関数h(x)に入力
出力値： 0, 1, …, r – 1, r, r + 1, …, A – 1

記録する

記録しない

9 全ての値が等確率→全パケットのr/Aだけが記録される．
9 同一パケットは同じ出力→１つのルータで記録＝他のルータでも記録分散ハッシュテーブル（１）9 例えば，I. Stoica他，Chord: a scalable peer-to-peer
lookup protocol for Internet applications, IEEE/ACM
Trans. on Networking, 11, pp.17-32, Feb. 2003.
9 問題• 多数のコンピュータがインターネットに接続されていて，多数のデータがこれらのコンピュータで管理• コンピュータは同じように振舞う（P2P環境）• 各コンピュータができるだけ同じ量のデータを扱うように• コンピュータの離脱・追加時のデータの移動は簡単にコンピュータと，データの関係はどうしたらよいか？

分散ハッシュテーブル（２）9 イメージ図

分散配置されたデータ
PC2

PC1 data A,B,C

data D,E,F

data O,P・・・

欲しいデータインターネット

PC6

PC5

data M,N

PC4

何処に？

PC3 data G
data H,I,J,K,L

問題：どのデータをどのコンピュータに管理させるか

分散ハッシュテーブル（３）9 出力値が0, 1, …, 2m – 1となるハッシュ関数を使用
9 出力値：下図のように円状に配置
2m – 1 02m – 2・・・

データの名前（キー）コンピュータのアドレス

12・・・ハッシュ関数へ入力

分散ハッシュテーブル（４）9 データ：アドレスのハッシュ値が，名前（キー）のハッシュ値に等しいか，円を時計周りに見て名前のハッシュ値の後ろにあるようなコンピュータで管理
n2が管理

データの名前n1

k1
k2

XXXXXXX
k6

XOXOOXXn2

OOXOOOX

コンピュータのアドレス
a.b.c.de.f.g.hi.j.k.ln3

ハッシュ関数↓0,…, 2m – 1の整数を出力

k3
k5

k4

n3が管理

ハッシュ関数↓0,…, 2m – 1の整数を出力

分散ハッシュテーブル（５）9 ハッシュ関数を使うことによる効果• コンピュータが管理するデータの数は，特定のコンピュータに集中しない（ほぼ全てのコンピュータが同じ負荷）• 新しいコンピュータが追加されたり，削除されたりしたとき必要なデータの移動が容易• データの名前（キー）から，それを管理しているコンピュー
タのアドレスを導く効率良い手法がある

研究動向：まとめ
9 ハッシュ関数の性質を有効利用した，インターネット技術の研究事例を紹介
9 ハッシュ関数に基づく攻撃のIPトレースバック：出力値が限られた範囲になることを利用し，記憶領域削減
9 監視パケットのサンプリング：出力値が一様分布する性質を利用し，一定の割合でパケットを選択
9 分散ハッシュテーブル：出力値が一様分布する性質を利用し，優れた性質の分散データ管理

第３部 講師の研究成果
9 インターネットのパッシブ性能測定とハッシュ関数• インターネットの性能測定• パッシブ測定とアクティブ測定• パッシブ測定とハッシュ関数• 問題点と解決法• 効果の確認インターネットの性能測定
9 インターネットのサービス提供者：性能測定が必要• 通信需要に対し設備不足で性能劣化→設備増設が必要• 通信需要に対し過剰設備→不経済• 性能劣化が起きず，設備量が適正であることを測定を通じて確認
9 性能尺度（測定項目）の例• パケット損• 転送遅延，遅延変動

パッシブ測定とアクティブ測定
パッシブ測定：ユーザパケットを観測

アクティブ測定：試験トラヒックを注入・測定
アクティブ測定

パッシブ測定ユーザの体験する性能：測定困難

ユーザの体験する性能：測定可能• 試験トラヒック注入による負荷状態変化• 試験トラヒックとユーザトラヒッ
ク：特性の違い

記憶領域・伝送帯域：極めて大• 送り側，受け側でパケットの蓄積が必要→膨大な記憶領域• 蓄積したパケット：比較のため集める必要→広い伝送帯域

記憶領域・伝送帯域：問題なし

パッシブ測定による性能測定の原理
9 送信側と受信側でパケットを一定の時間記録
9 同一パケットの送信側と受信側の記録を比較• パケットが送信側・受信側の両方で記録？→損失測定• 送信側・受信側の記録時刻の比較→遅延，遅延変動
IPパケットインターネット
受信側

送信側

記録

同一パケット比較
性能尺度

記録

パッシブ測定とハッシュ関数
9 ハッシュ関数によるIPパケットを識別可能な特徴情報
IPパケット
一部バイト列

出力値・・・[0, A − 1]の整数を出力するハッシュ関数h(x)⎡(log 2 A) / 8⎤ バイト9パケット長よりはるかに短い
9同一パケットを識別可能

パッシブ測定でハッシュ出力値を送信側・受信側で記録記憶領域を大幅削減可能

問題点
9 ハッシュ関数：異なった入力値から同じ出力値を発生する確率：非常に小さいが，０ではない• 同じ出力が発生 → 送信側，受信側で異なるパケットの記録を比較＝測定誤り• 解決法：送信側，受信側で記録の開始・停止順序を適切に実行
9 ハッシュ関数 → パケットの識別情報の記憶領域は激減
・・・時刻情報（タイムスタンプ）の圧縮も必要• 時刻情報：遅延，遅延変動の測定では記録が必須• 解決法：可変長符号化

問題点の解決法１（ハッシュ値衝突対策）
9 パケット損測定の例
受け側

送り側
開始要求

送り側の記録より先に開始

Requeste
Respons

記録開始

送り側で記録したパケット

記録開始

終了要求

T1 > 遅延
Request

記録転送要求e
Respons
Request

記録終了

記録終了

受け側に到着したら受け側でも記録（損失を正しく計数）

記録転送
Data

記録比較
損失計数

送り側の記録終了後十分な時間経過後に終了

問題点の解決法２(タイムスタンプ圧縮）
9 従来技術 ：時刻の差を記録することでバイト長低減
パケットtxn + 2
Tn + 2xn + 1
Tn + 1

xn
Tn

記録対象

←送信（受信）時刻• 送信・受信時刻の絶対値：開始時刻に時刻差を加算することで復元可• 時刻差は小さいので所要桁数が小問題点：時刻差の最大値を表現可能な一定のバイト長→多くのパケットで不必要に大きなバイト長
提案：時刻差の大きさに適応してバイト長を可変に

実験による検証
9 実験系

帯域・損失を設定：NIST Net を使用
Source Host

Transit Host
(Netwrork Emulator)

1000Base-T

Pentium 4, 2.66GHz

Destination Host

1000Base-T

Pentium 4, 3.2GHz

Pentium 4, 2.66GHz

ユーザ（測定対象）トラヒック：mgenで発生
パケット損失，遅延変動の測定法をソフトウェアで実装

実験結果１：パケット損失率の測定
9 ネットワークエミュレータで設定したパケット損失率と実測値の関係
Measured Packet Loss Ratio, Pmeas

1.0E+00

1.0E-01

1.0E-02

ProposedMethod
Iperfping
Ideal Value

1.0E-03

1.0E-04

1.0E-05
1.0E-05 1.0E-04 1.0E-03 1.0E-02 1.0E-01
Packet Loss Ratio Set on Emulator, Pset

実験結果２：遅延変動の測定
9 遅延標準偏差のネットワークエミュレータ設定値と測定値

Measured Value (msec)

120
100

Proposed Method
Ideal Value

80604020002040 60 80 100 120
Standard Deviation Set on Emulator (msec)

実験結果３：記憶領域の削減
9 記憶領域削減効果（遅延変動測定の例）
パケット識別情報

タイムスタンプ部分
9・パケットの一部で識別→16バイト以上必要

8Byte Length

7・ハッシュ関数使用
→3バイト

65432
1
0

時刻
絶対値

時刻差
固定長符号化
方法１

符号化
方法２

可変長符号化＋ハッシュ
関数：20%程度に記憶領域を削減

講師の研究：まとめ
9 利点がある一方，記憶領域が巨大であるため用途が限られていたパッシブ測定を研究対象
9 ハッシュ関数を使うことで僅かな記憶領域でパッシブ測定可能なことに着目
9 ハッシュ関数出力値の間の「衝突」や，時刻情報の記憶領域削減手法を研究
9 実験により，ハッシュ関数に基づく手法によるパケット損，遅延変動測定は正確で，かつ記憶領域は大きく削減できることを示した．

本日のまとめ
9 インターネットにおける数学的センスのある技術として「ハッシュ関数」の応用について紹介
9 近年提案されている，ハッシュ関数の性質を活用した研究• 攻撃トラヒックのIPトレースバック• 記録対象パケットのサンプリング• 分散ハッシュテーブル
9 講師自身の最近の研究• ハッシュ関数を利用したパッシブ性能測定（パケット損失，遅延変動）