共查询到19条相似文献,搜索用时 151 毫秒
1.
线性时态逻辑SE-LTL是具有高表达力和基于状态、事件推理能力的并发系统规约语言.目前,SE-LTL的模型检测算法依然是显式的,状态空间爆炸是检测的主要困难.对SE-LTL引入一种有界模型检测技术,该技术将SE-LTL模型检测归约为命题公式的可满足性问题,避免了基于二叉图方法中状态空间的快速增长,加速了验证过程.对SE-LTL-X进一步在该技术中集成stuttering等价技术.实验结果表明该集成有效地降低了验证时间. 相似文献
2.
模型检验是一种自动化验证技术,其应用主要的困难在于状态空间爆炸问题.针对构件组合形成的状态空间爆炸问题,结合构件抽象组合原理及反例引导的抽象精化框架,提出了一种测试用例自动生成的方法.根据某个待集成构件抽象已集成的其他构件,并通过组合各个抽象构件生成抽象组合模型.利用模型检验工具对组合模型进行集成测试,生成抽象测试用例,再通过精化得到原模型对应的具体测试用例.实验结果表明该方法减小了状态空间,在一定程度上减缓了状态空间爆炸的问题. 相似文献
3.
4.
模型检测因其自动化程度高、能够提供反例路径等优势,被广泛应用于Web服务组合的兼容性验证。本文针对模型检测过程中存在的状态爆炸问题,在传统的模型检测方法中引入谓词抽象和精化技术,提出了一种针对Web服务组合的抽象精化验证框架。使用谓词抽象技术对原子Web服务抽象建模,将各Web服务抽象模型组合成组合抽象模型;将模型检测后得到的反例在各原子Web服务上做投影操作,对投影反例进行确认;对产生伪反例的Web服务抽象模型进行精化,生成新的组合抽象模型,再次对性质进行验证。最后通过实例分析说明基于抽象精化技术的Web服务组合验证框架在缓解状态爆炸问题上的可行性。 相似文献
5.
6.
基于分层模型的网络安全策略逐级求精算法 总被引:4,自引:0,他引:4
基于策略的安全防护技术是当前网络安全研究的重点之一,但其中的抽象策略求精问题一直没有得到很好解决,从而导致基于策略的安全应用需要人工干预配置策略.本文基于安全策略的分层管理模型,提出了一个集目标求精和实体求精为一体的安全策略逐级求精算法.该算法首先通过目标求精将抽象策略转化为系统应执行的安全行为,然后通过实体求精确定安全行为的执行环境,从而将抽象策略转化为系统可理解和可执行的操作规则,解决了策略求精问题. 相似文献
7.
Web服务组合现已成为跨组织业务流程集成的关键技术,然而在松耦合开发模式和开放的互联网运行环境下,其正确性、可靠性、安全性等可信性质难以得到保证。为解决该问题,提出一种Web服务组合形式化验证方法,将基于图状反例向导的抽象与精化方法应用于多主体系统( MAS)模型检测工具( MCTK)中,大幅缓解模型检测的状态爆炸问题,从理论上证明该验证方法的正确性。实验通过将银行贷款风险评估系统转换成MCTK描述的MAS,并对比抽象前后的模型检测代价,结果显示,基于抽象的Web服务验证方法明显优于未采用抽象技术的验证方法。 相似文献
8.
9.
10.
有界模型检测的优化 总被引:2,自引:1,他引:1
G(p)和G(p→F(q))是有界模型检测(bounded model checking,简称BMC)中的两个重要的常用模态算子.对验证G(p)和G(p→F(q))编码转换公式进行优化.通过分析当验证这些模态算子时FSM(finite state machine)的状态转移和线性时序逻辑(linear-time temporal logic,简称LTL)的语义特征.在现有的编码公式的基础上,给出了简洁、高效的递推公式,该公式有利于高效编码成SAT(satisfiability)实例;证明了递推公式和原转换公式的逻辑关系.通过实验比较分析,在生成SAT实例规模和易求解方面都优于BMC中求解这些模态算子的现有的两种重要方法AA_BMC和Timo_BMC.所给出的方法和思想对于BMC中验证其他模态算子时的编码优化也有参考价值. 相似文献
11.
Interpolant Learning and Reuse in SAT-Based Model Checking 总被引:1,自引:0,他引:1
Bounded Model Checking (BMC) is one of the most paradigmatic practical applications of Boolean Satisfiability (SAT). The utilization of SAT in model checking has allowed significant performance gains and, as a consequence, a large number of commercial verification tools now include SAT-based model checkers. Recent work has provided SAT-based BMC with completeness conditions, and this is generally referred to as unbounded model checking (UMC). Among the existing approaches for SAT-based UMC, the utilization of interpolants is among the most effective. Despite their success, interpolants have only been used for identifying a fixed point of the set of reachable states. This paper extends the utilization of interpolants in SAT-based model checking. This is achieved by observing that, under reasonable assumptions, interpolants can be reused, i.e. computed interpolants can be reused at later stages of the model checking process. The paper develops conditions for validity of interpolant reuse. In addition, the paper outlines a new fixed point condition, alternative to the existing interpolant-based fixed point condition. Preliminary practical experience on interpolant learning and reuse is reported. 相似文献
12.
Bounded Model Checking has been recently introduced as an efficient verification method for reactive systems. This technique reduces model checking of linear temporal logic to propositional satisfiability. In this paper we first present how quantified Boolean decision procedures can replace BDDs. We introduce a bounded model checking procedure for temporal logic CTL* which reduces model checking to the satisfiability of quantified Boolean formulas. Our new technique avoids the space blow up of BDDs, and extends the concept of bounded model checking. 相似文献
13.
Accelerating Bounded Model Checking of Safety Properties 总被引:4,自引:0,他引:4
Ofer Strichman 《Formal Methods in System Design》2004,24(1):5-24
Bounded Model Checking based on SAT methods has recently been introduced as a complementary technique to BDD-based Symbolic Model Checking. The basic idea is to search for a counterexample in executions whose length is bounded by some integer k. The BMC problem can be efficiently reduced to a propositional satisfiability problem, and can therefore be solved by SAT methods rather than BDDs. SAT procedures are based on general-purpose heuristics that are designed for any propositional formula. We show how the unique characteristics of BMC invariant formulas (G
p) can be exploited for a variety of optimizations in the SAT checking procedure. Experiments with these optimizations on real designs prove their efficiency in many of the hard test cases, in comparison to both the standard SAT procedure and a BDD-based model checker. 相似文献
14.
Yonit Kesten Amir Pnueli 《International Journal on Software Tools for Technology Transfer (STTT)》2000,2(4):328-342
In spite of the impressive progress in the development of the two main methods for formal verification of reactive systems
– Symbolic Model Checking and Deductive Verification, they are still limited in their ability to handle large systems. It
is generally recognized that the only way these methods can ever scale up is by the extensive use of abstraction and modularization,
which break the task of verifying a large system into several smaller tasks of verifying simpler systems.
In this paper, we review the two main tools of compositionality and abstraction in the framework of linear temporal logic.
We illustrate the application of these two methods for the reduction of an infinite-state system into a finite-state system
that can then be verified using model checking.
The technical contributions contained in this paper are a full formulation of abstraction when applied to a system with both
weak and strong fairness requirements and to a general temporal formula, and a presentation of a compositional framework for
shared variables and its application for forming network invariants. 相似文献
15.
Malay K. Ganai Aarti Gupta Zijiang Yang Pranav Ashar 《International Journal on Software Tools for Technology Transfer (STTT)》2006,8(4-5):387-396
SAT-based Bounded Model Checking (BMC), though a robust and scalable verification approach, still is computationally intensive,
requiring large memory and time. Even with the recent development of improved SAT solvers, the memory limitation of a single
server rather than time can become a bottleneck for doing deeper BMC search for large designs. Distributing computing requirements
of BMC over a network of workstations can overcome the memory limitation of a single server, albeit at increased communication
cost. In this paper, we present (a) a method for distributed SAT over a network of workstations using a Master/Client model
where each Client workstation has an exclusive partition of the SAT problem and uses knowledge of partition topology to communicate
with other Clients, (b) a method for distributing SAT-based BMC using the distributed SAT. For the sake of scalability, at
no point in the BMC computation does a single workstation have all the information. We experimented on a network of heterogeneous
workstations interconnected with a standard Ethernet LAN. To illustrate, on an industrial design with ∼13 K FFs and ∼0.5 million
gates, the non-distributed BMC on a single workstation (with 4 GB memory) ran out of memory after reaching a depth of 120;
on the other hand, our SAT-based distributed BMC over 5 similar workstations was able to go up to 323 steps with a communication
overhead of only 30%. 相似文献
16.
17.
Francesco Alberti Roberto Bruttomesso Silvio Ghilardi Silvio Ranise Natasha Sharygina 《Formal Methods in System Design》2014,45(1):63-109
Lazy abstraction with interpolation-based refinement has been shown to be a powerful technique for verifying imperative programs. In presence of arrays, however, the method suffers from an intrinsic limitation, due to the fact that invariants needed for verification usually contain universally quantified variables, which are not present in program specifications. In this work we present an extension of the interpolation-based lazy abstraction framework in which arrays of unknown length can be handled in a natural manner. In particular, we exploit the Model Checking Modulo Theories framework to derive a backward reachability version of lazy abstraction that supports reasoning about arrays. The new approach has been implemented in a tool, called safari, which has been validated on a wide range of benchmarks. We show by means of experiments that our approach can synthesize and prove universally quantified properties over arrays in a completely automatic fashion. 相似文献
18.
Bing Li Chao Wang Fabio Somenzi 《International Journal on Software Tools for Technology Transfer (STTT)》2005,7(2):143-155
We present an abstraction refinement algorithm for model checking of safety properties that relies exclusively on a SAT solver for checking the abstract model, testing abstract counterexamples on the concrete model, and refinement. Model checking of the abstractions is based on bounded model checking extended with checks for the existence of simple paths that help in deciding passing properties. All minimum-length spurious counterexamples are eliminated in one refinement step by an incremental procedure that combines the analysis of the conflict dependency graph produced by the SAT solver while looking for concrete counterexamples with an effective refinement minimization procedure. 相似文献
19.
This paper presents VyrdMC, a runtime verification tool we are building for concurrent software components. The correctness criterion checked by VyrdMC is refinement: Each execution of the implementation must be consistent with an atomic execution of the specification. VyrdMC combines testing, model checking, and Vyrd, the runtime refinement checker we developed earlier. A test harness first drives the component to a non-trivial state which serves as the starting state for a number of simple, very small multi-threaded test cases. An execution-based model checker explores for each test case all distinct thread interleavings while Vyrd monitors executions for refinement violations. This combined approach has the advantage of improving the coverage of runtime refinement checking at modest additional computational cost, since model checkers are only used to explore thread interleavings of a small, fixed test program. The visibility and detailed checking offered by using refinement as the correctness criterion differentiate our approach from simply being a restricted application of model checking. An important side benefit is the reduction in program instrumentation made possible if VyrdMC is built using a model checker with its own virtual machine, such as Java PathFinder [Guillaume Brat, Klaus Havelund, Seung-Joon Park, and Willem Visser. Model Checking Programs. In IEEE International Conference on Automated Software Engineering (ASE), September 2000]. We are investigating the use of two different model checkers for building VyrdMC: Java PathFinder, an explicit-state model checker and Verisoft, a “stateless” model checker [P. Godefroid. Model Checking for Programming Languages using VeriSoft. In Proceedings of the 24th ACM Symposium on Principles of Programming Languages, pages 174–186, Paris, January 1997]. 相似文献