Abstract
We consider the problem of automating the verification of distributed control software relying on publish-subscribe middleware. In this scenario, the main challenge is that software correctness depends intrinsically on correct usage of middleware components, but structured models of such components might not be available for analysis, e.g., because they are too large and complex to be described precisely in a cost-effective way. To overcome this problem, we propose to identify abstract models of middleware as finite-state automata, and then to perform verification on the combined middleware and control software models. Both steps are carried out in a computer-assisted way using state-of-the-art techniques in automata-based identification and verification. Our main contribution is to show that the combination of identification and verification is feasible and useful when considering typical issues that arise in the implementation of distributed control software.
Introduction
Verifying the reliability of robot software is notoriously difficult because middleware like ROS or YARP (Yet Another Robot Platform) acts as a complex "black box." Modern robots rely on distributed control architectures where different modules—such as vision systems and motor controllers—communicate via publish-subscribe middleware. While this modularity simplifies development, it makes formal verification—the process of proving software will not fail—nearly impossible.
The core challenge is that the correctness of a robot's behavior depends intrinsically on how the middleware handles messages, including buffering, timing, and synchronization. Middleware libraries are often massive, exceeding 150,000 lines of code, making manual modeling impractical. If a developer misuses a middleware primitive—for instance, by assuming a message is buffered when it is not—the robot might deadlock or enter an unsafe state. This research proposes a workflow that uses active learning to reverse-engineer middleware components into formal models, which are then used with model-checking tools to automatically detect these critical failures.
Methodology: Identification and Verification
The proposed framework combines two powerful techniques: Automata-based Identification and Model Checking.
1. Identification (Active Learning)
Using a tool called AIDE (Automata IDentification Engine), the researchers treat the middleware as a black box. They employ the $L^+_M$ algorithm to "interrogate" the middleware with specific input patterns and observe the resulting outputs. This active learning process builds a "conjecture" of the middleware's behavior, eventually producing an Interface Automaton (IA)—a mathematical map of states and transitions.
2. Verification (Model Checking)
Once a formal model of the middleware is generated, it is combined with a model of the robot's control code. This integrated system is fed into SPIN, a state-of-the-art model checker. SPIN exhaustively explores every possible interaction between the control code and the middleware to verify requirements, such as ensuring the robot never stops moving unexpectedly due to a software hang.
Experimental Evaluation
The study focused on YARP, the standard middleware for the humanoid iCub robot. The researchers tested various configurations, including standard versus buffered ports and strict (FIFO queue) versus non-strict (overwriting) reading modes.
In a "Planner-Controller" case study involving multiple processes (P1, P2, and P3), the model checker successfully identified a deadlock that occurs when the middleware is configured to drop messages in non-strict mode. This demonstrates the framework's ability to catch subtle bugs that arise from the interaction between application logic and middleware configuration.
Key Insights and Results
- Efficiency and Scalability: The system successfully identified models for various YARP port configurations. For a buffer size of 6, the tool performed 531 experiments and generated a model in approximately 31 seconds. However, as buffer size increases, the number of required experiments grows more than proportionally, highlighting a trade-off between model precision and computational cost.
- Hidden Bug Discovery: During experiments, the authors discovered a real-world bug in YARP. They found that an "interrupt" command on a port failed to unblock the current write operation as expected, only affecting future ones. This undocumented behavior had gone unnoticed in practical applications, proving that reverse engineering is a powerful debugging tool even for middleware creators.
- The Reset Bottleneck: A significant technical finding was that 95% of the learning time was spent on resetting the system (clearing ports and threads) between tests rather than on the identification algorithm itself.
Conclusion and Future Work
While the current approach assumes deterministic middleware, future work will address non-determinism introduced by network delays and hardware interrupts. Additionally, while middleware modeling is now automated, the robot's control code still requires manual translation into the PROMELA language for SPIN. Automating this "code-to-model" step remains a primary goal for making formal verification accessible to the broader robotics community.
Summary updated