gLTSdiff: A Generalized Framework for Structural Comparison of Software Behavior
Dennis Hendriks, Wytse Oortwijn · 2023
State machine models, such as labeled transition systems and (extended) finite automata, can be structurally compared, for instance to find potential behavioral regressions in new software versions, to evaluate the accuracy of different model learning algorithms, and to fingerprint software for security applications. The state-of-the-art LTSDiff structural comparison algorithm has limited assumptions, making it broadly applicable. However, representation-specific information is not taken into account, requiring adaptations to prevent sub-optimal or even invalid results. We propose gLTSdiff, which generalizes and extends LTSDiff, allowing a wide range of state machine models to be compared, by recursively comparing the structure of state and transition labels. Additional challenges that we faced while applying LTSDiff in industrial practice are also addressed by gLTSdiff, as it rewrites undesired difference patterns, supports comparison of any number of input models, and allows for an effort/quality trade-off. gLTSdiff is implemented as an extensible open source library for structural model comparison. Using multiple large-scale industrial and open source case studies, we evaluate both its practical value and its various improvements.