The Problem Statement

Our ABAC v1 model from Posts 5-6 enables context-aware permissions with simple conditions like "Alice can view during business hours" or "Users can view if department matches." But real-world authorization often requires complex multi-predicate conditions that combine multiple checks with boolean logic.

Real-world examples from production systems:

Looking at public documentation and policy examples from major authorization systems reveals a clear pattern:

  • Google Cloud IAM Conditions: Supports boolean expressions like (resource.type == "storage.bucket" && resource.name.startsWith("prod-")) || request.auth.claims.admin == true

  • AWS IAM Condition Operators: Provides StringLike, DateGreaterThan, IpAddress operators that are commonly combined with multiple Condition blocks (implicit AND)

  • Azure ABAC: Supports complex conditions like @Resource[Department] == @Principal[Department] && (@Resource[Confidentiality] == "Public" || @Principal[ClearanceLevel] >= @Resource[ClearanceLevel])

  • Open Policy Agent (OPA): Rego policies routinely combine multiple predicates with boolean logic

Common patterns that require boolean logic:

  1. Security clearance systems: (employee OR contractor) AND NOT suspended AND clearance_level >= required_level

  2. Healthcare HIPAA compliance: (doctor_assigned_to_patient OR emergency_access) AND NOT patient_restricted AND within_business_hours

  3. Financial transaction approval: amount < threshold OR (dual_approval_received AND manager_level >= 3)

  4. Multi-tenant SaaS: tenant_match AND (resource_public OR user_has_special_access) AND NOT user_suspended

What we can't express today:

"Grant access if (user is employee OR contractor) AND NOT suspended AND clearance level ≥ 3."

Our current model forces us to choose between:

  • ❌ Creating separate tuples for employees and contractors (duplication)

  • ❌ Encoding logic in parameter names (brittle)

  • ❌ Pushing logic to application layer (defeats purpose of authorization system)

The core problem: Our current model can express individual predicates (clearance >= 3), but we need to combine them with AND, OR, and NOT logic, plus support dynamic computations through function calls (local_hour(now_utc, timezone)).

Why Current Models Don't Work

Let's try to express "grant access if (employee OR contractor) AND NOT suspended AND clearance ≥ 3" using our existing tools from Posts 1-6.

What We Have So Far (Post 1-6 Recap)

From previous posts, we have:

From Post 5: Basic caveat expressions with single predicates:

// Simple comparison: current_hour >= 9
&BooleanExpr{
    Op: BOOL_PREDICATE,
    Pred: &Predicate{
        Left:  &IdentifierExpr{Name: "current_hour"},
        Op:    CMP_GE,
        Right: &LiteralExpr{Value: 9, Type: CAV_T_INT},
    },
}

From Post 6: Namespace-based parameters for attribute matching:

// Attribute comparison: user.department == document.department
&BooleanExpr{
    Op: BOOL_PREDICATE,
    Pred: &Predicate{
        Left:  &IdentifierExpr{Name: "user.department"},
        Op:    CMP_EQ,
        Right: &IdentifierExpr{Name: "document.department"},
    },
}

What's missing: We can't combine multiple predicates with boolean logic!

Approach 1: Multiple Separate Caveats (Doesn't Work)

// Try to create separate caveats for each condition
employeeCaveat := &CaveatDefinition{
    Name: "is_employee_or_contractor",
    Parameters: []*CaveatParameter{
        &ScalarParameter{Name: "user.employment_type", Type: CAV_T_STRING},
    },
    Expression: &BooleanExpr{
        Op: BOOL_PREDICATE,
        Pred: &Predicate{
            Left:  &IdentifierExpr{Name: "user.employment_type"},
            Op:    CMP_EQ,
            Right: &LiteralExpr{Value: "employee", Type: CAV_T_STRING},
        },
    },
}

// How do we express "employee OR contractor"? We can't!
// How do we combine this with "NOT suspended"? We can't!

Problems:

  • ❌ Can't express OR logic: No way to say "employee OR contractor" in a single predicate

  • ❌ Can't express NOT logic: No way to negate a condition

  • ❌ Can't combine caveats: Multiple caveats are AND-ed together, but we need more flexibility

  • ❌ Requires multiple tuples: Would need separate tuples for each employment type

Approach 2: Encode Logic in Parameter Names (Brittle)

// Try to encode the logic in parameter names
caveat := &CaveatDefinition{
    Name: "complex_check",
    Parameters: []*CaveatParameter{
        &ScalarParameter{Name: "user.is_employee_or_contractor", Type: CAV_T_BOOL},
        &ScalarParameter{Name: "user.is_not_suspended", Type: CAV_T_BOOL},
        &ScalarParameter{Name: "user.has_sufficient_clearance", Type: CAV_T_BOOL},
    },
    Expression: &BooleanExpr{
        Op: BOOL_PREDICATE,
        Pred: &Predicate{
            Left:  &IdentifierExpr{Name: "user.is_employee_or_contractor"},
            Op:    CMP_EQ,
            Right: &LiteralExpr{Value: true, Type: CAV_T_BOOL},
        },
    },
}

Problems:

  • ❌ Pushes logic to caller: Application must compute "is_employee_or_contractor" before calling Check

  • ❌ Loses auditability: Can't see the actual conditions in the authorization system

  • ❌ Not reusable: Each complex condition requires custom pre-computation

  • ❌ Breaks separation of concerns: Authorization logic leaks into application layer

Approach 3: Application-Layer Logic (Defeats the Purpose)

// Check each condition separately in application code
result1 := authzService.Check(resource, subject, ctx1) // Check employment type
result2 := authzService.Check(resource, subject, ctx2) // Check suspension
result3 := authzService.Check(resource, subject, ctx3) // Check clearance

// Combine results in application
if (result1.Granted || result2.Granted) && !result3.Granted && result4.Granted {
    // Allow access
}

Problems:

  • ❌ Multiple round-trips: N conditions = N authorization checks

  • ❌ Inconsistent state: Conditions might be evaluated at different times

  • ❌ No atomic evaluation: Can't guarantee all conditions are checked together

  • ❌ Audit nightmare: Authorization logs don't show the complete decision logic

Conclusion: We need boolean algebra inside caveat expressions to combine multiple predicates with AND, OR, and NOT logic

The Solution: Boolean Algebra in Caveats

We need to extend our caveat expression model to support:

  1. Boolean operators: AND, OR, NOT to combine predicates

  2. Function calls: Dynamic computations like now(), contains(), startsWith()

  3. Nested expressions: Arbitrary depth of boolean combinations

The solution builds on the expression types we introduced in Post 5:

Part 1: Boolean Expression Operators (Already Defined!)

In Post 5, we defined BooleanExpr with four operators, but only used BOOL_PREDICATE:

type BooleanOp int32
const (
    BOOL_AND       BooleanOp = iota  // Logical AND
    BOOL_OR                          // Logical OR
    BOOL_NOT                         // Logical NOT
    BOOL_PREDICATE                   // Leaf predicate (comparison)
)

type BooleanExpr struct {
    Op       BooleanOp         // Which operation
    Children []*BooleanExpr    // Child expressions (for AND/OR/NOT)
    Pred     *Predicate        // Leaf predicate (for BOOL_PREDICATE)
}

In Post 7, we activate the full boolean algebra!

Part 2: Activating CallExpr for Function Calls

In Post 5, we defined CallExpr but marked it as "reserved for future use":

type CallExpr struct {
    FnName  string       // Function name (e.g., "local_hour", "contains")
    Version int          // Function version (for safe updates, default: 1)
    Args    []CaveatExpr // Arguments (can be IdentifierExpr, LiteralExpr, or nested CallExpr)
}

In Post 7, we activate CallExpr with a whitelist of pure, deterministic functions!

Key design principle: All functions must be pure and parameterized:

  • ✅ Pure: No side effects, no external state

  • ✅ Deterministic: Same inputs always produce same outputs

  • ✅ Total: Must return a value for all valid inputs (never throw/panic)

  • ✅ Bounded: Finite execution time

Examples of valid functions:

  • local_hour(now_utc, tz) — Convert UTC timestamp to local hour in timezone

  • contains(haystack, needle) — Check if string contains substring

  • starts_with(str, prefix) — Check if string starts with prefix

  • list_contains(list, element) — Check if list contains element

Examples of INVALID functions:

  • ❌ now() — Non-deterministic (depends on system clock)

  • ❌ fetch_user_attr(user_id) — Side effects (database query)

  • ❌ random() — Non-deterministic

  • ❌ sleep(seconds) — Side effects, unbounded time

Why this matters: Determinism ensures that two evaluators always agree on the result, which is critical for distributed systems and audit compliance.

Function Registry Interface

All caveat functions must implement this interface:

type CaveatFunction interface {
    // Name returns the function name (e.g., "local_hour")
    Name() string

    // Evaluate executes the function with given arguments
    // Must be pure, deterministic, total, and bounded
    Evaluate(args []any) (any, error)

    // ReturnType specifies the function's return type
    ReturnType() CaveatParameterType

    // ArgTypes specifies expected argument types
    ArgTypes() []CaveatParameterType
}

Example: local_hour function

type LocalHourFunction struct{}

func (f *LocalHourFunction) Name() string {
    return "local_hour"
}

func (f *LocalHourFunction) Evaluate(args []any) (any, error) {
    nowUtc := args[0].(int64)
    timezone := args[1].(string)

    loc, err := time.LoadLocation(timezone)
    if err != nil {
        return 0, err
    }

    t := time.Unix(nowUtc, 0).In(loc)
    return t.Hour(), nil
}

func (f *LocalHourFunction) ReturnType() CaveatParameterType {
    return CAV_T_INT
}

func (f *LocalHourFunction) ArgTypes() []CaveatParameterType {
    return []CaveatParameterType{CAV_T_TIMESTAMP, CAV_T_STRING}
}

Function registration:

// Global function registry
var functionRegistry = map[string]CaveatFunction{
    "local_hour":   &LocalHourFunction{},
    "contains":     &ContainsFunction{},
    "starts_with":  &StartsWithFunction{},
    "ends_with":    &EndsWithFunction{},
    "list_contains": &ListContainsFunction{},
}

func GetFunction(name string) CaveatFunction {
    return functionRegistry[name]
}

Why this interface?

  • Type safety: Functions declare their types upfront

  • Validation: Can validate function calls at schema creation time

  • Discoverability: Easy to list all available functions

  • Versioning: Can add version field for safe updates

Function versioning for safe updates:

type CaveatFunction interface {
    Name() string
    Version() int  // Add version field
    Evaluate(args []any) (any, error)
    ReturnType() CaveatParameterType
    ArgTypes() []CaveatParameterType
}

// Registry supports multiple versions
var functionRegistry = map[string]map[int]CaveatFunction{
    "local_hour": {
        1: &LocalHourFunctionV1{},
        2: &LocalHourFunctionV2{},  // Updated implementation
    },
}

// Caveat definitions specify which version to use
&CallExpr{
    FnName:  "local_hour",
    Version: 1,  // Explicitly pin to v1
    Args:    []CaveatExpr{...},
}

Benefits:

  • ✅ No breaking changes: Old caveats continue using v1

  • ✅ Gradual migration: New caveats can use v2

  • ✅ Auditability: Know exactly which version was used

  • ✅ Rollback safety: Can revert to old version if needed

Extending the Model: Complete Boolean Algebra

Now let's see how boolean operators work in practice:

Boolean AND — All Conditions Must Be True

// (employee OR contractor) AND NOT suspended AND clearance >= 3
&BooleanExpr{
    Op: BOOL_AND,
    Children: []*BooleanExpr{
        // Condition 1: employee OR contractor
        {
            Op: BOOL_OR,
            Children: []*BooleanExpr{
                {
                    Op: BOOL_PREDICATE,
                    Pred: &Predicate{
                        Left:  &IdentifierExpr{Name: "user.employment_type"},
                        Op:    CMP_EQ,
                        Right: &LiteralExpr{Value: "employee", Type: CAV_T_STRING},
                    },
                },
                {
                    Op: BOOL_PREDICATE,
                    Pred: &Predicate{
                        Left:  &IdentifierExpr{Name: "user.employment_type"},
                        Op:    CMP_EQ,
                        Right: &LiteralExpr{Value: "contractor", Type: CAV_T_STRING},
                    },
                },
            },
        },
        // Condition 2: NOT suspended
        {
            Op: BOOL_NOT,
            Children: []*BooleanExpr{
                {
                    Op: BOOL_PREDICATE,
                    Pred: &Predicate{
                        Left:  &IdentifierExpr{Name: "user.is_suspended"},
                        Op:    CMP_EQ,
                        Right: &LiteralExpr{Value: true, Type: CAV_T_BOOL},
                    },
                },
            },
        },
        // Condition 3: clearance >= 3
        {
            Op: BOOL_PREDICATE,
            Pred: &Predicate{
                Left:  &IdentifierExpr{Name: "user.clearance_level"},
                Op:    CMP_GE,
                Right: &LiteralExpr{Value: 3, Type: CAV_T_INT},
            },
        },
    },
}

Evaluation semantics (Kleene tri-state logic from Post 5):

AND Truth Table:

T AND T = T    |  T AND F = F    |  T AND R = R
F AND T = F    |  F AND F = F    |  F AND R = F
R AND T = R    |  R AND F = F    |  R AND R = R

Where: T = TRUE, F = FALSE, R = REQUIRES_CONTEXT

Rules:

  • If any child is FALSE → result is FALSE (short-circuit)

  • If all children are TRUE → result is TRUE

  • If any child is REQUIRES_CONTEXT and no child is FALSE → result is REQUIRES_CONTEXT

Boolean OR — At Least One Condition Must Be True

// document.is_public OR user.has_special_access
&BooleanExpr{
    Op: BOOL_OR,
    Children: []*BooleanExpr{
        {
            Op: BOOL_PREDICATE,
            Pred: &Predicate{
                Left:  &IdentifierExpr{Name: "document.is_public"},
                Op:    CMP_EQ,
                Right: &LiteralExpr{Value: true, Type: CAV_T_BOOL},
            },
        },
        {
            Op: BOOL_PREDICATE,
            Pred: &Predicate{
                Left:  &IdentifierExpr{Name: "user.has_special_access"},
                Op:    CMP_EQ,
                Right: &LiteralExpr{Value: true, Type: CAV_T_BOOL},
            },
        },
    },
}

Evaluation semantics:

OR Truth Table:

T OR T = T    |  T OR F = T    |  T OR R = T
F OR T = T    |  F OR F = F    |  F OR R = R
R OR T = T    |  R OR F = R    |  R OR R = R

Where: T = TRUE, F = FALSE, R = REQUIRES_CONTEXT

Rules:

  • If any child is TRUE → result is TRUE (short-circuit)

  • If all children are FALSE → result is FALSE

  • If any child is REQUIRES_CONTEXT and no child is TRUE → result is REQUIRES_CONTEXT

Boolean NOT — Negate a Condition

// NOT user.is_suspended
&BooleanExpr{
    Op: BOOL_NOT,
    Children: []*BooleanExpr{
        {
            Op: BOOL_PREDICATE,
            Pred: &Predicate{
                Left:  &IdentifierExpr{Name: "user.is_suspended"},
                Op:    CMP_EQ,
                Right: &LiteralExpr{Value: true, Type: CAV_T_BOOL},
            },
        },
    },
}

Evaluation semantics:

NOT Truth Table:

NOT T = F
NOT F = T
NOT R = R

Where: T = TRUE, F = FALSE, R = REQUIRES_CONTEXT

Rules:

  • NOT TRUE = FALSE

  • NOT FALSE = TRUE

  • NOT REQUIRES_CONTEXT = REQUIRES_CONTEXT (can't negate unknown)

Important: BOOL_NOT negates the result of its child expression; it does not rewrite comparison operators. Therefore NOT (A == B) is distinct from (A != B) in the presence of REQUIRES_CONTEXT. Both yield REQUIRES_CONTEXT when parameters are missing, but the semantic evaluation path differs.

Function Calls: Dynamic Computations

Function calls enable dynamic computations within caveat expressions. Let's see how they work:

Example 1: Time-Based Access with Timezone Support

Problem: Business hours vary by timezone. We need to convert UTC to local time.

Solution: Use local_hour(now_utc, tz) function.

// Business hours: 9 AM - 5 PM in user's timezone
&CaveatDefinition{
    Name: "business_hours_tz",
    Parameters: []*CaveatParameter{
        &ScalarParameter{Name: "env.now_utc", Type: CAV_T_TIMESTAMP},
        &ScalarParameter{Name: "user.timezone", Type: CAV_T_STRING},
    },
    Expression: &BooleanExpr{
        Op: BOOL_AND,
        Children: []*BooleanExpr{
            // local_hour(now_utc, tz) >= 9
            {
                Op: BOOL_PREDICATE,
                Pred: &Predicate{
                    Left: &CallExpr{
                        FnName: "local_hour",
                        Args: []CaveatExpr{
                            &IdentifierExpr{Name: "env.now_utc"},
                            &IdentifierExpr{Name: "user.timezone"},
                        },
                    },
                    Op:    CMP_GE,
                    Right: &LiteralExpr{Value: 9, Type: CAV_T_INT},
                },
            },
            // local_hour(now_utc, tz) < 17
            {
                Op: BOOL_PREDICATE,
                Pred: &Predicate{
                    Left: &CallExpr{
                        FnName: "local_hour",
                        Args: []CaveatExpr{
                            &IdentifierExpr{Name: "env.now_utc"},
                            &IdentifierExpr{Name: "user.timezone"},
                        },
                    },
                    Op:    CMP_LT,
                    Right: &LiteralExpr{Value: 17, Type: CAV_T_INT},
                },
            },
        },
    },
}

At evaluation time:

ctx := NewCaveatContext()
ctx.SetValue("env.now_utc", time.Now().Unix())
ctx.SetValue("user.timezone", "America/New_York")

// local_hour(1640000000, "America/New_York") → 14
// 14 >= 9 AND 14 < 17 → TRUE

Example 2: String Matching with Operators

Problem: Check if user's email domain is in allowed list.

Solution: Use CMP_ENDS_WITH comparison operator.

// Allow access if email ends with "@company.com" OR "@partner.com"
&CaveatDefinition{
    Name: "email_domain_check",
    Parameters: []*CaveatParameter{
        &ScalarParameter{Name: "user.email", Type: CAV_T_STRING},
    },
    Expression: &BooleanExpr{
        Op: BOOL_OR,
        Children: []*BooleanExpr{
            {
                Op: BOOL_PREDICATE,
                Pred: &Predicate{
                    Left:  &IdentifierExpr{Name: "user.email"},
                    Op:    CMP_ENDS_WITH,
                    Right: &LiteralExpr{Value: "@company.com", Type: CAV_T_STRING},
                },
            },
            {
                Op: BOOL_PREDICATE,
                Pred: &Predicate{
                    Left:  &IdentifierExpr{Name: "user.email"},
                    Op:    CMP_ENDS_WITH,
                    Right: &LiteralExpr{Value: "@partner.com", Type: CAV_T_STRING},
                },
            },
        },
    },
}

Note: For simple string operations, we use built-in comparison operators (CMP_STARTS_WITH, CMP_ENDS_WITH, CMP_CONTAINS) instead of function calls. Function calls are needed for more complex operations like timezone conversions.

Example 3: List Membership Checks

Problem: Check if user's IP address is in allowlist.

Solution: Use CMP_IN operator with list parameters.

// Allow access if request IP is in allowlist
&CaveatDefinition{
    Name: "ip_allowlist",
    Parameters: []*CaveatParameter{
        &ScalarParameter{Name: "request.ip_address", Type: CAV_T_STRING},
        &ListParameter{Name: "document.allowed_ips", ElementType: CAV_T_STRING},
    },
    Expression: &BooleanExpr{
        Op: BOOL_PREDICATE,
        Pred: &Predicate{
            Left:  &IdentifierExpr{Name: "request.ip_address"},
            Op:    CMP_IN,
            Right: &IdentifierExpr{Name: "document.allowed_ips"},
        },
    },
}

At evaluation time:

ctx := NewCaveatContext()
ctx.SetValue("request.ip_address", "192.168.1.100")
ctx.SetValue("document.allowed_ips", []string{"192.168.1.100", "192.168.1.101"})

// "192.168.1.100" IN ["192.168.1.100", "192.168.1.101"] → TRUE

Design Decisions: Determinism and Context

Decision 1: Caller-Provided Time (Not System Time)

Question: Should now() read the system clock or require caller to provide time?

Answer: Caller provides time — for determinism and testability.

Rationale:

  • Determinism: Same inputs always produce same outputs

  • Testability: Can test time-based logic with fixed timestamps

  • Auditability: Evaluation results are reproducible

  • Distributed consistency: Multiple evaluators agree on the result

Bad (non-deterministic):

// ❌ System clock — different results at different times
&CallExpr{FnName: "now", Args: []CaveatExpr{}}

Good (deterministic):

// ✅ Caller provides timestamp — deterministic
&CallExpr{
    FnName: "local_hour",
    Args: []CaveatExpr{
        &IdentifierExpr{Name: "env.now_utc"},  // Caller provides
        &IdentifierExpr{Name: "user.timezone"},
    },
}

At call time:

// Application provides current time
ctx := NewCaveatContext()
ctx.SetValue("env.now_utc", time.Now().Unix())
ctx.SetValue("user.timezone", "America/New_York")

result := authzService.Check(resource, subject, ctx)

Decision 2: Minimal Missing-Set Tie-Break

Question: What happens when a subset of parameters is missing?

Answer: Use minimal missing-set tie-break — prefer results with fewer missing parameters.

The Problem:

Consider this caveat:

// (employee OR contractor) AND NOT suspended AND clearance >= 3

Scenario: Context has {employment_type: "employee", clearance_level: 5} but missing is_suspended.

Evaluation:

  • employment_type == "employee" → TRUE

  • employment_type == "contractor" → FALSE

  • employee OR contractor → TRUE

  • is_suspended == true → REQUIRES_CONTEXT (missing parameter)

  • NOT is_suspended → REQUIRES_CONTEXT

  • clearance_level >= 3 → TRUE

  • TRUE AND REQUIRES_CONTEXT AND TRUE → REQUIRES_CONTEXT

Result: REQUIRES_CONTEXT (need is_suspended to make final decision)

Why this matters: The system correctly identifies that it needs more information, rather than making a wrong decision.

Minimal missing-set optimization (for multiple candidates):

This optimization applies when evaluating multiple authorization paths (e.g., multiple tuples that could grant access). When multiple candidates return REQUIRES_CONTEXT, prefer the one with fewer missing parameters.

Context: This is relevant for graph traversal (Post 8) where multiple paths might lead to the same resource. For example:

Alice → document:1#viewer could be satisfied by:
  Path A: Direct tuple (missing {is_suspended, clearance_level})
  Path B: Via role (missing {is_suspended})
  Path C: Via group (missing {})

Choose Path C (0 missing) > Path B (1 missing) > Path A (2 missing)

Algorithm (detailed in Post 8):

ALGORITHM: SelectBestCandidate(candidates)

INPUT: List of evaluation results from different authorization paths

OUTPUT: Best result to return to caller

STEPS:
1. Separate candidates by result type:
   - granted = candidates where result == TRUE
   - denied = candidates where result == FALSE
   - partial = candidates where result == REQUIRES_CONTEXT

2. IF granted is not empty:
     RETURN first granted result (access granted)

3. IF partial is not empty:
     a. For each partial result, count missing parameters
     b. Sort by missing parameter count (ascending)
     c. RETURN partial result with fewest missing parameters
        (tells caller exactly what's needed)

4. ELSE:
     RETURN denied (all paths failed)

Example:

// Evaluate multiple paths
results := []EvaluationResult{
    {Granted: false, CaveatResult: REQUIRES_CONTEXT, MissingParams: []string{"is_suspended", "clearance"}},
    {Granted: false, CaveatResult: REQUIRES_CONTEXT, MissingParams: []string{"is_suspended"}},
    {Granted: true,  CaveatResult: TRUE, MissingParams: []string{}},
}

// Select best: Path 3 (granted) wins
best := SelectBestCandidate(results)
// Result: Granted = true

// If no path granted:
results := []EvaluationResult{
    {Granted: false, CaveatResult: REQUIRES_CONTEXT, MissingParams: []string{"is_suspended", "clearance"}},
    {Granted: false, CaveatResult: REQUIRES_CONTEXT, MissingParams: []string{"is_suspended"}},
}

best := SelectBestCandidate(results)
// Result: REQUIRES_CONTEXT with MissingParams = ["is_suspended"]
// (Prefer path with fewer missing params)

Rationale:

  • Efficiency: Minimize the number of parameters caller needs to provide

  • User experience: Ask for minimal information to make a decision

  • Determinism: Tie-break rule is deterministic (count-based, then lexicographic)

  • Practical: Helps callers understand the "cheapest" path to access

Note: For single-caveat evaluation (this post), there's only one path, so this optimization doesn't apply. It becomes critical in Post 8 when we have multiple authorization paths through the graph.

Implementation: Evaluation Algorithm

Here's the high-level algorithm for evaluating boolean expressions with function calls:

Algorithm 1: Evaluate Boolean Expression

ALGORITHM: EvaluateBooleanExpr(expr, context, params)

INPUT:
  - expr: BooleanExpr to evaluate
  - context: CaveatContext with runtime values
  - params: List of CaveatParameter definitions

OUTPUT:
  - CaveatEvalResult: TRUE | FALSE | REQUIRES_CONTEXT

STEPS:

1. MATCH expr.Op:

   CASE BOOL_PREDICATE:
     a. Evaluate Left side of predicate:
        leftVal, leftResult = EvaluateCaveatExpr(expr.Pred.Left, context)
        IF leftResult == REQUIRES_CONTEXT:
          RETURN REQUIRES_CONTEXT

     b. Evaluate Right side of predicate:
        rightVal, rightResult = EvaluateCaveatExpr(expr.Pred.Right, context)
        IF rightResult == REQUIRES_CONTEXT:
          RETURN REQUIRES_CONTEXT

     c. Apply comparison operator:
        result = ApplyCompareOp(expr.Pred.Op, leftVal, rightVal)
        RETURN result ? TRUE : FALSE

   CASE BOOL_AND:
     a. Initialize: hasRequiresContext = false
     b. FOR EACH child IN expr.Children:
          childResult = EvaluateBooleanExpr(child, context, params)
          IF childResult == FALSE:
            RETURN FALSE  // Short-circuit
          IF childResult == REQUIRES_CONTEXT:
            hasRequiresContext = true
     c. IF hasRequiresContext:
          RETURN REQUIRES_CONTEXT
        ELSE:
          RETURN TRUE

   CASE BOOL_OR:
     a. Initialize: hasRequiresContext = false
     b. FOR EACH child IN expr.Children:
          childResult = EvaluateBooleanExpr(child, context, params)
          IF childResult == TRUE:
            RETURN TRUE  // Short-circuit
          IF childResult == REQUIRES_CONTEXT:
            hasRequiresContext = true
     c. IF hasRequiresContext:
          RETURN REQUIRES_CONTEXT
        ELSE:
          RETURN FALSE

   CASE BOOL_NOT:
     a. childResult = EvaluateBooleanExpr(expr.Children[0], context, params)
     b. MATCH childResult:
          TRUE → RETURN FALSE
          FALSE → RETURN TRUE
          REQUIRES_CONTEXT → RETURN REQUIRES_CONTEXT

Algorithm 2: Evaluate Caveat Expression

ALGORITHM: EvaluateCaveatExpr(expr, context)

INPUT:
  - expr: CaveatExpr (IdentifierExpr | LiteralExpr | CallExpr)
  - context: CaveatContext with runtime values

OUTPUT:
  - (value, result) where result is TRUE | FALSE | REQUIRES_CONTEXT

STEPS:

1. MATCH expr type:

   CASE IdentifierExpr:
     a. value, exists = context.GetValue(expr.Name)
     b. IF NOT exists:
          RETURN (nil, REQUIRES_CONTEXT)
        ELSE:
          RETURN (value, TRUE)

   CASE LiteralExpr:
     a. RETURN (expr.Value, TRUE)

   CASE CallExpr:
     a. Look up function by name:
        fn = GetFunction(expr.FnName)
        IF fn == nil:
          RETURN (nil, FALSE)  // Unknown function

     b. Evaluate all arguments:
        args = []
        FOR EACH arg IN expr.Args:
          argVal, argResult = EvaluateCaveatExpr(arg, context)
          IF argResult == REQUIRES_CONTEXT:
            RETURN (nil, REQUIRES_CONTEXT)
          args.append(argVal)

     c. Call function:
        result = fn.Evaluate(args)
        RETURN (result, TRUE)

Algorithm 3: Apply Comparison Operator

ALGORITHM: ApplyCompareOp(op, left, right)

INPUT:
  - op: CompareOp (EQ, NE, LT, LE, GT, GE, IN, STARTS_WITH, ENDS_WITH, CONTAINS)
  - left: Left operand value
  - right: Right operand value

OUTPUT:
  - boolean: Comparison result

STEPS:

1. MATCH op:

   CASE CMP_EQ:
     RETURN left == right

   CASE CMP_NE:
     RETURN left != right

   CASE CMP_LT:
     // Numeric comparison
     RETURN toNumber(left) < toNumber(right)

   CASE CMP_LE:
     RETURN toNumber(left) <= toNumber(right)

   CASE CMP_GT:
     RETURN toNumber(left) > toNumber(right)

   CASE CMP_GE:
     RETURN toNumber(left) >= toNumber(right)

   CASE CMP_IN:
     // List membership: check if left is in right (list)
     FOR EACH element IN right:
       IF element == left:
         RETURN TRUE
     RETURN FALSE

   CASE CMP_STARTS_WITH:
     // String operation
     RETURN toString(left).startsWith(toString(right))

   CASE CMP_ENDS_WITH:
     RETURN toString(left).endsWith(toString(right))

   CASE CMP_CONTAINS:
     RETURN toString(left).contains(toString(right))

Type coercion rules:

  • Numeric types: CAV_T_INT, CAV_T_UINT, CAV_T_DOUBLE are comparable (coerce to common type)

  • String types: Only CAV_T_STRING is comparable with string operators

  • Boolean types: Only CAV_T_BOOL is comparable with equality operators

  • List types: Only CAV_T_LIST can be used with CMP_IN operator

  • No implicit conversions: Type mismatches are caught by static validation

Numeric coercion precedence:

  1. If either operand is DOUBLE, coerce both to DOUBLE

  2. If either operand is UINT and the other is INT, coerce both to INT64

  3. Otherwise, use native comparison

Examples:

// Numeric comparison (with coercion)
ApplyCompareOp(CMP_LT, int64(5), int64(10))     → true
ApplyCompareOp(CMP_GE, float64(3.5), int64(3))  → true (coerced to float: 3.5 >= 3.0)
ApplyCompareOp(CMP_EQ, uint64(100), int64(100)) → true (coerced to int64)

// String operations
ApplyCompareOp(CMP_STARTS_WITH, "[email protected]", "@company.com") → false
ApplyCompareOp(CMP_ENDS_WITH, "[email protected]", "@company.com")   → true
ApplyCompareOp(CMP_CONTAINS, "hello world", "world")                 → true

// List membership
ApplyCompareOp(CMP_IN, "192.168.1.100", []string{"192.168.1.100", "192.168.1.101"}) → true
ApplyCompareOp(CMP_IN, "admin", []string{"user", "viewer"})                          → false

// Boolean equality
ApplyCompareOp(CMP_EQ, true, true)   → true
ApplyCompareOp(CMP_NE, true, false)  → true

Error handling:

// Type mismatch (caught by static validation, but double-checked at runtime)
ApplyCompareOp(CMP_LT, "hello", 42)  → ERROR: "cannot compare string with int using <"

// Invalid operator for type
ApplyCompareOp(CMP_STARTS_WITH, 42, "hello")  → ERROR: "STARTS_WITH requires string operands"

// List element type mismatch
ApplyCompareOp(CMP_IN, "hello", []int{1, 2, 3})  → ERROR: "cannot check string membership in int list"

Key properties:

  • Short-circuit evaluation: AND stops at first FALSE, OR stops at first TRUE

  • Missing parameter propagation: REQUIRES_CONTEXT bubbles up through expression tree

  • Function purity: Functions are evaluated only when all arguments are available

  • Determinism: Same inputs always produce same outputs

  • Type safety: Static validation prevents type mismatches, runtime validation provides defense-in-depth

Complexity Analysis:

Time Complexity:

  • Best case (short-circuit): O(1) — first child in AND returns FALSE, or first child in OR returns TRUE

  • Average case: O(n) — where n is the number of predicates in the expression

  • Worst case: O(n × d × f) where:

    • n = number of predicates

    • d = maximum expression depth

    • f = maximum function execution time (bounded per registered function, not a global constant)

  • Function calls: O(f) per call, where f is bounded per function (e.g., 100μs for local_hour())

Space Complexity:

  • Recursion stack: O(d) where d = maximum expression depth (limited to 10)

  • Context storage: O(p) where p = number of parameters

  • Total: O(d + p), typically < 1KB per evaluation

Evaluation Order Guarantees:

Children are evaluated strictly left-to-right. This order is guaranteed for determinism—two evaluators must produce identical results given the same inputs.

// Example: Evaluation order is deterministic
&BooleanExpr{
    Op: BOOL_AND,
    Children: []*BooleanExpr{
        predicateA,  // ← Evaluated FIRST
        predicateB,  // ← Evaluated SECOND (only if A is TRUE)
        predicateC,  // ← Evaluated THIRD (only if A and B are TRUE)
    },
}

Important: Implementations MUST NOT reorder predicates for optimization. While reordering might improve performance in some cases, it would break determinism and make evaluation results unpredictable.

Performance characteristics:

  • Simple predicate (e.g., clearance >= 3): ~5μs

  • Function call (e.g., local_hour()): ~20μs

  • Complex expression (5 predicates, 2 functions): ~50μs

  • Typical caveat evaluation: < 100μs*

*Note: This is for single-expression evaluation only. Full authorization checks include graph traversal overhead, which adds proportional cost (covered in Post 8).

What We've Gained

Let's compare what we can express now vs. before:

🔴 Post 5 (ABAC v1) — Simple Predicates Only

Boolean Logic:

  • ❌ Single predicate only

  • Can't combine conditions with AND/OR/NOT

Function Calls:

  • ❌ Reserved (not active)

  • No dynamic computations

Complexity:

  • Simple: A >= B

  • One condition per caveat

Use Cases:

  • Time windows

  • Simple attribute checks

Evaluation:

  • ~5μs per check

  • Fast but limited

🟢 Post 7A (ABAC v2) — Full Boolean Algebra + Functions

Boolean Logic:

  • ✅ Full AND/OR/NOT support

  • Can express complex policies like (A ∨ B) ∧ ¬C ∧ D

Function Calls:

  • ✅ Active with whitelist registry

  • Dynamic computations: time conversions, string operations, list checks

Complexity:

  • Complex: (A ∨ B) ∧ ¬C ∧ D

  • Unlimited conditions per caveat

Use Cases:

  • Security clearance systems

  • HIPAA compliance rules

  • Financial transaction approval

  • Matches real-world systems (Google Cloud IAM, AWS IAM, Azure ABAC)

Evaluation:

  • ~50μs per complex caveat evaluation

  • ≈10× more work per check but typically < 100μs (acceptable for authorization)*

*Single-expression evaluation only; graph traversal adds proportional cost (Post 8).

Before Post 7A (Simple Predicates Only)

// Can only express: current_hour >= 9
&BooleanExpr{
    Op: BOOL_PREDICATE,
    Pred: &Predicate{
        Left:  &IdentifierExpr{Name: "current_hour"},
        Op:    CMP_GE,
        Right: &LiteralExpr{Value: 9, Type: CAV_T_INT},
    },
}

// Cannot express:
// - (employee OR contractor) AND NOT suspended
// - Business hours with timezone conversion
// - Complex multi-condition policies

After Post 7A (Full Boolean Algebra + Functions)

// Can express: (employee OR contractor) AND NOT suspended AND clearance >= 3
&BooleanExpr{
    Op: BOOL_AND,
    Children: []*BooleanExpr{
        {
            Op: BOOL_OR,
            Children: []*BooleanExpr{
                {Op: BOOL_PREDICATE, Pred: &Predicate{...}},  // employee
                {Op: BOOL_PREDICATE, Pred: &Predicate{...}},  // contractor
            },
        },
        {
            Op: BOOL_NOT,
            Children: []*BooleanExpr{
                {Op: BOOL_PREDICATE, Pred: &Predicate{...}},  // suspended
            },
        },
        {Op: BOOL_PREDICATE, Pred: &Predicate{...}},  // clearance >= 3
    },
}

// Can also express:
// - Time-based access with timezone conversion: local_hour(now_utc, tz) >= 9
// - String matching: email ENDS_WITH "@company.com"
// - List membership: ip IN allowed_ips
// - Arbitrary boolean combinations

Expressiveness gain: From simple single-predicate conditions to full ABAC with complex boolean logic and dynamic computations.

Real-world impact: We can now express authorization policies comparable to those in Google Cloud IAM, AWS IAM, and Azure ABAC—systems that all support multi-predicate boolean conditions and dynamic computations.

Takeaways

1. Boolean Algebra Enables Complex Policies

By activating BOOL_AND, BOOL_OR, and BOOL_NOT, we can express arbitrarily complex authorization policies:

  • Multi-predicate conditions: (A OR B) AND NOT C AND D

  • Nested logic: (A AND B) OR (C AND D)

  • Negation: NOT (A OR B) = NOT A AND NOT B (De Morgan's law)

2. Function Calls Enable Dynamic Computations

By activating CallExpr with a whitelist of pure functions, we can:

  • Convert UTC to local time: local_hour(now_utc, tz)

  • Perform string operations: to_lower(email), trim(name)

  • Check list membership: list_contains(allowed_ips, request_ip)

Critical constraint: All functions must be pure, deterministic, total, and bounded.

3. Determinism is Non-Negotiable

Every design decision prioritizes determinism:

  • ✅ Caller provides time (not system clock)

  • ✅ Whitelist-only function registry

  • ✅ Pure functions with no side effects

  • ✅ Type checking at runtime

  • ✅ Bounded execution time

Why: Ensures two evaluators always agree on the result, critical for distributed systems and audit compliance.

4. Tri-State Logic Handles Missing Parameters Gracefully

When parameters are missing:

  • AND: TRUE AND REQUIRES_CONTEXT = REQUIRES_CONTEXT

  • OR: FALSE OR REQUIRES_CONTEXT = REQUIRES_CONTEXT

  • NOT: NOT REQUIRES_CONTEXT = REQUIRES_CONTEXT

Result: System correctly identifies what information is needed, rather than making wrong decisions.

5. Short-Circuit Evaluation Improves Performance

  • AND stops at first FALSE

  • OR stops at first TRUE

  • Reduces unnecessary computation

  • Maintains determinism (evaluation order is defined)

What's Next?

In Post 7B, we'll explore:

  • Real-world composite caveats: Combining multiple conditions into single caveat definitions

  • Schema-level safety: Required caveats and subject constraints

  • Observability: Debugging complex caveats with evaluation traces

  • Edge cases: Type validation, expression depth limits, and safety measures

The challenge: How do we ensure complex caveats are safe, debuggable, and maintainable in production?

Summary

Post 7A activated the full power of boolean algebra in caveats:

  1. Boolean operators (AND, OR, NOT) enable complex multi-predicate conditions

  2. Function calls (CallExpr) enable dynamic computations with pure, deterministic functions

  3. Determinism is maintained through caller-provided time and whitelist-only functions

  4. Tri-state logic handles missing parameters gracefully

  5. Short-circuit evaluation improves performance

  6. Evaluation algorithms provide clear semantics for complex expressions

Real-world impact: We can now express sophisticated ABAC policies like security clearance systems, time-based access controls, and complex compliance rules—all while maintaining determinism and auditability.

Next: Composite caveats, observability, and safety measures (Post 7B).

Keep Reading

© 2026 Sub-Microseconds.
Report abusePrivacy policyTerms of use
beehiivPowered by beehiiv