Reverse Engineering State Machine Hierarchies by Grammar Inference (REGI)

软件系统弥漫在现代生活中；它们控制着一切，从电传飞机和金融转账系统，到汽车的ABS制动系统和微波烹饪模式。公认的事实是，随着软件系统的发展和需求的变化，它们变得越来越复杂和难以维护。不同的开发人员进行更改(有时相互冲突)来解决不同的错误或添加不同的功能，不久之后系统的原始设计就会被忽略，不可能准确地理解系统是如何运行的。解决这个问题的一种方法是保留一个高级设计文档，该文档准确地指定了系统应该如何运行。与实际软件本身一起开发这种规范的一个主要好处是，存在强大的测试和验证技术，可以用来确定实际系统是否符合规范。然而，有一个主要问题阻碍了此类规范的常规使用：随着软件系统的发展，将它们与代码分开生成和维护往往既乏味又耗时。通过这个项目，我们将产生一种技术，通过自动生成规范的过程来解决上述问题。给定一个没有规范(或只有部分规范)的系统，我们的技术将通过运行系统和查看其静态结构来分析和探测系统。它将生成一份完整的文档，将系统的行为指定为状态机的集合。通常，根据感兴趣的行为方面，以比其他方面更详细的级别显示某些方面是有用的(例如，对于金融系统，开发人员可能对次贷管理的细节而不是交易处理系统感兴趣)。因此，生成的状态机将以层次结构的形式呈现。设计一种实用的技术来自动对这些规范进行逆向工程是具有挑战性的；所讨论的系统需要进行适当的采样，以识别相关行为，并且最终的规范必须是这些样本的有效概括。我们如何确定可以用作生成规范的基础的样本集(S)？我们如何从这组样本中构建系统的准确规范？这项工作将研究的一个关键实现是，在语法推理领域出现了与这些相同的挑战，其中的挑战是从目标语言的句子样本构建语法(可以由状态机表示)。语法推理是一个非常成熟的领域，有许多非常强大的技术，但从来没有与软件系统中的反向工程规范这一类似问题联系在一起。本文将探索反向工程和语法推理这两个领域之间的关系，并将在现有技术的基础上产生一套方法，这些方法结合在一起将产生一种实用的技术，从而生成完整而准确的软件系统状态机层次结构。

Software systems pervade modern life; they control everything from fly-by-wire aircraft and financial transfer systems to ABS breaking systems in cars and cooking modes in microwaves. It is an accepted fact that, as software systems evolve and their requirements change, they become increasingly complex and difficult to maintain. Different developers carry out (sometimes conflicting) changes to address different bugs or add different features, and before long the original design of the system is neglected and it becomes impossible to understand exactly how the system operates.One way around this problem is to keep a high-level design document that specifies exactly how the system is supposed to behave. A major benefit of developing such specifications along with the actual software itself is the fact that powerful testing and verification techniques exist that can be used to determine whether the actual system conforms to the specification. However, one major problem hampers the routine use of such specifications: as the software system evolves, they often tedious and time-consuming to generate and maintain separately from the code. With this project we will produce a technique that addresses the above problem by automating the process of generating a specification. Given a system that has no specification (or only a partial one), our technique will analyse and probe the system by both running it and looking at its static structure. It will produce a complete document specifying the behaviour of the system as a collection of state machines. Often, depending on the facet of behaviour that is of interest, it is useful to display certain aspects at a greater level of detail than others (for a financial system for example, the developer might be interested in details sub-prime loan management and not the transaction processing system). For this reason, state machines that are generated will be presented as a hierarchy. Devising a practical technique to automatically reverse engineer such specifications is challenging; the system in question needs to be suitably sampled to identify relevant behaviour, and the final specification will have to be a valid generalisation of these samples. How do we identify the set(s) of samples that can be used as a basis for generating the specification? How do we go about building an accurate specification of the system from this set of samples? One key realisation that will be investigated in this work is the fact that identical challenges to these arise in the field of grammar inference, where the challenge is to build a grammar (which can be represented by a state machine) from a sample of sentences in the target language. Grammar inference is a very mature field, with many very powerful techniques, but has never been linked to the similar problem of reverse-engineering specifications from software systems.This work will explore the relationship between the two fields of reverse-engineering and grammar inference, and will produce a set of approaches based on and extending existing techniques that, when combined, will produce a practical technique that generates complete and accurate hierarchy of state machines of a software system.