Heuristics for model checking Java programs

Model checking of software programs has two goals – the verification of correct software and the discovery of errors in faulty software. Some techniques for dealing with the most crucial problem in model checking, the state space explosion problem, concentrate on the first of these goals. In this paper we present an array of heuristic model checking techniques for combating the state space explosion when searching for errors. Previous work on this topic has mostly focused on property-specific heuristics closely related to particular kinds of errors. We present structural heuristics that attempt to explore the structure (branching structure, thread interdependency structure, abstraction structure) of a program in a manner intended to expose errors efficiently. Experimental results show the utility of this class of heuristics. In contrast to these very general heuristics, we also present very lightweight techniques for introducing program-specific heuristic guidance.     

Partial model checking via abstract interpretation

Nowadays the emphasis in software engineering research is on the evolution of pre-existing sub-systems and component development. In this context, we tackle the following problem: given the formal specification of the system P, already built, how to characterize possible collaborators of P, through a given communication interface L, to the satisfaction of a given property φ. We propose an abstract interpretation framework to reason about this problem in a systematic way. Given P and L, the set of all transition systems that, composed with P and restricted by L, satisfy φ, is modeled as the abstract semantics of φ, parametric with respect to P and L. We show that the algorithm developed by Andersen (1995) [1] can be formulated in our framework.     

LTL model checking for communicating concurrent programs

Innovations in Systems and Software Engineering - We present in this paper a new approach to the static analysis of concurrent programs with procedures. To this end, we model multi-threaded...     

A framework for relating syntactic and semantic model differences

Model differencing is an important activity in model-based development processes. Differences need to be detected, analyzed, and understood to evolve systems and explore alternatives. Two distinct approaches have been studied in the literature: syntactic differencing, which compares the concrete or abstract syntax of models, and semantic differencing, which compares models in terms of their meaning. Syntactic differencing identifies change operations that transform the syntactical representation of one model to the syntactical representation of the other. However, it does not explain their impact on the meaning of the model. Semantic model differencing is independent of syntactic changes and presents differences as elements in the semantics of one model but not the other. However, it does not reveal the syntactic changes causing these semantic differences. We define Diffuse, a language-independent, abstract framework, which relates syntactic change operations and semantic difference witnesses. We formalize fundamental relations of necessary, exhibiting, and sufficient sets of change operations and analyze their properties. We further demonstrate concrete instances of the Diffuse framework for three different popular modeling languages, namely class diagrams, activity diagrams, and feature models. The Diffuse framework provides a novel foundation for combining syntactic and semantic differencing.     

A semantic framework of the multilevel secure relational model

A multilevel relational database represents information in a multilevel state of the world, which is the knowledge of the truth value of a statement with respect to a level in a security lattice. The authors develop a semantic framework of the multilevel secure relational model with tuple-level labelling, which formalizes the notion of validity in multilevel relational databases. They also identify the multilevel security properties that precisely characterize the validity of multilevel relational databases, which can be maintained efficiently. Finally, they give an update semantics of the multilevel secure relational model that preserves both integrity and secrecy     

程序模型检测的两阶段框架

模型检测是一种对有限状态变迁系统验证其时态逻辑性质的重要方法,可以弥补测试技术的不足。基于流分析的程序模型检测和基于语言转换的程序模型检测是当前程序模型检测的主要方法,它们都存在各自的局限性。基于对这两种程序模型检测方法各自优缺点的分析,提出了一种两阶段程序模型检测框架,通过结合两种程序模型检测方法,可有效提高程序模型检测对较大规模程序的适用性。     

A framework for checking proofs naturally

We propose a logical framework, called Natural Framework (NF), which supports formal reasoning about computation and logic (CAL) on a computer. NF is based on a theory of Judgments and Derivations. NF is designed by observing how working mathematical theories are created and developed. Our observation is that the notions of judgments and derivations are the two fundamental notions used in any mathematical activity. We have therefore developed a theory of judgments and derivations and designed a framework in which the theory provides a uniform and common play ground on which various mathematical theories can be defined as derivation games and can be played, namely, can write and check proofs. NF is equipped with a higher-order intuitionistic logic and derivations (proofs) are described following Gentzen’s natural deduction style. NF is part of an interactive computer environment CAL and it is also referred to as NF/CAL. CAL is written in Emacs Lisp and it is run within a special buffer of the Emacs editor. CAL consists of user interface, a general purpose parser and a checker for checking proofs of NF derivation games. NF/CAL system has been successfully used as an education system for teaching CAL for undergraduate students for about 8 years. We will give an overview of the NF/CAL system both from theoretical and practical sides.     

Towards scalable model checking of self-stabilizing programs

Existing approaches for verifying self-stabilization with a symbolic model checker have relied on the use of weak fairness. We point out that this approach has limited scalability. To overcome this limitation, first, we show that if self-stabilization is possible without fairness then the cost of verifying self-stabilization is substantially lower. In fact, we observe from several case studies that the cost of verification under weak fairness is more than 1000 times that of the cost without fairness.     

Boolean and Cartesian abstraction for model checking C programs

We show how to attack the problem of model checking a C program with recursive procedures using an abstraction that we formally define as the composition of the Boolean and the Cartesian abstractions. It is implemented through a source-to-source transformation into a Boolean C program; we give an algorithm to compute the transformation with a cost that is exponential in its theoretical worst-case complexity but feasible in practice.     

A semantic framework for open processes

We propose a general methodology for analysing the behaviour of open systems modelled as coordinators, i.e., open terms of suitable process calculi. A coordinator is understood as a process with holes or placeholders where other coordinators and components (i.e., closed terms) can be plugged in, thus influencing its behaviour. The operational semantics of coordinators is given by means of a symbolic transition system, where states are coordinators and transitions are labeled by spatial/modal formulae expressing the potential interaction that plugged components may enable. Behavioural equivalences for coordinators, like strong and weak bisimilarities, can be straightforwardly defined over such a transition system. Different from other approaches based on universal closures, i.e., where two coordinators are considered equivalent when all their closed instances are equivalent, our semantics preserves the openness of the system during its evolution, thus allowing dynamic instantiation to be accounted for in the semantics. To further support the adequacy of the construction, we show that our symbolic equivalences provide correct approximations of their universally closed counterparts, coinciding with them over closed components. For process calculi in suitable formats, we show how tractable symbolic semantics can be defined constructively using unification.     

A framework for defining semantic metrics

Software metrics are measures of particular characteristics found in the software. Research in this area seeks to identify relationships between software characteristics and software engineering processes. Most software metrics are based on program structure and are determined statically. This article presents a framework by which semantic information can be quantified. By semantic information, we mean information concerning what occurs internally during execution as program states are created.     

A semantic framework for metamodel-based languages

In the model-based development context, metamodel-based languages are increasingly being defined and adopted either for general purposes or for specific domains of interest. However, meta-languages such as the MOF (Meta Object Facility)—combined with the OCL (Object Constraint Language) for expressing constraints—used to specify metamodels focus on structural and static semantics but have no built-in support for specifying behavioral semantics. This paper introduces a formal semantic framework for the definition of the semantics of metamodel-based languages. Using metamodelling principles, we propose several techniques, some based on the translational approach while others based on the weaving approach, all showing how the Abstract State Machine formal method can be integrated with current metamodel engineering environments to endow language metamodels with precise and executable semantics. We exemplify the use of our semantic framework by applying the proposed techniques to the OMG metamodelling framework for the behaviour specification of the Finite State Machines provided in terms of a metamodel.     

A semantic framework for textual data enrichment

In this work we present a semantic framework suitable of being used as support tool for recommender systems. Our purpose is to use the semantic information provided by a set of integrated resources to enrich texts by conducting different NLP tasks: WSD, domain classification, semantic similarities and sentiment analysis. After obtaining the textual semantic enrichment we would be able to recommend similar content or even to rate texts according to different dimensions. First of all, we describe the main characteristics of the semantic integrated resources with an exhaustive evaluation. Next, we demonstrate the usefulness of our resource in different NLP tasks and campaigns. Moreover, we present a combination of different NLP approaches that provide enough knowledge for being used as support tool for recommender systems. Finally, we illustrate a case of study with information related to movies and TV series to demonstrate that our framework works properly.     

A framework for automatic semantic video annotation

Hypermedia composite templates define generic structures of nodes and links to be added to a document composition, providing spatio-temporal synchronization semantics. This paper presents EDITEC, a graphical editor for hypermedia composite templates. EDITEC templates are based on the XTemplate 3.0 language. The editor was designed for offering a user-friendly visual approach. It presents a new method that provides several options for representing iteration structures graphically, in order to specify a certain behavior to be applied to a set of generic document components. The editor provides a multi-view environment, giving the user a complete control of the composite template during the authoring process. Composite templates can be used in NCL documents for embedding spatio-temporal semantics into NCL contexts. NCL is the standard declarative language used for the production of interactive applications in the Brazilian digital TV system and ITU H.761 IPTV services. Hypermedia composite templates could also be used in other hypermedia authoring languages offering new types of compositions with predefined semantics.     

An evaluation framework for energy aware buildings using statistical model checking

Cyber-physical systems are to be found in numerous applications throughout society.The principal barrier to develop trustworthy cyber-physical systems is the lack of expressive modelling and specification formalisms supported by efficient tools and methodologies.To overcome this barrier,we extend in this paper the modelling formalism of the tool UPPAAL-SMC to stochastic hybrid automata,thus providing the expressive power required for modelling complex cyber-physical systems.The application of Statistical Model Checking provides a highly scalable technique for analyzing performance properties of this formalisms.A particular kind of cyber-physical systems are Smart Grids which together with Intelligent,Energy Aware Buildings will play a major role in achieving an energy efficient society of the future.In this paper we present a framework in UPPAAL-SMC for energy aware buildings allowing to evaluate the performance of proposed control strategies in terms of their induced comfort and energy profiles under varying environmental settings(e.g.weather,user behavior etc.).To demonstrate the intended use and usefulness of our framework,we present an application to the Hybrid Systems Verification Benchmark.