Automatic White-Box Testing of First-Order Logic Ontologies

Javier Álvez, Montserrat Hermo, Paqui Lucio, German Rigau

Abstract

Formal ontologies expressed in First-Order Logic (FOL) are foundational to knowledge representation but are prone to logical errors and redundancies. This paper introduces a white-box testing framework that automatically generates logical conjectures from axiom syntax. Using Automated Theorem Provers (ATPs) as an oracle, the system identifies defects such as typos and redundant sub-formulas. The approach was validated on several large-scale ontologies, including Adimen-SUMO and FPK, revealing significant defects even in mature systems.

Introduction

In Artificial Intelligence, ontologies serve as formal blueprints of knowledge, defining domain concepts through First-Order Logic (FOL) axioms. However, engineering these ontologies is a complex task. Like software code, logical blueprints often harbor "bugs"—typos, redundant rules that impede reasoning performance, or contradictions.

Traditional "black-box" testing relies on manual Competency Questions (CQs) to verify outputs. While useful, black-box testing is labor-intensive and fails to detect internal structural "bloat" or subtle logical defects that do not immediately break high-level queries. This research proposes an automated alternative that treats ontology engineering more like modern software development.

Methodology: White-Box Testing for FOL

The proposed framework shifts the focus to "white-box" testing, where the internal syntax of axioms drives test generation. This automated process involves three main stages:

  1. Test Generation: For each axiom, the system generates two types of conjectures:
  2. Falsity-tests (FT): These are statements that should not be provable if the axiom is lean and correct. If an ATP manages to prove an FT, it indicates a redundancy or a logical error.
  3. Truth-tests (TT): These are the negations of FTs. They should be provable and are used to measure the "suitability" of an axiom—essentially how much of the intended logic is functioning.
  4. Automation: Axioms are converted into Negation Normal Form. The system identifies disjunctions and implications to systematically probe for logical weaknesses without requiring a human to understand the domain semantics.
  5. The Oracle: State-of-the-art Automated Theorem Provers (such as Vampire) act as the judge, determining the validity of the generated conjectures.

Experimental Setup and Datasets

The framework was evaluated against several prominent FOL ontologies. These range from foundational linguistic models to massive knowledge bases used in formal mathematical proofs.

Table 1: Distribution of rules and non-rules across the evaluated ontologies.

As shown in Table 1, the datasets vary significantly in scale. FPK represents a massive corpus with over 78,000 rules, while Adimen-SUMO contains a balanced mix of rules and non-rules. The testing framework was applied to these diverse structures to assess its generalizability.

Results and Discussion

The framework successfully identified non-trivial defects across all tested ontologies, including those considered "mature."

Adimen-SUMO

The tool was used to iteratively improve Adimen-SUMO from version 2.4 to 2.6. The testing detected and facilitated the repair of 21 typos, 3 redundant axioms, 17 incorrect axioms, and 47 redundant sub-formulas. In version 2.6, 54% of the axioms are now certified as "completely suitable" for automated reasoning.

KIF-DOLCE

Testing revealed a critical structural flaw in KIF-DOLCE. The addition of simple constants (e.g., a specific "world") triggered a hidden contradiction within the foundational definitions of "worlds" and "particulars." This finding suggests that nearly all axioms in this version were operating in a logically compromised environment.

FPK

Despite its high degree of formalization for the Kepler conjecture proof, 10.6% of FPK's axioms contained redundancies. While many were minor (such as redundant "True" constants), their identification demonstrates the tool's precision at scale.

Conclusion

Automatic white-box testing provides a scalable, objective method for cleaning up formal ontologies. While the detection of defects is now automated, the resolution of these issues—interpreting ATP proofs to rewrite axioms—still requires human expertise. Future work will focus on expanding the types of redundancies detected and improving ATP performance through axiom selection techniques to minimize "unknown" results from prover timeouts.

Summary updated

Abstract

Formal ontologies are axiomatizations in a logic-based formalism. The development of formal ontologies, and their important role in the Semantic Web area, is generating considerable research on the use of automated reasoning techniques and tools that help in ontology engineering. One of the main aims is to refine and to improve axiomatizations for enabling automated reasoning tools to efficiently infer reliable information. Defects in the axiomatization can not only cause wrong inferences, but can also hinder the inference of expected information, either by increasing the computational cost of, or even preventing, the inference. In this paper, we introduce a novel, fully automatic white-box testing framework for first-order logic ontologies. Our methodology is based on the detection of inference-based redundancies in the given axiomatization. The application of the proposed testing method is fully automatic since a) the automated generation of tests is guided only by the syntax of axioms and b) the evaluation of tests is performed by automated theorem provers. Our proposal enables the detection of defects and serves to certify the grade of suitability --for reasoning purposes-- of every axiom. We formally define the set of tests that are generated from any axiom and prove that every test is logically related to redundancies in the axiom from which the test has been generated. We have implemented our method and used this implementation to automatically detect several non-trivial defects that were hidden in various first-order logic ontologies. Throughout the paper we provide illustrative examples of these defects, explain how they were found, and how each proof --given by an automated theorem-prover-- provides useful hints on the nature of each defect. Additionally, by correcting all the detected defects, we have obtained an improved version of one of the tested ontologies: Adimen-SUMO.
BibTeX
@article{alvez2017automatic,
  author = {Javier Álvez and Montserrat Hermo and Paqui Lucio and German Rigau},
  title = {{Automatic White-Box Testing of First-Order Logic Ontologies}},
  journal = {J. Log. Comput.},
  year = {2017},
  doi = {10.1093/logcom/exz001},
}
Figure