Reverse Engineering State Machine Hierarchies by Grammar Inference (REGI)

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

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.