(57)【特許請求の範囲】
【請求項１】
BGPネットワーク上で各ASから広報されるBGPメッセージに含まれる不正メッセージを検出するBGP不正メッセージ検出装置において、
BGPメッセージを抽出するメッセージ抽出手段と、
前記メッセージでアナウンスされる属性変動を検知する変動検知手段と、
前記属性変動が検知されたメッセージを変動後の属性値ごとにグループ分けする分類手段と、
前記グループごとに、複数のメッセージが共に経由する共有ASを検出する共有AS検出手段と、
前記検出された共有ASの識別情報を含む不正メッセージ通知を出力する不正メッセージ通知手段とを具備したことを特徴とするBGP不正メッセージ検出装置。
【請求項２】
BGP経路表を収集する手段と、
前記BGP経路表に基づいて、プレフィックスごとに各属性の初期値を検出する手段とを具備し、
前記変動検知手段は、BGP経路表を参照することでプレフィックスごとに各属性の初期値を把握し、過去に観測されたことのない新規なプレフィックスの属性値が初期値と同じであれば、これを属性変動として検知しないことを特徴とする請求項１に記載のBGP不正メッセージ検出装置。
【請求項３】
BGP経路表を収集する手段と、
前記BGP経路表に基づいて、属性ごとに各属性値を使用するAS数を集計する手段とを具備し、
前記変動検知手段は、前記BGP経路表において多くのASにより使用されている属性値への変動を属性変動として検知しないことを特徴とする請求項１に記載のBGP不正メッセージ検出装置。
【請求項４】
前記メッセージ抽出手段は、BGPルータからオンラインでメッセージを抽出することを特徴とする請求項１ないし３のいずれかに記載のBGP不正メッセージ検出装置。
【請求項５】
前記メッセージ抽出手段は、BGPルータからオフラインでメッセージを抽出することを特徴とする請求項１ないし３のいずれかに記載のBGP不正メッセージ検出装置。
【請求項６】
BGPネットワーク上で各ASから広報されるBGPメッセージに含まれる不正メッセージを検出するBGP不正メッセージ検出方法において、
BGPメッセージを抽出し、各メッセージでアナウンスされる属性変動を検知する手順、
前記属性変動が検知されたメッセージを変動後の属性値ごとにグループ分けする手順と、
前記グループごとに、複数のメッセージが共に経由する共有ASを検出し、その識別情報を含む不正メッセージ通知を出力する手順とを含むことを特徴とするBGP不正メッセージ検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、BGPネットワークにおいて、BGPメッセージで通知されるプレフィックス毎の属性変動の状況に基づいて不正メッセージや不正ASを検出する方法および装置に関する。
【背景技術】
【０００２】
異常検出はコンピューター・セキュリティーの分野で広く研究されてきた。非特許文献１，２には、コンピューター・セキュリティー分野における異常検出の技術が開示されている。非特許文献１は、過去に観測された異常時のトラヒックパターンから異常パターンを定義し、監視ネットワークにおいて同パターンのトラヒックが観測された場合に異常状態として検出する方法である。非特許文献２は、トラヒック量などの特徴量を用い、過去の統計的な特徴量に較べて現在の特徴量が一定の閾値を超えた場合を異常状態として検出する方法である。
【０００３】
非特許文献３は、非特許文献１，２に開示された検出法をBGPネットワークの異常検出に適応した手法である。非特許文献４は、BGPネットワークにおいて、経路ハイジャックの検出に特化した異常検出手法であり、BGPメッセージで通知されるプレフィックスの広報元ASの変化に着眼し、観測したプレフィックスの広報元ASが正常時から変化した場合を異常状態として検出する方法である。
【０００４】
しかしながら、非特許文献１に代表される従来技術では、過去に観測された異常時のトラヒックパターンから異常パターンが定義され、同パターンに一致するトラヒックが異常状態として検出される。実用例として、非特許文献３では、実BGPネットワークで観測された異常時の経路変動から６つの異常パターンが定義され、同パターンに一致する経路変動が検出される。しかしながら、本方法による異常検出は、予め定義されたパターンに一致する経路変動に限られるため、過去に観測されたことのない異常変動を検出できない。
【０００５】
非特許文献2では、トラヒック量などの過去の統計的な特徴量に較べて現在の特徴量が一定の閾値を超えた場合を異常状態として検出するので、正常時に較べて特徴量が大幅に乖離しない異常変動は検出できない。
【０００６】
非特許文献３では、プレフィックス毎の単位時間あたりのBGPメッセージ数やAS_PATH属性におけるASの出現回数などを用いて正常時との乖離度が計算され、一定の閾値を超えた場合が異常状態として検出される。しかしながら、本手法は特徴量に基づいた異常検出であるため、正常時と較べて特徴量が大幅に乖離しない異常変動は検出できない。また、仮に異常状態を検出できた場合でも、その原因となる不正メッセージを特定できない。
【０００７】
非特許文献４では、BGPメッセージで通知されるプレフィックスの広報元ASの変化に着眼し、その変化が検出される。本手法は、AS_PATH属性における広報元ASの変化が少ない点に着眼しているため、頻繁に変化する属性を対象とした場合には検出数が膨大となり、不正メッセージを容易に特定できない。
【０００８】
このような技術課題に対して、本発明の発明者等は、過去に観測されたことのない異常や、正常時と較べて特徴量が大幅には乖離しない異常を引き起こす不正メッセージを容易に特定するために、多数の広報元ASが同時に同じ不正属性値を広報する確率が低いことに注目し、BGPネットワークにおいて、プレフィックス毎の属性値の変動を分析し、少数の広報元ASが使用する属性値へ変動するBGPメッセージをBGP不正メッセージとして検出する方法および装置を発明し、特許出願（特許文献１）した。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２０１１−１８２０３０号公報
【非特許文献】
【００１０】
【非特許文献１】M. Roesch, Snort: Lightweight intrusion detection for networks, USENIX LISA Conference, 1999.
【非特許文献２】H.S. Javitz, and A. Valdes, The NIDES Statistical Component: Description and Justification, SRI International, 1993.
【非特許文献３】K. Zhang, A. Yen, X. Zhao, D. Massey, S. F. Wu, and L. Zhang, On detection of anomalous routing dynamics in BGP, IFIP-TC6 Networking, 2004.
【非特許文献４】J. Karlin, S. Forrest, and J. Rexford, Pretty Good BGP: Improving BGP by Cautiously Adopting Routes, ICNP, 2006.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
特許文献１では、BGPメッセージの広報元が不正メッセージを公報した場合には、これを検知できる。しかしながら、公報されたBGPメッセージが経由するAS（以下、経由ASと表現する場合もある）において、当該BGPメッセージに不正属性が追加されて不正メッセージ化されても、これを検知することができない場合があった。
【００１２】
本発明の目的は、上記した従来技術の課題を解決し、公報されたBGPメッセージに対して、その経由ASにおいて不正属性が追加され、不正メッセージ化されても、これを確実に検知できるBGP不正メッセージ検出方法および装置を提供することにある。
【課題を解決するための手段】
【００１３】
上記の目的を達成するために、本発明は、BGPネットワーク上で各ASから広報されるBGPメッセージに含まれる不正メッセージを検出するBGP不正メッセージ検出装置において、以下のような手段を講じた点に特徴がある。
【００１４】
(1)BGPの経路更新を広報するメッセージを抽出するメッセージ抽出手段と、前記メッセージでアナウンスされる属性変動を検知する変動検知手段と、前記属性変動が検知されたメッセージを変動後の属性値ごとにグループ分けする分類手段と、前記グループごとに、複数のメッセージが共に経由する共有ASを検出する共有AS検出手段と、前記検出された共有ASの識別情報を含む不正メッセージ通知を出力する不正メッセージ通知手段とを具備した。
【００１５】
(2)BGP経路表を収集する手段と、BGP経路表に基づいて、プレフィックスごとに各属性の初期値を検出する手段とを更に設け、変動検知手段は、BGP経路表を参照することでプレフィックスごとに各属性の初期値を把握し、過去に観測されたことのない新規なプレフィックスの属性値が初期値と同じであれば、これを属性変動として検知しないようにした。
【００１６】
(3)BGP経路表を収集する手段と、BGP経路表に基づいて、属性ごとに各属性値を使用するAS数を集計する手段とを更に設け、変動検知手段は、BGP経路表において多くのASにより使用されている属性値への変動を属性変動として検知しないようにした。
【発明の効果】
【００１７】
本発明によれば、以下のような効果が達成される。
【００１８】
(1)同一の属性変動を広報する複数のBGPメッセージが共に経由する共有ASを検出し、このような共有ASが不正属性を追加した不正ASと推定されるようにしたので、正常なメッセージに対して経由ASにより不正属性が追加された場合にも、これを確実に検知できるようになる。
【００１９】
(2)BGP経路表を参照することでプレフィックスごとに各属性の初期値を把握し、過去に観測されたことのない新規なプレフィックスのメッセージであっても、その変動後の属性値が初期値と同じであれば、この属性変動は除外されるので、過去に観測されたことのないプレフィックスの属性値が全て不正な属性変動の候補として抽出されてしまうことを防止できる。
【００２０】
(5)BGPメッセージで広報される属性変動の属性値をBGP経路表と照合し、変動後の属性値を使用しているAS数が多い場合には、この属性変動を不正候補から除外するようにしたので、少数の正規メッセージが不正メッセージ候補とされる誤検出を防止できるようになる。
【図面の簡単な説明】
【００２１】
【図１】本発明の一実施形態に係るBGP不正メッセージ検出装置のブロック図である。
【図２】BGP不正メッセージ検出装置の他の実施形態のブロック図である。
【図３】本発明が適用されるBGPネットワークの構成を示したブロック図である。
【図４】本発明の第１実施形態に係る計算サーバの機能ブロック図である。
【図５】本発明の第１実施形態の動作を示したフローチャートである。
【図６】属性変動の抽出結果の一例を模式的に表現した図である。
【図７】変動後属性値を使用するAS数の一覧を示した図である。
【図８】変動後属性値に基づくグループ分けの一例を示した図である。
【図９】本発明が適用されるBGPネットワークの構成を示したブロック図である。
【図１０】変動後属性値に基づくグループ分けの一例を示した図である。
【図１１】本発明の第２実施形態に係る計算サーバの機能ブロック図である。
【図１２】本発明の第３実施形態に係る計算サーバの機能ブロック図である。
【図１３】AS数の集計結果の一例を示した図である。
【図１４】不正メッセージの推定方法を模式的に表現した図である。
【図１５】不正メッセージの抽出例を示した図である。
【発明を実施するための形態】
【００２２】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明の一実施形態に係るBGP不正メッセージ検出装置の構成を示したブロック図であり、BGPネットワーク（インターネット）に所属する管理下のBGPルータ（後述するAS20）から境界ルータRを中継して収集されたBGPメッセージおよびBGP経路表を取得し、不正メッセージおよびその広報元として疑わしいASをプレフィックスごとに検出する計算サーバ１と、前記検出結果を表示する表示装置２とを主要な構成としている。
【００２３】
前記ネットワークと計算サーバ１とは、図１に示したようにオンラインで接続されていても良いし、あるいは図２に示した他の実施形態のように、オフラインであってもよい。この場合、管理下のBGPルータにより収集されたBGPメッセージやBGP経路表のログデータは、ディスク状の記録媒体３や可搬性の半導体メモリ４を仲介して計算サーバ１に取り込まれる。
【００２４】
図３は、本発明が適用されるBGPネットワークの構成を示したブロック図であり、前記と同一の符号は同一または同等部分を表している。本実施形態では、ネットワークを構成する７つのAS（AS10〜AS70）に着目し、AS30が不正メッセージの広報元たる経由ASである場合を例にして説明する。
【００２５】
[実施形態１]
【００２６】
図４は、本発明の第１実施形態に係る計算サーバ１の機能ブロック図であり、ここでは本発明の説明に不要な構成は図示が省略されている。
【００２７】
メッセージ抽出部１０１は、BGPルータAS20により観測・収集されているBGPメッセージの中から、BGPの経路更新を広報するANNOUNCEメッセージを抽出する。変動検知部１０２において、属性値抽出部１０２ａは、前記メッセージに記述されている各変動属性の属性値をプレフィックス毎に抽出する。変動抽出部１０２ｂは、前後に観測されたANNOUNCEメッセージに記述されている各変動属性の属性値（変動後）をプレフィックス毎に比較することで属性値の変動を抽出する。
【００２８】
不正メッセージ検出部１０３において、分類部１０３ａは、属性変動が検知されたプレフィックスを変動後の属性値に応じて分類することで、各メッセージのエントリを変動後の属性値ごとにグループ分けする。共有AS検出部１０３ｂは、複数のエントリが登録されているグループごとに、各メッセージが共に経由するAS（共有AS）を検出し、このような共有ASを不正ASすなわち不正属性を追加したASと推定する。不正メッセージ通知部１０３ｃは、前記検出された共有ASの識別情報を含む不正メッセージ通知を出力する。
【００２９】
図５は、本実施形態の動作を示したフローチャートであり、主に計算サーバ１の動作を示している。ステップＳ１では、前記メッセージ抽出部１０１により、BGPルータAS20において観測・収集されている多数のBGPメッセージの中からANNOUNCEメッセージが抽出される。ステップＳ２では、各ANNOUNCEメッセージに付加情報として記述されている属性（パス属性）およびその属性値が前記属性値抽出部１０２ａにより抽出される。前記属性には、経路情報の生成元を示す"ORIGIN"、メッセージが通過するAS番号のリストを示す"AS_PATH"、トラヒックを転送すべきルータのアドレスを示す"NEXT_HOP"などがある。
【００３０】
ステップＳ３では、前記変動抽出部１０２ｂにおいて、前後に観測されてプレフィックスが同一のANNOUNCEメッセージに記述されている属性値を属性ごとに比較することで属性変動がプレフィックスごとに抽出される。このとき、過去に観測されたことのない新規なプレフィックスのANNOUNCEメッセージに記述されている属性は、全て変動として抽出される。
【００３１】
図６は、前記変動抽出部１０２ｂによりプレフィックス毎に抽出された属性変動の一例を模式的に表現した図であり、本実施形態では、属性値の変動が検知されるごとに、その観察日、観察時刻、経由するAS(AS_PATH)、プレフィックス（宛先のネットワークアドレス）、変動のあった属性（変動属性）および変動後の属性値が関連付けられてエントリされる。
【００３２】
図６において、「変動属性」が"NEXT_HOP"であって「属性値」が"10.0.0.0"のエントリは、あるプレフィックスに対応する"NEXT_HOP"属性の属性値が"10.0.0.0"に変化したことを意味する。同様に、「属性値」が"30.0.0.0"のエントリは、あるプレフィックスに対応する"NEXT_HOP"属性の属性値が"30.0.0.0"に変化したことを意味する。なお、各メッセージの広報元ASは、AS_PATH属性内で最も右側に位置するASとして検出できる。例えば、AS_PATHが[10 40]であれば、その広報元ASは「40」となり、経由ASは「10」となる。
【００３３】
図５へ戻り、ステップＳ４では、各属性変動の特異性を判定するために、各エントリが変動後の属性値に応じて、前記分類部１０３ａによりグループ分けされる。図７は、前記グループ分けの一例を示した図であり、ここでは、同じ時間間隔（例えば1分間）で発生した属性変動後の属性値が同一であるエントリが同一グループに分類される。
【００３４】
本実施形態では、「変動属性」"NEXT_HOP"が「属性値」"10.0.0.1"に変動したことを広報する、送信元がAS40，AS50の２つのANNOUNCEメッセージのエントリがグループ１に分類され、「変動属性」"NEXT_HOP"が「属性値」"30.0.0.1"に変動したことを広報する、送信元がAS50，AS60の２つのANNOUNCEメッセージのエントリがグループ２に分類されている。なお、変動後の「属性値」が同じであってもメッセージの観測日時が異なるエントリは異なるグループに分類される。
【００３５】
ステップＳ５では、前記共有AS検出部１０３ｂにより、前記グループごとに各エントリのメッセージが同一のASを経由しているか否か、すなわち共有ASを有するか否かが検出され、この検出結果に基づいて不正メッセージが推定される。
【００３６】
本実施形態では、図８に示したように、グループ１では経由ASに関する２つの集合の積｛AS10 AS40｝∩｛AS30 AS50｝が空集合となり、共有ASが存在しないので不正候補から除外される。これに対して、グループ２では経由ASに関する２つの集合の積｛AS30 AS50｝∩｛AS30 AS60｝がAS30となるので、このAS30が不正属性を追加した不正ASと推定される。ステップＳ６では、前記不正AS30および当該エントリに既登録の情報の記述された不正メッセージ通知が、前記不正メッセージ通知部１０３ｃから表示部２へ出力される。
【００３７】
本実施形態によれば、属性変動を広報するBGPメッセージが抽出され、同一の属性変動を広報する複数のBGPメッセージが共に経由する共有ASが、不正属性を追加した不正ASと推定されるので、正常なメッセージに対して経由ASにより不正属性が追加された場合にも、これを検知できるようになる。
【００３８】
なお、上記の実施形態では、経由ASが不正である場合を例にして説明したが、本発明はこれのみに限定されるものではなく、図９に一例を示したように、メッセージの公報元AS40が不正の場合も同様に検出できる。
【００３９】
公報元AS40が不正であると、図１０に示したような２つのANNOUNCEメッセージのエントリが同一グループに分類される。すなわち、公報元AS40からAS10を経由してAS20に到着したメッセージでは、"NEXT_HOP"を"40.0.0.1"に変える更新がアナウンスされ、また送信元AS40からAS70を経由してAS20に到着したメッセージでは、"NEXT_HOP"を"40.0.0.1"に変える更新がアナウンスされる。
【００４０】
ここで、各エントリの経由ASに関する２つの集合の積｛AS10 AS40｝∩｛AS70 AS40｝はAS40となるので、当該共有AS40が不正ASと推定される。
[実施形態２]
【００４１】
上記の第１実施形態では、過去に観測されたことのないプレフィックスのANNOUNCEメッセージに記述されている属性が全て変動として抽出されるので、正規のメッセージも不正メッセージ候補と誤認される場合があった。そこで、本発明の第２実施形態では、BGP経路表を参照することでプレフィックスごとに各属性の初期値を把握し、過去に観測されたことのない新規なプレフィックスのANNOUNCEメッセージであっても、その属性値が初期値と同じであれば除外され、属性変動として抽出されないようにしている。
【００４２】
図１１は、本発明の第２実施形態に係る計算サーバ１の機能ブロック図であり、前記と同一の符号は同一または同等部分を表しているので、その説明は省略する。
【００４３】
経路表抽出部１０４は、BGPルータAS20により収集されているBGP経路表を抽出する。初期値検出部１０５は、前記抽出されたBGP経路表に基づいて、プレフィックスごとに各属性の初期値を検出する。前記変動検知部１０２の変動絞込部１０２ｃは、過去に観測されたことのない新規なプレフィックスであるとして前記変動抽出部１０２ｂにより抽出された属性変動が前記BGP経路表に初期値として登録されているか否かを判定する。そして、未登録であれば、その属性変動としての扱いを維持する一方、既登録であれば除外することで前記属性変動を絞り込む。
【００４４】
本実施形態によれば、過去に観測されたことのない新規なプレフィックスのメッセージであっても、その変動後の属性値が初期値と同じであれば、この属性変動は除外されるので、過去に観測されたことのないプレフィックスの属性値が全て不正な属性変動の候補として抽出されてしまうことを防止できる。
[実施形態３]
【００４５】
上記の第１実施形態では、過去に観測されたことのないプレフィックスのANNOUNCEメッセージに記述されている属性が全て変動として抽出されるので、例えば多くのASにより使用されている属性値に変動したプレフィックスのように、正規の属性変動を広報するメッセージまでもが不正メッセージ候補と誤認される場合があった。そこで、本発明の第３実施形態では、BGP経路情報を予め集計することで属性ごとに各属性値を使用するAS数を把握し、BGP経路表において多くのASにより使用されている属性値に関しては、これを不正な属性変動と判定しないようにしている。
【００４６】
図１２は、本発明の第３実施形態に係る計算サーバ１の機能ブロック図であり、前記と同一の符号は同一または同等部分を表しているので、その説明は省略する。  
【００４７】
初期値検出部１０５において、集計部１０５ａは、前記抽出されたBGP経路表の初期値に基づいて、属性ごとに各属性値を使用するAS数を集計する。前記変動絞込部１０２ｃは、属性ごとに経路表の中でも多くのASにより使用されている属性値に変動しているエントリについては、属性変動の対象から除外することで前記属性変動を絞り込む。
【００４８】
図１３は、前記AS数の集計結果の一例を模式的に表現した図であり、この例では、「属性」"NEXT_HOP"の「属性値」として"4.4.4.4"を利用するAS数（度数）が44,444であり、"2.2.2.2"を利用するAS数が22,222であることを示している。
【００４９】
前記変動絞込部１０２ｃは、図１４に一例を示したように、属性変動を広報するメッセージのエントリ（ここでは、４つ）と、前記属性ごとに各属性値を使用するAS数とを照合して不正メッセージ候補の広報元ASを推定する。本実施形態では、「変動属性」"NEXT_HOP"の属性値"2.2.2.2"および"4.4.4.4"は、多数のASにより使用されていることがBGP経路表から明らかなのに対して、属性値"3.3.3.3"を使用しているASは存在しないので、図１５に示したように、変動後の属性値が"3.3.3.3"であるエントリのみが、不正判定の対象として抽出される。
【００５０】
本実施形態によれば、BGPメッセージで広報される属性変動の属性値をBGP経路表と照合し、変動後の属性値を使用しているAS数が多い場合には、この属性変動を不正候補から除外するようにしたので、少数の正規メッセージが不正メッセージ候補とされる誤検出を防止できるようになる。
【符号の説明】
【００５１】
１…計算サーバ，２…表示装置，１０１…メッセージ抽出部，１０２…変動検知部，１０２ａ…属性値抽出部，１０２ｂ…変動抽出部，１０２ｃ…変動絞込部，１０３…不正メッセージ検出部，１０３ａ…分類部，１０３ｂ…共有AS検出部，１０３ｃ…不正メッセージ通知部，１０４…経路表抽出部，１０５…初期値検出部，１０５ａ…集計部
【図１】
0005774970.tif 000002
【図２】
0005774970.tif 000003
【図３】
0005774970.tif 000004
【図４】
0005774970.tif 000005
【図５】
0005774970.tif 000006
【図６】
0005774970.tif 000007
【図７】
0005774970.tif 000008
【図８】
0005774970.tif 000009
【図９】
0005774970.tif 000010
【図１０】
0005774970.tif 000011
【図１１】
0005774970.tif 000012
【図１２】
0005774970.tif 000013
【図１３】
0005774970.tif 000014
【図１４】
0005774970.tif 000015
【図１５】
0005774970.tif 000016