説明

BGP不正メッセージ検出方法および装置

【課題】BGPの不正メッセージおよび不正ASを容易に検出できるBGP不正メッセージ検出方法および装置を提供する。
【解決手段】BGPのANNOUNCEメッセージを抽出するメッセージ抽出部101と、メッセージでアナウンスされた属性変動を検知する変動検知部102と、属性変動が検知されたメッセージを当該属性変動ごとにグループ分けする分類部103aと、前記グループごとに、複数のメッセージが共に経由する共有ASを検出する共有AS検出部103bと、検出された共有ASの識別情報を含む不正メッセージ通知を出力する不正メッセージ通知部103cとを含む。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、BGPネットワークにおいて、BGPメッセージで通知されるプレフィックス毎の属性変動の状況に基づいて不正メッセージや不正ASを検出する方法および装置に関する。
【背景技術】
【0002】
異常検出はコンピューター・セキュリティーの分野で広く研究されてきた。非特許文献1,2には、コンピューター・セキュリティー分野における異常検出の技術が開示されている。非特許文献1は、過去に観測された異常時のトラヒックパターンから異常パターンを定義し、監視ネットワークにおいて同パターンのトラヒックが観測された場合に異常状態として検出する方法である。非特許文献2は、トラヒック量などの特徴量を用い、過去の統計的な特徴量に較べて現在の特徴量が一定の閾値を超えた場合を異常状態として検出する方法である。
【0003】
非特許文献3は、非特許文献1,2に開示された検出法をBGPネットワークの異常検出に適応した手法である。非特許文献4は、BGPネットワークにおいて、経路ハイジャックの検出に特化した異常検出手法であり、BGPメッセージで通知されるプレフィックスの広報元ASの変化に着眼し、観測したプレフィックスの広報元ASが正常時から変化した場合を異常状態として検出する方法である。
【0004】
しかしながら、非特許文献1に代表される従来技術では、過去に観測された異常時のトラヒックパターンから異常パターンが定義され、同パターンに一致するトラヒックが異常状態として検出される。実用例として、非特許文献3では、実BGPネットワークで観測された異常時の経路変動から6つの異常パターンが定義され、同パターンに一致する経路変動が検出される。しかしながら、本方法による異常検出は、予め定義されたパターンに一致する経路変動に限られるため、過去に観測されたことのない異常変動を検出できない。
【0005】
非特許文献2では、トラヒック量などの過去の統計的な特徴量に較べて現在の特徴量が一定の閾値を超えた場合を異常状態として検出するので、正常時に較べて特徴量が大幅に乖離しない異常変動は検出できない。
【0006】
非特許文献3では、プレフィックス毎の単位時間あたりのBGPメッセージ数やAS_PATH属性におけるASの出現回数などを用いて正常時との乖離度が計算され、一定の閾値を超えた場合が異常状態として検出される。しかしながら、本手法は特徴量に基づいた異常検出であるため、正常時と較べて特徴量が大幅に乖離しない異常変動は検出できない。また、仮に異常状態を検出できた場合でも、その原因となる不正メッセージを特定できない。
【0007】
非特許文献4では、BGPメッセージで通知されるプレフィックスの広報元ASの変化に着眼し、その変化が検出される。本手法は、AS_PATH属性における広報元ASの変化が少ない点に着眼しているため、頻繁に変化する属性を対象とした場合には検出数が膨大となり、不正メッセージを容易に特定できない。
【0008】
このような技術課題に対して、本発明の発明者等は、過去に観測されたことのない異常や、正常時と較べて特徴量が大幅には乖離しない異常を引き起こす不正メッセージを容易に特定するために、多数の広報元ASが同時に同じ不正属性値を広報する確率が低いことに注目し、BGPネットワークにおいて、プレフィックス毎の属性値の変動を分析し、少数の広報元ASが使用する属性値へ変動するBGPメッセージをBGP不正メッセージとして検出する方法および装置を発明し、特許出願(特許文献1)した。
【先行技術文献】
【特許文献】
【0009】
【特許文献1】特開2011−182030号公報
【非特許文献】
【0010】
【非特許文献1】M. Roesch, Snort: Lightweight intrusion detection for networks, USENIX LISA Conference, 1999.
【非特許文献2】H.S. Javitz, and A. Valdes, The NIDES Statistical Component: Description and Justification, SRI International, 1993.
【非特許文献3】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.
【非特許文献4】J. Karlin, S. Forrest, and J. Rexford, Pretty Good BGP: Improving BGP by Cautiously Adopting Routes, ICNP, 2006.
【発明の概要】
【発明が解決しようとする課題】
【0011】
特許文献1では、BGPメッセージの広報元が不正メッセージを公報した場合には、これを検知できる。しかしながら、公報されたBGPメッセージが経由するAS(以下、経由ASと表現する場合もある)において、当該BGPメッセージに不正属性が追加されて不正メッセージ化されても、これを検知することができない場合があった。
【0012】
本発明の目的は、上記した従来技術の課題を解決し、公報されたBGPメッセージに対して、その経由ASにおいて不正属性が追加され、不正メッセージ化されても、これを確実に検知できるBGP不正メッセージ検出方法および装置を提供することにある。
【課題を解決するための手段】
【0013】
上記の目的を達成するために、本発明は、BGPネットワーク上で各ASから広報されるBGPメッセージに含まれる不正メッセージを検出するBGP不正メッセージ検出装置において、以下のような手段を講じた点に特徴がある。
【0014】
(1)BGPの経路更新を広報するメッセージを抽出するメッセージ抽出手段と、前記メッセージでアナウンスされる属性変動を検知する変動検知手段と、前記属性変動が検知されたメッセージを変動後の属性値ごとにグループ分けする分類手段と、前記グループごとに、複数のメッセージが共に経由する共有ASを検出する共有AS検出手段と、前記検出された共有ASの識別情報を含む不正メッセージ通知を出力する不正メッセージ通知手段とを具備した。
【0015】
(2)BGP経路表を収集する手段と、BGP経路表に基づいて、プレフィックスごとに各属性の初期値を検出する手段とを更に設け、変動検知手段は、BGP経路表を参照することでプレフィックスごとに各属性の初期値を把握し、過去に観測されたことのない新規なプレフィックスの属性値が初期値と同じであれば、これを属性変動として検知しないようにした。
【0016】
(3)BGP経路表を収集する手段と、BGP経路表に基づいて、属性ごとに各属性値を使用するAS数を集計する手段とを更に設け、変動検知手段は、BGP経路表において多くのASにより使用されている属性値への変動を属性変動として検知しないようにした。
【発明の効果】
【0017】
本発明によれば、以下のような効果が達成される。
【0018】
(1)同一の属性変動を広報する複数のBGPメッセージが共に経由する共有ASを検出し、このような共有ASが不正属性を追加した不正ASと推定されるようにしたので、正常なメッセージに対して経由ASにより不正属性が追加された場合にも、これを確実に検知できるようになる。
【0019】
(2)BGP経路表を参照することでプレフィックスごとに各属性の初期値を把握し、過去に観測されたことのない新規なプレフィックスのメッセージであっても、その変動後の属性値が初期値と同じであれば、この属性変動は除外されるので、過去に観測されたことのないプレフィックスの属性値が全て不正な属性変動の候補として抽出されてしまうことを防止できる。
【0020】
(5)BGPメッセージで広報される属性変動の属性値をBGP経路表と照合し、変動後の属性値を使用しているAS数が多い場合には、この属性変動を不正候補から除外するようにしたので、少数の正規メッセージが不正メッセージ候補とされる誤検出を防止できるようになる。
【図面の簡単な説明】
【0021】
【図1】本発明の一実施形態に係るBGP不正メッセージ検出装置のブロック図である。
【図2】BGP不正メッセージ検出装置の他の実施形態のブロック図である。
【図3】本発明が適用されるBGPネットワークの構成を示したブロック図である。
【図4】本発明の第1実施形態に係る計算サーバの機能ブロック図である。
【図5】本発明の第1実施形態の動作を示したフローチャートである。
【図6】属性変動の抽出結果の一例を模式的に表現した図である。
【図7】変動後属性値を使用するAS数の一覧を示した図である。
【図8】変動後属性値に基づくグループ分けの一例を示した図である。
【図9】本発明が適用されるBGPネットワークの構成を示したブロック図である。
【図10】変動後属性値に基づくグループ分けの一例を示した図である。
【図11】本発明の第2実施形態に係る計算サーバの機能ブロック図である。
【図12】本発明の第3実施形態に係る計算サーバの機能ブロック図である。
【図13】AS数の集計結果の一例を示した図である。
【図14】不正メッセージの推定方法を模式的に表現した図である。
【図15】不正メッセージの抽出例を示した図である。
【発明を実施するための形態】
【0022】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図1は、本発明の一実施形態に係るBGP不正メッセージ検出装置の構成を示したブロック図であり、BGPネットワーク(インターネット)に所属する管理下のBGPルータ(後述するAS20)から境界ルータRを中継して収集されたBGPメッセージおよびBGP経路表を取得し、不正メッセージおよびその広報元として疑わしいASをプレフィックスごとに検出する計算サーバ1と、前記検出結果を表示する表示装置2とを主要な構成としている。
【0023】
前記ネットワークと計算サーバ1とは、図1に示したようにオンラインで接続されていても良いし、あるいは図2に示した他の実施形態のように、オフラインであってもよい。この場合、管理下のBGPルータにより収集されたBGPメッセージやBGP経路表のログデータは、ディスク状の記録媒体3や可搬性の半導体メモリ4を仲介して計算サーバ1に取り込まれる。
【0024】
図3は、本発明が適用されるBGPネットワークの構成を示したブロック図であり、前記と同一の符号は同一または同等部分を表している。本実施形態では、ネットワークを構成する7つのAS(AS10〜AS70)に着目し、AS30が不正メッセージの広報元たる経由ASである場合を例にして説明する。
【0025】
[実施形態1]
【0026】
図4は、本発明の第1実施形態に係る計算サーバ1の機能ブロック図であり、ここでは本発明の説明に不要な構成は図示が省略されている。
【0027】
メッセージ抽出部101は、BGPルータAS20により観測・収集されているBGPメッセージの中から、BGPの経路更新を広報するANNOUNCEメッセージを抽出する。変動検知部102において、属性値抽出部102aは、前記メッセージに記述されている各変動属性の属性値をプレフィックス毎に抽出する。変動抽出部102bは、前後に観測されたANNOUNCEメッセージに記述されている各変動属性の属性値(変動後)をプレフィックス毎に比較することで属性値の変動を抽出する。
【0028】
不正メッセージ検出部103において、分類部103aは、属性変動が検知されたプレフィックスを変動後の属性値に応じて分類することで、各メッセージのエントリを変動後の属性値ごとにグループ分けする。共有AS検出部103bは、複数のエントリが登録されているグループごとに、各メッセージが共に経由するAS(共有AS)を検出し、このような共有ASを不正ASすなわち不正属性を追加したASと推定する。不正メッセージ通知部103cは、前記検出された共有ASの識別情報を含む不正メッセージ通知を出力する。
【0029】
図5は、本実施形態の動作を示したフローチャートであり、主に計算サーバ1の動作を示している。ステップS1では、前記メッセージ抽出部101により、BGPルータAS20において観測・収集されている多数のBGPメッセージの中からANNOUNCEメッセージが抽出される。ステップS2では、各ANNOUNCEメッセージに付加情報として記述されている属性(パス属性)およびその属性値が前記属性値抽出部102aにより抽出される。前記属性には、経路情報の生成元を示す"ORIGIN"、メッセージが通過するAS番号のリストを示す"AS_PATH"、トラヒックを転送すべきルータのアドレスを示す"NEXT_HOP"などがある。
【0030】
ステップS3では、前記変動抽出部102bにおいて、前後に観測されてプレフィックスが同一のANNOUNCEメッセージに記述されている属性値を属性ごとに比較することで属性変動がプレフィックスごとに抽出される。このとき、過去に観測されたことのない新規なプレフィックスのANNOUNCEメッセージに記述されている属性は、全て変動として抽出される。
【0031】
図6は、前記変動抽出部102bによりプレフィックス毎に抽出された属性変動の一例を模式的に表現した図であり、本実施形態では、属性値の変動が検知されるごとに、その観察日、観察時刻、経由するAS(AS_PATH)、プレフィックス(宛先のネットワークアドレス)、変動のあった属性(変動属性)および変動後の属性値が関連付けられてエントリされる。
【0032】
図6において、「変動属性」が"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」となる。
【0033】
図5へ戻り、ステップS4では、各属性変動の特異性を判定するために、各エントリが変動後の属性値に応じて、前記分類部103aによりグループ分けされる。図7は、前記グループ分けの一例を示した図であり、ここでは、同じ時間間隔(例えば1分間)で発生した属性変動後の属性値が同一であるエントリが同一グループに分類される。
【0034】
本実施形態では、「変動属性」"NEXT_HOP"が「属性値」"10.0.0.1"に変動したことを広報する、送信元がAS40,AS50の2つのANNOUNCEメッセージのエントリがグループ1に分類され、「変動属性」"NEXT_HOP"が「属性値」"30.0.0.1"に変動したことを広報する、送信元がAS50,AS60の2つのANNOUNCEメッセージのエントリがグループ2に分類されている。なお、変動後の「属性値」が同じであってもメッセージの観測日時が異なるエントリは異なるグループに分類される。
【0035】
ステップS5では、前記共有AS検出部103bにより、前記グループごとに各エントリのメッセージが同一のASを経由しているか否か、すなわち共有ASを有するか否かが検出され、この検出結果に基づいて不正メッセージが推定される。
【0036】
本実施形態では、図8に示したように、グループ1では経由ASに関する2つの集合の積{AS10 AS40}∩{AS30 AS50}が空集合となり、共有ASが存在しないので不正候補から除外される。これに対して、グループ2では経由ASに関する2つの集合の積{AS30 AS50}∩{AS30 AS60}がAS30となるので、このAS30が不正属性を追加した不正ASと推定される。ステップS6では、前記不正AS30および当該エントリに既登録の情報の記述された不正メッセージ通知が、前記不正メッセージ通知部103cから表示部2へ出力される。
【0037】
本実施形態によれば、属性変動を広報するBGPメッセージが抽出され、同一の属性変動を広報する複数のBGPメッセージが共に経由する共有ASが、不正属性を追加した不正ASと推定されるので、正常なメッセージに対して経由ASにより不正属性が追加された場合にも、これを検知できるようになる。
【0038】
なお、上記の実施形態では、経由ASが不正である場合を例にして説明したが、本発明はこれのみに限定されるものではなく、図9に一例を示したように、メッセージの公報元AS40が不正の場合も同様に検出できる。
【0039】
公報元AS40が不正であると、図10に示したような2つのANNOUNCEメッセージのエントリが同一グループに分類される。すなわち、公報元AS40からAS10を経由してAS20に到着したメッセージでは、"NEXT_HOP"を"40.0.0.1"に変える更新がアナウンスされ、また送信元AS40からAS70を経由してAS20に到着したメッセージでは、"NEXT_HOP"を"40.0.0.1"に変える更新がアナウンスされる。
【0040】
ここで、各エントリの経由ASに関する2つの集合の積{AS10 AS40}∩{AS70 AS40}はAS40となるので、当該共有AS40が不正ASと推定される。
[実施形態2]
【0041】
上記の第1実施形態では、過去に観測されたことのないプレフィックスのANNOUNCEメッセージに記述されている属性が全て変動として抽出されるので、正規のメッセージも不正メッセージ候補と誤認される場合があった。そこで、本発明の第2実施形態では、BGP経路表を参照することでプレフィックスごとに各属性の初期値を把握し、過去に観測されたことのない新規なプレフィックスのANNOUNCEメッセージであっても、その属性値が初期値と同じであれば除外され、属性変動として抽出されないようにしている。
【0042】
図11は、本発明の第2実施形態に係る計算サーバ1の機能ブロック図であり、前記と同一の符号は同一または同等部分を表しているので、その説明は省略する。
【0043】
経路表抽出部104は、BGPルータAS20により収集されているBGP経路表を抽出する。初期値検出部105は、前記抽出されたBGP経路表に基づいて、プレフィックスごとに各属性の初期値を検出する。前記変動検知部102の変動絞込部102cは、過去に観測されたことのない新規なプレフィックスであるとして前記変動抽出部102bにより抽出された属性変動が前記BGP経路表に初期値として登録されているか否かを判定する。そして、未登録であれば、その属性変動としての扱いを維持する一方、既登録であれば除外することで前記属性変動を絞り込む。
【0044】
本実施形態によれば、過去に観測されたことのない新規なプレフィックスのメッセージであっても、その変動後の属性値が初期値と同じであれば、この属性変動は除外されるので、過去に観測されたことのないプレフィックスの属性値が全て不正な属性変動の候補として抽出されてしまうことを防止できる。
[実施形態3]
【0045】
上記の第1実施形態では、過去に観測されたことのないプレフィックスのANNOUNCEメッセージに記述されている属性が全て変動として抽出されるので、例えば多くのASにより使用されている属性値に変動したプレフィックスのように、正規の属性変動を広報するメッセージまでもが不正メッセージ候補と誤認される場合があった。そこで、本発明の第3実施形態では、BGP経路情報を予め集計することで属性ごとに各属性値を使用するAS数を把握し、BGP経路表において多くのASにより使用されている属性値に関しては、これを不正な属性変動と判定しないようにしている。
【0046】
図12は、本発明の第3実施形態に係る計算サーバ1の機能ブロック図であり、前記と同一の符号は同一または同等部分を表しているので、その説明は省略する。
【0047】
初期値検出部105において、集計部105aは、前記抽出されたBGP経路表の初期値に基づいて、属性ごとに各属性値を使用するAS数を集計する。前記変動絞込部102cは、属性ごとに経路表の中でも多くのASにより使用されている属性値に変動しているエントリについては、属性変動の対象から除外することで前記属性変動を絞り込む。
【0048】
図13は、前記AS数の集計結果の一例を模式的に表現した図であり、この例では、「属性」"NEXT_HOP"の「属性値」として"4.4.4.4"を利用するAS数(度数)が44,444であり、"2.2.2.2"を利用するAS数が22,222であることを示している。
【0049】
前記変動絞込部102cは、図14に一例を示したように、属性変動を広報するメッセージのエントリ(ここでは、4つ)と、前記属性ごとに各属性値を使用するAS数とを照合して不正メッセージ候補の広報元ASを推定する。本実施形態では、「変動属性」"NEXT_HOP"の属性値"2.2.2.2"および"4.4.4.4"は、多数のASにより使用されていることがBGP経路表から明らかなのに対して、属性値"3.3.3.3"を使用しているASは存在しないので、図15に示したように、変動後の属性値が"3.3.3.3"であるエントリのみが、不正判定の対象として抽出される。
【0050】
本実施形態によれば、BGPメッセージで広報される属性変動の属性値をBGP経路表と照合し、変動後の属性値を使用しているAS数が多い場合には、この属性変動を不正候補から除外するようにしたので、少数の正規メッセージが不正メッセージ候補とされる誤検出を防止できるようになる。
【符号の説明】
【0051】
1…計算サーバ,2…表示装置,101…メッセージ抽出部,102…変動検知部,102a…属性値抽出部,102b…変動抽出部,102c…変動絞込部,103…不正メッセージ検出部,103a…分類部,103b…共有AS検出部,103c…不正メッセージ通知部,104…経路表抽出部,105…初期値検出部,105a…集計部

【特許請求の範囲】
【請求項1】
BGPネットワーク上で各ASから広報されるBGPメッセージに含まれる不正メッセージを検出するBGP不正メッセージ検出装置において、
BGPメッセージを抽出するメッセージ抽出手段と、
前記メッセージでアナウンスされる属性変動を検知する変動検知手段と、
前記属性変動が検知されたメッセージを変動後の属性値ごとにグループ分けする分類手段と、
前記グループごとに、複数のメッセージが共に経由する共有ASを検出する共有AS検出手段と、
前記検出された共有ASの識別情報を含む不正メッセージ通知を出力する不正メッセージ通知手段とを具備したことを特徴とするBGP不正メッセージ検出装置。
【請求項2】
BGP経路表を収集する手段と、
前記BGP経路表に基づいて、プレフィックスごとに各属性の初期値を検出する手段とを具備し、
前記変動検知手段は、BGP経路表を参照することでプレフィックスごとに各属性の初期値を把握し、過去に観測されたことのない新規なプレフィックスの属性値が初期値と同じであれば、これを属性変動として検知しないことを特徴とする請求項1に記載のBGP不正メッセージ検出装置。
【請求項3】
BGP経路表を収集する手段と、
前記BGP経路表に基づいて、属性ごとに各属性値を使用するAS数を集計する手段とを具備し、
前記変動検知手段は、前記BGP経路表において多くのASにより使用されている属性値への変動を属性変動として検知しないことを特徴とする請求項1に記載のBGP不正メッセージ検出装置。
【請求項4】
前記メッセージ抽出手段は、BGPルータからオンラインでメッセージを抽出することを特徴とする請求項1ないし3のいずれかに記載のBGP不正メッセージ検出装置。
【請求項5】
前記メッセージ抽出手段は、BGPルータからオフラインでメッセージを抽出することを特徴とする請求項1ないし3のいずれかに記載のBGP不正メッセージ検出装置。
【請求項6】
BGPネットワーク上で各ASから広報されるBGPメッセージに含まれる不正メッセージを検出するBGP不正メッセージ検出方法において、
BGPメッセージを抽出し、各メッセージでアナウンスされる属性変動を検知する手順、
前記属性変動が検知されたメッセージを変動後の属性値ごとにグループ分けする手順と、
前記グループごとに、複数のメッセージが共に経由する共有ASを検出し、その識別情報を含む不正メッセージ通知を出力する手順とを含むことを特徴とするBGP不正メッセージ検出方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate