Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Inferring extended probabilistic finite-state automaton models from software executions
Emam S., Miller J. ACM Transactions on Software Engineering and Methodology27 (1):1-39,2018.Type:Article
Date Reviewed: Oct 25 2018

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.

Reviewer:  Partha Pratim Das Review #: CR146296 (1902-0033)
1) Walkinshaw, N.; Taylor, R.; Derrick, J. Inferring extended finite state machine models from software executions. In Proceedings of the 20th Working Conference on Reverse Engineering IEEE, 2013, 301–310.
2) Lang, K. J.; Pearlmutter, B. A.; Price, R. A. Results of the Abbadingo one DFA learning competition and a new evidence-driven state merging algorithm. In: Grammatical inference (LNCS 1433). 1-12, Springer, 1998.
Bookmark and Share
 
Formal Methods (D.2.4 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Formal Methods": Date
On a method of multiprogramming
Feijen W., van Gasteren A., Springer-Verlag New York, Inc., New York, NY, 1999. Type: Book (9780387988702)
May 1 2000
Computer-Aided reasoning: ACL2 case studies
Kaufmann M. (ed), Manolios P. (ed), Moore J. Kluwer Academic Publishers, Norwell, MA,2000. Type: Divisible Book
Jul 2 2002
Architecting families of software systems with process algebras
Bernardo M., Ciancarini P., Donatiello L. ACM Transactions on Software Engineering and Methodology 11(4): 386-426, 2002. Type: Article
Mar 10 2003
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy