Plan, apply and roll back changes to a production ontology, with a blast radius report and a proof an auditor can re-check.
Rust ai-nativedescription-logicsformal-verificationinfrastructure-as-codeisabelle-languageknowledge-graphleanlean4mcpmcp-serverontologyowlowl2reasoningrustshaclsparqltheorem-proving
//! The Lean certificate layer, end to end.
//!
//! `reason --certificate DIR` writes what the reasoner started from and, for
//! every triple it inferred, the rule and premises it used. `lean/` holds a
//! checker for that certificate whose soundness is a machine-checked theorem
//! (`OOCert.certificate_sound`): a certificate it accepts contains only
//! triples entailed by the asserted graph. These tests close the loop.
//!
//! 1. Every ontology this repository ships certifies. The list is walked,
//! not hand-picked, and anything excluded is named with the reason.
//! 2. Every rule the reasoner has appears in a certificate the checker
//! accepts, so the emitter and the checker agree on all twenty premise
//! orders, not just the common ones.
//! 3. The checker can say no. A forged conclusion, a premise outside the
//! graph, and the exact derivation `cls-svf1` used to make before it was
//! found unsound are each rejected. A gate that cannot fail is not a gate.
//!
//! The checker needs a Lean toolchain (`lake`). Without one these tests skip
//! loudly through `common::skip_unless`; the CI job that installs Lean runs
//! them with `OO_REQUIRE_FIXTURES=1`, which turns that skip into a failure.
mod common;
use open_ontologies::graph::GraphStore;
use open_ontologies::reason::{InferenceTarget, Reasoner};
use std::path::{Path, PathBuf};
use std::process::Command;
use std::sync::{Arc, OnceLock};
fn repo() -> PathBuf {
PathBuf::from(env!("CARGO_MANIFEST_DIR"))
}
fn lean_dir() -> PathBuf {
repo().join("lean")
}
fn lake_available() -> bool {
// `.current_dir(lean_dir())` is not cosmetic. elan resolves the toolchain
// from the working directory's `lean-toolchain`, and the crate root is the
// one directory in this repository with none in its ancestry. Run from
// there against an elan that has no default toolchain, which is exactly
// what `leanprover/lean-action` installs, `lake --version` exits non-zero
// with "no default toolchain configured". The probe then reported lake as
// missing, `skip()` returned false, and `OO_REQUIRE_FIXTURES=1` turned
// that into five panics: the CI job that gates the proofs could not pass,
// while every local run was green because a developer machine has a
// default toolchain. `checker()` below already did this correctly, which
// is why the real `lake build` would have worked.
Command::new("lake")
.arg("--version")
.current_dir(lean_dir())
.output()
.map(|o| o.status.success())
.unwrap_or(false)
}
fn skip() -> bool {
common::skip_unless(
lake_available(),
"lake (the Lean 4 build tool)",
"install elan from https://github.com/leanprover/elan; lean/lean-toolchain pins the version",
)
}
/// Build the checker once per test binary. The proofs are part of the build,
/// so a failure here is a failure, never a skip.
fn checker() -> &'static Path {
static BUILT: OnceLock<PathBuf> = OnceLock::new();
BUILT.get_or_init(|| {
let out = Command::new("lake")
.arg("build")
.current_dir(lean_dir())
.output()
.expect("run lake build");
assert!(
out.status.success(),
"lake build failed:\n{}\n{}",
String::from_utf8_lossy(&out.stdout),
String::from_utf8_lossy(&out.stderr)
);
let exe = lean_dir().join(".lake").join("build").join("bin").join("oo-cert");
assert!(exe.exists(), "checker binary missing at {}", exe.display());
exe
})
}
/// Run the checker on a certificate directory. Returns (accepted, output).
fn check(dir: &Path) -> (bool, String) {
let out = Command::new(checker())
.arg(dir.join("asserted.tsv"))
.arg(dir.join("derivations.tsv"))
.output()
.expect("run oo-cert");
let text = format!(
"{}{}",
String::from_utf8_lossy(&out.stdout),
String::from_utf8_lossy(&out.stderr)
);
(out.status.success(), text)
}
fn scratch(name: &str) -> PathBuf {
let dir = std::env::temp_dir().join(format!("oo-cert-{}-{}", name, std::process::id()));
let _ = std::fs::remove_dir_all(&dir);
std::fs::create_dir_all(&dir).unwrap();
dir
}
fn certify_turtle(ttl: &str, profile: &str, dir: &Path) -> serde_json::Value {
let store = Arc::new(GraphStore::new());
store.load_turtle(ttl, None).unwrap();
let out = Reasoner::run_full(&store, profile, false, InferenceTarget::DefaultGraph, Some(dir)).unwrap();
serde_json::from_str(&out).unwrap()
}
const PREFIXES: &str = r#"
@prefix : <http://ex.org/> .
@prefix owl: <http://www.w3.org/2002/07/owl#> .
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
"#;
/// One ontology that fires all twenty rules.
const EVERY_RULE: &str = r#"
:A rdfs:subClassOf :B . :B rdfs:subClassOf :C . :a a :A .
:p rdfs:domain :Dom ; rdfs:range :Rng . :s :p :o .
:q rdfs:subPropertyOf :r . :r rdfs:subPropertyOf :t . :s :q :o .
:anc a owl:TransitiveProperty . :x :anc :y . :y :anc :z .
:near a owl:SymmetricProperty . :x :near :y .
:parent owl:inverseOf :child . :m :parent :n . :u :child :v .
:a owl:sameAs :a2 .
:E1 owl:equivalentClass :E2 . :pe1 owl:equivalentProperty :pe2 .
:R1 a owl:Restriction ; owl:onProperty :has ; owl:someValuesFrom :F . :w :has :f . :f a :F .
:RA a owl:Restriction ; owl:onProperty :hasPart ; owl:allValuesFrom :Part .
:whole a :RA ; :hasPart :bit .
:R2 a owl:Restriction ; owl:onProperty :col ; owl:hasValue :red .
:K rdfs:subClassOf :R2 . :k a :K . :j :col :red .
:I owl:intersectionOf ( :M1 :M2 ) . :i a :M1 , :M2 .
:U owl:unionOf ( :N1 :N2 ) . :n a :N2 .
"#;
const ALL_RULES: [&str; 19] = [
"rdfs2", "rdfs3", "rdfs5", "rdfs7", "rdfs9", "rdfs11",
"prp-trp", "prp-symp", "prp-inv1", "prp-inv2", "eq-sym",
// scm-eqc1 and scm-eqp1 each license two conclusions, so they appear twice
// in a certificate under one id. The second used to be emitted as
// "scm-eqc2" / "scm-eqp2", which name different W3C rules.
"scm-eqc1", "scm-eqp1",
"cls-svf1", "cls-avf", "cls-hv1", "cls-hv2", "cls-int1", "cls-uni",
];
#[test]
fn every_rule_family_appears_in_an_accepted_certificate() {
if skip() {
return;
}
let dir = scratch("every-rule");
let r = certify_turtle(&format!("{PREFIXES}{EVERY_RULE}"), "owl-rl-ext", &dir);
let by_rule = r["certificate"]["by_rule"].as_object().expect("by_rule in the response");
let missing: Vec<&str> = ALL_RULES.iter().copied().filter(|k| !by_rule.contains_key(*k)).collect();
assert!(missing.is_empty(), "rules that never fired on the all-rules ontology: {missing:?}\n{r}");
assert_eq!(
r["certificate"]["derivations"], r["inferred_count"],
"one certificate line per inferred triple: {r}"
);
let (ok, out) = check(&dir);
assert!(ok, "the checker rejected the all-rules certificate:\n{out}");
assert!(out.contains("\"ok\":true"), "{out}");
}
#[test]
fn a_forged_conclusion_is_rejected() {
if skip() {
return;
}
let dir = scratch("forged");
certify_turtle(&format!("{PREFIXES}{EVERY_RULE}"), "owl-rl-ext", &dir);
let (ok, _) = check(&dir);
assert!(ok, "the honest certificate must pass first");
// rdfs9 with premises that do not support the conclusion.
let forged = "rdfs9\t<http://ex.org/a>\t<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>\t<http://ex.org/Z>\t\
<http://ex.org/a>\t<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>\t<http://ex.org/A>\t\
<http://ex.org/A>\t<http://www.w3.org/2000/01/rdf-schema#subClassOf>\t<http://ex.org/B>\n";
let path = dir.join("derivations.tsv");
let mut content = std::fs::read_to_string(&path).unwrap();
content.push_str(forged);
std::fs::write(&path, content).unwrap();
let (ok, out) = check(&dir);
assert!(!ok, "a conclusion the premises do not support must be rejected:\n{out}");
assert!(out.contains("\"ok\":false") && out.contains("first_rejected"), "{out}");
}
#[test]
fn a_premise_outside_the_graph_is_rejected() {
if skip() {
return;
}
let dir = scratch("outside");
certify_turtle(&format!("{PREFIXES}{EVERY_RULE}"), "owl-rl-ext", &dir);
// Well-formed rdfs9 whose subClassOf premise nobody asserted or derived.
let forged = "rdfs9\t<http://ex.org/a>\t<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>\t<http://ex.org/Ghost>\t\
<http://ex.org/a>\t<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>\t<http://ex.org/A>\t\
<http://ex.org/A>\t<http://www.w3.org/2000/01/rdf-schema#subClassOf>\t<http://ex.org/Ghost>\n";
let path = dir.join("derivations.tsv");
let mut content = std::fs::read_to_string(&path).unwrap();
content.push_str(forged);
std::fs::write(&path, content).unwrap();
let (ok, out) = check(&dir);
assert!(!ok, "a premise that is neither asserted nor derived must be rejected:\n{out}");
}
#[test]
fn the_derivation_the_old_svf_rule_made_is_rejected() {
if skip() {
return;
}
// The ontology from tests/reason_rl_ext_soundness_test.rs, and the line
// the reasoner used to emit for it: x ∈ C from C ⊑ ∃p.D and x ∈ ∃p.D.
let dir = scratch("old-svf");
let ttl = format!(
"{PREFIXES}
:C rdfs:subClassOf :R .
:R a owl:Restriction ; owl:onProperty :p ; owl:someValuesFrom :D .
:x :p :y . :y a :D ."
);
let r = certify_turtle(&ttl, "owl-rl-ext", &dir);
let (ok, out) = check(&dir);
assert!(ok, "the sound derivations must pass: {out}\n{r}");
let forged = "cls-svf1\t<http://ex.org/x>\t<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>\t<http://ex.org/C>\t\
<http://ex.org/R>\t<http://www.w3.org/2002/07/owl#onProperty>\t<http://ex.org/p>\t\
<http://ex.org/R>\t<http://www.w3.org/2002/07/owl#someValuesFrom>\t<http://ex.org/D>\t\
<http://ex.org/x>\t<http://ex.org/p>\t<http://ex.org/y>\t\
<http://ex.org/y>\t<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>\t<http://ex.org/D>\n";
let path = dir.join("derivations.tsv");
let mut content = std::fs::read_to_string(&path).unwrap();
content.push_str(forged);
std::fs::write(&path, content).unwrap();
let (ok, out) = check(&dir);
assert!(!ok, "the converse of a subclass axiom has no rule; the checker must reject it:\n{out}");
assert!(out.contains("cls-svf1"), "the rejection names the step: {out}");
}
#[test]
fn owl_dl_refuses_to_pretend_it_has_a_certificate() {
let store = Arc::new(GraphStore::new());
store.load_turtle(&format!("{PREFIXES} :A rdfs:subClassOf :B ."), None).unwrap();
let dir = scratch("owl-dl");
let err = Reasoner::run_full(&store, "owl-dl", false, InferenceTarget::DefaultGraph, Some(&dir))
.expect_err("owl-dl has no rule trace and must say so");
assert!(err.to_string().contains("no derivation certificate"), "{err}");
}
/// Every RDF file the repository tracks, rather than a hand-picked list of
/// directories.
///
/// The list used to be five named directories, three of which hold no RDF at
/// all, so 59 of the 128 tracked RDF files were never walked, and they were
/// excluded SILENTLY. That contradicted this file's own promise that anything
/// excluded is named with the reason, and the README's claim that CI certifies
/// every RDF file in the repository. Walking from the root makes both true, and
/// it is what surfaced the literal-subject defect in `prp-symp` and friends
/// (`tests/reason_literal_subject_test.rs`), which lived in `benchmark/`, a
/// directory the old list did not name.
const SIZE_CAP: u64 = 4 * 1024 * 1024;
/// Build output, dependency trees and virtual environments. Each holds RDF that
/// is not this repository's to certify: a Python venv drops pyshacl's own
/// `shacl.ttl` under site-packages, and it certified happily, but it is theirs.
const SKIP_DIRS: [&str; 8] = [
"node_modules", "target", ".lake", ".git", ".venv", "venv", "site-packages", "__pycache__",
];
/// The RDF files this repository actually contains, from `git ls-files`.
///
/// Enumerating from git rather than from the filesystem is what makes "every
/// RDF file in this repository" a statement with one meaning. A filesystem walk
/// sees whatever a developer has generated locally as well, so it takes 190
/// LUBM files nobody committed on one machine and none on a fresh clone, and
/// the run stops being comparable between them. It is also minutes slower for
/// no extra coverage.
fn corpus() -> Vec<PathBuf> {
let out = Command::new("git")
.args(["ls-files", "-z", "*.ttl", "*.owl", "*.rdf", "*.nt"])
.current_dir(repo())
.output()
.expect("run git ls-files");
assert!(out.status.success(), "git ls-files failed: {}", String::from_utf8_lossy(&out.stderr));
let mut files: Vec<PathBuf> = String::from_utf8_lossy(&out.stdout)
.split('\0')
.filter(|p| !p.is_empty())
// `tests/fixtures/clash-coverage/` holds one contradictory graph per clash
// detector, each written to make exactly that detector fire (#160), plus a
// near-miss twin. They are test data and not ontologies: swept as corpus they
// would turn a measurement of the shipped corpus into a statement about this
// repository's own fixtures, which is measuring the ruler. The same reasoning
// and the same treatment as `tests/fixtures/horn-coverage/`.
// `tests/clash_detector_coverage_test.rs` asserts this exclusion is still here.
.filter(|p| !p.starts_with("tests/fixtures/clash-coverage/"))
// `docs/assets/claims/` holds the tiny ontologies the certified-claims
// figure is drawn from. They exist to demonstrate a downgrade and a
// disagreement, not to be ontologies, and counted as corpus they would
// dilute a measurement of what this repository actually ships. Same
// reasoning and same treatment as `tests/fixtures/horn-coverage/`.
.filter(|p| !p.starts_with("docs/assets/claims/"))
.filter(|p| !SKIP_DIRS.iter().any(|d| p.split('/').any(|seg| seg == *d)))
.map(|p| repo().join(p))
.collect();
files.sort();
files
}
#[test]
fn every_shipped_ontology_certifies() {
if skip() {
return;
}
let files = corpus();
assert!(files.len() >= 120, "expected the whole corpus, found {} files", files.len());
let mut excluded: Vec<(String, String)> = Vec::new();
let mut failures: Vec<(String, String)> = Vec::new();
let mut certified = 0usize;
let mut total_derivations = 0u64;
for path in &files {
let rel = path.strip_prefix(repo()).unwrap().display().to_string();
let size = std::fs::metadata(path).unwrap().len();
if size > SIZE_CAP {
excluded.push((rel, format!("{} bytes, over the {} byte cap", size, SIZE_CAP)));
continue;
}
let store = Arc::new(GraphStore::new());
if let Err(e) = store.load_file(&path.display().to_string()) {
excluded.push((rel, format!("does not parse: {}", e.to_string().lines().next().unwrap_or(""))));
continue;
}
let dir = scratch(&format!("corpus-{}", certified));
let out = match Reasoner::run_full(&store, "owl-rl-ext", false, InferenceTarget::DefaultGraph, Some(&dir)) {
Ok(o) => o,
Err(e) => {
failures.push((rel, format!("reasoner error: {e}")));
continue;
}
};
let r: serde_json::Value = serde_json::from_str(&out).unwrap();
if r["certificate"]["derivations"] != r["inferred_count"] {
failures.push((rel.clone(), format!("certificate has {} lines for {} inferred triples", r["certificate"]["derivations"], r["inferred_count"])));
}
let (ok, text) = check(&dir);
if ok {
certified += 1;
total_derivations += r["inferred_count"].as_u64().unwrap_or(0);
eprintln!("CERTIFIED {rel}: {} asserted, {} derived", r["initial_triples"], r["inferred_count"]);
} else {
failures.push((rel, text));
}
let _ = std::fs::remove_dir_all(&dir);
}
eprintln!("certified {certified} files, {total_derivations} derivations checked");
for (f, why) in &excluded {
eprintln!("EXCLUDED {f}: {why}");
}
assert!(certified >= 100, "too few files certified ({certified}); excluded: {excluded:?}");
assert!(total_derivations > 0, "the corpus produced no inferences at all, so nothing was checked");
assert!(
failures.is_empty(),
"{} certificate(s) rejected or malformed:\n{}",
failures.len(),
failures.iter().map(|(f, t)| format!("--- {f}\n{t}")).collect::<Vec<_>>().join("\n")
);
}