(57)【特許請求の範囲】
【請求項１】
セキュリティルールＲの集合Ｓを記憶するように構成される電子デバイスにおいてセキュリティルールの衝突を管理するオンラインの方法であって、
ルールのそれぞれは、条件属性のリストＣと、少なくとも１つの対応する判断とを含み、
前記条件属性のリストは、ｍ個の個々の条件属性Ｃnをさらに備え、ｍ個の個々の条件属性Ｃnは、条件を設定するための対応する値の区間によって識別され、ここで、ｎは、ルールにおける異なる条件属性を識別する変数である
方法において、
前記方法は、前記電子デバイスによって実行される複数のステップとして、
‐ｍ≧１であると判断すると、ｍ個のノードレベルを備える衝突管理ツリーを取得する（２０１）ステップであって、
異なるレベルの前記ノードは、前記条件属性値の区間又は部分区間によってラベル付けされるアークによって互いに接続され、
前記ノードは、対応するノードにつながっている前記アークをラベル付けする前記区間又は前記部分区間によって設定された前記条件を満たす１つ又は複数のルールによって識別され、
前記衝突管理ツリーは、最後のノードレベルを起源とする前記アークの端部にリーフを有し、
リーフのそれぞれは、現在のリーフにつながっている前記アークをラベル付けする前記区間又は前記部分区間によって設定された前記条件を満たす１つ又は複数のルールによって識別され、
リーフのそれぞれは、前記少なくとも１つの対応する判断によってさらに識別され、
前記アークの少なくともいくつかは、条件を設定するための値の間隔の部分間隔によってラベル付けされる、
取得するステップと、
‐前記セキュリティルールの集合Ｓに追加されるべき新しいルールｒを受け取る（２０３）ステップと、
‐前記受け取った新しいルールに基づいて前記衝突管理ツリーをオンラインで更新する（２２９）ステップと
を含む、方法。
【請求項２】
前記更新することは、
ａ）変数Ｘを定義する（２２３）ことと、
ｂ）Ｘが
【数１】
0005154328.tif 000010
の値を取ることであって、ここで、∪は数学的演算の和集合を示し、∩は数学的演算の共通集合を示し、「現在のノードアークj」は、現在のノードからレベルｎ−１のノードへのアークｊの前記区間又は前記部分区間を示し、ここで、
【数２】
0005154328.tif 000011
は、前記条件属性Ｃnの前記区間又は前記部分区間に対応する前記和集合演算の集合であることと、
ｃ）Ｘの集合のそれぞれがただ１つのアークをラベル付けするのに使用されるように、レベルｎ−１のノードへのアークの形成に前記Ｘの集合を使用する（２２９）ことであって、
前記レベルｎ−１のノードは、前記対応するルールによって識別され、それによって、ノードのそれぞれが、対応するノードにつながっている前記アークをラベル付けする前記対応する集合によって設定された前記条件を満たす前記ルールによってのみ識別される、
使用することと
を含む、請求項１に記載の方法。
【請求項３】
前記更新することは、
ｄ）ｎ−１が０に等しいか否かを判断する（２３１）ことと、
ｅ）ｎ−１が０に等しい場合に、現在のノードの前記レベルｎ−１にリーフを追加する（２３３）ことであって、前記リーフは、対応するリーフにつながっている前記アークをラベル付けする前記集合の前記条件を満たす１つ又は複数のルールによって識別される、追加することと
をさらに含む、請求項２に記載の方法。
【請求項４】
前記更新することは、
ｆ）ｎ−１が０に等しくない場合、又は、ステップｅ）を実行した後に、現在のレベルｎのすべてのノードが処理されたか否かを判断する（２３５）と共に、処理されていない場合に、現在のレベルｎの前記すべてのノードが処理されるまで、ステップａ）〜ｄ）を繰り返すことと、
ｇ）ｎを１だけデクリメントし（２３９）、その後、ステップａ）〜ｆ）を繰り返すことと
をさらに含む、請求項３に記載の方法。
【請求項５】
前記ステップｄ）の判断は、レベルｎ＋１のすべてのノードをチェックすることと、
レベルｎ＋１を起源とするすべてのアークが処理されたことを検証することと
を含む、請求項３に記載の方法。
【請求項６】
同一のリーフに少なくとも２つのルールがあるか否かをチェックすることと、
同一のリーフに少なくとも２つのルールがある場合に、前記セキュリティルールの集合Ｓに少なくとも１つの構成ミスのアノマリがあると判断することと
をさらに含む、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
新しいルールが導入されるたびに、前記異なるアノマリに関して管理者に警告するためにコンソールが使用される、請求項６に記載の方法。
【請求項８】
前記電子デバイスを管理する管理者にアノマリに関して警告すること、及び／又は、
衝突の存在しないルールの集合を提供すること
をさらに含む、請求項６に記載の方法。
【請求項９】
衝突の存在しないルールの集合を提供することは、前記ルールの優先順序を考慮することと、リーフにおいて最も高い優先度を有する前記ルールを選ぶこととを含み、
前記対応する属性値は、ルートから開始して、現在のリーフにつながっている前記属性値を採用することによって取得される、
請求項８に記載の方法。
【請求項１０】
衝突の存在しないルールの集合を提供することは、
リーフのそれぞれにおいて、同じ判断を有する少なくとも１つの第１のルール及び第２のルールが存在するか否かを判断することと、
同じ判断を有する少なくとも１つの第１のルール及び第２のルールが存在する場合には、これらのルールから最も高い優先度を有するルールを選ぶことと
を含み、
前記最も高い優先度を有するルールが存在するリーフのすべてにおいて、前記最も高い優先度を有するルールと同じ判断を有する別のルールが存在する場合には、前記最も高い優先度を有するルールは完全に冗長なものとして検出され、
前記対応する属性値は、ルートから開始して、現在のリーフにつながっている前記属性値を採用することによって取得される、
請求項８に記載の方法。
【請求項１１】
ｍが０に等しい場合に、前記衝突管理ツリーを更新することは、ｌ個のノードレベルを備える衝突管理ツリーを構築することを含み、ｌは、前記ルールｒの条件属性の個数を示し、
異なるレベルの前記ノードは、前記条件属性値の区間又は部分区間によってラベル付けされるアークによって互いに接続され、
前記ノードは、前記対応するノードにつながっている前記アークをラベル付けする前記区間又は前記部分区間によって設定された前記条件を満たす１つ又は複数のルールによって特徴付けられ、
前記衝突管理ツリーは、最後のノードレベルを起源とする前記アークの端部にリーフを有し、
リーフのそれぞれは、現在のリーフにつながっている前記アークをラベル付けする前記区間又は前記部分区間によって設定された前記条件を満たす１つ又は複数のルールによって識別され、
リーフのそれぞれは、対応する判断（複数可）によってさらに識別される、
請求項１〜１０のいずれか一項に記載の方法。
【請求項１２】
コンピュータプログラム製品であって、電子デバイスのコンピュータ手段にロードされて実行されると、請求項１〜１１のいずれか一項に記載の方法におけるすべてのステップを実装するための命令を含む、コンピュータプログラム製品。
【請求項１３】
通信システムにおいてセキュリティルールの衝突をオンラインで管理することが可能な電子デバイスであって、
前記電子デバイスは、セキュリティルールＲiの集合Ｓを記憶するように構成され、
ルールのそれぞれは、条件属性のリストＣと、対応する少なくとも１つの判断とを備え、
前記条件属性のリストは、ｍ個の個々の条件属性Ｃnをさらに備え、ｍ個の個々の条件属性Ｃnは、条件を設定するための対応する値の区間によって識別され、ここで、ｎは、ルールにおける異なる条件属性を識別する変数である
電子デバイスにおいて、
前記電子デバイスは、
‐ｍ≧１の場合に、ｍ個のノードレベルを備える衝突管理ツリーを取得する手段であって、
異なるレベルの前記ノードは、前記条件属性値の区間又は部分区間によってラベル付けされるアークによって互いに接続され、
前記ノードは、対応するノードにつながっている前記アークをラベル付けする前記区間又は前記部分区間によって設定された前記条件を満たす１つ又は複数のルールによって識別され、
前記衝突管理ツリーは、最後のノードレベルを起源とする前記アークの端部にリーフを有し、
リーフのそれぞれは、現在のリーフにつながっている前記アークをラベル付けする前記区間又は前記部分区間によって設定された前記条件を満たす１つ又は複数のルールによって識別され、
リーフのそれぞれは、さらに、対応する判断（複数可）によっても識別され、
前記ツリーにおいて、前記アークの少なくともいくつかは、条件を設定するための値の間隔の部分間隔によってラベル付けされる、
取得する手段と、
‐前記セキュリティルールの集合Ｓに追加されるべき新しいルールを受け取る受け取りユニットと、
‐前記受け取った新しいルールに基づいて前記衝突管理ツリーをオンラインで更新する更新ユニットと
を備える、電子デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
［技術分野］
本発明は、既存の衝突管理ツリーを更新するために、または新たな衝突管理ツリーを構築するために、新たなアクセス制御ルールが追加される場合において、アクセス制御ルールの集合に存在する様々なアノマリ（anomaly）を検出するために使用することができる衝突管理方法に関する。このようなアクセス制御ルールは、たとえば、着信トラフィック及び発信トラフィックをフィルタリングするためのファイアウォール等の電子デバイス、ファイルアクセスを管理するためのオペレーティングシステム、侵入検知のための攻撃シグネチャデータベース、ルールを管理するための電子メールアプリケーション、又は産業メカニズムにおいて使用することができる。本発明は、同様に、このような電子デバイス及びこの方法を実施するように構成されたコンピュータプログラムに関する。
【０００２】
［発明の背景］
通信システムで実施されている現在のセキュリティメカニズムは、パケットをフィルタリングする作業に多くのルールが指定されるアクセス制御システムでこの作業を行うために、多数の技法を使用する。侵入検知システムも、ルールの集合を使用して、監視されるネットワークから捕捉された異なるフローを、ルールの集合に記載された現在の既知の攻撃と照合する。ルールを記述する作業は、アクセス制御目的の場合もあれば、侵入検知の目的の場合もあるが、困難な作業ではない。しかしながら、多数のルールの集合を取り扱い、テストされていないルールがあるか否か、又は冗長な他のルールがあるか否かを発見することは、特に、一連の管理者によって記述された非常に多くのルールを取り扱う時に容易な作業ではない。
【０００３】
セキュリティルールは、セキュリティポリシーの仕様を満たすように、注意深く記述されると共にうまく編成されるべきである。これは、一人のオペレータが解決することができる容易な作業ではないので、この問題を克服するために、新規且つ高速で自動的な方法が導入されるべきである。さらに、管理者には、構成ミスのタイプ及びそのような構成ミスにつながったルールの集合に関しての正確な情報が与えられるべきである。
【０００４】
多くの現在の企業、政府機関、学究機関、及び軍事機関は、自身の情報システムを安全にするためにコンポーネントの集合を使用する。ファイアウォールは、組織内の異なる信頼のゾーンをトラバースするトラフィックをフィルタリングして取り締まるために最も多く使用されているセキュリティ設備である。たとえば、インターネットは、信頼されないゾーンとみなされ、インターネットに対するすべての着信トラフィック及び発信トラフィックは、攻撃を防止するために適切なフィルタリングルールで制御されるべきである。
【０００５】
ファイアウォールは、トラフィックをフィルタリングして、組織内で考えられる様々なゾーンをトラバースするフローを制御するための強力な解決策を提供するが、定義されたセキュリティポリシーによるファイアウォールの適切な構成は、依然として困難な作業のままである。ターゲットのセキュリティポリシーに従って正しいルールを扱うことを困難にする理由には、様々な理由がある。第１に、当該組織の異なるサブ組織（異なるロケーション、国、及び大陸に位置するもの）には異なるファイアウォール（または他のセキュリティ設備の一部）がインストールされている場合がある。第２に、時と共に異なる管理者によって記述されている可能性のある数百又は数千のルールが、異なるファイアウォールで指定されている。最後に、ルールを追加又は削除することによって新しいセキュリティポリシーに従い様々なルールを更新することによって、管理者の作業はほとんど実行不可能になる。これらの理由のすべてから、管理者が、記述された様々なルールの検証、解析、及び修正を行うことを助けるための効率的な技法が導入されるべきである。
【０００６】
ファイアウォールの構成ミスの問題の解決を試みる様々なシステムがある。これらのシステムは、異なるアノマリを検出するために異なる方法を使用するが、これらのアノマリを検出するのにほぼ同じ問題を共有している。
【０００７】
Ehab S. Al-Shaer及びHazem H. Hamed著「Discovery of Policy Anomalies in Distributed Firewalls」（IEEE INFOCOM 2004）と題する刊行物は、アノマリを検出する方法を開示しているが、この方法は、オペレータによって提示されるすべてのルールを検討するときに存在し得るすべてのアノマリを検出するとは限らない。その理由は、その検出手法が、ルールを２つずつ比較することに基づいているためである。
【０００８】
１つの条件属性ｄＩＰ（宛先ＩＰ（destination IP））しか有しない以下の説明例を考えることができる。
Ｒ1：ｄＩＰ∈［４０−９０］→受理
Ｒ2：ｄＩＰ∈［８０−１２０］→拒否
Ｒ3：ｄＩＰ∈［５０−１１０］→受理
【０００９】
上記ルール集合では、ｄＩＰは、宛先のインターネットプロトコル（ＩＰ）アドレスを示している。この場合、提案される方法は、ルールＲ1及びＲ2の和集合のために、ルールＲ3が完全にシャドウイングしていること（complete shadowing）を検出しない。あるルールがマッチするすべてのパケットに対して、より高い優先順位を有する前のルール又はルールの組み合わせがすでにマッチしたという理由で、当該ルールが決して適用されない、そのようなルールが少なくとも１つ存在する場合、ルール集合は、完全なシャドウイングアノマリを含むことになる。
【００１０】
F. Cuppens、N. Cuppens-Boulahia、及びJ. Garcia-Alfaro著「Detection and Removal of Firewall Misconfiguration」（IASTED International Conference on Communication, Network and Information Security (CNIS 2005)）と題する刊行物は、上記問題を解決する別の解決法を開示しているが、この方法も、多くの欠点を有する。冗長性についての曖昧な定義が導入されている。実際には、同じ属性値を有する２つのルールが存在する場合に、最初のルールが冗長なルールとみなされ、３つ以上の同一のルールが存在する場合も同様である。この理由から、この欠点を抑制するために、シャドウイングの検出は、冗長性より前に検討される。しかしながら、（１）或るルールが、そのルールと同じ判断を有する、より低い優先度を有する１つ又は２つ以上のルールから成る集合よりも高い優先順位を有し、且つ、（２）最初のルールがマッチするすべてのパケットが、他のルール（複数可）の組み合わせによってもマッチされ、且つ、（３）最初のルールの条件属性値が、より低い優先度を有するルールの条件属性値に厳密に含まれる場合には、最初のルールは冗長なものとして検出される。これに加えて、或るルール集合が検討され、それらのルールが再配列される場合、いくつかのアノマリが、最初のルール集合では検出される一方、２番目のルール集合では検出されない場合があり、また、その逆の場合もある。以下のルール集合は、これらの２つの問題を示す一例である。
Ｒ1：ｄＩＰ∈［２０−９０］→受理
Ｒ2：ｄＩＰ∈［４０−１２０］→拒否
Ｒ3：ｄＩＰ∈［１０−５５］→受理
Ｒ4：ｄＩＰ∈［３０−１１０］→受理
【００１１】
この例では、ルールＲ1は、ルールＲ3及びＲ4の組み合わせに起因して冗長なルールとして検出される。しかしながら、ルールＲ1及びＲ3の順序が、以下に提示するように変更された場合でも、Ｒ1が下記リストから削除された場合にはフィルタリングの結果は変化しないので、Ｒ1は実際には冗長なものであっても、冗長なルールとしては検出されない。
Ｒ3：ｄＩＰ∈［１０−５５］→受理
Ｒ2：ｄＩＰ∈［４０−１２０］→拒否
Ｒ1：ｄＩＰ∈［２０−９０］→受理
Ｒ4：ｄＩＰ∈［３０−１１０］→受理
【００１２】
この状況は、その手法の曖昧さに起因するものである。その手法は、冗長性の実際の定義を検討するのではなく、異なるアルゴリズムを先に採用する。これに加えて、異なるルールの実行順序は、オリジナルのルール集合に従って維持されない。
【００１３】
管理者がセキュリティルールの集合をすでに有しているが、既存の集合に新しいルールを追加しなければならない場合に、特別な問題が生じる。この作業は、ルール集合をオンラインで更新しなければならず、衝突も同様にオンラインで検出しなければならない場合に、さらに困難となる。オンライン更新は、ルールを任意の時刻に追加することができることを意味する。たとえば、刊行物「Detection and Removal of Firewall Misconfiguration」に記載されているアルゴリズムがオンライン検出に適用される場合、最終的な結果は、このアルゴリズムをオフラインで適用したときの結果と同じでない場合がある。これは、定義の曖昧さに起因するものである。さらに、オンラインで導入される新しい各ルールに関して、様々なアルゴリズムが、すべてのルールにわたって適用されるべきである。しかしながら、これは多くの時間を要する。したがって、その方法は、時間消費及び変化する結果というこれらの２つの主な欠点のために、オンラインでのアノマリ検出には適切ではない。加えて、その方法は、すべてのルールを保存する記憶保持（memory keeping）機能を有しない。オンラインでの衝突管理は、管理者が新しいルールを導入する限り、起こり得るすべてのアノマリの検出をステップバイステップで可能にする革新的な方法である。新しいルールが１つ導入されるごとに、管理者は、構成ミスがあれば、その構成ミスに関しての警告を直接受ける。したがって、構成ミス検出をオンラインで行うとき、この方法は、新しいルールが１つ追加されるたびに開始される。
【００１４】
２００３年４月４日のE. Al-Shaer及びH. Hamed著「Firewall policy advisor for anomaly discovery and rule editing」（XP-002463654, Multimedia Networking Research Laboratory School of Computer Science, Telecommunications and Information Systems, DePaul University, Chicago USA）と題する科学刊行物は、レガシーファイアウォールにおけるルールの衝突及び潜在的な問題を明らかにするための、ファイアウォールポリシーによるアノマリの自動発見、並びに、ルールの挿入、削除、及び変更のためのアノマリのないポリシー編集を提供する一組の技法及びアルゴリズムを開示している。
【００１５】
E. AL-Shaer他著「Conflict classification and analysis of distributed firewall policies」（IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, vol. 23, No. 10, October 2005）と題する科学刊行物は、集中型ファイアウォール及び分散ファイアウォールにおいてポリシーアノマリを自動的に発見するための一組の技法及びアルゴリズムを開示している。
【００１６】
米国特許出願公開第２００６／０２９４５７７号公報は、異なるファイアウォールデザイン間の不一致を解決する、システム、コンピュータで実施可能な方法、及びコンピュータ使用可能媒体を開示している。
【００１７】
したがって、セキュリティルールの衝突を検出して管理する、改良されたオンラインの方法が必要とされている。
【００１８】
［発明の概要］
本発明の第１の態様によれば、請求項１に記載される衝突を管理するオンラインの方法が提案される。すなわち、セキュリティルールＲの集合Ｓを記憶するように構成される電子デバイスにおいてセキュリティルールの衝突を管理するオンラインの方法であって、
ルールのそれぞれは、条件属性のリストＣと、少なくとも１つの対応する判断とを含み、
前記条件属性のリストは、ｍ個の個々の条件属性Ｃnをさらに備え、ｍ個の個々の条件属性Ｃnは、条件を設定するための対応する値の区間によって識別され、ここで、ｎは、ルールにおける異なる条件属性を識別する変数である
方法において、
前記方法は、前記電子デバイスによって実行される複数のステップとして、
‐ｍ≧１であると判断すると、ｍ個のノードレベルを備える衝突管理ツリーを取得する（２０１）ステップであって、
異なるレベルの前記ノードは、前記条件属性値の区間又は部分区間によってラベル付けされるアークによって互いに接続され、
前記ノードは、対応するノードにつながっている前記アークをラベル付けする前記区間又は前記部分区間によって設定された前記条件を満たす１つ又は複数のルールによって識別され、
前記衝突管理ツリーは、最後のノードレベルを起源とする前記アークの端部にリーフを有し、
リーフのそれぞれは、現在のリーフにつながっている前記アークをラベル付けする前記区間又は前記部分区間によって設定された前記条件を満たす１つ又は複数のルールによって識別され、
リーフのそれぞれは、前記少なくとも１つの対応する判断によってさらに識別され、
前記アークの少なくともいくつかは、条件を設定するための値の間隔の部分間隔によってラベル付けされる、
取得するステップと、
‐前記セキュリティルールの集合Ｓに追加されるべき新しいルールｒを受け取る（２０３）ステップと、
‐前記受け取った新しいルールに基づいて前記衝突管理ツリーをオンラインで更新する（２２９）ステップと
を含む、方法である。
【００１９】
提案される発明は、検討されているフィルタリング設備をトラバースするインバウンドトラフィック及びアウトバウンドトラフィックをフィルタリングするために管理者によって指定された異なるセキュリティルール（または、オペレーティングシステムにおけるアクセス権を考慮する場合、アクセス権）の起こり得るすべての構成ミスを見つけることができる新規の方法を導入する。このメカニズムには、他の解決法と比較すると、多くの利点がある。提案される方法は、ルールの再配列（すなわちルールの優先度）に依存しない。この方法は、冗長性、シャドウイング等の、すべての起こり得るアノマリを見つける。異なるアノマリを、管理者に正確に提示することもできる。したがって、アノマリの一因となったすべてのルール及びそれらの属性範囲値を、さらなる調査のために、管理者に正確に示すことができる。したがって、ネットワークエレメントの管理者は、すべての構成ミスに関して警告を受けることができ、アプリオリに定義されたポリシーに従って、エラーの存在しない最良のルール集合を選ぶのは、管理者次第である。また、この方法が、管理者の選択に従って、エラーの存在しない１つの可能なルール集合を自動的に与えるように、この方法をアプリオリに調整することも可能である。
【００２０】
提案される方法は、「ルール記憶保持（rules memory keeping）」の利点も有する。この方法は、すべての構成ミスのアノマリ及び可能性を見つけるだけでなく、同時に、オリジナルのルール集合を、後に説明するようなそのデータ構造体に保持する。さらに、この方法は、ルールの更新に対して不変である。対応するアノマリが存在しない最終的なルール集合を盲目的に与える他の方法とは異なり、本提案の方法は、異なるアノマリを見つけながら、オリジナルのルール集合を保持する。本提案の方法は、ルールの順序にかかわらず同じ結果を与え、すべてのアノマリが見つけられるのに対して、他の方法は、生成される最後のルール及び追加又は省略される新規のルールに依存する。さらに、本提案の方法によって、ルール集合をオンラインで更新することが可能になる。したがって、管理者は、新たなルールを導入している間に、彼のコンソールの前ですべてのアノマリについて警告を受けることができる。
【００２１】
本発明の第２の態様によれば、検出された衝突を管理することができる電子デバイスのコンピュータ手段にロードされて実行されると、第１の態様による方法を実施するための命令を含むコンピュータプログラム製品がさらに提供される。
【００２２】
本発明の第３の態様によれば、請求項１３に記載の衝突を管理することが可能なネットワーク要素が提供される。すなわち、通信システムにおいてセキュリティルールの衝突をオンラインで管理することが可能な電子デバイスであって、
前記電子デバイスは、セキュリティルールＲiの集合Ｓを記憶するように構成され、
ルールのそれぞれは、条件属性のリストＣと、対応する少なくとも１つの判断とを備え、
前記条件属性のリストは、ｍ個の個々の条件属性Ｃnをさらに備え、ｍ個の個々の条件属性Ｃnは、条件を設定するための対応する値の区間によって識別され、ここで、ｎは、ルールにおける異なる条件属性を識別する変数である
電子デバイスにおいて、
前記電子デバイスは、
‐ｍ≧１の場合に、ｍ個のノードレベルを備える衝突管理ツリーを取得する手段であって、
異なるレベルの前記ノードは、前記条件属性値の区間又は部分区間によってラベル付けされるアークによって互いに接続され、
前記ノードは、対応するノードにつながっている前記アークをラベル付けする前記区間又は前記部分区間によって設定された前記条件を満たす１つ又は複数のルールによって識別され、
前記衝突管理ツリーは、最後のノードレベルを起源とする前記アークの端部にリーフを有し、
リーフのそれぞれは、現在のリーフにつながっている前記アークをラベル付けする前記区間又は前記部分区間によって設定された前記条件を満たす１つ又は複数のルールによって識別され、
リーフのそれぞれは、さらに、対応する判断（複数可）によっても識別され、
前記ツリーにおいて、前記アークの少なくともいくつかは、条件を設定するための値の間隔の部分間隔によってラベル付けされる、
取得する手段と、
‐前記セキュリティルールの集合Ｓに追加されるべき新しいルールを受け取る受け取りユニットと、
‐前記受け取った新しいルールに基づいて前記衝突管理ツリーをオンラインで更新する更新ユニットと
を備える、電子デバイスである。
【００２３】
本発明の他の特徴及び利点は、添付図面を参照して、非限定的な例示の実施形態の以下の説明から明らかになる。
【００２４】
［発明の実施形態の詳細な説明］
次に、添付図面を関して、本発明のいくつかの実施形態をより詳細に説明する。以下の説明では、本発明の実施形態は、インターネットプロトコル（ＩＰ）を使用する通信システムの文脈で説明される。しかしながら、本発明は、ＩＰの使用に決して限定されるものではない。
【００２５】
本発明は、フィルタリング設備の内部の論理デバイス又は物理デバイスにおいて実施することができる。この設備の唯一の条件は、この設備が、いくつかの条件が満たされたときに適用される、対応する動作又は判断を提供するルールの集合を使用するということである。これらのデバイスの例は、シグネチャデータベースで収集されたルールの集合を使用するハードウェアファイアウォール、ソフトウェアファイアウォール（ｎｅｔｆｉｌｔｅｒ、ｉｐｆｉｌｔｅｒ等）、侵入検知／防止システム（ｓｎｏｒｔ、ｄｒａｇｏｎ等）である。さらに、この技法は、新たなルールが追加される際、たとえば新たな電子メールの送受信のフォワーディングにおいて、サービス品質（ＱｏＳ）管理ツール、ルータ（ルーティング表管理、ボーダゲートウェイプロトコル集約等）、光ネットワークユニット（ＯＮＵ）、光ライン終端装置（ＯＬＴ）、ギガビットイーサネット（登録商標）受動光ネットワーク（ＧｅＰＯＮ）、マイクロソフト・アウトルックのようなメッセージングサーバおよびクライアントツール等の、他の非セキュリティ設備に一般化することができる。また、本発明は、新しい世代のネットワークにも役立つ。実際には、本発明は、現在のボイスオーバーＩＰ（ＶｏＩＰ）ネットワークで重要性が大きくなったセッションボーダコントローラ（ＳＢＣ）及びアプリケーションレイヤゲートウェイ（ＡＬＧ）の衝突構成に使用されるように推奨される。
【００２６】
当該技術分野で行われた関連する研究は、ルールの集合におけるいくつかのアノマリを検出することにのみ焦点を当ててきたが、本発明は、ファイアウォールの構成ミスだけでなく、ｓｎｏｒｔのルール等の侵入検知ルール、Ｗｉｎｄｏｗｓ（登録商標）、Ｌｉｎｕｘ、Ｕｎｉｘ（登録商標）等の異なるオペレーティングシステム（ＯＳ）におけるファイル（又はディレクトリ）アクセス制御、メッセージングサーバおよび／またはクライアント、産業メカニズム、及びオートメーションにも適用される。以下の詳細な説明では、本発明がより詳細に説明され、ファイアウォールルールが本発明の適用性を効率的に示すことから、本発明の様々なプロシージャが、これらのルールの集合に適用される。
【００２７】
ソフトウェアデバイス又はハードウェアデバイスのいずれかである現在の多くのセキュリティ設備の部分品は、主として、表１に紹介されるルールのようなルールの集合によって構成されている。一般に、各ルールは、属性値の集合に従って、受理、拒否、アラート、ログ等の判断を提供する。ファイアウォールフィルタリング機能の場合、これらの属性は、異なるＩＰパケットヘッダフィールドに関連付けることができる。しかしながら、この属性リストは、侵入検知におけるルールを扱う亜倍に、セッション開始プロトコル（ＳＩＰ）またはＩＰペイロードコンテンツを含む現在のＶｏＩＰプロトコル等のアプリケーションプロトコルに関連付けることもできる他の特徴に拡張可能である。簡単にするために、以下の説明では、いくつかのＩＰヘッダフィールドのみが検討され、たとえば、プロトコル（Ｐ）（たとえば、伝送制御プロトコル、ユーザデータグラムプロトコル、インターネット制御メッセージプロトコル等）、送信元ＩＰアドレス（ｓＩＰ）、宛先ＩＰアドレス（ｄＩＰ）、送信元ポート（ｓＰ）、宛先ポート（ｄＰ）等のみが検討される。異なる条件属性が満たすべき唯一の条件は、それらの条件属性が取り得る値が有限集合又は有限区間に属するということである。
【００２８】
以下では、ある文法が提供される。この文法は、異なる複数のルールのそれぞれに関して、対応する判断（複数可）を実現するために、ある一組の条件が満たされるべきであるということを説明するのに使用される。単一のルールのグローバルシンタックスは、以下のように定義することができる。
Ｒi：<条件（複数）> ： <判断（複数）>
<条件（複数）> → 条件∧<条件（複数）>／条件
<判断（複数）> → 判断 <ＯＰ> <判断（複数）>／判断
<ＯＰ>→∧／∨／…
【００２９】
このシンタックスでは、ＯＰは、オペランドを示し、∧は、ＡＮＤ演算を示し、∨は、ＯＲ演算を示す。「条件」端子は、属性が或る集合に属するか否かに関してその属性が検査される際の任意の条件とすることができる。この集合は、単一の集合に対応してもよく、多くの集合の共通集合に対応してもよく、異なる集合の和集合に対応してもよく、及び／又は、他の任意の演算集合に対応してもよい。「判断」端子は、ファイアウォール等のルールを管理するエレメントが適用することができる、「拒否」、「受理」、「ログ」等の任意の動作に対応する。この集合は、離散値（「ｔｃｐ」、「ｕｄｐ」、「ａ」、「ｂ」、「ｌｅｆｔ」、「ｒｉｇｈｔ」、「ｕｐ」、「ｄｏｗｎ」、「１」、「２」、「
【００３０】
【数１】
0005154328.tif 000002
【００３１】
」、「
【００３２】
【数２】
0005154328.tif 000003
【００３３】
」、「Paris」、「London」、「read」、「write」、「execute」等）、及び／又は、連続値（区間［−３０；５０００］、［２０．３６；５６２］等）を含むことができる。しかしながら、これらの集合又は区間は有限であるべきである。
【００３４】
【表１】
0005154328.tif 000004
【００３５】
上記に提示したグローバルシンタックスから、表１の例に関してのフィルタリングルールシンタックスは、
<条件（複数）> → <Ｐ> ∧ <ＳＩＰ> ∧ <ＳＰ> ∧ <ＤＩＰ> ∧ <ＤＰ>
<判断> → 受理／拒否
となる。
【００３６】
表記∧は、論理ＡＮＤ演算を意味する。表１では、５つの条件属性（略して属性）のみが提示されている。すなわち、Ｐ、ｓＩＰ、ｓＰ、ｄＩＰ、及びｄＰのみが提示されている。
【００３７】
オンラインルール更新方法を示すために、種々のルール及び対応する判断を、衝突管理ツリーの形態として提示する。図１は、このようなツリーの一例を示している。この図から分かるように、ツリーは、ノード、アーク、及びリーフという３つのコンポーネントを含む。第１に、各ノードは１つの条件属性に対応し、たとえば、ｓＩＰはこの例での１つの条件属性である。第２に、各アークは、１つの条件属性値、又は、値の１つの範囲でラベル付けされる。最後に、リーフは、カップル、すなわち、ルール番号及びその対応する判断に対応する。リーフは、特別なノードとみなすことができる。異なるルールは、或るリーフに到達するまで、ルールの条件属性値及びノード値に基づいてツリーを上から下にトラバースすることによって読み出すことができる。或るリーフに到達すると、２つの場合が起こり得る。衝突ツリーのルートからリーフへトラバースされるアークの値に従って、１つのカップルしか存在しないか、又は、少なくとも２つのカップルが存在する。前者の場合、対応するルールにはアノマリが存在しない。後者は、ルールのアノマリ又は衝突を示している。この後者の場合、異なるルール間の衝突が、検査されたリーフに存在する。
【００３８】
次に、図２ａおよび図２ｂのフローチャートを参照して、オンラインでルールを更新する方法を説明する。ステップ２０１において、衝突管理ツリーＴがルール集合Ｓに対応して定義される。このルール集合は異なる複数のルールＲを含む。各ルールはｍ個の条件属性を有する。ツリーＴは、衝突ツリーを構成するためのアルゴリズムが適用されるルール集合に対応する。ステップ２０３において、新しいルールｒが、ファイルアクセス制御のために、管理者、又は、ユーザ等の他の任意のエージェントによって提供され、その後、本提案のアルゴリズムは、新しいルールｒを追加した後の新しいルール集合に存在するすべての異なるアノマリを検出する。これは、新しい衝突ツリーが、前のルールの集合及び新しい追加されたルールｒを含めて構成されるべきであることを意味する。追加される新しいルールｒは、ｍ個の条件属性を備える。ここで、ｍは正の整数である。
【００３９】
新しいルールｒが、ステップ２０５において検査される。これは、ｒがいずれかの条件属性を実際に含んでいるか否か、すなわち、ｒが空でないかが判断されることを意味する。ｒがいずれの条件属性も含んでいない場合、ステップ２０７において、値「失敗」を取る単一のノードが返される。この後、このプロシージャは終了することができる。
【００４０】
他方、ステップ２０５において、ｒが条件属性を確かに含んでいると判断された場合、ステップ２０９において、Ｔが空であるか否かが判断される。Ｔが空であることは、すなわち、既存の衝突管理ツリーがなく、追加されたルールｒがたとえば管理者によって導入された最初のルールに対応することを意味する。Ｔが空である場合、ステップ２１１において、新しい衝突管理ツリーが作成される。作成されたツリーは存在する条件属性と同数のノードを含み、各ノードは対応する条件属性で識別される。さらに、これらの異なる複数のノードが、対応する条件属性値でラベル付けされるアークを通じて互いに接続される。最後の条件属性値の端部（すなわちｎ＝１）にリーフがある。リーフは、特別なノードとみなすことができる。リーフは、ルールｒ及びその対応する判断（複数可）で識別される。このステップの後、プロシージャは終了することができる。
【００４１】
図３は、新しいルール、すなわち、「Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−１２０］∧ｄＰ∈［２１−８０］→受理」が追加され、既存のツリーがないときに、構成された衝突管理ツリーの一例を示している。図から分かるように、与えられたルールｒには５つの条件属性があるため、対応する条件属性及びルールｒによって識別される５つのノードがある。さらに、ノードはアークによって互いにリンクされ、各アークは、対応する条件属性値でラベル付けされ又は識別される。最後のノードの後に、判断「受理」で識別されたリーフがある。
【００４２】
一方、ステップ２０９において、Ｔが空でないと判断された場合、すなわち、既存の衝突管理ツリーがあると判断された場合、ステップ２１３において、現在のノードは、レベルｎのルートノード、すなわち、既存の衝突管理ツリーの最初のノードであると定義される。ｎは、変数であり、異なるノードレベルを示す。このレベルにおいて、ｎはｍに等しい。換言すれば、所与のルール集合Ｓを検討するとき、最初の条件属性値に対応するノードは、ルートノードとみなすことができる。次に、ステップ２１５において、ルールｒが、レベルｎの現在のノードに追加される。各ノードレベルは、１つの条件属性に対応する。したがって、ｍ個の異なるノードレベルがあり、最後のレベルの後に、レベル０に対応するリーフがある。各ノードレベルは、いくつかの並列な子ノードを有する場合があることに留意すべきである。子ノードは、アークによって父ノード又は現在のノードに接続されたノードであると定義される。
【００４３】
次に、ステップ２１７において、条件属性のリストＣが検査される。換言すれば、条件属性のリストＣが空であるか否かが判断される。空である場合、ステップ２１９において、取得された衝突ツリーが返され、このプロシージャは終了する。条件属性のリストＣが空でない場合、このプロシージャは、ステップ２２１において、ＣnをＣのｎ番目の属性であるとして定義することによって続行される。次に、ステップ２２３において、変数Ｘが定義される。
【００４４】
ステップ２２５において、この変数には、
【００４５】
【数３】
0005154328.tif 000005
【００４６】
の値が与えられる。すなわち、以下の集合の和集合が与えられる。
【００４７】
【数４】
0005154328.tif 000006
【００４８】
ここで、ｒ［Ｃn］は、新しいルールｒのレベルｎの条件属性の値に対応する。図３に与えた例では、ｒ［Ｃ2］＝ｒ［ｄＩＰ］＝［１−１２０］である。
【００４９】
【数５】
0005154328.tif 000007
【００５０】
は、レベルｎの現在処理されているノードからレベルｎ−１のノードに向かうすべての値の和集合演算を示す。たとえば、図１及びレベル１の属性（すなわち、属性ｄＰ）を考え、さらに、そのレベルにおける２番目のノード、すなわち、Ｒ1、Ｒ2、及びＲ3が存在するノードを考える場合、結果は、
【００５１】
【数６】
0005154328.tif 000008
【００５２】
となる。次に、ステップ２２７において、Ｘの現在の値が返される。値Ｘは、ステップ２２５において定義されたような集合で構成される。
【００５３】
次に、ステップ２２９において、ステップ２２５において説明したような集合が使用されて、現在のノードからレベルｎ−１の新しいノードへのアークが構築され、これらのアークは、これらの異なる集合でラベル付けされるようになる。したがって、現在のノードからレベルｎ−１のノードに向かうアークは、集合の個数と同数存在する。レベルｎ−１のノードは、対応するルールでさらに識別され、それによって、各ノードは、対応するノードにつながっているアークをラベル付けする対応する集合によって設定された条件を満たすルールによってのみ識別される。集合は条件属性の値又はこれらの値の部分範囲に対応することに留意されたい。
【００５４】
次に、ステップ２３１において、ｎ−１の値が、０に等しいか否かを判断することによって検査される。０に等しい場合、ステップ２２９において作成された（新しいアークに対応する）レベルｎ−１の「ノード」が、リーフとして返される。返された各リーフは、対応するカップル（Ｒi，Ｄi）の値を取る。ここで、Ｒiは現在のノードの残りのルールに対応し、Ｄiは対応する判断（複数可）に対応する。サブインデックスｉは、異なるルール及び判断を識別するのに使用される。各リーフは、現在のリーフにつながっているアークをラベル付けする集合の条件を満たす１つ又は複数のルールによって識別される。現在のリーフに衝突がない場合には、１つのカップルのみが返されるのに対して、衝突がある場合には、少なくとも２つのカップルが返される。
【００５５】
ステップ２３１において行われた検査に対する応答が否定的である場合、このプロシージャは、ステップ２３５において、現在の条件属性Ｃnに関して、すなわち等価的にレベルｎに関して、すべてのノードが処理されたか否かを判断することによって続行される。これは、集合に対応するノードが常に存在するため、直前のレベル、すなわちレベルｎ＋１のすべてのノードをチェックすると共に、すべての集合が処理されたことを検証することによって行われる。集合は、ステップ２２５において定義されたもの、すなわち、和集合を取得するための集合である。これは、等価的に、直前のレベルのノード（複数可）からのすべてのアークが処理されたことをチェックすることとして表すことができる。すべてのノードが処理されていない場合には、ステップ２３７において、次のノードが検討され、次に、このプロシージャはステップ２２３で続行される。このループは、すべてのノードが処理されている間続行される。
【００５６】
他方、ステップ２３５において、現在のレベルｎに関して、すべてのノードが処理されていると判断された場合、このプロシージャは、ステップ２３９において、現在のノードＣnをＣから削除することによって続行される。すなわち、ｎは、値ｎ−１を取る。ステップ２３９から、このプロシージャは、ステップ２１７に直接戻る。
【００５７】
図２ａ及び図２ｂのフローチャートを参照して説明したようなオンライン衝突検出方法を示すために、図１に示す衝突管理ツリーを検討する。新しいルールとしての以下のルールが追加されるものと見なす。
Ｒ4：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−２００］∧ｄＰ∈［１−１３９］→受理
【００５８】
最初の３つの条件属性は、既存のルール集合の最初の３つの条件属性と比較して変更されていないことに留意されるべきである。したがって、このアルゴリズムの実行は、４番目の属性から開始して示される。最初の３つのステップは、図４で分かるように、この最後のルールのみを４つのレベルのノード（５、４、３、及び２）に追加する。ここで、最初の３つのノードは、ルールＲ1、Ｒ2、Ｒ3によってラベル付けされるだけでなく、Ｒ4によってもラベル付けされる。
【００５９】
２番目（ｎ＝２）の条件属性はｄＩＰである。ステップ２２５及び２２７を実行することによって、集合［６１−１２０］によってラベル付けされるアークは、２つの集合、すなわち、集合［６１−６９］及び［７０−１２０］に分割される。ステップ２２５及び２２７は、以下の説明では、パーティショニングプロシージャ（partitioning procedure）と呼ばれる。図４は、このステップが実行された後の衝突管理ツリーの状態を示している。
【００６０】
１番目（ｎ＝１）の条件属性はｄＰである。このステージでパーティショニングプロシージャを適用することによって、上記ツリーの最後の２つのｄＩＰノードから出るアークは、図５に示すように、それぞれ４つのアーク及び３つのアークに分割される。
【００６１】
最後に、ｎ−１＝０のときには、検査する条件属性がない。５つの条件属性のすべてが検査されている。したがって、図６に示すように、各アークについて１つのリーフが返される。リーフのそれぞれは、ルール番号及びその対応する判断から成る残りのカップルを含む。或る単一のリーフが２つ以上のルールを含む場合、これは、アノマリ又は衝突の表示である。図において、破線の輪郭線を有するリーフは、アノマリの表示である。
【００６２】
図６に示され、本オンライン衝突検出方法によって生成されるような衝突ツリーから追い出すことができる種々のアノマリを見つけ出そうとするとき、ツリーから直接、次のことに気づくことができる。すなわち、２つ以上のルールがあるリーフのそれぞれについて部分的シャドウイングを１つカウントすると、７つの部分的シャドウイングアノマリがあることに気づくことができる。また、破線のリーフのうち左から２番目のもののように、３つのルールがあって、より低い優先度を有するそのうちの２つのルールがシャドウイングされている場合に、各ルールを別々に考えると、９つの部分的シャドウイングがあることに気づくことができる。部分的シャドウイングは、以下のように定義することができる。Ｓをフィルタリングルールの集合とする。この場合、Ｓ内において、決して適用されないルールＲiの少なくとも一部が存在する場合、またその場合に限り、Ｒは部分的シャドウイングを示す。これは、このルールのその部分がマッチするすべてのパケットが、より高い優先度を有する前のルールの少なくとも一部によって事前にマッチされるということに起因する。図６において、７つの部分的シャドウイングアノマリは、次の通りである。
【００６３】
‐第１の部分的シャドウイング｛Ｒ1，Ｒ2｝：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−３０］∧ｄＰ∈［２１−２５］→｛Ｒ1：受理，Ｒ2：拒否｝。使用される優先度がファーストマッチである場合、すなわち、Ｒ1が、最も高い優先度を有する場合、衝突ツリーによって検出されるように、Ｒ1及びＲ2が同時にマッチするパケットは、Ｒ2の判断（拒否）の代わりにＲ1の判断（受理）を常に取り、逆の場合も同じである。これと同じ部分的シャドウイングアノマリは、ルールＲ1、Ｒ2、及びＲ3の以下の部分に関して発生する。
‐第２の部分的シャドウイング｛Ｒ1，Ｒ2，Ｒ3｝：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［３１−６０］∧ｄＰ∈［２１−２５］→｛Ｒ1：受理，Ｒ2：拒否，Ｒ3：拒否｝。この場合、２つの部分的シャドウイングアノマリを考えることができる。第１の部分的シャドウイングアノマリは、Ｒ1によってシャドウイングされるＲ2の部分的シャドウイングアノマリである。第２の部分的シャドウイングアノマリは、Ｒ3の部分的シャドウイングアノマリである。
‐第３の部分的シャドウイング｛Ｒ1，Ｒ3｝：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［３１−６０］∧ｄＰ∈［２６−８０］→｛Ｒ1：受理，Ｒ3：拒否｝。
‐第４の部分的シャドウイング｛Ｒ1，Ｒ3｝：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［６１−６９］∧ｄＰ∈［２１−８０］→｛Ｒ1：受理，Ｒ3：拒否｝。
‐第５の部分的シャドウイング｛Ｒ1，Ｒ3，Ｒ4｝：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−１２０］∧ｄＰ∈［２１−８０］→｛Ｒ1：受理，Ｒ3：拒否，Ｒ4：受理｝。
‐第６の部分的シャドウイング｛Ｒ3，Ｒ4｝：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−１２０］∧ｄＰ∈［８１−１３９］→｛Ｒ3：受理，Ｒ4：受理｝。
‐第７の部分的シャドウイング｛Ｒ3，Ｒ4｝：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１２１−２００］∧ｄＰ∈［２１−１３９］→｛Ｒ3：拒否，Ｒ4：受理｝。
【００６４】
本明細書で提案される２つの解決法が管理者に提供される。第１の解決法は、種々のアノマリに関して管理者に通知することにある。これは、図６のようにツリーを描くことによって、又は、衝突ツリーのルートからリーフへの種々のパスを管理者に与えることによって、又は、上記で説明したような部分的シャドウイングアノマリを管理者に与えることのみによって、行われる。
【００６５】
第２の解決法は、自動判断を行うことにあり、アノマリを自動的に削除することによって、管理者には、これらのアノマリの存在しない適切なルールが提供される。第２の技法は、おそらくアクセス制御ルールに関して十分な知識若しくはファイルアクセス権を有しない初心者の管理者若しくはユーザ、又は、本発明を適用することができる他の任意の分野からの初心者の管理者若しくはユーザにとって特に有用である。
【００６６】
第２の解決法によれば、アノマリの存在しないルールの集合を提供するによって、結果が自動化される。一態様では、この解決法は、ルールの優先順序付けを考慮することを含む。したがって、あるルールＲiが、ルールＲjよりも高い優先度のために順序が最初である場合には、Ｒiが、その衝突に対応するパスのルールとして選ばれる。したがって、この解決法は、管理者によって提供された最初のルール集合のマッチング順序と同じマッチング順序を維持する。これに加えて、決して適用されない種々の属性値が、最初のルール集合から削除される。この解決法は、管理者への警告に加え、オプションとして考えられる。
【００６７】
ルール集合には、生成されたその対応する衝突ツリーが、カップル（すなわち、ルール及びその対応する判断（複数可））を２つ以上有するリーフを含まない場合に、アノマリが存在しない。たとえば、図７に示すツリーには、いかなるアノマリもが存在しない。このツリーは、各リーフにおいて、最も高い優先度を有するルールを選択することによって生成される。衝突は、より高い優先度を有するルールの方を選んで選ばれるため、管理者の判断を考慮することなく直接の決定を行うことができる。
【００６８】
したがって、管理者（又はユーザ若しくは他の任意のエージェント）には、アノマリの存在しない以下のルールの集合が自動的に提供される。
Ｒ1：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−１２０］∧ｄＰ∈［２１−８０］→受理；
Ｒ2'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−６０］∧ｄＰ∈［１０−２０］→拒否；
Ｒ31'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［３１−１２０］∧ｄＰ∈［８１−６５５３５］→拒否；
Ｒ33'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１２１−２００］∧ｄＰ∈［２１−６５５３５］→拒否；及び
Ｒ4'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−２００］∧ｄＰ∈［１−２０］→受理。
【００６９】
衝突管理ツリーから生成されたルールは、完全に互いに素(disjoint)であり、アノマリが存在しない。それらのルールは互いに素であるため、それらの実行の結果は、異なる複数のルールの順序を変更しても同じである。上記に与えた例では、Ｒiは変更されていない。実際には、Ｒiは、以下のようにして衝突ツリーから生成される。
Ｒ11：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−３０］∧ｄＰ∈［２１−２５］→受理；
Ｒ12：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−３０］∧ｄＰ∈［２６−８０］→受理；
Ｒ13：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［３１−６０］∧ｄＰ∈［２１−２５］→受理；
Ｒ14：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［３１−６０］∧ｄＰ∈［２６−８０］→受理；
Ｒ15：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［６１−６９］∧ｄＰ∈［２１−８０］→受理；及び
Ｒ16：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−１２０］∧ｄＰ∈［２１−８０］→受理。
【００７０】
次に、このルール集合を以下のルール集合にグループ化する：
Ｒ1(1-2)：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−３０］∧ｄＰ∈［２１−２５］∪［２６−８０］→受理；
Ｒ1(3-4)：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［３１−６０］∧ｄＰ∈［２１−２５］∪［２６−８０］→受理；及び
Ｒ1(5-6)：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［６１−６９］∪ｘ．ｘ．ｘ．［７０−１２０］∧ｄＰ∈［２１−８０］→受理。
【００７１】
これを同様に１つのルールにグループ化する：
Ｒ1(1-6)：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−３０］∪ｘ．ｘ．ｘ．［３１−６０］∪ｘ．ｘ．ｘ．［６１−６９］∪ｘ．ｘ．ｘ．［７０−１２０］∧ｄＰ∈［２１−２５］∪［２６−８０］∪［２１−８０］→受理。
【００７２】
これはオリジナルのルールＲ1と等価である：
Ｒ1,1-6：    Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−１２０］∧ｄＰ∈［２１−８０］→受理。
【００７３】
他の３つのルールＲ2、Ｒ3、及びＲ4は、以下のように図６の衝突管理ツリーから取得される：
Ｒ21：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−３０］∧ｄＰ∈［１０−２０］→拒否；
Ｒ22：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［３１−６０］∧ｄＰ∈［１０−２０］→拒否；
Ｒ31：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［３１−６０］∧ｄＰ∈［８１−６５５３５］→拒否；
Ｒ32：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［６１−６９］∧ｄＰ∈［８１−６５５３５］→拒否；
Ｒ33：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−１２０］∧ｄＰ∈［８１−１３９］→拒否；
Ｒ34：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−１２０］∧ｄＰ∈［１４０−６５５３５］→拒否；
Ｒ35：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１２１−２００］∧ｄＰ∈［２１−１３９］→拒否；
Ｒ36：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１２１−２００］∧ｄＰ∈［１４０−６５５３５］→拒否；
Ｒ41：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−１２０］∧ｄＰ∈［１−２０］→受理；及び
Ｒ42：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１２１−２００］∧ｄＰ∈［１−２０］→受理。
【００７４】
上記のルール集合は以下の集合と等価である：
Ｒ2(1-2)：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−３０］∪ｘ．ｘ．ｘ．［３１−６０］∧ｄＰ∈［１０−２０］→拒否；
Ｒ3(1-2)：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［３１−６０］∪ｘ．ｘ．ｘ．［６１−６９］∧ｄＰ∈［８１−６５５３５］→拒否；
Ｒ3(3-4)：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−１２０］∧ｄＰ∈［８１−１３９］∪［１４０−６５５３５］→拒否；
Ｒ3(5-6)：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１２１−２００］∧ｄＰ∈［２１−１３９］∪［１４０−６５５３５］→拒否；及び
Ｒ4'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−１２０］∪［１２１−２００］∧ｄＰ∈［１−２０］→受理。
【００７５】
これは同様に以下の集合と等価である：
Ｒ2'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−６０］∧ｄＰ∈［１０−２０］→拒否；
Ｒ31'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［３１−６９］∧ｄＰ∈［８１−６５５３５］→拒否；
Ｒ32'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−１２０］∧ｄＰ∈［８１−６５５３５］→拒否；
Ｒ33'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１２１−２００］∧ｄＰ∈［２１−６５５３５］→拒否；
及び
Ｒ4'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−２００］∧ｄＰ∈［１−２０］→受理。
【００７６】
これは同様に、アノマリが存在しない以下のルール集合と等価である：
Ｒ1：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−１２０］∧ｄＰ∈［２１−８０］→受理；
Ｒ2'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１−６０］∧ｄＰ∈［１０−２０］→拒否；
Ｒ31'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［３１−１２０］∧ｄＰ∈［８１−６５５３５］→拒否；
Ｒ33'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［１２１−２００］∧ｄＰ∈［２１−６５５３５］→拒否；及び
Ｒ4'：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［７０−２００］∧ｄＰ∈［１−２０］→受理。
【００７７】
本発明の他の能力を示すために、「Detection and Removal of Firewall Misconfiguration」と題する刊行物に定義されているような冗長性アノマリを含む表１に提示された例を検討する。この文書では、冗長性は以下のように定義されている。Ｓをフィルタリングルールの集合とする。この場合、Ｓは、次の条件が当てはまるような少なくとも１つのフィルタリングルールＲiがＳに存在する場合、またその場合に限り、完全な冗長性（complete redundancy）を含む。この条件は、すなわち、（１）Ｒiが他のどのルールによってもシャドウイングされない；（２）ＳからＲiを削除しても、フィルタリング結果は変化しない、という条件である。ルールＲiが完全に冗長であるか否かをチェックするには、各リーフをチェックし、このリーフが存在する場合に、少なくとも１つの、同じ判断を有するルールが存在することをチェックすることで十分である。提示の便宜を図るために、宛先ＩＰ（ｄＩＰの条件属性に対応するノードレベルのみを、次により詳細に説明する。図８は、この状況を示している。
【００７８】
既存のルール集合のルールＲ3とＲ4との間に、新しいルールすなわちルールＲ34が追加される状況を検討する。Ｒ34：Ｐ∈任意∧ｓＩＰ∈任意∧ｓＰ∈任意∧ｄＩＰ∈ｘ．ｘ．ｘ．［３０−１３０］∧ｄＰ∈任意→拒否。管理者は、この追加されたルールが４番目に高い優先度を有するように、このルールを、以下の表２に示すようにＲ3とＲ4との間に追加する。
【００７９】
【表２】
0005154328.tif 000009
【００８０】
図２ａ及び図２ｂのフローチャートに関して説明したような方法を使用し、且つ、図８に示すような既存のツリーを使用することによって、新しいツリーが取得される。図９は、新しいルールＲ34が既存のルール集合に追加された時点での、ｄＩＰ条件属性に対応するレベルを示している。この時点で、取得された衝突管理ツリーから、種々のアノマリを検出することができる。
【００８１】
「Detection and Removal of Firewall Misconfiguration」と題する刊行物で定義されているような冗長性をチェックするには、衝突ツリーにおける種々のリーフを調べて、各ルールについて、より低い優先度を有すると共に、検査されているルールの判断と同じ判断を有する別のルールの存在をチェックすることで十分である。たとえば、図９に示す衝突ツリーによれば、あらゆるリーフにおいて、ルールＲ1と同じ判断及びより低い優先度を有する少なくとももう１つのルールが存在するように見えるため、ルールＲ1は、冗長なものとして検出される。実際には、Ｒ1がその存在を示す最初の３つのリーフに、より低い優先度及び同じ判断を有するＲ3が存在し、より低い優先度及び同じ判断を有するＲ5が、Ｒ1が存在する最後の３つのリーフに存在する。Ｒ1が存在する３番目のリーフには、２つのルールＲ3及びＲ5が共に存在する。ルールの順序にかかわらず一般的な冗長性を検出するには、たとえば表２に示されるＲ1について、検査されているルールと同じ判断を有すると共に、より低い優先度又はより高い優先度を有する別のルールの存在をチェックすることで十分である。同じ方法で、Ｒ2は冗長として検出される。図１０は、冗長なルールＲ1及びＲ2を示している。
【００８２】
「Detection and Removal of Firewall Misconfiguration」と題する刊行物で定義されているようなシャドウイングアノマリの検出には、冗長性アルゴリズムを適用した後、各リーフに１つのルールのみを保持することで十分である。ＳのルールＲiがマッチするすべてのパケットが、より高い優先順序を有する前のルール又はルールの組み合わせによってすでにマッチされているという理由で、ルールＲiは決して適用されない、そのようなルールＲiがＳ内に少なくとも１つ存在する場合に、ルール集合Ｓは完全なシャドウイングアノマリを含む。この場合、Ｒiは、完全にシャドウイングされたルールと呼ばれる。本発明で提案される方法を使用することによるルールＲiの完全なシャドウイングの検出には、このルールが存在する各リーフをチェックすることで十分である。したがって、そのルールが存在するリーフのすべてにおいて、そのルールが、より高い優先順序を有するルールの空でない有限集合によって部分的にシャドウイングされる場合、このルールは完全にシャドウイングされる。したがって、いずれかのルールが、生成された新しい衝突ツリーのどのリーフにも存在しない場合には、そのルールはシャドウイングアノマリとみなされる。これを行う１つのオプションは、リーフにおけるより低い優先度を有するルールを削除することを含む。図１１は、冗長性アルゴリズムを適用した後にシャドウイングアルゴリズムを適用した結果を提示している。図１１に示す衝突ツリーから、エラーの存在しない以下のルールの集合が生成される。
Ｒ3'：ｄＩＰ∈ｘ．ｘ．ｘ．［１−５５］→受理；
Ｒ34'：ｄＩＰ∈ｘ．ｘ．ｘ．［９１−１３０］→拒否；
Ｒ5'：ｄＩＰ∈ｘ．ｘ．ｘ．［５６−９０］→受理。
【００８３】
このルールの集合は、「Detection and Removal of Firewall Misconfiguration」と題する刊行物において紹介されているような冗長性アノマリ及びシャドウイングアノマリの定義を適用することによって取得される。
【００８４】
しかしながら、次のようなアノマリ定義を使用することもできる。すなわち、Ｓにおいて決して適用されないＳのルールＲiの少なくとも一部が存在する場合、またその場合に限り、Ｒは部分的シャドウイングを示す、というアノマリ定義である。この定義が、図９に示すオリジナルの衝突ツリー上で使用される場合に、アノマリが存在しない対応する衝突ツリーは図１２に示される。この結果は、図１２において、単に、各リーフの最初のルールを選び、現在のリーフの他のルールを削除することによって取得される。この選択は、最初のルール集合が初めに導入された時の、対応する設備による実行と比較して、取得されたルールの実行順序及び比較順序を変更しない。
【００８５】
図１２に示す衝突ツリーから、エラーの存在しない以下のルール集合が生成される。ｄＩＰ条件属性のみが、例示の題材として考慮されている。
Ｒ1'：ｄＩＰ∈ｘ．ｘ．ｘ．［２０−９０］→受理；
Ｒ2'：ｄＩＰ∈ｘ．ｘ．ｘ．［９１−１２０］→拒否；
Ｒ3'：ｄＩＰ∈ｘ．ｘ．ｘ．［１−１９］→受理；
Ｒ34'：ｄＩＰ∈ｘ．ｘ．ｘ．［１２１−１３１］→拒否。
【００８６】
図１１の衝突ツリーから生成されたルール集合は、図１２の衝突ツリーから生成されたものと異なっていることに留意すべきである。これは、「Detection and Removal of Firewall Misconfiguration」と題する刊行物において紹介されている冗長性の定義に起因するものである。実際には、最初のルール集合に関しては、オリジナルのルール集合に従った実行順序及び比較順序は維持されないが、本発明で提案されるオプションを使用すると、これは当てはまらない。図１２に示すような結果を取得するための解決法は、特に実施がかなり簡単であるため、一定の場合にはより良いものとみなすことができる。
【００８７】
管理者は、図２ａ及び図２ｂのフローチャートのアルゴリズムから自動的に生成された衝突ツリーから採用される適切な手段を選ぶことができる。衝突ツリーのリーフの異なる複数のルールを使用することによって、完全なシャドウイングや完全な冗長性のような構成ミスを発見することができる。これらの構成ミスを、上記で定義したものと異なる方法で定義することができる。ルールの構成ミスの定義にかかわらず、その検出は、衝突ツリーの異なるリーフに存在する異なるルールに直接依存する。ルールは、完全にシャドウイングされるものであると同時に、完全に冗長である場合がある。他の多くのアノマリ（一般化、相関等）を定義してもよい。これらのアノマリのすべてを、衝突ツリーから検出することができ、特にリーフから検出することができる。
【００８８】
図１２に示すような衝突ツリーから生成されたルールは、完全に互いに素であり、アノマリが存在しない。それらのルールは互いに素であるため、それらの実行の結果は、異なるルールの順序を変更しても同じである。
【００８９】
本発明は同様に、電子デバイスのコンピュータ手段にロードされて実行されると、本発明の実施形態の方法ステップのいずれかを実施することができるコンピュータプログラム製品に関する。
【００９０】
本発明は同様に、上述した方法ステップを実施するように構成された電子デバイスに関する。コンピュータプログラムは、電子デバイスによって実行されるように構成することができる。
【００９１】
このように、本発明は、起こり得るすべてのアノマリを最適な方法で検出することができるロバストで簡潔な方法を提供する。すなわち、空間消費及び時間消費が最小にされる。さらに、本発明は、ルール集合をオンラインで更新することを可能にし、それによって、関連した衝突管理ツリーをオンラインで更新することを可能にする。さらに、本発明の実施形態は、ネットワーク管理者に、アノマリの存在しないルールの適切な組み合わせを選ばせる。この決定は、自動的に行うこともできるし、管理者の好みに従って手動で行うこともできる。
【００９２】
図面及び上記説明で詳細に本発明を図示して説明してきたが、このような図示及び説明は、例証又は例示とみなされるべきであり、限定とみなされるべきではない。本発明は、開示した実施形態に限定されるものではない。
【００９３】
特許を請求する発明を実施する際に、図面、開示、及び添付の特許請求の範囲を検討することによって、当業者は、開示した実施形態に対する他の変形を理解して達成することができる。特許請求の範囲において、「備える」又は「含む」という用語は、他の要素又はステップを排除するものではなく、不定冠詞「a」又は「an」は複数を排除するものではない。単一のプロセッサ又は他のユニットが、特許請求の範囲で列挙されたいくつかのアイテムの機能を遂行する場合がある。単に、異なる特徴が、互いに異なる従属請求項に列挙されているということは、これらの特徴の組み合わせを好都合に使用することができないことを示すものではない。特許請求の範囲におけるどの参照符号も、本発明の範囲を限定するものとみなされるべきではない。
【図面の簡単な説明】
【００９４】
【図１】本発明の一実施形態に従って更新することができる衝突管理ツリーの一例の図である。
【図２ａ】本発明の一実施形態による方法を示すフローチャートである。
【図２ｂ】本発明の一実施形態による方法を示すフローチャートである。
【図３】セキュリティルール管理者によって導入された直後に１つのセキュリティルールのみからオンラインで作成された衝突管理ツリーを示す図である。
【図４】既存のルール集合に新しいルールを追加した時の、一時点での更新された衝突管理ツリーを示す図である。
【図５】既存のルール集合に新しいルールを追加した時の一時点での更新された衝突管理ツリーを示す図である。
【図６】既存のルール集合に新しいルールを追加した時の一時点での更新された衝突管理ツリーを示す図である。
【図７】ルールアノマリが存在しない衝突管理ツリーを示す図である。
【図８】ルールアノマリを含む別の衝突管理ツリーの一部を示す図である。
【図９】１つの新しい追加されたルールを有する図８の衝突管理ツリーを示す図である。
【図１０】冗長なルールの存在を示す図９の衝突管理ツリーを示す図である。
【図１１】ルールアノマリの存在しない図９の衝突管理ツリーの一部を示す図である。
【図１２】ルールアノマリの存在しない図９の衝突管理ツリーの一部を示す図である。
【図１】
0005154328.tif 000012
【図２ａ】
0005154328.tif 000013
【図２ｂ】
0005154328.tif 000014
【図３】
0005154328.tif 000015
【図４】
0005154328.tif 000016
【図５】
0005154328.tif 000017
【図６】
0005154328.tif 000018
【図７】
0005154328.tif 000019
【図８】
0005154328.tif 000020
【図９】
0005154328.tif 000021
【図１０】
0005154328.tif 000022
【図１１】
0005154328.tif 000023
【図１２】
0005154328.tif 000024