Formal Consistency Checking over Specifications in Natural Languages

Rongjie Yan, Chih‐Hong Cheng, Guangquan Zhang, Yesheng Chai

TL;DR

The SpecCC framework automatically translates natural language system requirements into Linear Temporal Logic (LTL) and verifies their consistency. By combining NLP with formal synthesis techniques, it ensures that high-level specifications are not just mathematically satisfiable, but "realizable"—meaning a physical system can actually be built to follow them without needing to predict the future.

What Problem Does This Paper Address?

In the early stages of software and hardware development, requirements are almost always written in natural language (like English). This creates a dangerous "semantic gap." Vague English sentences are difficult to verify, yet formalizing them into logic manually is time-consuming and error-prone.

Even when requirements are formalized, a hidden trap remains: unrealizability. A set of requirements might be mathematically consistent but physically impossible to implement. For example, a requirement stating "the output must always match the input three seconds from now" is logically fine but requires the system to have "clairvoyance" over future events. This paper introduces a tool to catch these contradictions early, before a single line of code is written.

Methods

The authors present a three-stage workflow called SpecCC (Specification Consistency Checking):

  1. Translation & Semantic Reasoning: The system uses the Stanford NLP parser to break down "Structured English" into grammatical components. Unlike standard parsers, SpecCC uses an antonym dictionary to simplify logic. For instance, if a requirement mentions "on" and another mentions "off," the system recognizes they are opposites (on ≡ ¬off), preventing the creation of redundant variables and simplifying the resulting logic.
  2. Time Abstraction: LTL often uses a "Next" operator ($X$) to represent discrete time steps. If requirements involve long durations (e.g., 180 seconds), the resulting formulas become massive and slow down solvers. SpecCC uses a Greatest Common Divisor (GCD) approach and an optimization algorithm (handling "arrival errors" or jitter) to compress these time steps into a computationally manageable format.
  3. Realizability Checking: The translated formulas are fed into G4LTL, a synthesis engine. Instead of just checking if the formulas could be true, it checks if a controller can be synthesized that reacts to environment inputs while always satisfying the requirements. If the engine fails, it points to the specific conflicting requirements.

Datasets

The framework was evaluated on three distinct case studies:

  • CARA (Computer-Aided Resuscitation Algorithm): An infusion pump control system. This was the primary testbed, involving 70 requirements related to safety-critical medical operations.
  • TELEPROMISE: A set of functional specifications for generic web applications (shopping, reservations, etc.).
  • Rescue Robot: A scenario involving multiple robots navigating rooms to find injured people, used to test the system's ability to handle spatial and coordination constraints.

Key Insights and Ideas

  • Realizability > Satisfiability: The core "aha" moment is that a consistent specification isn't enough; it must be realizable. The paper highlights that many "consistent" requirements are actually impossible because they assume the system knows what the user will do before they do it.
  • Heuristic I/O Partitioning: One of the hardest parts of formalizing requirements is deciding what is an "input" (from the environment) and what is an "output" (from the system). SpecCC uses sentence structure heuristics (e.g., subjects in "if" clauses are usually inputs) to automate this, with a fallback loop for manual adjustment if the synthesis fails.
  • Semantic vs. Syntactic Parsing: By looking up antonyms, the tool moves beyond just mapping words to symbols. It understands the relationship between states, which significantly reduces the complexity of the formal model.

Key Results

The researchers successfully applied SpecCC to the CARA system, managing 30 complex formulas with 22 inputs and 28 outputs in roughly 34 seconds.

In the TELEPROMISE case study, the tool successfully identified inconsistencies that were caused by incorrect Input/Output variable classifications. Once the tool's heuristic partition was manually refined, it was able to prove the specifications were consistent. The results (summarized in Table I) show that for most medium-sized specifications, the tool provides a verdict in under 2 seconds, making it viable for iterative design.

Limitations and Future Work

  • Structured English: The tool does not support "free-form" English. Users must write requirements within a specific grammatical subset (e.g., "If [condition], then [action]").
  • Verb Semantics: While the tool handles adjectives and adverbs well via antonym dictionaries, it cannot yet reason about the semantic relationships between different verbs (actions).
  • Manual Refinement: The partitioning of input and output variables is still heuristic. If the tool guesses wrong, a human expert must intervene to correct the variable roles.

The authors aim to improve the maturity of the NLP component in future versions, potentially using machine learning to better capture the nuances of natural language without requiring a strict "Structured English" format.

Summary updated

Abstract

Early stages of system development involve outlining desired features such as functionality, availability, or usability. Specifications are derived from these features that concretize vague ideas presented in natural languages. The challenge for the validation of specifications arises from the syntax and semantic gap between different representations and the need of automatic tools. In this paper, we present a requirement-consistency maintenance framework to produce consistent representations. The first part is the automatic translation from natural languages describing functionalities to formal logic with an abstraction of time. It extends pure syntactic parsing by adding semantic reasoning and the support of partitioning input and output variables. The second part is the use of synthesis techniques to examine if the requirements are consistent in terms of realizability. When the process fails, the formulas that cause the inconsistency are reported to locate the problem.
BibTeX
@misc{yan2014formal,
  author = {Rongjie Yan and Chih‐Hong Cheng and Guangquan Zhang and Yesheng Chai},
  title = {{Formal Consistency Checking over Specifications in Natural Languages}},
  year = {2014},
  eprint = {1405.5003},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1405.5003},
}

Loading related content...

Figure