Capability-based security (object capabilities)

Deep dive

How it works

In: a handle value, the right being exercised · Out: the object, or "denied" · State: per-holder handle table (slot: generation, object, rights mask, parent link) · Cost: O(1) per check, order of 1 ns when the table is in cache.

1. Start with nothing. A new program has no handles except those its creator passes in: opened files, sockets, directory handles, or imports linked at instantiation. There is no global namespace to look things up in (no ambient authority).
2. Grant. The creator of an object holds a handle with all rights (open_root).
3. Attenuate. derive(h, mask) creates a new handle with rights = parent ∩ mask. Asking for more than you have returns the intersection, never more.
4. Delegate. Hand the handle over: a message that carries it, a descriptor sent over a socket, an argument to a call. The receiver then holds exactly those rights on exactly that object. In the toy, transfer moves it to another table.
5. Use. Every operation names a handle, never a path or an identity. The kernel or runtime resolves the number in the caller's table, checks the rights bit, then acts.
6. Unforgeable. A process can write any integer, but it is only a key into its own table. Variants: a kernel table index (Unix descriptors, Fuchsia, seL4), an i32 index into a per-instance table (WASI), a sealed reference in a language runtime.
7. Revoke. Invalidate the table slot (the toy bumps a generation so old numbers fail), or give out a forwarding caretaker object and switch it off later. Descendants of a revoked handle die with it.
8. Confused deputy. A service that receives the caller's handle and uses only that handle cannot be tricked into using its own authority: the name and the permission arrive together. Hardy (1988) described a compiler with write authority over a billing file that a caller steered into overwriting it by naming that file as output.

Code

Toy handle table: generation counters make stale numbers fail, derive intersects rights, revocation kills descendants, transfer moves a handle between tables. Compiled and run on Rust stable (release): all asserts pass, about 0.7 ns per check.

use std::time::Instant;
pub const READ: u8 = 1;
pub const WRITE: u8 = 2;
pub const ALL: u8 = READ | WRITE;

struct Slot { gen: u32, live: bool, obj: u64, rights: u8, parent: Option<u64> }
#[derive(Default)]
pub struct HandleTable { slots: Vec<Slot>, free: Vec<u32> }

// Handle = generation << 32 | index. Userspace holds only this number;
// object and rights stay in table memory it cannot touch.
impl HandleTable {
    fn alloc(&mut self, obj: u64, rights: u8, parent: Option<u64>) -> u64 {
        let i = self.free.pop().unwrap_or_else(|| {
            self.slots.push(Slot { gen: 1, live: false, obj, rights, parent });
            self.slots.len() as u32 - 1
        });
        let s = &mut self.slots[i as usize];
        (s.live, s.obj, s.rights, s.parent) = (true, obj, rights, parent);
        (s.gen as u64) << 32 | i as u64
    }
    fn slot(&self, h: u64) -> Option<(usize, &Slot)> {
        let (i, g) = ((h & 0xffff_ffff) as usize, (h >> 32) as u32);
        let s = self.slots.get(i).filter(|s| s.live && s.gen == g)?;
        // a revoked (or recycled) ancestor kills the child
        s.parent.map_or(true, |p| self.slot(p).is_some()).then_some((i, s))
    }
    pub fn open_root(&mut self, obj: u64) -> u64 { self.alloc(obj, ALL, None) }
    pub fn derive(&mut self, h: u64, mask: u8) -> Option<u64> {
        let (_, s) = self.slot(h)?;
        let (obj, r) = (s.obj, s.rights & mask); // intersection: rights only shrink
        Some(self.alloc(obj, r, Some(h)))
    }
    pub fn check(&self, h: u64, right: u8) -> Option<u64> {
        self.slot(h).filter(|(_, s)| s.rights & right == right).map(|(_, s)| s.obj)
    }
    pub fn revoke(&mut self, h: u64) -> bool {
        let Some((i, _)) = self.slot(h) else { return false };
        let s = &mut self.slots[i];
        (s.live, s.gen) = (false, s.gen + 1); // old numbers now mismatch
        self.free.push(i as u32);
        true
    }
    pub fn transfer(&mut self, h: u64, to: &mut HandleTable) -> Option<u64> {
        let (_, s) = self.slot(h)?;
        let n = to.alloc(s.obj, s.rights, None); // fresh root slot in the receiver
        self.revoke(h);
        Some(n)
    }
}

fn main() {
    let (mut t, mut other) = (HandleTable::default(), HandleTable::default());
    let file = t.open_root(7);
    let ro = t.derive(file, READ).unwrap();
    assert!(t.check(ro, READ).is_some() && t.check(ro, WRITE).is_none());
    let ro2 = t.derive(ro, ALL).unwrap(); // asks for more, gets the intersection
    assert!(t.check(ro2, WRITE).is_none(), "no amplification");
    assert!(t.check(0xdead_beef, READ).is_none() && t.check(3 << 32 | 99, READ).is_none());
    // Confused deputy: the deputy resolves the CALLER's number in the CALLER's table.
    let (mut own, mut caller) = (HandleTable::default(), HandleTable::default());
    let billing = own.open_root(1); // only in the deputy's table
    let scratch = caller.open_root(2);
    assert_eq!(caller.check(billing, WRITE), Some(2)); // same number, caller's object
    assert!(caller.check(scratch + 1, WRITE).is_none()); // unmapped number
    assert_eq!(own.check(billing, WRITE), Some(1)); // deputy's own authority intact
    let child = t.derive(file, READ).unwrap(); // revocation kills descendants
    assert!(t.revoke(file) && t.check(child, READ).is_none() && t.check(ro2, READ).is_none());
    let reused = t.open_root(9); // slot reuse: same index, new generation
    assert_eq!(reused & 0xffff_ffff, file & 0xffff_ffff);
    assert!(t.check(file, READ).is_none() && t.check(child, READ).is_none());
    let moved = t.transfer(reused, &mut other).unwrap(); // transfer moves the handle
    assert!(t.check(reused, READ).is_none() && other.check(moved, WRITE) == Some(9));
    let (n, t0, mut acc) = (50_000_000u64, Instant::now(), 0u64);
    for i in 0..n { acc += other.check(std::hint::black_box(moved), 1 + (i & 1) as u8).unwrap(); }
    println!("ok; {:.2} ns/check (acc {acc})", t0.elapsed().as_nanos() as f64 / n as f64);
}

Complexity and constants

• check: bounds check, generation compare, mask test; plus one lookup per ancestor in the toy (kernels keep a derivation tree so revoke walks, not check).
• Memory: 24 bytes per toy slot; kernels pack 8-16.
• Measured: 0.69-0.71 ns per check over 50 M iterations on one hot handle (Apple Silicon Mac, release): the L1-resident best case. A cold table costs a cache miss per use.
• Setup dominates: Capsicum's authors report a constant 2.4 ms to sandbox gzip, and capability-aware syscalls a few percent slower than plain ones (Watson et al. 2010).

Efficiency

Cost: one table lookup per use (order of 1 ns hot, a cache miss cold); real cost is design: every crossing needs an explicit send, plus once-per-sandbox setup (2.4 ms for gzip in the Capsicum paper). Bound: IPC and first-access latency, not compute.

Levers:

• Pass a directory handle instead of proxying each open through a broker — saves one IPC round trip per file (Watson et al. 2010) — when the sandbox opens several files.
• Batch handles in one message — SCM_RIGHTS carries an array of descriptors per sendmsg (unix(7)) — when starting a worker with several resources.
• Resolve paths in the kernel with openat2 + RESOLVE_BENEATH — one syscall, no racy userland .. checks (openat2(2), Linux 5.6) — for untrusted paths.
• Narrow once at start (cap_rights_limit, then cap_enter) — later calls pay only the rights test — for long-lived workers.

Naive → standard → state of the art:

• Broker proxies every open over IPC · one round trip (µs) per operation.
• Pre-opened, rights-limited descriptors plus capability mode · one-time setup, then plain syscalls.
• Kernel- or runtime-level handle tables (seL4, Fuchsia, WASI) · uniform O(1) check on every operation.

Implementation notes

• Unix descriptors already are handles: kernel table index, per-process, passed by fork or SCM_RIGHTS (the receiver gets a reference to the open file description, usually under another number). Unix lacks the absence of global namespaces and per-descriptor rights. Capsicum adds both: cap_rights_limit reduces rights, never expands them; cap_enter makes the file-system and PID namespaces unreachable, is irreversible and inherited by children.
• In capability mode openat may only reach objects under the directory descriptor passed; Linux's openat2 offers RESOLVE_BENEATH and RESOLVE_IN_ROOT.
• WASI: Wasm has no syscall instructions. Link-time capabilities are imports chosen at linking; runtime capabilities are handles (i32 indices into per-instance tables). Wasmtime gives a guest no filesystem unless the host configures a preopened_dir.
• seL4: capabilities live in a CSpace of CSlots; CNode_Copy takes a rights mask, CNode_Revoke on the original deletes the copies the tutorial makes; the root task starts with all of them.
• Fuchsia: zx_handle_duplicate/zx_handle_replace can reduce rights; ZX_RIGHT_DUPLICATE and ZX_RIGHT_TRANSFER gate copying and channel sends.
• Allocate everything needed (libraries, DNS config, log sockets) before locking down.

Pitfalls

• Ambient fallback. One call falling back to a global path or uid undoes the model; Capsicum's dhclient needed a local-resolver change because DNS depended on file-system and network namespaces after cap_enter (Watson et al. 2010).
• .. and symlinks. A prefix-checked directory handle is a chroot with known escapes; use RESOLVE_BENEATH-style containment.
• Numbers collide across tables. 3 here is not 3 elsewhere; always resolve in the holder's table.
• Slot reuse. Without generations a stale number names a new object.
• Leaked handles. A descriptor inherited by accident or left open past lock-down is authority you did not mean to give.
• Unrevocable copies. A passed descriptor has no remote revoke in the pages read; design a caretaker that forwards calls and can be switched off.

Variants and alternatives

In production

• FreeBSD Capsicum — per the paper, tcpdump (two-line cap_enter change), dhclient, gzip, Chromium; libcasper serves sandboxed programs.
• WASI / Wasmtime — preopened directories and handle tables for Wasm guests.
• seL4 and Fuchsia (Zircon) — every kernel resource is reached through capabilities or handles.
• Linux — SCM_RIGHTS passing and openat2 containment in brokers.

Implementations

Sources

• Dennis, Van Horn, Programming semantics for multiprogrammed computations, CACM 9(3) 1966, 143-155. DOI 10.1145/365230.365252
• Hardy, The Confused Deputy, ACM SIGOPS Operating Systems Review 22(4) 1988, 36-38. DOI 10.1145/54289.871709
• Watson, Anderson, Laurie, Kennaway, Capsicum: practical capabilities for UNIX, USENIX Security 2010. paper
• FreeBSD capsicum(4), cap_enter(2), cap_rights_limit(2)
• WebAssembly WASI, Capabilities in WASI; Wasmtime WasiCtxBuilder
• seL4 docs, Capabilities tutorial
• Fuchsia, Zircon handles, rights
• Linux man-pages, openat2(2), unix(7)