The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Our goal is the verification of C programs at the source code level using formal proof tools. Programs are specified using annotations such as pre- and post-conditions and global invariants. An original approach is presented which allows to formally prove that a function implementation satisfies its specification and is free of null pointer dereferencing and out-of-bounds array access. The method...
We present a “memory-model-sensitive” approach to validating correctness properties for multithreaded programs. Our key insight is that by specifying both the inter-thread memory consistency model and the intra-thread program semantics as constraints, a program verification task can be reduced to an equivalent constraint solving problem, thus allowing an exhaustive examination of all thread interleavings...
While providing better performance, transparency and expressiveness, the main features of the web technologies such as web caching, session and cookies, dynamically generated web pages etc. may also affect the correct understanding of the web applications running on top of them. From the viewpoint of formal verification and specification-based testing, this suggests that the formal models of the web...
SVM (System Verification Manager) manages the application of verification methods for model-based development of embedded systems by providing integrated representations of requirements, system architecture, models and verification methods. Developed in Java within MATLAB®, SVM supports all types of tools for modelling and verification through an extensible framework of data and coding structures...
Reachability testing is a technique for testing concurrent programs. Reachability testing derives test sequences on-the-fly as the testing process progresses, and can be used to systematically exercise all the behaviors of a program. The main contribution of this paper is a general model for reachability testing. This model allows reachability testing to be applied to many different types of concurrent...
This paper presents a case study of the application of the knowledge-based approach to concurrent systems specification, design and verification. A highly abstract solution to the cache coherence problem is first presented, in the form of a knowledge-based program, that formalises the intuitions underlying the MOESI [Sweazey & Smith, 1986] characterisation of cache coherency protocols. It is shown...
The feature model is a domain/product-line oriented requirements model based on hierarchical structure and explicit variability modeling, and has been adopted by several important software reuse methods. However, with respect to the problem of verification of constraints on features and verification of partially customized feature models, these methods tend to be semi-formal and offer little formal...
A theory of programming is intended to aid the construction of programs that meet their specifications; for such a theory to be useful it should capture (only) the essential aspects of the program’s behaviour, that is only those aspects which one wishes to observe. And it should do so in a mathematically elegant – hence tractable – way.
We show how game semantics of an interesting fragment of Idealised Algol can be represented compositionally by CSP processes. This enables observational equivalence and a range of properties of terms-in-context (i.e. open program fragments) to be checked using the FDR tool. We have built a prototype compiler which implements the representation, and initial experimental results are positive.
In this paper we show that, by translating Alloy formulas to formulas in the language of fork algebras, we obtain a complete, equational, and purely relational calculus for Alloy.
In this paper we present a technique for the Spin tool, inspired by practical experiences with Spin and a FireWire protocol. We show how to guide simulations with Spin, by constructing a special guide process that limits the behaviour of the original system. We set up a theoretical framework in which we prove under some sufficient conditions that the adjusted system (with the added guide process)...
We develop a way of analyzing the behavior of systems modeled using Discrete Time Markov Chains (DTMC). Specifically, we define iLTL, an LTL with linear inequalities on the pmf vectors as atomic propositions. iLTL allows us to express not only properties such as the expected number of jobs or the expected energy consumption of a protocol during a time interval, but also inequalities over such values...
Iterative abstraction refinement has emerged in the last few years as the leading approach to software model checking. In this context Boolean programs are commonly employed as simple, yet useful abstractions from conventional programming languages. In this paper we propose Linear Programs as a finer grained abstraction for sequential programs and propose a model checking procedure for this family...
Software model checking tools based on a Counterexample Guided Abstraction Refinement (CEGAR) framework have attained considerable success in limited domains. However, scaling these approaches to larger programs with more complex data structures and initialization behavior has proven difficult. Explicit-state model checkers making use of states and operational semantics closely related to actual program...
When animating a formal model for validation or test generation purposes, scalability is a key issue. This paper describes a graph-based representation for the operations of state-based formal models. This representation makes it possible to handle large models efficiently and perform a variety of transformations, such as splitting an operation into separate behaviours, implementing various test coverage...
Interface automata is a formal model to be used for describing the temporal interface behaviors of software components. It adopts an alternating approach to design refinement, which is significantly different with the traditional use of automata. In this paper, it is proven that an interface automaton refines another if and only if there exists a special kind of forward simulation between their corresponding...
We present a novel approach for verifying safety properties of finite state machines communicating over unbounded FIFO channels that is based on applying machine learning techniques. We assume that we are given a model of the system and learn the set of reachable states from a sample set of executions of the system, instead of attempting to iteratively compute the reachable states. The learnt set...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.