一种基于离散时间自动机的LTL性质检测工具

模型检测是一种自动完成性质验证的算法过程,在模型检测过程中会遇到状态空间爆炸的问题,即随系统规模的增长状态空间的大小呈指数增长,如何缓解此问题一直是研究者研究的重点.目前利用模型检测方法对线性时序逻辑(LTL)性质进行检测的工具还比较少,且效率都较低.介绍了一种基于离散时间自动机的LTL性质检测工具,采用了在状态空间中存储延迟序列(DS)的技术,对状态进行压缩存储,减小了时间空间的消耗,加快了检测速度.实验表明,该工具的检测效果是不错的,要好于同类工具,如DTSpin.     

一个命题投影时序逻辑符号模型检测器

现有模型检测工具的形式化规范语言,如计算树逻辑(computation tree logic,简称CTL)和线性时序逻辑(linear temporal logic,简称LTL)等的描述能力不足,无法验证ω正则性质.提出了一个命题投影时序逻辑(propositional projection temporal logic,简称PPTL)符号模型检测工具——PLSMC(PPTL symbolic model checker)的设计与实现过程.该工具基于著名的符号模型检测系统NuSMV,实现了PPTL的符号模型检测算法.PLSMC的规范语言PPTL具有完全正则表达能力,这使得定性性质和定量性质均可被验证.此外,PLSMC可以有效地缓解模型检测工具中容易发生的状态空间爆炸问题.最后,利用PLSMC对铁路公路交叉道口护栏控制系统的安全性质和周期性性质进行验证.实验结果表明,PPTL符号模型检测工具扩充了NuSMV系统的验证能力,使得时间敏感、并发性和周期性等实时性质可以被描述和验证.     

基于扩展RED图的概率时间自动机可达性分析

RED图可以表示一个完整的时间自动机上的状态集,包括其连续时间部分和离散部分.在它基础上实现的模型检测工具RED,在时间自动机模型检测中表现出了优良的性能.另一方面,现有的概率时间自动机模型检测工具仍然使用不同的方法来分别表示概率时间自动机状态的连续时间和离散部分.我们在复用原始RED图的数据结构的基础上,对其做出了扩展,以令其支持概率状态的表达,同时保持其性能方面的优势.我们又为此实现了一个概率时间自动机可达性分析工具原型,并将其与两个概率模型检测工具（PRISM和Modest）就概率时间自动机可达性分析作实验对比,来评估该工具原型的性能.实验结果显示,我们的集成表示概率状态空间的方式,确实提高了概率时间自动机模型检测的时间效率和延展性.     

一种有效的基于LTL和Petri网的模型检测方法

模型检测的一个主要方法是构建线性与时序逻辑（LTL）公式φ的否定形式等价的Büchi自动机Aφ和系统模型M的正交积，并检测正交积的可接受语言是否为空。通过对Generalized Büchi自动机进行化简，可以减小自动机的状态空间，从而提高模型检测的效率。根据所提出的方法设计并实现的基于LTL和Petri网进行模型检测的工具包，可以有效地对基于Petri网表示的系统模型进行模型检测。     

基于UPPAAL的数据关联时序有限自动机模型验证

对数据关联过程建立了时序有限自动机模型,时序有限自动机时钟变量只取整数值,从而减小数据关联过程生成的状态空间。在一定的时间约束下,使用模型检测工具UPPAAL对所建模型的关键性质——关联准确性进行了分析和验证。检测结果验证了利用UPPAAL进行数据关联准确性分析的可行性。     

带时间约束的LTL性质的模型检测的实现

针对当前的模型检测工具不能对时间自动机直接检测带时间约束的线性时序逻辑性质的问题,对带时间约束的线性时序逻辑性质的模型检测进行了研究。带时间约束的线性时序逻辑公式转Büchi自动机后,性质自动机的迁移边上含有了时间约束,在对性质自动机和模型自动机的复合进行空性检测时,通过使用不同方法对如何获取性质自动机迁移边上的时间约束进行了研究,实现了对带时间约束的线性时序逻辑性质的检测,扩展了工具CATV的检测范围,方便了用户的使用。     

IEEE802.11中WEP认证协议的SPIN模型检测

用SPIN工具对WEP认证协议进行模型检测,不仅可以从状态空间上搜索出协议的漏洞,还可以各个角度分析WEP协议的运行逻辑.模型检测的方法先通过建立WEP认证协议的模型,转换成SPIN的输入语言Promela,然后通过建立WEP协议的性质转化成LTL语言,最后利用SPIN工具分析WEP认证协议.实验的结果说明WEP认证协议存在漏洞.     

基于约束依赖图的并发程序模型检测工具

模型检测是一种基于状态空间搜索的自动化验证方法,可以有效地提升程序的质量.然而,由于并发程序中线程调度的不确定性以及数据同步的复杂性,对该类程序验证时存在更为严重的状态空间爆炸问题.目前,大多采用基于独立性分析的偏序约简技术缩小并发程序探索空间.针对粗糙的独立性分析会显著增加需探索的等价类路径问题,开发了一款可细化线程迁移依赖性分析的并发程序模型检测工具CDG4CPV.首先,构造了待验证可达性性质对应的规约自动机;随后,根据线程迁移边的类型和共享变量访问信息构建约束依赖图;最后,利用约束依赖图剪裁控制流图在展开过程中的独立可执行分支.在SV-COMP 2022竞赛的并发程序数据集上进行了对比实验,并对工具的效率进行比较分析.实验结果表明,该工具可以有效地提升并发程序模型检测的效率.特别是,与基于BDD的程序分析算法相比,该工具可使探索状态数目平均减少91.38%,使时间和空间开销分别平均降低86.25%和69.80%.     

基于Yices对时间自动机的有界模型检测

为了避免在有界模型检测过程中对变量进行布尔编码以及对时间自动机模型中的时钟进行预处理,给出一个利用SMT(satisfiability modulo theories)工具进行的对时间自动机进行有界模型检测的方法.该方法将时间自动机模型直接转换成SMT工具可识别的逻辑公式,利用SMT工具可求解包含有整数型和实数型变量逻辑公式的能力来进行模型检测.实验结果表明,对于某些可达性性质的验证,该方法的效率有一定的优势.     

基于SPIN的LTL属性分解方法研究

提出一种基于模型检测工具SPIN的LTL属性分解方法以解决状态空间爆炸问题。根据逻辑和时序操作符常见的组合情况,讨论不同的属性分解模式,根据子属性构建的切片准则进行程序切片,利用SPIN对切片后的等价简化模型进行检测,从而将对原模型上属性的检测转化成对复杂度较低的子模型上各子属性的分别检测。实验结果表明,该方法具有一定的有效性。     

自动验证并发实时系统的线性时段性质

介绍了一个就线性时段性验证实时系统正确性的工具的设计思想以及相关算法,使用时间自动机作为产时系统的描述模型,同时,为了便珩描述并发实时系统,使用带共享变量和通道的时间自动机网作为模型描述并发实时系统,在检验时间自动机网时,用户可以使用工具提供的合成程序将其合并为一个时间自动机然后进行检验,由于时间自动机的状态空间是无究的,通过引入整数状态和状态等价关系的概念,将整个状态0空间划分为有限的状态等价类空间,模型检验过程只需要通过对等价类空间的搜索就可以完成,但往往等价类空间的规模很大,超出了现在计算机的处理能力,原始搜索算法仅仅在理论上是可知地的,为了增工具的使用性,工具中使用的算法运用了一些优化技术来避免对等价类空间的穷尽搜索,使得工具在使用时具有比较好的时间和空间效率。     

On the Construction of Monitors for Temporal Logic Properties

Temporal logic is a valuable tool for specifying correctness properties of reactive programs. With the advent of temporal logic model checkers, it has become an important aid for the verification of concurrent and reactive systems. In model checking the temporal logic properties are verified against models expressed in the tool's modelling language. In addition, model-checking techniques are useful to test actual implementations or to verify models of the system that are too detailed to be analysed by a model checker, by means of, for instance, simulation.A tableau construction is an algorithm that translates a temporal logic formula into a finite-state automaton that accepts precisely all the models of the formula. It is a key ingredient to checking satisfiability of a formula as well as to the automata-theoretic approach to model checking. An improvement to the efficiency of tableau constructions has been the development of on-the-fly versions.In this paper, we present a particular tableau construction for the incremental analysis of execution traces during test, simulation or model-checking. The automaton forms the basis of a monitor that detects both good and bad prefix of a particular kind, namely those that are informative for the property under investigation. We elaborate on the construction of the monitor and demonstrate its correctness.     

自动化车床管理的仿真及优化设计

该文通过对自动化车床100次刀具故障的记录进行数理统计分析,研究了自动化车床连续加工单一零件时刀具的检测及更换模型。首先利用概率大样本场合的D检验方法证明了刀具的故障发生规律服从正态分布,继而求出系统工序的寿命分布函数,列出以零件单位期望损失为目标,关于检测间隔和刀具定期更换间隔为变量的优化模型,最后利用计算机进行列举比较求解,从而得出取得最大经济效益的系统工序的最优检测间隔以及最优刀具更换策略。     

Automatic test case generation from Simulink/Stateflow models using model checking

Model‐based test generation techniques based on random input generation and guided simulation do not satisfy the demands of high test coverage and completeness guarantees as required by safety‐critical applications. Recently, test generation techniques based on model checking have been reported to bridge this gap. To evaluate the effectiveness of these techniques, an in‐house tool suite, AutoMOTGen, has been developed for Simulink/Stateflow and applied on real‐life case studies at General Motors. This paper outlines the test generation methodology of AutoMOTGen and gives a comparative study with a commercial, primarily random input‐based, test generation tool on the same set of examples. The results indicate that in terms of coverage, model checking‐based techniques complement the random input‐based techniques. In addition, they provide proofs for unreachability that can aid in debugging the models. Therefore, it is recommended that model checking‐based tools be utilized to complement and enhance the effectiveness of model‐based testing methods in safety‐critical systems engineering. Copyright © 2013 John Wiley & Sons, Ltd.     

智能组卷中组卷目标的满足性检查与处理

智能组卷是教育测量标准化、规范化的重要组成部分,但不符合题库条件的组卷目标会导致组卷失败.为此,提出一种组卷目标的满足性检查与处理模型,给出满足性检查的判定准则,对分解目标的满足性检查与调整进行算法设计,并利用Transact-SQL对其实现.实验表明,模型能够提高组卷的效率和成功率.     

BIM 支持的施工安全规范合规检查研究综述

 结合 BIM 的自动化安全规范检查可以提高安全管理效率,预防安全事故的出现, 减少安全事故的发生。目前,我国的建筑安全事故频发的现象仍未得到有效改善,建筑安全事 故严重危害了人民的人身和财产安全。近年来,安全管理的研究热度不断增高,但目前国内还 未有总结 BIM 支持安全检查的综述类文章。为此调研了近 10 年的相关文献,从相关技术和应 用层面对国内外 BIM 支持的安全检查的研究和平台进行了综述,重点归纳了规则翻译、模型准 备、执行检查和结果呈现的相关技术,并总结了安全规范检查的平台和应用领域。讨论了目前 安全检查过程中存在的问题,提出相应的解决办法,为安全检查进一步自动化的研究提供思路。     

Symbolic Verification and Analysis of Discrete Timed Systems

This paper presents a novel approach for real-time model checking. It combines the efficiency of traditional symbolic model checking with possibilities to describe and specify real-time systems. Using multi-terminal binary decision diagrams to represent time and time intervals, it becomes possible to transfer efficient algorithms and optimization heuristics known from standard CTL model checking to real-time applications. By introducing a new variant of models called I/O-interval structures we can describe systems in a modular way. Interval structures allow model composition of real-time structures such that state explosion effects are greatly reduced. Besides model checking we also present analysis algorithms which allow to compute key properties like system latencies and minimal response times from the structures describing the system. The practical applicability is proven by experimental results, computed by the verification system RAVEN, which implements all described algorithms, including counterexample generation and waveform visualization.     

模型检测基于概率时间自动机的反例产生研究

模型检测基于概率系统的反例产生问题,在最近引起人们的关注.已有的工作主要围绕模型检测Markov链的反例产生而开展.基于概率时间自动机(PTA)是Markov链的不确定性和系统时钟的扩展.关注的是模型检测PTA的反例产生问题.首先通过在PTA上寻找概率之和恰好大于λ的κ条最大概率的路径,并根据这些路径和原PTA构造原PTA的一个子图,从而快速找到违背性质的具有较少证据的反例.然后精化此结果——通过逐条加入上述各条最大概率的路径来精确地计算已加入路径所构成的PTA子图的最大概率.由于考虑到符号状态交集对概率系统的影响,可以得到证据更少的反例.     

统计算法选择对统计模型检测效率的影响分析

近年来,统计模型检测技术已经得到了广泛的应用,不同的统计算法对统计模型检测的性能有所影响。主要对比不同统计算法对统计模型检测的时间开销影响,从而分析算法的适用环境。选择的统计算法包括切诺夫算法、序贯算法、智能概率估计算法、智能假设检验算法及蒙特卡罗算法。采用无线局域网协议验证和哲学家就餐问题的状态可达性验证为实例进行分析,使用PLASMA模型检测工具进行验证。实验结果表明,不同的统计算法在不同的环境中对模型检测的效率有不同的影响。序贯算法适用于状态可达性性质的验证,时间性能最优;智能假设检验算法与蒙特卡罗算法适合验证复杂模型。这一结论有助于在模型检测时对统计算法的选择,从而提高模型检测的效率。     

混合自适应粒子群算法在电力经济调度中的应用

以电力系统中发电成本最低为目标,结合实际发电运行中系统平衡约束和机组操作约束条件,建立电力经济调度(ED)模型。由于标准粒子群算法存在易陷入局部最优的问题,用这种方法求解ED模型得到的最终结果会不太理想。为此,本文提出一种非线性自适应权重调整策略来增强算法全局搜索和局部搜索能力,首先引入小生境优化种群策略使算法跳出局部最优,然后将这种改进后的混合自适应粒子群算法（HAPSO）应用于求解ED模型。最后,算例分析结果表明本文所改进算法的有效性,提高了求解精度。