(57)【要約】  セキュリティ言語構造を、論理言語構造に変換することができ、逆も同様である。論理分解を、たとえば論理言語構造を使用してもたらすことができる。例示的な実施形態では、セキュリティ言語アサーションの少なくとも１つの論理言語ルールへの変換を説明する。もう１つの例示的な実施形態では、論理言語を反映する証明グラフのセキュリティ言語を反映する証明グラフへの変換を説明する。もう１つの例示的な実施形態では、決定性アルゴリズムを使用する論理言語プログラムの評価を説明する。
2010503129.tif 000002
【特許請求の範囲】
【請求項１】
アサートされるｆａｃｔおよび０個以上の条件ｆａｃｔを含むセキュリティ言語アサーションについて、アサートされるｆａｃｔがフラットであるかどうかを判定することと、
前記アサートされるｆａｃｔがフラットであると判定される場合に、前記セキュリティ言語アサーションを、前記アサートされるｆａｃｔに対応する主ｆａｃｔおよび前記０個以上の条件ｆａｃｔに対応する０個以上の付帯条件を含む論理言語ルールに変換することと、
前記アサートされるｆａｃｔがフラットではないと判定される場合に、
前記アサートされるｆａｃｔに対応する主ｆａｃｔおよび前記０個以上の条件ｆａｃｔに対応する０個以上の付帯条件を含む論理言語ルールを追加することと、
前記アサートされるｆａｃｔの委任ディレクティブ動詞ごとに、無制限の委任深さと委任を表す新しい変数とを論理言語ルールを追加することと
によって前記セキュリティ言語アサーションを論理言語ルールに変換することと
を含むことを特徴とする方法。
【請求項２】
前記アサートされるｆａｃｔがフラットであるかどうかの前記判定は、
前記アサートされるｆａｃｔが委任を含まないかどうかを判定すること
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記セキュリティ言語アサーションの前記変換の一部として作成される式を伴う主ｆａｃｔを有する論理言語ルールごとに、別名機能と別名オブジェクトを表す新しい変数とを有する別の論理言語ルールを追加すること
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
論理言語プログラムを作るために、アサーションコンテキストのセキュリティ言語アサーションごとに前記判定、前記変換、および前記追加を繰り返すことと、
認可クエリと共に前記論理言語プログラムを評価することと
をさらに含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記評価は、
前記論理言語を反映する証明グラフを作ること
を含み、
前記セキュリティ言語のセマンティックスルールに基づいて論理言語フラグメントとセキュリティ言語フラグメントとの間のめいめいの対応を確立するフラグメントサンプルを使用して、前記論理言語を反映する前記証明グラフを、前記セキュリティ言語を反映する別の証明グラフに変換すること
をさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記評価は
述部をグラウンド述部の集合にマッピングする第１テーブルおよび述部をサブゴールにマッピングする第２テーブルを利用するテーブル化に基づく決定性アルゴリズムを適用すること
を含むことを特徴とする請求項４に記載の方法。
【請求項７】
論理言語を反映する第１証明グラフのフラグメントを、セキュリティ言語を反映する第２証明グラフの対応するフラグメントに変換することと、
前記第１証明グラフのフラグメントごとに前記変換を繰り返すことと
を含むことを特徴とする方法。
【請求項８】
各フラグメントは、前記第１証明グラフの構造の一部を形成し、少なくとも２つの節点および少なくとも１つの有向辺を含むことを特徴とする請求項７に記載の方法。
【請求項９】
前記セキュリティ言語のアサーションコンテキストを前記論理言語のプログラムに変換することと、
前記論理言語の前記プログラムを評価することと、
前記評価に応答して前記第１証明グラフを作ることと
をさらに含むことを特徴とする請求項７に記載の方法。
【請求項１０】
前記評価は、
述部をグラウンド述部の集合にマッピングする第１テーブルおよび述部を前記第１証明グラフのサブゴールにマッピングする第２テーブルを利用するテーブル化に基づく決定性アルゴリズムを適用すること
を含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記変換は、
前記第１証明グラフの前記フラグメントの論理言語パターンを、複数の可能なセキュリティ言語パターンから選択された対応するセキュリティ言語パターンとマッチングすること
を含むことを特徴とする請求項７に記載の方法。
【請求項１２】
前記複数の可能なセキュリティ言語パターンの各めいめいのセキュリティ言語パターンは、前記セキュリティ言語のめいめいのセマンティックスルールに関連することを特徴とする請求項１１に記載の方法。
【請求項１３】
前記複数の可能なセキュリティ言語パターンは、少なくとも３つのセキュリティ言語パターンを含み、前記３つのセキュリティ言語パターンは、条件セマンティックスルールに関連する第１セキュリティ言語パターンと、委任セマンティックスルールに関連する第２セキュリティ言語パターンと、別名セマンティックスルールに関連する第３セキュリティ言語パターンとを含むことを特徴とする請求項１１に記載の方法。
【請求項１４】
前記第１証明グラフの前記フラグメントは、少なくとも１つの証明されたアサーションを表す１つまたは複数の節点と、少なくとも１つの付帯条件を表す１つまたは複数の節点とを含むことを特徴とする請求項７に記載の方法。
【請求項１５】
複数のアサーションを含むアサーションコンテキストを受け入れるための認可システムであって、前記複数のアサーションの各アサーションは、セキュリティ言語の構文に適合し、各アサーションの前記構文は、アサートされるｆａｃｔを含み、１つまたは複数の条件ｆａｃｔおよび１つまたは複数の制約を許容し、前記認可システムは、前記アサーションコンテキストを論理言語のプログラムに変換するためのものであり、前記論理言語の前記プログラムは、テーブル化に基づく決定性アルゴリズムを使用して認可クエリと共に評価されることを特徴とする認可システム。
【請求項１６】
前記決定性アルゴリズムは、述部をグラウンド述部の集合にマップする回答テーブルと、述部を証明グラフのサブゴールにマップするｗａｉｔテーブルとを利用することを特徴とする請求項１５に記載の認可システム。
【請求項１７】
前記証明グラフのサブゴールは、前記証明グラフのトップレベル述部、次に解くべき述部、およびその後に解くべき述部のリストを含むことを特徴とする請求項１６に記載の認可システム。
【請求項１８】
前記決定性アルゴリズムは、証明グラフを作り、前記認可システムは、さらに、前記論理言語を反映する前記証明グラフを、前記セキュリティ言語を反映する証明グラフに変換することを特徴とする請求項１５に記載の認可システム。
【請求項１９】
変換は、前記セキュリティ言語のめいめいのセマンティックスルールにめいめいが関連するフラグメントサンプルを、前記論理言語を反映する前記証明グラフの対応するフラグメントとマッチングすることによって実施されることを特徴とする請求項１８に記載の認可システム。
【請求項２０】
前記論理言語は、ある形のＤａｔａｌｏｇを含むことを特徴とする請求項１５に記載の認可システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、論理分解を用いるセキュリティ言語変換に関する。
【背景技術】
【０００２】
コンピュータおよび他の電子デバイスは、人々の職業（professional）生活および個人的（personal）生活に浸透している。職業セッティングで、人々は、プロジェクト協同作業中に機密情報を交換し、共有する。個人的セッティングで、人々は、電子商取引およびプライベート情報の伝送に従事する。上記および多数の他の実例で、電子セキュリティは、重要であると考えられる。
【０００３】
電子セキュリティパラダイムは、職業情報を秘密に保ち、個人情報をプライベートに保つことができる。電子セキュリティパラダイムは、あるレベルの暗号化ならびに／またはウィルス、ワーム、およびスパイウェアなどのマルウェアに対する保護を伴う場合がある。情報の暗号化とマルウェアからの保護との両方が、歴史的に、特に最近２〜３年に強く注目されてきた。
【０００４】
しかし、情報へのアクセスの制御は、電子情報の安全性を保護することの同等に重要な態様である。これは、利益が電子情報の共有および／または転送から引き出されるシナリオに特にあてはまる。そのようなシナリオでは、所定の人々がアクセスを許可され、他の人々が除外されなければならない。
【０００５】
アクセス制御は、早期の時分割システム以降の共有されるコンピュータおよびアプリケーションサーバの共通の特徴であった。情報へのアクセスを制御するのに使用された、多数の異なる手法がある。これらの手法は、あるリソースへのアクセスを要求するエンティティの認証と、許可されるアクセスを認可する機構との組合せにおいて、共通の基礎（common foundation）を共有する。認証機構は、パスワード、Ｋｅｒｂｅｒｏｓ、およびｘ．５０９証明書を含む。その目的は、リソースを制御するエンティティが、要求するエンティティ、または要求するそのエンティティに関する情報を明確に識別することを可能にすることである。
【０００６】
認可の例は、アクセス制御リスト（ＡＣＬ）と、ｅＸｔｅｎｓｉｂｌｅ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ（ＸＡＣＭＬ）またはＰｒｉｖｉｌＥｇｅ  ａｎｄ  Ｒｏｌｅ  Ｍａｎａｇｅｍｅｎｔ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ（ＰＥＲＭＩＳ）などのポリシベースの機構とを含む。これらの機構は、どのエンティティが、ファイルシステム内のファイル、ハードウェアデバイス、データベース情報などの所与のリソースにアクセスできるかを定義する。これらの機構は、リクエスタに関する認証された情報とリソースへの許可されるアクセスとの間のマッピングを提供することによって、この認可を実行する。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
コンピュータシステムが、インターネットなどの大規模ネットワークを介してよりユニバーサルに接続されるようになってきたので、これらの機構は、発展するアクセス制御要求の扱いにおいて若干制限があり、柔軟でないことがわかってきた。地理的に分散したユーザおよびコンピュータリソースのシステム、具体的には複数の管理ドメインにまたがるシステムは、現在展開されているテクノロジによって不十分に対処されている多数の課題を提示する。
【課題を解決するための手段】
【０００８】
セキュリティ言語構造を、論理言語構造に変換することができ、逆も同様である。論理分解は、たとえば論理言語構造を使用して達成され得る。例示的な実施形態において、セキュリティ言語アサーションの少なくとも１つの論理言語ルールへの変換を説明する。他の例示的な実施形態では、論理言語を反映する証明グラフのセキュリティ言語を反映する証明グラフへの変換を説明する。もう１つの例示的な実施形態では、決定性アルゴリズムを使用する論理言語プログラムの評価を説明する。
【０００９】
この概要は、「発明を実施するための形態」でさらに後述される概念の抜粋を単純化された形で紹介するために提供される。この概要は、請求される主題の主要な特徴または本質的特徴を識別することを意図されたものではなく、請求される主題の範囲を判定する際の助けとして使用されることを意図されたものでもない。さらに、他の方法、システム、方式、装置、デバイス、媒体、プロシージャ、ＡＰＩ、配置、プロトコルなどの実施態様を、本明細書で説明する。
【００１０】
同一の符号が、図面のすべてを通じて、類似するおよび／または対応する態様、特徴、およびコンポーネントを参照するのに使用される。
【図面の簡単な説明】
【００１１】
【図１】例示的セキュリティ方式を実施できる例示的な一般的な環境を示すブロック図である。
【図２】２つのデバイスと複数の例示的なセキュリティ関連コンポーネントとを有する例示的なセキュリティ環境を示すブロック図である。
【図３】例示的なセキュリティ関連データがセキュリティ関連コンポーネントの間で交換される、図２の例示的なセキュリティ環境を示すブロック図である。
【図４】本明細書で説明するセキュリティ関連実施態様に使用できる例示的なデバイスを示すブロック図である。
【図５】一般的なセキュリティ方式の例示的なアサーションフォーマットを示すブロック図である。
【図６】非集中認可ポリシの柔軟な指定および実施を可能にするセキュリティ言語を有する例示的なセキュリティ方式を示すブロック図である。
【図７】認可クエリ評価が効率的に完了することを保証するためにセキュリティ言語の安全性をチェックする方法の例を示す流れ図である。
【図８】セキュリティ言語を論理言語に変換する方法の例を示す流れ図である。
【図９】テーブル化を用いる例示的な決定的評価アルゴリズムを示すブロック図である。
【図１０】評価アルゴリズム中に作られ、グラフフラグメントを含む、例示的な論理言語証明グラフを示すブロック図である。
【図１１】論理言語証明グラフをセキュリティ言語証明グラフに変換する方法の例を示す流れ図である。
【図１２Ａ】条件セマンティックスルールに関する論理言語の例示的な証明フラグメントを示すブロック図である。
【図１２Ｂ】条件セマンティックスルールに関する図１２Ａに対応するセキュリティ言語の例示的な証明フラグメントを示すブロック図である。
【図１３Ａ】委任セマンティックスルールに関する論理言語の例示的な証明フラグメントを示すブロック図である。
【図１３Ｂ】委任セマンティックスルールに関する図１３Ａに対応するセキュリティ言語の例示的な証明フラグメントを示すブロック図である。
【図１４Ａ】別名セマンティックスルールに関する論理言語の例示的な証明フラグメントを示すブロック図である。
【図１４Ｂ】別名セマンティックスルールに関する図１４Ａに対応するセキュリティ言語の例示的な証明フラグメントを示すブロック図である。
【発明を実施するための形態】
【００１２】
［例示的なセキュリティ環境］
図１は、例示的セキュリティ方式１００を実施できる例示的な一般的な環境を示すブロック図である。セキュリティ方式（security scheme）１００は、セキュリティに対する統合された手法を表す。図示されているように、セキュリティ方式１００は、複数のセキュリティ概念すなわち、セキュリティトークン１００（Ａ）、セキュリティポリシ１００（Ｂ）、および評価エンジン１００（Ｃ）を含む。一般に、セキュリティトークン１００（Ａ）およびセキュリティポリシ１００（Ｂ）は、合同で評価エンジン１００（Ｃ）に入力を供給する。評価エンジン１００（Ｃ）は、それらの入力を受け入れ、あるリソースへのアクセスを許可すべきか拒否すべきかを示す認可出力を生産する。
【００１３】
説明される実施態様では、セキュリティ方式１００を、１つまたは複数のデバイス１０２にオーバーレイし、かつ／または一体化することができ、デバイス１０２は、ハードウェア、ソフトウェア、ファームウェア、これらのなんらかの組合せなどからなるものとすることができる。図示されているように、「ｄ」個のデバイス（「ｄ」はなんらかの整数である）が、１つまたは複数のネットワーク１０４を介して相互接続される。より具体的には、デバイス１０２（１）、デバイス１０２（２）、デバイス１０２（３）…デバイス１０２（ｄ）は、ネットワーク１０４を介して通信することができる。
【００１４】
各デバイス１０２は、セキュリティ方式１００の少なくとも一部を実装することができる任意のデバイスとすることができる。そのようなデバイスの例は、コンピュータ（たとえば、クライアントコンピュータ、サーバコンピュータ、パーソナルコンピュータ、ワークステーション、デスクトップ機、ラップトップ機、パームトップ機など）、ゲーム機（たとえば、コンソール、ポータブルゲームデバイスなど）、セットトップボックス、テレビジョン、消費者エレクトロニクス（たとえば、ＤＶＤプレイヤ／レコーダ、ビデオカメラ、ディジタルビデオレコーダ（ＤＶＲ）など）、携帯情報端末（ＰＤＡ）、携帯電話機、ポータブルメディアプレイヤ、これらのなんらかの組合せなどを含むが、これらに限定はされない。例示的な電子デバイスを、本明細書で、下で特に図４を参照して説明する。
【００１５】
ネットワーク１０４は、一緒にリンクされ、かつ／または互いの上にオーバーレイされた任意の１つまたは複数のネットワークから形成することができる。ネットワーク１０４の例は、インターネット、電話網、イーサネット、ローカルエリアネットワーク（ＬＡＮ）、広域ネットワーク（ＷＡＮ）、ケーブルネットワーク、ファイバネットワーク、ディジタル加入者回線（ＤＳＬ）ネットワーク、セルラネットワーク、Ｗｉ−Ｆｉ（登録商標）ネットワーク、ＷｉＭＡＸ（登録商標）ネットワーク、仮想プライベートネットワーク（ＶＰＮ）、これらのなんらかの組合せなどを含むが、これらに限定はされない。ネットワーク１０４は、複数のドメイン、１つまたは複数のグリッドネットワークなどを含むことができる。これらのネットワークのそれぞれまたはネットワークの組合せを、任意のネットワーキング標準規格に従って動作しているものとすることができる。
【００１６】
図示されているように、デバイス１０２（１）は、それと対話しているユーザ１０６に対応する。デバイス１０２（２）は、その上で実行されているサービス１０８に対応する。デバイス１０２（３）は、リソース１１０に関連する。リソース１１０は、デバイス１０２（３）の一部とするか、デバイス１０２（３）とは別々とすることができる。
【００１７】
ユーザ１０６、サービス１０８、および任意の所与のデバイス１０２などのマシンは、例示的なエンティティの非網羅的リストを形成する。エンティティは、時々、リソース１１０にアクセスすることを望む場合がある。セキュリティ方式１００は、正しく認証され、認可されたエンティティが、リソース１１０にアクセスすることを許可されるが、他のエンティティが、リソース１１０にアクセスするのを防がれることを保証する。
【００１８】
図２は、２つのデバイス１０２（Ａ）および１０２（Ｂ）と複数の例示的なセキュリティ関連コンポーネントとを有する例示的なセキュリティ環境２００を示すブロック図である。セキュリティ環境２００は、セキュリティトークンサービス（ＳＴＳ）オーソリティなどのオーソリティ２０２をも含む。デバイス１０２（Ａ）は、エンティティ２０８に対応する。デバイス１０２（Ｂ）は、リソース１１０に関連する。セキュリティ方式１００は、より複雑な環境で実施することができるが、この比較的単純な２デバイスのセキュリティ環境２００を使用して、例示的なセキュリティ関連コンポーネントを説明する。
【００１９】
図示されているように、デバイス１０２（Ａ）は、２つのセキュリティ関連コンポーネント、すなわち、セキュリティトークン２０４およびアプリケーション２１０を含む。セキュリティトークン２０４は、１つまたは複数のアサーション２０６を含む。デバイス１０２（Ｂ）は、５つのセキュリティ関連コンポーネント、すなわち、認可コンテキスト２１２、リソースガード２１４、監査ログ２１６、認可エンジン２１８、およびセキュリティポリシ２２０を含む。セキュリティポリシ２２０は、信頼および認可ポリシ２２２、認可クエリテーブル２２４、および監査ポリシ２２６を含む。
【００２０】
各デバイス１０２を異なって構成することができ、それでも、各デバイス１０２がセキュリティ方式１００のすべてまたは一部を実施することができる。たとえば、デバイス１０２（Ａ）は、複数のセキュリティトークン２０４および／またはアプリケーション２１０を有することができる。もう１つの例として、デバイス１０２（Ｂ）は、監査ログ２１６または監査ポリシ２２６を含まないものとすることができる。他の構成も可能である。
【００２１】
説明される実施態様では、オーソリティ２０２は、アサーション２０６を有するセキュリティトークン２０４をエンティティ２０８に発行する。アサーション２０６は、「セキュリティポリシアサーション言語（ｓｅｃｕｒｉｔｙ  ｐｏｌｉｃｙ  ａｓｓｅｒｔｉｏｎ  ｌａｎｇｕａｇｅ）の例示的な特性」と題するセクション内を含む下記において、本明細書にて説明する。したがって、エンティティ２０８は、セキュリティトークン２０４に関連する。動作時に、エンティティ２０８は、セキュリティトークン２０４によって、リソース１１０にアクセスするのにアプリケーション２１０を使用することを望む。
【００２２】
リソースガード２１４は、リソース１１０にアクセスする要求を受け取り、デバイス１０２（Ｂ）の他のセキュリティ関連コンポーネントと共に、認証および認可プロセスを効率的に管理する。信頼および認可ポリシ２２２は、その名前が示す通り、セキュリティ環境２００内でエンティティを信頼し、アクションを認可することを対象とするポリシを含む。信頼および認可ポリシ２２２には、たとえば、セキュリティポリシアサーション（図２には明示的には図示せず）を含めることができる。認可クエリテーブル２２４は、アクセス要求などの要求されたアクションを適当な認可ポリシにマップする。監査ポリシ２２６は、セキュリティ環境２００内でのセキュリティ方式１００の実施に関係付けられる監査責任および監査タスクを詳細に描写する。
【００２３】
認可コンテキスト２１２は、要求するエンティティを認証するのに使用されるアサーション２０６をセキュリティトークン２０４から収集し、セキュリティポリシアサーションを信頼および認可ポリシ２２２から収集する。認可コンテキスト２１２内のこれらの収集されたアサーションは、アサーションコンテキストを形成する。したがって、認可コンテキスト２１２には、さまざまなアサーションに加えて、他の情報を含めることができる。
【００２４】
認可コンテキスト２１２からのアサーションコンテキストおよび認可クエリテーブル２２４からの認可クエリは、認可エンジン２１８に供給される。このアサーションコンテキストおよび認可クエリを使用して、認可エンジン２１８は、認可判断を行う。リソースガード２１４は、この認可判断に基づいてアクセス要求に応答する。監査ログ２１６は、たとえば要求されたリソース１１０の識別および／または認可エンジン２１８によって実行されたアルゴリズム的評価ロジックなど、監査情報を含む。
【００２５】
図３は、例示的なセキュリティ関連データがセキュリティ関連コンポーネントの間で交換される、例示的なセキュリティ環境２００を示すブロック図である。セキュリティ関連データは、例示的なアクセス要求動作をサポートして交換される。この例示的なアクセス要求動作では、エンティティ２０８は、アプリケーション２１０を使用してリソース１１０にアクセスすることを望み、それを行うことの認可をセキュリティトークン２０４を用いて示す。したがって、アプリケーション２１０は、アクセス要求*をリソースガード２１４に送る。図３のこの説明では、アスタリスク（すなわち、「*」）は、述べられたセキュリティ関連データが図３に明示的に示されていることを示す。
【００２６】
説明される実施態様では、エンティティ２０８は、トークン*すなわちセキュリティトークン２０４を用いて、リソースガード２１４に対してそれ自体を認証する*。リソースガード２１４は、トークンアサーション*を認可コンテキスト２１２に転送する。これらのトークンアサーションは、セキュリティトークン２０４のアサーション２０６（図２の）である。セキュリティポリシ２２０は、認可クエリテーブル*をリソースガード２１４に供給する。この認可クエリテーブルは、認可クエリテーブルモジュール２２４から導出される。リソースガード２１４に送られる認可クエリテーブルは、現在のアクセス要求に直接に関係付けられる１つまたは複数の部分に制限することができる。
【００２７】
ポリシアサーションが、セキュリティポリシ２２０によって信頼および認可ポリシ２２２から抽出される。このポリシアサーションには、信頼関連アサーションと認可関連アサーションとの両方を含めることができる。セキュリティポリシ２２０は、このポリシアサーション*を認可コンテキスト２１２に転送する。認可コンテキスト２１２は、トークンアサーションとポリシアサーションとをアサーションコンテキストに組み合わせる。このアサーションコンテキスト*は、丸に囲まれた「Ａ」によって示されるように、認可コンテキスト２１２から認可エンジン２１８に供給される。
【００２８】
認証クエリが、認証クエリテーブルから確認される。リソースガード２１４は、認証クエリ（認証クエリ*）を認可エンジン２１８に供給する。認可エンジン２１８は、この認証クエリおよびアサーションコンテキストを評価アルゴリズムで使用して、認可判断を作る。この認可判断（認可判断*）が、リソースガード２１４に返される。エンティティ２０８がリソースガード２１４によってリソース１１０へのアクセスを許可されるか*どうかは、この認可判断に依存する。認可判断が肯定的である場合には、アクセスが許可される。その一方で、認可エンジン２１８によって発行された認可判断が否定的である場合には、リソースガード２１４は、エンティティ２０８がリソース１１０にアクセスするのを許可しない。
【００２９】
認可プロセスを、その認可プロセスに対して相補的なセマンティックスを使用して監査することもできる。監査は、認可プロセスの監視ならびに／あるいはたとえば認可エンジン２１８によって論理的に実行される評価アルゴリズムのすべての中間結果および／または最終結果のストレージを必然的に伴う。そのために、セキュリティポリシ２２０は、監査ポリシ２２６からの監査ポリシ*を認可エンジン２１８に供給する。少なくとも、監査が要求される時に、監査情報を有する監査レコード*を、認可エンジン２１８から監査ログ２１６に転送することができる。その代わりに、監査情報を、たとえば認可判断の一部としてまたは別々に、リソースガード２１４を介して監査ログ２１６にルーティングすることができる。
【００３０】
図４は、本明細書で説明するセキュリティ関連実施態様に使用できる例示的なデバイス１０２のブロック図である。複数のデバイス１０２が、１つまたは複数のネットワーク１０４を介して通信することができる。図示されているように、２つのデバイス１０２（Ａ／Ｂ）および１０２（ｄ）は、ネットワーク１０４を介する通信交換にかかわることができる。２つのデバイス１０２が具体的に図示されているが、実施態様に応じて、１つまたは３つ以上のデバイス１０２を使用することができる。
【００３１】
一般に、デバイス１０２は、クライアントデバイスまたはサーバデバイス、ワークステーションまたは他の一般的なコンピュータデバイス、ＰＤＡ、携帯電話機、ゲーミングプラットフォーム、エンターテイメントデバイス、図１を参照して上でリストしたデバイスの１つ、これらのなんらかの組合せなど、任意のコンピュータまたは処理の可能なデバイスを表すことができる。図示されているように、デバイス１０２は、１つまたは複数の入出力（Ｉ／Ｏ）インターフェース４０４、少なくとも１つのプロセッサ４０６、および１つまたは複数の媒体４０８を含む。媒体４０８は、プロセッサ実行可能命令４１０を含む。
【００３２】
デバイス１０２の説明される実施態様では、Ｉ／Ｏインターフェース４０４に、（ｉ）ネットワーク１０４を介して通信するネットワークインターフェース、（ｉｉ）ディスプレイスクリーンに情報を表示するディスプレイデバイスインターフェース、（ｉｉｉ）１つまたは複数のマンマシンインターフェースなどを含めることができる。（ｉ）ネットワークインターフェースの例は、ネットワークカード、モデム、１つまたは複数のポートなどを含む。（ｉｉ）ディスプレイデバイスインターフェースの例は、グラフィックスドライバ、グラフィックスカード、スクリーンまたはモニタ用のハードウェアまたはソフトウェアドライバなどを含む。印刷デバイスインターフェースを、同様にＩ／Ｏインターフェース４０４の一部として含めることができる。（ｉｉｉ）マンマシンインターフェースの例は、マンマシンインターフェースデバイス４０２（たとえば、キーボード、リモート、マウスまたは他のグラフィカルポインティングデバイスなど）とワイヤによってまたは無線で通信するものを含む。
【００３３】
一般に、プロセッサ４０６は、プロセッサ実行可能命令４１０などのプロセッサ実行可能命令を実行し、遂行し、かつ／または実施することができる。媒体４０８は、１つまたは複数のプロセッサアクセス可能媒体からなる。言い換えると、媒体４０８には、デバイス１０２による機能の実行を実現するためにプロセッサ４０６によって実行可能なプロセッサ実行可能命令４１０を含めることができる。
【００３４】
したがって、セキュリティ関連実施態様の実現を、プロセッサ実行可能命令の全般的な文脈で説明することができる。一般に、プロセッサ実行可能命令は、特定のタスクを実行し、かつ／もしくは可能にし、ならびに／あるいは特定の抽象データ型を実施する、ルーチン、プログラム、アプリケーション、コーディング、モジュール、プロトコル、オブジェクト、コンポーネント、メタデータおよびその定義、データ構造、アプリケーションプログラミングインターフェース（ＡＰＩ）、スキーマなどを含む。プロセッサ実行可能命令は、別々の記憶媒体に配置し、異なるプロセッサによって実行し、かつ／またはさまざまな伝送媒体を介して伝搬するかその伝送媒体に現存するものとすることができる。
【００３５】
プロセッサ（１つまたは複数）４０６は、任意の適用可能な処理可能なテクノロジを使用して実施することができる。媒体４０８は、デバイス１０２の一部として含められ、かつ／またはデバイス１０２によってアクセス可能な、任意の使用可能な媒体とすることができる。媒体４０８は、揮発性媒体および不揮発性媒体、取り外し可能媒体および取り外し不能媒体、ならびに記憶媒体および伝送媒体（たとえば、無線または有線の通信チャネル）を含む。たとえば、媒体４０８には、プロセッサ実行可能命令４１０の長期マスストレージ用のディスク／フラッシュメモリ／光媒体のアレイ、現在実行されつつある命令の短期記憶用のランダムアクセスメモリ（ＲＡＭ）、通信（たとえば、セキュリティ関連データ）を伝送するネットワーク１０４上のリンク（１つまたは複数）などを含めることができる。
【００３６】
具体的に図示されているように、媒体４０８は、少なくともプロセッサ実行可能命令４１０を含む。一般に、プロセッサ実行可能命令４１０は、プロセッサ４０６によって実行された時に、デバイス１０２が、さまざまな流れ図に示されたアクションを含む、本明細書で説明されるさまざまな機能を実行することを可能にする。例としてのみ、プロセッサ実行可能命令４１０に、セキュリティトークン２０４、そのアサーション２０６のうちの少なくとも１つ、認可コンテキストモジュール２１２、リソースガード２１４、監査ログ２１６、認可エンジン２１８、セキュリティポリシ２２０（たとえば、信頼および認可ポリシ２２２、認可クエリテーブル２２４、および／または監査ポリシ２２６など）、これらのなんらかの組合せなどを含めることができる。図４に明示的に図示されてはいないが、プロセッサ実行可能命令４１０に、アプリケーション２１０および／またはリソース１１０を含めることもできる。
【００３７】
［セキュリティポリシアサーション言語の例示的な特性］
このセクションでは、セキュリティポリシアサーション言語（ＳｅｃＰＡＬ）の実装の例示的な特性を説明する。このセクションのＳｅｃＰＡＬの実装は、比較的略式的で、例としてのみ説明される。このセクションのＳｅｃＰＡＬの実装は、エンドツーエンドソリューションの作成に用いられる広範囲のセキュリティポリシおよびセキュリティトークンの義務に対処する能力を有する。これらのセキュリティポリシおよびセキュリティトークンの責任は、限定ではなく例として、明示的信頼関係を記述すること、セキュリティトークン発行ポリシを表すこと、アイデンティティ、属性、能力、および／または委任（delegation）ポリシを含むセキュリティトークンを提供すること、リソース認可および委任ポリシを表すことなどを含む。
【００３８】
説明される実施態様では、ＳｅｃＰＡＬは、柔軟で扱いやすい形でセキュリティを表す宣言的な論理ベースの言語である。ＳｅｃＰＡＬは、包括的とすることができ、信頼関係、認可ポリシ、委任ポリシ、アイデンティティおよび属性アサーション、能力アサーション、撤回（ｒｅｖｏｃａｔｉｏｎ）、監査要件などを表す均一な（uniform）機構を提供することができる。この均一性は、セキュリティ方式を理解でき、分析可能なものにすることに関して具体的な利益をもたらす。この均一な機構は、別個のセキュリティテクノロジの間のセマンティック変換および調停の必要を回避するか、少なくとも大幅に削減することを可能にすることによって、セキュリティ保証をも改善する。
【００３９】
ＳｅｃＰＡＬの実装は、次の例示的な特徴のうちのいずれをも含むことができる。［１］ＳｅｃＰＡＬは、比較的理解しやすいものにすることができる。ＳｅｃＰＡＬは、そのアサーションを英文として読むことを可能にする定義構文を使用することができる。また、ＳｅｃＰＡＬの文法は、ユーザが、明瞭に定義されたセマンティックスを有する少数の主語−動詞−目的語（たとえば、主語−動詞句）構造を理解することだけを必要とするように制限することができる。最後に、アサーションのコレクションに基づいて演繹（推論）可能なｆａｃｔ（事実）を評価するアルゴリズムは、少数の比較的単純なルールに頼るものとすることができる。
【００４０】
［２］ＳｅｃＰＡＬは、その採用および既存システムへの統合を容易にするために、その実施態様において業界標準インフラストラクチャを活用することができる。たとえば、形式モデルからの単純なマッピングであるＸＭＬ（ｅｘｔｅｎｓｉｂｌｅ  ｍａｒｋｕｐ  ｌａｎｇｕａｇｅ）構文を使用することができる。これは、標準的なパーサおよび構文正当性検証ツールの使用を可能にする。これは、完全性、出所の証明、および機密性に関するＷ３ＣのＸＭＬ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ標準規格およびＸＭＬ  Ｅｎｃｒｙｐｔｉｏｎ標準規格の使用をも可能にする。
【００４１】
［３］ＳｅｃＰＡＬは、分散ポリシオーサリングおよびコンポジションをサポートすることによって、分散ポリシ管理を可能にすることができる。これは、ポリシまたはポリシの一部分が、割り当てられた管理義務に基づいてどこで作成されるかを支配する異なる動作モデルへの柔軟な採用を可能にする。ポリシオブジェクトのディジタル署名および暗号化への標準手法の使用は、そのセキュア分散を可能にする。［４］ＳｅｃＰＡＬは、効率的で安全な評価を可能にする。入力に対する単純な構文チェックが、評価が終了し、正しい回答を作ることを保証するのに十分である。
【００４２】
［５］ＳｅｃＰＡＬは、アイデンティティ管理のために要求されるポリシ、認可判断、監査、およびＰＫＩ（public-key infrastructure）をサポートするアクセス制御要件の完全なソリューションを提供することができる。対照的に、ほとんどの他の手法は、セキュリティ問題のスペクトルのうちの１つのサブセットに焦点を合わせ、対処することしかできない。［６］ＳｅｃＰＡＬは、Ｇｒｉｄ環境および他のタイプの分散システムに関するセキュリティ問題の処理を含むがこれに限定はされない複数の目的に関して十分に表現力のあるものとすることができる。拡張性は、特定のシステムの必要への適合を可能にしながら言語セマンティックスおよび評価プロパティを維持する形で可能にされる。
【００４３】
図５は、一般的なセキュリティ方式の例示的なアサーションフォーマット５００を示すブロック図である。本明細書で別な形で説明される実施態様に使用されるセキュリティ方式アサーションは、例示的なアサーションフォーマット５００とは異なる場合がある。しかし、アサーションフォーマット５００は、セキュリティ方式アサーションの１つの例示的なフォーマットの基本的な図示であり、一般的なセキュリティ方式のさまざまな態様の例示的な説明される実施態様を理解するための基礎を提供する。
【００４４】
アサーションフォーマット５００の最上行に示されているように、主要レベルでの例示的なアサーションは、ｐｒｉｎｃｉｐａｌ（プリンシパル）部分５０２、ｓａｙｓ（言う）部分５０４、およびｃｌａｉｍ（主張）部分５０６を含む。逐語的には、アサーションフォーマット５００の主要レベルは、「ｐｒｉｎｃｉｐａｌ」  ｓａｙｓ  「ｃｌａｉｍ」によって表すことができる。
【００４５】
アサーションフォーマット５００の次の行では、ｃｌａｉｍ部分５０６が、例示的な構成部分に分離されている。したがって、例示的なｃｌａｉｍ部分５０６は、ｆａｃｔ部分５０８、ｉｆ（もしも）部分５１０、「ｎ」個の条件ｆａｃｔ1…n部分５０８（１…ｎ）、およびｃ部分５１２を含む。添字「ｎ」は、なんらかの整数値を表す。凡例５２４によって示されるように、ｃ部分５１２は、制約部分を表す。単一の制約だけが図示されているが、ｃ部分５１２は、実際には複数の制約を表す場合がある（たとえば、ｃ1、…、ｃm）。ｉｆ部分５１０の右側の条件ｆａｃｔ部分５０８（１…ｎ）および制約５１２（１…ｍ）の組を、前件（antecedent）と称する場合がある。
【００４６】
逐語的には、ｃｌａｉｍ部分５０６は、ｆａｃｔ  ｉｆ  ｆａｃｔ1，…，ｆａｃｔn，ｃによって表すことができる。したがって、全体的なアサーションフォーマット５００は、逐語的にはｐｒｉｎｃｉｐａｌ  ｓａｙｓ  ｆａｃｔ  ｉｆ  ｆａｃｔ1，…，ｆａｃｔn，ｃと表すことができる。しかし、アサーションは、ｐｒｉｎｃｉｐａｌ  ｓａｙｓ  ｆａｃｔのように単純なものとすることができる。アサーションのこの省略された３部バージョンでは、ｉｆ部分５１０から始まりｃ部分５１２まで延びる条件部分が、省略されている。
【００４７】
各ｆａｃｔ部分５０８を、さらにその構成部分に副分割することもできる。例示的な構成部分は、ｅ部分５１４およびｖｅｒｂ  ｐｈｒａｓｅ（動詞句）部分５１６である。凡例５２４によって示されているように、ｅ部分５１４は、式（expression）部分を表す。逐語的には、ｆａｃｔ部分５０８は、ｅ  ｖｅｒｂｐｈｒａｓｅによって表すことができる。
【００４８】
各ｅ部分すなわち式部分５１４は、２つの例示的なオプションのうちの１つをとることができる。この２つの例示的な式オプションは、ｃｏｎｓｔａｎｔ（定数）５１４（ｃ）およびｖａｒｉａｂｌｅ（変数）５１４（ｖ）である。ｐｒｉｎｃｉｐａｌは、ｃｏｎｓｔａｎｔ  ５１４（ｃ）および／またはｖａｒｉａｂｌｅ  ５１４（ｖ）の下に含めることができる。
【００４９】
各ｖｅｒｂ  ｐｈｒａｓｅ部分５１６も、３つの例示的なオプションのうちの１つをとることができる。この３つの例示的なｖｅｒｂ  ｐｈｒａｓｅオプションは、１つまたは複数のｅ1…n部分５１４（１…ｎ）が続くｐｒｅｄｉｃａｔｅ（述部）部分５１８、ｆａｃｔ部分５０８が続くｃａｎ  ａｓｓｅｒｔ（アサートできる）部分５２０、および式部分５１４が続くａｌｉａｓ（別名）部分５２２である。逐語的には、これらの３つのｖｅｒｂ  ｐｈｒａｓｅオプションは、それぞれｐｒｅｄｉｃａｔｅ  ｅ1…ｅn、ｃａｎ  ａｓｓｅｒｔ  ｆａｃｔ、およびａｌｉａｓ  ｅによって表すことができる。整数「ｎ」は、ｆａｃｔ  ５０８（１…ｎ）および式５１４（１…ｎ）について異なる値をとることができる。
【００５０】
一般に、ＳｅｃＰＡＬステートメントは、セキュリティプリンシパルによって作られるアサーションの形である。セキュリティプリンシパルは、通常、暗号鍵によって識別され、その結果、システム境界にまたがってセキュリティプリンシパルを認証できるようになる。最も単純な形において、アサーションは、あるｆａｃｔが有効である（たとえば、ｆａｃｔ部分５０８を含むｃｌａｉｍ  ５０６によって表される）とプリンシパルが考えていることを述べるものである。アサーションは、１つまたは複数の他のｆａｃｔが有効であり、条件の何らかの集合が満足される（たとえば、ｆａｃｔ部分５０８からｉｆ部分５１０、条件ｆａｃｔ部分５０８（１…ｎ）、ｃ部分５１２まで延びるｃｌａｉｍ部分５０６によって表される）場合に、あるｆａｃｔが有効であることを述べることもできる。制約５１２を全く伴わない条件ｆａｃｔ  ５０８（１…ｎ）および／または条件ｆａｃｔ  ５０８（１…ｎ）を全く伴わない制約５１２も存在し得る。
【００５１】
説明される実施態様では、ｆａｃｔは、ｐｒｉｎｃｉｐａｌに関するステートメントである。ｆａｃｔステートメントの４つの例示的なタイプを、本明細書のこのセクションで説明する。第１に、ｆａｃｔは、ｐｒｉｎｃｉｐａｌがリソースに対するアクション（１つまたは複数）を行う権利を有することを、「ａｃｔｉｏｎ  ｖｅｒｂ（アクション動詞）」を用いて述べることができる。例示的なａｃｔｉｏｎ  ｖｅｒｂは、ｃａｌｌ（呼び出す）、ｓｅｎｄ（送る）、ｒｅａｄ（読み取る）、ｌｉｓｔ（リストする）、ｅｘｅｃｕｔｅ（実行する）、ｗｒｉｔｅ（書き込む）、ｍｏｄｉｆｙ（変更する）、ａｐｐｅｎｄ（追加する）、ｄｅｌｅｔｅ（削除する）、ｉｎｓｔａｌｌ（インストールする）、ｏｗｎ（所有する）などを含むが、これらに限定はされない。リソースは、ｕｎｉｖｅｒｓａｌ  ｒｅｓｏｕｒｃｅ  ｉｎｄｉｃａｔｏｒ（ＵＲＩ）または任意の他の手法によって識別することができる。
【００５２】
第２に、ｆａｃｔは、ｐｒｉｎｃｉｐａｌ識別子と１つまたは複数の属性との間の束縛を「ｐｏｓｓｅｓｓ（所有する）」動詞を使用して表すことができる。例示的な属性は、電子メール名、通称、グループ名、役職、アカウント名、ドメインネームサーバ／サービス（ＤＮＳ）名、インターネットプロトコル（ＩＰ）アドレス、デバイス名、アプリケーション名、組織名、サービス名、アカウント識別／識別子（ＩＤ）などを含むがこれらに限定はされない。ｆａｃｔの例示的な第３のタイプは、同一のｐｒｉｎｃｉｐａｌを表すために、「ａｌｉａｓ」動詞を使用して２つのｐｒｉｎｃｉｐａｌ識別子を定義できることである。
【００５３】
「修飾子」またはｆａｃｔ修飾子を、上の３つのｆａｃｔタイプのいずれかの一部として含めることができる。修飾子は、アサータが、ｆａｃｔが有効と考えられる場合に成り立たなければならないとそのアサータが考える環境パラメータ（たとえば、時刻、ｐｒｉｎｃｉｐａｌ位置など）を示すことを可能にする。そのようなステートメントは、アサータと、これらの修飾子値に基づく頼る当事者の妥当性チェックとの間できれいに分離することができる。
【００５４】
ｆａｃｔの例示的な第４のタイプは、「ｃａｎ  ａｓｓｅｒｔ」動詞によって定義される。この「ｃａｎ  ａｓｓｅｒｔ」動詞は、信頼関係および委任を表す柔軟で強力な機構を提供する。たとえば、「ｃａｎ  ａｓｓｅｒｔ」動詞は、あるｐｒｉｎｃｉｐａｌ（Ａ）が、第２のｐｒｉｎｃｉｐａｌ（Ｂ）によってアサートされたあるタイプのｆａｃｔを信じるつもりがあることを述べることを可能にする。たとえば、アサーション「Ａ  ｓａｙｓ  Ｂ  ｃａｎ  ａｓｓｅｒｔ  ｆａｃｔ０（ＡはＢがｆａｃｔ０をアサートできると言う）」および「Ｂ  ｓａｙｓ  ｆａｃｔ０（Ｂはｆａｃｔ０と言う）」とを与えられれば、ｆａｃｔ０が有効であるとＡが信じると結論することができ、したがって、「Ａ  ｓａｙｓ  ｆａｃｔ０（Ａはｆａｃｔ０と言う）」と演繹することができる。
【００５５】
そのような信頼アサーションおよび委任アサーションは、（ｉ）下流委任を許可するために、束縛されず、推移的とするか、（ｉｉ）下流委任を防止するために束縛されるものとすることができる。修飾子を「ｃａｎ  ａｓｓｅｒｔ」タイプのｆａｃｔに適用することができるが、これらの「ｃａｎ  ａｓｓｅｒｔ」タイプのｆａｃｔへの修飾子のサポートの省略は、所与のセキュリティ方式のセマンティックスおよび評価安全性プロパティを大幅に単純化することができる。
【００５６】
説明される実施態様では、具体的なｆａｃｔを述べることができ、あるいは、変数を使用してポリシ式を記述することができる。変数は、型付きであり、制限なし（たとえば、正しい型のすべての具体的な値と一致することを許可される）または制限付き（たとえば、指定されたパターンに基づく具体的な値の部分集合と一致することを要求される）のいずれかとすることができる。
【００５７】
セキュリティ認可判断は、適用可能なセキュリティポリシ（たとえば、セキュリティポリシ２２０）およびセキュリティトークン（たとえば、１つまたは複数のセキュリティトークン２０４）からのアサーションのコレクション（たとえば、アサーションコンテキスト）に対する認可クエリの評価アルゴリズム（たとえば、認可エンジン２１８で行うことができる評価アルゴリズム）に基づく。認可クエリは、論理式であり、この論理式は、ｆａｃｔおよび／または条件を組み合わせる非常に複雑なものになる場合がある。これらの論理式には、たとえば、付随する条件および／または制約を伴うまたは伴わないのいずれであれ、ｆａｃｔに対するＡＮＤ、ＯＲ、および／またはＮＯＴ論理演算を含めることができる。
【００５８】
認可クエリに対するこの手法は、所与のアクションを認可する前に、何を知らなければならず、何が有効でなければならないかを定義する柔軟な機構を提供する。クエリテンプレート（たとえば、認可クエリテーブル２２４からの）は、全体的なセキュリティ方式の一部を形成し、異なるタイプのアクセス要求および他の動作／アクションについて適当な認可クエリを宣言的に述べることを可能にする。
【００５９】
［論理分解を用いるセキュリティ言語変換の例示的な実装］
セキュリティは、現代のコンピューティングシステムにおいてクリティカルである。セキュリティを、認可されるアクセスを決定する効率的で高保証の柔軟な機構を用いて容易にすることができる。これは、ポリシベースの手法を使用して達成可能である。そのようなシステムでは、ポリシは、アクセス判断を行い、実施するための基礎になるコードを変更する必要なしに現在の必要を反映するように変化することができる。
【００６０】
既存の手法は、特に複雑な分散コンピューティング環境で、これらの必要を十分に満足することができない。ＡＣＬなどの単純なルールベースのポリシは、非常に効率的ではあるが十分に柔軟ではない。ＸＡＣＭＬなどのより複雑なルールベースのポリシシステムは、より非効率的な評価と引き換えにより高い柔軟性を提供する。さらに、そのようなルールベースのポリシシステムは、機能的制限（たとえば、委任サポートの欠如）を有する。
【００６１】
従来の論理ベースのポリシモデルは、一般に、最良の機能性を提供するが、他の問題がないわけではない。これらのモデルの一部は、適当な評価安全性プロパティを提供しない。言い換えると、所与の認可判断アルゴリズムが、終了することを保証することができない。他のいくつかのモデルは、非常に非効率的である。さらなる他のいくつかのモデルは、理論的には健全であるが、商用システムで実装するのに実用的とは考えられない。
【００６２】
必要なものは、実装するために実用的であると同時に非常に柔軟であり、効率的な評価ならびに保証された終了を保証する必須の評価安全性プロパティを有する、論理ベースのセキュリティポリシ言語である。例示的なセキュリティポリシ言語の説明される実施態様は、これらの領域での改善をもたらす。
【００６３】
下のセクションでは、例示的なセキュリティ言語を説明する。多くの場所で、この説明は、比較的厳格な論理的基礎によってサポート可能なセキュリティ言語モデルを提供する限り、正確である。厳格な論理的基礎を含む例示的に説明される実施態様は、理論的基盤が理解されることを保証するために提供される。しかし、セキュリティ言語の任意の所与の実世界実施態様が、厳格な論理的説明の諸態様のうちの任意の特定の（すべてより少ない）態様を含まない場合がある。したがって、本願の発明は、本明細書で説明される特定の詳細な実施形態のいずれによるのでもなく、特許請求の範囲によって定義されなければならない。
【００６４】
１  論理分解のためのセキュリティ言語式の序説
セキュリティ言語の式の複数の例示的な実施態様を、本明細書で提供する。これらの実施態様は、結果のセキュリティポリシを効率的なある種の形で論理的に分解できるように設計されている。
【００６５】
図６は、非集中認可ポリシの柔軟な指定および実施を可能にするセキュリティ言語６０２を有する例示的なセキュリティ方式６００を示すブロック図である。セキュリティ方式６００は、アサーション構文６０４および認可クエリ構文６０６を含む。セキュリティ方式は、複数のセマンティックスルール６０８（ｘ）をも含む。例示的なセマンティックスルールは、条件セマンティックスルール６０８（１）、委任セマンティックスルール６０８（２）、および別名セマンティックスルール６０８（３）を含むが、これらに限定はされない。これらのセマンティックスルール６０８（ｘ）は、合同で言語セマンティックス６０２を形成する。
【００６６】
アサーション構文６０４、認可クエリ構文６０６、および言語セマンティックス６０８のそれぞれは、例示的なセキュリティ言語６０２の形成および管理に寄与する。セキュリティ方式は、アサーション構文安全性チェック６１０および認可クエリ安全性チェック６１２をも含む。アサーション構文安全性チェック６１０および認可クエリ安全性チェック６１２を、セキュリティ言語６０２に一体化して、認可クエリの取り扱いやすさを保証するのを助けることができる。
【００６７】
下のセクション２では、セキュリティ言語のアサーションの例示的な構文およびセマンティックスを説明する。セクション３では、認可クエリの例示的な構文およびセマンティックスを説明する。セクション４では、アサーションおよび認可クエリの安全性原理を説明する。これらの安全性プロパティは、正しく適用された時に、認可クエリ評価が終了することを保証することができ、その評価が効率的に進行することを保証することができる。
【００６８】
２  例示的なセキュリティ言語の構文およびセマンティックス
例示的なセキュリティ言語のコア構文を、ここで説明する。セキュリティ構文の追加の構文は、たとえば単一のアサーション内の一連の権利を委任するための、アサーションのグループ化のために設けることができるが、これらの構文などの追加は、コア構文に限定することができる。セキュリティ言語の例示的な実施態様は、定数、関数、および変数の型付け規律を強制することもできるが、そのような型付け強制は、ここでは、コア構文に集中するために省略する。
【００６９】
アサーション
認可ポリシは、次の形のアサーションの集合として指定される。  
Ａ  ｓａｙｓ  ｆａｃｔ  ｉｆ  ｆａｃｔ1，…，ｆａｃｔn，ｃ
ここで、ｆａｃｔは、たとえば誰かがファイルを読み取る権利を有することなど、プリンシパルに関するプロパティを述べる述部にわたる。例示的な実施態様では、アサーションは、ホーン節に似たものとすることができるが、（１）アサーションは、アサートされるｃｌａｉｍを発行し、その証人となるあるプリンシパルＡによって修飾され、（２）ｆａｃｔは、キーワードｃａｎ  ａｓｓｅｒｔを使用することによってネストすることができ、これによって、委任権利が指定され、（３）アサーション内の変数は、ｃすなわち、たとえば時間的制約、不等性制約、木構造制約、正規表現制約などを表すことができるファーストオーダーの式（ｆｉｒｓｔ  ｏｒｄｅｒ  ｆｏｒｍｕｌａ）によって制約されるという相違を有する。
【００７０】
次のリスティングに、本明細書で使用されるアサーション構文６０４の用語法を示す。
【００７１】
【表１】
2010503129.tif 000003
【００７２】
説明される実施態様では、変数は、文字列および整数のみの範囲にまたがるが、ｐｒｅｄｉｃａｔｅ、ｆａｃｔ、ｃｌａｉｍ、およびａｓｓｅｒｔｉｏｎの範囲にはまたがらない。構文の句は、変数を含まない場合にグラウンド（ｇｒｏｕｎｄ）である。集合ＰｒｅｄｉｃａｔｅＮａｍｅｓは、ｃａｎ  ａｓｓｅｒｔ∞、ｃａｎ  ａｓｓｅｒｔ0、およびａｌｉａｓを含んではならない。関数および述部は、固定されたアリティを有する。述部は、そのオブジェクトパラメータ用の穴を有する動詞句である。述部が複数の単語を有する場合に、これらの穴は、たとえばｈａｓ  ａｃｃｅｓｓ  ｆｒｏｍ［−］ｔｉｌｌ［−］など、その述部の中で固定された位置にあるように見えるものとすることができる。
【００７３】
このテキストの残りでは、通常はｐｒｉｎｃｉｐａｌを記述するために、定数のメタ変数としてＡ、Ｂ、Ｃ、およびＤを使用する。アイテムの（おそらくは空の）リスト（またはタプル）を表すのにベクトル表記を使用し、たとえば、ｆ（ｅ1，…，ｅn）を
【００７４】
【数１】
2010503129.tif 000004
【００７５】
と書く場合がある。
【００７６】
ｆａｃｔは、上の構文定義からわかるように、ネストすることができる。ネストされたｆａｃｔは、次に定義するようにｆａｃｔがフラットである場合に、あるｎ≧１について、ｅ1  ｃａｎ  ａｓｓｅｒｔD1…ｅn  ｃａｎ  ａｓｓｅｒｔDn  ｆａｃｔの形になる。
【００７７】
２つの定義を下に提示する。第１の定義は、フラットｆａｃｔを定義し、第２の定義は、アサーションの諸部分を定義する。
【００７８】
定義２．１  ｆａｃｔは、ｃａｎ  ａｓｓｅｒｔがその中に現れない場合に限ってフラットであり、そうでない場合にはネストされている。
【００７９】
たとえば、Ａｌｉｃｅ  ｓａｙｓ  Ｂｏｂ  ｃａｎ  ｒｅａｄ  ｆというｆａｃｔはフラットであるが、Ａｌｉｃｅ  ｓａｙｓ  Ｃｈａｒｌｉｅ  ｃａｎ  ａｓｓｅｒｔ0  Ｂｏｂ  ｃａｎ  ｒｅａｄ  ｆはフラットではない。
【００８０】
定義２．２  Ａ  ｓａｙｓ  ｆａｃｔ  ｉｆ  ｆａｃｔ1，…，ｆａｃｔn，ｃがアサーションであるものとする。Ａは、その発行者であり、ｆａｃｔiは、その条件ｆａｃｔであり、ｃは、その制約である。ｆａｃｔは、アサーションの主ｆａｃｔまたはアサートされるｆａｃｔと考えることができる。
【００８１】
制約
制約は、下に示す例示的な基本制約領域を拡張するすべての制約領域にまたがる。基本制約は、整数不等性（たとえば、時間的制約を表すため）、ツリー順序制約（たとえば、ディレクトリ用）、および正規表現（たとえば、アドホックフィルタリング用）を含む。基本制約の例を、下に示す。
【００８２】
【表２】
2010503129.tif 000005
【００８３】
追加の制約を、決定可能性に影響せず、取り扱いやすさに大きくは影響せずに追加することができる。しかし、所望のレベルの取り扱いやすさを維持するために、グラウンド制約の妥当性を多項式時間でチェックできることが好ましい。
【００８４】
たとえばＦａｌｓｅ、ｅ1≠ｅ2、またはｃ1  ｏｒ  ｃ2など、基本的な制約の表記から導出できる制約のシュガード表記（ｓｕｇａｒｅｄ  ｎｏｔａｔｉｏｎ）を使用する。アサーションでは、通常はＴｒｕｅ制約を省略し、アサーションが条件ｆａｃｔを有しない時にはｉｆをも省略する。
【００８５】
セマンティックス
これから言語セマンティックス６０８の形式的な定義を与える。まず、グラウンド式の記号を定義する。定数Ａの記号は、単にＡであり、したがって［［Ａ］］＝Ａである。関数
【００８６】
【数２】
2010503129.tif 000006
【００８７】
の記号は、
【００８８】
【数３】
2010503129.tif 000007
【００８９】
がグラウンドである場合に定義され、やはり定数であるが、システム状態ならびに
【００９０】
【数４】
2010503129.tif 000008
【００９１】
に依存する場合がある。たとえば、［［ＣｕｒｒｅｎｔＴｉｍｅ（）］］は、おそらくは、異なる時刻に呼び出された時に異なる定数を返す。しかし、単一の認可クエリ評価が、システム状態に関して原子的であると仮定する。すなわち、式を複数回評価できる場合であっても、その記号は、単一の評価中には同一である。
【００９２】
所与の定数ｃについて、ｃが有効である場合に限って｜＝ｃと書く。次では、基本制約領域内の有効性を定義する。
｜＝Ｔｒｕｅ
｜＝ｅ1＝ｅ2                          ［［ｅ1］および［［ｅ2］］が等しい定数である場合に限って
｜＝ｅ1≦ｅ2                          ［［ｅ1］］および［［ｅ2］］が整数定数であり、［［ｅ1］］≦［［ｅ2］］の場合に限って
【００９３】
【数５】
2010503129.tif 000009
【００９４】
［［ｅ1］］および［［ｅ2］］が木定数であり、［［ｅ1］］が［［ｅ2］］の子孫であるかこれと等しい場合に限って
｜＝ｅ  ｍａｔｃｈｅｓ  ｐａｔｔｅｒｎ  ［［ｅ］］が、ｐａｔｔｅｒｎと一致する文字列定数である場合に限って
｜＝ｎｏｔ（ｃ）                        ｜＝ｃが成り立たない場合に限って
｜＝ｃ1，ｃ2                          ｜＝ｃ1かつ｜＝ｃ2である場合に限って
【００９５】
この文書の残りでは、置換θを、変数を定数および変数にマッピングする関数と呼ぶ。置換は、制約、述部、ｆａｃｔ、ｃｌａｉｍ、アサーションなどに自然な形で拡張され、通常はポストフィックス表記で書かれる。構文Ｘの句に現れる変数の集合を、Ｖａｒｓ（Ｘ）と書く。
【００９６】
説明される実施態様では、セキュリティ言語は、３つの演繹ルールを含む。これから、この言語のセマンティックスを把握するためにこの３つの演繹ルールを提示する。各ルールは、ＡＣ，Ｄ｜＝Ａ  ｓａｙｓ  ｆａｃｔの形の前提の集合および単一の結果を有し、ここで、Ｖａｒｓ（ｆａｃｔ）＝φかつＤ∈｛０，∞｝である。直観的には、この演繹関係は、結果をアサーションコンテキストＡＣから導出できる場合に成り立つ。導出フラグＤ＝０の場合には、導出ルール（ｃａｎ  ａｓｓｅｒｔ）は、導出に使用されない。
【００９７】
条件セマンティックスルール６０８（１）は、次の通りである。
【００９８】
【数６】
2010503129.tif 000010
【００９９】
一般的な委任ディレクティブ動詞の「ｃａｎ  ａｓｓｅｒｔ」動詞実施態様を伴う委任セマンティックスルール６０８（２）は、次の通りである。
【０１００】
【数７】
2010503129.tif 000011
【０１０１】
別名セマンティックスルール６０８（３）は、次の通りである。
【０１０２】
【数８】
2010503129.tif 000012
【０１０３】
ルール（ｃｏｎｄ）は、定数によって置換されたすべての自由変数と一致するＡＣ内のアサーションの演繹を可能にする。説明される厳密な論理実施態様では、条件ｆａｃｔは、演繹可能でなければならず、置換は、やはり制約（１つまたは複数）を有効にしなければならない。委任フラグＤは、すべての条件ｆａｃｔに伝搬される。
【０１０４】
言い換えると、アサーションコンテキストＡＣ、委任フラグＤ、プリンシパルＡ、および置換θを与えられれば、次のすべてが成り立つ場合に、「ＡＣ，Ｄ｜＝Ａ  ｓａｙｓ  ｆａｃｔ  θ」を導出することができる。  
（１）アサーションコンテキストＡＣ内にルール「Ａ  ｓａｙｓ  ｆａｃｔ  ｉｆ  ｆａｃｔ1，…，ｆａｃｔk，ｃ」があり、
（２）リスト「ｆａｃｔ1」，…，「ｆａｃｔk」内の「ｆａｃｔi」ごとに「ＡＣ，Ｄ｜＝Ａ  ｓａｙｓ  ｆａｃｔi  θ」を導出することができ、
（３）制約「ｃθ」が有効であり、
（４）ｆａｃｔ「ｆａｃｔ  θ」がグラウンドである。
【０１０５】
ルール（ｃａｎ  ａｓｓｅｒｔ）は、Ａによって作られたｃａｎ  ａｓｓｅｒｔアサーションをＢによって作られた一致するアサーションと組み合わせることによって、Ａによって作られたアサーションを演繹する。説明される厳密な論理実施態様では、このルールは、委任フラグが∞である時に適用される。Ｂによって作られた一致するアサーションは、Ａのｃａｎ  ａｓｓｅｒｔアサーションから入手される委任フラグＤを用いて証明されなければならない。
【０１０６】
言い換えると、アサーションコンテキストＡＣ、プリンシパルＡ、およびファクトｆａｃｔを与えられれば、次の両方が成り立つようになるプリンシパルＢおよび委任フラグＤがある場合に、「ＡＣ，∞｜＝Ａ  ｓａｙｓ  ｆａｃｔ」を導出することができる。  
（１）「ＡＣ，∞｜＝Ａ  ｓａｙｓ  Ｂ  ｃａｎ  ａｓｓｅｒｔD  ｆａｃｔ」を導出することができ、
（２）「ＡＣ，Ｄ｜＝Ｂ  ｓａｙｓ  ｆａｃｔ」を導出することができる。
【０１０７】
ルール（ａｌｉａｓ）は、Ｃについて成り立つすべてのｆａｃｔがＢについても成り立つことを述べる。
【０１０８】
言い換えると、アサーションコンテキストＡＣ、委任フラグＤ、プリンシパルＡ、Ｂ、およびＣ、ならびに動詞句「ｖｅｒｂｐｈｒａｓｅ」を与えられれば、次の両方が成り立つ場合に、「ＡＣ，Ｄ｜＝Ａ  ｓａｙｓ  Ｂ  ｖｅｒｂｐｈｒａｓｅ」を導出することができる。  
（１）「ＡＣ，Ｄ｜＝Ａ  ｓａｙｓ  Ｃ  ｖｅｒｂｐｈｒａｓｅ」を導出することができ、
（２）「ＡＣ，Ｄ｜＝Ａ  ｓａｙｓ  Ｂ  ａｌｉａｓ  Ｃ」を導出することができる。
【０１０９】
次の命題は、演繹関係の基本プロパティを述べ、上のルールに対する帰納によって確立される。  
命題２．３  ＡＣ，Ｄ｜＝Ａ  ｓａｙｓ  ｆａｃｔならば、Ｖａｒｓ（ｆａｃｔ）＝φである。  
命題２．４  ＡＣ，０｜＝Ａ  ｓａｙｓ  ｆａｃｔならば、ＡＣ，∞｜＝Ａ  ｓａｙｓ  ｆａｃｔである。  
命題２．５  ＡＣ1，Ｄ｜＝Ａ  ｓａｙｓ  ｆａｃｔならば、すべてのＡＣ2について、ＡＣ1  ∪  ＡＣ2，Ｄ｜＝Ａ  ｓａｙｓ  ｆａｃｔが成り立つ。  
命題２．６  ＡＣAが、その発行者がＡであるＡＣ内のすべてのアサーションの集合であるものとする。ＡＣA，０｜＝Ａ  ｓａｙｓ  ｆａｃｔである場合に限って、ＡＣ，０｜＝Ａ  ｓａｙｓ  ｆａｃｔである。  
【０１１０】
３  認可クエリ
認可要求は、アサーションコンテキスト（ローカルアサーションならびにインポートされたアサーションを含む）を照会することによって判断される。論理言語の説明される実施態様では、認可クエリに、否定を含む論理結合子によって組み合わされた、Ａ  ｓａｙｓ  ｆａｃｔおよび制約ｃの形の原子的クエリのコレクションを含めることができる。例示的な認可クエリ構文６０６は、次の通りである。
【０１１１】
【表３】
2010503129.tif 000013
【０１１２】
結果のクエリ言語は、原子的クエリだけが考慮される他の論理ベースの言語より表現力がある。たとえば、義務、しきい値、および拒否ポリシの分離を、否定および制約を用いて原子的クエリを構成することによって表すことができる。説明される実施態様では、否定は、アサーション言語内では許容されない。というのは、再帰言語との否定の結合が、意味論的曖昧さをもたらし、しばしば、より高い計算的複雑さまたは決定不可能性という結果になるからである。否定の使用を認可クエリのレベルに制限する（これらの特徴をアサーション言語自体に追加するのではなく）ことによって、否定が再帰から効果的に分離され、これによって、通常は否定に関連する問題が回避される。
【０１１３】
クエリのセマンティックスは、関係
【０１１４】
【数９】
2010503129.tif 000014
【０１１５】
によって定義される。次では、εが、空の置換であるものとする。否定されたクエリおよび制約が、グラウンド化されることと、第２のクエリが第１のクエリの結果によってインスタンス化される場合があるので、合接が交換可能ではないこととに留意されたい。
【０１１６】
【数１０】
2010503129.tif 000015
【０１１７】
クエリｑおよび認可コンテキストＡＣを与えられれば、認可アルゴリズムは、
【０１１８】
【数１１】
2010503129.tif 000016
【０１１９】
になるすべての置換θの集合を返さなければならない。クエリがグラウンドである場合には、回答集合は、空である（「ｎｏ」を意味する）か、空の置換εを含むシングルトン集合である（「ｙｅｓ」を意味する）かのいずれかになる。クエリが変数を含む場合には、回答集合内の置換は、クエリ木を作る変数割り当てのすべてである。
【０１２０】
次のセクションすなわちセクション４では、変数割り当てのこの集合が有限であり、意味があることを保証する安全性条件を説明する。下のセクション９で、認可クエリを評価するアルゴリズムを与える。
【０１２１】
認可クエリテーブル
概念上、認可クエリは、ローカルポリシの一部であり、命令的コードとは別に保持することができる。セキュリティ言語の説明される実施態様では、ローカルアサーションコンテキストに属する認可クエリは、認可クエリテーブルと呼ばれる単一の場所に保持される。このテーブルは、パラメータ化されたメソッド名をクエリにマッピングすることによって、認可クエリへのインターフェースを提供する。要求時に、リソースガードは、このテーブルによって認可クエリにマッピングされるメソッドを呼び出し（クエリを直接に発行するのではなく）、次に、この認可クエリが、アサーションコンテキストを照会するのに使用される。
【０１２２】
たとえば、認可クエリテーブルは、次のマッピングを含むことができる。
【０１２３】
【数１２】
2010503129.tif 000017
【０１２４】
たとえば、Ａｌｉｃｅが、支払いＰａｙｍｅｎｔ４７を認可することを試みる場合に、リソースガードは、ｃａｎＡｕｔｈｏｒｉｚｅＰａｙｍｅｎｔ（Ａｌｉｃｅ，Ｐａｙｍｅｎｔ４７）を呼び出し、これが、次のクエリをトリガする。
【０１２５】
【数１３】
2010503129.tif 000018
【０１２６】
結果の回答集合（要求が拒否されなければならない場合には空集合、またはｉｄの変数割り当てのいずれか）が、リソースガードに返され、次に、このリソースガードは、認可判断に従ってポリシを実施することができる。
【０１２７】
４  安全性
セキュリティ言語の例示的な実施態様では、認可アルゴリズムは、入力が何であろうと、終了し、説明されているセマンティックスに関する回答の完全な集合を返すことを要求される。さらなる制限なしには、これを保証することはできない。というのは、制約領域が制約コンパクトではないからである。したがって、説明される実施形態では、比較的単純で純粋に構文的な制限が、アサーションおよびクエリに対して強制される。
【０１２８】
定義４．１  （アサーション安全性チェック６１０（図６の））：Ａ  ｓａｙｓ  ｆａｃｔ  ｉｆ  ｆａｃｔ1，…，ｆａｃｔn，ｃがアサーションであるものとする。変数ｘ∈Ｖａｒｓ（ｆａｃｔ）は、ｘ∈Ｖａｒｓ（ｆａｃｔ1）∪…∪Ｖａｒｓ（ｆａｃｔn）の場合に限って安全である。
【０１２９】
アサーションＡ  ｓａｙｓ  ｆａｃｔ  ｉｆ  ｆａｃｔ1，…，ｆａｃｔn，ｃは、次の場合に限って安全である。
【０１３０】
１．ｆａｃｔがフラットである場合には、Ｖａｒｓ（ｆａｃｔ）内のすべての変数は安全であり、
そうではない（すなわち、ｆａｃｔがｅ  ｃａｎ  ａｓｓｅｒｔD  ｆａｃｔ’の形である）場合には、ｅのすべての変数は安全である、あるいは、より具体的には、ｅは安全な変数または定数であり、
２．Ｖａｒｓ（ｃ）⊆Ｖａｒｓ（ｆａｃｔ）∪Ｖａｒｓ（ｆａｃｔ1）∪…∪Ｖａｒｓ（ｆａｃｔn）であり、
３．ｆａｃｔ1，…，ｆａｃｔnがフラットである。
【０１３１】
安全なアサーションのいくつかの例は、次の通りである。
【０１３２】
【数１４】
2010503129.tif 000019
【０１３３】
安全でないアサーションのいくつかの例は、次の通りである。
【０１３４】
【数１５】
2010503129.tif 000020
【０１３５】
安全性条件は、下のセクション８で説明する論理言語変換の評価が、すべての場合に終了し、完全であることを保証する。さらに、安全性条件は、セクション８の評価アルゴリズム内での制約の単純な処理を可能にする。というのは、クエリがフラットである限り、条件述部が処理される時に制約のすべての変数が完全にインスタンス化され、したがって制約を伝搬させる必要がなく、複雑な制約解決アルゴリズムを実装する必要がないからである。
【０１３６】
ここで、アサーションコンテキストのアサーションが安全であるならば置換の集合が有限であることを保証する、認可クエリに対する安全性条件を定義する。さらに、この条件は、セクション９で定義される、合接の伝搬に関する左から右への評価ルールを仮定して、ｎｏｔ（ｑ）  ｏｒ  ｃの形のサブクエリが評価時にグラウンドになることを保証する。
【０１３７】
まず、形
【０１３８】
【数１６】
2010503129.tif 000021
【０１３９】
の判定を伴う演繹関係
【０１４０】
【数１７】
2010503129.tif 000022
【０１４１】
を定義し、ここで、ｑはクエリであり、ＩおよびＯは変数の集合である。直観的には、集合Ｉは、クエリのコンテキストによってグラウンド化される変数を表し、Ｏは、クエリによってグラウンド化される変数を表す。
【０１４２】
次の演繹関係は、推論ルールに基づく認可クエリに対する構文チェック６１２（図６の）を提供する。一番上が証明される場合に、一番下も証明されると考えることができる。
【０１４３】
安全なアサーション推論ルールは、
【０１４４】
【数１８】
2010503129.tif 000023
【０１４５】
である。
【０１４６】
安全な合接推論ルールは、
【０１４７】
【数１９】
2010503129.tif 000024
【０１４８】
である。
【０１４９】
安全な離接推論ルールは、
【０１５０】
【数２０】
2010503129.tif 000025
【０１５１】
である。
【０１５２】
安全な否定推論ルールは、
【０１５３】
【数２１】
2010503129.tif 000026
【０１５４】
である。
【０１５５】
安全な制約推論ルールは、
【０１５６】
【数２２】
2010503129.tif 000027
【０１５７】
である。
【０１５８】
定義４．２  （認可クエリ安全性６１２（図６の））：認可クエリｑは、
【０１５９】
【数２３】
2010503129.tif 000028
【０１６０】
になる変数の集合Ｏが存在する場合に限って安全である。
【０１６１】
安全性のチェックは、すべてのサブクエリを再帰的にトラバースし、これによって集合Ｏ（クエリおよびＩによって必ず一意に決定される）を構築することによって行うことができる。
【０１６２】
安全なクエリおよび安全でないクエリの例を、下の表に示す。次の例では、「，」および「ｏｒ」は、左側結合である。
【０１６３】
【表４】
2010503129.tif 000029
【０１６４】
図７は、認可クエリ評価が効率的に完了することを保証するためにセキュリティ言語の安全性をチェックする方法の例を示す流れ図７００である。流れ図７００は、３つの「主」ブロック７０２〜７０６および４つの「副」ブロック７０２（１）／（２）／（３）および７０４（１−５）を含む。流れ図７００のアクションは、他の環境内でおよびさまざまなハードウェア／ソフトウェア／ファームウェア組合せを用いて実行することができるが、図１〜６の特徴、コンポーネント、および態様の一部が、この方法の例を例示するのに使用される。
【０１６５】
説明される実施態様では、ブロック７０２で、アサーションコンテキストのアサーションの安全性をチェックする。たとえば、定義４．１を、アサーションコンテキストＡＣの各アサーションに適用することができる。したがって、ブロック７０２（１）で、アサーションの初期変数が安全であることを検証する。たとえば、定義４．１のパート（１）を適用することができる。たとえば、初期変数は、ｆａｃｔの変数（ｆａｃｔがフラットである場合）または式ｅの変数（ｆａｃｔがフラットではない場合）である。
【０１６６】
ブロック７０２（２）で、制約変数もアサーション内の他のどこかに存在することを検証する。たとえば、定義４．１のパート（２）を適用することができる。ブロック７０２（３）で、条件ｆａｃｔがフラットであることを検証する。たとえば、定義４．１のパート（３）を適用することができる。
【０１６７】
ブロック７０４で、認可クエリの安全性をチェックする。たとえば、定義４．２を認可クエリに適用することができる。ブロック７０４（１−５）で、認可クエリの構文に依存して、安全推論ルールのうちの１つまたは複数を認可クエリに適用して、準拠を確認し、クエリの安全性を保証する。例示的な推論ルールは、アサーション、合接、離接、否定、および制約である。
【０１６８】
アサーションコンテキストがそのチェックに合格しない（ブロック７０２で）または認可クエリがそのチェックに合格しない（ブロック７０４で）場合には、終了しないか完全ではないアサーションコンテキストおよび／または認可クエリを評価する試みを避けるために、評価アルゴリズムを異常終了することができる。安全性が成功してチェックされた（ブロック７０２および７０４）後に、ブロック７０６で、認可クエリをアサーションコンテキストと共に評価することができる。  
【０１６９】
５  アサーションの満了および撤回
セキュリティ言語の説明される実施態様では、満了日付を、通常の動詞句パラメータとして表すことができる。
【０１７０】
【数２４】
2010503129.tif 000030
【０１７１】
時々、満了日付を指定するか、それ自体の有効なタイムスパン要件をセットすることは、アクセプタ次第としなければならない。この場合に、アサーションは、日付を強制せずに日付を含めるだけとすることができる。
【０１７２】
【数２５】
2010503129.tif 000031
【０１７３】
その後、アクセプタは、アサーションの妥当性に関するそれ自体の時間ベースの制約を強制するのに日付を使用することができる。
【０１７４】
【数２６】
2010503129.tif 000032
【０１７５】
アサーションは、スケジューリングされた満了日付の前に撤回されなければならない場合がある。撤回が、明示的に信頼される発行者の暗号鍵が危険にさらされたことに起因して必要になる場合に、撤回は、もはやその鍵を信頼してはならないことを、頼る当事者に知らせることによって行われる。次に、頼る当事者は、その鍵への明示的な信頼を表すポリシを除去する。しかし、発行者が、その発行者が過去に行ったアサーションを撤回することを必要とすることの方が、はるかにより一般的である。これは、アサーションに関するプリンシパルに関連する暗号鍵が危険にさらされたこと、プリンシパルの関係のなんらかの変化（たとえば、雇用における変化）、またはプリンシパルの側での悪意のある振る舞いに起因する可能性がある。たとえば、上の例示的なアサーションは、Ａｌｉｃｅが大学を退学する場合には撤回されなければならない。
【０１７６】
すべてのアサーションＭが、識別子（たとえばシリアル番号）ＩＤMに関連すると仮定する。撤回（および撤回の委任）は、説明される実施態様では、動詞句ｒｅｖｏｋｅｓ  ＩＤMを有する撤回アサーションによって表すことができる。たとえば、撤回アサーション
【０１７７】
【数２７】
2010503129.tif 000033
【０１７８】
は、Ａによって発行され、識別子ＩＤを有するすべてのアサーションを、２００７年７月３１日より後に撤回する。
【０１７９】
定義５．１  （撤回アサーション）：アサーションは、安全であり、次の形である場合に撤回アサーションである。
【０１８０】
【数２８】
2010503129.tif 000034
【０１８１】
アサーションコンテキストＡＣと撤回アサーションＡＣrevの集合とを与えられ、ＡＣ  ∩  ＡＣrev＝φである場合には、認可クエリを評価する前に、ＡＣ内のＡＣrevによって撤回されるすべてのアサーションが除去される。フィルタリングされたアサーションコンテキストは、次によって定義される。
【０１８２】
ＡＣ−｛Ｍ｜Ｍ∈ＡＣ，ＡはＭの発行者，ＡＣrev，∞｜＝Ａ  ｓａｙｓ  Ａ  ｒｅｖｏｋｅｓ  ＩＤM｝
【０１８３】
ＡＣおよびＡＣrevが互いに素であるという条件は、撤回アサーションを撤回できないことを意味する（少なくとも、セキュリティ言語の説明される実施態様ではできない）。撤回アサーションをお互いによって撤回できるようにすることは、論理プログラミングでの否定された本体述部（ｎｅｇａｔｅｄ  ｂｏｄｙ  ｐｒｅｄｉｃａｔｅｓ）と同一の問題および意味論的曖昧さを引き起こす。これらの問題は、形式的には、たとえば層化可能な撤回集合のみを許容することまたは明確な基礎を与えられたモデルを計算することによって克服可能ではあるが、これらの手法は、商用システムでの使用を奨励するのに十分に単純ではない。  
【０１８４】
６  論理分解を用いるセキュリティ言語変換の序説
本明細書で上述したセキュリティ言語の例示的な実施態様は、人間がよく理解できる形でセキュリティポリシを表す機構を提供する。さらに、このセキュリティ言語を、安全性についてチェックすることができる。しかし、セキュリティポリシを、認可判断を行うために評価する必要もある。
【０１８５】
そのために、既存の論理言語を活用することができる。長期にわたって開発されてきた、完全にテストされた既存の論理言語がある。これらの論理言語と共に使用できる役立つツールもある。例示的な適用可能な論理言語が、Ｄａｔａｌｏｇ、具体的には制約付きＤａｔａｌｏｇ（ｃｏｎｓｔｒａｉｎｅｄ  Ｄａｔａｌｏｇ）である。しかし、他の論理言語をその代わりに利用することができる。
【０１８６】
本明細書で、そのような既存の論理言語をセキュリティ言語と共に使用することを可能にする技法および機構を説明する。セキュリティ言語を、セクション７で説明するように、論理言語に変換することができる。セクション８では、論理言語で実行されるテーブル化を用いる評価アルゴリズムを説明する。この評価アルゴリズムは、論理言語で証明グラフを作ることができる。セクション９では、論理言語を反映する証明グラフをセキュリティ言語を反映する証明グラフに変換する技法を説明する。したがって、この評価アルゴリズムを含む認可プロセスを、セキュリティ言語に関して分析することができる。  
【０１８７】
７  論理言語への変換
説明されるセキュリティ言語の例示的なアサーションセマンティックスは、セクション２の３つの演繹ルールによって定義される。このセマンティックスは、既に提案した、ある形の形式論理への変換に関して定義されたセマンティックスより理解でき、直観的である。それでも、このセマンティックスは、セキュリティ言語アサーションコンテキストを同等の論理言語プログラムに効率的に変換できるようになるのに有用である。次に、既知の複雑さ結果（たとえば、多項式データ複雑さ）を活用し、変換された論理言語プログラムをクエリ評価に使用することができ、これをセクション８で説明する。
【０１８８】
これから、安全なアサーションコンテキストを同等の論理言語プログラムに変換するアルゴリズムを説明する。例としてのみ、安全なアサーションコンテキストを制約付きＤａｔａｌｏｇプログラムに変換する。次では、ｅ1  ｓａｙｓk  ｆａｃｔの形の式をＤａｔａｌｏｇ述部として扱い、ここで、ｋは、変数または０または∞のいずれかである。これは、述部名が、ｃａｎ  ａｓｓｅｒｔの下付き文字を含む、式内に現れるすべてのインフィックス演算子（ｓａｙｓ、ｃａｎ  ａｓｓｅｒｔ、ａｌｉａｓ、ｒｅｖｏｋｅｓ、および述部名）の文字列連結である、述部のシュガード表記と考えることができる。述部の引数は、これらのインフィックス演算子の間の集められた式である。たとえば、式
【０１８９】
【数２９】
2010503129.tif 000035
【０１９０】
は、
【０１９１】
【数３０】
2010503129.tif 000036
【０１９２】
の省略表現である。
【０１９３】
アルゴリズム７．１  アサーションコンテキストＡＣの変換は、次のように進む。
１．ｆａｃｔ0がフラットである場合に、アサーション
【０１９４】
【数３１】
2010503129.tif 000037
【０１９５】
は、ルール
【０１９６】
【数３２】
2010503129.tif 000038
【０１９７】
に変換され、ここで、ｋは、新しい変数である。
【０１９８】
２．そうでない場合には、ｆａｃｔ0は、あるｎ≧１について、
【０１９９】
【数３３】
2010503129.tif 000039
【０２００】
の形であり、ここで、ｆａｃｔはフラットである。
【０２０１】
ｉ∈｛０．．ｎ−１｝について
【０２０２】
【数３４】
2010503129.tif 000040
【０２０３】
【数３５】
2010503129.tif 000041
であることに留意されたい。アサーション
【０２０４】
【数３６】
2010503129.tif 000042
【０２０５】
は、次のようにｎ＋１個のＤａｔａｌｏｇルールに変換される。
【０２０６】
（ａ）Ｄａｔａｌｏｇルール
【０２０７】
【数３７】
2010503129.tif 000043
【０２０８】
を追加する。ここで、ｋは新しい変数である。
【０２０９】
（ｂ）ｉ∈｛１．．ｎ｝のそれぞれについて、Ｄａｔａｌｏｇルール
【０２１０】
【数３８】
2010503129.tif 000044
【０２１１】
を追加する。ここで、ｘは新しい変数である。
【０２１２】
３．最後に、
Ａ  ｓａｙｓk  ｅ  ｖｅｒｂｐｈｒａｓｅ：−  …
の形の上で作成されたＤａｔａｌｏｇルールのそれぞれについて、ルール
Ａ  ｓａｙｓk  ｘ  ｖｅｒｂｐｈｒａｓｅ：−
Ａ  ｓａｙｓk  ｘ  ａｌｉａｓ  ｅ，
Ａ  ｓａｙｓk  ｅ  ｖｅｒｂｐｈｒａｓｅ
を追加する。ここで、ｘは新しい変数である。ｋが、新しい変数ではなく、定数またはオリジナルルールからとられた変数のいずれかであることに留意されたい。
【０２１３】
図８は、セキュリティ言語を論理言語に変換する方法の例を示す流れ図８００である。流れ図８００は、７つのブロック８０２〜８１４を含む。流れ図８００のアクションは、他の環境内でおよびさまざまなハードウェア／ソフトウェア／ファームウェア組合せを用いて実行することができるが、図１〜６の特徴、コンポーネント、および態様の一部が、この方法の例を例示するのに使用される。流れ図８００は、少なくとも部分的に上のアルゴリズム７．１を表す。
【０２１４】
説明される実施態様では、ブロック８０２で、アサートされたｆａｃｔおよび０個以上の条件ｆａｃｔを有するセキュリティ言語アサーションが、アサーションコンテキストから抽出される。ブロック８０４で、アサートされたｆａｃｔがフラットであるかどうかを判定する。そうである場合には、ブロック８０６で、アサーションを、主ｆａｃｔおよび０個以上の付帯条件を有する論理言語ルールに変換する。たとえば、アルゴリズム７．１のパート１を実行することができる。主ｆａｃｔは、アサートされたｆａｃｔに対応し、付帯条件は、条件ｆａｃｔに対応する。これらの異なる用語は、セキュリティ言語アサーションコンテキストの諸部分からの論理言語プログラムの異なる部分の逐語的区別を明瞭にするために使用されるものである。
【０２１５】
その一方で、アサートされたｆａｃｔがフラットではないと判定される（ブロック８０４で）場合には、セキュリティアサーションは、ブロック８０８および８１０によって変換される。ｆａｃｔがフラットではない場合には、アサーションは、少なくとも１つの委任ディレクティブ動詞（たとえば、ｃａｎ  ａｓｓｅｒｔ、ｃａｎ  ｓａｙなど）を伴う委任アサーションである。
【０２１６】
ブロック８０８で、主ｆａｃｔおよび０個以上の付帯条件を有する論理言語ルールを追加する（たとえば、成長する論理言語プログラムに）。たとえば、アルゴリズム７．１のパート２（ａ）を実行することができる。ブロック８１０で、セキュリティ言語アサーションのアサートされたｆａｃｔの委任ディレクティブ動詞ごとに、無制限の委任深さと委任を表す新しい変数とを有する論理言語ルールを追加する。より具体的には、この新しい変数は、その権利が委任されようとしているプリンシパルを表す。たとえば、アルゴリズム７．１のパート２（ｂ）を実行することができる。
【０２１７】
ブロック８１２で、作成された（ブロック８０６または８０８／８１０で）式を伴うアサートされたｆａｃｔを有する論理言語ルールごとに、別名機能とその別名のオブジェクトを表す新しい変数とを有するもう１つの論理言語ルールを論理言語プログラムに追加する。たとえば、アルゴリズム７．１のパート３を実行することができる。ブロック８１４で、これによって、セキュリティ言語アサーションコンテキストの入力アサーションに対応する論理言語プログラムセグメントを作る。流れ図８００のアクションは、所与のアサーションコンテキスト内のアサーションごとに繰り返される。
【０２１８】
アサーションの例示的な変換は、次の通りである。
【０２１９】
【数３９】
2010503129.tif 000045
【０２２０】
は、ステップ２ａおよび２ｂで、
【０２２１】
【数４０】
2010503129.tif 000046
【０２２２】
に変換される。
最後に、ステップ３で、次のルールも追加される。
【０２２３】
【数４１】
2010503129.tif 000047
【０２２４】
定義７．２  （結果演算子）：直接結果演算子（ｉｍｍｅｄｉａｔｅ  ｃｏｎｓｅｑｕｅｎｃｅ  ｏｐｅｒａｔｏｒ）ＴPは、グラウンド化された述部の集合の間の関数であり、次のように定義される。
【０２２５】
【数４２】
2010503129.tif 000048
【０２２６】
演算子ＴPは、単調かつ連続であり、その最小の固定点ＴPw（φ）は、Ｐから演繹可能なすべてのグラウンドｆａｃｔを含む。
【０２２７】
命題７．３  （健全さおよび完全さ）：Ｐが、アサーションコンテキストＡＣのＤａｔａｌｏｇ変換であるものとする。ＡＣ，Ｄ｜＝Ａ  ｓａｙｓ  ｆａｃｔの場合に限って、Ａ  ｓａｙｓD  ｆａｃｔ∈ＴPw（φ）である。  
【０２２８】
８  テーブル化を用いる論理言語評価
上のセクションでは、安全なセキュリティ言語アサーションの集合を、同等の少なくとも部分的に安全な制約付きＤａｔａｌｏｇプログラムにどのように変換できるかを示した。演繹データベースのコンテキストでは、ボトムアップ手法が、Ｄａｔａｌｏｇ評価に最も頻繁に使用される。その場合に、プログラムのモデルまたはその最小固定点（安全性に起因して有限である）は、一度だけ計算される。これは、完全で終了する手順であるという利益を有し、クエリ評価は、固定点が構築されたならば高速である。
【０２２９】
しかし、ボトムアップ評価は、セキュリティ言語の説明される実施態様にはそれほど適切ではない。というのは、アサーションコンテキストが一定ではないからである。実際に、アサーションコンテキストは、異なる要求の間で完全に異なる場合がある。すべての要求に関するモデルの計算は、関連しないゴールの評価をもたらすので効率的ではない。さらに、我々が関心を持つクエリは、通常、完全にまたは部分的にインスタンス化され、したがって、トップダウンのゴール指向手法が、より適切であると思われる。
【０２３０】
最も広く知られたトップダウン評価アルゴリズムは、Ｐｒｏｌｏｇで使用されるＳＬＤ導出である。残念ながら、ＳＬＤ導出は、述部の一部が再帰的定義を有する場合に、安全なＤａｔａｌｏｇプログラムに関してさえ無限ループに入る可能性がある。この問題は、深さ優先ではなく幅優先検索戦略が使用される場合であっても残り、ループは、ＳＬＤ探索木が無限なので発生する。テーブル化またはメモイング（ｍｅｍｏｉｎｇ）は、なんらかのボトムアップ技法をトップダウン分解戦略に組み込むことによって終了を保証する手法である。基本的な発想は、出会ったサブゴールおよびその回答のテーブルを保持することによって無限探索木を枝刈りし、テーブル内にまだ存在しない場合に限ってサブゴールを計算することである。
【０２３１】
ここで、テーブル化に基づく決定性アルゴリズムを説明し、これを、論理言語プログラムに変換済みのセキュリティ言語アサーションに適用する。２つのグローバルテーブルが、評価プロセス中に保持される。
【０２３２】
図９は、テーブル化を用いる例示的な決定的評価アルゴリズム９００を示すブロック図である。評価アルゴリズム９００は、５つのモジュール９０２すなわち、ＱＵＥＲＹモジュール９０２（１）、ＲＥＳＯＬＶＥ−ＣＬＡＵＳＥモジュール９０２（２）、ＲＥＳＯＬＶＥモジュール９０２（３）、ＰＲＯＣＥＳＳ−ＡＮＳＷＥＲモジュール９０２（４）、およびＰＲＯＣＥＳＳ−ＳＵＢＧＯＡＬモジュール９０２（５）を含む。評価アルゴリズム９００は、２つのテーブル９０４すなわち、Ａｎｓテーブル９０４（１）およびＷａｉｔテーブル９０４（２）をも含む。
【０２３３】
第１のテーブルすなわちＡｎｓテーブル９０４（１）は、述部をグラウンド述部の集合にマップする。サブゴールＰ（インスタンス化されていないか、部分的にまたは完全にインスタンス化された）が計算される場合に、Ｐは、Ａｎｓの領域に追加され、どの時点でも、Ａｎｓ（Ｐ）は、それまでに見つかったＰに対する回答（これらはＰのグラウンドインスタンスである）の集合を返す。評価プロセスの終りに、Ａｎｓは、ルートゴールを含むすべての出会ったサブゴールに対する完全な回答を含む。
【０２３４】
第２のテーブルは、Ｗａｉｔテーブル９０４（２）である。このテーブルは、述部Ｐを
【０２３５】
【数４３】
2010503129.tif 000049
【０２３６】
の形のサブゴールおよび述部
【０２３７】
【数４４】
2010503129.tif 000050
【０２３８】
にマップする。このサブゴールは、次のように解釈することができる。Ｐは、証明木のトップレベル述部であり、Ｐ0は、次に解くべき述部であり、
【０２３９】
【数４５】
2010503129.tif 000051
【０２４０】
は、Ｐ0の後に解かなければならない述部のリストであり、ｃは、述部変数に対する制約であり、Ｓは、連続的に絞り込むことによってこれまでに見つかったインスタンス化を記憶するＰのインスタンスである。
【０２４１】
この評価アルゴリズムに関係する複数の用語および概念を、下で定義し、かつ／または説明する。
【０２４２】
定義８．１  置換ρは、θ＝ρθ’になる置換θ’が存在する場合に限って、θより一般的である。
【０２４３】
定義８．２  ＰおよびＱが、２つの述部であるものとする。置換θは、Ｐθ＝Ｑθである場合に限って、ＰおよびＱのユニファイヤ（ｕｎｉｆｉｅｒ）である。置換θは、ＰおよびＱの他のどのユニファイヤより一般的である場合に限って、ＰおよびＱの最も一般的なユニファイヤである。
【０２４４】
定義８．３  述部Ｐの変数リネーミングは、θがＰに現れる変数の集合上の順列を定義するようになる置換θである。
【０２４５】
２つの述部ＰおよびＱがユニファイ可能である場合に、ＰおよびＱは、変数リネーミングまで一意である、最も一般的なユニファイヤをも有する。これを、Ｍｇｕ（Ｐ，Ｑ）によって表す。最も一般的なユニファイヤを見つけることは、比較的単純であるが、線形時間で動作する、より複雑なアルゴリズムがある。
【０２４６】
追加の用語および概念を、下で定義し、かつ／または説明する。
定義８．４  ＰおよびＱが、２つの述部であるものとする。ある置換θについてＰ＝Ｑθである場合に限って、Ｐは、Ｑのインスタンスである。ＰがＱによって包含されるとも言い、Ｐ＝＞Ｑと書く。
【０２４７】
命題８．５  ＰおよびＱの最も一般的なユニファイヤが存在し、θがＰの変数リネーミングである場合に限って、Ｐ＝＞Ｑである。
【０２４８】
次の擬似コードは、評価アルゴリズムの例を提供するものである。これを、下でさらに説明する。
【０２４９】
【数４６】
2010503129.tif 000052
【０２５０】
１  ｉｆ  θ＝Ｍｇｕ（Ｐ0，Ｐ0’）が存在する  ａｎｄ  ｄ＝Ｓｉｍｐｌｉｆｙ（ｃθ）が充足可能である  ｔｈｅｎ
【０２５１】
【数４７】
2010503129.tif 000053
【０２５２】
２    ｉｆ  Ｐ0⇒Ｐ0’になるＰ0’∈Ｄｏｍ（Ａｎｓ）が存在する
【０２５３】
【数４８】
2010503129.tif 000054
【０２５４】
ルールの集合
【０２５５】
【数４９】
2010503129.tif 000055
【０２５６】
に関する述部Ｐに対する回答を見つけるために、当初に空のＡｎｓテーブルおよびＷａｉｔテーブルを用いて（すなわち、Ｄｏｍ（Ａｎｓ）＝Ｄｏｍ（Ｗａｉｔ）＝φ）、ルーチンＱＵＥＲＹ（Ｐ）を呼び出す。
【０２５７】
５つのモジュール９０２のそれぞれを、下で説明する。
【０２５８】
ＱＵＥＲＹ（モジュール９０２（１））は、ＲＥＳＯＬＶＥ−ＣＬＡＵＳＥ（Ｐ）を呼び出すことによって新しい証明木を産む。その呼出しの後に、Ａｎｓ（Ｐ）に、正しい完全な回答が投入される。
【０２５９】
ＲＥＳＯＬＶＥ−ＣＬＡＵＳＥ（モジュール９０２（２））は、ＲＥＳＯＬＶＥを呼び出すことによって、Ｆｒｅｓｈ（Ｐ）に対して
【０２６０】
【数５０】
2010503129.tif 000056
【０２６１】
に含まれる各ルールを分解する。関数Ｆｒｅｓｈ（Ｐ）は、
【０２６２】
【数５１】
2010503129.tif 000057
【０２６３】
のどこにも現れない変数を新しいものにするために、Ｐに含まれるすべての変数をリネームする。
【０２６４】
ＲＥＳＯＬＶＥ（モジュール９０２（３））は、
【０２６５】
【数５２】
2010503129.tif 000058
【０２６６】
の形のサブゴールおよび述部Ｐ’0をパラメータとしてとる。ＲＥＳＯＬＶＥ内のＳｉｍｐｌｉｆｙ関数は、制約に対して、すべての種類の、同等性を保存する単純化（たとえば、（Ｆａｌｓｅ，ｃ）≡Ｆａｌｓｅ）を実行することができる。最低限でも、Ｓｉｍｐｌｉｆｙ関数は、グラウンド制約を真または偽に単純化しなければならない。行１に対する充足可能性チェックを過剰近似することは安全である。すなわち、「偽」は、ｃθが実際に充足不能である場合に限って返されなければならないが、「真」は、Ｓｉｍｐｌｉｆｙ（ｃθ）が完全にはインスタンス化されない限り、ｃθが充足不能である場合であっても返されてよい。したがって、近似充足可能性チェックの単純な実施態様は、単純化された制約がまだ完全にはインスタンス化されていない時に、必ず「真」を返すことができる。
【０２６７】
ユニフィケーションおよび充足可能性チェックが成功する場合に、２つのサブケースがある。リスト
【０２６８】
【数５３】
2010503129.tif 000059
【０２６９】
が空であり（この場合には、ＳθがＰに対する回答であることがわかる）、さらに、これは、安全性に起因して、グラウンド回答である。その後、ＰＲＯＣＥＳＳ−ＡＮＳＷＥＲを呼び出して、この回答をさらに処理する。そうでない場合には、次に解くべき述部としてリスト内の最初の述部を選ぶことによって、左から右への評価戦略を使用し、第１パラメータ以外のすべてのパラメータに置換θをプッシュしてＰＲＯＣＥＳＳ−ＳＵＢＧＯＡＬを呼び出す。第１パラメータＰは、オリジナルゴールが何であったかを記憶するのに使用されるので、未変更のままにされる。仮の解Ｓが、Ｓθに絞り込まれる。
【０２７０】
ＰＲＯＣＥＳＳ−ＡＮＳＷＥＲ（モジュール９０２（４））は、Ｐに対する回答をとり、Ａｎｓテーブル９０４（１）を更新する。Ｗａｉｔテーブル９０４（２）は、この回答を待っているすべての一時停止されたサブゴールを含む。各一時停止されたサブゴールは、新たに見つかった回答と一緒にＲＥＳＯＬＶＥを呼び出すことによって再開される。
【０２７１】
ＰＲＯＣＥＳＳ−ＳＵＢＧＯＡＬ（モジュール９０２（５））は、次に解くべき述部としてＰ0を有するサブゴールを引数としてとり、それを包含するＡｎｓテーブル９０４（１）内の既存のサブゴールＰ’0が既にあるかどうかをチェックする。ある場合には、Ｐ’0の既存の回答を再利用することができ（ＲＥＳＯＬＶＥを呼び出すことによって）、したがって、Ｐ0の新しい証明木を開始する必要はない。さらに、サブゴールのコピーが、Ｐ’0のＷａｉｔエントリに追加され、その結果、Ｐ’0に対するすべての将来の回答も使用されるようになる。Ａｎｓテーブル９０４（１）内のどのエントリもＰ0を包含しない場合に限って、新しい証明木が、ＲＥＳＯＬＶＥ−ＣＬＡＵＳＥへの呼出しによって産み出される。その前に、サブゴールを含むＰ0のエントリが、Ｗａｉｔテーブル９０４（２）内に作成される。
【０２７２】
追加の定義および定理を、下で説明する。
定義８．６
【０２７３】
【数５４】
2010503129.tif 000060
【０２７４】
は、呼出しが終了する場合に、等式なしのルールの集合
【０２７５】
【数５５】
2010503129.tif 000061
【０２７６】
ならびに当初は空のＡｎｓテーブルおよびＷａｉｔテーブル９０４のコンテキストでの呼出しＱＵＥＲＹ（Ｐ）の戻り値と定義される。そうでない場合には、
【０２７７】
【数５６】
2010503129.tif 000062
【０２７８】
は未定義である。
【０２７９】
定理８．７  （終了）：
【０２８０】
【数５７】
2010503129.tif 000063
【０２８１】
は、すべての部分的に安全なクエリＰについて定義され、有限である。
【０２８２】
定理８．８  （健全さおよび完全さ）：Ｐが、部分的に安全なクエリであるものとする。
【０２８３】
【数５８】
2010503129.tif 000064
【０２８４】
は、ＴPw（φ）に含まれるＰのすべてのグラウンドインスタンスの集合と等しい。
【０２８５】
図１０は、評価アルゴリズム中に作られ、グラフフラグメント１００６を含む、例示的な論理言語証明グラフ１０００のブロック図である。図示されているように、論理言語証明グラフ１０００は、複数の節点（node）１００２および複数の有向辺（directed edge）１００４を含む。具体的に言うと、論理言語証明グラフ１０００は、１０個の節点１００２（１…１０）を含む。しかし、論理言語証明グラフ１０００には、任意の個数の節点１００２および任意の個数の有向辺１００４を含めることができる。２つの有向辺１００４（１）および１００４（２）は、明示的にラベルを付けられている。有向辺１００４は、節点１００２の間の論理演繹を示す。
【０２８６】
セキュリティポリシのテストおよびトラブルシューティングを行う時には、認可判断の根拠を見られることが有用である場合がある。これは、上のセクション２のセマンティックルールシステムに従って構築された対応する証明グラフのビジュアル表現および／または逐語表現とすることができる。評価中に作られる証明グラフを、監査のためにアーカイブすることもできる。
【０２８７】
論理言語証明グラフ１０００の葉節点は、長方形の節点１００２（４）、１００２（５）、１００２（６）、１００２（８）、１００２（９）、および１００２（１０）によって表される。非葉節点は、円形の節点１００２（１）、１００２（２）、１００２（３）、および１００２（７）によって表される。円は、付帯条件（たとえば、本体述部）を提供する節点である。論理言語証明グラフ１０００の長方形の葉節点は、オリジナルのアサーションコンテキストからのアサーションから変換されたルールである。他の節点は、導出されたステートメントであり、これらは、上で説明した決定的テーブル化アルゴリズムが評価に使用される場合には回答テーブル（たとえば、Ａｎｓテーブル９０４（１））からとられる。
【０２８８】
論理言語証明グラフ１０００は、例示的なフラグメント１００６に分離される。具体的に言うと、３つのフラグメント１００６（１、２、３）が示されているが、証明グラフを、任意の個数のフラグメント１００６に分離することができる。各フラグメント１００６は、全体的な証明グラフの構造の一部を形成する。その結果、各フラグメント１００６は、節点（１つまたは複数）１００２および有向辺（１つまたは複数）１００４を含む。
【０２８９】
セキュリティ言語に馴染みのある誰かが分析、トラブルシューティング、および／または監査などを実行するために、論理言語証明グラフ１０００を、対応するセキュリティ言語証明グラフ（全体として別々には図示せず）に変換することができる。この変換をもたらすために、パターンマッチングプロセスが実行される。論理言語フラグメント１００６が、対応するセキュリティ言語フラグメントとマッチングされる。
【０２９０】
説明される実施態様では、パターンマッチングプロセスで使用できるサンプルセキュリティ言語フラグメントは、それぞれ、セキュリティ言語からのセマンティックスルールにめいめいが関連する。論理言語フラグメントとセキュリティ言語フラグメントとの間の例示的なフラグメント対応を、下で図１２Ａ、１２Ｂ、１３Ａ、１３Ｂ、１４Ａ、および１４Ｂを参照して説明する。
【０２９１】
説明される特定の例示的な実施態様では、上で図９を参照して提示したアルゴリズムを変更して、クエリ評価中にＤａｔａｌｏｇ証明グラフを構築することができる。証明グラフは、有向非循環グラフである。クエリに対する回答ごとに、グラフ内に１つのルート節点がある。すべての非葉節点が、Ａ  ｓａｙｓD  ｆａｃｔの形のグラウンドＤａｔａｌｏｇ述部であり、子節点としてＤａｔａｌｏｇルール、インスタンス化された条件ｆａｃｔ、およびインスタンス化された制約を有する。葉節点は、ＡＣ内のＤａｔａｌｏｇルールまたは有効なグラウンド制約のいずれかである。例を、図１２Ａ、１３Ａ、および１４Ａの左パネルとして示す）。
【０２９２】
上のアルゴリズム７．１の実行中に、各生成されるＤａｔａｌｏｇルールが、それが生成されるアルゴリズムステップ（すなわち、１、２（ａ）、２（ｂ）、または３）を用いてラベルを付けられる場合に、Ｄａｔａｌｏｇ証明グラフは、対応するセキュリティ論理証明グラフへの変換に十分な情報を含む。
【０２９３】
図１１は、論理言語証明グラフをセキュリティ言語証明グラフに変換する方法の例を示す流れ図１１００である。流れ図１１００は、５つのブロック１１０２〜１１１０を含む。流れ図１１００のアクションは、他の環境内でおよびさまざまなハードウェア／ソフトウェア／ファームウェア組合せを用いて実行することができるが、図１〜１０の特徴、コンポーネント、および態様の一部が、この方法の例を例示するのに使用される。
【０２９４】
説明される実施態様では、ブロック１１０２で、論理評価中の論理言語を反映する第１証明グラフを作る。たとえば、論理言語証明グラフ１０００を、論理評価中に作ることができる。論理評価は、変換を介してセキュリティ言語アサーションコンテキストから導出される論理言語プログラムに対して実施される。
【０２９５】
ブロック１１０４で、第１証明グラフのフラグメントを識別する。たとえば、論理言語証明グラフ１０００のフラグメント１００６を識別することができる。
【０２９６】
ブロック１１０６で、論理言語を反映する第１証明グラフのフラグメントを、セキュリティ言語を反映する第２証明グラフの対応するフラグメントに変換する。たとえば、論理言語（たとえば、Ｄａｔａｌｏｇなど）を反映する論理言語証明グラフ１０００のフラグメント１００６を、セキュリティ言語（たとえば、ポリシアサーションセキュリティ言語）を反映する第２証明グラフの対応するフラグメントに変換する。たとえば、第１証明グラフのフラグメントの論理言語パターンを、複数の可能なセキュリティ言語パターンから選択された対応するセキュリティ言語パターンとマッチングすることができる。これらのセキュリティ言語パターンは、たとえば、セキュリティ言語のセマンティックスルールに関連するものとすることができる。
【０２９７】
ブロック１１０８で、フラグメントの識別およびそのフラグメントの変換を、第１証明グラフのフラグメントごとに繰り返す。たとえば、次のフラグメントの矢印１１１２によって示されるように、論理言語証明グラフ１０００の別のフラグメント１００６を識別し、セキュリティ言語証明グラフの対応するフラグメントに変換することができる。
【０２９８】
ブロック１１１０で、論理言語証明グラフをトラバースし、変換し終えたならば、セキュリティ言語を反映する第２証明グラフを出力する。第２証明グラフは、第１証明グラフのめいめいのフラグメントに対応するフラグメントを含む。セキュリティ言語を反映するこの第２証明グラフを、アーカイブし、かつ／または監査することもできる。
【０２９９】
図１２Ａおよび１２Ｂは、それぞれ、条件セマンティックスルールに関する論理言語および対応するセキュリティ言語の例示的な証明フラグメントのブロック図である。条件セマンティックスルールのセキュリティ言語証明グラフフラグメントサンプル１２００Ｂを、図１２Ｂに示す。評価中に作られる証明グラフ内に存在し得る対応する論理言語証明グラフ（たとえば、親を伴う証明節点）フラグメント１２００Ａを、図１２Ａに示す。楕円の節点は、証明された付帯条件を表し、長方形の節点は、ルールまたは制約を表す。これらのグラフフラグメント１２００は、アルゴリズム７．１の変換ステップ１または２（ａ）に関係する。
【０３００】
図１３Ａおよび１３Ｂは、それぞれ委任セマンティックスルールに関する論理言語および対応するセキュリティ言語の例示的な証明フラグメントのブロック図である。委任セマンティックスルールのセキュリティ言語フラグメントサンプル１３００Ｂを、図１３Ｂに示す。評価中に作られる証明グラフ内に存在し得る対応する論理言語フラグメント１３００Ａを、図１３Ａに示す。これらのグラフフラグメント１３００は、変換ステップ２（ｂ）に関係する。
【０３０１】
図１４Ａおよび１４Ｂは、それぞれ別名セマンティックスルールに関する論理言語および対応するセキュリティ言語の例示的な証明フラグメントのブロック図である。別名セマンティックスルールのセキュリティ言語フラグメントサンプル１４００Ｂを、図１４Ｂに示す。評価中に作られる証明グラフ内に存在し得る対応する論理言語フラグメント１４００Ａを、図１４Ａに示す。これらのグラフフラグメント１４００は、変換ステップ３に関係する。  
【０３０２】
９  認可クエリの評価
前のセクションからのアルゴリズムに基づいて、これから、セクション３で定義した複雑な認可クエリをどのように評価するかを説明することができる。次では、ＡＣが、アサーションコンテキストであり、
【０３０３】
【数５９】
2010503129.tif 000065
【０３０４】
が、そのＤａｔａｌｏｇ変換であり、εが、空の置換であるものとする。認可クエリに対する関数ＡｕｔｈＡｎｓACを、次のように定義する。
【０３０５】
【数６０】
2010503129.tif 000066
【０３０６】
次の定理は、ＡｕｔｈＡｎｓACが、安全な認可クエリを評価するアルゴリズムであることを示す。
【０３０７】
定理９．１  （認可クエリ評価の有限性、健全さ、および完全さ）：すべての安全なアサーションコンテキストＡＣおよび安全な認可クエリｑについて、
１．ＡｕｔｈＡｎｓAC（ｑ）が定義され、有限であり、
２．θ∈ＡｕｔｈＡｎｓAC（ｑ）の場合に限って
【０３０８】
【数６１】
2010503129.tif 000067
【０３０９】
である。
【０３１０】
図１〜１４Ｂのデバイス、アクション、態様、特徴、関数、プロシージャ、モジュール、データ構造、プロトコル、コンポーネントなどは、複数のブロックに分割された図で図示されている。しかし、図１〜１４Ｂが説明され、かつ／または図示される順序、相互接続、相互関係、レイアウトなどは、限定として解釈されることを意図されたものではなく、論理分解を用いるセキュリティ言語変換のための１つまたは複数のシステム、方法、デバイス、プロシージャ、媒体、装置、ＡＰＩ、プロトコル、配置などを実施するために、任意の個数のブロックを任意の形で変更し、組み合わせ、再配置し、補足し、省略することなどができる。
【０３１１】
システム、媒体、デバイス、方法、プロシージャ、装置、機構、方式、手法、プロセス、配置、および他の実施態様を、構造的、論理的、アルゴリズム的、および機能的な特徴に固有の言葉および／または図で説明してきたが、添付の特許請求の範囲で定義される本発明が、必ずしも上で説明された特定の特徴または動作に限定されないことを理解されたい。そうではなく、上で説明された特定の特徴および動作は、特許請求の範囲を実施する例示的な形として開示されたものである。
【図１】
2010503129.tif 000068
【図２】
2010503129.tif 000069
【図３】
2010503129.tif 000070
【図４】
2010503129.tif 000071
【図５】
2010503129.tif 000072
【図６】
2010503129.tif 000073
【図７】
2010503129.tif 000074
【図８】
2010503129.tif 000075
【図９】
2010503129.tif 000076
【図１０】
2010503129.tif 000077
【図１１】
2010503129.tif 000078
【図１２Ａ】
2010503129.tif 000079
【図１２Ｂ】
2010503129.tif 000080
【図１３Ａ】
2010503129.tif 000081
【図１３Ｂ】
2010503129.tif 000082
【図１４Ａ】
2010503129.tif 000083
【図１４Ｂ】
2010503129.tif 000084
【国際調査報告】
2010503129.tif 000085
2010503129.tif 000086