一种基于无锁队列的运行时多线程并行验证方法

运行时验证是一种动态的软件验证技术,主要包括使用形式化规约描述待验证性质、自动生成对应监控器以及监控器的插桩.然而现有的面向C语言程序的运行时验证技术存在一些局限性,主要体现在多监控器的情况下,现有的运行时验证工具只能使用串行的方式处理,这大大降低了验证效率.因此,本文在分析了形式化规约的基础上,提出了一种基于无锁队列的运行时多线程并行验证方法.方法在现有工具MOVEC上实现并在测试集mibench上插桩运行,并与相关工具ACC、AC++和串行机制下的MOVEC进行了对比实验.实验结果表明,本文所实现的基于无锁队列的运行时多线程并行算法可以在有多个监控器的情况下有效地对C语言程序进行并行的运行时验证,且并行验证算法的性能比串行验证算法提升了约83%.

一种使用STL逻辑监控CPS的可解释规范挖掘方法

随着信息物理融合系统(CPS)日益复杂,很难捕获其相关行为并以一种可解释的方式检测它.因此本文提出了一种基于线性支持向量机(LSVM)框架的规范挖掘算法,从有限长度的信号轨迹中挖掘具有可解释性的信号时序逻辑(STL)公式.挖掘出的STL公式可以作为监控行为的抽象,用于CPS运行时验证的监控机制中.该算法根据一组被标记的有限时间轨迹和STL模板公式,将信号时序逻辑特有的鲁棒性满意度与LSVM的优化算法相结合生成所需规范.另外,本文还将对一维信号轨迹的规范挖掘技术扩展到多维信号上.最后,通过两个案例研究来说明提出算法的可行性和优势,结果表明该算法在保证高准确率的前提下,执行效率和可解释性都优于其他的规范挖掘算法.

基于单工架构的信息物理系统运行时安全性保障方法

运行时安全性保障方法旨在系统运行过程中确保安全性属性得到满足.基于单工(simplex)架构的运行时安全性保障方法能够在使用复杂且安全性未经验证的控制器的情况下,为系统提供安全性保证.其基本思想是将复杂且安全性未经验证的复杂控制器与经过严格形式化验证的安全控制器相结合,前者工作在无安全风险的情况下,若检测发现系统存在潜在的安全风险,则通过决策模块完成复杂控制器与安全控制器之间的切换,从而确保系统的安全性.本文重点关注基于simplex架构的信息物理系统运行时安全性保障方法,从simplex架构决策模块的设计、改进与拓展,以及simplex架构的应用3个方面展开研究,对相关工作进行了梳理和总结,指出当前面临的技术挑战,并展望未来的发展方向,认为基于simplex架构的运行时安全性保障方法将会是解决智能信息物理系统安全性保障问题的有效途径之一.

基于RPST的业务过程一致性运行时检查方法

一致性检查是关于计算流程模型与其执行实际之间相符情况的问题.运行时一致性检查因反馈的实时性和良好的应用前景,成为当前一致性检查的新问题.针对每个新产生的事件,如何以较小的性能代价计算得到最优的一致性检查结果是运行时一致性检查的难点.基于流程模型的结构信息(refined process structure tree,RPST)提出一致性监控树(conformance monitoring tree,CMT),基于CMT提出求解最优一致性结果的动态规划算法.通过3个实验数据集表明,对比已有相关工作,本文算法具备较明显的性能优势.

基于概率时间自动机的异构多agent自适应运行时验证

多agent自适应系统在运行过程中需要根据环境进行自适应调整。异构agent能够提高agent的使用效率和降低系统的构建成本,但存在复杂的协作问题,因此提出一种基于概率时间自动机的异构多agent自适应系统运行时验证方法。该方法通过形式化描述异构agent的功能特征并融合环境中的随机因素构建概率时间自动机模型模拟自适应系统的运行过程,针对异构agent之间的协作逻辑制定安全约束条件以确保系统运行中状态迁移流程的安全性。通过模型检查结合运行时定量验证方法进行实验验证,在智能泊车系统案例中应用该方法。实验结果表明,agent之间协作逻辑的正确性可以有效保证系统运行时的稳定性,且相较于不使用运行时定量验证的初始系统在相同时间内正常运行的时间提升了21%左右。

C程序数组越界的运行时验证技术研究与实现

缓存区溢出能引起非常严重的安全问题,对网络和分布式系统(如机群,网格,P2P系统等)构成严重威胁。数组越界在缓存区溢出中占据重要位置,如何检测数组越界错误是一个重要且极具意义的课题。针对该课题,给出一种对C语言数组越界进行运行时验证的方法。分析了数组越界的错误类型,根据这些类型分别研究了数组越界的运行时验证的思想;设计了基于程序插桩进行数组越界动态检测的算法,给出了该方法基于开源编译器Clang的具体实现;用实验证明了该方法是切实可行并且有效的。

基于AOP的运行时验证中的冲突检测

现有的形式化验证方法除了在模型层面对系统进行验证以外,越来越倾向于直接针对系统的实际代码和具体运行.运行时验证技术验证的对象是具体程序,它试图把形式化验证技术部署到程序的实际运行过程中.然而在把形式化技术部署到实际运行过程中会出现一系列在模型层面验证通常不会出现的问题,对这些问题中的冲突现象进行了研究,定义了运行时验证技术中存在的两种冲突,并给出了相应的检测算法.最后,对这些算法进行了实现和实例研究,结果表明了该方法的有用性.

安全可信工业控制系统构建方案

针对当前工业控制系统所面临的信息安全问题,提出了一种安全可信的体系架构。首先分析了工控系统特点、整体模型和控制流程,然后结合可信计算的思想,对工控系统的启动、组态和运行进行了安全加固,设计了静态度量、安全传输以及运行结果安全性验证。该体系可有效提高工控系统的安全防御能力。

基于UML2.0序列图的Web服务运行时验证方法

为了确保包括非功能属性在内的服务规约与服务实际运行行为之间的一致性,提出一种Web服务运行时行为验证方法。首先对UML 2.0序列图进行扩展,将QoS属性和功能属性的描述统一起来,以精确表达Web服务的需求规约。然后,提出利用确定有限自动机构造出扩展序列图(Extended Sequence Diagrams,ESD)的语义模型的方法。最后,给出验证准则,根据Web服务的交互消息和规约建模的结果来验证Web服务运行时行为与需求规约之间的一致性。基于上述研究,设计开发了Web服务运行时验证工具(Runtime Verification Tool for Web Services,RVT4WS),以支持对Web服务运行时行为的验证。

面向参数化LTL的预测监控器构造技术

介绍了一种基于自动机理论的参数化LTL(parameterized LTL(linear temporal logic),简称PALTL)公式运行时预测监控器构造方法.一方面研究PALTL公式的语法、预测语义、赋值提取以及赋值绑定等重要概念,从语法层面保证公式中参数化变量的正确绑定(binding)和使用(using);另一方面给出参数化预测监控器的概念.它由静态和动态两部分组成,静态部分由参数化Büchi自动机表示,动态部分为当前状态处的变量赋值.在系统运行过程中,预测监控器基于静态部分的参数化Büchi自动机,以on-the-fly的方式在当前状态处动态地提取和绑定变量赋值,递进地验证当前程序运行是否满足指定的参数化性质规约.在该过程中,参数化监控器能够精确地识别被验证性质的最小好/坏前缀.

多核处理器架构下面向监控的软件运行时验证方法研究

面向监控的软件运行时验证(Monitor-oriented Runtime Verification:MRV)方法可以有效的提高系统可靠性,但是在传统基于单核处理器架构的嵌入式系统中采用MRV方法会给目标系统性能造成较大的影响.本文对基于多核处理器架构的MRV方法进行了初步研究,分析并设计了在线验证、离线验证以及单监视器设计与多监视器设计等多种模式的MRV方法,给出了相应的MRV实现方案,并在几个开源项目中进行了MRV实例应用.实验数据分析表明,在不同模式下,基于多核处理器架构的MRV方法能够从不同程度上有效提高系统运行时验证的性能.本文工作为进一步设计有效的多核架构下MRV方法提供了基础.

UML行为图驱动的Java程序运行时验证工具

UML是一种标准的可视化建模工具,广泛应用于软件系统的描述、可视化、构建和建立文档。本文介绍了一种UML行为图驱动的Java程序运行时验证工具。该工具以一个随机的测试用例集作为输入,运行经过插装的被测Java程序,得到一组用于验证的程序运行轨迹。通过对程序运行轨迹和UML行为图中合法的事件序列的比较,该工具可以对程序的动态行为规约进行检查。本文描述了该工具的设计思想、算法和实现技术,并通过对实例研究对该工具的可用性和有效性进行了讨论。

一种基于运行时验证的Web服务选择方法

为了确保用户选择的Web服务的运行时行为与用户需求之间的一致性,提出了一种基于运行时验证的服务选择方法。首先基于自动机原理,对Web服务进行运行时验证。其次,定义了3种程度的行为匹配关系,基于运行时验证结果,量化Web服务运行时行为与用户需求之间的匹配程度,并使用AHP理论计算用户偏好。方法综合考虑行为匹配程度和用户偏好对服务选择的影响,提出服务选择策略。最后通过实验分析和比较说明了该方法的合理性。

参数化运行时验证研究和工具实现

随着软件规模的不断增大,如何保证软件的可靠性和安全性成为学术界和工业界越来越关注的问题.运行时验证是一种新型的程序自动验证技术,弥补了静态分析和模型检测等常用方法的缺点.设计一种针对C程序的监控器规约语言,用于描述针对C程序的形式化规约.该语言支持基于有限状态自动机和正则表达式的参数化运行时验证.本文借助开源工具flex和bison实现了支持该语言的参数化运行时验证工具M OVEC.为了对运行时产生的大量监控器进行索引,我们提出并实现了一种层次哈希森林的数据结构.实验证明该工具是可行且高效的.

多目标约束下软件运行时验证加速技术框架

软件运行时验证是一种近年来逐步兴起的通过监控程序运行来检验其是否满足给定性质的轻量级验证技术。由于复杂性质的运行时验证中常产生高额的时间开销,阻碍了该技术在部署后系统中的应用。在深入剖析国内外研究现状及存在问题基础上,从改善部署后软件运行时验证效率的角度出发,综合考虑性质违背检测能力、诊断支持能力等潜在开销优化制约因素,提出多目标约束下的软件运行时验证加速技术框架。该框架包括构建多目标约束模型、可加速监控器判定、加速控制技术研究以及原型工具开发等内容,并具体阐述了框架所涉及的关键技术方案。本研究将为解决运行时验证中的开销问题提供关键技术支撑,为运行时验证技术在部署后系统中的工程化应用奠定基础。

嵌套模式模板在运行时验证中的应用

随着信息技术的迅速发展,对于硬件、软件、网络等可靠性的高效检验成为急需解决的一个重要问题.在众多验证方法中,运行时验证由于其反馈及时、轻量级等多种优势正被应用到越来越广泛的领域.然而,现有运行时验证方法仍有两方面的不足:其一,尽管现有运行时验证中对性质的描述采用形式化方法,但现有自然语言向形式化语言的转化过程不能直接完成,这就会极大的影响了运行时验证的推广使用.其二,现有运行时中规约都是常量事件,并具有不可变性,而在实际中大量事件之间的关系是具有共性的.因此,在对现有规约进行统计的基础上,抽象出常用规约组成模式库,这样用户可根据需要,来调用模式库中的模板,从而减少了从自然语言到形式化方法的转化过程中所需的人工干预.

一种基于活性顺序图的运行时验证研究

运行时验证是一种轻量级的形式化验证方法,使用可视化的需求规约描述语言建模需求规约场景是运行时验证领域的研究热点。针对目前基于活性顺序图的运行时验证方法中容易产生冗余性质、二值语义的验证结果不准确、基于Maude工具引擎的重写逻辑验证算法效率较低等问题,提出一种基于活性顺序图的运行时验证的改进方法,以支持现有的运行时验证技术。实验表明,改进方法验证结果准确,且验证过程开销较小。

基于Multi-agent的实时系统运行故障监控研究

软件密集型装备中常常包含着许多担负监测和控制作用的嵌入式实时系统,它们常常属于安全关键或者任务关键系统(safety-critical/mission-critical system)。为了能够有效解决该类系统中的软件故障检测、诊断与修复任务,本文提出了基于Multi-agent的实时系统运行故障监控框架,旨在利用在多agent的协作构建运行故障监控系统来在系统运行当中验证系统是否满足时序逻辑描述的性质规约,并采用具体的算法进行故障定位和修复。

Agent主体的自演化技术及其支撑软件环境

提出了基于Agent,以动态绑定机制为核心的软件自演化技术,根据自演化的性质和特点,区分出微观层面个体Agent自演化约束和宏观层面系统全局自演化约束;提出了对自演化约束进行描述的语言设施,并通过运行时检查的方法对自演化约束条件进行了分析和检查。介绍了对系统自演化约束进行描述和检查的支撑软件环境SADE,并通过案例阐明了研究成果的可行性和有效性。

面向多线程程序的内存安全运行时验证

Linux操作系统、嵌入式系统、航电系统、通信系统等一般都是用C/C++语言进行编写。因为C语言具有偏底层硬件、移植性强、执行效率高等优秀特性。但是随着多核并行机的出现,许多语言也开始支持多线程编程。由于C语言本身存在着对内存访问时,不对内存边界进行检查的问题,从而造成软件系统相关的可靠性和安全性问题。对多线程C语言程序来说,由于多线程程序的不确定性,使得运行时验证多线程C程序的内存安全问题变得更加困难。通过使用基于改进的指针运行时验证技术、多核多线程技术、并行计算、无锁数据结构技术、源代码插桩技术方法,并结合开源工具Clang编译器实现原型工具Movec对多线程C程序的支持。该工具实现了对多线程C程序内存安全问题的运行时验证。然后通过Mibench和SARD测试用例进行实验,验证了该工具对多线程C程序进行运行时验证的有效性。