一种接口自动机的组合精化检验方法

接口自动机是一个用来描述软构件接口的时态行为的形式模型，传统的简单组合精化检验规则由于没有考虑到环境时子任务的影响而使其实际应用受到较大限制。本文提出了一种对该规则的改进方法，以弥补上述缺陷。     

时间符号迁移图上的可达性分析

提出了以时间符号迁科为建模语言、基于可达性分析的模型检测算法，并给出了算法的正确性证明。该算法可被用于硬件设计和通信协议验证等领域。     

时间自动机可达性分析中的状态空间约减技术综述

时间自动机是检验实时系统建模的有效工具,其可达性分析可以检验系统是否可能达到某些特定的状态,其算法通常采用对符号状态的枚举来遍历其状态空间。因为引入了时钟变量,时间自动机的可达性分析算法会产生大量的中间状态,需要巨大的存储空间,往往超出了计算机能力的极限,导致分析和检验不能完成。这就是所谓的“状态空间爆炸”。研究人员设计了很多种优化技术来约减可迭性分析所需的存储空间,以解决或者缓解这个问题。本文首先介绍了时间自动机及其可达性分析的基本概念,然后分类讨论了现有的空间约减优化技术并对此做出总结,最后提出了一些未来的研究方向。     

基于多面体包含的非线性混成系统可达性分析

针对一类非线性混成系统的可达性问题,提出了一种基于多面体包含的分析方法。首先介绍了混成系统及其可达性,讨论了如何应用多面体包含对多项式混成系统进行线性近似,并采用量词消去和非线性优化方法来构造相应的线性混成系统,然后运用验证工具SpaceEx求得原非线性混成系统的过近似可达集,并应用于验证系统的安全性。     

基于广义随机Petri网的Web服务组合建模与可达性分析

针对目前Web服务组合性能分析研究中的不足,深入研究了基于构件服务的服务组合模型和Web服务组合的技术特点,提出了一种基于广义随机Petri网的Web服务组合可靠建模和可达性分析方法,提高了Web服务组合性能分析的准确性,从而更有效的指导Web服务的组合过程中构件服务的选择和系统建构的调整。     

混合系统的符号化可达性分析

定义了一种称作混合区域的形式化结构表示矩形混合系统的状态集,它实际上是由一组特殊形式的线性不等式联立表示的多面体空间.证明了混合区域对于矩形混合系统的可达性操作的封闭性.此外,用矩形混合系统近似模拟非线性混合系统,相应地解决了非线性混合系统的可达性问题.使用混合区域,可以直接计算由某个正则的混合区域开始的可达集,这样,混合系统的可达性问题主要是求解混合区域的正则型问题,而这问题是一种线性规划问题,可以使用经典的线性规划算法加以解决.     

基于状态空间等价类的有色Petri网特性验证

在有色Petri网的状态空间中,有时一些状态具有相似的行为,这些状态可以用定义在状态空间上的一致的等价关系来表达,对每个等价状态类只研究它的一个代表状态的行为,这极大地减小了有色Petri网的状态空间。但是,通常对一个给定的等价关系是否为一致的验证都是通过用户的经验人工进行的,这不但容易产生错误,而且效率低下。该文依据普通状态图和等价类状态图的标记迁移系统关系,对状态空间一致性等价定义的计算机辅助验证做了深入的讨论,给出了相应的结果。     

基于下推系统可达性分析的输出信道信息流检测

提出了一种对含输出信道的命令式语言进行信息流安全性分析的方法。将程序抽象为下推系统,通过自合成将不千涉性转化为安全性属性,将两次相关执行中向输出信道的输出操作分别抽象为由下推规则表示的存储和匹配操作,通过对标错状态的可达性分析验证程序是否满足终止不敏感不干涉性。演化后的方法支持程序的发散执行,通过上界回退算法找到强制终止首次执行所需的最大输出信道上界。实验说明该方法与现有工作相比具有更高的精确性和验证效率。     

基于联合分布的多标记迁移学习

针对现有的多标记迁移学习忽略条件分布而导致泛化能力不足的问题,设计了一种基于联合分布的多标记迁移学习（Multi-label Transfer Learning via Joint Distribution Alignment,J-MLTL）。分解原始特征生成特征子空间,在子空间中计算条件分布的权重系数,最小化跨领域数据的边际分布和条件分布差异;此外,为了防止标记内部结构信息损失,利用超图对具有多个相同标签的数据进行连接,保持领域内几何流行结构不受领域外知识结构的影响,进一步最小化领域间的分布差异。实验结果表明,相比于已有多标记迁移学习算法在分类精度方面具有显著提升。     

面向程序可达性验证的数组处理循环压缩方法

计算机软件的安全性和健壮性逐渐成为一个非常重要的问题,而自动软件形式化验证是一种验证软件程序安全性和健壮性的可靠性较高的方法。在自动软件形式化验证中,大规模数组和复杂循环导致状态爆炸,使得验证器无法在规定时间内完成验证,因此如何在保证验证正确性的前提下压缩数组规模是一个值得研究的课题。文章提出复杂循环等价类的定义和相关命题,并提出一种面向程序可达性验证的数组处理循环压缩方法,先利用控制流自动机和系统依赖图进行静态分析划分等价类,再根据循环依赖关系对等价类进行压缩,用压缩后程序的验证结果代替原始程序的验证结果。实验结果表明,文章提出的方法能够在保证验证正确性的前提下压缩程序的规模,提高验证效率。     

一种新的安全通信协议安全性验证框架*

将CRA应用于安全通信协议的层次结构分析领域,采用LTS对协议的层次结构进行行为建模,并利用映像LTS描述协议行为的安全属性。采用接口技术对行为模型和属性模型进行组合约简,通过观察组合模型中错误状态是否可达来判定协议是否安全,为安全通信协议的安全性验证提供了一种新的框架。最后基于该框架给出FSFB/2(fail safe field bus/2)协议的安全性验证,表明该框架的可用性。     

An Automata-Theoretic Approach to the Reachability Analysis of RPPS Systems

We show how the tree-automata techniques proposed by Lugiez and Schnoebelen apply to the reachability analysis of RPPS systems. Using these techniques requires that we express the states of RPPS systems in a tailor-made process rewrite system where reachability is a relation recognizable by finite tree-automata.     

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

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

基于状态可达图的离散事件系统时态性质分析

离散事件系统的许多重要性质可用时态逻辑方便，直接和简明地进行描述，系统的性质分析可转化成时态满足关系的判定。基于状态可达图，给出了有限系统时态特征的判定方法。     

Reachability Analysis of Synchronized PA Systems

We present a generic approach for the analysis of concurrent programs with (unbounded) dynamic creation of threads and recursive procedure calls. We define a model for such programs based on a set of term rewrite rules where terms represent control configurations. The reachability problem for this model is undecidable. Therefore, we propose a method for analyzing such models based on computing abstractions of their sets of computation paths. Our approach allows to compute such abstractions as least solutions of a system of (path language) constraints. More precisely, given a program and two regular sets of configurations (process terms) T and T^′, we provide (1) a construction of a system of constraints which characterizes the set of computation paths leading from T to T^′, and (2) a generic framework, based on abstract interpretation, allowing to solve this system in various abstract domains leading to abstract analysis with different precision and cost.     

Verification of Similar FSMs by Mixing Incremental Re-encoding, Reachability Analysis, and Combinational Checks

State space exploration is often used to prove properties about sequential behavior of Finite State Machines (FSMs). For example, equivalence of two machines is proved by analyzing the reachable state set of their product machine. Nevertheless, reachability analysis is infeasible on large practical examples. Combinational verification is far less expensive, but on the other hand its application is limited to combinational circuits, or particular design schemes. Finally, approximate techniques imply sufficient, not strictly necessary conditions.The purpose of this paper is to extend the applicability of purely combinational checks. This is generally achieved through state minimization, partitioning, and re-encoding the FSMs to factor out their differences. We focus on re-encoding. In particular, we present an incremental approach to re-encoding for verification that transforms the product machine traversal into a combinational verification in the best case, and into a computationally simpler product machine traversal in the general case.Experimental results demonstrate the effectiveness of this technique on medium-large circuits where other techniques may fail.     

结合可达性分析的代码片段推荐

为满足日益复杂的软件需求,开发人员需要通过代码提示工具来辅助完成开发任务,但现有代码提示工具在推荐包含静态方法的代码片段时存在空间爆炸问题。为此,提出一种基于程序环境信息的代码片段推荐方法。结合可达性分析进行推荐能够有效削减静态方法入口点,在避免空间爆炸的同时,还可以准确、有效地描述程序环境信息。基于该方法实现在Eclipse中的代码推荐插件,并对Tomcat源码进行实验验证。实验结果表明,该方法可实现静态方法的代码片段推荐,与Eclipse Code Recommenders插件中的推荐方法相比,能获得更准确的推荐结果。