To facilitate the testing and maintenance of software systems, researchers have generated behavioral models in the form of finite-state automata from software execution traces. Even though a finite-state automaton (FSA) is a common dynamic model inference process, it suffers from low accuracy and undecidability, and it often does not provide a complete view of the software’s behavior. To address the same, additional parameters like constraints have been incorporated in the FSA. Further research has been done to build a probabilistic FSA with a transitional probability for each event to effectively reconstruct the certain behavior of the actual software. The authors here present a probabilistic model, ReHMM, to infer FSA and additionally address the issue of missing transition probabilities in the state machine. ReHMM employs both hidden Markov models (HMMs) and reinforcement learning to infer an improved finite-state model with capabilities to estimate the transition probabilities as part of the inference algorithm.

As a first step, the event traces of the software are converted to training sets based on the data attributes of the events, which are then used to learn a set of HMM classifiers to predict the next event to be called in the state model. This generates the initial tree-shaped automaton. Initially, authors assign the same probability to all the events to be executed, irrespective of the current state. The authors then develop a heuristic for a reward function, based on Levenshtein distance, to calculate the degree of similarity between events based on the amount of state-level changes incurred after execution. For example, execution of an event with parameter values that are highly different from the previously executed events can lead to major changes in state. The reward function is further used to estimate the transition probabilities for the events. Finally, based on the reward function, the authors merge similar states using the algorithm presented in [1,2].

To evaluate the accuracy of ReHMM, the authors calculate the binary classification rate (BCR) for the finite-state models extracted using ReHMM and other prevalent approaches. The BCR of ReHMM is 0.7, which is fairly acceptable, and the comparison study shows that ReHMM outperforms the other models in improving the accuracy of the inferred state model. Hence, this paper would be of interest to researchers trying to reverse engineer abstract behavior from the execution of software.