时间自动机与网络协议验证

随着网络协议复杂性的增大，其自身的潜在错误变得更加重要。使用形式化的方法来描述和验证网络协议可以发现其中的潜在错误。时间自动机是形式化方法的一种，可以很好地应用于网络协议验证中。目前基于时间自动机已经开发出了多种自动验证工具。文章介绍了网络协议验证的几种方法，并以KRONOS验证FDDI协议为例说明了用时间自动机验证协议的方法。     

时间自动机模型验证的研究进展

基于时间自动机的模型验证是一种形式化的实时并发系统时间性质验证技术,重大软件对时间行为、时序关系的高可靠性要求,不断刺激时间自动机模型验证技术的发展.介绍了时间自动机理论、模型验证算法及工具,对该领域的研究进展做了综述,指出了时间自动机模型验证存在的问题和研究方向.     

基于时间自动机的实时系统建模及验证

实时系统必须在一个事先定义好的时间限制内对来自外部或内部的事件进行响应,如何有效验证实时模型的正确性和安全性是一个难点.文章通过多个时间自动机来模拟实时系统中的各个对象,并用UPPAAL对模型进行验证,减少了模型验证的状态搜索空间,为实时嵌入式系统开发和验证提供了一种可行、安全的控制机制.实验结果显示了系统的有效性.     

基于马尔可夫模型的多agent自适应在线验证

用于领域中业务关键型的自适应系统(self-adaptive system,SAS)需要遵从严格的质量要求,在多agent自适应系统运行过程中需要根据动态环境与需求实现自适应调整。针对上述问题,提出了一种基于马尔可夫的多agent自适应在线验证方法。首先将多agent系统中环境影响因素转换为概率形式,然后将系统形式化为马尔可夫模型,最后通过模型检查的方式进行在线验证,使系统通过验证结果对自身进行调控。通过现实的智能无人停车场案例进行了实验,论述了方法的使用流程以及验证效果。实验结果表明,该方法适用于具有多agent的自适应系统,并能够在系统出现故障情况下及时进行调控,相比原始系统的稳定性有了较大的改善。     

基于最佳中继选择的异构多媒体自适应协作分集算法

本文提出一种自适应协作分集方案,以保证异构多媒体业务中主用户传输的服务质量(QoS),并改善次级用户的数据传输性能。采用基于功率控制的系统模型,使得主用户的平均信道增益相对稳定,并且能够在次用户中进行估计,可以节省在反馈信道上的资源。根据次级用户传输过程中的中断概率提出次级中断概率的闭式表达式 ,在满足主用户传输过程中所需要的中断概率约束的条件下,针对主用户和次用户的协作性和瑞利衰落信道的适应性提出了最佳中继选择的自适应协作分集,尽可能地次级中断概率,并获得的分集增益。实验仿真结果表明,该算法可以减少次级用户的中断概率并提高频谱效率,有助于提升次级用户的数据传输性能。     

混杂系统的扩展时间自动机模型及验证研究

混杂系统复杂度高且涉及领域广,没有通用的方法来解决分析、设计等问题。为解决一类工业控制混杂系统的建模和验证问题,对时间自动机进行了语义扩展,使其含有连续变量以及映射在其上的约束,使用扩展后的时间自动机对此类混杂系统进行建模,采用验证工具UPPAAL进行模型分析模拟,并使用简化的CTL对系统需求规范进行验证。具体实例研究表明,该方法对于分析设计一类混杂系统具有可行性和有效性。     

基于时间自动机的AADL端到端流规约验证方法

体系结构分析及设计语言(AADL)作为一种标准且直观的实时系统分析与设计工具,可以为系统设计、分析、验证、自动代码生成等关键环节提供统一的抽象表示。然而,AADL模型采用仿真的验证方法无法得到精确的端到端延迟验证结果,尤其是对于资源动态分配的实时系统。为解决结果不精确的问题,可结合基于系统有穷状态空间遍历的模型检验方法。首先,将实时系统AADL模型转换为时间自动机(TA)模型,以TA为理论体系进行模型检验。其次,基于反应链的需求分类定义端到端延迟需求表达模式。最后,给出对应需求模式的观察者模型,与系统模型并行组合,优化模型验证的时空资源消耗。     

运行时验证技术的研究进展

运行时验证是一种轻量级的验证方法,通过实时地监测系统的行为,验证系统的正确性,及时发现冲突,并发出警告或作出反应。运行时验证技术已经得到了越来越多的应用,以确保软件系统的正确性。总结了近年来运行时验证技术的研究进展,首先介绍了运行时验证的概念、原理和分类,接着深入分析了现有的几种解决方案,并对该领域中的研究热点进行了深入探讨,最后分析了运行时验证技术面临的主要挑战,并对未来该领域的研究方向进行了展望。     

基于时间自动机的物联网服务建模和验证

物联网服务的建模和验证是当前物联网服务提供中的一个重要问题.文中将物联网服务的行为建模为其与相关环境实体的交互,并引入环境实体以刻画物理世界各种物体的属性和行为,从而将物联网服务能力建模为它能够导致的环境实体发生的期望变化.文中以时间自动机为建模工具,分别为将要监测和要控制的物理环境实体以及不同种类的物联网服务独立建模...     

基于证据自动机的软件回归验证

为了在多版本程序验证中利用邻近版本之间的共享信息,提取并重用之前版本证据自动机中的循环不变式,提出基于证据自动机的软件回归验证。首先通过证据预处理生成适用于新版程序的证据文件,然后在辅助不变式增强的k-归纳方法的基础上实现了检验新证据文件及验证新版程序的回归验证过程,最后通过对比实验比较了不使用不变式信息的直接验证与结合或不结合数据流分析的三种回归验证的验证性能。与直接验证相比,不结合与结合数据流分析的回归验证的验证耗时分别减少了49%与75%,而内存消耗分别减少了18%与50%。实验结果表明,当程序满足其验证属性时,基于证据自动机的回归验证能极大地提高验证效率,而将证据自动机与数据流分析相结合的验证方式能得到更好的验证效果。     

基于Yices对时间自动机的有界模型检测

为了避免在有界模型检测过程中对变量进行布尔编码以及对时间自动机模型中的时钟进行预处理,给出一个利用SMT(satisfiability modulo theories)工具进行的对时间自动机进行有界模型检测的方法.该方法将时间自动机模型直接转换成SMT工具可识别的逻辑公式,利用SMT工具可求解包含有整数型和实数型变量逻辑公式的能力来进行模型检测.实验结果表明,对于某些可达性性质的验证,该方法的效率有一定的优势.     

基于概率验证的移动会议方案

基于移动网络的会议系统,着重于共享密钥的建立、分发与更新,对会议参与者的恶意或虚假消息,以往的方案不能阻止。提出了一种基于概率验证的方法,将其应用于移动会议的设计,可以有效地降低方案运行中的垃圾信息。     

基于时间自动机的测试用例自动生成及执行方法

为了实现对时间自动机模型的测试,采用符号状态拆分算法对时间自动机的状态空间进行等价划分,以得到最简稳定符号状态转移图,并将其中的抽象时间延迟转移替换为时间延迟变量;针对系统中每个时间自动机建立各自的符号状态转移图,再采用基于符号迁移系统的测试方法分别生成相应的转移动作序列;最后通过对这些序列进行组合产生系统的测试用例,为了执行测试用例,利用TTCN-3的多PTC并发执行能力来实施测试.     

Formal verification of multitasking applications based on timed automata model

The aim of this paper is to show, how a multitasking application running under a real-time operating system compliant with an OSEK/VDX standard can be modeled by timed automata. The application under consideration consists of several non-preemptive tasks and interrupt service routines that can be synchronized by events. A model checking tool is used to verify time and logical properties of the proposed model. Use of this methodology is demonstrated on an automated gearbox case study and the result of the worst-case response time verification is compared with the classical method based on the time-demand analysis. It is shown that the model-checking approach provides less pessimistic results due to a more detailed model and exhaustive state-space exploration.

Case study on distributed and fault tolerant system modeling based on timed automata

This article presents the modeling of a distributed fault-tolerant real-time application by timed automata. The application under consideration consists of several processors communicating via a Controller Area Network (CAN); each processor executes an application that consists of fault-tolerant tasks running on top of an operating system (e.g. OSEK/VDX compliant) and using inter-task synchronization primitives. For such a system, a model checking tool (e.g. UPPAAL) can be used to verify the complex time and logical properties formalized as safety or bounded liveness properties (e.g. end-to-end response time considering an occurrence of a fault). The proposed model reduces the size of the state-space by sharing clocks measuring the execution time of the tasks.     

基于JADE平台的MAS通信协议封装研究与设计

针对多Agent系统中异构Agent通信格式的规范问题,提出一个基于XML的多Agent通解决方案.该方案利用XML技术的优势,通过对Agent消息的封装处理,能够使各异构Agent更好地理解和交换消息,同时在JADE平台下开发了一个通信原型,为异构Agent通信格式的规范问题的解决,提供了一种技术途径.