计算机应用 ›› 2017, Vol. 37 ›› Issue (2): 574-580.DOI: 10.11772/j.issn.1001-9081.2017.02.0574

• 计算机软件技术 • 上一篇    下一篇

接口自动机的良构性检测算法及其实现

李雪, 朱嘉钢   

  1. 江南大学 物联网工程学院, 江苏 无锡 214122
  • 收稿日期:2016-07-22 修回日期:2016-08-28 出版日期:2017-02-10 发布日期:2017-02-11
  • 通讯作者: 李雪,jndx_axue@163.com
  • 作者简介:李雪(1990-),女,河南南阳人,硕士研究生,主要研究方向:软件工程、形式化方法;朱嘉钢(1957-),男,上海人,副教授,博士,主要研究方向:人工智能、模式识别、软件工程。
  • 基金资助:
    江苏省产学研项目(BY2013015-40)。

Well-formedness checking algorithm of interface automaton and its realization

LI Xue, ZHU Jiagang   

  1. College of IoT Engineering, Jiangnan University, Wuxi Jiangsu 214122, China
  • Received:2016-07-22 Revised:2016-08-28 Online:2017-02-10 Published:2017-02-11
  • Supported by:
    This work is supported by Industry-University-Research Project of Jiangsu Province (BY2013015-40).

摘要: 针对构件式系统中任一构件的非良构性会导致系统不能正常运行的问题,提出一种基于接口自动机(IA)来分析和检测构件良构性(well-formedness)的算法,并据此实现了一个构件良构性检测原型系统。该算法首先构造与接口自动机同构的可达图;其次,基于可达图通过深度优先遍历生成一条覆盖所有迁移的有序集;最后,根据该有序集检测在外界环境满足其输入假设的情况下,每个属于方法的活动到其对应返回活动的路径的自治无异常可达性,从而实现接口自动机的良构性检测。根据所提算法在Eclipse平台设计并实现了构件良构性检测原型系统T-CWFC,该系统通过JFLAP建立构件的接口自动机模型并构造其可达图,进而对接口自动机作良构性检测并输出相关检测信息。最后通过对一组构件的良构性检测实验验证了算法的有效性。

关键词: 接口自动机, 构件, 良构性, 最简运行

Abstract: To address the issue that the non-well-formed components in a component-based system may lead to the whole system working abnormally, an algorithm for checking the well-formedness of a component was proposed based on its Interface Automaton (IA) model, and a relevant prototype tool was developed. Firstly, the reachability graph isomorphic with the given IA was constructed. Secondly, an ordered set including all the transitions of the reachability graph relevant to the IA was obtained by depth-first-searching the reachability graph. Finally, the well-formedness check of a given IA was completed by checking whether each action belonging to a method in the IA could autonomously reach its return action without exception according to the ordered set under the condition that the external environment meets the input hypothesis. As a realization of the proposed algorithm, a relevant prototype tool was developed on Eclipse platform, namely T-CWFC (Tool for Component Well-Formedness Checking). The prototype tool can model the given component, set up its reachability graph, check its well-formedness and output check result message. The validity of the proposed algorithm was verified by running the tool on a set of components.

Key words: Interface Automaton (IA), component, well-formedness, the most simple run

中图分类号: