Deterministic Policy Evaluator Design

Status: Final Version: 1.0 Owner: Policy Guild Last Updated: 2025-11-27

Overview

The Policy Engine evaluator is designed for deterministic, reproducible execution. Given identical inputs, the evaluator produces byte-for-byte identical outputs regardless of host, timezone, or execution timing. This enables:

• Reproducible audit trails
• Offline verification of policy decisions
• Content-addressed caching of evaluation results
• Bit-exact replay for debugging and compliance

Contract and Guarantees

Determinism Guarantees

1. Input Determinism: All inputs are content-addressed or explicitly provided via the evaluation context.
2. Output Determinism: Given identical PolicyEvaluationRequest, the evaluator returns identical PolicyEvaluationResult objects.
3. Ordering Determinism: Rule evaluation order is stable and deterministic.
4. Value Determinism: All computed values use deterministic types (decimal vs float, immutable collections).

Prohibited Operations

The following operations are prohibited during policy evaluation:

Allowed Operations

Rule Ordering Semantics

Evaluation Order

Rules are evaluated in the following deterministic order:

1. Primary Sort: rule.Priority (ascending - lower priority number evaluates first)
2. Secondary Sort: Declaration order (index in the compiled IR document)

var orderedRules = document.Rules
    .Select((rule, index) => new { rule, index })
    .OrderBy(x => x.rule.Priority)
    .ThenBy(x => x.index)
    .ToImmutableArray();

First-Match Semantics

The evaluator uses first-match semantics:

• Rules are evaluated in order until one matches
• The first matching rule determines the base result
• No further rules are evaluated after a match
• If no rules match, a default result is returned

Exception Application Order

When multiple exceptions could apply, specificity scoring determines the winner:

1. Specificity Score: Computed from scope constraints (rule names, severities, sources, tags)
2. Tie-breaker 1: CreatedAt timestamp (later wins)
3. Tie-breaker 2: Id lexicographic comparison (earlier wins)

This ensures deterministic exception selection even with identical specificity scores.

Safe Value Types

Numeric Types

The severity lookup table maps normalized severity strings to decimal values:

"critical" => 5m
"high"     => 4m
"medium"   => 3m
"moderate" => 3m
"low"      => 2m
"info"     => 1m
"none"     => 0m
"unknown"  => -1m

String Comparisons

All string comparisons use StringComparer.OrdinalIgnoreCase for deterministic, culture-invariant comparison.

Collection Types

Timestamp Handling

Context-Injected Timestamp

The evaluation timestamp is provided via the evaluation context, not read from the system clock:

public sealed record PolicyEvaluationContext(
    PolicyEvaluationSeverity Severity,
    PolicyEvaluationEnvironment Environment,
    PolicyEvaluationAdvisory Advisory,
    PolicyEvaluationVexEvidence Vex,
    PolicyEvaluationSbom Sbom,
    PolicyEvaluationExceptions Exceptions,
    DateTimeOffset EvaluationTimestamp);  // Injected, not DateTime.UtcNow

Timestamp Format

All timestamps in outputs use ISO-8601 format with UTC timezone:

2025-11-27T14:30:00.000Z

Expression Evaluation

Boolean Expressions

Short-circuit evaluation is deterministic:

• AND: Left-to-right, stops on first false
• OR: Left-to-right, stops on first true

Identifier Resolution

Identifiers resolve in deterministic order:

1. Local scope (loop variables, predicates)
2. Global context (severity, env, vex, advisory, sbom)
3. Built-in constants (true, false)
4. Null (unresolved)

Member Access

Member access on scoped objects follows a fixed schema:

• severity.normalized, severity.score
• advisory.source, advisory.<metadata-key>
• vex.status, vex.justification
• sbom.tags, sbom.components

Verification

Content Hashing

Evaluation inputs and outputs can be content-addressed using SHA-256:

Input Hash:  SHA256(canonical_json(PolicyEvaluationRequest))
Output Hash: SHA256(canonical_json(PolicyEvaluationResult))

Golden Test Vectors

Test vectors are provided in docs/modules/policy/samples/deterministic-evaluator/:

Hash Recording

Each test vector records:

• Input content hash
• Expected output content hash
• Human-readable input/output for inspection

Implementation Notes

PolicyEvaluator Class

Located at: src/Policy/StellaOps.Policy.Engine/Evaluation/PolicyEvaluator.cs

Key determinism features:

• Uses ImmutableArray for ordered rule iteration
• Exception selection uses deterministic tie-breaking
• All collection operations preserve order

PolicyExpressionEvaluator Class

Located at: src/Policy/StellaOps.Policy.Engine/Evaluation/PolicyExpressionEvaluator.cs

Key determinism features:

• Uses decimal for numeric comparisons
• Severity ordering via static lookup table
• Immutable scope objects

Compliance Checklist

Before shipping changes to the evaluator, verify:

• [ ] No DateTime.Now or DateTime.UtcNow usage in evaluation path
• [ ] No Random or Guid.NewGuid() in evaluation path
• [ ] No network or filesystem access in evaluation path
• [ ] All collections use immutable types
• [ ] Numeric comparisons use decimal
• [ ] String comparisons use StringComparer.OrdinalIgnoreCase
• [ ] Golden tests pass with recorded hashes

References

• Prep document: docs/modules/policy/prep/2025-11-20-policy-engine-20-002-prep.md
• Sprint task: POLICY-ENGINE-20-002 in docs/implplan/SPRINT_124_policy_reasoning.md
• Implementation: src/Policy/StellaOps.Policy.Engine/Evaluation/