网构软件的资源自适应性的形式化分析与验证

针对基于构件的网构软件系统对环境资源变化的自适应性特征的可信分析与验证展开研究.具体工作包括:在网构软件的系统模型层次,使用带资源语义信息的接口自动机对软件构件的行为进行形式化建模,其包含了构件在完成特定功能的过程中对环境资源的使用特征;使用资源接口自动机网络来描述构件组装实体的组合行为;使用基于场景的UML顺序图模型来描述具有多功能的组合系统规约;分别研究了检验组合系统的所有行为是否都满足给定的资源约束以及检验指定的系统行为是否满足资源约束这两个具体问题:通过对资源自动机网络状态空间的分析,构造其相应的可达图,在此基础上给出了相应的检验资源可满足性、最小资源需求量以及检验指定功能合法性等算法.     

构件式实时系统建模与验证研究

在复杂的实时系统开发中使用构件式设计方法已成为目前软件开发领域中的研究热点,如何有效地验证实时软件的设计是否满足给定的时间需求并降低验证过程的复杂度,是实时计算领域中的主要挑战之一.文中对构件接口模型进行时间扩展,提出了时间接口模型,并将其用于构件接口交互行为的形式化建模.在接口自动机理论的的基础上进一步提出了时间接口自动机模型用于描述时间接口交互下构件的行为及组合方法,通过消除错误状态产生组合模型来约减构件时间接口自动机模型的积,并在约减的模型上进行性质检验,降低了分析复杂度,有效地应对状态空间爆炸问题.为了说明论文建议的方法,详细讨论了一个简单的、贯穿整篇论文的示例系统.     

构件化嵌入式软件设计模型非功能性质验证的工具实现

嵌入式软件的非功能性质是系统高可靠性的重要构成部分.传统的嵌入式软件可靠性保障技术主要关注于系统开发后期,缺乏有效工具对系统设计的非功能性质进行分析与验证.对基于接口自动机模型的构件化嵌入式软件设计验证原型工具T-CBESD(Tool for Component-based Embedded Software Designs)进行了资源及能耗等非功能性质验证功能的扩展设计与实现,包括:资源接口自动机和能耗接口自动机模型的输入输出接口设计、UML顺序图模型的预处理、带非功能语义信息的组合系统状态空间数据结构的设计、非实时资源使用性质与实时相关能量消耗特征验证算法的实现,以及一个通信构件组合系统的实例应用分析.     

数据库活动监控工具的接口自动机模型

使用接口自动机描述软件各模块的内、外部行为,依据接口自动机的构件组合方法来描述总体框架的运行机制,可清晰地展示出基于网络嗅探的数据库活动监控工具的多DBMS协议分析支持、分布式部署与协同工作等难点的解决。给出了该工具主要模块的内、外部行为和工具整体行为的接口自动机模型,通过实验,验证了基于该模型所实现工具的正确性和可用性。     

T-CBESD:一个构件化嵌入式软件设计模型验证工具

现代复杂嵌入式软件系统的高可靠性需要有效的基于模型的设计与分析技术.传统的嵌入式软件可靠性保障技术主要关注于系统开发后期.本文在Eclipse平台上设计并实现了一个基于接口自动机模型的构件化嵌入式软件设计的形式化验证原型工具T-CBESD(Tool for Component-Based Embedded Software Designs).工具直接使用UML顺序图模型作为系统规约,可以检验系统设计模型与场景式规约之间多种行为一致性问题;并使用消息事件的时间约束不等式,检验实时接口自动机网络与带时间约束的顺序图模型之间的实时行为一致性问题.工具设计与实现内容包括:输入输出接口、顺序图模型的预处理转换、状态空间数据结构设计、抽象验证算法的实现以及通信构件组合系统的实例应用分析.     

基于场景构件式实时软件设计的一致性检验

在复杂的实时软件系统中使用构件式设计方法,已成为目前软件工程中的研究热点.如何有效地验证实时软件的设计是否满足给定的时间规约,是实时计算领域中的主要挑战之一.通过在接口自动机模型中添加时间区间标记,来扩展其对实时系统接口行为的表达能力;使用实时接口自动机网络来描述实时软件系统的构件式设计模型;使用带布尔不等式时间约束的UML顺序图表示基于场景的需求规约,对系统设计阶段实时软件构件的动态行为进行形式化分析与检验.通过对实时接口自动机网络状态空间的分析,构造了其可兼容的整型状态等价类空间的可达图,并在此基础上给出了验证算法,以检验构件式实时软件系统的设计与带时间约束的场景式规约之间的一致性.     

基于接口自动机的Web应用验证

Web应用的快速发展及其一些异于传统程序的特点使Web应用的验证面临了新的挑战。使用接口自动机对Web应用的构件和构件组合进行行为建模,设计了接口自动机到模型检验器Spin程序的转换算法,然后利用Spin检验Web应用的性质,通过一个简单的网上银行示例说明了整个验证过程。     

基于MDE的AADL构件组合兼容的方法

实时嵌入式系统建模语言—体系结构分析与设计语言AADL是一种基于组件的半形式化建模语言,当AADL构件模型进行组合时,因为一些交互活动的序列不匹配从而导致构件组合行为不兼容,提出了一种基于模型驱动方法 MDE的AADL构件组合兼容方法。利用MDE异构模型转换框架将AADL模型转换至接口自动机IA,利用形式化方法验证IA的兼容性,使用IA Tool构建IA模型的构件兼容运行环境,将构造的环境映射到AADL组件,能够解决AADL构件组合的行为兼容性问题。     

基于场景规约的构件式系统设计分析与验证

使用接口自动机及接口自动机网络来描述构件式系统的行为设计模型,使用UML顺序图表示基于场景的需求规约,对系统设计阶段的构件交互行为的动态兼容性进行形式化分析和检验.通过对接口自动机网络状态空间的分析,给出了一系列算法以检验系统行为的存在一致性以及几种不同形式的强制一致性性质,包括前向强制一致性、逆向强制一致性以及双向强制一致性等.     

接口自动机--一种用于组件组合的形式系统

接口自动机是描述基于组件系统中组件及组件间交互行为的形式化工具。接口自动机在处理组件组合问题时所使用的“乐观方法”和博弈思想是区别于其它形式化工具的关键点。本文对接口自动机、时间接口自动机和资源接口及其中的博弈思想进行综述。在同其它形式化方法比较的基础上,指出了接口自动机的长处和局限。文中总结了接口自动机在理论上和实际中的意义并对其应用前景做了展望。     

A behavioral type system and its application in Ptolemy II

Interface automata [deH01] have been introduced as an interface theory [deH01a] capable of functioning as a behavioral type system. Behavioral type systems describe dynamic properties of components and their compositions. Like traditional (data) type systems, behavioral type systems can be used to check compatibility of components. In this paper, we use interface automata to devise a behavioral type system for Ptolemy II, leveraging the contravariant and optimistic properties of interface automata to achieve behavioral subtyping and polymorphism. Ptolemy II is a software framework supporting concurrent component composition according to diverse models of computation. In this paper, we focus on representing the communication protocols used in component communication within the behavioral type system. In building this type system, we identify two key limitations in interface automata formalisms; we overcome these limitations with two extensions, transient states and projection automata. In addition to static type checking, we also propose to extend the use of interface automata to the on-line reflection of component states and to run-time type checking, which enable dynamic component creation, morphing application structure, and admission control. We discuss the trade-offs in the design of behavioral type systems.Received September 2002Accepted in revised form November 2003 by M. Broy, G. Lüttgen and M. Mendler     

An I/O Automata-based Approach to Verify Component Compatibility: Application to the CyCab Car

An interesting formal approach to specify component interfaces is interface automata based approach, which is proposed by L. Alfaro and T. Henzinger. These formalisms have the ability to model both the input and output requirements of components system. In this paper, we propose a method to enrich interface automata by the semantics of actions in order to verify components interoperability at the levels of signatures, semantics, and protocol interactions of actions. These interfaces consist of a set of required and offered actions specified by Pre and Post conditions. The verification of the compatibility between interface automata reuse the L. Alfaro and T. Henzinger proposed algorithm and adapt it by taking into account the action semantics. Our approach is illustrated by a case study of the vehicle CyCab.     

构件交互模型与组合适配方法研究

构件交互操作与构件适配是基于构件的软件开发方法(CBD)中的关键问题。如何更有效地解决构件适配问题以提高软件的开发质量是一个永久的热点。而构件间的交互操作又是解决构件适配问题的关键所在。在已有的研究成果的基础上、基于自动机理论提出了一种构件交互模型。它将构件接口根据所提供的服务不同分为调用接口和使用接口,使得对构件间的交互操作描述的更为准确。在此基础上,对构件组合适配方法进行了分析。     

Generalized interface automata with multicast synchronization

Interface automata are one of the prominent formalisms for specifying interface behaviors of componentbased systems. However, only one-to-one communication is allowed in the composition of interface automata. This paper presents multicast interface automata which generalize the classic interface automata and accommodate multicast communication mechanism. The multicast interface automata endorse both bottom-up and top-down design methodologies. Theoretical results on compatibility and refinement are established for incremental design and independent implementability.     

基于二维元胞自动机的图案设计方法研究

研究者们常常根据元胞自动机的演化机制,模拟人类的社会现象、自然界中的物质变化等。元胞自动机在绘制图案的应用研究中,通常是用于对自然界、人体器官等实体仿真。而文中则是根据元胞自动机演化的多样性和随机性,提出了一种基于二维元胞自动机的图案设计方法。该方法可以根据算法的描述,结合参数的可控、规则的研究和元胞的不同大小,并最终在VC＋＋6．0上编程实现。实验结果显示,可以绘制出更加美妙、精确的图案,这些图案可以用来装饰壁毯、地毯、窗帘等。     

基于Mealy机的多主体演化博弈仿真研究

针对经济学研究中演化博弈建模表示与实现问题,提出构建一种基于Mealy有限自动机的经济学多主体博弈仿真系统.该系统用Mealy自限自动机表示组织和个人行为,采用面向对象的可视化界面控制技术构造有限自动机,利用人工智能中的语言翻译技术把有限自动机翻译成线程,并用并发调度和串行调度的方式对线程进行处理.在博弈过程中采用遗传算法产生新的有限自动机.用一个三人重复囚徒困境演化博弈实例,输入状态转换图,给出博弈均衡的结果.仿真实例表明系统方法是有效的.