Policy engines (PDP/PEP, Cedar, Rego, ReBAC)

Deep dive

How it works

Parts:

• PEP — enforcement point on the path (gateway, dispatcher, DB layer); builds the request, obeys the answer
• PDP — decision engine; evaluates policies and returns Allow/Deny plus determining policy ids
• policy store — permit/forbid rules (Cedar, Rego) or relationship tuples, versioned
• entity/data store — attributes and group membership the policies read
• decision log — request, result, policy ids, policy version

app -> PEP --(principal, action, resource, context)--> PDP <-- policies + entities
        ^                                                 |
        +---------- Allow/Deny + policy ids --------------+--> decision log

Steps:

1. PEP/PDP split. The PEP sits on the path (API gateway, tool dispatcher, DB layer), builds a request (principal, action, resource, context), calls the PDP, enforces the answer. Fail closed if the PDP is unreachable.
2. Decision model. RBAC, ABAC and ReBAC (Authorization models) differ in what the language expresses, not in the interface.
3. Semantics (Cedar). Collect the policies whose scope matches and whose conditions hold. Any forbid → Deny. Else any permit → Allow. Else Deny. The response lists the determining policies (satisfied permits, or satisfied forbids).
4. Indexing. Cedar keys policies by their principal and resource scope and unions the buckets of the request's entity and its ancestors; the paper proves slicing sound. OPA indexes rules on equality, in and glob statements, but negated expressions are never indexed. The code below indexes by action.
5. ReBAC. OpenFGA and SpiceDB store tuples doc:1#viewer@user:ann and rewrite relations (editor implies viewer, folder viewer implies document viewer). A check is a graph walk; Zanzibar adds consistency tokens ("zookies") against stale ACLs.
6. List endpoints. "Which documents may I see?" must not call the PDP per row. Partial evaluation treats the resource as unknown and returns conditions; OPA's compile API turns them into SQL WHERE terms joined by OR.
7. Caching. Cache (principal, action, resource, context-hash) → decision with a short TTL or a policy/data version key. Revocation latency equals the TTL.
8. Audit. Log every decision with request, result, determining policy ids and policy version (OPA ships decision logs; Cedar returns the ids).

Code

Cedar-like evaluator in std Rust, with an agent tool-call example in main.

use std::collections::HashMap;

#[derive(Clone, Copy, PartialEq, Debug)]
pub enum Effect { Permit, Forbid }

/// Which entity a scope matches: anything, a type, or one exact entity.
pub enum Scope { Any, Type(&'static str), Is(&'static str, &'static str) }

#[derive(Clone, Copy)]
pub enum Path { Principal(&'static str), Resource(&'static str), Context(&'static str) }

pub enum Cond {
    Eq(Path, &'static str),           // attribute == literal
    OneOf(Path, &'static [&'static str]),
    Same(Path, Path),                 // e.g. principal.tenant == resource.tenant
}

pub struct Policy {
    pub id: &'static str,
    pub effect: Effect,
    pub principal: Scope,
    pub action: Option<&'static str>, // None = any action
    pub resource: Scope,
    pub when: Vec<Cond>,              // all must hold
}

pub struct Entity { pub ty: &'static str, pub id: &'static str, pub attrs: HashMap<&'static str, &'static str> }

pub struct Request<'a> {
    pub principal: &'a Entity, pub action: &'static str, pub resource: &'a Entity,
    pub context: HashMap<&'static str, &'static str>,
}

#[derive(Debug, PartialEq)]
pub struct Decision { pub allow: bool, pub determining: Vec<&'static str>, pub errors: Vec<&'static str> }

pub struct Engine { policies: Vec<Policy>, by_action: HashMap<&'static str, Vec<usize>>, any_action: Vec<usize> }

impl Engine {
    pub fn new(policies: Vec<Policy>) -> Self {
        let (mut by_action, mut any_action) = (HashMap::new(), Vec::new());
        for (i, p) in policies.iter().enumerate() {
            match p.action {
                Some(a) => by_action.entry(a).or_insert_with(Vec::new).push(i),
                None => any_action.push(i),
            }
        }
        Engine { policies, by_action, any_action }
    }

    pub fn decide(&self, r: &Request) -> Decision {
        // Index: only policies naming this action (or any action) are candidates.
        let mut cand: Vec<usize> = self.by_action.get(r.action).cloned().unwrap_or_default();
        cand.extend(&self.any_action);
        cand.sort_unstable(); // stable audit order
        let (mut permits, mut forbids, mut errors) = (vec![], vec![], vec![]);
        for i in cand {
            let p = &self.policies[i];
            if !scope_ok(&p.principal, r.principal) || !scope_ok(&p.resource, r.resource) { continue; }
            match conds_ok(&p.when, r) {
                Ok(true) => if p.effect == Effect::Permit { permits.push(p.id) } else { forbids.push(p.id) },
                Ok(false) => {}
                Err(()) => errors.push(p.id), // missing attribute: policy skipped, reported
            }
        }
        // forbid wins; default deny when no permit matched
        if !forbids.is_empty() { Decision { allow: false, determining: forbids, errors } }
        else if !permits.is_empty() { Decision { allow: true, determining: permits, errors } }
        else { Decision { allow: false, determining: vec![], errors } }
    }
}

fn scope_ok(s: &Scope, e: &Entity) -> bool {
    match s { Scope::Any => true, Scope::Type(t) => e.ty == *t, Scope::Is(t, i) => e.ty == *t && e.id == *i }
}

fn get<'a>(p: Path, r: &'a Request) -> Result<&'a str, ()> {
    match p {
        Path::Principal(k) => r.principal.attrs.get(k),
        Path::Resource(k) => r.resource.attrs.get(k),
        Path::Context(k) => r.context.get(k),
    }.copied().ok_or(())
}

fn conds_ok(cs: &[Cond], r: &Request) -> Result<bool, ()> {
    for c in cs {
        let ok = match c {
            Cond::Eq(p, v) => get(*p, r)? == *v,
            Cond::OneOf(p, vs) => vs.contains(&get(*p, r)?),
            Cond::Same(a, b) => get(*a, r)? == get(*b, r)?,
        };
        if !ok { return Ok(false); } // evaluates left to right, stops early
    }
    Ok(true)
}

fn ent(ty: &'static str, id: &'static str, attrs: &[(&'static str, &'static str)]) -> Entity {
    Entity { ty, id, attrs: attrs.iter().cloned().collect() }
}

fn main() {
    let engine = Engine::new(vec![
        // Agent "triage" may call search and read_file on tools of its own tenant.
        Policy { id: "p-read", effect: Effect::Permit, principal: Scope::Is("Agent", "triage"),
            action: Some("call"), resource: Scope::Type("Tool"),
            when: vec![Cond::OneOf(Path::Resource("name"), &["search", "read_file"]),
                       Cond::Same(Path::Principal("tenant"), Path::Resource("tenant"))] },
        // Any agent may send mail, but only to the corporate domain.
        Policy { id: "p-mail", effect: Effect::Permit, principal: Scope::Type("Agent"),
            action: Some("call"), resource: Scope::Is("Tool", "send_mail"),
            when: vec![Cond::Eq(Path::Context("recipient_domain"), "corp.example")] },
        // Never anything while the session is flagged as prompt-injected.
        Policy { id: "f-tainted", effect: Effect::Forbid, principal: Scope::Any, action: None,
            resource: Scope::Any, when: vec![Cond::Eq(Path::Context("tainted"), "true")] },
    ]);
    let agent = ent("Agent", "triage", &[("tenant", "t1")]);
    let search = ent("Tool", "search", &[("name", "search"), ("tenant", "t1")]);
    let mail = ent("Tool", "send_mail", &[("name", "send_mail"), ("tenant", "t1")]);
    let req = |res, ctx: &[(&'static str, &'static str)]| Request {
        principal: &agent, action: "call", resource: res, context: ctx.iter().cloned().collect() };

    assert_eq!(engine.decide(&req(&search, &[("tainted", "false")])),
        Decision { allow: true, determining: vec!["p-read"], errors: vec![] });
    // forbid beats permit and names itself in the audit record
    let d = engine.decide(&req(&search, &[("tainted", "true")]));
    assert!(!d.allow && d.determining == ["f-tainted"]);
    assert!(engine.decide(&req(&mail, &[("tainted", "false"), ("recipient_domain", "corp.example")])).allow);
    let d = engine.decide(&req(&mail, &[("tainted", "false"), ("recipient_domain", "evil.example")]));
    assert!(!d.allow && d.determining.is_empty());
    // missing context attribute: policies error, are skipped and reported; result is deny
    let d = engine.decide(&req(&mail, &[]));
    assert!(!d.allow && d.errors == ["p-mail", "f-tainted"]);
    println!("ok");
}

Complexity and constants

Decision cost = index lookup + candidates × conditions; policy count matters only through bucket size. Drivers: candidates per request, attribute lookups, decision allocation, and loading entity attributes from a database (usually dwarfs evaluation). ReBAC checks cost one lookup per edge walked: depth and group fan-out dominate.

Efficiency

• Cost: measured by me on an Apple M4 Pro, this code, 10,000 policies with 10 per action, release build: about 0.5 µs per decision with the action index, about 19 µs by scanning all policies (about 35× slower). Bound: hash lookups and allocation; a network hop to a central PDP costs far more than evaluation. OPA docs cite a budget of order 1 ms per microservice decision.
• Levers:
  • Index by action/scope — 35× on the benchmark above (measured) — many policies, few relevant per request.
  • Embed the engine as a library or sidecar — no network hop per decision — latency-critical paths such as tool dispatch.
  • Decision cache keyed by policy version — skips evaluation — repeated identical checks.
  • Partial evaluation for lists — one query instead of N checks (OPA docs) — list/search endpoints.
  • Cedar slicing — 10.0×-18.0× faster on average in the paper's benchmark (Cutler et al. 2024) — large policy stores.
• Naive → standard → state of the art:
  • Evaluate every policy per request · linear in policy count (19 µs at 10,000, measured)
  • Index by action/resource scope, library embedding · sub-µs to µs per decision here; Cedar paper reports its authorizer 28.7×-35.2× faster than OpenFGA and 42.8×-80.8× faster than Rego on its workloads
  • Verified engine, partial evaluation for filters, version-keyed caches · same speed, no per-row calls

Implementation notes

• Canonicalize the request (sorted context, typed ids) before hashing a cache key; include the policy-set version.
• Skip-and-report on policy errors, as Cedar does, and alert on a non-empty errors list.
• Cedar's validator guarantees no evaluation error from type mismatch or bogus attribute names; its Lean model proves default deny, forbid-trumps-permit and sound slicing, and the Rust code is differential-tested against it (Cutler et al. 2024).

Agent tool-call authorization

The agent is the principal, a tool the resource, call the action, tool arguments and session state the context. Put the arguments (recipient domain, path prefix, amount) in conditions, and let a session flag set by prompt-injection defense feed a blanket forbid, as f-tainted does above. Decide in the dispatcher, outside the model; log determining ids with each tool call. Per-task grants fit capability tokens.

Pitfalls

• PDP error or timeout treated as allow. Fail closed.
• Time-of-check/time-of-use: decide on the attributes you enforce on.
• Stale cache after revocation, no version key.
• Negated or unindexed Rego conditions: latency grows with policy size.
• A forbid referencing an attribute some requests lack errors, is skipped, and silently does not apply.

Variants and alternatives

In production

• Media: Netflix enforces microservice access control with OPA; Google runs Zanzibar for Drive, Photos and YouTube (OPA adopters, paper).
• Finance: BNY Mellon runs OPA as a sidecar for application access control (OPA adopters).
• Telecom: VodafoneZiggo uses OPA for authorisation decisions in its internal developer platform (OPA adopters).
• Cloud infra: Amazon Verified Permissions is a managed Cedar service (AWS); Cloudflare uses OPA as a Kubernetes admission controller (OPA adopters); Canonical uses OpenFGA for Juju and LXD (OpenFGA adopters).

Implementations

Sources

• Cutler et al., Cedar: A New Language for Expressive, Fast, Safe, and Analyzable Authorization, 2024. paper · code
• Pang et al., Zanzibar: Google's Consistent, Global Authorization System, USENIX ATC 2019. paper
• OPA policy performance · decision logs · partial evaluation for data filters
• Cedar authorization semantics
• OPA project, Adopters. list
• OASIS, XACML 3.0 Core. spec