中断驱动系统模型检验

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

多处理器实时系统可调度性分析的UPPAAL模型

随着多处理器实时系统在安全性攸关系统中的广泛应用,保证这类系统的正确性成为一项重要的工作.可调度性是实时系统正确性的一项关键性质.它表示系统必须满足的一些时间要求.传统的可调度性分析方法结论保守或者不完备,为了避免这些方法的缺陷,提出使用模型检测的方法来实现可调度性分析.提出了一个用于多处理器实时系统可调度性分析的模板,将与系统可调度性相关的部分包括实时任务、运行平台和调度管理模块都用时间自动机建模,并使用UPPAAL验证可调度的性质是否总被满足.符号化模型检测方法被用于推断可调度性,但是由于秒表触发的近似机制,符号化模型检测方法不能用于证明系统不可调度.作为补充,统计模型检测方法被用于估算系统不可调度的概率,并在系统不可调度时生成反例.此外,在系统可调度时,通过统计模型检测方法获取一些性能相关的信息.     

基于形式化方法的航空电子系统检测

随着航空型号的快速发展,航空电子系统的数字化程度越来越高,软件在其中所占的比例越来越大.对航空电子系统中的软件进行测试和检测是保证航空电子系统质量及可信运行的基础.通过分析航空电子系统软件体系结构,对航空电子系统进行形式化建模,并在此基础上,提出了一种形式化的系统级综合检测方法,从静态和动态两个方面对航空电子系统进行检测,最后通过设计并实现一个综合检测系统来验证该方法的有效性.     

混合云环境下利用世系保障数据一致性的研究

混合云环境下,公有云与私有云共同为用户提供服务,公有云中的应用可能需要频繁读取私有云中的数据,通过复制私有云中的副本到公有云中可降低网络开销,但不同云中文件副本的动态更新会导致云中各个副本的不一致性。提出了一致性服务,该服务由一致性维护模块和一致性检测与恢复模块两个部分组成。一致性维护模块通过发送文件的更新消息的方法维护副本的一致,降低了系统的响应时间;一致性检测与恢复模块利用世系的思想,通过对比副本的世系记录来检测副本的一致性,可将副本不一致状态恢复成一致状态。实验证明混合云下利用世系一致性服务是可行的,由此带来的通信和存储开销在可接受范围内。     

一个分布式K互斥算法的概率模型检测

传统的验证方法难以保证分布式K互斥算法的有效性和安全性.为解决这一问题,给出了进一步的研究,提出一种基于概率模型检测器PRISM的方法,对Kerry Raymond的分布式K互斥算法进行形式化建模与分析验证.通过设置算法中各个进程进入临界区的时间而得出的结果中发现,改变临界区的数目K,对于某一进程进入临界区的平均及时时间的影响并不大.如果某一进程的执行时间比其他进程大很多,则K的增加可以提高运行效率.最后证明了这一结论.     

基于抽象和组合方法的网络协议验证

由于模型检测存在状态爆炸问题,多主体的网络协议组合模型检测往往难以进行。为了缓解该问题,分析了通信主体数量增加对状态数量的影响,提出了组合式的抽象验证方法。首先根据所需验证的LTL性质,建立各个通信主体的Kripke结构,再对该Kripke结构进行抽象;然后组合抽象模型;最后运用Spin对组合抽象模型进行检验。为验证该方法的有效性,对NSPK协议进行了检测,结果表明,该方法所需的状态空间向量长度、搜索深度、存贮和遍历的状态数都有明显减少,有利于缓解状态爆炸问题。     

可组合的描述符泄露类型检查

应用程序通过操作系统的系统调用对文件描述符进行操作并管理文件资源。如果应用程序对资源描述符的管理出现错误并发生描述符泄漏,会严重影响系统的可用性。据此,提出了一种检查程序是否会导致描述符泄漏的类型系统,给出了描述符操作方法的语义和类型约束,证明了类型系统的可靠性定理。此外,还初步讨论了该类型系统在并发程序下的扩展。     

概率模型检测技术在机器人路径规划中的应用

在机器人路径规划的实际应用中,针对机器人移动行为可能会受到外界环境影响的难题,提出了一种采用概率模型检测技术进行路径规划的新方法。首先,分析环境中的主要影响因素,将机器人的移动行为看作一个不确定事件,构建马尔可夫决策过程(MDP)模型。然后,采用概率计算树逻辑(PCTL)公式描述模型属性,表达机器人复杂多样的目标任务。最后,运用PRISM平台对模型进行分析和验证,得到满足属性的全局优化路径和定量数据。仿真结果表明,上述方法不仅能够保障机器人在障碍物环境中无碰撞移动,而且可以避开环境相对复杂的区域,保证机器人以最大概率完成任务。对比试验证明上述方法的正确性和有效性。     

一种基于扩展不完全Kripke结构的三值逻辑模型检测方法

多值模型检测是解决形式化验证中状态爆炸问题的一种重要方法,三值模型检测是多值模型检测的基础,其中如何检验不确定状态的真值是一难点。针对不确定状态检验,提出了一种模型检测方法,首先对不完全Kripke结构PKS进行了扩展,然后在扩展后的模型上给出了检测不确定状态真值的方法,最后给出了基于扩展不完全Kripke结构的三值逻辑模型检测算法。与已有的三值逻辑模型检测算法相比,该算法降低了算法复杂度,完善了对于不确定或不一致信息的处理,从而增强了三值逻辑模型检测的实用性。     

运用SPIN对开放授权协议OAuth 2.0的分析与验证

OAuth 2.0协议是一种开放授权协议,主要用于解决用户账号关联与资源共享问题。但是,其弱安全性导致各网络公司海量用户信息泄露,且OAuth 2.0传输数据采用的https通道效率低下,成为黑客攻击对象。提出采用http通道传输OAuth 2.0协议数据,基于Promale语言及Dolev-Yao攻击者模型对OAuth 2.0协议建模,运用SPIN进行模型检测。形式化分析结果表明,采用公钥加密体系对OAuth 2.0协议进行加密不安全。上述建模方法对类似的授权协议形式化分析有重要借鉴意义。