Proceedings - Working Conference on Reverse Engineering · 2007 · 77 citations · 19 references
ComputingComputer ScienceFormal MethodsKnowledge RepresentationSoftware EngineeringAbstract Syntax TreesFinite State Machine ModelingModel-driven DevelopmentModel-driven Software EngineeringSoftware TestingSpecification LanguagesAbstract MachinesAbstract State MachinesFormal Grammar InferenceGrammar InferenceSoftware Development MethodologyState Machine ModelsState MachinesState Models
Finite state machine-derived specifications such as X-machines, extended finite state machines and abstract state machines, are an established means to model software behaviour. They allow for comprehensive testing of an implementation in terms of its intended behaviour. In practice however they are rarely generated and maintained during software development, hence their benefits can rarely be exploited. We address this problem by using an interactive grammar inference technique to infer the underlying state machine representation of an existing software system. The approach is interactive because it generates queries to the user as it constructs a hypothesis machine, which can be interpreted as system tests. This paper describes (1) how an existing grammar inference technique (QSM) can be used to reverse-engineer state-based models of software from execution traces at a developer-defined level of abstraction and (2) how the QSM technique can be improved for a better balance between the number of tests it proposes and the accuracy of the machine it derives. The technique has been implemented, which has enabled us to present a small case study of its use with respect to a real software system, along with some preliminary performance results.
19
Introduction to automata theory, languages, and computation
Computer Languages · 1980 · 6.9K citations
Language identification in the limit
Eric Gold · Information and Control · 1967 · 3.6K citations
Learning regular sets from queries and counterexamples
Dana Angluin · Information and Computation · 1987 · 2.1K citations