TL;DR
This paper introduces a novel inductive logic programming approach to automatically refine Modal Transition Systems (MTSs). By learning from positive and negative event traces, it generates new safety properties that strengthen the MTS, ensuring required behaviors are met and proscribed behaviors are avoided, thus supporting incremental software development.
What Problem Does This Paper Address?
Software systems are often specified partially, leading to Modal Transition Systems (MTSs) that model required, proscribed, and "maybe" events. Refining these MTSs to become more concrete (closer to a full implementation) is crucial but challenging. This paper tackles the problem of automating the process of "strong refinement" of MTSs, where "maybe" events are resolved into either required or proscribed events based on observed system behavior (event traces). The goal is to provide a formal, tool-supported method for this refinement, moving beyond theoretical definitions to practical computation.
Methods
The core of the approach lies in combining Event Calculus (EC) for formalizing system behavior and Inductive Logic Programming (ILP) for learning new rules.
- Event Calculus (EC): The paper uses an EC logic program to encode the initial MTS, its fluent definitions (representing system properties), and the provided event traces. EC is well-suited for reasoning about actions and time, allowing explicit representation of event occurrences and their impact on fluents. This EC program acts as the "background knowledge" for the ILP system.
- Inductive Logic Programming (ILP): An ILP system is employed to learn new safety properties. The system takes the EC encoding of system specifications and traces as input. The traces are translated into "examples" for the ILP learner, specifying which events must happen (positive traces) and which must not happen (negative traces) in the refined system. The ILP system then "abduces" rules (hypotheses) that, when added to the background knowledge, explain these examples. These learned rules are then translated back into FLTL (Future Linear Temporal Logic) safety properties.
- Strong Refinement: The learned properties are designed to ensure that the resulting refined MTS is a "strong refinement" of the original. This means all required and proscribed behaviors of the original MTS are preserved, and the new properties enforce the behaviors dictated by the positive and negative traces.
Datasets
The paper uses a case study involving the Philips Television Set Configuration protocol. This protocol describes the control of a signal path to avoid visual artifacts when changing tuner frequencies. The authors provide:
- Fluent Definitions: Tuples defining system properties like
Active_t1,Tuning_t1, etc., based on events. - Initial MTS: A representation of the system's partial specification.
- Positive and Negative Traces (Σ⁺, Σ⁻): Sets of event sequences representing desired (required) and undesired (proscribed) behaviors. These traces are derived from the Philips TV set configuration scenario.
Key Insights and Ideas
- Bridging Theory and Practice: The paper demonstrates how abstract notions of modal refinement can be computationally realized using ILP, providing a practical tool for engineers.
- Leveraging Event Traces: Event traces, often used for testing, are repurposed here as a source of knowledge for synthesizing system refinements, not just verifying existing ones.
- Non-monotonic Learning for Refinement: The use of non-monotonic ILP is crucial because it allows the system to learn rules that can override default assumptions (e.g., that an event is "maybe") based on specific negative evidence (proscribed traces).
- EC as a Unifying Formalism: Event Calculus proves to be a powerful and flexible formalism for encoding diverse aspects of system specifications and observed behaviors, making it a suitable foundation for ILP.
- Strong Refinement Computation: The approach directly computes the conditions for strong refinement, ensuring that the learned properties lead to a system that is demonstrably "more defined" than the original MTS.
Key Results
The paper presents a case study demonstrating the approach on the Philips TV set configuration.
- Learned Safety Properties: The ILP system successfully learned two FLTL safety properties:
G(start → X (t1_tune))(If the system starts, thent1_tunemust occur next).G((Tuning_t1 ∧ WaitingDropAck_t1) → X ¬(t1_tune))(If the system is tuning and waiting for a drop acknowledgment, thent1_tunemust not occur next).- Refined MTS: These learned properties were used to generate a refined MTS (Figure 2 in the paper) that is a strong refinement of the initial MTS (Figure 1). This refined MTS correctly enforces the required
t1_tunetransition and prevents the proscribedt1_tunetransitions in the specified contexts.
Limitations and Future Work
- Focus on Safety Properties: The current approach primarily handles safety properties of a specific form (
G (∧¬fi → X(¬)à)orG (∧¬fi → Xà)). Extending this to a wider class of safety properties and other temporal logic constructs (like liveness) is a key area for future work. - Alphabet Extension: The authors plan to explore how to handle scenarios where new descriptions might introduce new events, requiring an extension of the system's alphabet.
- Weak Refinement: The paper focuses on "strong refinement." Future work could investigate learning for "weak refinement" semantics, which might involve more flexibility in how "maybe" events are resolved.
- Non-deterministic MTSs: The authors aim to extend the approach to reason about and refine non-deterministic MTSs, leveraging the full power of the EC representation.
- Tool Support: While the paper describes a formal approach, further development of tool support for the entire process would enhance its practical applicability.
Summary updated