Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Seclib.Network.Monotonicity

List.any_of_any_append_left — 🟢 proved

theorem · source

If any holds on a list, it holds on a superset (append). Go source: reachability.go — CanReach uses List.any; this is the abstract monotonicity principle underlying edge_monotone.

theorem List.any_of_any_append_left {l₁ l₂ : List α} {p : α → Bool}
    (h : l₁.any p = true) : (l₁ ++ l₂).any p = true

rule_check_mono — 🟢 proved

theorem · source

Abstract monotonicity: if a predicate holds when checking any over a set of rules, it still holds over a superset. Go source: reachability.go:36-51 — core of edge_monotone.

theorem rule_check_mono {rules extra : List SGRule}
    {check : SGRule → Bool}
    (h : rules.any check = true) :
    (rules ++ extra).any check = true

canReach_mono_abstract — 🟢 proved

theorem · source

If membership is preserved, any is preserved. Go source: reachability.go:36-51 The key invariant: adding an SG rule to a graph that already allows reachability cannot remove that reachability.

theorem canReach_mono_abstract
    (sgRules₁ sgRules₂ : String → List SGRule)
    (h_super : ∀ sg, ∀ r, r ∈ sgRules₁ sg → r ∈ sgRules₂ sg)
    (sgIds : List String) (check : SGRule → Bool)
    (h : sgIds.any (fun sg => (sgRules₁ sg).any check) = true) :
    sgIds.any (fun sg => (sgRules₂ sg).any check) = true

isolation_sound — 🟢 proved

theorem · source

If a host is tagged isolated and no host in the graph can reach it on any port (UNSAT), then canReachAny is false for all sources. Go source: graph.go:24 (IsIsolated), proof.go:588 (UNSAT)

theorem isolation_sound (g : NetGraph) (dst : Host)
    (_hIso : dst.isIsolated = true)
    (hUnsat : ∀ src, src ∈ g.hosts → g.canReachAny src dst = false) :
    ∀ src, src ∈ g.hosts → ¬ ReachableAny g src dst

hasGatedEgressPath — ⚪ definition

def · source

A graph has a gated egress path if an isolated host can reach a host whose subnet routes to a gated target. Go source: proof.go:560-584 (EVIDENCE_GATED condition)

def hasGatedEgressPath (g : NetGraph) : Prop

gated_not_unsat — 🟢 proved

theorem · source

If a gated egress path exists and no sink path exists, transitiveEgressVerdict returns evidenceGated, never unsat. Go source: proof.go:465 verdict precedence.

theorem gated_not_unsat (g : NetGraph)
    (hGated : g.isolatedHosts.any (fun iso =>

unsat_no_gated — 🟢 proved

theorem · source

Contrapositive: if verdict is UNSAT, no gated path exists. Go source: proof.go:465 (verdict precedence).

theorem unsat_no_gated (g : NetGraph)
    (h : transitiveEgressVerdict g = .unsat) :

transitiveEgress_decomposition — 🟢 proved

theorem · source

Transitive egress decomposes into two reachability queries: (1) isolated → service, (2) service has egress route. This is definitionally true from transitiveEgressSat. Go source: proof.go:532-557 (SAT check: canReachAnyPort then route classification).

theorem transitiveEgress_decomposition (g : NetGraph) :