guide:history@ja

ガイド

Multics から Zanzibar へ

ケイパビリティリストと Multics の ACL から、RBAC と ABAC を経て、Zanzibar とそれに続くオープンソースのシステムまで、60 年にわたるアクセス制御の歩みを、各段階の一次資料とともにたどる。

事実確認日 論文の該当節 §2.1, §3.2.4, §4, §5

Zanzibar の論文は、自らの系譜を §5 関連研究 で述べている。データモデルについては Multics、UNIX、POSIX ACL、VMS、Taos を、ロールについては RBAC を、RPC API の背後に 1 つの ACL ストアを置くという考え方については Amazon、Google、Microsoft の IAM システムを、同程度の規模のシステムとしては Facebook の TAO を、一貫性の問題については Lamport クロック、Spanner、Chubby、ZooKeeper を引いている。このページは同じ系譜を時系列でたどる。

考え方はどのように Zanzibar へつながったか

最初期のマルチユーザーシステムは、誰が何に触れてよいかを決める必要があった。1966 年、Dennis と Van Horn は各計算に ケイパビリティ のリストを与えた。ケイパビリティとは、オブジェクトを指し、それに対する権利を付与する、偽造できないトークンである (Dennis and Van Horn)。Lampson の 1971 年のアクセス行列は、ケイパビリティとアクセス制御リストが同じ表を行ごとに格納するか列ごとに格納するかの違いにすぎないことを示した (Lampson)。Multics は列の見方をとり、すべてのセグメントとディレクトリが ACL を持った (Saltzer)。Zanzibar も ACL の側にあり、「このオブジェクトに誰が触れられるか」に答える。

その後、オペレーティングシステムはリストをより安価で粗いものにし、のちに再び豊かにした。論文自身がこの流れをたどっている。UNIX の初版では、ファイルのフラグが “whether owner and non-owner can read or write the file” (所有者と所有者以外がファイルを読み書きできるかどうか) を表す。第 4 版では “for owner, group, and others” (所有者、グループ、その他に対する) 読み取り・書き込み・実行のビットがある。POSIX ACL は “an arbitrary list of users and groups” (ユーザーとグループの任意のリスト) を加え、VMS は “supports ACL inheritance for files created within a directory tree” (ディレクトリツリー内に作成されたファイルに対する ACL の継承をサポートする) (§5)。権限、ユーザー、グループ、継承というこの 4 つの語が、Zanzibar のデータモデルがサポートしようとするものである。

1970 年代から、モデルはオブジェクトごとのリストから離れていった。Bell–LaPadula と Biba は、所有者ではなくシステムがラベルによって判定する。Zanzibar は任意アクセス制御であるため、これらは祖先ではなく対比の対象である。ロールベースアクセス制御 (1992 年) は、ユーザーと権限の間にロールを置いた。論文はロールが “are similar to Zanzibar relations” (Zanzibar の関係に似ている) と述べている (§5)。属性ベースの制御は NIST の 2014 年のガイド SP 800-162 で定義され、リクエスト時に属性から判定を計算する。関係ベースの制御は 2007 年に Gates が名付け、2011 年に Fong が形式化したもので、「メンバーである」や「親フォルダである」のような、合成できる関係から判定する (Fong)。論文は ReBAC という語を一度も使っていないが、そのリレーションタプルはそうしたグラフをなしている。

Google で新しかったのは規模と一貫性である。論文は、2019 年 7 月の時点で Zanzibar が “has been in production use for more than 5 years” (5 年以上本番で使われてきた) と述べている (§4)。したがって遅くとも 2014 年には稼働していたが、開始年を示す公開資料はない。Zanzibar は Calendar、Cloud、Drive、Maps、Photos、YouTube に使われている (§1)。論文が比較対象とする TAO は “eventual global consistency” (グローバルな結果整合性) を提供するのに対し、Zanzibar は “external consistency and snapshot reads with bounded staleness” (外部一貫性と有界な古さを伴うスナップショット読み取り) を提供し、それによって「new enemy」問題を防ぐ (§5)。Lamport クロックは、“require explicit participation of all “processes”” (すべての「プロセス」の明示的な参加を必要とする) うえに、Zanzibar のプロセスの一部は “external clients or even human users” (外部のクライアントや、人間のユーザーでさえある) ため、採用されなかった。Chubby は “high volumes of data, efficient range reads, or reads at a client-specified snapshot with bounded staleness” (大量のデータ、効率的な範囲読み取り、クライアントが指定した有界な古さのスナップショットでの読み取り) をサポートせず、ZooKeeper はノードをまたぐ外部一貫性も、有界な古さを伴うスナップショット読み取りも提供しない (§5)。保証を与えたのは Spanner とその TrueTime クロックである (Spanner, OSDI ’12)。

論文の公開後、ほかの開発者たちがこの設計をオープンソースで作り直した。Ory Keto は 2021 年にこの設計を中心に書き直され、SpiceDB、OpenFGA、Permify、Topaz がおよそ 18 か月以内に続いた。同じ時期に、ABAC の系譜にあるポリシーエンジンの OPA と Cedar が成熟し、2023 年に結成された OpenID Foundation の AuthZEN ワーキンググループが、アプリケーションが認可エンジンに判定を問い合わせる方法を標準化した。その Authorization API 1.0 は 2026 年 1 月に OpenID Final Specification となった。各システムの詳細はエコシステムのページにある。

年表

オペレーティングシステム

  1. 1966

    ケイパビリティリスト

    Dennis と Van Horn は、計算の "sphere of protection" (保護圏) をそのケイパビリティのリスト、すなわち C-list として記述した。ケイパビリティは「この主体は何に触れられるか」に答える。

    出典
  2. 1971

    UNIX 初版: 所有者と所有者以外のビット

    chmod には 6 つのモードビットがある。所有者と所有者以外それぞれの読み取りと書き込み、実行可能、set-user-ID である。グループの区分はない。(日付はアーカイブのコピーによる。元のマニュアルは確認していない。)

    出典
  3. 1973

    UNIX 第 4 版: グループのビット

    8/5/73 付けの chmod のページは、set-group-ID と、所有者、グループ、その他に対する読み取り・書き込み・実行のビットを加えている。

    出典
  4. 1973–1974

    Saltzer が記述した Multics の ACL

    すべてのセグメントとディレクトリに ACL がある。1973 年 10 月に SOSP で発表され、1974 年 7 月に CACM に掲載された。Multics 自体はそれ以前から稼働していた。Zanzibar の参考文献 [23]。

    出典
  5. 1997–1998

    POSIX.1e ACL: draft 17、その後取り下げ

    draft 17 (1997 年 10 月) が Linux の ACL の基礎となった。1003.1e のスポンサーシップは 1998 年 1 月に取り下げられた。

    出典

モデルと標準

  1. 1971

    Lampson「Protection」: アクセス行列

    行はドメイン (主体)、列はオブジェクト、セルはアクセス属性である。ACL はオブジェクトに付随する 1 つの列であり、ケイパビリティはあるドメインのエントリである。

    出典
  2. 1973

    Bell–LaPadula

    強制的な機密性。上位を読まず、下位に書かない。MITRE MTR-2547 Vol. I (1973 年 3 月)。*-property (下位に書かない) は Vol. II (1973 年 5 月) で登場する。Bell 自身の回顧録から引用。

    出典
  3. 1975–1977

    Biba 完全性モデル

    Bell–LaPadula を完全性について双対にしたもの。MITRE MTR-3153 (1975 年 6 月)。改訂版の MTR-3153 Rev. 1 は 1977 年 4 月に ESD-TR-76-372 として発行された (DTIC AD-A039324)。

    出典
  4. 1992

    ロールベースアクセス制御

    Ferraiolo と Kuhn、第 15 回 National Computer Security Conference。Zanzibar の参考文献 [17]。

    出典
  5. 1996

    RBAC96

    Sandhu らが IEEE Computer 1996 年 2 月号で RBAC モデル群を形式化した。

    出典
  6. 2003

    XACML 1.0、OASIS Standard

    施行点と判定点を分離する XML のポリシー言語。2003 年 2 月の正確な承認日は資料によって異なる。

    出典
  7. 2004

    ANSI INCITS 359-2004 (RBAC)

    統一された NIST RBAC モデルが 2004 年 2 月 11 日に ANSI 標準となった。INCITS 359-2012 として改訂された。

    出典
  8. 2007

    「Relationship-Based Access Control」という語の誕生

    Carrie Gates、W2SP 2007。Fong の 2011 年の論文 (概要と参考文献 [18]) がこの命名を Gates に帰している。Gates の論文自体は確認していない。

    出典
  9. 2011

    Fong: ReBAC の保護モデル

    ソーシャルネットワークにおける所有者とアクセスする者の関係に基づいて判定する。ロールと異なり、関係は合成できる。

    出典
  10. 2013

    XACML 3.0、OASIS Standard

    コア仕様の日付は 2013 年 1 月 22 日である。

    出典
  11. 2014

    NIST SP 800-162 (ABAC)

    属性ベースアクセス制御を定義した。2014 年 1 月に公開され、2019 年 8 月 2 日に更新された。

    出典

地球規模

  1. 2012

    Spanner

    TrueTime と外部一貫性を備えた、Google のグローバル分散データベース。Zanzibar はタプルをこれに格納している (参考文献 [15])。

    出典
  2. 2014 年までに

    Zanzibar の本番稼働

    論文は "has been in production use for more than 5 years" (5 年以上本番で使われてきた) と述べている (§4)。これにより開始は 2014 年半ばより前となるが、その年を示す公開資料はない。

    出典
  3. 2019

    Zanzibar 論文、USENIX ATC '19

    Pang ら。2019 年 7 月にワシントン州レントンで発表された。このサイトが翻訳している論文である。

    出典

オープンソースと標準

  1. 2016

    Open Policy Agent v0.1.0

    Rego 言語を備えた汎用のポリシーエンジン。GitHub での最初のリリースは 2016 年 7 月 14 日である。

    出典
  2. 2021

    OPA が CNCF を卒業

    2021 年 2 月 4 日に発表された。

    出典
  3. 2021

    Ory Keto の Zanzibar 型への書き直し

    v0.6.0-alpha.1、2021 年 4 月 7 日。Keto 自体は 2018 年からある。

    出典
  4. 2021

    SpiceDB の最初のリリース

    2021 年 9 月 30 日、AuthZed による。

    出典
  5. 2022

    OpenFGA の最初のリリース

    2022 年 6 月 10 日。Okta の従業員が開発した。2025 年 10 月 28 日から CNCF の Incubating プロジェクトである。CNCF ブログでの発表は 2025 年 11 月 11 日。

    出典
  6. 2022

    Permify の最初のリリース

    2022 年 8 月 3 日。

    出典
  7. 2022

    Topaz の最初のリリース

    2022 年 10 月 25 日、Aserto による。

    出典
  8. 2023

    Cedar のオープンソース化

    AWS が 2023 年 5 月 10 日に Cedar ポリシー言語を Apache-2.0 で公開した。

    出典
  9. 2023

    Amazon Verified Permissions の一般提供

    Cedar のポリシーを評価するマネージドサービス。2023 年 6 月 13 日に一般提供が開始された。

    出典
  10. 2023

    OpenID AuthZEN ワーキンググループ

    2023 年 10 月 20 日に発表された。目的は "standard mechanisms, protocols and formats for communication between authorization components" (認可コンポーネント間の通信のための標準的な機構、プロトコル、形式) を定義することである。

    出典
  11. 2026

    AuthZEN Authorization API 1.0 Final

    OpenID Final Specification として承認され、2026 年 1 月 12 日に発表された (賛成 81、反対 1、棄権 25)。この API により、ポリシー施行点 (PEP) がポリシー判定点 (PDP) に判定を問い合わせられる。

    出典

Zanzibar はどこから何を取り入れたか

論文は、何かの上に構築することと、何かに似ていることの違いに注意を払っている。Zanzibar は Spanner と Leopard の上で動いている。以前の ACL システムの機能をサポートしている。そして RBAC のロールを自らの関係に、Abadi らの “blessings” を自らのタプルに似ているとしている (§5)。

先行研究のどれが Zanzibar のどの部分に現れているか。

Zanzibar はどこから何を取り入れたか左の列は先行研究と Zanzibar が動作する基盤のシステム。Multics、UNIX、POSIX ACL、VMS (ACL、グループ、継承)、Abadi ら 2015 年 (blessings)、RBAC 1992 年 (ロール)、Spanner 2012 年 (TrueTime、スナップショット読み取り、緑)、Zanzibar の構成要素である Leopard インデックス (緑)。右の列は Zanzibar の部分。リレーションタプルとユーザーセット (§2.1)、関係とユーザーセット書き換え (§2.3.1)、外部一貫性と zookie (§2.2)、入れ子のグループのチェック (§3.2.4)。「機能をサポート」「類似」とラベルの付いた破線の矢印が、ACL システムと Abadi らからタプルとユーザーセットへ、RBAC から関係へ伸びる。「上に構築」とラベルの付いた実線の矢印が、Spanner から外部一貫性へ、Leopard から入れ子のグループのチェックへ伸びる。Multics, UNIX, POSIX ACL, VMSACL、グループ、継承Abadi ら (2015)"blessings"RBAC (1992)ロールSpanner (2012)TrueTime、スナップショット読み取りLeopard インデックス(Zanzibar の一部)リレーションタプルとユーザーセット (§2.1)関係とユーザーセット書き換え (§2.3.1)外部一貫性、zookie (§2.2)入れ子のグループのチェック (§3.2.4)機能をサポート類似類似上に構築上に構築
実線の矢印: Zanzibar はその上で動作する。破線の矢印: 論文が先例または類似の考え方として挙げているもの (§5、§3.2.4)。

この分かれ方に注目したい。上半分のデータモデルは古い考え方の組み合わせ直しである。論文自身が主張しているのはその統一であり、タプルによるモデル化は “allows us to unify the concepts of ACLs and groups” (ACL とグループの概念を統一できる) (§2.1)。Abadi らはこれらを分けたままにしていた (§5)。下半分は Google の規模でそれを機能させたものである。“external consistency and snapshot reads with bounded staleness” (外部一貫性と有界な古さを伴うスナップショット読み取り) のための Spanner (§5) と、ポインタ追跡では十分速く処理できないグループのための (§3.2.4)、“an indexing system used to optimize operations on large and deeply nested sets” (大規模で深く入れ子になった集合に対する操作を最適化するためのインデックスシステム) である Leopard (§3) である。

出典