Search

The design and verification of distributed software systems is often hindered by their ever-increasing complexity and their asynchronous operational semantics. This article considers choreography specifications for distributed systems to reduce that complexity. We use labelled state-transitions systems as ground model for both choreographies and the corresponding distributed systems. Based on Event-B method, we propose a stepwise correct-by-construction model to build asynchronous distributed systems which a priori realise their choreographies. We rely on a sufficient and necessary realisability condition and we apply several refinement steps w.r.t. that condition to generate the distributed peers. The first refinement returns peer behaviours obtained by synchronous projection. The previously computed system is then refined into its asynchronous version using unbounded FIFO buffers. We prove, thanks to invariant preservation, that a sequence of exchanged messages is preserved at each refinement step. We provide a formalised proof of a realisability algorithm for deterministic choreographies. Besides that, our contribution is twofold: the approach is a priori and the problackposed solution scales up to any number of peers communicating with each other. [ABSTRACT FROM AUTHOR]

We present SATMC 3.0, a SAT-based bounded model checker for security-critical systems that stems from a successful combination of encoding techniques originally developed for planning with techniques developed for the analysis of reactive systems. SATMC has been successfully applied in a variety of application domains (security protocols, security-sensitive business processes, and cryptographic APIs) and for different purposes (design-time security analysis and security testing). SATMC strikes a balance between general purpose model checkers and security protocol analyzers as witnessed by a number of important success stories including the discovery of a serious man-in-the-middle attack on the SAML-based single sign-on (SSO) for Google Apps, an authentication flaw in the SAML 2.0 Web Browser SSO Profile, and a number of attacks on PKCS#11 Security Tokens. SATMC is integrated and used as back-end in a number of research prototypes (e.g., the AVISPA Tool, Tookan, the SPaCIoS Tool) and industrial-strength tools (e.g., the Security Validator plugin for SAP NetWeaver BPM). [ABSTRACT FROM AUTHOR]

Web services business activity (WS-BA) specification defines two coordination protocols BAwCC (Business Agreement with Coordination Completion) and BAwPC (Business Agreement with Participant Completion) that ensure a consistent agreement on the outcome of long-running distributed applications. To verify fundamental properties of the protocols, we provide formal analyses in the model checker Uppaal. Our analyses are supported by a newly developed tool chain, where in the first step we translate tables with state-transition protocol descriptions into an intermediate XML format, and in the second step we translate this format into a network of communicating state machines directly suitable for verification in Uppaal. Our results show that the WS-BA protocols, as described in the standard specification, violate correct operation by reaching invalid states for all underlying communication media except for a perfect FIFO. Hence, we propose changes to the protocols and a further investigation of the modified protocols suggests that in case of the BAwCC protocol, messages should be received in the same order as they are sent to preserve correct behaviour, while BAwPC is now correct even for asynchronous, unordered, lossy and duplicating media. Another important property of communication protocols is that all parties always reach, under certain fairness assumptions, their final states. Based on an automatic verification with different communication models, we prove that our enhanced protocols satisfy this property whereas the original protocols do not. All verification results presented in this article were performed in a fully automatic way using our new tool csv2uppaal. [ABSTRACT FROM AUTHOR]

Developing tools that are able to perform automatic verification on realistic models of software systems is one of the main challenges facing the formal methods community. We briefly review the research area and introduce three papers selected from the Seventeenth International Conference on Tools and Algorithms for the Construction and Analysis of Systems ( tacas 2011). [ABSTRACT FROM AUTHOR]

This study deals with interoperability testing of protocol implementations. The objective is to define a method for automatic test derivation based on formal definitions. First, the notion of interoperability criteria is introduced. They formally describes the conditions that two implementations must verify in order to be considered interoperable. Then, based on the equivalence of two of the defined interoperability criteria, we propose a method to derive automatically interoperability test cases that avoids the state-space explosion problem. [ABSTRACT FROM AUTHOR]

In this paper, we present a software framework for adding fault-tolerance to existing finite-state programs. The input to our framework is a fault-intolerant program and a class of faults that perturbs the program. The output of our framework is a fault-tolerant version of the input program. Our framework provides (1) the first automated tool for the synthesis of fault-tolerant distributed programs, and (2) an extensible platform for researchers to develop a repository of heuristics that deal with the complexity of adding fault-tolerance to distributed programs. We also present a set of heuristics for polynomial-time addition of fault-tolerance to distributed programs. We have used this framework for automated synthesis of several fault-tolerant programs including a simplified version of an aircraft altitude switch, token ring, Byzantine agreement, and agreement in the presence of Byzantine and fail-stop faults. These examples illustrate that our framework can be used for synthesizing programs that tolerate different types of faults (process restarts, Byzantine and fail-stop) and programs that are subject to multiple faults (Byzantine and fail-stop) simultaneously. We have found our framework to be highly useful for pedagogical purposes, especially for teaching concepts of fault-tolerance, automatic program transformation, and the effect of heuristics. [ABSTRACT FROM AUTHOR]

This paper presents a methodology for test suite implementation based on Testing and test control notation (TTCN)-3 libraries which has been developed and successfully applied for the implementation of complex, standardized Internet Protocol version 6 (IPv6) conformance test suites at ETSI. It introduces the concept of a TTCN-3 library, discusses benefits and challenges, and examines the effect of some important TTCN-3 language constructs on reuse. Finally, it explains in detail a layered library design approach to test implementation in the context of a IPv6 test suite. [ABSTRACT FROM AUTHOR]

The Capability Exchange Signalling (CES) protocol is one of the sub-protocols of recommendation H.245, “Control protocol for multimedia communication” issued by the International Telecommunication Union. In this paper, we model the CES protocol with Coloured Petri Nets and verify it using state space and language analyses. The results reveal that the CES protocol could fail when the sequence numbers used by the protocol wrap. To solve this problem, we propose a set of changes to the CES protocol. State space and language analyses are then applied to the revised protocol. Verification results suggest that the revised protocol satisfies the desired properties with the errors discovered being eliminated. [ABSTRACT FROM AUTHOR]

The sweep-line state space method allows states to be deleted from memory during state exploration, thus alleviating the state explosion problem. Properties of the system (such as the absence of deadlocks) can then be verified on-the-fly. This paper presents an extension to the sweep-line method that allows on-the-fly checking of safety properties expressed as sequences of actions of the modelled system. This has been implemented in a prototype sweep-line library for Coloured Petri nets. We evaluate the prototype by applying it to the connection management procedures of the Datagram Congestion Control Protocol, a new Internet transport protocol. [ABSTRACT FROM AUTHOR]

The reasons for translating a description of a model in one notation into another are reviewed. Such model descriptions are used as input to formal verification tools or as design-level descriptions for protocols or hardware. Translations are used to produce input to a different tool to verify properties not verified in the source model, and to connect notations that have no associated verification tool to those that do. The VeriTech framework for translation is described. A system being analyzed is seen as a collection of versions, along with a characterization of how the versions are related, and properties known to be true of each version. The versions are given in different notations connected through a core notation by compilers from and to the notations of existing tools and specification methods. The reasons that translations cannot always be exact are analyzed. To facilitate optimizations during retranslation, error tracing, and analysis, additional information is gathered during translation, and is also included with the system being analyzed. The concept of a faithful relation among models and families of properties true of those models is presented. In this framework families of properties are provided with uniform syntactic transformations, in addition to the translations of the models. This framework generalizes common instances of relations among translations previously treated in an ad hoc way. The example of refinement translations is shown in detail. The classes of properties that can be faithful for a given translation provide a measure of the usefulness of the translation. [ABSTRACT FROM AUTHOR]

Lurette is an automated testing tool dedicated to reactive programs. The test process is automated at two levels: given a formal description of the System Under Test (SUT) environment, Lurette generates realistic input sequences; and, given a formal description of expected properties, Lurette performs the test results analysis. Lurette has been re-implemented from scratch. In this new version, the main novelty lies in the way the SUT environment is described. This is done by means of a new language called Lucky, dedicated to the programming of probabilistic reactive systems. This article recalls the principles of Lurette, briefly presents the Lucky language, and describes some case studies from the IST project Safeair II. The objective is to illustrate the usefulness of Lurette on real case studies, and the expressiveness of Lucky in accurately describing SUT environments. We show in particular how Lurette can be used to test a typical fault-tolerant system; we also present case studies conducted with Hispano-Suiza and Renault. [ABSTRACT FROM AUTHOR]

This paper presents a formal analysis of the device discovery phase of the Bluetooth wireless communication protocol. The performance of this process is the result of a complex interaction between several devices, some of which exhibit random behaviour. We use probabilistic model checking and, in particular, the tool PRISM to compute the best- and worst-case performance of device discovery: the expected time for the process to complete and the expected power consumption. We illustrate the utility of performing an exhaustive, low-level analysis to produce exact results in contrast to simulation techniques, where additional probabilistic assumptions must be made. We demonstrate an example of how seemingly innocuous assumptions can lead to incorrect performance estimations. We also analyse the effectiveness of improvements made between versions 1.1 and 1.2 of the Bluetooth specification. [ABSTRACT FROM AUTHOR]

In the context of computer networks, conformance testing determines whether an implementation under test conforms to its specification. Testing was carried out in a centralized and sequential way. This is no longer feasible or realistic as systems to be tested have become increasingly complex and can be widely distributed. Our further goal is to evaluate how a distributed approach can help in testing complex systems such as a network’s components efficiently. We present two solutions to generate automatically distributed tests. As it is somehow less difficult to generate centralized tests, the proposed solutions consist in automatically distributing these tests. By applying these solutions to military ISDN protocols, we showed that: (i) the solutions ease development of distributed tests and (ii) distributed tests obtained are well suited for testing complex systems. [ABSTRACT FROM AUTHOR]

In this paper we show that statistical properties of the transition graph of a system to be verified can be exploited to improve memory or time performances of verification algorithms.We show experimentally that protocols exhibittransition locality. That is, with respect to levels of a breadth-first state space exploration, state transitions tend to be between states belonging to close levels of the transition graph. We support our claim by measuring transition locality for the set of protocols included in the Mur? verifier distribution .We present acache-based verification algorithmthat exploits transition locality to decrease memory usage and adisk-based verification algorithmthat exploits transition locality to decrease disk read accesses, thus reducing the time overhead due to disk usage. Both algorithms have been implemented within the Mur? verifier.Our experimental results show that our cache-based algorithm can typically save more than 40% of memory with an average time penalty of about 50% when using (Mur?) bit compression and 100% when using bit compression and hash compaction, whereas our disk-based verification algorithm is typically more than ten times faster than a previously proposed disk-based verification algorithm and, even when using 10% of the memory needed to complete verification, it is only between 40 and 530% (300% on average) slower than (RAM) Mur? with enough memory to complete the verification task at hand. Using just 300 MB of memory our disk-based Mur? was able to complete verification of a protocol with about 109 reachable states. This would require more than 5 GB of memory using standard Mur? . [ABSTRACT FROM AUTHOR]