∎ maxsummary-values.tex

11institutetext:  Donghwan Shin 22institutetext: Domenico Bianculli
33institutetext: Lionel Briand 44institutetext: University of Luxembourg
44email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>55institutetext: Lionel Briand 66institutetext: University of Ottawa

# PRINS: Scalable Model Inference for Component-based System Logs††thanks:
This work has received funding from the Luxembourg National Research Fund
(FNR) under grant agreement No C-PPP17/IS/11602677 and from the NSERC
Discovery and Canada Research Chair programmes. Donghwan Shin was also
partially supported by the Basic Science Research Program through the National
Research Foundation of Korea (NRF) funded by the Ministry of Education
(2019R1A6A3A03033444).

Donghwan Shin  Domenico Bianculli  Lionel Briand

(Received: date / Accepted: date)

###### Abstract

Behavioral software models play a key role in many software engineering tasks;
unfortunately, these models either are not available during software
development or, if available, quickly become outdated as implementations
evolve. Model inference techniques have been proposed as a viable solution to
extract finite state models from execution logs. However, existing techniques
do not scale well when processing very large logs that can be commonly found
in practice.

In this paper, we address the scalability problem of inferring the model of a
component-based system from large system logs, without requiring any extra
information. Our model inference technique, called _PRINS_ , follows a divide-
and-conquer approach. The idea is to first infer a model of each system
component from the corresponding logs; then, the individual component models
are merged together taking into account the flow of events across components,
as reflected in the logs. We evaluated _PRINS_ in terms of scalability and
accuracy, using nine datasets composed of logs extracted from publicly
available benchmarks and a personal computer running desktop business
applications. The results show that _PRINS_ can process large logs much faster
than a publicly available and well-known state-of-the-art tool, without
significantly compromising the accuracy of inferred models.

††journal: Empirical Software Engineering

##  1 Introduction

Behavior models of software system components play a key role in many software
engineering tasks, such as program comprehension Cook and Wolf (1998), test
case generation Fraser and Walkinshaw (2012), and model checking Clarke Jr et
al. (2018). Unfortunately, such models are either scarce during software
development or, if available, quickly become outdated as the corresponding
implementations evolve, because of the time and cost involved in generating
and maintaining them Walkinshaw et al. (2010).

One possible way to overcome the lack of software models is to use _model
inference_ techniques, which extract models—typically in the form of Finite
State Machine (FSM)—from execution logs. Although the problem of inferring a
minimal FSM is NP-complete Gold (1967), there have been several proposals of
polynomial-time approximation algorithms to infer FSMs Biermann and Feldman
(1972); Beschastnikh et al. (2011) or richer variants, such as gFSM (guarded
FSM) Walkinshaw et al. (2016); Mariani et al. (2017) and gFSM extended with
transition probabilities Emam and Miller (2018), to obtain relatively faithful
models.

Though the aforementioned model inference techniques are fast and accurate
enough for relatively small programs, all of them suffer from scalability
issues, due to the intrinsic computational complexity of the problem. This
leads to out-of-memory errors or extremely long, impractical execution time
when processing very large logs Wang et al. (2015) that can be commonly found
in practice. A recent proposal Luo et al. (2017) addresses scalability using a
distributed FSM inference approach based on MapReduce. However, this approach
requires to encode the data to be exchanged between mappers and reducers in
the form of key-value pairs. Such encoding is application-specific; hence, it
cannot be used in contexts—like the one in which this work has been
performed—in which the system is treated as a black-box (i.e., the source code
is not available), with limited information about the data recorded in the
system logs.

In this paper, we address the scalability problem of inferring a system model
from the logs recorded during the execution (possibly multiple executions) of
a system composed of multiple “components” (hereafter called _component-based
system_), without requiring any extra information other than the logs. In this
paper, we use the term “component” in a broad sense: the large majority of
modern software systems are composed of different types of “components”, such
as modules, classes, and services; in all cases, the resulting system
decomposition provides a high degree of modularity and separation of concerns.
Our goal is to efficiently infer a system model that captures not only the
components’ behaviors but also the flow of events across the components as
reflected in the logs.

Our approach, called _PRINS_ , follows a _divide-and-conquer_ strategy: we
first infer a model of each component from the corresponding logs using a
state-of-the-art model inference technique, and then we “stitch” (i.e., we do
a peculiar type of merge) the individual component models into a system-level
model by taking into account the interactions among the components, _as
reflected in the logs_. The rationale behind this idea is that, though
existing model inference techniques cannot deal with the size of all combined
component logs, they can still be used to infer the models of individual
components, since their logs tend to be sufficiently small. In other words,
_PRINS_ alleviates the scalability issues of existing model inference
techniques by limiting their application to the smaller scope defined by
component-level logs.

We implemented _PRINS_ in a prototype tool, which internally uses MINT
Walkinshaw et al. (2016), the only publicly available state-of-the-art
technique for inferring gFSMs, to infer the individual component models. We
evaluate the scalability (in terms of execution time) and the accuracy (in
terms of recall and specificity) of _PRINS_ in comparison with MINT (to
directly infer system models from system logs), on 9 datasets composed of logs
extracted from publicly available benchmarks He et al. (2020) and a personal
computer (PC) running desktop business applications on a daily basis. The
results show that _PRINS_ is significantly more scalable than MINT and can
even enable model inference when MINT leads to out-of-memory failures. It also
achieves higher specificity than MINT (with a difference ranging between
$\DTLfetch{max}{data}{all}{spec.min}\text{\,}\mathrm{\textup{pp}}$ and
$+\DTLfetch{max}{data}{all}{spec.max}\text{\,}\mathrm{\textup{pp}}$, with
$\mathrm{\textup{pp}}$=percentage points) while achieving lower recall than
MINT (with a difference ranging between
$\DTLfetch{max}{data}{all}{recall.min}\text{\,}\mathrm{\textup{pp}}$ and
$+\DTLfetch{max}{data}{all}{recall.max}\text{\,}\mathrm{\textup{pp}}$).
Through a detailed analysis, we determined that a lower recall for _PRINS_
only happens when logs are inadequate to infer accurate models, using any of
the techniques. We also propose a simple and practical metric for engineers to
easily predict (and thus improve) such cases before running model inference.
With adequate logs, _PRINS_ therefore provides a comparable or even better
accuracy.

To summarize, the main contributions of this paper are:

  * •

the _PRINS_ approach for taming the scalability problem of inferring the model
of a component-based system from the individual component-level logs, when no
additional information is available;

  * •

the novel _stitching_ algorithm that “combine” individual component models
together taking into account the flow of events across components as recorded
in logs;

  * •

a publicly available implementation of _PRINS_ (see Section5.8);

  * •

the empirical evaluation, in terms of scalability and accuracy, of _PRINS_ and
its comparison with the state-of-the-art model inference tool.

The rest of the paper is organized as follows. Section 2 gives the basic
definitions of logs and models that will be used throughout the paper. Section
3 illustrates the motivating example. Section 4 describes the different stages
of _PRINS_. Section 5 reports on the evaluation of _PRINS_. Section 6
discusses related work. Section 7 concludes the paper and provides directions
for future work.

##  2 Background

This section provides the basic definitions for the main concepts that will be
used throughout the paper.

###  2.1 Logs

A _log_ is a sequence of log entries; a _log entry_ contains a timestamp
(recording the time at which the logged event occurred), a component
(representing the name of the component where the event occurred), and a log
message (with run-time information related to the logged event). A log message
is typically a block of free-form text that can be further decomposed Zhu et
al. (2019); He et al. (2017); Messaoudi et al. (2018); El-Masri et al. (2020)
into an event template, characterizing the event type, and the parameter
values of the event, which are determined at run time. For example, given the
log entry “15:37:56 - Master - end (status=ok)”, we can see that the event end
of the component Master occurred at timestamp 15:37:56 with the value ok for
parameter status.

More formally, let $C$ be the set of all components of a system, $\mathit{ET}$
be the set of all events that can occur in the system, $V$ be the set of all
mappings from event parameters to their concrete values, for all events
$\mathit{et}\in\mathit{ET}$, and $L$ be the set of all logs retrieved for the
system; a log $l\in L$ is a sequence of log entries $\langle
e_{1},e_{2},\dots,e_{n}\rangle$, with
$e_{i}=(\mathit{ts}_{x},\mathit{cm}_{i},\mathit{et}_{i},v_{i})$,
$\mathit{ts}_{i}\in\mathbb{N}$, $\mathit{cm}_{i}\in C$,
$\mathit{et}_{i}\in\mathit{ET}$, and $v_{i}$ is a vector of parameter values
over $V$. To denote individual log entries, we use the notation $e_{i,j}$ for
the $i$-th log entry in the $j$-th execution log.

###  2.2 Models

In this paper, we represent the models inferred for a system for a component
as guarded Finite State Machines (gFSMs). Informally, a gFSM is an “extended”
finite state machine whose transitions are triggered by the occurrence of an
event and are guarded by a function that evaluates the values of the event
parameters.

More formally, let $\mathit{ET}$ and $V$ be defined as above. A gFSM is a
tuple $m=(S,\mathit{ET},G,\delta,s_{0},F)$, where $S$ is a finite set of
states, $G$ is a finite set of guard functions of the form $g\colon
V\to\\{\textit{True},\textit{False}\\}$, $\delta$ is the transition relation
$\delta\subseteq S\times\mathit{ET}\times G\times S$, $s_{0}\in S$ is the
initial state, and $F\subseteq S$ is the set of final states. A gFSM $m$ makes
a guarded transition from a (source) state $s\in S$ to a (target) state
$s^{\prime}\in S$ when reading an input log entry
$e=(\mathit{ts},\mathit{cm},\mathit{et},v)$, written as
$s\xrightarrow{e}s^{\prime}$, if $(s,\mathit{et},g,s^{\prime})\in\delta$ and
$g(v)=\textit{True}$. We say that a guarded transition is _deterministic_ if
there is at most one target state for the same source state and the same log
entry. Otherwise, it is _non-deterministic_. Based on this, we say that a gFSM
is deterministic if all of its guarded transitions are deterministic;
otherwise, the gFSM is non-deterministic. We say that a gFSM $m$ _accepts_ a
log $l=\langle e_{1},\dots,e_{n}\rangle$ if there exists a sequence of states
$\langle\gamma_{0},\dots,\gamma_{n}\rangle$ such that  (1) $\gamma_{i}\in
S$for $i=0,\dots,n$,  (2) $\gamma_{0}=s_{0}$,  (3)
$\gamma_{i-1}\xrightarrow{e_{i}}\gamma_{i}$for $i=1,\dots,n$, and  (4)
$\gamma_{n}\in F$.

##  3 Motivating Example

This section presents a simple example to motivate and demonstrate our work.

Let us consider an imaginary system composed of two components, Master and
Job; Figure 1 depicts the set of logs $L_{\texttt{S}}=\\{l_{1},l_{2}\\}$
recorded during the executions of the system. Entries in the logs are denoted
using the notation introduced in Section 2.1; for instance, log entry
$e_{8,1}$ corresponds to the tuple
$(\cdot,\texttt{Master},\textit{end},[\textit{ok}])$, where the event is “end”
and the value for its first (and only) parameter is “ok”. Notice that in
Figure 1 we use a short form (as in “end (ok)”) to indicate both an event and
its parameter value; also, we omit timestamps in the running example logs as
they are not used in our approach.

A software engineer is tasked with building a finite-state model of the system
that accurately captures the behavior observed in the logs. However, the
engineer cannot rely on the system source code since it is not available. This
is the case, for example, where the system is mainly composed of
heterogeneous, 3rd-party components for which neither the source code nor the
documentation are available Aghajani et al. (2019); Palmer and McAddis (2019);
Rios et al. (2020). The only information about the system to which engineers
have access is represented by the execution logs $L_{\texttt{S}}$. To perform
this task, the engineer uses a tool implementing one of the state-of-the-art
_model inference techniques_ Walkinshaw et al. (2016); Mariani et al. (2017);
Emam and Miller (2018) proposed in the literature; the tool takes as input the
logs $L_{\texttt{S}}$ and returns the system model $m_{\texttt{S}}$ shown in
Figure LABEL:sub@fig:system. Intuitively, we can see that $m_{\texttt{S}}$
properly reflects the flow of events recorded in $L_{\texttt{S}}$. However,
when the engineer tries to execute the model inference tool on much larger
logs of the same system, she observes that the tool does not terminate within
a practical time limit (e.g., one day). Indeed, due to the intrinsic
complexity of the model inference problem Gold (1967), the time complexity of
state-of-the-art model inference algorithms is polynomial Lang et al. (1998);
Emam and Miller (2018) in the size of the input logs.

First execution log $l_{1}$ |  Second execution log $l_{2}$
---|---
ID | Component | Event | ID | Component | Event
$e_{1,1}$ | Master | start | $e_{1,2}$ | Master | start
$e_{2,1}$ | Job | init | $e_{2,2}$ | Job | init
$e_{3,1}$ | Master | working | $e_{3,2}$ | Master | working
$e_{4,1}$ | Job | try | $e_{4,2}$ | Job | try
$e_{5,1}$ | Job | pass | $e_{5,2}$ | Job | wait
$e_{6,1}$ | Job | try | $e_{6,2}$ | Job | wait
$e_{7,1}$ | Job | pass | $e_{7,2}$ | Job | fail
$e_{8,1}$ | Master | end (ok) | $e_{8,2}$ | Master | end (err)
Figure 1: Running example logs $L_{\texttt{S}}=\\{l_{1},l_{2}\\}$, inspired by
Hadoop logs He et al. (2020)

(a) $m_{\texttt{S}}$ (b) $m_{\texttt{M}}$ (c) $m_{\texttt{J}}$

Figure 2: Models corresponding to the running example logs ($m_{\texttt{S}}$:
system model, $m_{\texttt{M}}$: model for component Master, $m_{\texttt{J}}$:
model for component Job)

To address this problem, the engineer decides to use our new approach, _PRINS_
: it takes as input the logs $L_{\texttt{S}}$ in Figure 1 and returns the
_same_ system model $m_{\texttt{S}}$ shown in Figure LABEL:sub@fig:system; the
main difference with the tool used in the previous attempts is that _PRINS_
takes considerably less time to yield a system model.

The main idea behind _PRINS_ is to tackle the intrinsic complexity of model
inference by means of a _divide-and-conquer_ approach: _PRINS_ uses existing
model inference techniques to infer a model, not for the whole system but _for
each component_. Figure LABEL:sub@fig:master and Figure LABEL:sub@fig:job show
the component models $m_{\texttt{M}}$ and $m_{\texttt{J}}$ for the Master and
Job components, respectively. Component-level model inference is one of the
main contributors to the significant reduction of the execution time achieved
by _PRINS_. Furthermore, component-level model inference can be easily
parallelized.

However, before yielding a system model, _PRINS_ needs to properly “combine”
the individual component models. In our running example, this means building
the $m_{\texttt{S}}$ model shown in Figure LABEL:sub@fig:system by “combining”
the component models in $M_{C}=\\{m_{\texttt{M}},m_{\texttt{J}}\\}$ and shown
in Figure LABEL:sub@fig:master and Figure LABEL:sub@fig:job. This is a
challenging problem: we cannot simply concatenate or append the two component
models together, because the result would not conform to the flow of events
across the components recorded in the logs. In our running example logs, it is
recorded that the event _start_ of Master is immediately followed by the event
_init_ of Job. Such a flow of events recorded in the logs should be
represented in the final system model produced by _PRINS_. To efficiently and
effectively solve this problem, we propose a novel algorithm for _stitching_
component models in the context of model inference.

##  4 Scalable Model Inference

Our technique for scalable model inference follows a _divide-and-conquer_
approach. The main idea is to first _infer_ a model of each system component
from the corresponding logs that are generated by the _projection_ of system
logs on the components; then, the individual component models are _stitched_
together taking into account the flows of the events across the components,
_as reflected in the logs_. We call this approach _PRINS_ (_PR_ ojection-_IN_
ference-_S_ titching). The rationale behind _PRINS_ is that, though existing
(log-based) model inference techniques cannot deal with the size of system
logs, they can still be used to accurately infer the models of individual
components, since their logs are sufficiently small for the existing model
inference techniques to work. As anticipated in Section 3, the challenge is
then how to “stitch” together the models of the individual components to build
a system model that reflects not only the components’ behaviors but also the
flow of events across the components, while preserving the accuracy of the
component models. Tackling this challenge is our main contribution, as
detailed in Section 4.3.

Figure 3: Overview of _PRINS_

Figure 3 outlines the workflow of _PRINS_. It takes as input the logs of the
system under analysis, possibly coming from multiple executions; it returns a
system model in the form of a gFSM. _PRINS_ is composed of four main stages:
_projection_ , _inference_ , _stitching_ , and _determinization_. The
projection stage produces a set of logs for each component from the input
system logs. The component logs are then used to infer individual component
models in the inference stage. The stitching stage combines the component
models into a non-deterministic system model. Last, the determinization stage
transforms the non-deterministic model into a deterministic model that is the
output of _PRINS_. The four stages are described in detail in the following
subsections.

We remark that _PRINS_ does not require any extra information (e.g., source
code and documentation) other than logs. Furthermore, we do not restrict logs
to be produced by one thread/process: as one can see in the replication
package for our evaluation (see Section 5.8), individual logs for many of our
subject systems are already produced by multiple threads/processes
(distinguished by tid/pid). Our only assumption is that log entries contain
the name of the “component” that generated them. This assumption is realistic
since this is common in practice, as shown in real logs He et al. (2020).
Also, as indicated in Section 1, we use the term “component” in a broad sense
(e.g., modules, classes) to represent an architectural “part” of a system.
Therefore, _PRINS_ is applicable to any software system composed of multiple
components as long as their behavior is recorded in logs.

###  4.1 Projection

This stage generates a set of component logs—which will be used to infer a
model for each component—from system logs. For instance, for our running
example logs $L_{\texttt{S}}=\\{l_{1},l_{2}\\}$ shown in Figure 1, we want to
generate the set of logs for the Master component $L_{\texttt{M}}=$
$\\{\langle e_{1,1},e_{3,1},e_{8,1}\rangle$, $\langle
e_{1,2},e_{3,2},e_{8,2}\rangle\\}$, and the set of logs for the Job component
$L_{\texttt{J}}=\\{\langle
e_{2,1},e_{4,1},e_{5,1},e_{6,1},e_{7,1}\rangle,\langle
e_{2,2},e_{4,2},e_{5,2},e_{6,2},e_{7,2}\rangle\\}$. To achieve this, we define
the _projection_ operation as follows. Let $L$ be a set of logs of a system
and $C$ be a set of components of the system; the projection of $L$ for a
component $c\in C$, denoted with $L|c$, is the set of logs obtained from $L$
by removing all occurrences of log entries of all $c^{\prime}\in C$ where
$c^{\prime}\neq c$. For the running example, we have
$L_{\texttt{S}}|\texttt{Master}=L_{\texttt{M}}$ and
$L_{\texttt{S}}|\texttt{Job}=L_{\texttt{J}}$.

###  4.2 Inference

This stage infers individual component models from the sets of component logs
generated from the projection stage. This is straightforward because inferring
a (component) model from a set of logs can be achieved using an off-the-shelf
model inference technique. We remark that _PRINS_ does not depend on any
particular model inference technique, as long as it yields a deterministic FSM
(or a deterministic gFSM111A deterministic gFSM
$m=(S,\mathit{ET},G,\delta,s_{0},F)$ with $\delta:S\times\mathit{ET}\times
G\to S$ can be easily converted into a deterministic FSM
$m^{\prime}=(S,\Sigma,\delta^{\prime},s_{0},F)$ with
$\delta^{\prime}:S\times\Sigma\to S$ where $\Sigma=\mathit{ET}\times G$.) as a
resulting model. Also, _PRINS_ can infer multiple component models in parallel
because the inference processes of the individual component models are
independent from each other. For the running example, using an off-the-shelf
model inference tool like MINT Walkinshaw (2018) on the logs in
$L_{\texttt{M}}$ and $L_{\texttt{J}}$, we obtain models $m_{\texttt{M}}$ (see
Figure LABEL:sub@fig:master) and $m_{\texttt{J}}$ (see Figure
LABEL:sub@fig:job), respectively.

We want to note that the parallelization of component model inference is just
a byproduct of using the divide-and-conquer approach enabled by the central
component of _PRINS_ : stitching (Section 4.3).

###  4.3 Stitching

Individual component models generated from the inference stage are used in
this _stitching_ stage, which is at the core of _PRINS_. In this stage, we
build a system model that captures not only the components’ behaviors inferred
from the logs but also the flow of events across components as reflected in
the logs. For the running example, this means building a model that is as
“similar” as possible to $m_{\texttt{S}}$, using models $m_{\texttt{M}}$ and
$m_{\texttt{J}}$ as well as the input logs $L_{\texttt{S}}$ reflecting the
flow of events.

The idea of stitching comes from two important observations on the system and
component models:

  1. (1)

A system model is the composition of _partial models_ of the individual
components; this means that _partial behaviors_ of components are
_interleaved_ in a system model.

  2. (2)

The component partial models (included within a system model) are combined
together (i.e., appended) _according to the flow of events recorded in logs_ ,
since the system model must be able to accept the logs that were used to infer
it.

For example, in the models shown in Figure 2, we can see that the subgraph of
$m_{\texttt{S}}$, enclosed with a red solid line, contains two partial models:
one, called $m_{\texttt{M}}^{p}$ and enclosed with a blue dashed line,
extracted from $m_{\texttt{M}}$ (including the states $s_{8}$ and
$s_{9}$—mapped to $s_{0}$ and $s_{1}$ in $m_{\texttt{S}}$—and the
corresponding transition labeled with start) and the other, called
$m_{\texttt{J}}^{p}$ and enclosed with a green dashed line, extracted from
$m_{\texttt{J}}$ (including the states $s_{13}$ and $s_{14}$—mapped to $s_{1}$
and $s_{2}$ in $m_{\texttt{S}}$—and the corresponding transition labeled with
init). Notice that the partial models $m_{\texttt{M}}^{p}$ and
$m_{\texttt{J}}^{p}$ correspond to the partial (behaviors recorded in the)
logs $\langle e_{1,1}\rangle$ and $\langle e_{2,1}\rangle$, respectively, that
are determined by the interleaving of components in the system log $l_{1}$
shown in Figure 1. Furthermore, in $m_{\texttt{S}}$, $m_{\texttt{J}}^{p}$ is
appended to $m_{\texttt{M}}^{p}$, reflecting the fact that event start (from
component Master) is immediately followed by init (from component Job) in the
input logs.

Based on these observations, we propose a novel stitching technique that first
“ _slices_ ” individual component models into partial models according to the
component interleavings shown in logs; then it “ _appends_ ” partial models
according to the flow of the events recorded in logs. However, the behaviors
of components recorded in logs can be different from execution to execution
(for instance, see the difference in terms of recorded events between $l_{1}$
and $l_{2}$ in our running example). To address this, we first build an
intermediate, system-level model _for each execution_ (i.e., for each log) and
then merge these models together at the end.

The Stitch algorithm (whose pseudocode is shown in Algorithm 1) takes as input
a set of logs $L_{\mathit{sys}}$ and a set of component models $M_{C}$; it
returns a system model $m_{\mathit{sys}}$ (built from the elements in $M_{C}$)
that accepts $L_{\mathit{sys}}$.

1

Input : Set of System Logs (Structured) $L_{\mathit{sys}}$

Set of Component Models $M_{C}$

Output : System Model $m_{\mathit{sys}}$

2

3Set of Models $A\leftarrow\emptyset$

4 foreach  _Log $l_{\mathit{sys}}\in L_{\mathit{sys}}$_ do

5 Model $m_{a}\leftarrow\mathit{emptyModel}$

6 $\mathit{initializeSliceStartStates}(M_{C})$

7 List of Logs $P\leftarrow\textit{{Partition}}(l_{\mathit{sys}})$

8 foreach  _Log $l_{c}\in P$_ do

9 Model $m_{c}\leftarrow\mathit{getCorrespondingModel}(c,M_{C})$

10 Model $m_{\mathit{sl}}\leftarrow\textit{{Slice}}(m_{c},l_{c})$

11 $m_{a}\leftarrow\textit{{Append}}(m_{a},m_{\mathit{sl}})$

12

13 $A.\mathit{add}(m_{a})$

14

15 Model $m_{\mathit{sys}}\leftarrow\textit{{Union}}(A)$

16 return $m_{\mathit{sys}}$

17

Algorithm 1 Stitch

The algorithm builds a system-level model $m_{a}$ for each system log
$l_{\mathit{sys}}\in L_{\mathit{sys}}$ (lines 1–1). To build $m_{a}$ for a
given $l_{\mathit{sys}}$, the algorithm first initializes $m_{a}$ as an empty
model (line 1) and initializes the start states of all components models in
$M_{C}$ to their initial states (line 1). The algorithm then partitions
$l_{\mathit{sys}}$ into a list of logs $P$, each one corresponding to log
entries of one component, according to the component interleavings shown in
$l_{\mathit{sys}}$ (using algorithm Partition at line 1, described in detail
in Section 4.3.1). For each log $l_{c}\in P$ (lines 1–1), the algorithm
retrieves the component model $m_{c}\in M_{C}$ of the component $c$ that
produced $l_{c}$, slices it (using algorithm Slice at line 1, described in
detail in Section 4.3.2) into a partial model $m_{\mathit{sl}}$ that accepts
_only_ log $l_{c}$, and then appends $m_{\mathit{sl}}$ to $m_{a}$ (using
algorithm Append at line 1, described in detail in Section 4.3.3). During the
iteration over the system logs in $L_{\mathit{sys}}$, the resulting system-
level models $m_{a}$ are collected in the set $A$. Last, the models in $A$ are
combined into a single model $m_{\mathit{sys}}$ (using algorithm Union at line
1, described in detail in Section 4.3.4). The algorithm ends by returning
$m_{\mathit{sys}}$ (line 1), inferred from all logs in $L_{\mathit{sys}}$.

Before illustrating an example for Stitch, let us first present the details of
the auxiliary algorithms Partition, Slice, Append, and Union.

####  4.3.1 Partition

This algorithm takes as input a system log $l$ (i.e., a sequence of log
entries from various components); it partitions $l$ into a sequence of logs
$P$, where each log $l_{c}\in P$ is the longest uninterrupted sequence of log
entries produced by the same component, and returns $P$. By doing this, we can
divide a system log into component-level logs, each of which represents the
longest uninterrupted partial behavior for a component, while preserving the
flow of events across components as recorded in the system log.

For instance, when the function takes as input the running example log
$l_{1}$, it returns $P=\langle l_{c,1},l_{c,2},\dots,l_{c,5}\rangle$ where
$l_{c,1}=\langle e_{1,1}\rangle$, $l_{c,2}=\langle e_{2,1}\rangle$,
$l_{c,3}=\langle e_{3,1}\rangle$, $l_{c,4}=\langle
e_{4,1},e_{5,1},e_{6,1},e_{7,1}\rangle$, and $l_{c,5}=\langle e_{8,1}\rangle$.

####  4.3.2 Slice

This algorithm (whose pseudocode is shown in Algorithm 2) takes as input a
component model $m_{c}$ and a component log $l_{c}$; it returns a new model
$m_{\mathit{sl}}$, which is the sliced version of $m_{c}$ and accepts only
$l_{c}$.

1

Input : Component Model $m_{c}$

Component Log $l_{c}=\langle e_{1},e_{2},\dots\rangle$

Output : Component Model $m_{\mathit{sl}}$

2

3Model $m_{\mathit{sl}}\leftarrow\texttt{emptyModel}$

4 State $s\leftarrow\mathit{getSliceStartState}(m_{c})$

5 foreach  _Log Entry $e\in l_{c}$_ do

6 Guarded Transition $\mathit{gt}\leftarrow\mathit{getGT}(m_{c},s,e)$

7 $m_{\mathit{sl}}\leftarrow\mathit{addGTAndStates}(m_{\mathit{sl}},gt)$

8 $s\leftarrow\mathit{getTargetState}(\mathit{gt})$

9

10 $\mathit{updateSliceStartState}(m_{c},s)$

11 return $m_{\mathit{sl}}$

Algorithm 2 Slice

First, the algorithm retrieves the state of $m_{c}$ that will become the
initial state $s$ of the sliced model $m_{\mathit{sl}}$ (line 2). Upon the
first invocation of Slice for a certain model $m_{c}$, $s$ will be the initial
state of $m_{c}$; for the subsequent invocations, $s$ will be the last state
visited in $m_{c}$ when running the previous slice operations. Note that there
is always only one last visited state because $m_{c}$ is deterministic, as
described in Section 4.2. Starting from $s$, the algorithm performs a run of
$m_{c}$ as if it were to accept $l_{c}$ by iteratively reading each log entry
$e\in l_{c}$: the traversed states and guarded transitions of $m_{c}$ are
added into $m_{\mathit{sl}}$ (lines 2–2). After the end of the iteration, the
algorithm records the last state $s$ visited in $m_{c}$ (line 2), which is the
(only one) final state of $m_{\mathit{sl}}$ and will be used as the initial
state of the next slice on $m_{c}$. The algorithm ends by returning
$m_{\mathit{sl}}$.

For example, let us consider the case where Slice is called with parameters
$m_{c}=m_{\texttt{M}}$ and $l_{c}=\langle e_{1,1}\rangle$, and the slice start
state returned by getSliceStartState for $m_{\texttt{M}}$ is the initial state
$s_{8}$. Starting from $s=s_{8}$, a run of $m_{\texttt{M}}$ is performed:
reading log entry $e_{1,1}$ results in making the guarded transition to
$s_{1}$ in $m_{\texttt{M}}$. This results in $m_{\mathit{sl}}$ to include the
guarded transition from $s_{8}$ to $s_{9}$ with label start as well as the
states $s_{8}$ and $s_{9}$; the call to function getTargetState updates $s$ to
$s_{9}$. Since there is no more log entry in $l_{c}$, $s_{9}$ is the final
state of $m_{\mathit{sl}}$ and is the slice start state for the next call to
Slice for $m_{\texttt{M}}$. The resulting $m_{\mathit{sl}}$ is
$\mathit{slice}_{1}$ shown in Figure 4.

Figure 4: Illustration of appending two sliced models generated by Slice for
$l_{c,1}=\langle e_{1,1}\rangle$ and $l_{c,2}=\langle e_{2,1}\rangle$. They
are appended by Append, resulting in $m_{a^{\prime}}$ that accepts $\langle
e_{1,1},e_{2,1}\rangle$.

####  4.3.3 Append

This algorithm takes as input two models $m_{a}$ and $m_{\mathit{sl}}$; it
returns an updated version of $m_{a}$ built by appending $m_{\mathit{sl}}$ to
the end of the original version of $m_{a}$. If $m_{a}$ is an empty model
(i.e., when Slice is called for the first time after the initialization of
$m_{a}$ in line 1 in Algorithm 1), the algorithm simply returns
$m_{\mathit{sl}}$. Otherwise, the algorithm merges the final state of $m_{a}$
and the initial state of $m_{\mathit{sl}}$ and ends by returning the updated
$m_{a}$. Merging two states $s_{x}$ and $s_{y}$ is done by simply changing
both the source states of all outgoing transitions of $s_{y}$ and the target
states of all incoming transitions of $s_{y}$ as $s_{x}$. Note that a sliced
model $m_{\mathit{sl}}$ has only one final state as noted in Section 4.3.2,
and therefore so does $m_{a}$.

For example, let us consider the case where Append is called with parameters
$m_{a}=\mathit{slice}_{1}$ and $m_{\mathit{sl}}=\mathit{slice}_{2}$ shown in
the left block of Figure 4. The algorithm merges $s_{9}$ (i.e.,the final state
of $m_{a}$) and $s_{13}$ (i.e., the initial state of $m_{\mathit{sl}}$),
resulting in $m_{a^{\prime}}$ shown in the right block of Figure 4.

####  4.3.4 Union

This algorithm takes as input a set of models $A$; it returns a model $m_{u}$
that is able to accept all logs that can be accepted by all models in $A$. To
do this, the algorithm simply merges the initial states of all models in $A$,
and ends by returning the merged model as $m_{u}$.

We remark that merging states in Append and Union can make the resulting model
non-deterministic. Actually, the two algorithms are simplified222To be
precise, merging two states is not equivalent to introducing an epsilon-
transition from one to another, but equivalent to introducing bi-directional
epsilon-transitions between the two states. versions of the standard NFA (Non-
deterministic Finite Automata) concatenation and union operation,
respectively. We will discuss non-determinism later in the determinization
stage (see Section 4.4).

####  4.3.5 Application of Stitch to the running example

Let us consider the case where the Stitch algorithm is called with parameters
$L_{\mathit{sys}}=\\{l_{1},l_{2}\\}$ and
$M_{C}=\\{m_{\texttt{M}},m_{\texttt{J}}\\}$. For $l_{1}$, the call to
Partition yields $P=\langle l_{c,1},l_{c,2},\dots,l_{c,5}\rangle$ where
$l_{c,1}=\langle e_{1,1}\rangle$, $l_{c,2}=\langle e_{2,1}\rangle$,
$l_{c,3}=\langle e_{3,1}\rangle$, $l_{c,4}=\langle
e_{4,1},e_{5,1},e_{6,1},e_{7,1}\rangle$, and $l_{c,5}=\langle e_{8,1}\rangle$.
For each $l_{c,i}\in P$, the call to Slice yields a sliced model
$\mathit{slice}_{i}$ shown in the top block of Figure 5, originated from the
component models $m_{\texttt{M}}$ and $m_{\texttt{J}}$ shown in Figure 2. The
five sliced models are appended to $m_{a}$ using Append, resulting in a
system-level model $m_{a,1}$ shown at the bottom of Figure 5. The state names
of $m_{a,1}$ show how the initial and final states of the sliced models were
merged. For example, $s_{10,14,10}$ is generated by merging $s_{10}$ (i.e.,
the final state of $\mathit{slice}_{3}$), $s_{14}$ (i.e., the initial and
final state of $\mathit{slice}_{4}$), and $s_{10}$ (i.e., the initial state of
$\mathit{slice}_{5}$). Note that each $\mathit{slice}_{i}$ accepts the
corresponding $l_{c,i}\in P$ and, as a result, $m_{a,1}$ accepts $l_{1}$. The
algorithm ends the iteration for $l_{1}$ by adding $m_{a,1}$ into $A$ and
moves on to the next iteration to process log $l_{2}$. After this second
iteration completes, the newly built model $m_{a,2}$ for $l_{2}$ is added to
$A$; the call to Union yields a system model $m_{\mathit{uni}}$, shown at the
top of Figure 6. We can see that $m_{\mathit{uni}}$ is composed of $m_{a,1}$
(i.e., the upper subgraph enclosed with a blue dashed line) and $m_{a,2}$
(i.e., the lower subgraph enclosed with a red dashed line).

Figure 5: Illustration of building a system-level model for the running
example log $l_{1}$. The five sliced models are generated by Slice according
to the partition of $l_{1}$. They are appended by Append to build a system-
level model $m_{a,1}$ that accepts $l_{1}$. Figure 6: Illustration of the
determinization using state merges for the system model build for the running
example logs. The labels of nondeterministic transitions are highlighted in
bold.

In the above example, we can see that the output model $m_{\mathit{uni}}$
accepts the input logs $L_{\mathit{sys}}$ as expected. However,
$m_{\mathit{uni}}$ is actually not equivalent to $m_{\texttt{S}}$ shown in
Figure LABEL:sub@fig:system: there exist potential logs that only
$m_{\texttt{S}}$ can accept, but $m_{\mathit{uni}}$ cannot. We will see how
$m_{\mathit{uni}}$ can be further transformed through the last stage of
_PRINS_ , i.e., determinization, described in detail in Section 4.4.

###  4.4 Determinization

The last stage of _PRINS_ post-processes the model yielded by the stitching
stage for mainly converting a non-deterministic model into a deterministic
one.

Through the projection, inference, and stitching stages, we already get a
system model as an intermediate output. The non-determinism nature of such a
model does not represent an issue in many use cases (e.g., program
comprehension Cook and Wolf (1998), test case generation Fraser and Walkinshaw
(2012)). However, especially when a model is used as an “acceptor” of (the
behavior recorded in) a log (e.g., in the case of anomaly detection Chandola
et al. (2009)), determinism is important for efficient checking. To broaden
the use cases of _PRINS_ , we propose this determinization stage as an
optional post-processing in _PRINS_.

The simplest way of converting a non-deterministic model into a deterministic
one is using standard algorithms, such as the powerset construction Hopcroft
et al. (2006), that guarantee the equivalence between the non-deterministic
model provided in input and the deterministic one returned as output. However,
the worst-case complexity of the powerset construction is exponential in the
size of the non-deterministic model, making it an impracticable solution for
many applications.

To tackle this issue, we introduce a new approach inspired by the heuristic-
based determinization approach proposed by Damas et al. (2005). Unlike the
powerset construction, their heuristic-based approach recursively merges the
target states of non-deterministic transitions starting from the given state
of the input model. While the idea of this approach is intuitive, since it
simply merges states during the process of determinization, it may
_generalize_ the model being determinized, meaning the determinized model may
accept additional logs that are not accepted by the original non-deterministic
model. Our preliminary evaluation found that this simple strategy of merging
states can produce an _over_ -generalized model by merging too many states,
especially when there are already many non-deterministic transitions in the
input model. To avoid such over-generalization, we propose a new algorithm,
called _Hybrid Determinization with parameter $u$_ (HDu), by combining ideas
from the heuristic-based determinization and the powerset construction
methods.

Our HDu merges the target states of non-deterministic transitions, similar to
the heuristic-based determinization. However, to prevent over-generalization
it applies a heuristic: HDu does not merge a state with other
states333Regardless of the number of states to be merged, multiple states can
be merged into one state at once, not incrementally. if the former has already
been merged $u$ times. The rationale behind this heuristic is to prevent the
merging of too many states, which causes the over-generalization. If non-
deterministic transitions remain because their target states are restricted
from being merged because of the value of $u$, HDu uses the powerset
construction to remove the remaining non-determinism while preserving the
level of the generalization. The larger the $u$ value is used, the more the
model can be generalized. The $u$ value can also be seen as the weight between
the heuristic-based determinization and the powerset construction; HD∞ is the
same as the heuristic-based determinization, while HD0 is the same as the
powerset construction.

Algorithm 3 shows the pseudocode of HDu. It takes as input a non-deterministic
model $m_{n}$ and a threshold $u$; it returns a deterministic model $m_{d}$
that can accept all logs that can be accepted by $m_{n}$.

1

Input : Model $m_{n}$

Threshold $u$

Output : Model $m_{d}$

2

3Model $m_{d}\leftarrow\mathit{copy}(m_{n})$

4 Set of States $S_{n}\leftarrow\textbf{{getTargetStatesWithLimit}}(m_{d},u)$

5 while  _$S_{n}\neq\emptyset$_ do

6 $\mathit{mergeStates}(m_{d},S_{n})$

7 $S_{n}\leftarrow\textbf{{getTargetStatesWithLimit}}(m_{d},u)$

8

9 if  _$\mathit{isNonDeterministic}(m_{d})$_ then

10 $m_{d}\leftarrow\mathit{standardDeterminize}(m_{d})$

11 return $m_{d}$

Algorithm 3 Hybrid Determinization (HDu)

The algorithm iteratively merges the set of states $S_{n}$ in $m_{d}$ as
determined by getTargetStatesWithLimit (described below) until it is empty
(lines 3–3). After the iteration ends, if $m_{d}$ is still non-deterministic,
the algorithm removes all the remaining non-determinism using the powerset
construction (lines 3–3). The algorithm ends by returning $m_{d}$.

The heuristic to avoid the over-generalization is mainly implemented in
function getTargetStatesWithLimit (whose pseudocode is shown in Algorithm 4).
It takes as input a non-deterministic model $m_{n}$ and a threshold $u$; it
returns a set of states $S_{n}$ to be merged to reduce non-determinism in
$m_{n}$, which does not contain the states that are restricted from being
merged because of the threshold $u$.

1

Input : Model $m_{n}$

Threshold $u$

Output : Set of States $S_{n}$

2 foreach  _Guarded Transition $\mathit{gt}\in getAllGT(m_{n})$_ do

3 Set of States $S_{t}\leftarrow\mathit{getTargetStates}(\mathit{gt})$

4 Set of States $S_{n}\leftarrow\mathit{removeAlreadyMergedStates}(S_{t},u)$

5 if  _$|S_{n}| >1$_ then

6 return $S_{n}$

7

8

9 return $\emptyset$

Algorithm 4 getTargetStatesWithLimit

For each guarded transition $\mathit{gt}$ in the transition relation of
$m_{n}$ (lines 4–4), the algorithm gets the set of target states $S_{t}$ (line
4), removes the states that have already been merged $u$ times from $S_{t}$ to
build $S_{n}$ (line 4), and returns $S_{n}$ (and ends) if it has more than one
state (lines 4–4). If there is no such $S_{n}$ for all guarded transitions,
the algorithm ends by returning $S_{n}=\emptyset$ (line 4).

For example, let us consider the case where the getTargetStatesWithLimit
algorithm begins the iteration for a non-deterministic (guarded) transition
whose target states are $s_{\mathit{abc}}$, $s_{d}$, and $s_{e}$, with $u=1$.
If $s_{\mathit{abc}}$ was generated by merging three states $s_{a}$, $s_{b}$,
and $s_{c}$, $S_{t}$ becomes $\\{s_{\mathit{abc}},s_{d},s_{e}\\}$ but $S_{n}$
becomes $\\{s_{d},s_{e}\\}$ because $\mathit{removeAlreadyMergedStates}$
excludes $s_{\mathit{abc}}$ (since it has been already merged once, given
$u=1$). Since $|S_{n}|=2$, the algorithm ends by returning
$S_{n}=\\{s_{d},s_{e}\\}$.

Figure 6 shows how HD works for our running example. Recall that
$m_{\mathit{uni}}$ is the intermediate output of the stitching stage. Starting
from the initial state, HD iteratively merges the target states of non-
deterministic transitions, such as $s_{1}$ and $s_{1}^{\prime}$ in
$m_{\mathit{uni}}$ and then $s_{2}$ and $s_{2}^{\prime}$ in
$m_{\mathit{int}}$, until no more non-deterministic transition remains; the
resulting model is $m_{\mathit{det}}$. We can see that $m_{\mathit{det}}$ is
exactly the same as (i.e., is graph-isomorphic to) the ideal model
$m_{\texttt{S}}$ in Figure 2.

Notice that HDu causes a reduction in size of the models since it merges the
target states of non-deterministic transitions in the course of its heuristic
determinization. However, a more important question is to what extent the
accuracy of the resulting models varies because of size reduction. In our
empirical evaluation, we will assess the impact of using HDu on the accuracy
of the inferred models in _PRINS_ with respect to the value of threshold $u$.
We will also investigate the execution time of HDu and devise practical
guidelines for choosing the value of $u$ (see Section 5).

##  5 Evaluation

In this section, we report on the evaluation of the performance of _PRINS_ in
generating models of a component-based system from system logs.

First, we assess the execution time of _PRINS_ in inferring models from large
execution logs. This is the primary dimension we focus on since we propose
_PRINS_ as a viable alternative to state-of-the-art techniques for processing
large logs. Second, we analyze how accurate the models generated by _PRINS_
are. This is an important aspect because it is orthogonal to scalability but
has direct implications on the feasibility of using the generated models to
support software engineering tasks (e.g., test case generation). However, the
execution time of _PRINS_ and the accuracy of the models generated by _PRINS_
might depend on its configuration, i.e., the number of parallel inference
tasks in the inference stage (see Section 4.2) and the parameter $u$ of HDu in
the determinization stage (see Section 4.4). Therefore, it is important to
investigate the best configurations of _PRINS_ before comparing it to state-
of-the-art techniques.

Summing up, we investigate the following research questions:

  1. RQ1:

How does the execution time of _PRINS_ change according to the parallel
inference tasks in the inference stage?

  2. RQ2:

How does the execution time of HDu change according to parameter $u$?

  3. RQ3:

How does the accuracy of the models (in the form of gFSMs) generated by HDu
change according to parameter $u$?

  4. RQ4:

How fast is _PRINS_ when compared to state-of-the-art model inference
techniques?

  5. RQ5:

How accurate are the models generated by _PRINS_ when compared to those
generated by state-of-the-art model inference techniques?

###  5.1 Benchmark and Settings

To evaluate _PRINS_ , we assembled a benchmark composed of logs extracted from
two sources: the LogHub project He et al. (2020) and a personal computer (PC)
running desktop business applications on a daily basis. Table 1 lists the
systems we included in the benchmark (grouped by source) and provides
statistics about the corresponding logs: the number of components (column _#
Cmps_), the number of logs444In LogHub He et al. (2020), the original dataset
for HDFS contains $575\,061\text{\,}\mathrm{l}$ogs (distinguishable by block-
ids), but we used only 1000 logs that are randomly sampled from all logs,
since we found that the 1000 logs are representative enough, as they contain
all event templates that appear in all logs. (column _# Logs_), the number of
event templates (column _# Tpls_), and the total number of log entries555When
additional logging level information (e.g., info, warn, debug, error) was
available for each log entry, we only used the log entries of the two main
levels, i.e., info and error, as the others provide unnecessary details (e.g.,
the status of a specific internal variable) for building behavioral models.
(column _# Entries_).

Table 1: Subject Systems and Logs Source | System | # Cmps | # Logs | # Tpls | # Entries | Conf
---|---|---|---|---|---|---
LogHub He et al. (2020) | Hadoop | $19$ | $68$ | $41$ | $3575$ | $1.00$
HDFS | $8$ | $1000$ | $16$ | $18\,741$ | $0.95$
Linux | $31$ | $42$ | $115$ | $11\,259$ | $0.78$
Spark | $11$ | $217$ | $21$ | $67\,725$ | $0.98$
Zookeeper | $18$ | $36$ | $40$ | $25\,298$ | $0.91$
PC | CoreSync | $54$ | $1418$ | $204$ | $30\,223$ | $0.94$
NGLClient | $27$ | $42$ | $70$ | $892$ | $0.89$
Oobelib | $12$ | $250$ | $147$ | $56\,557$ | $0.89$
PDApp | $10$ | $787$ | $75$ | $47\,394$ | $0.87$

LogHub He et al. (2020) is a data repository containing a large collection of
structured logs (and the corresponding event templates) from 16 different
systems. Among them, we selected the logs of the five systems based on two
conditions:  (1) the component (name or ID) for each log entry is available in
the logs;  (2) the number of logs for each system is more than 10.  We set
condition #1 because _PRINS_ targets component-based systems; as for condition
#2, we require a minimum number of logs to validate the accuracy as part of
RQ2 (see Section 5.6).

To increase the diversity of our benchmark logs, we also included the logs of
a personal computer running daily for office use. We collected the logs
through the built-in Console.app application of macOS 10.15. Among the many
logs available on the PC, we selected those fulfilling the same two conditions
stated above, ending up with four systems. Additionally, to identify the
events templates of the unstructured log messages in these logs, we first used
state-of-the-art tools for log message format identification (i.e., Drain He
et al. (2017) and MoLFI Messaoudi et al. (2018)) to compute an initial set of
templates and then manually refined them, e.g., by collapsing similar
templates into a single one. All the structured logs (anonymized to hide
sensitive information) are available online (see Section 5.8).

To additionally evaluate whether the benchmark logs are sufficient to infer
models that faithfully represent actual system behaviors, following another
state-of-the-art model inference study Emam and Miller (2018), we computed log
confidence scores using the formula provided by Cohen and Maoz (2015). Briefly
speaking, a low confidence score (e.g., $\leq 0.2$) indicates that the logs
are not sufficient, and therefore the model inferred from the logs are likely
not to be compatible with the actual behaviors of the system under analysis.
On the contrary, a high confidence score (e.g., $\geq 0.85$) indicates that
the logs are probably sufficient for the inferred model to faithfully
represent the actual system behaviors. Column _Conf_ in Table 1 shows the
confidence scores calculated for our benchmark logs. The values suggest that
the logs are mostly sufficient to infer faithful models. Although the
confidence score for Linux (0.78) is lower than the other benchmarks scores,
the Linux logs are from an existing benchmark He et al. (2020) and cannot
therefore be improved. Furthermore, since our main focus is to compare _PRINS_
and other model inference techniques using the same logs, having a somewhat
moderate confidence score is not a major threat to the validity of our
experiments.

We conducted our evaluation on a high-performance computing platform666The
experiments presented in this paper were carried out using the HPC facilities
of the University of Luxembourg Varrette et al. (2014) (see https://hpc.uni.lu
for more details)., using nodes equipped with Dell C6320 units (2 Xeon
E5-2680v4@$2.4\text{\,}\mathrm{GHz}$, $128\text{\,}\mathrm{GB}$). We allocated
four cores and $16\text{\,}\mathrm{GB}$ per job.

###  5.2 RQ1: Parallel Inference

####  5.2.1 Methodology

To answer RQ1, we assessed the execution time of _PRINS_ with different
parallelization configurations for its inference stage. Specifically, we
varied the maximum number of parallel workers (i.e., the maximum number of
parallel inference tasks) from one to four in steps of one to investigate the
relationship between the maximum number of parallel workers and the execution
time of _PRINS_. For example, when the number is set to four, at most four
workers are running in parallel to infer four component models at the same
time in the inference stage of _PRINS_.

To infer individual component models in the inference stage of _PRINS_ , we
used MINT Walkinshaw et al. (2016), a state-of-the-art model inference tool.
We selected MINT because other tools are either not publicly available or
require additional information other than just logs (e.g., source code or
architectural design documents). In all experiments, we used the same
configuration of MINT (i.e., minimum state merge score $k=2$ and AdaBoost as
data classifier algorithm), which we set based on the one used in a previous
study Walkinshaw et al. (2016) conducted by the authors of MINT.

For each system in our benchmark, we ran the four configurations of _PRINS_ to
infer a system model from the same logs and measured their execution time. To
account for the randomness in measuring execution time, we repeated the
experiment 10 times.

We remark that we disabled the determinization stage of _PRINS_ because it is
not the main focus of RQ1. Determinization configurations will be
comprehensively investigated in RQ2 and RQ3.

####  5.2.2 Results

Figure 7: Relationship between the maximum number of parallel workers and the
execution time of _PRINS_

Figure 7 shows the relationship between the maximum number of parallel
inference tasks (workers) and the execution time of _PRINS_. None of the
configurations was able to infer a model for Spark on all ten executions due
to out-of-memory errors. This occurred because MINT (used by _PRINS_ for
inferring individual component models) could not process the (huge) log of a
component that is responsible for producing about 97% of all log messages of
the system.

For all systems in our benchmark, it is clear that execution time decreases as
the maximum number of parallel inferences increases. This is consistent with
the general expectation for parallelization.

However, doubling the maximum number of parallel inferences does not decrease
the execution time in half. For example, there is no clear difference in
execution time between two workers and four workers for Linux, Zookeeper,
CoreSync, and PDApp. A detailed analysis of the results found that it is
mainly because there are at most two major components that take up more than
70% of all log messages. For example, Linux has two major components that
represent around 50% and 34% of all log messages, while the third-largest
component takes up only 9.4% of all messages. This implies that, for systems
like Linux, inferring component models is fast enough, except for a few major
components, and therefore having more than three parallel workers does not
significantly reduce execution time.

The answer to RQ1 is that the execution time of _PRINS_ can be significantly
reduced by the parallel inference of individual component models. However, the
magnitude of the reduction in execution time is not linear with respect to the
maximum number of parallel inferences, because not all components are equally
sized in their logs. In practice, an engineer can set the maximum number of
parallel inferences considering both available resources (e.g., the number of
CPUs and the total size of memory) and the log size distribution of
components.

###  5.3 RQ2: Execution Time of Hybrid Determinization

####  5.3.1 Methodology

To answer RQ2, we assessed the execution time of HDu with different parameter
values for $u$. Specifically, we varied the value of $u$ from one to ten in
steps of one to investigate the relationship between the value of $u$ and the
execution time of HDu. To additionally compare HDu to the standard powerset
construction, we also set $u=0$ (see Section 4.4 for more details).

For each system in our benchmark, we first ran _PRINS_ without the
determinization stage to infer a non-deterministic system model. _PRINS_
internally used the same configuration of MINT as used in RQ1. For each non-
deterministic model, we ran HDu for all $u=0,1,\dots,10$ and measured their
execution time. To account for the randomness in measuring execution time, we
repeated the experiment 10 times.

####  5.3.2 Results

Figure 8: Relationship between the value of $u$ and the execution time of HDu

Figure 8 shows the relationship between the value of $u$ and the execution
time of HDu. We have no results for Spark because its non-deterministic system
model was not available for the reasons explained in Section 5.2.2.

For all the cases in which _PRINS_ completed their execution for generating
non-deterministic system models, HDu (with $u\geq 1$) took less than a minute.
This implies that our hybrid determinization can efficiently determinize non-
deterministic models generated by _PRINS_. On the other hand, the powerset
construction (i.e., $u=0$) took more than an hour for Zookeeper. This is due
to the worst-case complexity of the powerset construction as discussed in
Section 4.4. Interestingly, for the same non-deterministic model of Zookeeper,
using $u\geq 1$ significantly reduces the determinization time. This clearly
highlights the benefit of hybrid determinization, i.e., combining the powerset
construction and the heuristic-based determinization.

The answer to RQ2 is that the execution time of HDu is practically the same
for all $u\geq 1$ because all of them are completed in less than a minute.
This implies that the best value of $u$ can be selected mainly based on the
accuracy of the resulting models, which will be investigated in RQ3. On the
other hand, the powerset construction is indeed very time-consuming in extreme
cases, which is consistent with its well-known theoretical worst-case
complexity. Since this cannot be predicted before running the determinization
algorithms, in practice, we can conclude that HDu with $u\geq 1$ is to be
recommended over the standard powerset construction.

###  5.4 RQ3: Accuracy of Models Generated by Hybrid Determinization

####  5.4.1 Methodology

To answer RQ3, we first ran _PRINS_ without the determinization stage to infer
a non-deterministic system model for each system in our benchmark, as we did
for RQ2. For each of the non-deterministic models, we then ran HDu for all
$u=0,1,\dots,10$ and measured the accuracy of the deterministic models
generated by HDu.

We measured the accuracy in terms of _recall_ , _specificity_ , and Balanced
Accuracy (BA), following previous studies Damas et al. (2005); Walkinshaw et
al. (2016); Mariani et al. (2017); Emam and Miller (2018) in the area of model
inference. Recall measures the ability of the inferred models of a system to
accept “positive” logs, i.e., logs containing feasible behaviors that the
system may exhibit. Specificity measures the ability of the inferred models to
reject “negative” logs, i.e., logs containing behaviors that the system cannot
exhibit. BA measures the balance between recall and specificity and provides
the summary of the two.

However, it is intrinsically difficult to evaluate the accuracy of inferred
models when there is no ground truth, i.e., reference models. To address this
issue, we computed the metrics by using the well-known $k$-fold cross
validation (CV) method with $k=10$, which has also been used in previous model
inference studies Walkinshaw et al. (2016); Mariani et al. (2017); Emam and
Miller (2018). This method randomly partitions a set of logs into $k$ non-
overlapping folds: $k-1$ folds are used as “training set” from which the model
inference tool infers a model, while the remaining fold is used as “test set”
to check whether the model inferred by the tool accepts the logs in the fold.
The procedure is repeated $k$ times until all folds have been considered
exactly once as the test set. For each fold, if the inferred model
successfully accepts a positive log in the test set, the positive log is
classified as True Positive (TP); otherwise, the positive log is classified as
False Negative (FN). Similarly, if an inferred model successfully rejects a
negative log in the test set, the negative log is classified as True Negative
(TN); otherwise, the negative log is classified as False Positive (FP). Based
on the classification results, we calculated
$\mathit{recall}=\tfrac{|\mathit{TP}|}{|\mathit{TP}|+|\mathit{FN}|}$,
$\mathit{specificity}=\tfrac{|\mathit{TN}|}{|\mathit{TN}|+|\mathit{FP}|}$, and
the BA as the average of the recall and the specificity.

As done in previous work Walkinshaw et al. (2016); Mariani et al. (2017); Emam
and Miller (2018), we synthesized negative logs from positive logs by
introducing small changes (mutations):  (1) swapping two randomly selected log
entries,  (2) deleting a randomly selected log entry, and  (3) adding a log
entry randomly selected from other executions.  The changes should be small,
because the larger the change is, the easier an inferred model can detect the
deviation of negative logs. To further increase the probability777Recall that
there are no reference models for the subject systems, and therefore we cannot
verify if a synthesized log correctly contains an invalid system behavior.
that a log resulting from a mutation contains invalid behaviors of the system,
we checked whether the sequence of entries around the mutation location (i.e.,
the mutated entries and the entries immediately before and after the mutants)
did not also appear in the positive logs.

####  5.4.2 Results

Figure 9: Relationship between the value of $u$ and the accuracy of the models
generated by HDu

Figure 9 shows the relationship between the value of $u$ and the accuracy of
the deterministic models generated by HDu. Again, Spark is not shown for the
reasons explained in Section 5.2.2.

For Hadoop, CoreSync, NGLClient, Oobelib, and PDApp, there is no change in
recall, specificity, and BA when the value of $u$ changes. This means that,
for these five systems, the accuracy of deterministic models generated by HDu
does not change when the value of parameter $u$ changes (for
$u=0,1,\dots,10$). Furthermore, considering the fact that the powerset
construction (i.e., HD0) guarantees the equivalence between the non-
deterministic model provided in input and the deterministic one returned as
output, identical accuracy for $u=0,1,\dots,10$ also implies that, regardless
of the value of $u$, HDu can convert non-deterministic models into
deterministic ones without sacrificing model accuracy for five out of the
eight systems in our benchmark, regardless of the value of $u$.

For HDFS, Linux, and Zookeeper, as the value of $u$ increases, recall values
increase while specificity values decrease. This means that, for the
deterministic models generated by HDu, if we increase the value of $u$, then
the ability to correctly accept positive logs is improved whereas the ability
to correctly reject negative logs is diminished. This is intuitive because
increasing the value of $u$ merges more states to remove non-deterministic
transitions, yielding a generalized model that accepts more logs than the
original, non-deterministic model.

However, we can distinguish the increase in recall and the decrease in
specificity, because the former happens when the recall values of the input
non-deterministic models are close to zero (i.e., Linux and Zookeeper),
whereas the latter happens when the specificity values of the non-
deterministic models are around 0.8. Since the non-deterministic models of
Linux and Zookeeper were already incapable of correctly accepting positive
logs, slightly improving them with determinization is not practically
significant. In fact, the logs of Linux and Zookeeper were already inadequate
for model inference in general, which will be discussed in detail in Section
5.6.2. On the other hand, the decrease in specificity for HDFS is significant
for HDu since it should preserve the high specificity of the non-deterministic
model provided in input as much as possible. As a result, practically
speaking, the smaller the value of $u$, the better. Indeed, this supports our
idea that using $u$ to limit over-generalization in hybrid determinization is
helpful to avoid a significant accuracy loss.

The answer to RQ3 is that, for five out of eight systems in our benchmark, the
value of $u$ does not affect the accuracy of the deterministic models
generated by HDu. However, for one system, the accuracy practically decreases
as the value of $n$ increases. Additionally considering the high execution
time of HD0 (RQ2), we can therefore conclude that $u=1$ is the best
configuration trade-off for HDu in terms of both execution time and accuracy
in practice.

###  5.5 RQ4: Execution Time of _PRINS_ Compared to State-of-the-Art

####  5.5.1 Methodology

To answer RQ4, we assessed the scalability of _PRINS_ , in terms of execution
time, in comparison with MINT Walkinshaw et al. (2016), the same tool that is
used internally by _PRINS_ to generate component-level models. In other words,
we used _two_ instances of MINT: the one used for the comparison in inferring
system models; the other one used internally by _PRINS_. By doing this, we
investigated to what extent the execution time of model inference can be
improved by using the divide-and-conquer approach of _PRINS_ compared to using
a vanilla model inference.

Recall that _PRINS_ can naturally infer many component models in parallel at
the inference stage, which can further improve the execution time of _PRINS_
as shown by the result of RQ1. To further investigate this aspect, we used
_two_ configurations of _PRINS_ : _PRINS_ -P where the parallel inference is
enabled and _PRINS_ -N where no parallelization is used. For _PRINS_ -P, we
set the maximum number of parallel inferences to four, based on the result of
RQ1 and the number of allocated nodes (as described in Section 5.1). For both
_PRINS_ -P and _PRINS_ -N, we used the determinization stage (i.e., HDu),
since MINT produces a deterministic model. For the value of $u$, we used $u=1$
based on the results of RQ2 and RQ3.

We also varied the size of input logs to better understand the impact of using
larger logs on the execution time of _PRINS_ and MINT. To systematically
increase such size while preserving the system behaviors recorded in
individual logs, we duplicated each of the logs following the experiment
design of Busany and Maoz (2016). For example, when the duplication factor is
set to eight for the 250 logs ($56\,557$ log entries) of Oobelib, each of the
250 logs is duplicated eight times, and therefore a total of $250\times
8=2000$ logs ($8\times$56\,557$=$452\,456$$ log entries) are given as input
both to _PRINS_ and to MINT. Notice that the system characteristics, such as
the number of components and the number of event templates, remain the same
when using duplicated logs. Since MINT could not infer models for large logs
due to out-of-memory failures or timeout (after 10 hours) in our preliminary
evaluation, we only varied the duplication factor from 1 to 8 in steps of 1.

For each set of duplicated logs for each system in our benchmark, we ran MINT,
_PRINS_ -P, and _PRINS_ -N to infer a deterministic system model from the same
logs and measured the execution time of the tools. To account for the
randomness in measuring execution time, we repeated the experiment three times
and computed the average results.

####  5.5.2 Results

Figure 10: Comparison between MINT, _PRINS_ -P, and _PRINS_ -N in terms of
execution time for various log sizes (obtained by varying the duplication
factor of the benchmark logs)

Figure 10 shows the comparison results between MINT, _PRINS_ -P, and _PRINS_
-N in terms of execution time. Because MINT (both the standalone instance and
the one used by _PRINS_) could not process the log of Spark, as explained in
Section 5.2.2, we have no results for it. Also, due to the same reason, we
have no results for Zookeeper with a duplication factor above 5.

For all the cases in which at least one of the tools completed their
execution, we can see two distinct patterns in MINT’s execution time: for all
of the duplicated logs, MINT completed its execution only in two cases (Hadoop
and NGLClient) out of eight; otherwise, MINT could not complete its execution
(HDFS, Linux, Zookeeper, CoreSync, Oobelib, and PDApp).

However, for Hadoop and NGLClient, for which MINT completed its execution for
all of the duplicated logs, we can see that MINT was quite fast (the execution
time is less than $5\text{\,}\mathrm{s}$); this can be attributed to the small
size of the logs ($28\,600$ entries for Hadoop and $7136$ entries for
NGLClient even with a duplication factor of 8). When the (standalone) MINT
instance is already fast, _PRINS_ is actually slower than MINT due to the
overhead for projection, stitching, and determinization. Nevertheless, even in
these cases, using _PRINS_ instead of MINT is still practical since _PRINS_ -P
took less than $15\text{\,}\mathrm{s}$. Also, we want to remark that such
small logs are not really representative of the large logs targeted by
_PRINS_.

For the remaining six cases (HDFS, Linux, Zookeeper, CoreSync, Oobelib, and
PDApp) with larger log sizes, the execution time of MINT increases steeply as
the duplication factor increases. Furthermore, with a duplication factor above
a certain value (5 for HDFS, 4 for Zookeeper and PDApp, and 3 for Linux,
CoreSync, and Oobelib), MINT could not complete its execution due to out-of-
memory failures (Zookeeper) or timeouts after 10 hours (HDFS, Linux, CoreSync,
Oobelib, and PDApp). In contrast, for the same logs, the execution time of
_PRINS_ -N increases slowly as the duplication factor increases, and there is
no case where _PRINS_ -N could not complete its execution (except for
Zookeeper in which the MINT instance internally used by _PRINS_ for component
model inference caused an out-of-memory failure when the duplication factor is
greater than 5). This means that the scalability of model inference can be
greatly improved by using the divide-and-conquer approach of _PRINS_.
Furthermore, for Zookeeper with a duplication factor of 5, though MINT could
not complete its execution due to out-of-memory failures, _PRINS_ , on the
other hand, completed successfully due to its divide-and-conquer approach.

Interestingly, for the six cases with larger log sizes, the difference between
_PRINS_ -P and _PRINS_ -N is very small compared to the difference between
_PRINS_ -N and MINT. This means that the key factor in the scalability
improvement of _PRINS_ is the divide-and-conquer approach, not the parallel
inference of component models.

The answer to RQ4 is that the divide-and-conquer approach of _PRINS_ greatly
improves the scalability of model inference for component-based system logs
and can even enable model inference when MINT leads to out-of-memory failures.

###  5.6 RQ5: Accuracy of _PRINS_ Compared to State-of-the-Art

####  5.6.1 Methodology

To answer RQ2, we assessed the accuracy of the models inferred both by _PRINS_
and by MINT for each system in our benchmark, using the same configuration for
_PRINS_ and MINT used as part of RQ4. We measured the accuracy in terms of
recall, specificity and BA as we did for RQ3 (see Section 5.4.1 for more
details).

####  5.6.2 Results

Table 2: Comparison between MINT (M) and _PRINS_ (P) in terms of Accuracy. Differences between recall ($\Delta_{R}$), specificity ($\Delta_{S}$), and balanced accuracy ($\Delta_{B}$) values are expressed in percentage points ($\mathrm{\textup{pp}}$); $\mathcal{LDS}$ is the log-component diversity score. | Recall | Specificity | Balanced Accuracy |
---|---|---|---|---
System | M | P | $\Delta_{R}$ | M | P | $\Delta_{S}$ | M | P | $\Delta_{B}$ | $\mathcal{LDS}$
Hadoop | $1.00$ | $1.00$ | $0.0$ | $0.91$ | $0.88$ | $-3.1$ | $0.96$ | $0.94$ | $-1.5$ | $0.015$
HDFS | $0.98$ | $0.98$ | $-0.1$ | $0.37$ | $0.72$ | $34.9$ | $0.68$ | $0.85$ | $17.4$ | $0.007$
Linux | $0.36$ | $0.12$ | $-23.5$ | $0.89$ | $0.98$ | $9.5$ | $0.62$ | $0.55$ | $-7.0$ | $0.561$
Zookeeper | $0.22$ | $0.10$ | $-11.7$ | $0.93$ | $1.00$ | $7.5$ | $0.57$ | $0.55$ | $-2.1$ | $0.571$
CoreSync | $0.95$ | $0.93$ | $-1.6$ | $0.85$ | $0.89$ | $4.2$ | $0.90$ | $0.91$ | $1.3$ | $0.048$
NGLClient | $0.86$ | $0.86$ | $0.0$ | $1.00$ | $0.98$ | $-2.5$ | $0.93$ | $0.92$ | $-1.3$ | $0.195$
Oobelib | $0.98$ | $0.98$ | $0.0$ | $1.00$ | $1.00$ | $0.0$ | $0.99$ | $0.99$ | $0.0$ | $0.016$
PDApp | $0.97$ | $0.95$ | $-2.3$ | $0.98$ | $0.98$ | $-0.1$ | $0.97$ | $0.96$ | $-1.2$ | $0.014$
Average | $0.79$ | $0.74$ | $-4.9$ | $0.87$ | $0.93$ | $6.3$ | $0.83$ | $0.83$ | $0.7$ | $0.178$

The accuracy scores of _PRINS_ and MINT are shown in Table 2. Under the
_Recall_ column, sub-columns _M_ and _P_ indicate the recall of MINT and
_PRINS_ , respectively, and sub-column _$\Delta_{R}$_ indicates the difference
in recall between _PRINS_ and MINT in percentage points
($\mathrm{\textup{pp}}$). The sub-columns under the _Specificity_ and
_Balanced Accuracy_ columns follow the same structure, with sub-column
_$\Delta_{S}$_ indicating the difference in specificity between _PRINS_ and
MINT, and sub-column _$\Delta_{B}$_ indicating the difference in BA between
_PRINS_ and MINT. Again, none of the tools was able to infer a model for
Spark, for the reasons explained in Section 5.5.2.

For all the cases in which the 10-fold CV completed without error, the average
difference in BA between _PRINS_ and MINT is only
$\DTLfetch{max}{data}{all}{ba.avg}\text{\,}\mathrm{\textup{pp}}$, meaning
that, on average, _PRINS_ is as accurate as MINT in inferring system models in
terms of BA. However, the average difference in recall between _PRINS_ and
MINT is $\DTLfetch{max}{data}{all}{recall.avg}\text{\,}\mathrm{\textup{pp}}$,
while the average difference in specificity between _PRINS_ and MINT is
$\DTLfetch{max}{data}{all}{spec.avg}\text{\,}\mathrm{\textup{pp}}$. This
implies that, on average, _PRINS_ tends to infer models that are relatively
less capable of accepting positive logs but more capable of rejecting negative
logs than those inferred by MINT. The intuitive explanation is that a model
built by _PRINS_ could be, in certain cases discussed below, more specific to
the flows of events recorded in individual input logs, due to the way _PRINS_
builds the model. As described in Section 4.3, _PRINS_ first builds an
intermediate system-level model for each execution log and then merges these
intermediate models by merging only their initial states at the end of the
stitching. Though determinization after stitching might further merge the
other states for removing non-determinism, it does so only for the states
related to non-deterministic transitions. Therefore, the execution-specific
flows of events captured in the intermediate system-level models can be
maintained (without being merged with the others) in the final system model
built by _PRINS_. In contrast, since MINT infers a model for all system
execution logs at once, it tends to merge the execution-specific flows of
events to a larger extent than _PRINS_. As expected, such characteristics also
impact the size of inferred models. As shown in Table 3, the models inferred
by _PRINS_ have on average 3.6 times more states and 5.5 times more
transitions than the models inferred by MINT. Since larger models are more
difficult to manually analyze and comprehend, this might be interpreted as a
drawback of _PRINS_. However, the models inferred by MINT are already too
large to be manually analyzed and understood, especially for systems with
large logs. Thus, automated techniques, such as model abstraction Polyvyanyy
et al. (2008), should be utilized in practice anyway. Furthermore, inferred
models can be used for other important applications, such as test case
generation Fraser and Walkinshaw (2012) and anomaly detection Chandola et al.
(2009), which do not require minimally sized models. Therefore, the increased
model size can be considered acceptable given the significant scalability
improvement reported in Section 5.5.

Table 3: Comparison between MINT and _PRINS_ in terms of Model Size | States | Transitions
---|---|---
System | MINT | _PRINS_ | ratio | MINT | _PRINS_ | ratio
Hadoop | $67$ | $65$ | $1.0$ | $70$ | $66$ | $0.9$
HDFS | $76$ | $392$ | $5.2$ | $177$ | $1308$ | $7.4$
Linux | $342$ | $1990$ | $5.8$ | $476$ | $3322$ | $7.0$
Zookeeper | $376$ | $3184$ | $8.5$ | $553$ | $10667$ | $19.3$
CoreSync | $3876$ | $7524$ | $1.9$ | $4318$ | $10798$ | $2.5$
NGLClient | $148$ | $154$ | $1.0$ | $160$ | $195$ | $1.2$
Oobelib | $447$ | $1195$ | $2.7$ | $545$ | $1484$ | $2.7$
PDApp | $1301$ | $3523$ | $2.7$ | $1466$ | $3801$ | $2.6$
Average | $829$ | $2253$ | $3.6$ | $971$ | $3955$ | $5.5$

Looking at the results for individual systems, results differ significantly in
terms of $\Delta_{R}$ and $\Delta_{S}$ and it is important to understand why
to draw conclusions. For instance, for HDFS, the value of $\Delta_{S}$ is high
($34.9\text{\,}\mathrm{\textup{pp}}$), while the value of $\Delta_{R}$ is
negligible. This shows that _PRINS_ , compared to MINT, can significantly
increase the accuracy of the inferred models by increasing their ability to
correctly reject negative logs, without compromising their ability to
correctly accept positive logs.

On the other hand, for Linux and Zookeeper, the values of $\Delta_{R}$ are
negative and practically significant ($-23.5\text{\,}\mathrm{\textup{pp}}$ for
Linux and $-11.7\text{\,}\mathrm{\textup{pp}}$ for Zookeeper) while the values
of $\Delta_{S}$ are positive and practically significant as well
($34.9\text{\,}\mathrm{\textup{pp}}$ for Linux and
$7.5\text{\,}\mathrm{\textup{pp}}$ for Zookeeper). Furthermore, the recall
values of both MINT and _PRINS_ are relatively lower for Linux and Zookeeper
compared to the recall values for the other systems. In terms of the 10-fold
CV, this means that the positive logs in the test set are not properly
accepted by the models inferred from the logs in the training set for Linux
and Zookeeper. Experimentally, this is mainly due to the logs in the training
set being _too different_ from the logs in the test set, this being caused by
the highly diverse logs of Linux and Zookeeper overall. From a practical
standpoint, this implies that, regardless of the model inference technique, a
model inferred from existing logs may not be able to correctly accept unseen
(but positive) logs if the latter are too different from the former. However,
for the reasons mentioned above, the issue of highly diverse logs has a
moderately larger impact on _PRINS_ than on MINT. Practical implications are
discussed below.

Before running model inference, to effectively predict and avoid cases where
_PRINS_ is likely to be worse than MINT and where both techniques fare poorly,
we propose a new and practical metric to measure the diversity of logs. Our
log diversity metric is based on the combination of components appearing in
the individual logs because  (1) _PRINS_ targets component-based systems
considering not only the individual components’ behaviors but also their
interactions,  (2) it is much simpler than using, for example, the flows of
log entries in the logs, and  (3) it does not require any extra information
other than the logs.  More formally, let $L$ be a set of logs of a system and
let $C(l)$ be the set of components appearing in a log $l\in L$. We define
_log-component diversity score_ ($\mathcal{LDS}$) of the system logs
$L_{\mathit{sys}}$ as $\mathcal{LDS}(L_{\mathit{sys}})=\frac{U-1}{N-1}$, where
$U=\lvert\\{C(l)\mid l\in L_{\mathit{sys}}\\}\rvert$ (i.e., the total number
of unique $C(l)$s for all $l\in L_{\mathit{sys}}$) and $N=\lvert
L_{\mathit{sys}}\rvert$ (i.e., the total number of logs in
$L_{\mathit{sys}}$). In other words, $\mathcal{LDS}$ indicates the ratio of
logs that are unique (i.e., different from the others) in terms of the set of
components appearing in the individual logs, ranging between 0 and 1; the
higher its value, the higher the diversity of the logs in terms of recording
different component interactions. For instance,
$\mathcal{LDS}(L_{\texttt{S}})=0$ for our running example logs
$L_{\texttt{S}}=\\{l_{1},l_{2}\\}$ because $N=2$ and
$U=\lvert\\{C(l_{1}),C(l_{2})\\}\rvert=1$ (since $C(l_{1})$ $=$ $C(l_{2})$ $=$
$\\{\texttt{Master},\texttt{Job}\\}$). This means that $L_{\texttt{S}}$ is not
diverse at all in terms of the appearing components. Notice that
$\mathcal{LDS}$ is a characteristic of logs, which can be calculated before
model inference takes place.

We measured $\mathcal{LDS}$ for the logs of each system in our benchmark.
Column $\mathcal{LDS}$ in Table 2 shows the results. We can see that the
resulting $\mathcal{LDS}$ values of Linux (0.561) and Zookeeper (0.571) are
much higher than those of the other systems, which range between 0.007 (HDFS)
and 0.195 (NGLClient). This confirms that $\mathcal{LDS}$ can be effectively
used to predict whether the models inferred from the existing logs can
correctly accept unseen (but positive) logs or not before running model
inference.

In practice, if $\mathcal{LDS}$ is high (e.g., $>0.2$) for the logs of a
system, it implies that these logs do not sufficiently exercise, in a
comprehensive way, the potential behaviors of the system. As a result, there
is a high probability that many component interactions have not been recorded
or too rarely so. Therefore, an engineer can address this problem by
collecting more system logs until $\mathcal{LDS}$ is low enough.

The answer to RQ5 is that, compared to MINT, _PRINS_ tends to infer models
that are more capable of rejecting negative logs (i.e., yielding a higher
specificity value) while sometimes being less capable of accepting positive
logs (i.e., yielding a lower recall value). The latter happen anyway only in
cases where logs are not adequate for both techniques to work well. In
practice, an engineer can compute the diversity score of the logs before
running model inference, and easily determine whether more logs should be
collected, either through testing or usage, until the score is acceptable.

###  5.7 Discussion and Threats to Validity

From the results above, we conclude that _PRINS_ is an order of magnitude
faster than MINT in model inference for component-based systems, especially
when the input system logs are large and the individual component-level logs
are considerably smaller than the system logs, without significantly
compromising the accuracy of the models. Furthermore, since the large majority
of modern software systems is composed of many “components”, which can be
modules, classes, or services, depending on the context, the logs typically
encountered in practice will satisfy the best conditions for _PRINS_ to fare
optimally: the system logs are large but the individual component-level logs
are considerably smaller. There are situations where _PRINS_ exhibits a poorer
recall than MINT. However, this is the case when the system logs are
inadequate for model inference in general, regardless of the technique, and we
have proposed a way to detect such situations and remedy the problem.

One drawback of the divide-and-conquer approach in _PRINS_ is the increased
size of inferred models. In this sense, _PRINS_ can be seen as sacrificing
model size for improving the execution time of model inference. Nevertheless,
it is worth to note that _PRINS_ does not significantly compromise the
accuracy of the inferred models. Furthermore, given the significant execution
time reduction in model inference on large logs, increasing model size can be
considered acceptable.

In terms of threats to validity, using a specific model inference tool (MINT)
is a potential factor that may affect our results. However, we expect that
applying other model inference techniques would not change the trends in
results since the fundamental principles underlying the different model
inference techniques are very similar. Furthermore, MINT is considered state-
of-the-art among available tools. Nevertheless, an experimental comparison
across alternative tools would be useful and is left for future work.

We used $k$-fold cross validation to evaluate the accuracy of inferred models
due to the lack of ground truth (i.e., reference models) for our benchmark
systems. Therefore, the computed accuracy scores might not faithfully
represent the similarity between the inferred models and their (unknown)
ground truths, especially when the collected logs do not sufficiently
represent the system behaviors. To mitigate this issue, we calculated the log-
confidence values, following existing studies, and these results suggested
that the logs in our benchmarks are sufficient to derive faithfully inferred
models. Furthermore, since the same logs are used for both _PRINS_ and MINT,
not relying on ground truth does not severely affect our empirical evaluation
results.

###  5.8 Data Availability

The implementation of _PRINS_ is available as a Python program. The
replication package, including the benchmark logs and our implementation of
_PRINS_ , is publicly available Shin et al. (2022). We also made a public
GitHub repository at https://github.com/SNTSVV/PRINS.

##  6 Related Work

Starting from the seminal work of Biermann and Feldman (1972) on the _k-Tail_
algorithm, which is based on the concept of state merging, several approaches
have been proposed to infer a Finite State Machine (FSM) from execution traces
or logs. _Synoptic_ Beschastnikh et al. (2011) uses temporal invariants, mined
from execution traces, to steer the FSM inference process to find models that
satisfy such invariants; the space of the possible models is then explored
using a combination of model refinement and coarsening. _InvariMINT_
Beschastnikh et al. (2015) is an approach enabling the declarative
specification of model inference algorithms in terms of the types of
properties that will be enforced in the inferred model; the empirical results
show that the declarative approach outperforms procedural implementations of
_k-Tail_ and _Synoptic_. Nevertheless, this approach requires prior knowledge
of the properties that should hold on the inferred model; such a pre-condition
cannot be satisfied in contexts (like the one in which this work is set) where
the knowledge about the system is limited and the only information about the
system is provided by logs. _mk-Tails_ Busany et al. (2019) is a
generalization of the _k-Tail_ algorithm from single to many parameters, which
enables fine-grained control over the abstraction (generalization) on
different subsets of the events. It allows users to deal with the trade-off
between size and accuracy in model inference.

Other approaches infer other types of behavioral models that are richer than
an FSM. _GK-tail+_ Mariani et al. (2017) infers guarded FSM (gFSM) by
extending the _k-Tail_ algorithm and combining it with Daikon Ernst et al.
(2007) to synthesize constraints on parameter values; such constraints are
represented as guards of the transitions of the inferred model. _MINT_
Walkinshaw et al. (2016) also infers a gFSM by combining EDSM (Evidence-Driven
State Merging) Cheng and Krishnakumar (1993) and data classifier inference
Witten et al. (2016). EDSM, based on the Blue-Fringe algorithm Lang et al.
(1998), is a popular and accurate model inference technique, which won the
Abbadingo Lang et al. (1998) competition; it is also utilized in DFASAT Heule
and Verwer (2013) that won the StaMinA competition Walkinshaw et al. (2013).
Data-classifier inference identifies patterns or rules between data values of
an event and its subsequent events. Using data classifiers, the data rules and
their subsequent events are explicitly tied together. _ReHMM_ (Reinforcement
learning-based Hidden Markov Modeling) Emam and Miller (2018) infers a gFSM
extended with transition probabilities, by using a hybrid technique that
combines stochastic modeling and reinforcement learning. ReHMM is built on top
of MINT; differently from the latter, it uses a specific data classifier
(Hidden Markov model) to deal with transition probabilities.

Model inference has also been proposed in the context of distributed and
concurrent systems. _CSight_ Beschastnikh et al. (2014) infers a communicating
FSM from logs of vector-timestamped concurrent executions, by mining temporal
properties and refining the inferred model in a way similar to _Synoptic_.
_MSGMiner_ Kumar et al. (2011) is a framework for mining graph-based models
(called Message Sequence Graphs) of distributed systems; the nodes of this
graph correspond to Message Sequence Chart, whereas the edges are determined
using automata learning techniques. This work has been further extended Kumar
et al. (2012) to infer (symbolic) class level specifications. However, these
approaches require the availability of channel definitions, i.e., which events
are used to send and receive messages among components.

Liu and Dongen Liu et al. (2016) use a _divide-and-conquer_ strategy, similar
to the one in our _PRINS_ approach, to infer a system-level, hierarchical
process model (in the form of a Petri net with nested transitions) from the
logs of interleaved components, by leveraging the calling relation between the
methods of different components. This approach assumes the knowledge of the
caller and callee of each component methods; in our case, we do not have this
information and rely on the _leads-to_ relation among log entries, computed
from high-level architectural descriptions and information about the
communication events.

Nevertheless, all the aforementioned approaches cannot avoid scalability
issues due to the intrinsic computational complexity of inferring FSM-like
models; the minimal consistent FSM inference from logs is NP-complete Gold
(1967) and all the more practical approaches are approximation algorithms with
polynomial complexity.

One way to tackle the intrinsic scalability issue of (automata-based) model
inference is to rely on distributed computing models, such as MapReduce Dean
and Ghemawat (2008), by transforming the sequential model inference algorithms
into their corresponding distributed version. In the case of the _k-Tail_
algorithm, the main idea Wang et al. (2015) is to parallelize the algorithm by
dividing the traces (sequences of log messages) into several groups, and then
run an instance of the sequential algorithm on each of them. A more fine-
grained version Luo et al. (2017) parallelizes both the trace slicing and the
model synthesis steps. Being based on MapReduce, both approaches require to
encode the data to be exchanged between mappers and reducers in the form of
key-value pairs. This encoding, especially in the trace slicing step, is
application-specific; for instance, to correctly slice traces recorded by an
online shopping system, different event parameter values, such as user id,
order id, and item id, must be correctly identified and categorized from
individual messages beforehand. Notice that this is more challenging than just
identifying parameter values from free-formed messages, since different types
of parameters must be distinguished. Hence, MapReduce cannot be used in
contexts in which the system is treated as a black-box, with limited
information about the data recorded in the log entries. Furthermore, though
the approach can infer a FSM from large logs of over 100 million events, the
distributed model synthesis can be significantly slower for $k\geq 3$ (of _k-
Tail_), since the underlying algorithm is exponential in $k$.

Another way of taming scalability is to reduce the size of input logs by
sampling them from the entire set of collected logs using statistical analysis
and provide statistical guarantees on the inferred models. This is called
statistical log analysis and was first presented by Busany and Maoz (2016).
Its key idea is to iteratively sample new logs until the probability of adding
new system behaviors into the model inferred by sampled logs is less than a
given level of confidence threshold. While the idea of using statistical
analysis to address the scalability of model inference is promising, as
already noted by the authors, it is only applicable to sequential model
inference algorithms, where each log can be processed independently Busany and
Maoz (2016). _PRINS_ , on the other hand, is applicable to all model inference
algorithms as only the inference target is changed from systems to components.
Therefore, all model inference algorithms can benefit from using the divide-
and-conquer approach in _PRINS_.

##  7 Conclusion

In this paper, we addressed the scalability problem of inferring the model of
a component-based system from system logs, assuming that the only information
available about the system is represented by the logs. Our approach, called
_PRINS_ , first infers a model of each system component from the corresponding
logs; then, it merges the individual component models together taking into
account the flow of events across components, as reflected in the logs. Our
evaluation, performed on logs from nine datasets, has shown that _PRINS_ can
process large logs an order of magnitude faster than a publicly available and
well-known state-of-the-art technique without significantly compromising the
accuracy of inferred models. While there are some cases where _PRINS_ achieves
a moderately lower recall than the state-of-the-art, this happens when the
logs are inadequate for model inference in general, regardless of the
technique. Furthermore, we have proposed an easy way to detect such cases and
remedy the problem.

As part of future work, we plan to evaluate _PRINS_ on different datasets,
especially collected from real-world industrial applications, and to integrate
it with other model inference techniques. We also aim to assess the
effectiveness of the inferred models when applied to support software
engineering activities, such as test case generation.

## References

  * Aghajani et al. (2019) Aghajani E, Nagy C, Vega-Márquez OL, Linares-Vásquez M, Moreno L, Bavota G, Lanza M (2019) Software documentation issues unveiled. In: 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE), IEEE Press, Piscataway, NJ, USA, pp 1199–1210
  * Beschastnikh et al. (2011) Beschastnikh I, Brun Y, Schneider S, Sloan M, Ernst MD (2011) Leveraging existing instrumentation to automatically infer invariant-constrained models. In: Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering (ESEC/FSE 2011), ACM, New York, NY, USA, pp 267–277
  * Beschastnikh et al. (2014) Beschastnikh I, Brun Y, Ernst MD, Krishnamurthy A (2014) Inferring models of concurrent systems from logs of their behavior with CSight. In: Proceedings of the 36th International Conference on Software Engineering (ICSE 2014), ACM, New York, NY, USA, pp 468–479
  * Beschastnikh et al. (2015) Beschastnikh I, Brun Y, Abrahamson J, Ernst MD, Krishnamurthy A (2015) Using declarative specification to improve the understanding, extensibility, and comparison of model-inference algorithms. IEEE Trans Softw Eng 41(4):408–428
  * Biermann and Feldman (1972) Biermann AW, Feldman JA (1972) On the synthesis of finite-state machines from samples of their behavior. IEEE Transactions on Computers C-21(6):592–597, DOI 10.1109/TC.1972.5009015
  * Busany and Maoz (2016) Busany N, Maoz S (2016) Behavioral log analysis with statistical guarantees. In: 2016 IEEE/ACM 38th International Conference on Software Engineering (ICSE), pp 877–887, DOI 10.1145/2884781.2884805
  * Busany et al. (2019) Busany N, Maoz S, Yulazari Y (2019) Size and accuracy in model inference. In: 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE), IEEE Press, Piscataway, NJ, USA, pp 887–898, DOI 10.1109/ASE.2019.00087
  * Chandola et al. (2009) Chandola V, Banerjee A, Kumar V (2009) Anomaly detection: A survey. ACM Comput Surv 41(3), DOI 10.1145/1541880.1541882, URL https://doi.org/10.1145/1541880.1541882
  * Cheng and Krishnakumar (1993) Cheng K, Krishnakumar AS (1993) Automatic functional test generation using the extended finite state machine model. In: Proceedings of the 30th Design Automation Conference (DAC 1993), ACM, New York, NY, USA, pp 86–91
  * Clarke Jr et al. (2018) Clarke Jr EM, Grumberg O, Kroening D, Peled D, Veith H (2018) Model checking. MIT press, Cambridge, MA, USA
  * Cohen and Maoz (2015) Cohen H, Maoz S (2015) Have we seen enough traces? (t). In: 2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE), pp 93–103, DOI 10.1109/ASE.2015.62
  * Cook and Wolf (1998) Cook JE, Wolf AL (1998) Discovering models of software processes from event-based data. ACM Trans Softw Eng Methodol 7(3):215–249, DOI 10.1145/287000.287001
  * Damas et al. (2005) Damas C, Lambeau B, Dupont P, van Lamsweerde A (2005) Generating annotated behavior models from end-user scenarios. IEEE Transactions on Software Engineering 31(12):1056–1073, DOI 10.1109/TSE.2005.138
  * Dean and Ghemawat (2008) Dean J, Ghemawat S (2008) Mapreduce: Simplified data processing on large clusters. Commun ACM 51(1):107–113
  * El-Masri et al. (2020) El-Masri D, Petrillo F, Guéhéneuc YG, Hamou-Lhadj A, Bouziane A (2020) A systematic literature review on automated log abstraction techniques. Information and Software Technology 122:106276, DOI 10.1016/j.infsof.2020.106276
  * Emam and Miller (2018) Emam SS, Miller J (2018) Inferring extended probabilistic finite-state automaton models from software executions. ACM Trans Softw Eng Methodol 27(1), DOI 10.1145/3196883, URL https://doi.org/10.1145/3196883
  * Ernst et al. (2007) Ernst MD, Perkins JH, Guo PJ, McCamant S, Pacheco C, Tschantz MS, Xiao C (2007) The Daikon system for dynamic detection of likely invariants. Sci Comput Program 69(1):35–45
  * Fraser and Walkinshaw (2012) Fraser G, Walkinshaw N (2012) Behaviourally adequate software testing. In: 2012 IEEE Fifth International Conference on Software Testing, Verification and Validation, IEEE Press, Piscataway, NJ, USA, pp 300–309, DOI 10.1109/ICST.2012.110
  * Gold (1967) Gold EM (1967) Language identification in the limit. Information and Control 10(5):447–474
  * He et al. (2017) He P, Zhu J, Zheng Z, Lyu MR (2017) Drain: An online log parsing approach with fixed depth tree. In: 2017 IEEE International Conference on Web Services (ICWS), IEEE Press, Piscataway, NJ, USA, pp 33–40, DOI 10.1109/ICWS.2017.13
  * He et al. (2020) He S, Zhu J, He P, Lyu MR (2020) Loghub: A large collection of system log datasets towards automated log analytics. URL https://arxiv.org/abs/2008.06448
  * Heule and Verwer (2013) Heule MJ, Verwer S (2013) Software model synthesis using satisfiability solvers. Empirical Software Engineering 18(4):825–856, DOI 10.1007/s10664-012-9222-z
  * Hopcroft et al. (2006) Hopcroft JE, Motwani R, Ullman JD (2006) Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., USA
  * Kumar et al. (2011) Kumar S, Khoo SC, Roychoudhury A, Lo D (2011) Mining message sequence graphs. In: Proceedings of the 33rd International Conference on Software Engineering (ICSE 2011), ACM, New York, NY, USA, pp 91–100
  * Kumar et al. (2012) Kumar S, Khoo SC, Roychoudhury A, Lo D (2012) Inferring class level specifications for distributed systems. In: Proceedings of the 34th International Conference on Software Engineering (ICSE 2012), IEEE, Piscataway, NJ, USA, pp 914–924
  * Lang et al. (1998) Lang KJ, Pearlmutter BA, Price RA (1998) Results of the Abbadingo One DFA learning competition and a new evidence-driven state merging algorithm. In: Proceedings of the 4th International Colloquium on Grammatical Inference (ICGI 1998), Springer, Berlin, Heidelberg, LNCS, vol 1433, pp 1–12
  * Liu et al. (2016) Liu C, van Dongen B, Assy N, van der Aalst WMP (2016) Component behavior discovery from software execution data. In: Proceedings of the Symposium Series on Computational Intelligence (SSCI 2016), IEEE, Piscataway, NJ, USA, pp 1–8
  * Luo et al. (2017) Luo C, He F, Ghezzi C (2017) Inferring software behavioral models with mapreduce. Science of Computer Programming 145:13 – 36, DOI https://doi.org/10.1016/j.scico.2017.04.004, URL http://www.sciencedirect.com/science/article/pii/S0167642317300795
  * Mariani et al. (2017) Mariani L, Pezzè M, Santoro M (2017) Gk-tail+ an efficient approach to learn software models. IEEE Transactions on Software Engineering 43(8):715–738, DOI 10.1109/TSE.2016.2623623
  * Messaoudi et al. (2018) Messaoudi S, Panichella A, Bianculli D, Briand L, Sasnauskas R (2018) A search-based approach for accurate identification of log message formats. In: 2018 IEEE/ACM 26th International Conference on Program Comprehension (ICPC), IEEE Press, Piscataway, NJ, USA, pp 167–16710
  * Palmer and McAddis (2019) Palmer JD, McAddis N (2019) Documentation as a cross-cutting concern of software. In: Proceedings of the 37th ACM International Conference on the Design of Communication, Association for Computing Machinery, New York, NY, USA, SIGDOC ’19, DOI 10.1145/3328020.3353949, URL https://doi.org/10.1145/3328020.3353949
  * Polyvyanyy et al. (2008) Polyvyanyy A, Smirnov S, Weske M (2008) Process model abstraction: A slider approach. In: 2008 12th International IEEE Enterprise Distributed Object Computing Conference, pp 325–331, DOI 10.1109/EDOC.2008.17
  * Rios et al. (2020) Rios N, Mendes L, Cerdeiral C, Magalhães APF, Perez B, Correal D, Astudillo H, Seaman C, Izurieta C, Santos G, Oliveira Spínola R (2020) Hearing the voice of software practitioners on causes, effects, and practices to deal with documentation debt. In: Requirements Engineering: Foundation for Software Quality, Springer International Publishing, Cham, pp 55–70
  * Shin et al. (2022) Shin D, Bianculli D, Briand L (2022) PRINS replication package. DOI 10.6084/m9.figshare.12851030, URL https://doi.org/10.6084/m9.figshare.12851030
  * Varrette et al. (2014) Varrette S, Bouvry P, Cartiaux H, Georgatos F (2014) Management of an academic hpc cluster: The ul experience. In: Proc. of the 2014 Intl. Conf. on High Performance Computing & Simulation (HPCS 2014), IEEE, Bologna, Italy, pp 959–967
  * Walkinshaw (2018) Walkinshaw N (2018) mintframework. https://github.com/neilwalkinshaw/mintframework, accessed: 2020-03-05
  * Walkinshaw et al. (2010) Walkinshaw N, Bogdanov K, Damas C, Lambeau B, Dupont P (2010) A framework for the competitive evaluation of model inference techniques. In: Proceedings of the First International Workshop on Model Inference In Testing (MIIT 2010), ACM, New York, NY, USA, pp 1–9
  * Walkinshaw et al. (2013) Walkinshaw N, Lambeau B, Damas C, Bogdanov K, Dupont P (2013) Stamina: A competition to encourage the development and assessment of software model inference techniques. Empir Softw Eng 18(4):791–824
  * Walkinshaw et al. (2016) Walkinshaw N, Taylor R, Derrick J (2016) Inferring extended finite state machine models from software executions. Empirical Software Engineering 21(3):811–853, DOI 10.1007/s10664-015-9367-7, URL https://doi.org/10.1007/s10664-015-9367-7
  * Wang et al. (2015) Wang S, Lo D, Jiang L, Maoz S, Budi A (2015) Scalable parallelization of specification mining using distributed computing. In: Bird C, Menzies T, Zimmermann T (eds) The Art and Science of Analyzing Software Data, Morgan Kaufmann, Boston, pp 623 – 648, DOI https://doi.org/10.1016/B978-0-12-411519-4.00021-5, URL http://www.sciencedirect.com/science/article/pii/B9780124115194000215
  * Witten et al. (2016) Witten IH, Frank E, Hall MA, Pal CJ (2016) Data Mining: Practical Machine Learning Tools and Techniques, Fourth Edition. Morgan Kaufmann, San Francisco, CA, USA
  * Zhu et al. (2019) Zhu J, He S, Liu J, He P, Xie Q, Zheng Z, Lyu MR (2019) Tools and benchmarks for automated log parsing. In: Proceedings of the 41st International Conference on Software Engineering: Software Engineering in Practice, IEEE Press, Piscataway, NJ, USA, ICSE-SEIP ’10, pp 121–130, DOI 10.1109/ICSE-SEIP.2019.00021, URL https://doi.org/10.1109/ICSE-SEIP.2019.00021