共查询到18条相似文献,搜索用时 140 毫秒
1.
模型检验是一种自动化验证技术,其应用主要的困难在于状态空间爆炸问题.针对构件组合形成的状态空间爆炸问题,结合构件抽象组合原理及反例引导的抽象精化框架,提出了一种测试用例自动生成的方法.根据某个待集成构件抽象已集成的其他构件,并通过组合各个抽象构件生成抽象组合模型.利用模型检验工具对组合模型进行集成测试,生成抽象测试用例,再通过精化得到原模型对应的具体测试用例.实验结果表明该方法减小了状态空间,在一定程度上减缓了状态空间爆炸的问题. 相似文献
2.
针对模型组合中常见的"状态空间爆炸"问题,分析了抽象和组合两种方法各自的优缺点,采用"反例引导的抽象精化"框架和模型检验思想,将抽象和组合结合起来,为模型组合的检验提出了一种新的方法.设计了模型的抽象、组合、检验和精化算法,开发了一款基于反例引导的、图形化的模型检验工具,使用Kripke结构建立模型,用LTL描述性质,从而表明了反例引导的模型检验方法的过程. 相似文献
3.
4.
构件组合的抽象精化验证 总被引:2,自引:0,他引:2
针对构件组合的状态爆炸问题,改进了反例引导的抽象精化框架,提出了组合式的抽象精化方法,使构件组合的模型检验转化为各成分构件的局部抽象精化,降低了分析的复杂度.提出了在构件组合情况下基于等价关系和存在商的构件抽象方法,用构件抽象的组合建立构件组合的抽象;提出了组合确认定理并给出证明,使反例确认分解为在各构件上对反例投影的确认;通过对单个构件的等价关系的精化实现构件组合的抽象模型的精化.在模型检验构件组合的过程中,不需要为构件组合建立全局的具体状态空间. 相似文献
5.
模型检测因其自动化程度高、能够提供反例路径等优势,被广泛应用于Web服务组合的兼容性验证。本文针对模型检测过程中存在的状态爆炸问题,在传统的模型检测方法中引入谓词抽象和精化技术,提出了一种针对Web服务组合的抽象精化验证框架。使用谓词抽象技术对原子Web服务抽象建模,将各Web服务抽象模型组合成组合抽象模型;将模型检测后得到的反例在各原子Web服务上做投影操作,对投影反例进行确认;对产生伪反例的Web服务抽象模型进行精化,生成新的组合抽象模型,再次对性质进行验证。最后通过实例分析说明基于抽象精化技术的Web服务组合验证框架在缓解状态爆炸问题上的可行性。 相似文献
6.
接口自动机是一个用来描述软构件接口的时态行为的形式模型,传统的简单组合精化检验规则由于没有考虑到环境时子任务的影响而使其实际应用受到较大限制。本文提出了一种对该规则的改进方法,以弥补上述缺陷。 相似文献
7.
为解决松耦合Web事务复杂业务流程的建模问题,确保组合事务的可靠性和一致性,提出一种基于配对Petri网的结构化组合补偿精化方法,实现复杂多伙伴业务流程的抽象层次建模.定义了4种基于配对Petri网的基本组合补偿结构:顺序、并行、选择和循环结构.引入组合流程精化和组合补偿抽象的定义,分析了复杂业务流程的精化和抽象过程,给出了精化流程应满足的性质.通过具体业务实例验证了该精化和抽象方法的可行性. 相似文献
8.
该文在用层次自动机结构化表示UMLStatecharts的基础上,把Statecharts的层次结构特点纳入到组合验证中,使得对实现规范的验证可以通过把系统的某些层次精化部分用更抽象的规约代替来进行,以缓解模型检验中的状态爆炸问题。 相似文献
9.
基于完备抽象解释的模型检验CTL公式研究 总被引:1,自引:0,他引:1
在模型检验中,抽象是解决状态空间爆炸问题的重要方法之一.给定具体Kripke结构和时序描述语言CTL,基于抽象解释框架以及完备抽象解释和性质强保留之间的关系,抽象模型最小精化使得CTL性质强保留,可转换为抽象解释中抽象域的最小完备精化,并且总是存在抽象域的最小完备精化.根据状态标签函数确定初始抽象域,然后通过不动点求解,获得对CTL标准算子完备的最小抽象域,并依据此抽象域求得CTL性质强保留的最优抽象状态划分,最后构造出CTL性质强保留且最优的抽象状态转换系统.并指出了抽象域对CTL标准算子是完备的当且仅当抽象域对补集和标准前向转换是完备的. 相似文献
10.
针对复杂异构、松耦合Web组合事务执行失败时原子性和一致性保持的问题,提出一种基于配对Petri网的复杂组合业务流程的补偿和精化方法,解决复杂多伙伴业务流程的抽象建模问题。首先定义了4种基于配对Petri网的基本组合补偿结构:顺序、并行、选择和迭代结构;然后引入组合流程精化的概念,给出了精化后相关性质的证明,最后通过具体业务实例验证该精化方法的可行性。 相似文献
11.
精化检测是一种重要的形式化验证方法,将系统实现和性质规约用相同形式化语言进行建模,如能证明两者间存在某种精化关系且该关系能够维持性质,可得出系统实现满足性质规约.为验证不同类型的系统性质, traces、stable failures和failures-divergence精化检测方法已被提出.精化检测算法依赖于子集构造,因而其面临状态空间爆炸问题.近年来,已有学者针对NFA语言包含问题提出了基于模拟关系的状态空间消减方法,大大提高了算法性能,且该方法能直接用于traces精化检测.在此基础上,本文提出了基于模拟关系的stable failures和failures-divergence精化检测方法.此外,本文还将精化检测扩展到了时间系统的验证中,提出了基于模拟关系的时间自动机traces精化检测方法.实验结果表明,基于模拟关系的算法效率有很大提高. 相似文献
12.
13.
Compositional verification using assume-guarantee reasoning has recently seen an uprise due to the introduction of automatic techniques for learning assumptions. In this paper, we transfer this technique to a setting with CSP as modelling and property specification language, and present an approach to compositional traces refinement checking. The approach has been implemented using the CSP model checker FDR as teacher during learning. The implementation shows that the compositional approach can both drastically outperform as well as underperform FDR's performance, depending on the example at hand. 相似文献
14.
一种基于满足性判定的并发软件验证策略 总被引:1,自引:0,他引:1
对线性时态逻辑SE-LTL提出了一种基于SAT的有界模型检测过程,该过程避免了基于BDD方法中状态空间快速增长的问题.在SE-LTL的子集SE-LTL?X的有界模型检测过程中,集成了stuttering等价技术,该集成有效地加速了验证过程.进一步提出了一种组合了基于SAT的有界模型检测、基于反例的抽象求精、组合推理3种状态空间约简技术的并发软件验证策略.该策略中,抽象和求精在每一个构件上独立进行.同时,模型检测的过程是符号化的.实例表明,该策略降低了验证时间和对内存空间的需求. 相似文献
15.
16.
Chao Wang Roderick Bloem Gary D. Hachtel Kavita Ravi Fabio Somenzi 《Formal Methods in System Design》2006,28(1):5-36
We propose a refinement approach to language emptiness, which is based on the enumeration and the successive refinements of
SCCs on over-approximations of the exact system. Our algorithm is compositional: It performs as much computation as possible
on the abstract systems, and prunes uninteresting part of the search space as early as possible. It decomposes the state space
disjunctively so that each state subset can be checked in isolation to decide language emptiness for the given system. We
prove that the strength of an SCC or a set of SCCs decreases monotonically with composition. This allows us to deploy the
proper model checking algorithms according to the strength of the SCC at hand. We also propose to use the approximate distance
of a fair cycle from the initial states to guide the search. Experimental studies on a set of LTL model checking problems
prove the effectiveness of our method.
This work was done when the first two authors were in University of Colorado at Boulder. Parts of this work appeared in preliminary
form in [38] and [39]. 相似文献
17.
Many safety-critical systems that have been considered by the verification community are parameterized by the number of concurrent components in the system, and hence describe an infinite family of systems. Traditional model checking techniques can only be used to verify specific instances of this family. In this paper, we present a technique based on compositional model checking and program analysis for automatic verification of infinite families of systems. The technique views a parameterized system as an expression in a process algebra (CCS) and interprets this expression over a domain of formulas (modal mu-calculus), considering a process as a property transformer. The transformers are constructed using partial model checking techniques. At its core, our technique solves the verification problem by finding the limit of a chain of formulas. We present a widening operation to find such a limit for properties expressible in a subset of modal mu-calculus. We describe the verification of a number of parameterized systems using our technique to demonstrate its utility. 相似文献
18.
Bounded Model Checking Using Satisfiability Solving 总被引:10,自引:1,他引:9
Edmund Clarke Armin Biere Richard Raimi Yunshan Zhu 《Formal Methods in System Design》2001,19(1):7-34
The phrase model checking refers to algorithms for exploring the state space of a transition system to determine if it obeys a specification of its intended behavior. These algorithms can perform exhaustive verification in a highly automatic manner, and, thus, have attracted much interest in industry. Model checking programs are now being commercially marketed. However, model checking has been held back by the state explosion problem, which is the problem that the number of states in a system grows exponentially in the number of system components. Much research has been devoted to ameliorating this problem.In this tutorial, we first give a brief overview of the history of model checking to date, and then focus on recent techniques that combine model checking with satisfiability solving. These techniques, known as bounded model checking, do a very fast exploration of the state space, and for some types of problems seem to offer large performance improvements over previous approaches. We review experiments with bounded model checking on both public domain and industrial designs, and propose a methodology for applying the technique in industry for invariance checking. We then summarize the pros and cons of this new technology and discuss future research efforts to extend its capabilities. 相似文献