Componentwise Automata Learning for System Integration (Extended Version)

Hiroya Fujinami, Masaki Waga, Jie An, Kohei Suenaga, Nayuta Yanagisawa, Hiroki Iseri, Ichiro HasuoarXiv 2025 · DOI · arXiv

Abstract

Automata learning is a powerful technique for reverse-engineering black-box systems, yet it often struggles with the complexity of modern integrated systems. This paper introduces Contextual Componentwise Automata Learning (CCwL*), an algorithm specifically tailored for System Integration (SI) scenarios. Unlike traditional methods that learn components in isolation or as a monolithic whole, CCwL leverages Context Analysis (CA) to focus on behaviors relevant to the specific system configuration. By pruning redundant features of third-party components, CCwL achieves significantly smaller models and improved query efficiency.

Introduction

In the domain of System Integration (SI), engineers frequently build complex systems by combining third-party black-box components. While active automata learning (e.g., the L* algorithm) can generate surrogate models for these systems, learning them "monolithically" often becomes computationally intractable.

Existing compositional learning techniques typically target legacy systems where internal components are inaccessible. However, in SI, components are often accessible but "over-engineered," containing numerous features irrelevant to the final integrated system. This "redundancy trap" leads to inefficient learning processes that map unused states. CCwL* addresses this by learning only the necessary parts of each component within its operational context.

Methods

The authors formalize systems as Moore Machine Networks (MMN), where components operate in a fully synchronized, dense manner.

Figure 1: Example of a Moore Machine Network where the behavior of component M_c2 is constrained by the output of M_c1.

The CCwL* algorithm introduces two key innovations:

  1. Direct Component Access: Unlike legacy-focused algorithms, CCwL* queries components directly, which is significantly more efficient than system-level black-box queries.
  2. Context Analysis (CA): Before exploring a component's state space, the algorithm performs reachability analysis on the product of the current hypothesis models of all other components. This determines the "context"—the set of inputs a component can actually receive given its neighbors' behaviors. If a behavior is unreachable in the current configuration, it is pruned from the learning process.

To manage the computational cost of this analysis, the algorithm uses two tuning parameters: $\mathcal{E}$ (Abstraction) to group similar states and $\mathcal{R}$ (Reachability Bound) to limit the search depth.

CCwL* distinguishes itself from prior research by focusing on system integration rather than legacy system analysis.

Figure 2: Comparison of the current work with existing literature across various dimensions like application domain and target systems.

As shown in the comparison table above, while most existing works focus on system-level querying and legacy analysis, CCwL* utilizes both system- and component-level interfaces to handle structured, synchronized component interactions efficiently.

Key Results

The researchers evaluated CCwL* using random benchmarks and realistic scenarios like an MQTT-based IoT lighting system and binary counters. Key findings include:

  • Efficiency Gains: CCwL consistently outperformed monolithic learning (MnL), which frequently timed out on larger systems.
  • Model Pruning: In the MQTT_Lighting benchmark, CCwL learned a model with only 27 states, whereas a naive componentwise approach that ignored context required 39 states*.
  • Query Reduction: The algorithm significantly reduced the number of "resets" and "steps," the most expensive parts of hardware-in-the-loop (HILS) testing.
  • Flexibility: Experiments confirmed that finer-grained context analysis leads to smaller models, while coarser analysis is faster for the learner, allowing users to choose the best trade-off for their specific hardware constraints.

Limitations and Future Work

Despite its successes, CCwL faces challenges with alphabet explosion, where a high number of incoming edges to a component leads to an exponential growth in input combinations. Future work will explore symbolic automata* to represent transitions using logical predicates rather than explicit lists. Additionally, the authors are working on expanding the availability of standardized, large-scale real-world benchmarks for Moore Machine Networks in IoT and robotics applications.

Summary updated

Abstract

Compositional automata learning is attracting attention as an analysis technique for complex black-box systems. It exploits a target system's internal compositional structure to reduce complexity. In this paper, we identify system integration -- the process of building a new system as a composite of potentially third-party and black-box components -- as a new application domain of compositional automata learning. Accordingly, we propose a new problem setting, where the learner has direct access to black-box components. This is in contrast with the usual problem settings of compositional learning, where the target is a legacy black-box system and queries can only be made to the whole system (but not to components). We call our problem componentwise automata learning for distinction. We identify a challenge there called component redundancies: some parts of components may not contribute to system-level behaviors, and learning them incurs unnecessary effort. We introduce a contextual componentwise learning algorithm that systematically removes such redundancies. We experimentally evaluate our proposal and show its practical relevance.
BibTeX
@misc{fujinami2025componentwise,
  author = {Hiroya Fujinami and Masaki Waga and Jie An and Kohei Suenaga and Nayuta Yanagisawa and Hiroki Iseri and Ichiro Hasuo},
  title = {{Componentwise Automata Learning for System Integration (Extended Version)}},
  year = {2025},
  eprint = {2508.04458},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.04458},
}
Figure