Take-Grant Model 深度解析：以有向圖追蹤權限擴散與形式化存取控制安全分析

在存取控制安全分析領域，Take-Grant Model（拿取-給予模型）以有向圖為數學基礎，系統化追蹤權限如何在主體與客體之間擴散，是形式化驗證系統安全性的經典框架。

有向圖結構與核心操作

Take-Grant Model 將系統狀態表示為有向圖（Directed Graph），節點代表主體（Subject）或客體（Object），邊上標記的標籤則代表該節點持有的存取權限（如 read、write、take、grant）。模型定義四個基本操作：Take 允許主體從另一主體「奪取」其對某客體的權限；Grant 允許主體將自身持有的權限「授予」另一主體；Create 產生新節點與新邊；Remove 刪除現有邊上的權限標記。分析重點在於：透過反覆套用這四個操作，判斷系統能否從初始狀態抵達「不安全」目標狀態。

安全性判斷與可達性分析

Take-Grant Model 的核心問題是可達性（Reachability）：給定初始圖 G₀，是否存在一組操作序列，使特定主體最終獲得對目標客體的某項權限？Lipton 與 Snyder 於 1977 年證明，此可達性問題在 Take-Grant 模型下可於線性時間 O(|V| + |E|) 內決定，遠優於一般存取矩陣模型的不可判定結果。分析方法透過追蹤「tg-連通分量」（節點間是否存在同時擁有 take 或 grant 權限的路徑），即可快速判斷權限能否跨節點傳播，進而確認系統整體是否滿足安全不變量。

💡 重點整理

• 有向圖建模：節點為主客體，帶標籤的有向邊表示權限關係。
• 四大操作：Take、Grant、Create、Remove 構成權限狀態轉移的完整規則集。
• 線性時間可判定：可達性分析複雜度 O(|V|+|E|)，具備實用性。
• tg-連通性：判斷安全的關鍵在於追蹤 take/grant 邊形成的連通分量範圍。

Take-Grant Model 以精簡的圖論規則，提供了嚴謹且高效的權限擴散分析基礎，至今仍是資訊安全形式化方法課程的核心經典模型。

📚 參考文獻

1. Lipton, R. J., & Snyder, L. (1977). A Linear Time Algorithm for Deciding Subject Security. Journal of the ACM, 24(3), 455–464. — Take-Grant 可達性線性時間演算法原始論文。
2. Bishop, M. (2003). Computer Security: Art and Science. Addison-Wesley. — 涵蓋 Take-Grant Model 完整章節的權威教科書。
3. Sandhu, R. S. (1992). The Typed Access Matrix Model. IEEE Symposium on Security and Privacy. — 延伸討論 Take-Grant 與存取矩陣模型關係的重要文獻。

⚠️ 本文內容基於撰寫時的最新資訊，實際應用時請參考官方文件的最新版本。