The policy prover's solve time depends on the order of a module's rules #4664

User Story

I use OpenShell to contain an agent while it builds real projects. Before applying a policy, I check it with openshell-prover against my boundary. When I approved a large new dependency, the check came back inconclusive (solver timeout), and I could not tell whether the policy was safe or not.

Problem Statement

openshell-prover check returns a result in under a second for some candidate policies and times out on others that differ only in the order of their allow rules. With two rest allow rules whose paths share a long common prefix, the check decides in ~0 s when the path that exceeds the boundary is listed first; when an allowed path is listed first it returns inconclusive (solver_timeout) at the default budget (10 s), and needs 30 to 65 s (0.1.4; 150 to 168 s on 0.1.3) to name the path.

Impact / Why This Matters

A boundary check that is correct but order-sensitive gives inconclusive on policies it could decide, so an operator cannot tell "the policy is unsafe" from "the prover ran out of time". Raising the timeout does not scale: each allowed rule that sorts before the offending one added roughly two minutes (measured on 0.1.3). The workaround (reordering rules by hand, or re-running with a large budget) is fragile and defeats using the prover as an automated gate.

Acceptance Criteria

• The two candidate policies below decide in comparable time regardless of rule order.
• A policy that exceeds the boundary returns exceeds_boundary with the offending path within the default budget for this size of input.

Reproduction Steps

Uses only openshell-prover and three small files; no third-party tools. The paths are two Go module proxy objects in Cloud Storage, plain strings here (no Go toolchain): A (…aws-sdk-go-v1.55.8.zip), which the boundary allows, and K (…kubernetes-v1.31.0.zip), which exceeds it.

1. Save boundary.yaml:

   version: 1
   filesystem_policy:
     include_workdir: true
     read_only: [/usr, /lib, /etc]
     read_write: [/tmp]
   landlock:
     compatibility: hard_requirement
   process:
     run_as_user: "1000"
     run_as_group: "1000"
   network_policies:
     go:
       endpoints:
         - host: proxy.golang.org
           port: 443
           protocol: rest
           enforcement: enforce
           access: read-only
         - host: storage.googleapis.com
           port: 443
           protocol: rest
           enforcement: enforce
           rules:
             - allow:
                 method: GET
                 path: /proxy-golang-org-prod/6c63e6375d93395c-github.com:aws:aws-sdk-go-v1.55.8.zip
       binaries:
         - path: /usr/local/go/bin/go

2. Save candidate-slow.yaml (A listed before K):

   version: 1
   filesystem_policy:
     include_workdir: true
     read_only: [/usr, /lib, /etc]
     read_write: [/tmp]
   landlock:
     compatibility: hard_requirement
   process:
     run_as_user: "1000"
     run_as_group: "1000"
   network_policies:
     go:
       endpoints:
         - host: proxy.golang.org
           port: 443
           protocol: rest
           enforcement: enforce
           rules:
             - allow:
                 method: GET
                 path: /github.com/aws/aws-sdk-go/@v/v1.55.8.zip
         - host: storage.googleapis.com
           port: 443
           protocol: rest
           enforcement: enforce
           rules:
             - allow:
                 method: GET
                 path: /proxy-golang-org-prod/6c63e6375d93395c-github.com:aws:aws-sdk-go-v1.55.8.zip
             - allow:
                 method: GET
                 path: /proxy-golang-org-prod/fd22cb77aa61fb9f-k8s.io:kubernetes-v1.31.0.zip
       binaries:
         - path: /usr/local/go/bin/go

3. Save candidate-fast.yaml: the same as candidate-slow.yaml with the two storage.googleapis.com rules swapped (K before A).

4. openshell-prover check candidate-fast.yaml --boundary boundary.yaml → exceeds_boundary naming K, in 0.02 s.

5. openshell-prover check candidate-slow.yaml --boundary boundary.yaml → inconclusive (timeout) after the default 10 s.

6. openshell-prover check candidate-slow.yaml --boundary boundary.yaml --timeout 4m → exceeds_boundary naming K, in 34 to 64 s on 0.1.4 (three runs; 150 and 168 s on 0.1.3).

Long paths with a shared prefix are what trigger it; short synthetic paths decide fast in both orders.

Suggested UX (if applicable)

None required; the result and timing should not depend on authored rule order.

Environment

• OpenShell: v0.1.4 (also seen on v0.1.3)
• OS: macOS 26.6.2 (Darwin 25.6.0)
• Deployment: Docker 29.5.2 via Colima 0.10.3; Docker driver
• Prover: openshell-prover 0.1.4 (Homebrew), linked against Homebrew's z3 5.1.0

Logs

$ openshell-prover check candidate-slow.yaml --boundary boundary.yaml
result: inconclusive
coverage: domains=filesystem,network_l4,network_rest,process,landlock
reason: timeout

$ openshell-prover check candidate-fast.yaml --boundary boundary.yaml
result: exceeds_boundary
coverage: domains=filesystem,network_l4,network_rest,process,landlock
counterexample: network binary=- ancestor_binary=- binary_identity_required=false host=storage.googleapis.com:443 destination_ip=8.8.8.8 trusted_gateway=false protocol=rest method=GET path=/proxy-golang-org-prod/fd22cb77aa61fb9f-k8s.io:kubernetes-v1.31.0.zip