基于服务分组和调用轨迹的Web服务组合验证方案

针对Web服务组合的有效性验证问题,提出了一种基于服务分组和调用轨迹的Web服务组合形式化验证方案。首先,基于服务调用顺序,利用提出的Web服务集分组(WSSG)算法将候选Web服务划分为几个子集,并结合调用轨迹编排这些子集组成WSSG图,作为系统的抽象模型;然后,推理出系统所需的预期交互规范,并利用线性时序逻辑(LTL)来描述交互规范;最后,通过检测模型是否符合交互规范来验证组合模型的可行性。实验结果表明,该方案能够有效验证Web服务组合的正确性,且避免了死锁现象。     

基于Craig插值的线性混成系统符号化模型检测

最强后件的计算是模型检测算法的核心.本文使用一阶逻辑可满足性模线性算术理论给出线性混成自动机的有界模型检测表示公式,利用一阶逻辑公式不可满足情况下的插值存在性定理,对线性混成自动机的有界模型检测公式进行指定的划分,使用支持线性算术插值计算的可满足性模理论后端证明引擎的线性时间复杂度的消解反证技术获得这两部分公式间的插值公式,按一阶逻辑Craig插值的性质,所得到的插值公式就是模型检测过程中最强后件公式的上近似表示.有效地避免了使用逻辑编码方案实现线性混成自动机模型检测过程中需要双指数时间复杂度的量词消去操作求取最强后件公式,也不需像有界模型检测按步长展开变迁公式进行可满足性判定.最后本文在此最强后件计算的基础上,以有界模型检测技术作为反例确认方法,实现了一种无假反例的混成系统近似可达集计算算法.实验证明该算法与目前已经得到广泛工业应用的有界模型检测算法相比具有更优的性能.     

模糊线性时序逻辑的可实现性

模糊线性时序逻辑（fuzzy linear temporal logic）被应用于刻画模糊系统的规范语言,其可实现性（realizability）用于判断满足该时序逻辑公式的开放系统模型是否存在.模糊线性时序逻辑可实现性和系统合成（synthesis）的基本思想是：给定模糊线性时序逻辑公式,判断是否存在满足该公式的系统.如果存在,则构造满足该公式的最优系统.为了检验模糊线性时序逻辑的可实现性,首先引入模糊Büchi博弈的定义,作为检验模糊线性时序逻辑公式是否可实现的模型.其次通过归约的方法,研究模糊Büchi博弈的性质（最优无记忆策略存在性.最后验证模糊线性时序逻辑的可实现性并且给出其系统合成的过程,并说明它们的时间复杂度.     

基于XYZ/ADL的Web服务组合描述与验证

Web服务组合是当前Web服务领域的一个研究热点,目前已有一些相关的描述与验证方法,本文从软件体系结构角度研究Web服务组合描述与验证方法.基于软件体系结构描述语言XYZ/ADL和精化检验/模型检测方法,提出了一种Web服务组合的描述与验证方法.XYZ/ADL是时序逻辑语言XYZ/E的扩展,考虑到多数Web服务具有实时特征,采用XYZ/E的实时扩展语言XYZ/RE表示系统应满足的时间约束.针对Web服务组合系统,根据XYZ/RE到时间自动机的映射规则将系统描述转换为对应的时间自动机,分别采用精化检验和模型检测两种技术验证Web服务组合的正确性;最后通过两个实例分析分别阐述了上述方法的可行性和有效性.     

PSL的有界模型检验

 基于SAT的有界模型检验被视为是基于OBDD的符号化模型检验技术的重要补充,是并行反应式系统的一种有效验证方法.然而,直至现在,有界模型检验已验证的属性逻辑还十分有限.PSL是一种用于描述并行系统的属性规约语言(IEEE-1850),包括线性时序逻辑FL和分支时序逻辑OBE两部分.通过模型检验可验证系统的PSL属性,本文提出了PSL的有界模型检验方法及其算法框架.首先,定义PSL逻辑的有界语义,而后,将有界语义进一步简化为SAT,分别将PSL性质规约公式和系统M的状态迁移关系转换为SAT命题公式,最后验证上述两个SAT命题公式合取式的可满足性,这样就将时序逻辑PSL的存在模型检验转化为一个命题公式的可满足性问题,并用一个队列控制电路实例具体解释算法执行过程.     

离散时间区间时序逻辑可满足性的判定

目前还没有模型检查的方法自动检测模型是否满足时间区间时序逻辑描述的性质.我们约束时间域到离散时间,证明了离散时间区间时序逻辑的可满足性是可判定的,因而是可模型检查的.提出了时间正则图模型,通过从离散时间区间时序逻辑到时间正则图的构造,提出了基于该逻辑的判定算法,该算法可以推广到其它的时序逻辑模型检查,并优于现有的基于自动机的时序逻辑判定方法.     

基于MDA的语义Web服务的组合与验证

针对语义组合Web服务的验证问题,研究了模型验证相关技术、统一模型语言(UML),提出了基于模型驱动架构(MDA)的组合方法.该方法使用UML类图和用例图对OWL-S进行静态组合建模,使用活动图对OWL-S进行动态组合建模,实现了语义组合Web服务的UML描述,然后将该描述转换为Promela语言代码,在Promela代码之后增加LTL的声明,使用SPIN工具进行正确性、安全性和活性验证.该模型保证了组合过程的正确性.     

一种代币智能合约的两段式模型检测方法

针对代币智能合约的形式化验证方法中模型检测存在的状态空间爆炸问题,提出了一种两段式模型检测方法.使用图转换规则对智能合约建模,利用工具生成模型状态空间.第一阶段对部分状态空间进行分支时序逻辑验证后,第二阶段先使用前一阶段的状态验证信息构造马尔可夫链,使用集束搜索结合马尔可夫链对余下状态进一步筛选,再进行验证.实验结果表...     

具有模糊时态的广义可能性线性时序逻辑的模型检测

本文首先定义了具有模糊时态的广义可能性线性时序逻辑GPoFLTL（Generalized Possibilistic Fuzzy Linear Tempora Logic）的语构以及基于路径和基于语言的两种语义解释,证明了GPoFLTL在模糊时态方面对GPoLTL（Generalized Possibilistic Linear Tempora Logic）进行了扩张,并通过实例说明了GPoFLTL比GPoLTL具有更强的表达能力;其次在广义可能性测度下通过模糊矩阵运算讨论了"不久","几乎总是"等几类模糊时态性质的模型检测问题;最后研究了模糊时态性质的必要性阈值模型检测问题,给出了基于自动机的GPoFLTL的阈值模型检测算法及算法的复杂度.     

面向SoC系统芯片中跨时钟域设计的 模型检验方法

 传统方法无法在RTL验证阶段全面验证SoC系统芯片中的跨时钟域设计.为解决此问题,本文首先提出描述亚稳态现象的等价电路实现,用以在RTL验证中准确体现亚稳态现象的实际影响;然后使用线性时序逻辑对跨时钟域设计进行设计规范的描述;为缓解模型检验的空间爆炸问题,进一步针对跨时钟域设计的特点提出基于输入信号的迁移关系分组策略和基于数学归纳的优化策略.实验结果表明本文提出的方法不仅可以在RTL验证阶段有效地发现跨时钟域设计的功能错误,而且可以使验证时间随实验用例中寄存器数量的递增趋势从近似指数级增长减小到近似多项式级增长.     

林业信息系统模型检测应用方法研究

模型检测作为一种形式化验证技术已成功应用于硬件以及协议的性质验证过程,目前正转向软件验证领域并逐渐扩展其应用范围。针对特定的森林防火专家系统的知识库规则,研究其所需满足的性质规范的形式化验证问题。首先将规则体描述为状态迁移图,通过引入转换函数对状态迁移图的变迁过程及状态性质进行了有效说明,然后将性质规范描述为相应的时序逻辑表达式,最后通过实例对模型检测过程进行了详细说明,本文的研究成果有效地说明了将模型检测应用于森林防火专家系统等林业信息系统的可行性与正确性。     

Verification of Secure Network Protocols in Uncertain Environments

In this paper, we present a method for protocol checking and verification using discrete event control. By protocol checking and verification, we mean verifying that a protocol is logically correct, that it does not cause deadlocks, and that it has been defined to respond to uncontrollable events that may occur in a system implementing it. Our approach differs from those previously suggested in two key ways. We extend the elementary theory of discrete event control to allow us to model more complicated protocols, including protocols relying on arbitrary counting models. We then present a maximum probability method for analyzing a protocol’s ability to react to a priori unspecified events. Unlike current protocol modeling, we use a pushdown automata for modeling protocols. This allows us to model protocols with greater fidelity. Our methods are illustrated using a simple two-level hierarchical protocol that defines the behavior of ad hoc wireless network nodes as they attempt to establish a secure connection. As wireless networks become more prevalent throughout the world, the off-line verification of protocols before they are implemented will help ensure that wireless network protocols are robust to security intrusions before they are deployed into the field. This will save time and money in the long run.     

面向模型检验的跨时钟域设计电路 特性生成方法

对跨时钟域设计进行功能验证是SoC验证中的难点问题.传统的面向跨时钟域设计的模型检验方法并没有充分考虑电路特性描述的完整性问题,然而制订完整的电路特性是模型检验有效性的基础,不全面的电路特性描述将可能隐藏设计错误.为生成完整的描述跨时钟域设计的电路特性,本文首先提出基于有限状态自动机的电路特性生成方法;然后为缓解状态空间爆炸问题,提出基于亚稳态的数值化简策略.通过对两个典型的跨时钟域设计进行实验的结果表明,采用本文方法不仅能够达到100%的电路特性覆盖率,而且可以发现被传统方法隐藏的功能错误.同时模型检验的时间代价也能够得到大幅度降低.     

总线监视器的设计

随着集成电路设计规模的不断增加，传统的验证方法学由于无法提供足够的能力来检查系统所有可能功能的正确性，已经不能满足SoC验证的需求。验证重用方法学是解决这一问题的有效途径。在SoC的验证过程中．利用总线监视器对片上总线上发生的事务进行实时监视，并将监视结果以机器可读的格式显示出来，从而可以帮助验证工程师有效地判断数据传输的正确性，达到验证单个模块和系统功能的目的。本文提出了一种SoC功能。验证平台中总线监视器的设计方法，并给出了具体的实现过程。     

多源数据融合理论与同期线损校核方法研究

针对传统同期线损校核速度较慢、校核结果准确度较低的问题,文中设计一种新型线损校核框架,实现电力交易过程中线损数据核对的目的.文中基于多源数据融合理论,对电力市场多源化数据进行融合,通过建立同期线损数据监测模型,对电力市场数据进行监测,保证校核结果的准确性;利用联合转移分布因子算法对校核数据进行整合,使校核数据能够合理应...     

On applying molecular computation to binary linear codes

Adleman's (1994) successful solution of a seven-vertex instance of the NP-complete Hamiltonian directed path problem by a DNA algorithm initiated the field of biomolecular computing. In this correspondence, we describe DNA algorithms based on the sticker model to perform encoding, minimum-distance computation, and maximum-likelihood (ML) decoding of binary linear codes. We also discuss feasibility and limitations of the sticker algorithms