Loading learning content...
Delegation creates a fundamental problem: once you give someone a capability, how do you take it back?\n\nIn the physical world, if you give someone a key to your house and later want to revoke their access, you must either get the key back or change the locks. Capability revocation faces the same dilemma—but in a world where keys can be perfectly copied and distributed instantaneously.\n\nRevocation is critical for real-world security:\n\n- An employee leaves the company; their access must be terminated\n- A service is compromised; all capabilities it holds must be invalidated\n- A temporary grant expires; associated capabilities must become invalid\n- A security policy changes; existing capabilities must be adjusted\n\nThis page explores the mechanisms, algorithms, and trade-offs in capability revocation—one of the most studied and debated topics in capability-based security.
By the end of this page, you will understand why revocation is challenging in capability systems, the various revocation mechanisms (indirect objects, generational references, propagation tracking), the trade-offs between revocation approaches, how modern systems like seL4 and CHERI handle revocation, and when to prefer revocation versus time-limited capabilities.
Capability revocation is inherently difficult because of the capability model's core strength: possession is authorization. Once a subject holds a capability, it can use it. There is no central database to update, no single point where access can be denied.\n\nWhy Revocation is Hard\n\nConsider the simplest case: Alice grants Bob a capability, then wants to revoke it.\n\nIn theory, Alice could simply delete Bob's capability from Bob's C-list. But:\n\n1. Copies may exist: Bob might have delegated to Carol, who delegated to Dave. Where are all the copies?\n\n2. No central registry: Unlike ACLs where the object knows its accessors, capabilities are distributed. There's no inherent list of all capability holders.\n\n3. Storage locations vary: Capabilities might be in C-lists, in IPC message buffers, in shared memory, saved to disk, serialized to network packets...\n\n4. Time of check vs. time of use: Even if we invalidate a capability, it might be 'in flight' in an ongoing operation.
Capabilities are designed to be easily shareable—that's their strength for modular security. But easy sharing is the enemy of revocation. Every sharing operation potentially creates a path that must be traced during revocation. This tension is intrinsic to capability-based security.
Revocation Scenarios\n\nDifferent use cases have different revocation requirements:
| Scenario | Scope | Urgency | Challenge |
|---|---|---|---|
| Employee termination | All capabilities held by one subject | Immediate | Finding all capabilities transferred from/to employee |
| Object deletion | All capabilities to one object | Immediate | Finding all holders, handling in-flight operations |
| Rights reduction | All capabilities with specific rights | May be gradual | Narrowing rights without full revocation |
| Session expiry | Time-limited grants | At defined time | Enforcement without continuous checking |
| Security policy change | Class of capabilities | Policy-dependent | Identifying affected capabilities |
Comparison with ACL Revocation\n\nIn ACL systems, revocation is straightforward: modify the object's ACL to remove the subject's entry. All future access checks will fail. The object is the single point of control.\n\nIn capability systems, there is no equivalent single point. This is the price paid for the flexibility and modularity of capabilities.
Several mechanisms have been developed to address the revocation problem, each with different trade-offs. Understanding these mechanisms is essential for designing secure capability systems.\n\n1. Indirect Objects (The Caretaker Pattern)\n\nInstead of granting a direct capability to an object, grant a capability to an intermediary (caretaker, proxy, forwarder) that holds the actual capability. Revocation is accomplished by telling the intermediary to stop forwarding, or by revoking the intermediary's capability to the real object.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
// Caretaker Pattern for revocation // The actual objecttypedef struct { char data[1024]; // ... object fields} RealObject; // Caretaker: intermediary that can be 'switched off'typedef struct { RealObject* target; // Points to real object bool revoked; // Revocation flag uint32_t allowed_rights; // Can further restrict} Caretaker; // Create a revocable capability via caretakerCaretaker* create_caretaker(RealObject* obj, uint32_t rights) { Caretaker* ct = allocate_caretaker(); ct->target = obj; ct->revoked = false; ct->allowed_rights = rights; // Return capability to caretaker (not to real object) return ct;} // Operations go through caretakerint caretaker_read(Caretaker* ct, void* buffer, size_t len) { // Check revocation status if (ct->revoked) return -EACCES; // Access revoked! // Check rights if (!(ct->allowed_rights & CAP_READ)) return -EPERM; // Forward to real object return object_read(ct->target, buffer, len);} // Revocation: simply mark the caretakervoid revoke_caretaker(Caretaker* ct) { ct->revoked = true; // All future operations through this caretaker will fail // The holder still has the capability to the caretaker, // but the caretaker no longer provides access to the object} // Key insight: All capabilities derived from this caretaker// are effectively revoked, even if they were further delegated// This is "revocation by indirection"Advantages of Caretaker Pattern:\n- Simple to implement\n- O(1) revocation (just flip a flag)\n- Doesn't require modifying capability infrastructure\n\nDisadvantages:\n- Performance overhead (indirection on every operation)\n- Memory overhead (one caretaker per revocable grant)\n- Must plan for revocation in advance (can't retrofit)\n\n2. Generational References\n\nAssociate a generation number with each object. Capabilities include the generation number when created. If the object's generation is incremented, all capabilities with the old generation become invalid.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
// Generational References for revocation typedef struct { uint64_t object_id; uint64_t data[100]; // Generation counter: incremented on revocation uint64_t generation;} GenerationalObject; typedef struct { GenerationalObject* object; uint64_t generation; // Generation at time of capability creation uint32_t rights;} GenerationalCapability; // Create capability: snapshot current generationGenerationalCapability create_cap(GenerationalObject* obj, uint32_t rights) { return (GenerationalCapability){ .object = obj, .generation = obj->generation, // Capture current generation .rights = rights };} // Validate capability before usebool validate_generation(GenerationalCapability* cap) { // Check if generations match if (cap->generation != cap->object->generation) { // Object has been 'revoked and recycled' return false; } return true;} // Use capabilityint gen_cap_read(GenerationalCapability* cap, void* buffer, size_t len) { if (!validate_generation(cap)) return -ESTALE; // Capability invalidated if (!(cap->rights & CAP_READ)) return -EPERM; return object_read(cap->object, buffer, len);} // Revocation: bump the generationvoid revoke_all_capabilities(GenerationalObject* obj) { obj->generation++; // ALL capabilities to this object with the old generation // are now invalid, regardless of where they are stored // or who holds them} // Selective revocation: create new caretaker at current generation// Old caretakers become invalid, new ones workvoid selective_revoke_and_reissue(GenerationalObject* obj, Process** still_authorized, int count) { // Increment generation (invalidates all existing caps) obj->generation++; // Issue new capabilities with new generation for (int i = 0; i < count; i++) { GenerationalCapability new_cap = create_cap(obj, CAP_READ); grant_to_process(still_authorized[i], new_cap); }}Advantages of Generational References:\n- Atomic revocation of ALL capabilities to an object\n- No need to find capability holders\n- Check happens at use time, not at revocation time\n\nDisadvantages:\n- Cannot selectively revoke individual capabilities\n- Requires re-issuing capabilities to remaining authorized holders\n- Small per-operation overhead for generation check\n\n3. Revocation Lists (Blacklisting)\n\nMaintain a list of revoked capabilities. Every capability use checks against this list.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
// Revocation Lists for capability invalidation // Each capability has a unique identifiertypedef struct { uint64_t cap_id; // Unique capability ID uint64_t object_id; uint32_t rights;} IdentifiedCapability; // Global revocation listtypedef struct { uint64_t* revoked_cap_ids; size_t count; size_t capacity; rwlock_t lock; // For efficiency: bloom filter for fast negative check bloom_filter_t bloom;} RevocationList; static RevocationList global_revocation_list; // Create capability with unique IDIdentifiedCapability create_identified_cap(uint64_t obj_id, uint32_t rights) { return (IdentifiedCapability){ .cap_id = generate_unique_id(), // UUID or counter .object_id = obj_id, .rights = rights };} // Revoke a capability (O(1) to add)void revoke_capability(uint64_t cap_id) { write_lock(&global_revocation_list.lock); // Add to list if (global_revocation_list.count >= global_revocation_list.capacity) { grow_list(&global_revocation_list); } global_revocation_list.revoked_cap_ids[global_revocation_list.count++] = cap_id; // Add to bloom filter for fast checking bloom_add(&global_revocation_list.bloom, cap_id); write_unlock(&global_revocation_list.lock);} // Check if capability is revoked (O(n) worst case, but bloom filter helps)bool is_revoked(uint64_t cap_id) { // Fast path: bloom filter says not revoked if (!bloom_might_contain(&global_revocation_list.bloom, cap_id)) return false; // Definitely not revoked // Slow path: check actual list read_lock(&global_revocation_list.lock); for (size_t i = 0; i < global_revocation_list.count; i++) { if (global_revocation_list.revoked_cap_ids[i] == cap_id) { read_unlock(&global_revocation_list.lock); return true; // Revoked! } } read_unlock(&global_revocation_list.lock); return false; // Not revoked} // Use capability with revocation checkint use_capability(IdentifiedCapability* cap) { if (is_revoked(cap->cap_id)) return -EACCES; // Revoked! return perform_operation(cap);}Revocation lists grow over time as capabilities are revoked. Eventually, the list might need to be compacted by expiring old entries, or the system might need a 'epoch rollover' that invalidates all capabilities and reissues valid ones. This is analogous to how PKI handles CRL (Certificate Revocation List) growth.
For selective revocation (revoking some but not all capabilities to an object), the system must track how capabilities have propagated through delegation. This enables revoking a capability and all its derivatives.\n\nseL4's Capability Derivation Tree (CDT)\n\nseL4 maintains a tree structure tracking parent-child relationships between capabilities. When a capability is revoked, all its descendants in the tree are also revoked.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
// Capability Derivation Tree (CDT) - seL4 approach // Each capability slot has metadata for the derivation treetypedef struct mdb_node { struct cte* parent; // Parent capability (where this was derived from) struct cte* first_child; // First child (derived from this) struct cte* next_sibling; // Next sibling (same parent) struct cte* prev_sibling; // Previous sibling // Additional flags for revocation bool revocable; // Can this be revoked? uint8_t depth; // Depth in tree (for cycle prevention)} mdb_node_t; // CTE: Capability Table Entry with both cap and derivation infotypedef struct cte { cap_t cap; // The capability itself mdb_node_t mdb; // Derivation tree links} cte_t; // Grant capability: creates child in derivation treeint cap_grant_tracked(cte_t* source, cte_t* dest) { // Copy capability dest->cap = source->cap; // Link into derivation tree dest->mdb.parent = source; dest->mdb.first_child = NULL; // Add as child of source dest->mdb.next_sibling = source->mdb.first_child; if (source->mdb.first_child) source->mdb.first_child->mdb.prev_sibling = dest; source->mdb.first_child = dest; dest->mdb.prev_sibling = NULL; dest->mdb.depth = source->mdb.depth + 1; return 0;} // Revoke: removes capability AND all descendants (transitively)void cap_revoke(cte_t* cap) { // DFS to revoke all children first while (cap->mdb.first_child != NULL) { cap_revoke(cap->mdb.first_child); } // Unlink from siblings if (cap->mdb.prev_sibling) cap->mdb.prev_sibling->mdb.next_sibling = cap->mdb.next_sibling; if (cap->mdb.next_sibling) cap->mdb.next_sibling->mdb.prev_sibling = cap->mdb.prev_sibling; // Unlink from parent if (cap->mdb.parent) { if (cap->mdb.parent->mdb.first_child == cap) cap->mdb.parent->mdb.first_child = cap->mdb.next_sibling; } // Invalidate the capability itself cap->cap = cap_null; cap->mdb = (mdb_node_t){0};} // Example derivation tree://// [Kernel root cap]// |// [Init cap] ---------> granted to init process// |// +----+----+// | |// [Server cap] [User cap] --> granted to different processes// |// [Client cap] -----------> further delegation//// Revoking [Server cap] also revokes [Client cap]// Revoking [Init cap] revokes entire subtreeRevocation Complexity\n\nWith propagation tracking, revocation is O(n) where n is the number of descendants to revoke. This can be significant for deeply shared capabilities, but it's bounded and predictable.\n\nMemory Overhead\n\nEach capability carries additional metadata for tree links (typically 3-4 pointers). This is the price for revocability.
seL4 chose to pay the memory/complexity cost for full propagation tracking because it enables complete, immediate revocation—essential for a high-assurance microkernel. The formal verification of seL4 includes proofs that revocation correctly invalidates all derived capabilities.
| Mechanism | Revocation Speed | Selectivity | Memory Cost | Complexity |
|---|---|---|---|---|
| Caretaker/Proxy | O(1) | Per-caretaker | One object per grant | Simple |
| Generational | O(1) + redistribute | All-or-nothing per object | One counter per object | Simple |
| Revocation List | O(1) add, O(list) check | Per-capability | Growing list | Moderate |
| Derivation Tree (CDT) | O(descendants) | Subtree | Pointers per capability | Complex |
An alternative to explicit revocation is not granting permanent capabilities in the first place. Time-limited capabilities automatically expire, eliminating the need for active revocation in many scenarios.\n\nHow Time-Limited Capabilities Work\n\nEach capability includes an expiration time. Before performing any operation, the system checks if the capability has expired.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
// Time-Limited Capabilities typedef struct { uint64_t object_id; uint32_t rights; // Temporal constraint uint64_t issued_at; // When capability was created uint64_t expires_at; // When capability becomes invalid} TemporalCapability; // Create time-limited capabilityTemporalCapability create_temporal_cap(uint64_t obj, uint32_t rights, uint64_t duration_seconds) { uint64_t now = current_time(); return (TemporalCapability){ .object_id = obj, .rights = rights, .issued_at = now, .expires_at = now + duration_seconds };} // Validate: check expirationbool is_valid(TemporalCapability* cap) { if (current_time() > cap->expires_at) return false; // Expired! return true;} // Use capabilityint use_temporal_cap(TemporalCapability* cap) { if (!is_valid(cap)) return -ETIMEDOUT; // Capability expired return perform_operation(cap->object_id, cap->rights);} // Renewable capabilities: holder can request refreshtypedef struct { TemporalCapability base; // Renewal metadata uint64_t max_renewals; // How many times can be renewed uint64_t renewals_used; // How many times renewed so far uint64_t renewal_duration; // Duration of each renewal} RenewableCapability; int renew_capability(RenewableCapability* cap) { // Check if renewal is allowed if (cap->renewals_used >= cap->max_renewals) return -EPERM; // No more renewals // Must renew before expiration if (!is_valid(&cap->base)) return -ETIMEDOUT; // Already expired, cannot renew // Extend expiration cap->base.expires_at = current_time() + cap->renewal_duration; cap->renewals_used++; return 0;} // Usage pattern: short-lived capability with refresh tokenvoid oauth_style_capability_usage() { // Access token: short-lived (5 minutes) TemporalCapability access_cap = create_temporal_cap( RESOURCE_ID, CAP_READ | CAP_WRITE, 300); // Refresh token: long-lived but can only get new access tokens RenewableCapability refresh_cap = { .base = create_temporal_cap(AUTH_SERVER, 0, 86400), // 24 hours .max_renewals = 100, .renewals_used = 0, .renewal_duration = 300 // Each renewal extends by 5 minutes }; // When access_cap expires, use refresh_cap to get new access_cap // If refresh_cap expires, must re-authenticate}Advantages of Time-Limited Capabilities\n\n- No explicit revocation infrastructure needed\n- Natural bound on exposure from compromised capabilities\n- Works well in distributed systems (no revocation propagation)\n- Simplifies reasoning about authority lifetime\n\nDisadvantages\n\n- Requires synchronized clocks (in distributed systems)\n- Overhead of renewal protocols\n- Cannot immediately revoke if needed\n- Duration must be chosen carefully (too short = overhead, too long = risk)
Modern web authentication heavily uses time-limited tokens. OAuth 2.0 access tokens and JWTs typically have short lifetimes (minutes to hours) and require refresh. This is essentially capability-based security with temporal constraints, favoring expiration over revocation for simplicity in distributed environments.
Hybrid Approach: Time-Limited with Revocation Backstop\n\nMany practical systems combine time-limited capabilities with revocation lists:\n\n- Capabilities have short lifetimes (e.g., 5-15 minutes)\n- Revocation list only needs to track recently-issued, unexpired capabilities\n- Revocation list can be aggressively pruned (anything older than max_lifetime is expired anyway)\n- Provides both automatic expiration and emergency revocation capability
Hardware capability systems like CHERI face unique revocation challenges: capabilities are scattered throughout memory, registers, and potentially swapped to disk. Finding and invalidating them all is non-trivial.\n\nThe CHERI Revocation Challenge\n\nIn CHERI, capabilities are fat pointers stored in registers and memory. When memory is freed, any remaining capabilities to that memory become dangling—a use-after-free vulnerability. CHERI's memory safety guarantees require revoking these dangling capabilities.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
// CHERI revocation: revoking capabilities to freed memory // The problem: after free(), capabilities to that memory may still existvoid* __capability ptr = allocate(1024);void* __capability alias = ptr; // Another capability to same memory free_using_cap(ptr); // 'alias' is now a dangling capability!// In traditional CHERI, dereferencing 'alias' would access freed memory// We need temporal memory safety: revoke 'alias' automatically // Solution 1: Generational memory (MemSafe approach)typedef struct { void* base; size_t length; uint64_t generation; // Incremented on free} GenerationalAllocation; void* __capability safe_malloc(size_t size) { // Allocate with generation tracking GenerationalAllocation* alloc = internal_malloc(size + sizeof(uint64_t)); alloc->generation = global_generation_counter++; void* __capability cap = cheri_bounds_set(alloc + 1, size); // Encode generation in capability's unused bits (CHERI supports this) cap = cheri_set_generation(cap, alloc->generation); return cap;} void safe_free(void* __capability ptr) { // Increment generation on the allocation metadata GenerationalAllocation* alloc = get_allocation_header(ptr); alloc->generation++; // Any capability with old generation is now invalid // Checked at dereference time by load/store extension internal_free(alloc);} // Solution 2: Sweeping revocation (Cornucopia approach)// Periodically scan all memory for capabilities to be revoked typedef struct { void* revoked_range_start; void* revoked_range_end;} RevocationRequest; void revoke_by_sweeping(RevocationRequest* req) { // Scan all memory (registers, stack, heap, globals) for (word_t* p = memory_start; p < memory_end; p++) { if (is_capability_tagged(p)) { void* __capability cap = *(void* __capability*)p; void* cap_base = cheri_base_get(cap); // Check if capability points into revoked range if (cap_base >= req->revoked_range_start && cap_base < req->revoked_range_end) { // Invalidate: clear the tag bit clear_capability_tag(p); // Or: replace with null capability *p = cheri_null; } } } // Also scan registers of all threads for_each_thread(t) { for_each_cap_register(t, reg) { // Same check and invalidation } }}CHERI Revocation Approaches
The Cornucopia system demonstrates practical heap temporal safety for CHERI. It uses a combination of quarantine (freed memory not immediately reused) and concurrent sweeping (background thread scans for dangling capabilities). Benchmarks show <5% overhead on many workloads—practical for real-world deployment.
seL4 provides a comprehensive revocation mechanism that is formally verified to work correctly. Understanding seL4's approach illustrates the state of the art in capability revocation for high-assurance systems.\n\nseL4 Revocation Primitives\n\nseL4 provides two revocation operations:\n\n- seL4_CNode_Delete: Removes a single capability from a CSpace slot (does NOT revoke derived capabilities)\n- seL4_CNode_Revoke: Removes a capability AND all capabilities derived from it\n\nThe difference is crucial: Delete is a local operation; Revoke is transitive.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
// seL4 Revocation API and semantics // Delete: remove single capability (O(1))seL4_Error seL4_CNode_Delete( seL4_CNode cnode, // CNode containing the capability seL4_Word index, // Slot index in CNode seL4_Uint8 depth // Depth for CSpace lookup);// After Delete: the specified slot is empty// BUT: any capabilities derived from this one remain valid! // Revoke: remove capability AND all derivatives (O(descendants))seL4_Error seL4_CNode_Revoke( seL4_CNode cnode, // CNode containing the capability seL4_Word index, // Slot index in CNode seL4_Uint8 depth // Depth for CSpace lookup);// After Revoke: the specified slot and ALL slots with capabilities// derived from this one are empty // Example usage scenario:void server_manages_client_resources(void) { // Server creates endpoint for client seL4_CPtr client_ep = allocate_endpoint(); // Grant capability to client (creates derivative) seL4_CNode_Copy( client_cnode, client_slot, client_depth, my_cnode, client_ep, my_depth, seL4_AllRights ); // Now client has derived capability to the endpoint // ... client uses endpoint ... // Client misbehaves or session ends; revoke access seL4_CNode_Revoke(my_cnode, client_ep, my_depth); // Client's derived capability is now invalid // Server still has original capability (Revoke removes derivatives, not parent)} // Mutual revocation: both parties lose accessvoid mutual_terminate(void) { // Delete the parent capability (not just revoke derivatives) seL4_CNode_Delete(my_cnode, client_ep, my_depth); // Now no one has access to the endpoint // (Derivatives were implicitly revoked)}The Mapping Database (MDB)\n\nseL4's capability derivation tree is called the Mapping Database (MDB). Despite the name, it tracks all capability derivations, not just memory mappings.\n\nThe MDB is a doubly-linked list structure where:\n- Each capability has links to its parent, first child, and siblings\n- Revoke traverses this list, invalidating capabilities\n- The structure is maintained during grant/copy operations\n\nFormal Verification of Revocation\n\nseL4's formal proofs include verification that:\n- After Revoke, no derived capabilities remain valid\n- Revoke terminates (no infinite loops)\n- Revoke doesn't affect unrelated capabilities\n- The MDB invariants are maintained\n\nThis is remarkable: mathematical proof that revocation works correctly, covering all edge cases.
seL4's Revoke operation can take unbounded time (proportional to the number of descendants). For real-time systems, this is problematic. seL4 addresses this by limiting the depth of derivation trees and allowing applications to structure their capability graphs to bound revocation time.
Choosing a revocation strategy requires understanding the trade-offs and matching them to system requirements. There is no universally best approach—each has strengths for particular scenarios.\n\nDecision Factors
| Factor | Prefer Time-Limited | Prefer Explicit Revocation |
|---|---|---|
| Urgency | Graceful expiration OK | Immediate revocation needed |
| Distribution | Highly distributed system | Centralized or local |
| Clock sync | Good clock synchronization | Cannot rely on clocks |
| Revocation freq | Rare revocations | Frequent access changes |
| Scale | Massive scale | Bounded scale |
| Auditability | Duration-based audit sufficient | Need revocation audit trail |
| Complexity budget | Simple preferred | Can afford complexity |
Best Practices for Revocation Design
In most systems, there is a window between 'revocation requested' and 'revocation complete'. During this window, the capability may still be usable. Design security-critical systems to account for this window—especially in distributed scenarios where propagation delays are significant.
Revocation completes the capability lifecycle: creation, delegation, use, and finally, invalidation. We've explored the challenges, mechanisms, and trade-offs that make revocation one of capability security's most studied topics.
What's Next\n\nWe have now covered capabilities thoroughly: concept, lists, delegation, and revocation. The final page compares capabilities with ACLs directly, examining when each approach is appropriate and how modern systems combine them.
You now understand capability revocation—the challenges of taking back delegated authority, the various mechanisms available, and how to choose among them. Continue to the final page to compare capabilities with ACLs.