We introduce a new way of reasoning about invariance in terms of footprints in a program logic for object-oriented components. A footprint of an object-oriented component is formalized as a monadic predicate that describes which objects on the heap can be affected by the execution of the component. Assuming encapsulation, this amounts to specifying which objects of the component can be called. Adaptation of local specifications into global specifications amounts to showing invariance of assertions, which is ensured by means of a form of bounded quantification which excludes references to a given footprint. The new approach is compared to two existing approaches to reason about invariance: separation logic and dynamic frames.

Abstract The basic set-theoretic interpretation of the separating connectives of first-order separation logic allows for an effective, sound and complete axiomatization in a hybrid extension.

The main objective of the International Conference on Software Engineering and Formal Methods (SEFM) is to bring together practitioners and researchers from academia, industry, and government, to advance the state of the art in formal methods, to help in their large-scale application in the software industry, and to encourage their integration with other practical software engineering methods.

This article addresses the long-standing problem of program correctness for programs that describe systems of parallel executing processes. We propose a new method for proving correctness of parallel implementations of high-level models expressed as transition systems. The implementation language underlying the method is based on the concurrency model of actors and active objects. The method defines program correctness in terms of a simulation relation between the transition system that specifies the program semantics of the parallel program and the transition system that is described by the correctness specification. The simulation relation itself abstracts from the fine-grained interleaving of parallel processes by exploiting a global confluence property of the concurrency model of the implementation language considered in this article. As a proof of concept, we apply our method to the correctness of a parallel simulator of multicore memory systems.

Abstract The standard semantics of separation logic is restricted to finite heaps. This restriction already gives rise to a logic which does not satisfy compactness, hence it does not allow for an effective, sound and complete axiomatization. In this paper we therefore study both the general model theory and proof theory of the separation logic of finite and infinite heaps over arbitrary (first-order) models. We show that we can express in the resulting logic finiteness of the models and the existence of both countably infinite and uncountable models. We further show that a sound and complete sequent calculus still can be obtained by restricting the second-order quantification over heaps to first-order definable heaps.

Abstract We discuss integrating abstract data types (ADTs) in the KeY theorem prover by a new approach to model data types using Isabelle/HOL as an interactive back-end, and represent Isabelle theorems as user-defined taclets in KeY. As a case study of this new approach, we reason about Java’s interface using histories, and we prove the correctness of several clients that operate on multiple objects, thereby significantly improving the state-of-the-art of history-based reasoning. Open Science. Includes video material (Bian and Hiep in FigShare, 2021. https://doi.org/10.6084/m9.figshare.c.5413263 ) and a source code artifact (Bian et al. in Zenodo, 2022. https://doi.org/10.5281/zenodo.7079126 ).

Abstract As a particular case study of the formal verification of state-of-the-art, real software, we discuss the specification and verification of a corrected version of the implementation of a linked list as provided by the Java Collection Framework.

Abstract In this paper, we provide a formal explanation of symbolic execution in terms of a symbolic transition system and prove its correctness and completeness with respect to an operational semantics which models the execution on concrete values.We first introduce a formalmodel for a basic programming languagewith a statically fixed number of programming variables. This model is extended to a programming language with recursive procedures which are called by a call-by-value parameter mechanism. Finally, we present a more general formal framework for proving the soundness and completeness of the symbolic execution of a basic object-oriented language which features dynamically allocated variables.

We provide a sound and relatively complete Hoare logic for reasoning about partial correctness of recursive procedures in presence of local variables and the call-by-value parameter mechanism and in which the correctness proofs support contracts and are linear in the length of the program. We argue that in spite of the fact that Hoare logics for recursive procedures were intensively studied, no such logic has been proposed in the literature.

Software libraries, such as the Java Collection Framework, are used by many applications: thus their correctness is of utmost importance. The state-of-the-art KeY system can be used to formally reason about program correctness of Java programs. Recently, KeY has been used to show major flaws in the Java Collection Framework. However, some methods are challenging for verification, namely those involving parameters of interface type. This lecture discussed a new history-based specification method for reasoning about the correctness of clients and arbitrary implementations of interfaces, and the Collection interface in particular.

Abstract As a particular case study of the formal verification of state-of-the-art, real software, we discuss the specification and verification of a corrected version of the implementation of a linked list as provided by the Java Collection framework.

We present a formal translation of a resource-aware extension of the Abstract Behavioral Specification (ABS) language to the functional language Haskell. ABS is an actor-based language tailored to the modeling of distributed systems. It combines asynchronous method calls with a suspend and resume mode of execution of the method invocations. To cater for the resulting cooperative scheduling of the method invocations of an actor, the translation exploits for the compilation of ABS methods Haskell functions with continuations. The main result of this article is a correctness proof of the translation by means of a simulation relation between a formal semantics of the source language and a high-level operational semantics of the target language, i.e., a subset of Haskell. We further prove that the resource consumption of an ABS program extended with a cost model is preserved over this translation, as we establish an equivalence of the cost of executing the ABS program and its corresponding Haskell-translation. Concretely, the resources consumed by the original ABS program and those consumed by the Haskell program are the same, considering a cost model. Consequently, the resource bounds automatically inferred for ABS programs extended with a cost model, using resource analysis tools, are sound resource bounds also for the translated Haskell programs. Our experimental evaluation confirms the resource preservation over a set of benchmarks featuring different asymptotic costs.

This paper describes the development of a parallel simulator of a multicore memory system from a model formalized as a structural operational semantics (SOS). Our implementation uses the Abstract Behavioral Specification (ABS) language, an executable, active object modelling language with a formal semantics, targeting distributed systems. We develop general design patterns in ABS for implementing SOS, and describe their application to the SOS model of multicore memory systems. We show how these patterns allow a formal correctness proof that the implementation simulates the formal operational model and discuss further parallelization and fairness of the simulator.

TimSort is the main sorting algorithm provided by the Java standard library and many other programming frameworks. Our original goal was functional verification of TimSort with mechanical proofs. However, during our verification attempt we discovered a bug which causes the implementation to crash by an uncaught exception. In this paper, we identify conditions under which the bug occurs, and from this we derive a bug-free version that does not compromise performance. We formally specify the new version and verify termination and the absence of exceptions including the bug. This verification is carried out mechanically with KeY, a state-of-the-art interactive verification tool for Java. We provide a detailed description and analysis of the proofs. The complexity of the proofs required extensions and new capabilities in KeY, including symbolic state merging.

No abstract available.

We give two different notions of deadlock for systems based on active objects and futures. One is based on blocked objects and conforms with the classical definition of deadlock by Coffman, Jr. et al. The other one is an extended notion of deadlock based on blocked processes which is more general than the classical one. We introduce a technique to prove deadlock freedom of systems of active objects. To check deadlock freedom an abstract version of the program is translated into Petri nets. Extended deadlocks, and then also classical deadlock, can be detected via checking reachability of a distinct marking. Absence of deadlocks in the Petri net constitutes deadlock freedom of the concrete system.

We present an extension of the actor model with real-time, including deadlines associated with messages, and explicit application-level scheduling policies, e.g.,"earliest deadline first" which can be associated with individual actors. Schedulability analysis in this setting amounts to checking whether, given a scheduling policy for each actor, every task is processed within its designated deadline. To check schedulability, we introduce a compositional automata-theoretic approach, based on maximal use of model checking combined with testing. Behavioral interfaces define what an actor expects from the environment, and the deadlines for messages given these assumptions. We use model checking to verify that actors match their behavioral interfaces. We extend timed automata refinement with the notion of deadlines and use it to define compatibility of actor environments with the behavioral interfaces. Model checking of compatibility is computationally hard, so we propose a special testing process. We show that the analyses are decidable and automate the process using the Uppaal model checker.

Summary Cloud environments have become a standard method for enterprises to offer their applications by means of web services, data management systems, or simply renting out computing resources. In our previous work, we presented how we can use a modeling language together with the new features of JAVA 8 to overcome certain drawbacks of data structures and synchronization mechanisms in parallel applications. We extend this solution into a design pattern that allows application‐specific optimizations in a distributed setting. We validate this integration using our previous case study of the Prime Sieve of Eratosthenes and illustrate the performance improvements in terms of speed‐up and memory consumption. Copyright © 2015 John Wiley & Sons, Ltd.

A software product line describes explicitly the commonalities of and differences between different products in a family of (software) systems. A formalization of these commonalities and differences amounts to reduced development, analysis and maintenance costs in the practice of software engineering. An important feature common to next-generation real-time software systems is the need of application-level control over scheduling for optimized utilization of resources provided by for example many-core and cloud infrastructures. In this paper, we introduce a formal model of real-time software product lines which supports variability in scheduling policies and rigorous and efficient techniques for modular schedulability analysis.

Abstract Delta Modeling is a technique for implementing (software) product lines. Deltas are placed in a partial order which restricts their application and are then sequentially applied to a core product in order to form specific products in the product line. In this paper we explore the semantics of deltas in more detail. We regard them as relations between products and introduce a multimodal logic that may be used for reasoning about their effects. Our main innovation is a modality for partially ordered sets of deltas. We prove completeness results on both the frame level and the model level and demonstrate the logic through an example.

In this paper we present prototype tool-support for the runtime assertion checking of the Java Modeling Language (JML) extended with communication histories specified by attribute grammars. Our tool suite integrates Rascal, a meta programming language and ANTLR, a popular parser generator. Rascal instantiates a generic model of history updates for a given Java program annotated with history specifications. ANTLR is used for the actual evaluation of history assertions.

The complex interactions appearing in service-oriented computing make coordination a key concern in service-oriented systems. In this paper, we present a fault-based method to generate test cases for component connectors from specifications. For connectors, faults are caused by possible errors during the development process, such as wrongly used channels, missing or redundant subcircuits, or circuits with wrongly constructed topology. We give test cases and connectors a unifying formal semantics by using the notion of design, and generate test cases by solving constraints obtained from the specification and faulty connectors. A prototype symbolic test case generator serves to demonstrate the automatizing of the approach.

We apply automata theory to specifying behavioralinterfaces of objects and show how to check schedulabilityand compatibility of real time asynchronous objects.The behavioral interfaces of real time objects specify(the order and timings of) the messages an object maysend and receive. Each object is checked against itsbehavioral interface; first, to guarantee its correct outputbehavior, and second to make sure that every messageit may receive is processed within the designateddeadline (schedulability analysis). Next, we propose anew technique for testing whether every object is usedas expected (i.e., according to its behavioral interface)when combined with other objects (compatibility check).Compatibility additionally implies schedulability in thecontext of the actual system. The analyses are automatedusing the Uppaal model checker.

In this paper, we present a dynamic logic for a propositional version of the agent programming language 3APL. A 3APL agent has beliefs and a plan. The execution of a plan changes an agent's beliefs. Plans can be revised during execution by means of plan revision rules. Due to these plan revision capabilities of 3APL agents, plans cannot be analyzed by structural induction as in for example standard propositional dynamic logic. We propose a dynamic logic that is tailored to handle the plan revision aspect of 3APL. The logic is one for plans that are restricted in a certain way. For this logic, we give a sound and complete axiomatization. Further, we discuss how this logic for restricted 3APL plans can be extended to a logic for non-restricted plans and we discuss some example proofs, using the logic. Finally, we consider the relation between proving properties of 3APL agents and proving properties of procedural programs.

A temporal logic is presented for reasoning about the correctness of timed concurrent constraint programs. The logic is based on modalities which allow one to specify what a process produces as a reaction to what its environment inputs. These modalities provide an assumption/commitment style of specification which allows a sound and complete compositional axiomatization of the reactive behavior of timed concurrent constraint programs.

A coherent description of architectures provides insight, enables communication among different stakeholders and guides complicated (business and ICT) change processes. Unfortunately, so far no architecture description language exists that fully enables integrated enterprise modeling. In this paper we focus on the requirements and design of such a language. This language defines generic, organization-independent concepts that can be specialized or composed to obtain more specific concepts to be used within a particular organisation. It is not our intention to re-invent the wheel for each architectural domain: wherever possible we conform to existing languages or standards such as UML. We complement them with missing concepts, focusing on concepts to model the relationships among architectural domains. The concepts should also make it possible to define links between models in other languages. The relationship between architecture descriptions at the business layer and at the application layer (business-IT alignment) plays a central role.

MoCha is a middleware for distributed communication and collaboration using mobile channels as its medium. Channels allow directed, anonymous, and peer-to-peer communication among entities, while mobility ensures that the structure of their connections can change over time in arbitrary ways. MoCha provides communication mechanisms without requiring central servers or fixed network infrastructures, and it allows exogenous coordination between processes. In this paper we briefly introduce MoCha and discuss the implementation of an important channel type: the asynchronous FIFO mobile channel.

In [5] we introduced a Timed Linda language (T-Linda) whic hwas obtained by a natural timed interpretation of the usual constructs of the Linda model and by including a simple primitive for specifying time-outs. Here we define a denotational model for T-Linda which is based on timed reactive sequences. The correctness of this model is proved w.r.t a notion of observ ables which include finite traces of actions and input/output pairs.

A temporal logic is presented for reasoning about the correctness of timed concurrent constraint programs. The logic is based on epistemic modalities which express either what a process knows at a certain time or what a process believes about the results of the other processes. In terms of these epistemic modalities of knowledge and belief a compositional axiomatization is given of the reactive behaviour of timed concurrent constraint programs.

In this paper, we consider communication between agents that employ different vocabularies to represent information. In particular, we develop a communication mechanism in which translators between the vocabularies of agents are generated. Instead of being defined in advance, these translators are dynamically constructed during execution of the system, and are based both on the information that the agents exchange and on their underpinning ontologies. Moreover, these translators are not necessarily defined for the total vocabulary of the agents, but instead, only for the parts that have been involved in communication steps. The framework can for instance be used to study and to analyze experiments as performed in the research on the origins of language, like language games, in which the purpose of communication is to come to a mutual understanding of the agents' vocabularies. © 2001 John Wiley & Sons, Inc.

In this paper, we present a logical framework that combines modality with a first‐order variable‐binding mechanism. The logic, which belongs to the family of hybrid languages, differs from standard first‐order modal logics in that quantification is not performed inside the worlds of a model, but the worlds in the model themselves constitute the domain of quantification. The locality principle of modal logic is preserved via the condition that in each world, the domain of quantification is given by a subset of the entire set of worlds in the model. In comparison with standard hybrid languages, the logic covers separate mechanisms for navigation and for variable‐binding and formalizes reasoning about the worlds of a model in terms of equational logic. We show that the logic is semantically characterized by a generalization of classical bisimulation, called history‐based bisimulation, and study the application of the logic to describe and reason about network topologies.

We develop a denotational, fully abstract semantics for constraint logic programming (clp) with respect to successful and failed observables. The denotational approach turns out very useful for the definition of new operators on the language as the counterpart of some abstract operations on the denotational domain. In particular, by defining our domain as a cylindric Heyting algebra, we can exploit, to this aim, operations of both cylindric algebras (such as cylindrification), and Heyting algebras (such as implication and negation). The former allows us to generalize the clp language by introducing an explicit hiding operator, the latter allows us to define a notion of negation which extends the classical negation used in logic programming. In particular, we show that our notion subsumes both negation as failure and negation as instantiation.

We introduce a simple compositional proof system for proving (partial) correctness of concurrent constraint programs (CCP). The proof system is based on a denotational approximation of the strongest postcondition semantics of CCP programs. The proof system is proved to be correct for full CCP and complete for the class of programs in which the denotational semantics characterizes exactly the strongest postcondition. This class includes the so-called confluent CCP, a special case of which is constraint logic programming with dynamic scheduling.

We develop a compositional proof-system for the partial correctness of concurrent constraint programs. Soundness and (relative) completeness of the system are proved with respect to a denotational semantics based on the notion of strongest postcondition. The strongest postcondition semantics provides a justification of the declarative nature of concurrent constraint programs, since it allows to view programs as theories in the specification logic.

Abstract We develop a Hoare-style proof system for reasoning about the behaviour of processes that interact via a dynamically evolving communication structure.

The authors study the paradigm of asynchronous process communication, as contrasted with the synchronous communication mechanism that is present in process algebra frameworks such as CCS, CSP, and ACP. They investigate semantics and axiomatizations with respect to various observability criteria: bisimulation, traces and abstract traces. The aim is to develop a process theory that can be regarded as a kernel for languages based on asynchronous communication, like data flow, concurrent logic languages, and concurrent constraint programming.>

A compositional proof systems for a parallel language, P, with dynamic process creation is presented. It is shown how a dynamic system of processes can be described in terms of specifications of the local processes which involve a characterization of their interface with the environment. The proof system formalizes reasoning about these interfaces on an abstraction level that is at least as high as that of the programming language. The programming language P is described, and two assertion languages, the local one and the global one, are defined. The proof system is described and its soundness and completeness are discussed.>