Abstract
MedTiny is a component-based modeling language designed to facilitate the formal verification of complex software systems. By supporting arbitrary-depth hierarchies and a robust "port-and-link" mechanism, it allows developers to build reusable, encapsulated models that remain mathematically equivalent to standard Labeled Transition Systems (LTS). This paper presents the design, formal semantics, and implementation of MedTiny, demonstrating its effectiveness in modeling complex synchronization patterns and cyber-physical systems.
Introduction
As software systems grow in complexity, verifying their correctness becomes a monumental task. While component-based design helps manage this complexity in traditional programming, formal verification tools often lag behind. Many existing tools, such as Uppaal or PRISM, lack native support for hierarchical composition, forcing users to "flatten" their models. This leads to "code bloat," where the model size explodes, making it nearly impossible to maintain or reuse components.
Furthermore, predecessor languages like Mediator suffered from restrictive rules—such as forbidding "rings" in port connections—that prevented the modeling of basic parallel patterns like "ping-pong" programs. MedTiny was developed to address these expressiveness and soundness issues while providing a user-friendly syntax familiar to modern engineers.
Modeling Methodology
MedTiny is defined through two core building blocks: Functions, which are standard computational units guaranteed to terminate, and Automata, which are state machines defining behavior over time. Automata can contain other functions or sub-automata, enabling hierarchical nesting.
The core innovation of MedTiny is its Multi-Level Composition mechanism. Unlike many modeling languages that impose a two-level limit, MedTiny utilizes a "port-and-link" system supporting arbitrary depth. This system relies on two types of ports:
- Internal Ports: Facilitate direct communication between a parent component and its children.
- Pass-Thru Ports: Allow a sub-component's port to be exposed directly to the external environment.
The operational semantics of MedTiny use a post-order traversal method for instantiation, ensuring that leaf components are initialized before their parents, maintaining a rigorous mathematical "rulebook" for execution.
Key Insights and Formal Semantics
A primary goal of MedTiny is to treat encapsulation as a first-class citizen. By enforcing strict boundaries, the language ensures that internal state changes in one component do not unexpectedly affect another, making components truly reusable.
Crucially, the authors prove that any MedTiny model can be mapped to a Labeled Transition System (LTS). This Bisimilarity to LTS ensures that MedTiny models can be verified using existing, powerful model-checking engines. The language also avoids "semantic over-abstraction" by using time-tested programming patterns that are easier for engineers to reason about than the hidden port manipulations of previous iterations.
Bridging the Cyber-Physical Gap
MedTiny is particularly well-suited for modeling Cyber-Physical Systems (CPS). It allows for the modeling of sensors and actuators as data sources and sinks, enabling the deterministic logic of software (the Cyber System) to interact with the stochastic nature of the physical environment.
Evaluation and Results
The language's expressiveness was evaluated using classic modeling benchmarks, including the Dining Philosophers, Map-Reduce, Traffic Lights, and a Debounced LED Toggle (a CPS example).
Key results include:
- Formal Equivalence: Theorems 4.1 and 4.2 prove that MedTiny's hierarchical composition is mathematically equivalent to a flat LTS, confirming its broad expressiveness.
- Compiler Implementation: Two versions of the MedTiny compiler (Java and Python) have been developed to translate code into formats compatible with PRISM and SMTLib.
- Improved Expressiveness: MedTiny successfully handles complex synchronization patterns that were impossible in its predecessor, Mediator.
Conclusion and Future Work
While MedTiny provides a solid foundation for hierarchical formal verification, future work will focus on enhancing the compiler with automated model validation checks and "automated theory selection" for SMT solvers to optimize verification efficiency. Additionally, the team plans to integrate MedTiny with hybrid system verifiers to better handle systems involving both discrete logic and continuous physical processes.
Summary updated