ここまで、権限管理について以下の実装を試してきました。

　
このシリーズの最後として、ReBAC (Relationship-Based Access Control) を実装してみます。

今回も標準的なReBACについて調べたりClaude Codeに質問したりして実装しました。とはいえ抜けがあるかもしれないため、「標準的なReBACではこのような仕様もある」などがありましたら、ツッコミをお願いします。

環境
ABACとの違いについて
今回実装するReBACの仕様について
実装
- 型
- クラス
動作確認
参考資料
ソースコード

環境

mac
Claude Code + Opus 4.0/4.1
- 学んでいる最中にOpusのバージョンが上がったため、両方使っています
TypeScript 5.7.3
Bun 1.2.19
Biome 2.1.2

ABACとの違いについて

前回の記事で見た通り、ABACは属性を元に評価を行い、権限の判定を行います。一方、ReBACは関係性を元に評価を行い、権限の判定を行います。

ReBACの関係性は、グラフを元にした Relationship Tuple (関係性タプル)という概念で表現します。

　
例えば、「aliceがdocumentの所有者である」は

       [owns]
alice --------> document

という図で表せるとします。

これをグラフ構造で表すと、

ノード (頂点)
- alice (始点)
- document (終点)
エッジ (辺)
- owns

になります。このとき、エッジ(owns)はノードにある始点(alice)と終点(document)の関係を表しているといえます。

この3つの要素(始点ノード、関係性を表すエッジ、終点ノード)の組み合わせが 関係性タプル となります。

　
また、関係性タプル同士が関係を持つこともできます。

例えば、「チームのマネージャーは、チームメンバーのアクセス権限と同等になる」という前提で

aliceはbobのマネージャーである
bobはdocumentの所有者である

という関係がある場合、aliceはbobを経由してdocumentへとアクセス可能になります。図で表すと以下の通りです。

       [manages]        [owns]
alice -----------> bob --------> document

　
さらに、ReBACでは探索の効率性と権限有無の明確性から「より直接的な関係(最短経路)」を優先して選択します。

例えば、以下の図にある2つの関係性であれば、上の方がより直接的な関係とみなされます。

alice ---> bob ---> document

alice ---> bob ---> carol ---> document

今回実装するReBACの仕様について

基本方針

今回も学習用途なので、基本方針は以下とします。

学習用のシンプルな実装とする
ABAC同様の作り方
- 題材は社内ドキュメント管理システムとする
- パーミッションは「読み取り」「書き込み」の2種類
- 1リソースで、1つのReBACで保護するクラスのインスタンスを使う

関係タイプについて

ReBACの標準的な実装では、単一の関係性タイプのみを扱う実装が存在します。

一方、今回の実装では理解しやすさを優先します。つまり、2種類の関係タイプを定義することで、「documentがuserをmanage」のような不自然な関係が存在するのを防ぎます。

直接的関係
- 用途
  - エンティティ - リソース間のアクセス関係として、エンティティからリソースへのアクセス権限を表す
- 例
  - owns、viewer、editor
間接的関係
- 用途
  - エンティティ(ユーザーやグループ) - エンティティ間の関係として、エンティティ間のつながりを表す
- 例
  - manages、memberOf

関係性タプルの表現方法について

関係性タプルをTypeScriptで表現する場合、「配列」と「オブジェクト」のどちらを使うか決める必要があります。

前述の「aliceがdocumentのオーナーである」を配列で示す場合は以下です。

const tuple = ['alice', 'owns', 'document']

　
一方、オブジェクトで示す場合は以下です。

const tuple = {
  subject: 'alice',
  relation: 'owns',
  object: 'document'
}

　
配列だと「何番目がどの要素なのか」がやや分かりづらいことから、今回はオブジェクトで示す方針としました。

グラフ構造の表現方法について

上記の通り、ReBACはグラフ構造で関係性を表現します。グラフ構造としては

隣接行列
隣接リスト

の2つがあります。

　
隣接行列は、すべての組み合わせを表にする方法です。イメージは以下で、関係ある箇所に 1 を設定します。

          alice  bob  document
alice       0     1      1
bob         0     0      1
document    0     0      0

　
一方、隣接リストは「誰と誰が関係あるか」だけを持ちます。

alice    → { manages: [bob], owns: [document] }
bob      → { owns: [document] }

# documentは人ではないので、誰とも関係を持っていない
document → { }

　
今回は

隣接行列より隣接リストの方が実装がシンプルになる
- 関係が増えると、表が巨大になる
関係性だけ保存するので、メモリなどが効率的になる

という点から、隣接リストを使います。

グラフの探索方法について

一般的にグラフではエッジに重みをつけることもできますが、Google Zanzibarをはじめとした既存のReBACは重み付けがありません。これより、今回のReBACにおけるグラフの検索では

深さ優先探索 (Depth First Search、DFS)
幅優先探索 (Breadth First Search、BFS)

のどちらかが使えそうです。

DFSでは最初に見つけた関係を深く探索するため、最短の関係とは限りません。一方、BFSでは幅ごとに探索するため、最短の関係を保証しています。

そこで、今回はBFSを採用します。また、BFSの場合は見つかるまで階層を深く潜っていきますが、今回は学習用途のため、深さは3階層までに制限します。

否定的関係について

例えば「aliceはdocumentにいかなる場合もアクセスできない」という否定的関係についても表現したくなるかもしれません。

しかし、

既存のReBAC実装を見ても否定的関係は導入していないこと
否定的関係を考慮すると複雑になること

から、今回の学習用途では否定的関係は仕様に盛り込みません。「関係がない場合は否定」として判断します。

判定結果について

ABACでの実装と異なり、今回のReBAC実装では「関係があれば許可」のみを定義します。

そのため、判定結果も「許可」「拒否」の2値とします。

実装

今までの権限管理に比べ実装量が多いことから、解説する上で必要な部分のみ抜粋します。ソースコード全体は後述のGitHub リポジトリにあるため、そちらを参照してください。

型

エンティティ識別子

複数箇所に出てくるため、名前をつけておきます。

export type EntityId = string

関係タイプ

前述した通り、今回は理解しやすさを優先するため、関係タイプを2種類用意します。

直接的関係タイプ
間接的関係タイプ

まずは直接的関係タイプの型 DirectRelationType です。直接的関係として、エンティティからリソースへのアクセス権限を表します。

export type DirectRelationType =
  | 'owns' // 所有関係
  | 'viewer' // 閲覧者権限
  | 'editor' // 編集者権限

　
続いて IndirectRelationType 型です。間接的関係として、エンティティ間でのつながりを表します。

export type IndirectRelationType =
  | 'manages' // 管理関係
  | 'memberOf' // 所属関係 (user memberOf team)
  | 'has' // 所属関係 (team has user)

　
また、関係タイプの全種類を表す RelationType 型も定義します。

export type RelationType = IndirectRelationType | DirectRelationType

関係性タプル

今回は関係性タプルをオブジェクトで示します。不自然な関係性タプルとならないよう、関係タイプごとに関係性タプルの型を定義します。

まずは直接的関係の関係性タプル DirectRelationTuple です。

export type DirectRelationTuple = {
  subject: EntityId // ユーザーまたはグループ
  relation: DirectRelationType // リソースへのアクセス関係
  object: EntityId // リソース（ドキュメント）
}

　
続いて、間接的関係の関係性タプル IndirectRelationTuple です。

export type IndirectRelationTuple = {
  subject: EntityId // ユーザーまたはグループ
  relation: IndirectRelationType // エンティティ間の関係
  object: EntityId // グループまたはユーザー
}

　
関係性タプルでも全種類を表す RelationTuple 型を定義します。

export type RelationTuple = IndirectRelationTuple | DirectRelationTuple

　
関係性タプルの連鎖に関する型も定義します。

export type RelationshipChain = RelationTuple[]

隣接リスト

隣接リストの型も定義しておきます。

// あるエンティティから見た、関係タイプごとのエンティティ集合を表す型
// 例: aliceに関する、own、manages、memberOfごとのエンティティ集合
// Map {
//   "owns" => Set(["document1", "document2"]),
//   "manages" => Set(["bob", "carol"]),
//   "memberOf" => Set(["engineering-team"])
// }
type RelationMap = Map<RelationType, Set<EntityId>>

// 隣接リスト全体
type AdjacencyList = Map<EntityId, RelationMap>

ReBAC判定結果

前述の通り、「許可」「拒否」の2種類です。ただ、拒否には

必要な関係が見つからない
探索の最大深度を探索しても、関係が見つからなかった
- 深度をより深くすれば見つかる可能性はある

の2種類があります。

　
そこで、拒否は2種類あることも型として表現します。

export type ReBACDecision =
  | {
  type: 'granted'
  path: RelationshipChain // 権限の根拠となる関係性パス
  relation: DirectRelationType // マッチした関係
}
  | {
  type: 'denied'
  reason: 'no-relation' // 必要な関係性が見つからない
  searchedRelations: DirectRelationType[] // 探索した関係
}
  | {
  type: 'denied'
  reason: 'max-depth-exceeded' // 探索深度の制限
  maxDepth: number
}

クラス

今回は

関係性グラフを管理するクラス
関係性の探索を行うクラス
ReBACによって保護されたリソースを表すクラス

の3クラスを用意します。

関係性グラフを管理するクラス

隣接リストを使って関係性グラフを管理します。

例えば alice -- (owns) --> document という関係があった場合、隣接リストは以下になります。

// alice → owns → document
Map {
  "alice" => Map {
    "owns" => Set(["document"])
  }
}

　
実際の RelationGraph クラスです。

export class RelationGraph {
  // 隣接リスト (subject -> relation -> objects)
  private adjacencyList: AdjacencyList

  constructor() {
    this.adjacencyList = new Map()
  }

  // 関係性を追加
  addRelation(tuple: IndirectRelationTuple | DirectRelationTuple): void {}

  // 関係性を削除
  removeRelation(tuple: RelationTuple): void {}

  // 直接関係の存在確認
  hasDirectRelation(subject: EntityId, relation: RelationType, object: EntityId): boolean {}

  // subjectから出る関係を取得
  // あるエンティティ（例:alice）から出る全ての関係を取得
  getRelations(subject: EntityId): ReadonlyArray<RelationTuple> {}

  // すべての関係を削除
  clear(): void {}
}

関係性の探索を行うクラス

このクラスでは、BFSでの関係性の探索を行います。

関係性の探索については

直接的関係
間接的関係

の順で探索しています。既存のReBAC実装同様、効率よく探索する目的で、BFSを使わなくても解決する直接的関係から探索します。

　
また、BFSのアルゴリズム通り、データ構造はキューを使っています。TypeScriptにはキュー専用の型はなさそうなので、オブジェクトの配列で実装しています。

export class RelationshipExplorer {
  constructor(
    private graph: RelationGraph,
    private config: ExplorationConfig = DEFAULT_CONFIG
  ) {}

  findRelationPath(
    subject: EntityId,
    targetObject: EntityId,
    targetRelations: ReadonlySet<RelationType>
  ): ExplorationResult {
    for (const relation of targetRelations) {
      if (this.graph.hasDirectRelation(subject, relation, targetObject)) {
        return {
          type: 'found',
          path: [{ subject, relation, object: targetObject }],
          matchedRelation: relation
        }
      }
    }

    // BFSでの探索
    const queue: SearchState[] = [{ current: subject, path: [], depth: 0 }]
    const visited = new Set<EntityId>([subject])

    while (queue.length > 0) {
      const item = queue.shift()
      if (!item) break
      const { current, path, depth } = item

      if (depth >= this.config.maxDepth) {
        return {
          type: 'max-depth-exceeded',
          maxDepth: this.config.maxDepth
        }
      }

      const relations = this.graph.getRelations(current)
      for (const tuple of relations) {
        if (tuple.object === targetObject && targetRelations.has(tuple.relation)) {
          return {
            type: 'found',
            path: [...path, tuple],
            matchedRelation: tuple.relation
          }
        }

        if (visited.has(tuple.object)) continue
        visited.add(tuple.object)

        queue.push({
          current: tuple.object,
          path: [...path, tuple],
          depth: depth + 1
        })
      }
    }

    return { type: 'not-found' }
  }
}

ReBACによって保護されたリソースを表すクラス

ReBACProtectedResource クラスでは、1つのリソースにつき、このクラスの1インスタンスを使います。

また、関係性に基づいて権限チェックも行いますが、BFSによる探索自体は RelationshipExplorer へ移譲しています。

export class ReBACProtectedResource {
  private explorer: RelationshipExplorer

  constructor(
    private resourceId: EntityId,
    graph: RelationGraph,
    private relationPermissions: RelationPermissions[] = DEFAULT_RELATION_PERMISSIONS,
    config?: ExplorationConfig
  ) {
    this.explorer = new RelationshipExplorer(graph, config)
  }

  // 関係性に基づいて権限をチェック
  checkRelation(subject: EntityId, action: PermissionAction): ReBACDecision {
    const requiredRelations = this.getRequiredRelations(action)

    const result = this.explorer.findRelationPath(subject, this.resourceId, requiredRelations)

    switch (result.type) {
      case 'found':
        return {
          type: 'granted',
          path: result.path,
          relation: result.matchedRelation as DirectRelationType
        }

      case 'max-depth-exceeded':
        return {
          type: 'denied',
          reason: 'max-depth-exceeded',
          maxDepth: result.maxDepth
        }

      case 'not-found':
        return {
          type: 'denied',
          reason: 'no-relation',
          searchedRelations: Array.from(requiredRelations)
        }
    }
  }

  // アクションに必要な関係性を取得
  getRequiredRelations(action: PermissionAction): ReadonlySet<DirectRelationType> {
    return new Set(
      this.relationPermissions
        .filter((rule) => rule.permissions[action])
        .map((rule) => rule.relation)
    )
  }
}

動作確認

ReBACの場合もテストコードで動作確認をします。

ここではいくつかのテストパターンを見ていきます。テストコード全体については後述のリポジトリを参照してください。

直接的関係でマッチするパターン

user1 -- (owns) --> doc1 という直接的関係があった時に、マッチすると判定するパターンです。

describe('直接関係あり', () => {
  it('grantedで、関係が返されること', () => {
    const graph = new RelationGraph()
    const relation: RelationTuple = {
      subject: 'user1',
      relation: 'owns',
      object: 'doc1'
    }
    graph.addRelation(relation)

    const resource = new ReBACProtectedResource('doc1', graph)
    const result = resource.checkRelation('user1', 'write')

    expect(result).toEqual({
      type: 'granted',
      relation: 'owns',
      path: [relation]
    })
  })
})

間接的関係でマッチするパターン

続いて、間接的関係です。ここでは長めの user1 -- (memberOf) --> team1 -- (memberOf) --> org1 -- (owns) --> doc1 という間接的関係があった時に、マッチすると判定するパターンです。

describe('3ホップ', () => {
  it('関係が見つかること', () => {
    const graph = new RelationGraph()
    const relation1: RelationTuple = {
      subject: 'user1',
      relation: 'memberOf',
      object: 'team1'
    }
    const relation2: RelationTuple = {
      subject: 'team1',
      relation: 'memberOf',
      object: 'org1'
    }
    const relation3: RelationTuple = {
      subject: 'org1',
      relation: 'owns',
      object: 'doc1'
    }

    graph.addRelation(relation1)
    graph.addRelation(relation2)
    graph.addRelation(relation3)

    const explorer = new RelationshipExplorer(graph)
    const result = explorer.findRelationPath('user1', 'doc1', new Set(['owns', 'editor']))

    expect(result).toEqual({
      type: 'found',
      path: [relation1, relation2, relation3],
      matchedRelation: 'owns'
    })
  })
})

最短の関係でマッチするパターン

マッチするパターンが

user1 -- (memberOf) --> team1 -- (editor) --> doc1
user1 -- (memberOf) --> org1 -- (memberOf) --> team2 -- (owns) --> doc1

の2つあった時、前者でマッチしたとみなすパターンです。

describe('深さが異なる、条件を満たすパスが複数存在', () => {
  it('最短パスを返すこと', () => {
    const graph = new RelationGraph()

    // 深さ2: editor経由のパス
    graph.addRelation({
      subject: 'user1',
      relation: 'memberOf',
      object: 'team1'
    })
    graph.addRelation({
      subject: 'team1',
      relation: 'editor',
      object: 'doc1'
    })

    // 深さ3: owns経由のパス
    graph.addRelation({
      subject: 'user1',
      relation: 'memberOf',
      object: 'org1'
    })
    graph.addRelation({
      subject: 'org1',
      relation: 'memberOf',
      object: 'team2'
    })
    graph.addRelation({
      subject: 'team2',
      relation: 'owns',
      object: 'doc1'
    })

    const explorer = new RelationshipExplorer(graph)
    const result = explorer.findRelationPath('user1', 'doc1', new Set(['editor', 'owns']))

    expect(result).toEqual({
      type: 'found',
      matchedRelation: 'editor',
      path: [
        { subject: 'user1', relation: 'memberOf', object: 'team1' },
        { subject: 'team1', relation: 'editor', object: 'doc1' }
      ]
    })
  })
})

深さ制限によりマッチしないパターン

describe('maxDepthを超えた深度に条件を満たすパスが存在', () => {
  it('max-depth-exceededを返すこと', () => {
    const graph = new RelationGraph()
    const relation1: RelationTuple = {
      subject: 'user1',
      relation: 'memberOf',
      object: 'team1'
    }
    const relation2: RelationTuple = {
      subject: 'team1',
      relation: 'memberOf',
      object: 'org1'
    }
    const relation3: RelationTuple = {
      subject: 'org1',
      relation: 'editor',
      object: 'doc1'
    }

    graph.addRelation(relation1)
    graph.addRelation(relation2)
    graph.addRelation(relation3)

    const explorer = new RelationshipExplorer(graph, { maxDepth: 2 })
    const result = explorer.findRelationPath('user1', 'doc1', new Set(['editor', 'owns']))

    expect(result).toEqual({
      type: 'max-depth-exceeded',
      maxDepth: 2
    })
  })
})

参考資料

ReBACについてはほぼ分からない状態から始めたため、複数の資料を参照しました。

ReBACの概要については、OSOのAuthorization Academyに記載されていました。
Authorization Academy - Relationship-Based Access Control (ReBAC)

　
ReBACの実装としてよく見かけるのがGoogleのZanzibarです。これについてはGoogleのZanzibar論文や、Zanzibarのアーキテクチャ解説のブログを読みました。

また、以下のページでZanzibarが体験できるようです。
Zanzibar: A Global Authorization System - Presented by Auth0

　
ReBACに対応しているライブラリとしては OpenFGA を目にする機会が多かったです。

　
今回実装したReBACでは、BFSを使って関係を探索しました。BFSのアルゴリズムを視覚的に理解する場合、以下の書籍が分かりやすかったです。後者では擬似コードによるBFSのアルゴリズムも掲載されていました。

ソースコード

GitHubに上げました。
https://github.com/thinkAmi-sandbox/authorization_practice_in_memory

今回のプルリクはこちら。ここまでの権限管理に関するドキュメントも合わせて整理したため、変更量が多くなってしまっています。
https://github.com/thinkAmi-sandbox/authorization_practice_in_memory/pull/5

なお、Claude Codeに任せた部分と自分で書いた部分は、それぞれ別のコミットにしています。また、Claude Codeに任せたコミットには、Claude Codeに対するプロンプトも記載してあります。

メモ的な思考的な

権限管理の1つであるReBAC (Relationship-Based Access Control) をTypeScriptで実装してみた

環境