Reverse Engineering State Machine Hierarchies by Grammar Inference (REGI)

通过语法推理 (REGI) 进行逆向工程状态机层次结构

• 批准号: EP/F065825/1
• 负责人: Kirill Bogdanov
• 金额: $ 40.16万
• 依托单位: University of Sheffield
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2009
• 资助国家: 英国
• 起止时间: 2009 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FF065825%2F1
• 关键词: Reverse; Engineering; State; Machine; Hierarchies

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.

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

项目成果

Effectively Incorporating Expert Knowledge in Automated Software Remodularisation

有效地将专家知识融入自动化软件重构中

• DOI: 10.1109/tse.2017.2786222
• 发表时间: 2018
• 期刊: IEEE Transactions on Software Engineering
• 影响因子: 7.4
• 作者: Hall M

Synapse

突触

• DOI: 10.1145/2633448.2633457
• 发表时间: 2014
• 作者: Lamela Seijas P

An identification of program factors that impact crossover performance in evolutionary test input generation for the branch coverage of C programs

识别影响 C 程序分支覆盖的进化测试输入生成中交叉性能的程序因素

• DOI: 10.1016/j.infsof.2012.03.010
• 发表时间: 2013
• 期刊: Information and Software Technology
• 影响因子: 3.9
• 作者: McMinn P

Superstate identification for state machines using search-based clustering

使用基于搜索的聚类对状态机进行超级状态识别

• DOI: 10.1145/1830483.1830736
• 发表时间: 2010
• 作者: Hall M

Expression analysis and regulation of GLI and its correlation with stemness and metabolic alteration in human brain tumor.

GLI在人脑肿瘤中的表达分析和调控及其与干性和代谢改变的相关性。

• DOI: 10.1007/978-3-319-30936-1_10
• 发表时间: 2023
• 期刊: 3 Biotech
• 影响因子: 2.8
• 作者: Agrawal K