Abstractions for hybrid systems

We present a procedure for constructing sound finite-state discrete abstractions of hybrid systems. This procedure uses ideas from predicate abstraction to abstract the discrete dynamics and qualitative reasoning to abstract the continuous dynamics of the hybrid system. It relies on the ability to decide satisfiability of quantifier-free formulas in some theory rich enough to encode the hybrid system. We characterize the sets of predicates that can be used to create high quality abstractions and we present new approaches to discover such useful sets of predicates. Under certain assumptions, the abstraction procedure can be applied compositionally to abstract a hybrid system described as a composition of two hybrid automata. We show that the constructed abstractions are always sound, but are relatively complete only under certain assumptions.     

A Goal-Dependent Abstraction for Legal Reasoning by Analogy

This paper presents a new algorithm to find an appropriate similarityunder which we apply legal rules analogically. Since there may exist a lotof similarities between the premises of rule and a case in inquiry, we haveto select an appropriate similarity that is relevant to both thelegal rule and a top goal of our legal reasoning. For this purpose, a newcriterion to distinguish the appropriate similarities from the others isproposed and tested. The criterion is based on Goal-DependentAbstraction (GDA) to select a similarity such that an abstraction basedon the similarity never loses the necessary information to prove the ground (purpose of legislation) of the legal rule. In order to cope withour huge space of similarities, our GDA algorithm uses some constraintsto prune useless similarities.     

Efficient Verification of Sequential and Concurrent C Programs

There has been considerable progress in the domain of software verification over the last few years. This advancement has been driven, to a large extent, by the emergence of powerful yet automated abstraction techniques such as predicate abstraction. However, the state-space explosion problem in model checking remains the chief obstacle to the practical verification of real-world distributed systems. Even in the case of purely sequential programs, a crucial requirement to make predicate abstraction effective is to use as few predicates as possible. This is because, in the worst case, the state-space of the abstraction generated (and consequently the time and memory complexity of the abstraction process) is exponential in the number of predicates involved. In addition, for concurrent programs, the number of reachable states could grow exponentially with the number of components. We attempt to address these issues in the context of verifying concurrent (message-passing) C programs against safety specifications. More specifically, we present a fully automated compositional framework which combines two orthogonal abstraction techniques (predicate abstraction for data and action-guided abstraction for events) within a counterexample-guided abstraction refinement scheme. In this way, our algorithm incrementally increases the granularity of the abstractions until the specification is either established or refuted. Additionally, a key feature of our approach is that if a property can be proved to hold or not hold based on a given finite set of predicates $\mathcal{P}$ , the predicate refinement procedure we propose in this article finds automatically a minimal subset of $\mathcal{P}$ that is sufficient for the proof. This, along with our explicit use of compositionality, delays the onset of state-space explosion for as long as possible. We describe our approach in detail, and report on some very encouraging experimental results obtained with our tool MAGIC.     

基于符号模拟和约束逻辑编程的RTL级Verilog谓词抽象方法

利用人工智能最新研究成果--约束逻辑编程对Verilog描述进行谓词抽象,并与目前基于SAT的方法进行了比较.首先通过符号模拟建立Verilog的形式化模型,然后结合要抽象的谓词,将谓词抽象问题转化为约束逻辑编程问题并进行求解.该方法的优点是在计算抽象系统时,不需要像基于SAT的方法那样将字级约束打散成位级约束,求解效率显著提高;提供了一个统一的框架用于描述各种约束.实验结果表明,与基于SAT的抽象技术相比,基于约束逻辑编程的抽象方法的求解速度有显著提高.     

Planning with abstraction based on partial predicate mappings

Planning with abstraction is an act of finding an abstract plan that can be instantiated into a concrete plan for a given planning problem. It is very important for an abstract planning system to satisfy a property, calledDownward-Solution Property (DSP), that any abstract plan can always be instantiated into a concrete plan. J. D. Tenenberg has proposed a framework for constructing a planning system satisfying DSP. The system is constructed by abstracting operators under a givenpredicate mapping f to obtain abstract operators. Intuitively speaking, the predicate mapping corresponds to an inheritance hierarchy of concepts with which the planning is concerned. However, the condition for abstracting operators is so strong that there exist many cases whereonly a few abstract operators are obtained. Consequently, the system often generates only a very small abstract search space, and therefore fails to find a plan for a given problem at concrete level. The aim of this paper is to provide a new revised framework according to which we can construct a more flexible abstract planning system still preserving DSP. For this purpose, we introduce a notion ofpartial predicate mapping. Partial predicate mappings are computed from concrete operators andf. Intuitively, computing them corresponds to refiningf into mappings under which it is possible to obtain more number of abstract operators. Furthermore, some experimental results show that using our abstraction based on partial predicaate mappings is useful to improve planning efficiency.     

Abstracting for Dimensionality Reduction in Text Classification

There is a growing interest in efficient models of text mining and an emergent need for new data structures that address word relationships. Detailed knowledge about the taxonomic environment of keywords that are used in text documents can provide valuable insight into the nature of the subject matter contained therein. Such insight may be used to enhance the data structures used in the text data mining task as relationships become usefully apparent. A popular scalable technique used to infer these relationships, while reducing dimensionality, has been Latent Semantic Analysis. We present a new approach, which uses an ontology of lexical abstractions to create abstraction profiles of documents and uses these profiles to perform text organization based on a process that we call frequent abstraction analysis. We introduce TATOO, the Text Abstraction TOOlkit, which is a full implementation of this new approach. We present our data model via an example of how taxonomically derived abstractions can be used to supplement semantic data structures for the text classification task.     

Compositional Abstractions of Hybrid Control Systems

Abstraction is a natural way to hierarchically decompose the analysis and design of hybrid systems. Given a hybrid control system and some desired properties, one extracts an abstracted system while preserving the properties of interest. Abstractions of purely discrete systems is a mature area, whereas abstractions of continuous systems is a recent activity. In this paper we present a framework for abstraction that applies to discrete, continuous, and hybrid systems. We introduce a composition operator that allows to build complex hybrid systems from simpler ones and show compatibility between abstractions and this compositional operator. Besides unifying the existing methodologies we also propose constructions to obtain abstractions of hybrid control systems.     

模型检验中抽象技术研究综述

在模型检验中,抽象技术是解决状态空间爆炸问题的有效方法之一。论文描述了模型检验对抽象模型的基本要求,给出了抽象模型的定义及其评价指标,对抽象技术和自动化的抽象精化技术的主要方法及其研究进展作了比较深入、全面的综述,并讨论了抽象技术今后的发展方向。     

Aspects of abstraction in software development

Abstraction is a fundamental tool of human thought in every context. This essay briefly reviews some manifestations of abstraction in everyday life, in engineering and mathematics, and in software and system development. Vertical and horizontal abstraction are distinguished and characterised. The use of vertical abstraction in top-down and bottom-up program development is discussed, and also, the use of horizontal abstraction in one very different approach to program design. The ubiquitous use of analogical models in software is explained in terms of analytical abstractions. Some aspects of the practical use of abstraction in the development of computer-based systems are explored. The necessity of multiple abstractions is argued from the essential nature of abstraction, which by definition focuses on some concerns at the expense of discarding others. Finally, some general recommendations are offered for a consciously thoughtful use of abstraction in software development.     

Abstractions of data types

The use of abstraction in the context of abstract data types, is investigated. Properties to be checked are formulas in a first order logic under Kleene's 3-valued interpretation. Abstractions are defined as pairs consisting of a congruence and a predicate interpretation. Three types of abstractions are considered,∀∀, ∀∃ and ∃^0,1∀, and for each of them corresponding property preservation results are established. An abstraction refinement property is also obtained. It shows how one can pass from an existing abstraction to a (less) finer one. Finally, equationally specified abstractions in the context of equationally specified abstract data types are discussed and exemplified.On leave from the Department of Computer Science, “Al. I. Cuza” University, Iaşi 740083, RomaniaThe research reported in this paper was partially supported by the program ECO-NET 08112WJ/2004-2005 and by the National University Research Council of Romania, grants CNCSIS 632(28)/2004 and CNCSIS 632(50)/2005.     

The software model checker Blast

Blast is an automatic verification tool for checking temporal safety properties of C programs. Given a C program and a temporal safety property, Blast either statically proves that the program satisfies the safety property, or provides an execution path that exhibits a violation of the property (or, since the problem is undecidable, does not terminate). Blast constructs, explores, and refines abstractions of the program state space based on lazy predicate abstraction and interpolation-based predicate discovery. This paper gives an introduction to Blast and demonstrates, through two case studies, how it can be applied to program verification and test-case generation. In the first case study, we use Blast to statically prove memory safety for C programs. We use CCured, a type-based memory-safety analyzer, to annotate a program with run-time assertions that check for safe memory operations. Then, we use Blast to remove as many of the run-time checks as possible (by proving that these checks never fail), and to generate execution scenarios that violate the assertions for the remaining run-time checks. In our second case study, we use Blast to automatically generate test suites that guarantee full coverage with respect to a given predicate. Given a C program and a target predicate p, Blast determines the program locations q for which there exists a program execution that reaches q with p true, and automatically generates a set of test vectors that cause such executions. Our experiments show that Blast can provide automated, precise, and scalable analysis for C programs.     

Infinite-state invariant checking with IC3 and predicate abstraction

We address the problem of verifying invariant properties on infinite-state systems. We present a novel approach, IC3ia, for generalizing the IC3 invariant checking algorithm from finite-state to infinite-state transition systems, expressed over some background theories. The procedure is based on a tight integration of IC3 with Implicit Abstraction, a form of predicate abstraction that expresses abstract paths without computing explicitly the abstract system. In this scenario, IC3 operates only at the Boolean level of the abstract state space, discovering inductive clauses over the abstraction predicates. Theory reasoning is confined within the underlying SMT solver, and applied transparently when performing satisfiability checks. When the current abstraction allows for a spurious counterexample, it is refined by discovering and adding a sufficient set of new predicates. Importantly, this can be done in a completely incremental manner, without discarding the clauses found in the previous search. The proposed approach has two key advantages. First, unlike previous SMT generalizations of IC3, it allows to handle a wide range of background theories without relying on ad-hoc extensions, such as quantifier elimination or theory-specific clause generalization procedures, which might not always be available and are often highly inefficient. Second, compared to a direct exploration of the concrete transition system, the use of abstraction gives a significant performance improvement, as our experiments demonstrate.     

Theorem proving with abstraction

A class of mappings called abstractions are defined, and examples of abstractions are given. These functions map a set S of clauses onto a possibly simpler set T of clauses. Also, resolution proofs from S map onto possibly simpler resolution proofs from T. In order to search for a proof of a clause C from S, it suffices to search for a proof from T and attempt to invert the abstraction mapping to obtain a proof of C from S. Some theorem proving strategies based on this idea are presented. Most of these strategies are complete. A method of using more than one abstraction at the same time is also presented. This requires the use of ‘multiclauses’, which are multisets of literals, and associated ‘m-abstraction mappings’ on multiclauses. Certain abstractions are especially interesting, because they correspond to particular interpretations of the set S of clauses. The use of abstractions permits the advantages of set-of-support strategies to be realized in arbitrary complete non set-of-support resolution strategies.     

Abstractions of Hamiltonian control systems

Given a control system and a desired property, an abstracted system is a reduced system that preserves the property of interest while ignoring modeling detail. In previous work, abstractions of linear and nonlinear control systems were considered while preserving reachability properties. In this paper, we consider the abstraction problem for Hamiltonian control systems, where, in addition to the property of interest we also preserve the Hamiltonian structure of the control system. We show how the Hamiltonian structure of control systems can be exploited to simplify the abstraction process. We then focus on local accessibility preserving abstractions, and provide conditions under which local accessibility properties of the abstracted Hamiltonian system are equivalent to the local accessibility properties of the original Hamiltonian control system.     

Can digital games help us identify our skills to manage abstractions?

In this work we present our progress in the field of Intelligent User Profiling. Our objective is to build a user profile that captures users’ skills rather than classical users’ interests. Thus, we propose a novel approach to learn users’ skills by observing their behavior during a very common activity: playing games. Specifically, we automatically identify users’ skills to manage abstractions by using digital games. Abstraction skills identification is important because it is related to several behavioral tendencies such as career preferences, aptitudes, and learning styles. Traditional skills identification is based on questionnaires whose application implies many complications, including non-intentional influences in the way questions are formulated, difficulty to motivate people to fill them out, and lack of awareness of the consequences or future uses of questionnaires. To address these limitations, we built a user profile that collects users’ actions when playing digital games. Then, we built and trained a Hierarchical Naive Bayes network to infer users’ skills to manage abstractions. The experiments carried out show that digital games can help us to identify abstraction skills with a promising accuracy.     

Predicate diagrams for the verification of real-time systems

This article discusses a new format of predicate diagrams for the verification of real-time systems. We consider systems that are defined as extended timed graphs, a format that combines timed automata and constructs for modelling data, possibly over infinite domains. Predicate diagrams are succinct and intuitive representations of Boolean abstractions. They also represent an interface between deductive tools used to establish the correctness of an abstraction, and model checking tools that can verify behavioral properties of finite-state models. The contribution of this article is to extend the format of predicate diagrams to timed systems. We establish a set of verification conditions that are sufficient to prove that a given predicate diagram is a correct abstraction of an extended timed graph; these verification conditions can often be discharged with SMT solvers such as CVC-lite. Additionally, we describe how this approach extends naturally to the verification of parameterized systems. The formalism is supported by a toolkit, and we demonstrate its use at the hand of Fischer’s real-time mutual-exclusion protocol.     

Conceptual design, manufacturability evaluation and preliminary process planning using function-form relationships in stamped metal parts

A large number of design decisions are made during the conceptual design of a part. However, there are few representation and reasoning tools for decision support during conceptual design. The conceptual design stage is characterized by a lack of complete geometric information. Existing geometric modelers require complete geometric information, while a functional reasoning methodology using a <verb, noun > representation is typically too terse. In this paper, we present a new representation called sketching abstraction for conceptual design, using the function-form relations in a design. The functionally critical part of the geometry is presented using a set of functional features, while the rest of the geometry is abstracted as a set of linkages. Part functionality is correlated with the sketching abstraction using data structures called function-form matrices. The sketching abstraction is annotated using a set of primitives, and a set of grammar rules are used to extract canonical relationships between the functional features. The sketching abstraction can be used for extracting designs that are geometrically dissimilar but functionally similar, thus providing the designer with ideas for design alternatives. The sketching abstraction can also be used to carry out domain-dependent manufacturability evaluation checks. A further use of sketching abstractions is to initiate the development of a process plan for manufacturing. Sketching abstractions are related to the solid model of a part. Thus, this representation provides a link between pure functional and pure geometric representations. The domain of application is stamped metal parts. We present the part functionality and the features used in this domain. We also illustrate the use of sketching abstractions for conceptual design, manufacturability evaluation and preliminary process planning.