基于模型的自适应方法综述

自适应为管理现代软件系统的复杂性提供了有效的解决方案,被设计为自适应系统的软件能够持续的演化以应对环境中的不确定性.在现有的研究工作中,基于模型的自适应方法是一类广泛使用的方法,它将模型驱动工程技术的应用从设计时扩展到运行时以支持自适应能力的实现.通过利用软件模型对运行时丰富和不确定的信息进行管理,这类方法避免了将自适应逻辑与程序语言交织带来的复杂性,从而简化了自适应系统的开发.本文对近些年来国内外学者在该研究领域取得的成果进行了系统总结.首先,给出了六个研究问题,包括相关工作常用的需求模型、结构模型、行为模型、环境模型、模型与模型或模型与系统间的同步方式、自适应规划算法等;接着,依次总结了相关工作在这六个研究问题上的已有研究成果;最后,对未来研究可能面临的挑战进行了展望.     

基于符号化模型检测的对弈必胜策略验证

在对弈的研究中,验证对弈双方是否存在必胜策略的问题一直没能很好地解决,因为这涉及到超大规模的状态空间搜索。而随着符号化模型检测技术的发展,大规模系统的验证成为了可能。给出了使用符号化模型检测来验证对弈必胜策略的一般方法,并给出了一个井字棋必胜策略验证的实例。     

模型检验综述

在软硬件验证里,模型检验是一个重要手段,至今它已经形成一个庞大的方法论体系。现在我们把模型检验内容从标准方法、抽象解释方法、综合方法3个范畴加以介绍,旨在形成人们对模型检验总的印象,从而全面理解和掌握模型检验各个方法的精神实质和具体情况,有助于将这些方法运用到实际软硬件验证中并从中受到启发,以便进一步发展模型检验理论或开发模型检验新的方法和工具。     

基于LSC的模型检验研究

LSC是一种表达能力很强的顺序图建模语言,模型检验技术是验证软件模型正确性的重要方法,提出了一个对LSC模型进行模型检验的方法,并实现了相关支持工具。首先分析了LSC语言,然后基于其语义提出了生成LSC等价状态模型的方法,进而对生成的状态模型进行模型检验;最后进行了实例研究,利用给出的实现工具检验了用CTL描述的验证性质。     

基于模型的复杂系统任务保证研究综述

任务保证是国外航天领域为确保复杂系统在任务周期内的安全、可靠而提出的一种工作方式。随着基于模型的系统工程技术近年来的迅猛发展,将其与任务保证相结合而形成的基于模型的任务保证概念开始得到广泛的应用和认可。这为复杂系统在安全性、可靠性工作方法上的进一步发展提供了有利条件。介绍了基于模型的任务保证概念,并对其所涉及的安全/保证案例、基于模型的系统工程、目标结构表示等关键要素,以及其目前在复杂系统设计中的典型应用进行了阐述。对基于模型的任务保证在未来的发展方向进行了展望。为基于模型的任务保证在复杂系统中的应用提供了理论参考。     

基于随机时间自动机和统计模型检验技术的无线传感网络协议建模与分析

近年来,传感器技术得到了长足而有效的提升,无线传感网络(WSN)以其开放、动态的特征获得了极大的关注,并成为了互联网计算的一个重要组成.WSN系统行为复杂,经常面临信息丢失、节点动态变化等不确定因素,且网络中的节点一旦部署将很难更改、维护.因此,为了保证相关应用的正常工作,在系统设计阶段对WSN中的底层协议进行质量保障就成为了一项非常重要的研究问题.系统设计人员不仅需要保证协议功能上的正确性,还应该评估协议在目标工作环境下的性能,以保证其可以胜任相应的工作需求.针对以上问题,本文提出了一种基于随机时间自动机和统计模型检验技术的WSN协议建模、分析和评估途径.在建模阶段,首先将采用时间自动机对协议在理想环境下的基本业务流程进行建模.考虑到WSN系统实际工作中会遇到的各种不确定性因素,将用带权分枝来对模型进行扩展,生成协议的随机时间自动机.在验证阶段,首先采用经典模型检验技术,在理想时间自动机上检验相关功能性质,保证协议工作逻辑的正确性.为评估协议在不同条件下的具体性能,则在随机时间自动机上用统计模型检验技术对其进行数值分析,以进行参数配置、性能预测、协议比较等工作.为展示该途径的可用性及其技术细节,本文对两种著名的WSN时间同步协议,TPSN和FTSP分别进行了完整的建模与评估.     

基于线性带权值的广义表的模型检验方法

提出了一个线性带权值的广义表（Linear Weighted Generalized List,LWGL）模型,同时给出了LWGL加法和乘法、析取和合取运算规则,实现了基于LWGL的高层次模型检验方法。实验结果表明LWGL模型对高层次模型检验是有效的。     

ETL的符号化模型检验

为使符号化模型检验技术适用于全部ω-正规性质,研究了ETL(extended temporal logic)的符号化模型检验方法.首先,扩展了LTL(linear temporal logic)的Tableau方法,给出了ETL的Tableau构造方法,进而给出了该方法基于BDD(binary decision diagram)的符号化实现.同时,在NuSMV的基础上实现了支持ETL符号化验证的模型检验工具ENuSMV.该工具允许用户自定义时序连接子,从而可以检验全部ω-正规性质.实验结果表明,ETL性质能够被高效地采用符号化技术加以检验.     

基于模型的软件测试综述

随着面向对象软件开发技术的广泛应用和软件测试自动化的要求,特别是基于UML的软件开发技术的逐渐普及,基于模型的软件测试逐渐得到了软件开发人员和软件测试人员的认可和接受。针对被测试软件的不同特征和不同测试目的,已经提出了多种测试模型。本文详细阐述了基于模型的软件测试研究现状和应用现状,并对测试中使用的不同模型进行了比较,着重介绍了状态机模型、UML模型和马尔可夫链模型。最后提出了未来的研究方向。     

密码协议的符号模型检测及分析

对密码协议模型检测的方法作了理论上的研究,并用SMV检测工具给出了一个实际分析的例子。结果表明,利用符号模型检测方法分析并发现密码协议重放攻击的漏洞是一种行之有效的方法。     

基于吴方法的符号模型检验

模型检验技术广泛应用于验证并发系统的性质。它的瓶颈一直是内存爆炸问题,将BDD技术引入到模型检验中的方法能有效地缓和状态组合爆炸问题。然而,随着系统规模的增大,BDD的大小仍呈指数增长。吴方法是一种处理多项式的符号计算方法,能有效地求解代数方程组并成功地应用于几何定理机器证明。给出应用吴方法计算表示Kripke结构和CTL公式的多项式的特征列的方法,从而实现对较大规模的系统性质的验证,进一步缓和状态组合爆炸问题。     

Symbolic model checking APSL

Property specification language (PSL) is a specification language which has been accepted as an industrial standard. In PSL, SEREs are used as additional formula constructs. In this paper, we present a variant of PSL, namely APSL, which replaces SEREs with finite automata. APSL and PSL are of the exactly same expressiveness. Then, we extend the LTL symbolic model checking algorithm to that of APSL, and then present a tableau based APSL verification technique, which can be easily implemented via the BDD based symbolic approach. Moreover, we implement an extension of NuSMV, and this adapted version supports symbolic model checking of APSL. Experimental results show that this variant of PSL can be efficiently verified. Henceforth, symbolic model checking PSL can be carried out by a transformation from PSL to APSL and symbolic model checking APSL.     

Verifying the summit bus converter protocols with symbolic model checking

We report on our investigation of a new verification tool, the Symbolic Model Verifier (SMV), created at Carnegie Mellon University. We have successfully, employed this tool to detect deadlock in an industrial design, namely, Hewlett-Packard's Summit bus converter chips. In addition to locating a known deadlock in the original chip design and checking its solution, we successfully detected other previously unknown defects in the design. In our experiments, we were able to verify properties on finite-state models of the circuit with 150 to 200 state variables in a matter of minutes.     

可能性测度下的CTL符号化模型检测

随着系统复杂性的增加,系统中的不确定信息亟待处理,状态爆炸问题也越来越严峻,现有的模型检测技术已不能完全适用于复杂系统的验证。 对可能性测度下CTL符号化模型检测进行了研究。首先用多终端二值决策图和布尔公式分别描述系统模型和待验证性质,然后再对系统模型进行归一化和简化,最后利用不动点计算完成系统验证。该研究是对可能性测度下的模型检测技术和符号化模型检测技术的整合,不但能处理系统的不确定信息,而且保持了符号化模型检测对计算时空要求低的优点,对于复杂系统模型检测具有重要意义。     

动态环境下基于概率模型检测的路径规划方法

提出了一种动态复杂环境下采用概率模型检测技术进行路径规划的新方法。考虑到实际应用中机器人其移动行为总是受到外界因素的影响,将机器人移动行为看作一个不确定事件,提取环境中的影响因素,构建马尔可夫决策过程模型。采用时态逻辑语言描述机器人目标任务,表达复杂多样的需求行为。运用工具PRISM验证属性,得到满足任务需求的全局优化路径。另外,在全局路径的基础上提出了一种动态避障策略,实现避障局部规划的同时尽量保证机器人最大概率完成任务。通过理论和仿真实验结果证明该方法的正确性和有效性。     

基于模型检测的硬件木马检测技术研究

硬件木马对原始电路的恶意篡改,已成为集成电路面临的核心安全威胁.为了保障集成电路的安全可信,研究人员提出了诸多硬件木马检测方法.其中,模型检测作为一种形式化验证方法,在设计阶段可有效检测出硬件木马.首先,阐述了模型检测的工作原理和应用流程;其次,介绍了基于模型检测的硬件木马检测技术的研究进展;最后,指出了当前该技术所面...     

模糊计算树逻辑的符号模型检测

对含有模糊不确定性信息的系统进行模型检测时,状态空间爆炸问题成为了亟待解决的主要问题.将形式化的系统模型用拟布尔公式表示,用多终端二叉决策图来对拟布尔公式进行存储.对模糊计算树逻辑的不动点语义给出了解释和证明,然后给出模糊计算树逻辑的符号化模型检测算法,最后通过一个实例验证算法的正确性.该算法可有效缓解对模糊模型检测验证时的状态空间爆炸问题,并扩展了模型检测的应用范围.     

Scalable distributed on-the-fly symbolic model checking

This paper presents a scalable method for parallel symbolic on-the-fly model checking in a distributed memory environment. Our method combines a scheme for on-the-fly model checking for safety properties with a scheme for scalable reachability analysis. We suggest an efficient, BDD-based algorithm for a distributed construction of a counterexample. The extra memory requirement for counterexample generation is evenly distributed among the processes by a memory balancing procedure. At no point during computation does the memory of a single process contain all the data. This enhances scalability. Collaboration between the parallel processes during counterexample generation reduces memory utilization for the backward step. We implemented our method on a standard, loosely- connected environment of workstations, using a high-performance model checker. Our initial performance evaluation, carried out on several large circuits, shows that our method can check models that are too large to fit in the memory of a single node. Our on-the-fly approach may find counterexamples even when the model is too large to fit in the memory of the parallel system.