中断驱动系统模型检验

针对一类中断驱动系统提出了一种建模和模型检验的方法.该系统通常由中断处理程序和操作系统调度的任务组成,前者由中断源触发后处理中断事件,后者则负责处理系统的日常任务以及某些中断处理事件的后续处理.因为这类系统是实时控制系统,对中断事件的处理需要在规定时间内响应并完成,否则可能造成严重的系统失效.为了帮助系统设计人员在系统设计过程中应用模型检验技术来提高系统的正确性,首先确定了此类系统中与时序性质相关的系统要素(包括系统调度任务、中断源、中断处理程序)和相关参数,并要求设计人员在设计阶段明确指出这些要素的参数.然后,提出了将这些要素和参数自动转化为形式化模型的方法:使用时间自动机对中断事件进行建模,使用中断向量表和CPU处理栈对中断处理过程进行建模.对于得到的形式化模型,给出了针对中断处理超时错误的检测方法,并在此基础上给出了针对共享资源的完整性、子程序原子性的检验方法.     

中断驱动的嵌入式系统数据竞争检测工具

中断驱动的嵌入式系统广泛应用于对安全和稳定性要求极高的领域,但因系统设计复杂,运行环境多样等原因,中断不确定性导致的严重故障时有发生,数据竞争是较为棘手的问题之一。已有工作对中断导致的数据竞争检测做了许多尝试,但目前还没有比较易用的解决方案。为了解决这类问题,提出了一种基于控制流图的静态检测方法。该方法通过对源程序进行预处理分析,检测出程序中使用的共享资源和中断使能操作;根据预处理的结果,构建出源程序对应的简要控制流图;通过对简要控制流图的抢占关系分析,得到可能会导致竞争关系的执行序列。实验结果表明,该方法能有效检测出程序中潜在的竞争关系,并指明该潜在竞争的发生路径,帮助软件测试人员对故障进行确认和修复。     

BACH:线性混成系统有界可达性模型检验工具

混成自动机的模型检验问题非常困难,即使是其中相对简单的一个子类--线性混成自动机,它的可达性问题仍然是不可判定的.现有的相关工具大都使用多面体计算来判定线性混成自动机状态空间的可达集,复杂度高、效率低,无法解决实际应用规模的问题.描述了一个面向线性混成系统有界可达性模型检验工具--BACH(bounded reacha...     

Linux下中断方式的设备驱动程序设计

中断处理是嵌入式Hnux操作系统的核心任务之一,提高应用程序效率的关键技术是在设备驱动程序中使用中断方式.本文介绍了ARM Linux中断处理过程,研究了Linux下设备驱动程序及其中断服务程序的开发方法和技巧,并实例介绍了键盘中断的服务程序开发方法.     

有界模型检测的优化

G(p)和G(p→F(q))是有界模型检测(bounded model checking,简称BMC)中的两个重要的常用模态算子.对验证G(p)和G(p→F(q))编码转换公式进行优化.通过分析当验证这些模态算子时FSM(finite state machine)的状态转移和线性时序逻辑(linear-time temporal logic,简称LTL)的语义特征.在现有的编码公式的基础上,给出了简洁、高效的递推公式,该公式有利于高效编码成SAT(satisfiability)实例;证明了递推公式和原转换公式的逻辑关系.通过实验比较分析,在生成SAT实例规模和易求解方面都优于BMC中求解这些模态算子的现有的两种重要方法AA_BMC和Timo_BMC.所给出的方法和思想对于BMC中验证其他模态算子时的编码优化也有参考价值.     

基于生物启发模型的欠驱动水平TORA系统的有界输入镇定控制

针对欠驱动水平TORA(translational oscillators with rotating actuator)系统,提出一种基于生物启发模型的有界输入控制方法,实现系统在执行器存在饱和约束情况下的镇定控制.首先,根据水平TORA系统的动力学模型分析系统的无源特性,进而给出系统的控制目标;接着,基于无源特性构造一种新颖的Lyapunov函数,在此基础上设计一种结构简单的非线性状态反馈控制器;然后,考虑执行器的饱和约束条件,引入受生物启发建立的神经动力学模型,利用该模型的有界平滑输出特性,设计一种改进的状态反馈控制器;最后,根据LaSalle不变性原理对系统的稳定性进行严格的数学分析和证明.与其他方法相比,所提方法不仅考虑了执行器的饱和约束问题,而且设计的控制算法简单高效,易于工程实现.仿真与对比结果表明,所提方法具有更好的控制性能.     

基于Stuttering等价技术的有界模型检测的优化

在讨论有界模型检测及其转换公式的基础上,对有界模型检测转换公式[[M,f]]k中的[[M]]k进行优化。通过在LTL有界模型检测中引入Stuttering等价技术,对状态转换路径优化,避免了SAT求解工具在有界Stuttering等价路径中的重复搜索。以安全系统验证为例,通过两个重要的模态算子G（p）和G（p→F（q））,验证优化方法,实验结果表明,该方法有效地提高了对安全系统保密性和认证性验证的效率。     

有界模型检测同步多智体系统的时态认知逻辑

提出在同步的多智体系统中验证时态认知逻辑的有界模型检测(bounded model checking,简称BMC)算法.基于同步解释系统语义,在时态逻辑CTL*的语言中引入认知模态词,从而得到一个新的时态认知逻辑ECKL_n.通过引入状态位置函数的方法获得同步系统的智能体知识,避免了为时间域而扩展通常的时态认知模型的状态及迁移关系编码.ECKL_n的时态认知表达能力强于另一个逻辑CTLK.给出该算法的技术细节及正确性证明,并用火车控制系统实例解释算法的执行过程.     

有界模型检测和串空间模型相结合的安全协议验证

提出用BMC和串空间结合的方法对安全协议进行验证.首先是通过串空间的出测试理论先构造不安全协议的部分丛结构,通过该丛结构来约束协议运行的的规模和角色行为;然后用BMC对该丛结构进行建模,建立起对应的有限状态自动机和LTL验证规范,进行验证,有效减轻状态空间爆炸问题;利用不安全协议丛结构的特点,对BMC的下界进行优化.这种方式结合了模型检测和定理证明的优点,通过典型的安全协议的分析和实验,验证了本方法较传统的模型检测方法在验证安全协议时,验证效率提高明显.     

uClinux下中断驱动的I/O方式

在开发数据流设备的驱动程序时,采用中断驱动的I/O方式结合缓冲区的使用,可以将数据的接收和系统调用read隔离开来,提高设备在系统中的运行效率。本文在讨论uClinux下中断处理程序和底半部分的开发的基础上,以一种电信E1线路和以太网互联设备上数据流设备为例,讲述中断驱动的I/O方式的驱动程序开发。主要过程是在中断期间填充数据到缓冲块,并用链表将缓冲块串接起来;在系统调用read期间从缓冲块取走数据,再将缓冲块放到自由链表中备用。涉及驱动程序中常用的阻塞式I/O和自旋锁等技术应用。通过使用上述多种技术开发的数据流设备驱动程序,确保系统稳定高效的动作。     

航天嵌入式软件整数溢出的形式化验证方法

整数溢出引起的软件系统安全性问题屡见不鲜,已有的模型检测技术由于存在状态空间爆炸、不能有效支持中断驱动型程序检测等缺点而少有工程应用.结合真实案例,对航天嵌入式软件整数溢出问题的分布和特征进行了系统性的分析.在有界模型检测技术的基础上,结合整数溢出特征,提出了基于整数溢出变量依赖的程序模型约简技术;同时,针对中断驱动型...     

多智体系统中约简状态空间的限界模型检测算法

为了形式化描述多智体系统中与概率、实时、知识相关的性质,提出了一种概率实时认知逻辑PTCTLK.模型检测是验证多智体系统是否满足PTCTLK公式的主要技术,状态空间爆炸是该技术实用化的主要瓶颈,为此提出一种PTCTLK的限界模型检测算法.其基本思想是,在有限的局部可达空间中逐步搜索属性成立的证据,从而达到约简状态空间的目的.首先,将PTCTLK的模型检测问题转换为无实时算子的PBTLK的模型检测问题;其次,定义PBTLK的限界语义,并证明其正确性;然后,设计基于线性方程组求解的限界模型检测算法;最后,依据概率度量的演化规律,探索检测过程终止的判别准则.实例研究结果表明,与无界模型检测相比,在属性为真的证据较短的情况下,限界模型检测完成验证所需空间更小.     

概率计算树逻辑的限界模型检测

为了缓解概率计算树逻辑模型检测中的状态空间爆炸问题,提出了概率计算树逻辑的限界模型检测技术.该技术首先定义概率计算树逻辑的限界语义,并证明其正确性;之后,通过实例说明在传统限界模型检测中,以路径长度作为判断检测过程终止的标准已经失效,基于数值计算中牛顿迭代法的终止准则,设计了新的终止判断标准;然后提出基于线性方程组求解的限界模型检测算法;最后,通过3个测试用例说明,概率计算树逻辑限界模型检测方法在反例较短的情况下能够快速完成检测过程,而且比概率计算树逻辑的无界模型检测算法所需求得的状态空间要少.     

一种基于满足性判定的并发软件验证策略

对线性时态逻辑SE-LTL提出了一种基于SAT的有界模型检测过程,该过程避免了基于BDD方法中状态空间快速增长的问题.在SE-LTL的子集SE-LTL?X的有界模型检测过程中,集成了stuttering等价技术,该集成有效地加速了验证过程.进一步提出了一种组合了基于SAT的有界模型检测、基于反例的抽象求精、组合推理3种状态空间约简技术的并发软件验证策略.该策略中,抽象和求精在每一个构件上独立进行.同时,模型检测的过程是符号化的.实例表明,该策略降低了验证时间和对内存空间的需求.     

基于半张量积的完备性阈值求解方法

为了精确地计算Kripke模型的完备性阈值,将半张量积引入到有界模型检测的完备性阈值的计算中,采用离散时间进化系统来研究Kripke模型的状态进化拓扑结构,提出了基于半张量积的有界模型检测完备性阈值的求解算法。通过实例说明了本方法能够求解Kripke模型的完备性阈值。结果表明利用矩阵采用代数方法能够精确地计算模型的前向半径。