15353920
Beyond safety: customized SAT-based model checking
Model checking of safety properties has taken a significant lead over nonsafety properties in recent years. To bridge the gap, we propose dedicated SAT-based model checking algorithms for properties beyond safety. Previous bounded model checking (BMC) approaches have relied on either converting such properties to safety checking, or finding proofs by deriving termination criteria using loop-free path analysis. Instead, our approach uses a customized SAT-based formulation for bounded model checking of nonsafety properties, and determines the completeness bounds for liveness using unbounded SAT-based analysis. Our main contributions are: 1) Customized property translations for LTL formulas for BMC, with novel features that utilize partitioning, learning, and incremental formulation. Customized translations not only improve the BMC performance significantly in comparison to standard monolithic LTL translations, but also allow efficient derivation and use of completeness bounds. Though we discuss the translation schemas for liveness, they can be easily extended to handle other LTL properties as well. 2) Customized formulations for determining completeness bounds for liveness using SAT-based unbounded model checking (UMC) rather than using loop-free path analysis. These formulations comprise greatest fixed-point and least fixed-point computations to efficiently handle nested properties using SAT-based quantification approaches. We show the effectiveness of our overall approach for checking liveness on public benchmarks and several industry designs.
6555974
Lazy constraints and SAT heuristics for proof-based abstraction
SAT proof analysis techniques have been used recently with BMC in order to generate proof-based abstractions that preserve the correctness of the property up to a certain depth. In this paper, we propose various techniques for handling BMC constraints that are targeted at reducing the size of the abstract model while preserving bounded correctness. We propose lazy constraints, where the idea is to delay propagation of certain implied values without modifying a standard SAT solver. We propose different methods for automatic use of lazy constraints in SAT-based BMC. Their use can be regarded as a heuristic, which typically leads to significant reduction in the size of the abstract model, frequently accompanied by an overall performance improvement. We also use SAT proof analysis to loosen the user-specified environmental constraints, in order to generate smaller abstract models for conservative verification. We briefly describe other SAT-based heuristics for reducing the size of the abstract model. We have implemented our techniques in a prototype verification platform, and demonstrate their effectiveness on several large industry designs.
10395010
Abstraction and BDDs Complement SAT-Based BMC in DiVer
Bounded Model Checking (BMC) based on Boolean Satisfiability (SAT) procedures has recently gained popularity for finding bugs in large designs. However, due to its incompleteness, there is a need to perform deeper searches for counterexamples, or a proof by induction where possible. The DiVer verification platform uses abstraction and BDDs to complement BMC in the quest for completeness. We demonstrate the effectiveness of our approach in practice on industrial designs.
11038357
Reasoning About Threads Communicating via Locks
We propose a new technique for the static analysis of concurrent programs comprised of multiple threads. In general, the problem is known to be undecidable even for programs with only two threads but where the threads communicate using CCS-style pairwise rendezvous [11]. However, in practice, a large fraction of concurrent programs can either be directly modeled as threads communicating solely using locks or can be reduced to such systems either by applying standard abstract interpretation techniques or by exploiting separation of control from data. For such a framework, we show that for the commonly occurring case of threads with nested access to locks, the problem is efficiently decidable. Our technique involves reducing the analysis of a concurrent program with multiple threads to individually analyzing augmented versions of the given threads. This not only yields decidability but also avoids construction of the state space of the concurrent program at hand and thus bypasses the state explosion problem making our technique scalable. We go on to show that for programs with threads that have non-nested access to locks, the static analysis problem for programs with even two threads becomes undecidable even for reachability, thus sharpening the result of [11]. As a case study, we consider the Daisy file system [1] which is a benchmark for analyzing the efficacy of different methodologies for debugging concurrent programs and provide results for the detection of several bugs.
8920735
Partition-based decision heuristics for image computation using SAT and BDDs
Methods based on Boolean satisfiability (SAT) typically use a conjunctive normal form (CNF) representation of the Boolean formula, and exploit the structure of the given problem through use of various decision heuristics and implication methods. We propose a new decision heuristic based on separator-set induced partitioning of the underlying CNF graph. It targets those variables whose choice generates clause partitions with disjoint variable supports. This can potentially improve performance of SAT applications by decomposing the problem dynamically within the search. In the context of a recently proposed image computation method combining SAT and BDDs, this results in simpler BDD subproblems. We provide algorithms for CNF partitioning - one based on a clause-variable dependency matrix, and another based on standard hypergraph partitioning techniques, and also for the use of partitioning information in decision heuristics for SAT. The effectiveness of the proposed partition-based heuristic is shown with practical results for reachability analysis of benchmark sequential circuits.
600527
Learning from BDDs in SAT-based bounded model checking
Bounded Model Checking (BMC) based on Boolean Satisfiability (SAT) procedures has recently gained popularity as an alternative to BDD-based model checking techniques for finding bugs in large designs. In this paper, we explore the use of learning from BDDs, where learned clauses generated by BDD-based analysis are added to the SAT solver, to supplement its other learning mechanisms. We propose several heuristics for guiding this process, aimed at increasing the usefulness of the learned clauses, while reducing the overheads. We demonstrate the effectiveness of our approach on several industrial designs, where BMC performance is improved and the design can be searched up to a greater depth by use of BDD-based learning.
17058061
Sequential and Parallel Algorithms for Embedding Problems on Classes of Partial k-Trees
We present sequential and parallel algorithms for various embedding problems on bounded degree partial k-trees and k-connected partial k-trees; these include subgraph isomorphism and topological embedding, known to be NP-complete for general partial k-trees. As well as contributing to our understanding of the types of graphs for which these problems are tractable, this paper introduces methods for solving problems on graphs. In particular, we make use of the tree-decomposition of the graph to apply techniques used to solve problems on trees to solve problems on partial k-trees.
13854955
Modeling Interactive Web Sources for Information Mediation
We propose a method for modeling complex Web sources that have active user interaction requirements. Here "active" refers to the fact that certain information in these sources is only reachable through interactions like filling out forms or clicking on image maps. Typically, the former interaction can be automated by wrapper software (e.g., using parameterized urls or post commands) while the latter cannot and thus requires explicit user interaction. We propose a modeling technique for such interactive Web sources and the information they export, based on so-called interaction diagrams. The nodes of an interaction diagram model sources and their exported information, whereas edges model transitions and their interactions. The paths of a diagram correspond to sequences of interactions and allow to derive the various query capabilities of the source. Based on these, one can determine which queries sire supported by a source and derive query plans with minimal user interaction. This technique can be used offline to support design and implementation of wrappers, or at runtime when the mediator generates query plans against such sources.
607185
Localization using evolution strategies in sensornets
With the emergence of wireless sensor networks and pervasive computing, innovative location-aware technologies and services are being investigated. Several iterative approaches employing distributed computations over sensors have been proposed in the literature for locating all the sensor nodes in the network. Due to their iterative nature these techniques are inefficient in terms of power, a very precious resource in sensor networks. This paper presents a novel power efficient approach aimed at identifying the locations of all the nodes in a sensor network given the location of a small subset of nodes. The technique, using evolution strategies, is independent of the ranging method used to estimate distances between nodes and involves sink nodes in the computation. The proposed approach provides substantial energy savings over existing techniques while providing comparable accuracy, and requires the presence of at least one neighbor for each sensor node compared to at least 3 neighbors for most of the existing techniques
5958805
Selective and authentic third-party distribution of XML documents
Third-party architectures for data publishing over the Internet today are receiving growing attention, due to their scalability properties and to the ability of efficiently managing large number of subjects and great amount of data. In a third-party architecture, there is a distinction between the Owner and the Publisher of information. The Owner is the producer of information, whereas Publishers are responsible for managing (a portion of) the Owner information and for answering subject queries. A relevant issue in this architecture is how the Owner can ensure a secure and selective publishing of its data, even if the data are managed by a third-party, which can prune some of the nodes of the original document on the basis of subject queries and access control policies. An approach can be that of requiring the Publisher to be trusted with regard to the considered security properties. However, the serious drawback of this solution is that large Web-based systems cannot be easily verified to be secure and can be easily penetrated. For these reasons, we propose an alternative approach, based on the use of digital signature techniques, which does not require the Publisher to be trusted. The security properties we consider are authenticity and completeness of a query response, where completeness is intended with regard to the access control policies stated by the information Owner. In particular, we show that, by embedding in the query response one digital signature generated by the Owner and some hash values, a subject is able to locally verify the authenticity of a query response. Moreover, we present an approach that, for a wide range of queries, allows a subject to verify the completeness of query results.
25659803
BIRN-M: a semantic mediator for solving real-world neuroscience problems
A goal of the Biomedical Informatics Research Network (birn) project is to develop a multi-institution information management system for Neurosciences to gain a deeper understanding of several neurological disorders. Each institution specializes in a different subdiscipline and produces a database of its experimental or computationally derived data; a mediator module performs semantic integration over the databases to enable neuroscientists to perform analyses that could not be done from any single institution’s data. The overall system architecture of the birn system is that of a wrapper-mediator system. The information sources are various relational sources including Oracle 9i having userdefined packages, Oracle 8i with the Spatial Data Cartridge, and databases made available over the web. Sources also include computational resources that need to be “run” to produce data. A source can be either accessed directly by the mediator, or through a middleware called the Storage Resource Broker (SRB) to shield the mediator from keeping low-level information like data location and user authentication information, and from large object handling. Wrappers handle source registration, schema mapping, and translation from the mediator’s logic queries to the corresponding sql or web request. birn-m also admits knowledge sources, which host ontologies and domain-specific general knowledge in the form of logic rules. birn-m maintains a registry with semantic schemas from all sources, integrated views defined in a GAV fashion, and source query capabilities as binding patterns and special predicates or functions admissible by it. The registry also records the types of data a client can handle, and has an API for interactive custom-built clients.