第 5 章 マーキング数推定による確率的 パケットマーキングの高速化手法パケットマーキングの高速化手法
5.2 PPM におけるパケットマーキングの重複
一般的にPPMでは，被害ホストに近いルータほどマーキング重複数が多くなるという 傾向があることがこれまでの研究で示されている [81]．この傾向の要因として，[82]で 示されているように主に次の2つが考えられる．
• ホップ数に起因するマーキング重複
PPMでは，ルータはパケットがすでに他のルータによってマーキングされている かどうかに関わらず，確率的にパケットのマーキングを行うことから，ルータを経 由するたびにマーキングが上書きされる可能性がある．このため，攻撃ホストと被 害ホスト間のホップ数が多いほど，パケットがより多くのルータを経由することに なるため，マーキング情報が上書きされやすい．その結果，マーキング重複数は被 害ホストに近いルータほど指数的に増加することになる．
• トポロジに起因するマーキング重複
上述の通り，PPMでは被害ホストに近いルータほどマーキング重複数が多くなる という傾向があるが，被害ホストへのホップ数が同一のルータ間においても，被害 ホストから下流に向かうリンク数によってマーキング重複数が異なる．一般的に DDoS攻撃は，世界中に広く分散された攻撃ホストから，攻撃パケットを同時に被 害ホストへ送信することで，被害ホストのサービスを停止させる．このため，多く のリンクが接続されたルータほど被害ホストへのトラヒックは増大することから，
マーキング重複数が多くなる．
V
ld+1,1,a
d Hops
R1,1
Rd+1,1
Rd+1,i
Rd,1
Rd+1,l͇
R1,l̓
ld+1,I,a
ld+1,l,a
図5.1:攻撃ホストまでの経路
V R1,1 R2,1 Rd,1 Rd+1,1 Rk-1,1
A k Hops
d Hops
図5.2:タンデムネットワークモデル
一般的に DDoS攻撃の経路は，被害ホストを根としたツリー構造で表現することが できる．そこで本論文では，一般的な攻撃経路として図 5.1 で示されるツリーを考え る．ここで，被害ホスト(V)からdホップ離れたルータの集合を Rdとし，その要素を Rd,i(1≤i≤ |Rd|)とする．さらに，ルータRd,i において，下流にアドレスがaである被 害ホストを攻撃対象としている攻撃ホストが存在するエッジ数をld,i,a，マーキング確率 をpd,iとする．
0 5 10 15 20 25
0 5 10 15 20 25 30
Number of marking duplications
Hop counts from victim node 図5.3:各ルータにおけるマーキング重複数
5.2.1 ホップ数に起因するマーキング重複
本節ではホップ数によるマーキングの上書きによる影響を分析するため，図 5.2で示 されたkホップ離れた単一の攻撃ホスト(A)から被害ホスト(V)までが線形に接続され たモデルを用い，PPMによるマーキング重複数がどのように変化するかを述べる．した がって，各ルータの下流ルータへの接続リンク数はすべて1である．またPPMではすべ てのルータが同じマーキング確率pによりマーキングを行うものとする．このとき，被 害ホストにおいて，Rd,1のマーキング重複が発生する確率をvd,1 とすると，
vd,1 =p(1−p)d−1 (5.1)
である．さらに攻撃ホスト(V)が N 個の攻撃パケットを送信した場合，ルータRd,1 の マーキング重複数の期待値nd,1 は，
nd,1 =N vd,1 =N p(1−p)d−1 (5.2)
となる．図5.3にk = 30の場合の各ルータのマーキング重複数を示す．この図より，マー キング重複数は被害ホストに近いホストほど増加し，その増加数は指数的に変化するこ とがわかる．
攻撃経路を特定するためには，必ずしも被害ホストに近いルータほど指数的に重複数 を大きくする必要はない．例えば線形に重複数を変化させることによって，マーキング 重複数を減少させることができる．これらは，被害ホストに近いルータほどマーキング 確率を減少させることによって実現できる．
5.2.2 トポロジに起因するマーキング重複
これまでに述べたとおり，被害ホストからの攻撃経路は被害ホストを根とするツリーに よって構成されると考えることができる．すなわち，被害ホストに近いルータほど下流 からのトラヒックが集約され，被害ホスト宛のトラヒックが多くなる．したがって，等し い確率でパケットマーキングを行った場合，より多くの下流トラヒックを集約したルー タほどより多くのパケットをマーキングすることになる．このため，被害ホストまでの ホップ数が同一のルータ間においても，下流からのトラヒックが多く集約されるルータ ほど，マーキング重複数が多くなる．攻撃ホストがネットワークに多数かつ広く分散さ れている場合，被害ホストまでのホップ数が同じルータでは，マーキング重複数はルー
タの持つ下流への接続リンク数に比例すると考えられる．
攻撃経路を再構築するために必要となるマーキング重複数の増加量を維持できれば，そ れ以上のマーキング重複は必ずしも必要でないため，これらの不要なマーキング重複に ついては，下流への接続リンク数が多いほどマーキング確率を小さくすることによって 削減できる．