PRINS: scalable model inference for component-based system logs

Donghwan Shin, Domenico Bianculli, Lionel C. Briand

TL;DR

This paper introduces PRINS, a novel approach to inferring behavioral models of component-based systems from execution logs. PRINS tackles the scalability challenge of existing methods by employing a divide-and-conquer strategy, enabling faster and more efficient model inference for large-scale systems.

What Problem Does This Paper Address?

Software models are crucial for various engineering tasks like comprehension and testing, but they are often unavailable or quickly become outdated. Model inference techniques can extract these models from execution logs, but they struggle with the massive log sizes common in modern systems, leading to out-of-memory errors or impractical execution times. This paper addresses this scalability bottleneck, aiming to infer accurate system models from large component-based system logs without requiring additional system information.

Methods

PRINS employs a four-stage divide-and-conquer approach:

  • Projection: System logs are partitioned into component-specific logs.
  • Inference: Existing state-of-the-art model inference techniques (like MINT) are applied to these smaller component logs to infer individual component models. This stage can be parallelized.
  • Stitching: A novel algorithm combines these individual component models into a system-level model, crucially accounting for the flow of events between components as observed in the logs. This stage involves "slicing" component models and "appending" them based on log sequences.
  • Determinization: An optional stage converts the potentially non-deterministic system model into a deterministic one using a hybrid approach (HDu) that balances heuristic merging with powerset construction to avoid over-generalization and maintain efficiency.

Datasets

The authors evaluated PRINS using a benchmark composed of logs from:

  • LogHub project: Logs from 16 different systems, from which they selected 5 (Hadoop, HDFS, Linux, Spark, Zookeeper) that met specific criteria (component availability in logs, minimum log count).
  • Personal Computer (PC): Logs collected from a PC running desktop business applications, resulting in 4 additional systems (CoreSync, NGLClient, Oobelib, PDApp).

Log message templates were identified using tools like Drain and MoLFI, and then manually refined.

Key Insights and Ideas

  • Divide and Conquer for Scalability: The core idea is that while inferring a model for a massive system log is intractable, inferring models for smaller, component-specific logs is feasible. Stitching these component models intelligently is the key to building a system model.
  • Stitching is Crucial: Simply concatenating component models is insufficient. The "stitching" algorithm's ability to reconstruct the system's overall behavior by considering inter-component event flows is a significant contribution.
  • Hybrid Determinization Balances Accuracy and Efficiency: The proposed HDu algorithm for determinization is more efficient than standard powerset construction and avoids over-generalization, which can lead to inaccurate models.
  • Log Diversity as a Predictor: The Log-Component Diversity Score (LDS) can predict when logs might be insufficient for accurate model inference, allowing engineers to collect more data proactively.

Key Results

  • Scalability: PRINS significantly outperforms MINT in execution time, achieving an order of magnitude speedup for large logs. In some cases, PRINS could infer models where MINT failed due to out-of-memory errors. The divide-and-conquer approach was identified as the primary driver of this scalability improvement, rather than parallel inference.
  • Accuracy: PRINS generally achieves comparable accuracy to MINT. While PRINS sometimes exhibits slightly lower recall (accepting fewer positive logs), it often shows higher specificity (rejecting more negative logs). This trade-off is acceptable, especially when logs are inadequate.
  • Determinization Efficiency: The HDu determinization stage is very fast (under a minute) for most systems, significantly outperforming the standard powerset construction, which can take over an hour.
  • Model Size: PRINS-inferred models tend to be larger than those inferred by MINT (average 3.6x more states, 5.5x more transitions), but this is considered an acceptable trade-off for the significant gains in scalability and the potential for automated analysis.

Limitations and Future Work

  • Model Size: A drawback of PRINS is the increased size of the inferred models compared to MINT. However, the authors argue this is acceptable given the scalability benefits and the fact that MINT models are already large.
  • Tool Dependency: The evaluation used MINT as the underlying inference tool. Future work could explore integrating PRINS with other model inference techniques.
  • Log Adequacy: The paper highlights that when logs are inadequate for model inference (indicated by high LDS), accuracy can suffer for both PRINS and MINT. The LDS metric is proposed to address this.
  • Future Work: The authors plan to evaluate PRINS on more diverse real-world industrial applications, integrate it with other model inference techniques, and assess the effectiveness of the inferred models for downstream tasks like test case generation.

Summary updated

BibTeX
@article{shin2022prins,
  author = {Donghwan Shin and Domenico Bianculli and Lionel C. Briand},
  title = {{PRINS: scalable model inference for component-based system logs}},
  journal = {Empir. Softw. Eng.},
  year = {2022},
  doi = {10.1007/s10664-021-10111-4},
}
Figure