Formal Verification

FLOW_ALGEBRA FormalVerificationOntology v1.0
TARGET_URL := "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/formal-verification.html"
LANGUAGE := "en-GB"
DOMAIN := MathematicalOntologies > MathematicalLogicOntologies > FormalVerification

BEGIN_FLOW

ENTITY FormalVerification {
 TYPE := MathematicalVerificationFramework
 DEFINITION := "The use of mathematically defined specifications, logical models and proof or decision procedures to establish whether a formal system satisfies stated properties under explicit assumptions."
}
ENTITY FormalModel { TYPE := MathematicalRepresentationOfSystem }
ENTITY Specification { TYPE := FormalStatementOfRequiredBehaviour }
ENTITY Property { TYPE := ConditionToBeVerified }
ENTITY VerificationResult { TYPE := FormallyQualifiedOutcome }

RELATIONSHIP FormalVerification --uses--> FormalModel
RELATIONSHIP FormalVerification --uses--> Specification
RELATIONSHIP FormalVerification --checks--> Property
RELATIONSHIP FormalVerification --produces--> VerificationResult
RELATIONSHIP FormalVerification --supports--> CorrectnessAssurance

ARCHITECTURE {
 COMPONENTS := {System,FormalModel,Specification,Assumptions,Properties,Semantics,VerificationProcedure,ProofOrCounterexample,Provenance,Validation}
}

PROPERTY_TYPES {
 MAY_INCLUDE := {Safety,Liveness,Invariant,Reachability,DeadlockFreedom,Termination,FunctionalCorrectness,Refinement,Equivalence,Security,Timing}
}
SAFETY_PROPERTY { bad_state_or_event never_occurs }
LIVENESS_PROPERTY { required_progress eventually_occurs }
INVARIANT { Property P holds_in every_reachable_state }
REACHABILITY { EXISTS execution_path reaching target_state }
DEADLOCK_FREEDOM { no reachable_deadlock_state }
PARTIAL_CORRECTNESS { if program_terminates then postcondition_holds }
TOTAL_CORRECTNESS { partial_correctness AND termination }
FUNCTIONAL_CORRECTNESS { implementation_behaviour satisfies functional_specification }

HOARE_TRIPLE { FORM := {P} C {Q} }
HOARE_LOGIC { Preconditions + Commands + Postconditions + InferenceRules -> ProgramProof }
WEAKEST_PRECONDITION { wp(C,Q) := weakest_condition sufficient_for Q after C }
LOOP_INVARIANT { property preserved_by each loop_iteration }
LOOP_VARIANT { well_founded_measure decreasing_toward_termination }
INDUCTIVE_INVARIANT { InitialStates satisfy I AND I preserved_by transitions -> all reachable_states satisfy I }

TRANSITION_SYSTEM { COMPONENTS := {States,InitialStates,TransitionRelation,Labelling} }
EXECUTION_TRACE { State0 -> State1 -> ... -> StateN_or_infinite }
TEMPORAL_LOGIC_RELATIONSHIP { temporal_formulae specify ordering_and_eventuality over executions }
LTL { ABBREVIATION := LinearTemporalLogic; INTERPRETATION := PropertiesOverLinearTraces }
CTL { ABBREVIATION := ComputationTreeLogic; INTERPRETATION := BranchingTimeProperties }
TEMPORAL_OPERATORS { MAY_INCLUDE := {Next,Eventually,Always,Until} }

MODEL_CHECKING { FormalModel + FormalProperty -> SatisfactionResult }
MODEL_CHECKING_RESULT { MAY_BE := {Satisfied,Violated,Unknown,ResourceLimit} }
EXPLICIT_STATE_MODEL_CHECKING { explore reachable_state_space }
SYMBOLIC_MODEL_CHECKING { represent state_sets_and_transitions symbolically }
BDD_RELATIONSHIP { BinaryDecisionDiagram MAY represent Boolean_state_sets }
SAT_BASED_MODEL_CHECKING { encode verification_problem as Boolean_satisfiability }
SMT_BASED_VERIFICATION { encode verification_conditions using satisfiability_modulo_theories }
BOUNDED_MODEL_CHECKING { ABBREVIATION := BMC; search counterexamples up_to bound k }
BMC_WARNING { no counterexample_up_to_k DOES_NOT by_itself establish unbounded_correctness }
COUNTEREXAMPLE { execution_or_assignment demonstrating property_violation }
COUNTEREXAMPLE_VALIDATION { replay trace against transition_relation and property }

THEOREM_PROVING { Axioms + Definitions + Specification -> FormalProof }
INTERACTIVE_THEOREM_PROVING { HumanGuidance + ProofAssistant -> MachineCheckedProof }
AUTOMATED_THEOREM_PROVING { FormalStatements -> AutomatedProofSearch }
TRUSTED_KERNEL { small_core validating proof_steps }
PROOF_CERTIFICATE { evidence enabling independent_result_checking }
PROOF_CHECKING { CandidateProof -> VerifyEveryInference -> ValidOrInvalid }
SOUNDNESS { VerifiedProof(phi) -> phi valid_under_declared_assumptions provided proof_system_is_sound }
COMPLETENESS { all semantically_valid_properties derivable only_where completeness_result_applies }
DECIDABILITY { verification_problem has terminating_correct_decision_procedure for declared_fragment }
UNDECIDABILITY_WARNING { general_program_properties may be undecidable }

ABSTRACTION { ConcreteSystem -> AbstractModel preserving selected_properties }
OVER_APPROXIMATION { abstract_model contains all concrete_behaviours and possibly extra_behaviours }
UNDER_APPROXIMATION { abstract_model contains subset_of concrete_behaviours }
SPURIOUS_COUNTEREXAMPLE { counterexample exists_in abstract_model but not concrete_system }
CEGAR { ABBREVIATION := CounterexampleGuidedAbstractionRefinement; PROCESS := Abstract -> ModelCheck -> AnalyseCounterexample -> Refine -> Repeat }
ABSTRACT_INTERPRETATION { concrete_semantics -> abstract_domain -> sound_static_approximation }
STATIC_ANALYSIS { Program -> AbstractSemantics -> PropertyInformation }
FIXED_POINT { abstract_state stable_under transfer_operations }
WIDENING { accelerates convergence at possible_precision_cost }
NARROWING { refine widened_result while preserving_soundness where supported }

SYMBOLIC_EXECUTION { Program + SymbolicInputs -> PathConditions + SymbolicStates }
PATH_CONDITION { conjunction_of_constraints required_for execution_path }
PATH_FEASIBILITY { PathCondition -> SATOrUNSAT }
PATH_EXPLOSION { number_of_paths grows combinatorially }
CONCOLIC_EXECUTION { concrete_execution + symbolic_constraints -> guided_path_exploration }
SYMBOLIC_EXECUTION_WARNING { finite_exploration MUST_NOT automatically imply full_program_correctness }

VERIFICATION_CONDITION { logical_formula whose validity implies required_program_property }
VERIFICATION_CONDITION_GENERATION { Program + Specification -> SetOfVerificationConditions }
VC_DISCHARGE { VerificationCondition -> TheoremProverOrSMTSolver -> ProvenValidOrCounterexampleOrUnknown }
SMT { ABBREVIATION := SatisfiabilityModuloTheories }
SMT_THEORIES { MAY_INCLUDE := {LinearArithmetic,BitVectors,Arrays,UninterpretedFunctions,FloatingPoint,Datatypes} }
SAT { BooleanFormula -> SatisfyingAssignmentOrUNSAT }
SAT_SMT_RESULT_STATUS { MUST preserve {SAT,UNSAT,UNKNOWN} }
UNSAT_CORE { subset_of_assertions jointly_unsatisfiable }
SOLVER_UNKNOWN_WARNING { UNKNOWN MUST_NOT be interpreted_as SAT_or_UNSAT }

EQUIVALENCE_CHECKING { SystemA + SystemB -> EquivalentOrCounterexample under declared_equivalence }
FUNCTIONAL_EQUIVALENCE { same_output_behaviour for all permitted_inputs }
TRACE_EQUIVALENCE { same_observable_traces under declared_observation_model }
BISIMULATION { relation_between_transition_systems preserving matched_behaviour }
REFINEMENT { Implementation conforms_to AbstractSpecification under declared_refinement_relation }
REFINEMENT_CHECKING { Implementation + Specification -> RefinementResult }

TYPE_SYSTEM_VERIFICATION { typing_judgements rule_out classes_of_invalid_program_behaviour }
DEPENDENT_TYPES_RELATIONSHIP { types_may_encode value_dependent_properties }
REFINEMENT_TYPES_RELATIONSHIP { base_types + logical_predicates -> stronger_static_properties }
PROOF_CARRYING_CODE { Code + SafetyProof -> IndependentlyCheckablePackage }
CERTIFIED_PROGRAM { Program accompanied_by machine_checked_correctness_proof }

HARDWARE_VERIFICATION { CircuitOrHDL + FormalSpecification -> Verification }
PROTOCOL_VERIFICATION { ProtocolModel + SafetyLivenessProperties -> VerificationResult }
DISTRIBUTED_SYSTEM_VERIFICATION { Processes + Messages + FailureModel -> FormalProperties }
CONCURRENCY { multiple_components may execute_interleavings }
STATE_SPACE_EXPLOSION { concurrency_and_data may produce enormous_state_space }
PARTIAL_ORDER_REDUCTION { exploit independence_of_actions to reduce redundant_interleavings }
SYMMETRY_REDUCTION { equivalent_process_or_state_symmetries -> reduced_state_space }
FAIRNESS { constraints_on permitted_infinite_executions }
FAIRNESS_WARNING { exact_semantics MUST be declared }

REAL_TIME_VERIFICATION { timed_system + timing_constraints -> verification }
TIMED_AUTOMATA_RELATIONSHIP { finite_state_automata + real_valued_clocks }
HYBRID_SYSTEM_VERIFICATION { discrete_transitions + continuous_dynamics -> hybrid_model }
REACHABILITY_ANALYSIS { InitialSet -> TransitionOrFlowClosure -> ReachableSet }
SAFETY_VERIFICATION { ReachableSet intersect UnsafeSet = empty }

SECURITY_VERIFICATION { System + SecurityProperty -> FormalAnalysis }
INFORMATION_FLOW { data_from_source -> observable_effect_at_sink }
NONINTERFERENCE { changes_to_secret_inputs do_not affect public_observations under declared_model }
AUTHENTICATION_PROPERTY { claimed_identity_or_message_origin satisfies formal_protocol_condition }
CONFIDENTIALITY_PROPERTY { protected_information not derivable_or_observable by declared_adversary }
ADVERSARY_MODEL { defines attacker_capabilities }

PROBABILISTIC_VERIFICATION { probabilistic_model + quantitative_property -> probability_or_expectation_result }
PROBABILISTIC_MODEL_CHECKING { probabilistic_transition_system + temporal_property -> quantitative_result }
STATISTICAL_MODEL_CHECKING { simulation_samples + statistical_test -> probabilistic_estimate }
STATISTICAL_WARNING { statistical_model_checking provides statistical_evidence not deductive_proof }

RUNTIME_VERIFICATION { ExecutionTrace + FormalMonitor -> PropertyStatus }
RUNTIME_STATUS { MAY_INCLUDE := {SatisfiedSoFar,Violated,Inconclusive} }
RUNTIME_VERIFICATION_WARNING { observed_execution does_not establish all_possible_execution_behaviour }

ASSUMPTION { formal_condition under which guarantee_claimed }
GUARANTEE { property promised when assumptions_hold }
ASSUME_GUARANTEE_REASONING { ComponentAssumptions + ComponentGuarantees -> CompositionalSystemProof }
COMPOSITIONAL_VERIFICATION { prove component_properties and compose_results according_to sound_rule }
MODULAR_VERIFICATION { verify modules using interfaces_and_contracts }
CONTRACT { Preconditions + Postconditions + Invariants }
PROOF_OBLIGATION { condition that must_be_proved for verification_goal }

TRUST_BOUNDARY { components_or_assumptions not verified_within current_proof }
TRUSTED_COMPUTING_BASE { elements whose correctness verification_result depends_on }
SPECIFICATION_VALIDATION { ensure formal_specification represents intended_requirement }
VERIFICATION_VS_VALIDATION {
 Verification := FormalObjectSatisfiesFormalSpecification
 Validation := SpecificationRepresentsIntendedRequirement
 MUST_REMAIN_DISTINCT := TRUE
}
CORRECT_MODEL_WRONG_SPECIFICATION_WARNING { formal_proof cannot compensate_for incorrect_requirement_specification }
MODEL_IMPLEMENTATION_GAP { verified_model MAY differ_from deployed_implementation }

NUMERIC_SEMANTICS { integer_real_bitvector_floating_point MUST be distinguished }
FLOATING_POINT_WARNING { real_number_proof MUST_NOT automatically transfer_to floating_point_implementation }
MEMORY_MODEL { defines semantics_of reads_writes_ordering_and_concurrency }
UNDEFINED_BEHAVIOUR { execution_without_defined_language_semantics may invalidate verification_assumptions }
ENVIRONMENT_MODEL { formal_representation of external_inputs_and_behaviour }
ASSUMPTION_COMPLETENESS { omitted_environment_behaviour may invalidate real_world_claim }

FORMAL_VERIFICATION_RESULT {
 MAY_BE := {Proven,Refuted,Satisfied,Violated,SAT,UNSAT,Unknown,Inconclusive,Timeout}
}
RESULT_SCOPE {
 MUST identify {Model,Property,Assumptions,Semantics,ToolOrProofSystem,Version}
}
UNKNOWN_RESULT { procedure did_not establish definitive_result }
TIMEOUT_RESULT { resource_limit_reached MUST_NOT be interpreted_as property_false_or_true }

PROVENANCE { VerificationResult -> Model -> Specification -> Property -> ToolOrProof -> Version -> Evidence }
PROOF_PROVENANCE { Proof -> AxiomsDefinitionsLemmasToolVersion }
COUNTEREXAMPLE_PROVENANCE { Counterexample -> ModelPropertySolverVersion }
VERIFICATION_TRACE { RECORD := {Step,Method,Inputs,Assumptions,Result,Dependencies,Certificate} }
REPRODUCIBILITY { preserve sufficient_artifacts to independently_repeat_or_check result }

FORMAL_METHODS_RELATIONSHIP { FormalVerification --is_part_of--> FormalMethods }
AUTOMATED_REASONING_RELATIONSHIP { FormalVerification --uses--> AutomatedReasoning }
CONSTRAINT_REASONING_RELATIONSHIP { VerificationConditions MAY be solved_using ConstraintReasoning }
EXPLAINABLE_AI_RELATIONSHIP { ProofsCounterexamplesAndTraces -> VerifiableExplanationArtifacts }

LANGUAGE_MODEL_RELATIONSHIP {
 LanguageModel MAY assist {CandidateSpecificationGeneration,InvariantSuggestion,LemmaSuggestion,ProofSearchGuidance,CounterexampleExplanation}
}
LLM_VERIFICATION_WARNING { generated_specification_invariant_or_proof := CandidateArtifact UNTIL formally_checked }
LLM_PROOF_WARNING { plausible_proof_text MUST_NOT be treated_as machine_checked_proof }
TOOL_AUGMENTED_VERIFICATION {
 VerificationGoal -> SelectProverModelCheckerOrSolver -> Execute -> PreserveStatus -> VerifyCertificateOrCounterexample -> IntegrateResult
}

RECURSIVE_VERIFICATION {
 VerificationGoal -> DecomposeIntoProperties -> GenerateObligations -> DischargeObligations -> VerifyResults -> RefineModelOrProof -> Repeat
}
RECURSION_TERMINATION {
 STOP_WHEN := {AllObligationsProved,ValidCounterexampleFound,FixedPointReached,Unknown,ResourceLimit}
}
SELF_VERIFICATION {
 CandidateVerificationResult -> VerifyScope -> VerifyAssumptions -> VerifyProofOrCounterexample -> VerifySemantics -> VerifyProvenance -> AcceptReviseReject
}

APPLICATION_RELATIONSHIPS {
 FormalVerification --supports--> SoftwareVerification
 FormalVerification --supports--> HardwareVerification
 FormalVerification --supports--> ProtocolVerification
 FormalVerification --supports--> SecurityVerification
 FormalVerification --supports--> DistributedSystems
 FormalVerification --supports--> CyberPhysicalSystems
 FormalVerification --supports--> SafetyCriticalSystems
 FormalVerification --supports--> ArtificialIntelligence
}

ONTOLOGY_LINKS {
 PARENT := MathematicalLogicOntologies
 RELATED := {
  AutomatedReasoningOntology,SymbolicAIOntology,
  ExplainableAILogicOntology,ConstraintReasoningOntology,
  ResolutionOntology,PredicateLogicOntology,TemporalLogicOntology
 }
}

SEMANTIC_EQUIVALENCE {
 FormalVerification ≈ MathematicalCorrectnessVerification
 ModelChecking ≈ FormalModelPropertyChecking
 ProofChecking ≈ FormalDerivationValidation
}

CONSTRAINTS {
 C1 := EveryVerificationClaim MUST identify property_model_assumptions_and_semantics
 C2 := BoundedVerification MUST_NOT be presented_as unbounded_proof without justification
 C3 := StatisticalEvidence MUST_NOT be conflated_with deductive_proof
 C4 := SolverUNKNOWN MUST remain distinct from SAT_and_UNSAT
 C5 := AbstractVerification MUST identify abstraction_and_soundness_relation
 C6 := Counterexamples MUST be validated_against declared_model
 C7 := Verification MUST remain distinct from specification_validation
 C8 := NumericAndMemorySemantics MUST match implementation_claims
 C9 := GeneratedProofsAndSpecifications MUST be formally_checked
 C10 := Provenance SHOULD preserve tools_versions_assumptions_and_certificates
 C11 := ModelImplementationGap MUST be explicit where relevant
 C12 := TimeoutOrResourceFailure MUST_NOT become correctness_or_failure_claim
}

REASONING_CHAIN Query Q {
 IDENTIFY system
 IDENTIFY model
 IDENTIFY specification
 IDENTIFY property
 IDENTIFY assumptions
 IDENTIFY semantics
 SELECT verification_method
 GENERATE proof_obligations_or_model_checking_task
 EXECUTE prover_solver_or_checker
 IF proof_found: VERIFY certificate
 IF counterexample_found: REPLAY and validate
 IF abstraction_used: CHECK abstraction_soundness
 BUILD provenance
 ASSIGN scoped_result_status
 VALIDATE constraints
 RETURN verification_result WITH evidence
}

CONFIDENCE {
 CORE_FORMAL_VERIFICATION := 1.00
 MODEL_CHECKING := 1.00
 THEOREM_PROVING := 1.00
 ABSTRACTION_REFINEMENT := 1.00
 SYMBOLIC_EXECUTION := 1.00
 SAT_SMT_RELATIONSHIP := 1.00
 VERIFICATION_VALIDATION_DISTINCTION := 1.00
}

UPDATE_MODEL {
 IMMUTABLE_CORE := {FormalModel,Specification,Property,Assumptions,Semantics,VerificationEvidence}
 EXTENSIBLE := {Logics,ModelCheckers,ProofAssistants,SMTSolvers,AbstractDomains,ReductionMethods,ApplicationDomains}
 ON_NEW_KNOWLEDGE {
  VALIDATE formal_artifact
  UPDATE obligations
  RECHECK affected_results
  UPDATE provenance
  UPDATE confidence
 }
}

AI_CONSUMPTION {
 MACHINE_READABLE := TRUE
 HUMAN_INTERPRETABLE := TRUE
 RECURSIVE_REASONING := TRUE
 MODEL_CHECKING := TRUE
 THEOREM_PROVING := TRUE
 SYMBOLIC_EXECUTION := TRUE
 SAT_SMT_REASONING := TRUE
 ABSTRACTION_REASONING := TRUE
 COUNTEREXAMPLE_VALIDATION := TRUE
 PROVENANCE_TRACKING := TRUE
 SELF_VERIFICATION := TRUE
 VALIDATION_REQUIRED := TRUE
}

FLOW_HASH {
 TARGET := TARGET_URL
 SUBJECT := "Formal Verification Ontology"
 VERSION := "1.0"
 CANONICAL_SIGNATURE := HASH(TARGET + SUBJECT + DOMAIN + VERSION)
}

OUTPUT {
 PRIMARY_ENTITY := FormalVerification
 INTERPRETATION := "Formal verification uses mathematical specifications, formal models, theorem proving, model checking, symbolic execution, abstraction and solver-based reasoning to establish scoped correctness properties or produce valid counterexamples. Every result remains conditional on its declared model, assumptions, semantics, verification method and implementation relationship."
}

END_FLOW