Controlling High Bandwidth Aggregates in the Network について 米澤研究室　博士１年 小林　義徳

内容 Introduction Aggregate-based Congestion Control(ACC) シミュレーション Local ACC Pushback シミュレーション 結論と Future Work

Introduction

目的 ネットワークの輻輳から、正規ユーザーの帯域を保護 輻輳の原因 DDoS 攻撃 = 同時に複数のホストから、あるホストに大量に　 パケットを送りつける Flash Crowds　 = 特定の Web サイトにアクセスが集中

本論文では・・・ 従来の、Flow 単位での輻輳制御では不十分 DDoS 攻撃、Flash Crowds に対し無力 パケット群が複数の flow にまたがっている Aggregate-Based Congestion Control(ACC) の提案 Local ACC Pushback Mechanism

Aggregate とは? あるプロパティを持つパケット群 cf. flow プロパティ例 以下のものが全て等しいパケット群 TCP パケット ICMP ECHO パケット あるホスト行きの HTTP パケット チェックサムが間違っている IP パケット cf. flow 以下のものが全て等しいパケット群 送信元 IPアドレス: ポート番号 あて先　IP アドレス: ポート番号 プロトコル フィールド (TCP, UDP などをあらわす)

Aggregate-Based Congestion Control (ACC) Local ACC: 各ルーター 輻輳を起こしているパケット群(aggregate) の特定 問題のパケット群に対し帯域制限 Pushback: 複数のルーターで 上流のルーターに問題のパケット群の帯域制限を要求

Pushback R5 R4 R6 R7 R2 R1 R3 R0 Local ACC で輻輳制御しきれない場合、 より上流のルーターに帯域制限を要求 heavy traffic flow pushback message

Aggregate-Based Congestion Control (ACC) 輻輳しているか? パケットの drop rate で判断 輻輳の原因となるパケット群(aggregate) は? どのくらい帯域制限するか? pushback するべきか? いつ帯域制限を解除するか? 以上を各ルーターが判断・実行 ※ これらはポリシー依存であるが、この論文では深入りせず、単純なポリシーを扱う

ACC-enabled Router Input queues Output queue Match Congestion No Signature? No Yes Rate limiter Drop Drop adjust local ACC update congestion signature pushbackd pushback

Local ACC 輻輳の検出 帯域制限する aggregate の特定 output キューでのパケットの drop 率 > phigh がK 秒間続いた時、2. 以下を実行 帯域制限する aggregate の特定 帯域の大部分を占めている aggregate の特徴(congestion signature)を抽出 =　この論文では、あて先アドレスのみを使用

Local ACC 帯域の制限 5 秒ごとに L を更新 Rexcess = 全体の drop 率を ptarget 以下にするためのトラフィック量の上限 帯域制限 L の計算 Σ(Aggregate[k].arrival_rate – L) = Rexcess 5 秒ごとに L を更新 帯域制限がきつくなりすぎるのを防止

Simulation ～ Local ACC 5 つのaggregate 使用 Aggregate 1-4 は、いくつかの CBR flow から構成される Aggregate 5 は、 t=13 で増加、 t=25 で減り始める

Simulation ～ without ACC

Simulation ～ Local ACC 下のグラフ: 五番目のaggregate の、rate-limiter によるパケットの drop は含まない。

Simulation ～ Local ACC Aggregate 1-4 が、 aggregate 5 から保護されているのがわかる

Local ACC の限界 Local ACC では、あて先が同じ場合、 攻撃パケットと正規パケットの区別がつかない → どちらのパケット群にも同じように帯域制限をしてしまう より上流で帯域制限し、攻撃パケットから正規パケットを分離・保護すべし R1 より上流で帯域制限することで、攻撃パケットから正規パケットを分離、保護 R0

上流での帯域制限 ～ ご利益 保護されていない 保護される 40 40 R4 R4 2 R3 R3 R2 R2 100 Mbps

Pushback 上流のルーターに 帯域制限を要求 再帰的に上流に伝播 保護される 40 R4 2 R3 R2 ここで、 が10Mbps 以下に帯域制限される 100 Mbps ここで、 が10Mbps 以下に帯域制限される R1 10 Mbps R0 ここで、 が10Mbps 以下に帯域制限される

Pushback メカニズム(1/3) いつ Pushback するか? 上流ルーターへの Pushback 要求 メッセージの送信 rate-limiter でのパケットの drop が多い状態が数秒続いたとき 他の方法で、DDoS 攻撃されていることを知った時 上流ルーターへの Pushback 要求 メッセージの送信 それぞれの上流ルーターに、帯域制限を分配 max-min fashion 1., 2. は、上流に向かって再帰的になされる

Pushback request メッセージ Congestion Signature Bandwidth Limit Expiration Time RLS(Rate-limit-Session)-ID Depth of Requesting Node Pushback Type

Pushback ～帯域分配例 max-min fashion R2 R4 4 R3 2, 5, 12 : 上流から来ているトラフィック[Mbps] 2 5 12 2 4 R1 2, 4, 4 : 帯域制限要求[Mbps] 10 Mbps に制限したい R0

Pushback メカニズム(2/3) 下流ルーターへの Feedback 上流ルーターは pushback statusメッセージを返す(次のページ) 送信のタイミング leaf ノードは、タイマー使用 non-leaf ノードは、全ての上流ルーターから pushback status メッセージをうけとったら送信

下流ルーターへの Feedback R6 R7 R4 1 R5 10 7 5 R2 R1 R3 16 16 7 0.5 R0 Pushback status message = 帯域制限をやめた時のパケット量の見積もり 下流からの Pushback により帯域制限 を行っているルーター Rn

Pushback メカニズム(3/3) Pushback refresh メッセージ 下流ルーターは、上流からの feedback に基づいて帯域制限を再計算、 refresh メッセージ送信 上流ルーターは pushback refresh メッセージが来ない場合、帯域制限を解除

Simulation ～ Local ACC + pushback

Simulation ～ Local ACC + pushback Simple Topology での DoS 攻撃の シミュレーション より大きなネットワークでの、DDoS 攻撃のシミュレーション Flash Crowds congestion signature はパケットのあて先のみ ネットワークシミュレータ ns を使用

Traffic sources good: 正規パケット源 bad : DoS 攻撃者 poor: DoS 攻撃者と 誤認識されてしまう かわいそうな正規パケット源 congestion signature が同じ: 例) あて先が同じ

Simulation ～ Simple Topology good source bad source poor source R2 R3 100 Mbps 100 Mbps R1 ここが輻輳 Rn 10 Mbps router Local ACC のみの実験では、 R1 でのみ帯域制限、 pushback も加わると、R2, R3 も帯域制限をする。 R0 (1)帯域制限なし、 (2) Local ACC のみ、 (3) Local ACC + pushback の各場合について、 R1-R0 間の、各パケットが占める割合を測定

Simulation ～ Simple Topology 　DoS 攻撃の設定 攻撃が on の期間と、off の期間が等しい 0 < T < 40 [sec] で、ランダムの決定 on 期間は、 1Mbps の UDP flow を送信 bad flow の数 = 10 ～ 40

結果 default Local ACC 一番上 Local ACC + pushback

Simulation ～ Simple Topology 結果 帯域制限なしの場合 がほぼ100 % 近くまで増えてしまう Local ACC のみの場合 の帯域が制限され、 が保護されている と は区別不能、 は保護されない Local ACC + pushback の場合 と は区別可能、 も保護されている

Simulation ～ DDoS Attacks fan-in 4 R1 – R0 が輻輳 × 10 ホスト ここのバンド幅の割合を測定 × 4 ホスト × 4 or 32 ホスト

Simulation ～ DDoS Attacks 結果 4 ホスト × 2 Mbps (on 時) 32 ホスト × 0.25 Mbps(on 時)

Simulation ～ DDoS Attacks 結果 帯域制限なしの場合 帯域のほとんどを が占めてしまう Local ACC のみの場合 　　　は保護されるが、 は保護されない Local ACC + pushback の保護されている割合が、 × 32 の方では、 　　× 4 の場合の約半分 pushback をしてもまだ、 と を区別しきれない

Simulation ～ Flash Crowds ある Web サイトにアクセスが集中 シミュレーション設定 トポロジーは、DDoS Attack のときと同じ Flash traffic 源×32: 同じ Web サイトにアクセス × 10 : 他のサイトにアクセス HTTP リクエストが完了するまでの時間を測定

Simulation ～ Flash Crowds 結果

Simulation ～ Flash Crowds 結果 Pushback ありの場合 のリクエストの約 80 % が、6 sec で完了 (drop rate: 30 % → 6 %) Flash traffic の方に対しても、それほど悪い影響は与えていない (drop rate 30% → 33 %) 帯域制限なしの場合 6 sec 以内に完了しているリクエストの割合が 40 % 以下

Conclusions Aggregate-Based 輻輳制御メカニズムを提案 DDoS 攻撃、 Flash Crowds に対し有効であることをシミュレーションで示した とくに有効～

Future Work これらのメカニズムの落とし穴の調査 Aggregate-Based な輻輳が実際どのぐらい起こるのかの調査 ポリシー

Testbed Network good source bad source poor source R2 R3 R1 10 Mbps Rn router 5 Mbps 5 Mbps R6 2 Mbps 標的 標的

References [1] Implementing Pushback: Router-Based Defense Against DDoS Attacks John Ioannidis, Steven M.Bellovin, 2002 [2] Controlling High Bandwidth Aggregates in the Network Ratul Mahajan, Steven M.Bellovin, Sally Floyd, John Ioannidis, Vern Paxson, and Scott Shenker, 2001

References [3] Controlling High Bandwidth Aggregates in the Network (Extended Version) Ratul Mahajan, Steven M.Bellovin, Sally Floyd, John Ioannidis, Vern Paxson, and Scott Shenker, 2001