操作系统汇编级形式化设计和验证方法

由于系统的巨大规模,操作系统设计和实现的正确性很难用传统的方法进行描述和验证.在汇编层形式化地对系统模块的功能语义进行建模,提出一种汇编级的系统状态模型,作为汇编语言层设计和验证的纽带.通过定义系统状态模型的合法状态和状态转换函数来建立系统状态模型的论域,并以此来描述汇编层的论域.通过验证汇编层的功能模块的正确性来保证汇编语言层设计的正确性,达到对系统功能实现的正确性验证.同时,使用定理证明工具Isabelle/HOL来形式化地描述这一系统状态模型,基于这一形式化模型,在Isabelle/HOL中验证系统模块的功能语义的正确性.以实现的安全可信OS（verified secure operating system,简称VSOS）为例,阐述了所提出的形式化设计和验证方法,说明了这一方法的可行性.     

一种混杂Petri网模型动态演变研究

为了实现R.David和H.Alla所定义的混杂Petri网模型行为分析的正确性,提出了一个通用的模型动态演变方法.该方法给出了基于线性规划方法的混杂Petri网瞬时引发速率求解方法,解决了有效冲突情形下的瞬时引发速率求解问题.分析了改变不变行为(Invariant Behavior,简称IB)状态事件之间的相互作用及其对模型演变正确性的影响,同时提出了判定改变IB状态事件的方法.例子表明了所提出的理论与方法对混杂Petri网模型动态演变正确求解的重要性和有效性.     

基于颜色Petri网的有偿交互QA系统投诉模型

有偿交互问答(QA)系统受到越来越多的关注,但是补偿的不公平性等问题可能会引起用户的投诉。通过分析有偿交互QA系统的投诉流程,首先利用颜色Petri网对投诉流程进行形式化建模;然后使用CPN Tools对所建立的形式化模型进行验证;最后对所建模型的状态空间报告进行分析,证明了系统各响应流程设计的正确性等特性。所提出的方法对有偿交互QA系统的综合形式化分析具有重要意义。     

基于Petri网的模型检测研究

模型检测是关于系统属性验证的算法和方法.它通常采用状态空间搜索的方法来检测一个给定的计算模型是否满足某个用时序逻辑公式表示的特定属性.系统模型的状态空间的爆炸问题是模型检测所面临的主要问题,其主要原因是系统自身的并发特性和状态变迁的语义交织对基于Petri网的模型检测理论和验证技术进行了较为详细的研究,着重探讨了基于Petri网状态可达图的偏序简化和偏序语义技术、基于自动机的模型检测算法、基于Petri网的状态聚合法以及基于系统对称性的参数化和符号模型检测技术，并给出了研究思路以及未来所要进行的重点研究工作.模型检测技术已在通信协议和硬件系统的验证等领域得到成功应用，并且随着各种状态空间简化技术和模型检测算法的不断优化，其在其他应用领域也展示出广泛的应用前景.     

反例引导的C代码空间流模型检测方法

软件验证一直是确保软件正确性和安全性的热点研究问题.然而,由于程序语言复杂的语法语义特性,应用形式化方法验证程序的正确性存在准确度低和效率差的问题.其中,由指针操作带来的地址空间的状态变化使得现有模型检测方法的检测准确度难以得到保证.为此,通过结合模型检测与稀疏值流分析方法,设计了一种空间流模型,实现了对C程序在符号变量层面和地址空间层面的状态行为的有效描述,并提出了一种反例引导的抽象细化和稀疏值流强更新算法(CEGAS),实现了C程序指向信息敏感的形式化验证.建立了包含多种指针操作的C代码基准库,并基于该基准库进行了对比实验.实验结果表明:所提出的模型检测算法CEGAS在分析含有多种C代码特性的任务中,与现有模型检测工具相比均能取得突出的结果,其检测准确度为92.9%,每行代码的平均检测时间为2.58 ms,优于现有检测工具.     

基于时态逻辑的工作流分析

工作流的属性规约语言需要具有高表达力以及基于状态和事件的推理能力。本文提出了一种时态逻辑规约语言E-CTL^＊，该语言集成了状态和事件，能够精确和直觉地表示验证的属性。工作流的畅通性验证无论在时间上还是空间上代价都是非常高的，状态空间爆炸是验证的主要困难所在。利用E-CTL^＊描述畅通性，可以使用存在的符号化模型检测工具验证畅通性，在一定程度上克服了状态爆炸问题。同时模型检测技术给出失效路径的优点可以引导我们纠正工作流的错误。工作流的变动需要具有正确性。从时态逻辑的角度讨论了变动正确性问题，得出了保持变动正确性的一般特征。     

基于ASK-CTL的有色Petri网模型检验算法研究

针对使用CPN Tools工具建立系统CPN(Colored Petri Net)模型并进行仿真所得到的状态空间报告中出现的死标识是否会影响系统的安全性和模型的正确性进行研究,提出基于ASK-CTL的有色Petri网模型检验算法及死标识合理性验证算法。算法描述了系统有色Petri网的建模与仿真过程,根据得到的状态空间报告判断是否存在死标识,对存在的死标识采用非标准状态空间查询法使用ML语言编辑相关功能函数以验证死标识的合理性,进而确保所建立CPN模型的正确性与系统的安全性。最后,以电梯门系统为例,证明了算法的有效性。     

改进身份认证协议的形式化描述与验证

以前用着色Petri网验证协议,大多只验证了其正确性,采用着色Petri网对自行设计的基于PKI的动态身份认证系统的安全性进行了描述和验证;一般在使用传统1-可达性分析方法分析复杂身份认证协议时,会存在状态空间爆炸的问题,为了有效地解决该问题,提出了一种用1-可迭性分析方法和向回分析方法相结合的策略,对该身份认证协议进行了分析,从而验证了该身份认证协议是安全的.     

基于状态空间的工作流模型验证

工作流模型的正确性和可靠性是工作流管理系统健壮性的基础。该文提出一种基于状态空间的工作流模型验证方法,从而确保在构造期间产生有效的工作流模型。     

基于Petri网的工作流结构正确性化简验证方法

工作流技术是近年来在计算机应用领域发展最为迅速的新技术之一,但基于覆盖图的工作流网的结构正确性检查的实现过于复杂.本文在Aalst提出的基于Petri网的工作流网的控制流的正确性理论的基础上,提出了工作流网的正确性检查的化简规则及相应的化简算法,实现了对于正确结构的工作流网直接验证;对于错误结构的工作流网,输出其包含问题节点在内的子网结构,可以进一步通过覆盖图的方法确认问题节点,从而降低了工作流网正确性检查的复杂性.     

基于Petri网的AADL模型正确性验证研究

体系结构分析和设计语言AADL能够在架构级对系统进行建模,并通过一系列验证尽早发现系统设计中的问题,在航空航天等嵌入式系统中具有广阔的应用前景。但是目前的验证集中在性能分析等方面,忽略了AADL模型本身的正确性验证。提出将AADL模型的模式和模式转换映射成Petri网模型,结合Petri网的理论对AADL模型正确性进行验证的方法,从而确保建模阶段模型的正确性,为后续各种验证分析奠定了基础,同时进一步降低了在系统实现后发现问题修改模型所带来的时间和成本。最后,通过具体实例验证了该方法的可实施性和有效性。     

面向跨组织业务流程的角色行为验证方法

为了更有效地保证跨组织业务流程模型的正确性和合理性,应用Pi演算提出了一种基于状态的角色行为的验证方法。基于Pi演算提出了跨组织业务协作中的角色模型,设计了角色描述表,以清晰、直观地描述角色的权利、职责和义务,进而应用Pi演算验证工具MWB(移动工作平台)的check和step命令提出了单角色验证方法,并在此基础上从业务对象状态和业务操作角度提出了多角色验证方法。实现了角色行为的验证,并为跨组织业务流程的可达性、一致性和死锁等分析奠定基础。     

基于UML和模型检测的安全模型验证方法

安全策略的形式化分析与验证随着安全操作系统研究的不断深入已成为当前的研究热点之一.文中在总结前人工作的基础上,首次提出一种基于UML和模型检测器的安全模型验证方法.该方法采用UML将安全策略模型描述为状态机图和类图,然后利用转换工具将UML图转化为模型检测器的输入语言,最后由模型检测器来验证安全模型对于安全需求的满足性.作者使用该方法验证了DBLP和SLCF模型对机密性原则的违反.     

跨组织多业务事务建模与验证方法

面向服务的事务处理是保障业务交互和协作正确性的关键技术.针对跨组织多业务流程,提供了一种支持多业务事务建模与验证的方法.在建模方法上,对Pi-演算扩展了事务语义,将进程间的动作交互与跨组织膜活动相关联来刻画多业务事务协调行为.在验证过程中,基于等价自动机转换思路集成现有模型检验技术,验证多业务事务是否满足人们需要的各种性质.实验结果表明,该建模与验证方法能够有效地保障多业务流程在设计与实现过程中的正确性.     

实时鲁棒的自动人眼状态分类

探讨了自动人眼状态分类问题,提出一种基于全局扫描并验证策略的分类框架.该方法采用一种级联结构(Cascade)来组织分类器,采用Adaboost算法学习分类器.实验表明,该方法无论在鲁棒性、正确率和速度方面都达到了很好的性能,具有非常明显的实际应用价值.     

Analysis and verification of real-time systems using quantitative symbolic algorithms

The task of checking if a computer system satisfies its timing specifications is extremely important. These systems are often used in critical applications where failure to meet a deadline can have serious or even fatal consequences. This paper presents an efficient method for performing this verification task. In the proposed method a real-time system is modeled by a state-transition graph represented by binary decision diagrams. Efficient symbolic algorithms exhaustively explore the state space to determine whether the system satisfies a given specification. In addition, our approach computes quantitative timing information such as minimum and maximum time delays between given events. These results provide insight into the behavior of the system and assist in the determination of its temporal correctness. The technique evaluates how well the system works or how seriously it fails, as opposed to only whether it works or not. Based on these techniques a verification tool called Verus has been constructed. It has been used in the verification of several industrial real-time systems such as the robotics system described below. This demonstrates that the method proposed is efficient enough to be used in real-world designs. The examples verified show how the information produced can assist in designing more efficient and reliable real-time systems.     

基于Petri网的一种时序分析方法

Ｐｅｔｒｉ网由于有强大的建模能力和成熟的理论支持,被广泛应用于各种系统的建模．本文通过把Ｐｅｔｒｉ网转换成转移系统,利用转移系统和Ｋｒｉｐｋｅ结构给出时序逻辑语义的解释,从而建立了一种在Ｐｅｔｒｉ网上进行时序分析的方法．这种方法是根据不动点理论,用模型检查验证公式正确性．通过对Ａｄａ程序会合性质进行模型检查,验证了这种方法的有效性．     

工作流过程建模中的形式化验证技术

工作流过程建模是一个复杂且易错的过程．若过程定义在投入运行之后被发现有错,则修复错误的代价相当高,这个问题引起了研究界和工业界的高度重视．因此,在建模阶段进行有效的过程验证是十分必要的．综述了工作流过程验证技术的发展现状,包括强调验证的重要性,叙述了需要验证的问题和复杂度;介绍了对验证方法的要求;讨论了过程合理性验证和化简验证技术等;并通过对研究现状的分析和对比,提出了仍然没有解决的问题和将来的工作．     

基于Petri网的工作流过程验证方案的研究

工作流管理系统最主要的功能是要能够对业务流程的变化做出有效的反应。然而,当前的工作流管理系统并不能灵活应对业务流程的频繁变化,因为它们对所建的工作流模型几乎没有任何检查,以保证一些最低限度的正确性。本文结合Petri网相关理论技术,提出一种将过程模型验证机制集成到工作流流程定制组件中的方法,并对所采用的验证方案进行阐述。