Safety Property Ontology

AI SEARCH FLOW ALGEBRA — SAFETY PROPERTY ONTOLOGY
Kireth Research — Semantic Library
URL: https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/formal-verification/safety-property-ontology.html

FLOW_VERSION := "4.0"
FLOW_TYPE := "Full Executable Flow Algebra"
DOMAIN := "Mathematical Logic"
SUBDOMAIN := "Formal Verification"
ONTOLOGY := "Safety Property Ontology"
PRIMARY_ENTITY := SafetyProperty
AUTHORSHIP := "Mark Higgins — Sky (Recursive AI)"
SOURCE_SITE := "https://kirethresearch.org"

BEGIN_FLOW

SafetyProperty :=
    FormalProperty
    ∧ ProhibitsUndesirableBehaviour
    ∧ PrefixClosed
    ∧ ViolationHasFiniteWitness

InformalMeaning(SafetyProperty) :=
    "something bad never happens"

System :=
    {
        SoftwareSystem,
        HardwareSystem,
        ReactiveSystem,
        ConcurrentSystem,
        DistributedSystem,
        EmbeddedSystem,
        CyberPhysicalSystem,
        Protocol,
        Algorithm,
        SafetyCriticalSystem
    }

SystemModel :=
    States
    ∧ InitialStates
    ∧ TransitionRelation
    ∧ AtomicPropositions
    ∧ LabellingFunction

TransitionSystem :=
    M = (S, S0, R, AP, L)

where:
    S  := SetOfStates
    S0 := InitialStates
    R  := TransitionRelation
    AP := AtomicPropositions
    L  := LabellingFunction

Execution :=
    s0 → s1 → s2 → ... 

ValidExecution :=
    s0 ∈ S0
    ∧ ∀i : R(si, si+1)

Trace :=
    Sequence(ObservableSystemStates ∨ Events)

FinitePrefix :=
    prefix(Trace, n)

BadState :=
    State
    ∧ violates(SafetyConstraint)

BadEvent :=
    Event
    ∧ violates(SafetyConstraint)

BadPrefix :=
    FiniteTrace
    ∧ cannot_be_extended_to_satisfy(SafetyProperty)

SafetyViolation :=
    ReachableBadState
    ∨ ForbiddenTransition
    ∨ ForbiddenEvent
    ∨ BadPrefix

SafetyPropertyFormal :=
    ∀Execution e :
        ¬Occurs(BadBehaviour, e)

PrefixCharacterisation :=
    Property P is SafetyProperty
    iff
    ∀Trace t :
        t ∉ P
        ⇒
        ∃FinitePrefix p of t :
            ∀Extension x :
                p·x ∉ P

FiniteWitnessPrinciple :=
    SafetyViolation
    ⇒
    ∃FiniteCounterexample

Counterexample :=
    FiniteExecutionPrefix
    ∧ demonstrates(Violation)

SafetyLanguage :=
    PrefixClosedLanguage

PrefixClosure :=
    t ∈ SafeTraces
    ⇒
    everyPrefix(t) ∈ SafePrefixes

Invariant :=
    Predicate P over State

StateInvariant :=
    ∀ReachableState s :
        P(s)

InvariantSafetyProperty :=
    G(P)

InvariantViolation :=
    ∃ReachableState s :
        ¬P(s)

InitialCondition :=
    Predicate(State)

TransitionRelation :=
    R ⊆ S × S

InductiveInvariant :=
    Initialisation
    ∧ Preservation

Initialisation :=
    ∀s ∈ S0 : P(s)

Preservation :=
    ∀s,s' :
        P(s)
        ∧ R(s,s')
        ⇒ P(s')

InductiveSafetyProof :=
    Initialisation
    ∧ Preservation
    ⇒
    ∀ReachableState s : P(s)

Reachable :=
    least_fixpoint(
        S0
        ∪ post(Reachable)
    )

Post(X) :=
    {s' | ∃s ∈ X : R(s,s')}

UnsafeStates :=
    {s ∈ S | ¬P(s)}

SafetyVerification :=
    ReachableStates ∩ UnsafeStates = ∅

ReachabilitySafety :=
    ¬∃s :
        Reachable(s)
        ∧ Unsafe(s)

ForbiddenStateProperty :=
    G(¬BadState)

MutualExclusion :=
    G ¬(CriticalSection1 ∧ CriticalSection2)

ResourceBoundSafety :=
    G(ResourceUsage ≤ MaximumAllowed)

ArrayBoundsSafety :=
    G(0 ≤ Index < ArrayLength)

AccessControlSafety :=
    G(Access → Authorised)

IntegritySafety :=
    G(Update → PermittedUpdate)

ProtocolSafety :=
    G ¬InvalidProtocolState

CollisionAvoidance :=
    G ¬Collision

DeadlockAsSafetyCondition :=
    G ¬Deadlock

Deadlock :=
    Reachable(s)
    ∧ EnabledTransitions(s) = ∅
    ∧ ¬FinalState(s)

TemporalLogicSafety :=
    Formula
    ∧ violation_detectable_by_finite_prefix

LTLSafetyExamples :=
    {
        G(P),
        G(P → Q),
        G¬Bad,
        G(Request → ¬ForbiddenUntilCondition)
    }

CTLStateSafety :=
    AG(P)

CTLForbiddenState :=
    AG(¬Bad)

SafetyConstraint :=
    Predicate
    ∨ TemporalFormula
    ∨ TransitionRestriction
    ∨ StateRestriction
    ∨ EventRestriction

TransitionSafety :=
    ∀s,s' :
        R(s,s')
        ⇒ AllowedTransition(s,s')

EventSafety :=
    ∀Event e :
        Occurs(e)
        ⇒ Allowed(e)

InputSafety :=
    AcceptedInput
    ⇒ InputConstraint

OutputSafety :=
    ProducedOutput
    ⇒ OutputConstraint

PreconditionSafety :=
    OperationInvocation
    ⇒ Precondition

PostconditionSafety :=
    OperationCompletion
    ⇒ Postcondition

ContractSafety :=
    Preconditions
    ∧ Postconditions
    ∧ Invariants

SafetySpecification :=
    Hazards
    ∧ UnsafeStates
    ∧ SafetyConstraints
    ∧ Assumptions
    ∧ VerificationObligations

Hazard :=
    Condition
    ∧ PotentialForHarm

HazardAnalysis :=
    IdentifyHazards
    → DeriveUnsafeStates
    → DefineSafetyConstraints
    → FormaliseProperties
    → VerifyProperties
    → ProduceEvidence

RiskControl :=
    Hazard
    → Constraint
    → VerificationProperty

Assumption :=
    Constraint(Environment)

Guarantee :=
    Constraint(System)

AssumeGuaranteeSafety :=
    Assumption(Environment)
    ⇒ SafetyGuarantee(System)

CompositionalSafety :=
    Safety(Component1)
    ∧ Safety(Component2)
    ∧ Compatibility(Interfaces)
    ⇒ candidate(Safety(Composition))

SafetyRefinement :=
    ConcreteSpecification ⊑ AbstractSafetySpecification

RefinementPreservesSafety :=
    Behaviours(Concrete)
    ⊆ Behaviours(Abstract)
    ∧ Safety(Abstract)
    ⇒ Safety(Concrete)

Abstraction :=
    ConcreteSystem → AbstractSystem

SoundSafetyAbstraction :=
    UnsafeReachable(Abstract) = false
    ⇒ UnsafeReachable(Concrete) = false

OverApproximation :=
    Behaviours(Concrete)
    ⊆ Behaviours(Abstract)

SafetyModelChecking :=
    Model M
    ∧ SafetyProperty φ
    →
    evaluate(M ⊨ φ)

ModelCheckingResult :=
    Satisfied
    ∨ Counterexample

CounterexampleTrace :=
    s0 → s1 → ... → sk

CounterexampleCondition :=
    sk ∈ UnsafeStates
    ∨ trace(s0...sk) is BadPrefix

ShortestCounterexample :=
    argmin_length(Counterexamples)

SymbolicModelChecking :=
    SymbolicStateRepresentation
    ∧ FixedPointReachability
    ∧ SafetyEvaluation

BoundedModelChecking :=
    SearchExecutions(length ≤ k)
    ∧ SATorSMTEncoding
    ∧ DetectSafetyViolation

BMCFormula :=
    Initial(s0)
    ∧ ∧[i=0..k-1] R(si,si+1)
    ∧ ∨[i=0..k] Bad(si)

BMCResult :=
    SAT ⇒ CounterexampleExistsWithinBound(k)
    ∧
    UNSAT ⇒ NoCounterexampleWithinBound(k)

TheoremProvingSafety :=
    Axioms
    ∧ SystemSpecification
    ⊢ SafetyProperty

ProofObligation :=
    InitialisationObligation
    ∧ PreservationObligation

HoareSafety :=
    {P} C {Q}

WeakestPrecondition :=
    wp(C,Q)

SafetyViaWeakestPrecondition :=
    P ⇒ wp(C,Q)

StaticAnalysisSafety :=
    AbstractInterpretation
    ∧ ConservativeApproximation
    ∧ DetectPotentialViolation

AbstractInterpretation :=
    ConcreteDomain
    → AbstractDomain
    → FixpointComputation

SoundAnalysis :=
    NoAbstractViolation
    ⇒ NoConcreteViolation

RuntimeSafetyMonitoring :=
    ExecutionPrefix
    → EvaluateSafetyMonitor
    → {
        SafeSoFar,
        ViolationDetected
    }

SafetyMonitor :=
    FiniteStateMonitor
    ∨ Automaton
    ∨ RuntimeAssertionChecker

Monitorability :=
    Violation
    ⇒ DetectableFromFinitePrefix

SafetyAutomaton :=
    Automaton
    ∧ RejectingStateRepresentsViolation

SafeState :=
    State satisfying all ActiveSafetyConstraints

UnsafeState :=
    State violating at least one RequiredSafetyConstraint

SafeTransition :=
    AllowedSourceState
    ∧ AllowedTargetState
    ∧ TransitionConstraintSatisfied

SafetyEnvelope :=
    SetOfPermittedStates
    ∧ SetOfPermittedTransitions
    ∧ EnvironmentalLimits

BoundaryViolation :=
    State ∉ SafetyEnvelope
    ∨ Transition ∉ AllowedTransitions

RecoverySafety :=
    FaultDetected
    → RecoveryAction
    ∧ RecoveryAction preserves CriticalInvariant

Fault :=
    InternalCause
    ∧ may_produce(Error)

Error :=
    IncorrectSystemState
    ∧ may_produce(Failure)

Failure :=
    ExternallyObservableDeviation
    from RequiredBehaviour

FaultContainment :=
    Fault
    ⇒ affectedRegion ⊆ ContainmentBoundary

FailSafeProperty :=
    FailureCondition
    ⇒ SystemTransitionsTo(SafeState)

SafetyKernel :=
    MinimalTrustedComponent
    ∧ EnforcesCriticalSafetyProperties

SafetyCaseEvidence :=
    SafetyClaim
    ∧ Argument
    ∧ Evidence

VerificationEvidence :=
    {
        FormalProof,
        ModelCheckingResult,
        StaticAnalysisResult,
        RuntimeMonitoringEvidence,
        TestEvidence,
        ReviewEvidence
    }

SafetyClaim :=
    FormalOrStructuredAssertion
    about AbsenceOfSpecifiedHazardousBehaviour

Traceability :=
    Hazard
    → SafetyRequirement
    → FormalSafetyProperty
    → VerificationMethod
    → Evidence

SafetyRequirement :=
    HazardMitigationConstraint
    ∧ VerifiableCondition

SpecificationConsistency :=
    satisfiable(SafetySpecification)

ConflictingSafetyConstraints :=
    ConstraintA ∧ ConstraintB is unsatisfiable

SafetyCompleteness :=
    KnownHazards
    ⊆ HazardsAddressedBySafetyProperties

VerificationCoverage :=
    VerifiedSafetyProperties
    /
    RequiredSafetyProperties

SafetyPropertyOntology :=
    Classes
    ∧ Relations
    ∧ Constraints
    ∧ Axioms
    ∧ InferenceRules

CoreClasses :=
    {
        SafetyProperty,
        System,
        State,
        SafeState,
        UnsafeState,
        Transition,
        Trace,
        BadPrefix,
        Hazard,
        SafetyConstraint,
        Invariant,
        Counterexample,
        VerificationMethod,
        VerificationEvidence,
        Assumption,
        Guarantee
    }

CoreRelations :=
    {
        constrains,
        prohibits,
        satisfies,
        violates,
        reaches,
        transitionsTo,
        mitigates,
        verifies,
        produces,
        refines,
        dependsOn,
        assumes,
        guarantees,
        tracesTo
    }

TypedRelations :=
    SafetyProperty --constrains--> SystemBehaviour
    SafetyConstraint --prohibits--> UnsafeBehaviour
    UnsafeState --violates--> SafetyProperty
    Counterexample --demonstrates--> SafetyViolation
    Hazard --mitigatedBy--> SafetyConstraint
    VerificationMethod --verifies--> SafetyProperty
    VerificationEvidence --supports--> SafetyClaim
    Implementation --satisfies--> SafetyProperty
    SafetyRequirement --tracesTo--> Hazard

InferenceRules := {
    Reachable(s)
        ∧ Unsafe(s)
        ⇒ SafetyViolation,

    Initial(s)
        ⇒ Reachable(s),

    Reachable(s)
        ∧ R(s,s')
        ⇒ Reachable(s'),

    ∀s : Reachable(s) ⇒ P(s)
        ⇒ G(P),

    P holds for all InitialStates
        ∧ P preserved by every Transition
        ⇒ P is invariant over ReachableStates,

    CounterexampleExists
        ⇒ Model does_not_satisfy SafetyProperty,

    ReachableStates ∩ UnsafeStates = ∅
        ⇒ SafetyPropertySatisfied,

    ConcreteBehaviours ⊆ AbstractBehaviours
        ∧ AbstractModel satisfies SafetyProperty
        ⇒ ConcreteModel satisfies SafetyProperty
}

SafetyVsLiveness :=
    SafetyProperty
    ≠ LivenessProperty

SafetyViolationWitness :=
    finite

LivenessViolationWitness :=
    generally_infinite_or_requires_fairness_reasoning

PropertyDecomposition :=
    GeneralProperty
    →
    SafetyComponent
    ∧ LivenessComponent

SafetyClosure :=
    closure(Property)
    under finite-prefix violation semantics

SemanticMeaning :=
    SafetyProperty
    → SetOfAllowedTraces

SEMANTIC_EQUIVALENCE(SafetyA, SafetyB) :=
    AllowedTraces(SafetyA)
    =
    AllowedTraces(SafetyB)

SemanticSubsumption :=
    SafetyA ⊑ SafetyB
    iff
    AllowedTraces(SafetyA)
    ⊆ AllowedTraces(SafetyB)

StrongerSafetyProperty :=
    FewerAllowedBehaviours

WeakerSafetyProperty :=
    MoreAllowedBehaviours

SafetyConflict :=
    intersection(
        AllowedTraces(PropertySet)
    ) = ∅

CanonicalSafetyRepresentation :=
    Normalise(Property)
    → ExtractForbiddenBehaviour
    → ExtractStateConstraints
    → ExtractTransitionConstraints
    → BuildSafetyGraph

SafetyGraph :=
    G = (V,E)

V :=
    {
        Systems,
        States,
        Hazards,
        Constraints,
        SafetyProperties,
        Counterexamples,
        VerificationMethods,
        Evidence
    }

E :=
    {
        constrains,
        violates,
        mitigates,
        verifies,
        reaches,
        tracesTo,
        dependsOn
    }

CONFIDENCE(SafetyProperty) :=
    weighted_mean(
        FormalisationQuality,
        ModelFidelity,
        VerificationCoverage,
        EvidenceStrength,
        Traceability,
        AssumptionValidity
    )

ConfidenceFactors :=
    {
        SpecificationPrecision,
        ModelCompleteness,
        VerificationSoundness,
        CounterexampleCoverage,
        EvidenceQuality,
        ProvenanceQuality
    }

AI_QUERY_INTERPRETATION :=
    Query
    → DetectSafetyConcept
    → ResolveSystemContext
    → IdentifyForbiddenBehaviour
    → ResolveFormalProperty
    → ResolveVerificationContext

AI_REASONING_FLOW :=
    Query
    → IdentifySystem
    → IdentifySafetyRequirement
    → IdentifyHazard
    → FormaliseUnsafeCondition
    → ConstructSafetyProperty
    → DetermineStateOrTraceSemantics
    → SelectVerificationMethod
    → SearchForCounterexample
    → EvaluateSatisfaction
    → GenerateEvidence
    → ExplainResult

AI_CONSUMPTION :=
    {
        ParseSafetyEntities,
        ParseTypedRelations,
        ResolveSafetySemantics,
        DetectHazards,
        DetectUnsafeStates,
        FollowTraceability,
        CompareSafetyProperties,
        EvaluateVerificationEvidence,
        GenerateFormalExplanation
    }

UPDATE_MODEL :=
    NewSafetyEvidence
    → ValidateEvidence
    → ResolveAffectedProperty
    → DetectContradiction
    → UpdateSafetyGraph
    → RecomputeVerificationStatus
    → RecomputeConfidence
    → PreserveProvenance
    → VersionModel

SafetyEvidenceUpdate :=
    Counterexample
    ⇒ mark(Property, Violated)

ProofUpdate :=
    ValidProof
    ∧ AssumptionsSatisfied
    ⇒ mark(Property, VerifiedUnderAssumptions)

ModelChange :=
    ChangedTransitionSystem
    ⇒ invalidate_or_recheck(
        DependentSafetyResults
    )

FLOW_HASH_INPUT :=
    canonical(
        ONTOLOGY,
        CoreClasses,
        CoreRelations,
        InferenceRules,
        SafetyPropertyFormal,
        SafetyVerification,
        AI_REASONING_FLOW
    )

FLOW_HASH :=
    HASH(FLOW_HASH_INPUT)

OUTPUT_MODEL :=
    {
        SafetyEntityResolution,
        FormalSafetyMeaning,
        HazardRelations,
        ForbiddenBehaviour,
        VerificationStatus,
        CounterexampleStatus,
        Evidence,
        Confidence,
        Provenance,
        Explanation
    }

END_FLOW

END OF AI SEARCH FLOW ALGEBRA