💻 computer science

Counterexample-Guided Interval Weakening

This paper introduces CEGIW, a counterexample-guided algorithm that automatically and optimally weakens the timing intervals in Metric Temporal Logic specifications to restore their validity for systems experiencing performance degradation while preserving their original logical structure.

Original authors: Ben M. Andrew, Louise A. Dennis, Michael Fisher, Marie Farrell

Published 2026-04-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ben M. Andrew, Louise A. Dennis, Michael Fisher, Marie Farrell

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: When Perfect Plans Meet Real-World Glitches

Imagine you are the manager of a busy hotel. You have a strict rule for your staff: "Every time a guest presses the elevator button, the elevator must arrive within 30 seconds." This is your "ideal specification."

In a perfect world with brand-new equipment, this rule holds true. But what happens if the elevator's motor starts to wear out? It gets slower. Suddenly, it takes 45 seconds to arrive. Your strict 30-second rule is now broken.

In the world of critical systems (like self-driving cars, medical ventilators, or drones), when a rule breaks, the usual reaction is to panic and say, "The system has failed!" But the authors of this paper ask a different question: "Can we adjust the rule just enough so it still works, without making it so loose that it becomes useless?"

Instead of saying, "The elevator is broken," they want to say, "Okay, the elevator is slower now. Let's officially change the rule to: 'The elevator must arrive within 60 seconds.' This is a weaker promise, but it's still a useful, safe promise."

The Problem: Finding the "Just Right" Rule

The challenge is knowing exactly how much to relax the rule.

If you change it to 61 seconds, maybe that's too loose?
If you change it to 31 seconds, maybe it's still impossible?
How do you know the best new number without guessing?

The authors created a tool called CEGIW (Counterexample-Guided Interval Weakening) to solve this automatically.

How the Tool Works: The "Detective" Analogy

Think of the CEGIW algorithm as a very persistent detective trying to fix a broken contract. Here is how it operates, step-by-step:

1. The Initial Check (The Crime Scene)
The detective looks at the system (the elevator) and the original rule ("Arrive in 30 seconds"). The detective runs a simulation and finds a specific scenario where the rule fails.

Example: "Ah, I see a case where the guest pressed the button, and the elevator took 45 seconds to arrive. The rule is broken."

2. The Adjustment (The Negotiation)
Instead of giving up, the detective looks at that specific failure and asks, "What is the smallest change to the rule that would make this specific failure go away?"

Since the elevator took 45 seconds, the detective suggests, "Okay, let's change the rule to 'Arrive within 45 seconds'."
Now, that specific failure is fixed.

3. The Loop (The Investigation Continues)
But wait! Just because the elevator arrived in 45 seconds in that one case doesn't mean it will always arrive in 45 seconds. Maybe next time it takes 50 seconds.

The detective runs the simulation again with the new "45-second rule."
If it fails again, the detective finds the new failure (e.g., "It took 52 seconds this time!") and adjusts the rule again (e.g., "Okay, let's try 52 seconds").

4. The Conclusion (The Final Verdict)
The detective keeps repeating this loop: Find a failure → Adjust the rule slightly → Check again.
Eventually, one of two things happens:

Success: The rule is adjusted to a point where the system always passes. The detective says, "The best we can guarantee is 60 seconds. We cannot go lower than that." This is the optimal (strongest possible) new rule.
Failure: The detective realizes that no matter how much they stretch the rule (even to "arrive within 1 hour"), the system still fails. In this case, the tool says, "No amount of relaxing the rule will save this system; the design is fundamentally broken."

Why This is Special

Most computer tools are like a strict judge: "You broke the rule. Guilty."
This tool is like a pragmatic engineer: "You broke the rule. Let's figure out exactly how much we can stretch the truth before it stops being true, so we can keep the system running safely."

Real-World Examples from the Paper

The authors tested this on real systems to see if it works:

The Robot Swarm: They had a robot that was supposed to return home within 3 seconds. The simulation showed the robot getting stuck in an infinite loop (walking in circles forever).
- Result: The tool realized no amount of time would fix a robot stuck in a loop. It flagged a design error. Once the engineers fixed the loop, the tool helped them find the exact new time limit (20 seconds) that the robot could actually meet.
The Drone: A drone had a rule to finish a control loop in 12 milliseconds. If the drone's battery got low or the signal got weak, it might take longer.
- Result: The tool calculated that if the signal was weak, the rule could be safely relaxed to 24 milliseconds. This tells engineers, "If your signal is bad, you can still fly safely, but you must accept a slower response time."
The Ventilator: A medical ventilator must stay on for 120 minutes after a power failure.
- Result: If the battery is degraded, the tool can tell you exactly how many minutes you can guarantee (e.g., 90 minutes) before the system fails. This is crucial for safety regulations.

The Bottom Line

The paper presents a method to automatically find the "Goldilocks" rule for failing systems. It doesn't just tell you a system is broken; it tells you exactly how much you need to lower your expectations to keep the system working safely. It preserves the logic of the original plan but adjusts the timing numbers to match reality.

1. Problem Statement

Systems operating in dynamic environments often experience performance degradation (e.g., hardware failures, resource constraints) that invalidates their original timing guarantees, even if their functional logic remains correct. These timing guarantees are typically specified using Metric Temporal Logic (MTL).

The Challenge: When a system degrades, an ideal MTL specification (e.g., "arrive within 30 seconds") may no longer hold. However, a logically weaker variant (e.g., "arrive within 60 seconds") might still be satisfied and useful.
The Gap: Existing methods for specification repair often focus on unrealizable requirements (finding any implementation) or use heuristic, non-deterministic approaches (like genetic algorithms) that do not guarantee the strongest possible weakening. There is a lack of formal, semantics-driven methods to automatically derive the optimal (strongest) weakened interval for a specific degraded system model.

2. Methodology: The CEGIW Algorithm

The authors propose CEGIW (Counterexample-Guided Interval Weakening), an iterative algorithm that automatically adjusts the time intervals in MTL specifications to make them hold for a given system model.

Core Concepts

Contexts: The algorithm treats the MTL formula as a "context" $C$ with a "hole" $[-]$ where the specific sub-formula containing the interval to be weakened resides. This allows the algorithm to preserve the logical structure of the original specification while only modifying interval bounds.
Weakening Order:
- For the Until ( $U$ ) operator, weakening corresponds to extending the right-bound of the interval (allowing more time).
- For the Release ( $R$ ) operator, weakening corresponds to contracting the right-bound of the interval (requiring less time).
- The paper proves that these modifications create a total order, allowing the algorithm to identify a unique "optimal" weakening.

Algorithm Workflow

The algorithm operates in two nested levels:

Iterative Loop (Top Level):
- A model checker (specifically nuXmv) checks if the current MTL property holds on the system model.
- If the property fails, the model checker produces a counterexample trace (specifically a "lasso trace," consisting of a finite prefix and a repeating suffix).
- The algorithm calls the Weaken function to adjust the interval based on this specific counterexample.
- The process repeats with the new, weakened property until the property holds on the model or no valid weakening exists.
Weakening on Counterexamples (Bottom Level):
- Lasso Coverage: Instead of iterating over infinite traces, the algorithm uses a "covering interval" to determine satisfaction over the infinite lasso trace using only finite computation.
- Recursive Traversal: The Weaken function recursively traverses the MTL context.
  - Base Cases: Directly calculates the minimal interval extension (for $U$ ) or contraction (for $R$ ) required to satisfy the specific trace.
  - Inductive Cases: Propagates the weakening requirements up the syntax tree. For example, if a sub-formula is the left operand of a $U$ operator, the algorithm must find an interval that satisfies the condition for all time steps until the right operand becomes true, selecting the weakest interval that covers all requirements.

3. Key Contributions

CEGIW Algorithm: A novel, iterative, counterexample-guided algorithm that automatically derives the strongest possible interval weakening for MTL specifications given a degraded system model.
Formal Guarantees: The authors provide rigorous proofs for:
- Correctness: If the algorithm returns an interval, the weakened property holds on the system.
- Optimality: The returned interval is the "strongest" possible weakening (i.e., no strictly stronger interval would satisfy the system).
Context Preservation: The method modifies only the numerical bounds of intervals, preserving the logical structure and semantics of the original specification, which is crucial for maintaining the intent of safety-critical requirements.
Empirical Validation: The approach was tested on real-world case studies using the FRET (Formal Requirements Elicitation Tool) framework.

4. Results and Evaluation

The authors evaluated CEGIW using two research questions:

RQ1: Diagnostic Capability (Foraging Robot Case Study):
- Applied to a robot swarm model, CEGIW first identified a design flaw (an infinite loop) where no weakening existed.
- After fixing the model, CEGIW successfully derived the optimal timing bounds: extending the "return home" time from 3 to 20 units and contracting the "stay away" time from 20 to 3 units.
- This demonstrates CEGIW's ability to both diagnose modeling errors and quantify system resilience.
RQ2: Applicability to Real-World Requirements:
- Analyzed 419 requirements from 8 real-world case studies (e.g., mechanical lung ventilators, autonomous drones, aircraft controllers).
- Findings: 124 out of 419 requirements (approx. 30%) were amenable to interval weakening.
- Interpretation: 116 required interval extension (e.g., allowing a control loop more time due to network latency), and 11 required contraction (e.g., a ventilator must stay on for at least a certain time, so the lower bound is tightened).
- The study confirms that interval weakening is a practical tool for safety-critical domains where degradation is expected.

5. Significance and Future Work

Significance: CEGIW bridges the gap between formal verification and system degradation. It moves beyond simple "pass/fail" verification to provide actionable, quantitative feedback on how much a system's performance can degrade before its guarantees fail. This is vital for designing resilient safety-critical systems.
Limitations & Future Work:
- Currently, the algorithm only modifies the right-hand bound of intervals. Future work aims to handle both left and right bounds, which introduces a partial order and complicates the definition of "optimality."
- Currently, only one interval is weakened at a time. Future work plans to incorporate multi-objective optimization (Pareto optimality) to weaken multiple intervals simultaneously.
- The scope is currently limited to interval modifications; future research may explore syntactic changes to the formula structure itself.

In summary, the paper presents a robust, mathematically grounded framework for automatically repairing timing specifications in degraded systems, offering engineers a precise way to understand and quantify system resilience.