Scalable Inference of System-level Models from Component Logs

Donghwan Shin, Salma Messaoudi, Domenico Bianculli, Annibale Panichella, Lionel C. Briand, Raimondas SasnauskasarXiv 2019 · arXiv

TL;DR

This paper introduces SCALER, a novel approach to automatically infer system-level behavioral models from component-level execution logs. SCALER tackles the scalability challenge of traditional model inference techniques by breaking down the problem into inferring individual component models and then intelligently merging them, achieving significant speedups and improved accuracy for large-scale systems.

What Problem Does This Paper Address?

In software engineering, behavioral models are crucial for understanding, testing, and verifying software. However, these models are often unavailable or quickly become outdated as implementations evolve. Model inference techniques aim to automatically generate these models from execution logs. While effective for smaller systems, existing methods struggle with the sheer volume of data generated by modern, component-based systems, especially when logs from multiple components need to be combined. Furthermore, inferring a system-level model that captures interactions between components is difficult, particularly when detailed information about communication channels between these components (especially third-party ones) is scarce. This paper addresses the need for a scalable and accurate method to infer system-level models from component logs when only high-level architectural dependencies and a list of communication event templates are known.

Methods

SCALER employs a "divide and conquer" strategy. The core idea is to first infer individual models for each component using a state-of-the-art tool (MINT in their implementation) on their respective, smaller logs. This circumvents the scalability issues of applying inference directly to the combined, massive system logs.

The process involves two main stages:

  1. Pre-processing Stage:
    • Inferring Component Models: For each component, MINT is used to infer a guarded Finite State Machine (gFSM) from its individual logs.
  2. Identifying Log Entries Dependencies: A heuristic is developed to identify how log entries from different components are related, based on architectural dependencies and communication event templates. This "leads-to" relationship is crucial for understanding inter-component interactions.
  3. Stitching Stage:
    • Grafting: For each execution log, a system-level gFSM is built by merging the individual component models. This process, called "grafting," takes into account the identified log entry dependencies. It involves "slicing" component models to represent specific execution paths and then "inserting" these sliced models into others to capture the flow of control and data between components.
  4. Stitching: The system-level gFSMs generated for each execution are then merged using a standard DFA union operation to produce the final system model.

Datasets

The authors evaluated SCALER using seven proprietary datasets from an industrial partner in the satellite domain. These datasets consist of component-level logs from a satellite ground control system. The datasets vary in size, ranging from 5K to 35K total log entries, and were derived from 120 system executions. The paper does not introduce a new benchmark but uses real-world industrial data.

Key Insights and Ideas

  • Decomposition is Key to Scalability: The core insight is that by breaking down the problem of inferring a large system model into inferring smaller component models, the scalability limitations of existing techniques can be overcome.
  • Log Entry Dependencies Bridge the Gap: Identifying the "leads-to" relationships between log entries from different components is critical for accurately stitching individual models into a coherent system-level model that reflects inter-component interactions.
  • "Grafting" and "Stitching" for System Integration: The novel algorithms for "grafting" (merging models for a single execution) and "stitching" (merging models across multiple executions) are central to SCALER's ability to build a comprehensive system model.
  • Trade-off Between Specificity and Recall: SCALER achieves significantly higher recall (finding more true behaviors) at the cost of a slight decrease in specificity (rejecting fewer false behaviors) compared to MINT when run on linearized system logs. This trade-off is often acceptable in practice for improved completeness and speed.

Key Results

  • Scalability: SCALER is significantly faster than MINT when processing large system logs. The speed-up ranges from 27x to 428x, with SCALER being considerably more efficient as log sizes increase. MINT even timed out on the largest dataset.
  • Accuracy:
    • Recall: SCALER achieves substantially higher recall (average improvement of 35.5 percentage points) compared to MINT, indicating more complete models.
  • Specificity: SCALER has slightly lower specificity (average difference of 1.67 percentage points) than MINT, meaning it might incorrectly accept a few more "negative" logs. However, the specificity remains high (always above 0.96 on average).
  • Model Size: SCALER-generated system-level gFSMs tend to have more states and transitions (4.6x and 7.0x more, respectively) than those generated by MINT, reflecting their greater completeness.

Limitations and Future Work

  • Limitations:
    • The accuracy of SCALER can be affected by the quality of inferred component models, potential over-generalization from parallel composition, and the determinization process.
  • The heuristic for identifying log entry dependencies can be imprecise, especially with coarse-grained timestamps or fast, out-of-order communications.
  • The paper notes that standard DFA minimization can significantly increase execution time without substantial model size reduction.
  • Future Work:
    • Refine heuristics for identifying log entry dependencies to handle imprecise timestamps and out-of-order messages.
  • Evaluate SCALER on more diverse datasets.
  • Integrate SCALER with other model inference techniques.
  • Assess the effectiveness of SCALER-inferred models in downstream software engineering tasks like test case generation.

Summary updated

BibTeX
@misc{shin2019scalable,
  author = {Donghwan Shin and Salma Messaoudi and Domenico Bianculli and Annibale Panichella and Lionel C. Briand and Raimondas Sasnauskas},
  title = {{Scalable Inference of System-level Models from Component Logs}},
  year = {2019},
  eprint = {1908.02329},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.02329},
}

Loading related content...

Figure