UML is widely adopted for modelling object-oriented software systems, including diagrams that cover the several facets of the entire development life cycle. Approaches to formal semantics of UML tend to concentrate on individual diagrams and, so far, no complete, standard, semantics is available. Here, we explore a different path and define a natural-language semantics for UML models that embody state machines and composite structure diagrams. We then integrate with the NAT2TEST strategy to provide means for an integrated framework for the validation (via simulation) and verification (via testing – QuickChick, interactive theorem proving – Rocq, and model checking – FDR) of UML models. The integration is based on a systematic process (mapping rules), and its soundness has been validated considering an independent reference formal semantics. The developed tool support uses ATL to implement the translation from UML models to natural-language requirements directly based on the proposed mapping rules. We illustrate our contributions and tool support with respect to two case studies: the classical Dijkstra’s dining philosophers problem, and a distributed ring-buffer model.

Formal methods encompass a wide choice of techniques and tools for the specification, development, analysis, and verification of software and hardware systems. Formal methods are widely applied in industry, in activities ranging from the elicitation of requirements and the early design phases all the way to the deployment, configuration, and runtime monitoring of actual systems. Formal methods allow one to precisely specify the environment in which a system operates, the requirements and properties that the system should satisfy, the models of the system used during the various design steps, and the code embedded in the final implementation, as well as to express conformance relations between these specifications. We present a broad scope of successful applications of formal methods in industry, not limited to the well-known success stories from the safety-critical domain, like railways and other transportation systems, but also covering other areas such as lithography manufacturing and cloud security in e-commerce, to name but a few. We also report testimonies from a number of representatives from industry who, either directly or indirectly, use or have used formal methods in their industrial project endeavours. These persons are spread geographically, including Europe, Asia, North and South America, and the involved projects witness the large coverage of applications of formal methods, not limited to the safety-critical domain. We thus make a case for the importance of formal methods, and in particular of the capacity to abstract and mathematical reasoning that are taught as part of any formal methods course. These are fundamental Computer Science skills that graduates should profit from when working as computer scientists in industry, as confirmed by industry representatives.

Abstract State machines are widely used in industry and academia to capture behavioural models of control. They are included in popular notations, such as UML and its variants, and used (sometimes informally) to describe computational artefacts. In this paper, we present laws for state machines that we prove sound with respect to a process algebraic semantics for refinement, and complete, in that they are sufficient to reduce an arbitrary model to a normal form that isolates basic (action and control) elements. We consider two variants of UML-like state machines, both enriched with facilities to deal with time budgets, timeouts and deadlines over triggers and actions. In the first variant, machines are self-contained components, declaring all the variables, events and operations that they require or define. In contrast, in the second variant, machines are open, like in UML for instance. Laws for open state machines do not depend on a specific context of variables, events and operations, and normalization uses a novel operator for open-machine (de)composition. Our laws can be used in behaviour-preservation transformation techniques. Their applications are automated by a model-transformation engine.

RoboSim is a tool-independent notation for modeling software simulations of robots, and it can be verified by a variety of techniques and tools, including model checking and theorem proving. RoboSim has a formal tock-CSP (Communicating Sequential Processes) semantics, and so refinement checkers, such as FDR, can be used for verification of models. In this paper, we explore the use of UPPAAL, as a well-established tool for verification of time-dependent properties. We propose a model-transformation strategy to translate RoboSim models into NTA (Network of Timed Automata) based on some patterns and mapping rules. We implement our strategy as a plug-in for the RoboSim modeling and verification tool. Using examples, we compare the verification results of UPPAAL and FDR for a series of safety, reachability, and liveness properties. Moreover, we use a robotic platform model of swarm robots in an uncertain environment, to illustrate how our approach can be extended to the verification of stochastic and hybrid systems using UPPAAL SMC. Such an extension cannot be easily conceived for The original tock-CSP semantics of RoboSim.

Conformance testing is a formal and structured approach to verifying system correctness. We propose a conformance testing algorithm for cyber-physical systems, based on the notion of hybrid conformance by Abbas and Fainekos. We show how the dynamics of system specification and the sampling rate play an essential role in making sound verdicts. We specify and prove error bounds that lead to sound test-suites for a given specification and a given sampling rate. We use reachability analysis to find such bounds and implement the proposed approach using the CORA toolbox in Matlab. We apply the implemented approach on a case study from the automotive domain.

No abstract available.

Software systems need to be constantly tested, either to verify changes or to check conformance to requirements.The current leading approaches to automate GUI tests are coding and the use of Capture & Replay (C&R) tools.Coding is usually associated with (even if ad hoc) reuse strategies, but requires from the developer specialized knowledge about the adopted framework.On the other hand, even though C&R is able to promote faster automation, it raises maintainability and scalability issues in the long term due to scripts scattering and rework for each new test case, because usually there is no associated reuse strategy.In order to combine the benefits of both approaches, we propose: an abstract and framework-free representation of test actions captured during testing activities; a text-based strategy that matches a new test case with previously recorded test actions; and a C&R tool that implements these concepts in the mobile context.We developed and evaluated our strategy in the context of a partnership with Motorola Mobility, achieving a reuse ratio up to 71% with time gains similar to traditional C&R approaches when compared to coding.

CSP is well established as a process algebra for refinement. Most refinement relations for CSP do not differentiate between inputs and outputs, and so are unsuitable for testing. This paper provides CSP with a denotational semantics based on suspension traces; it gives the traditional CSP operators a novel view, catering for the differences between inputs and outputs. We identify healthiness conditions for the suspension-traces model and include a treatment of termination not contemplated in the context of input-output labelled transition systems. Using our suspension-traces semantics, we provide for CSP a characterisation of the conformance relation ioco, which is widely used in testing. Finally, we propose a strategy to mechanise the verification of conformance according to ioco and suspension-trace refinement using CSP tools. This work provides the basis for a theory of testing for CSP with inputs and outputs, and opens up the possibility of studying algebraic laws and compositional reasoning techniques based on ioco. Ultimately, it contributes to making CSP models useful for both design and testing of systems.

Abstract At the very beginning of system development, typically only natural-language requirements are documented. As an informal source of information, however, natural-language specifications may be ambiguous and incomplete; this can be hard to detect by means of manual inspection. In this work, we present a formal model, named data-flow reactive system (DFRS), which can be automatically obtained from natural-language requirements that describe functional, reactive and temporal properties. A DFRS can also be used to assess whether the requirements are consistent and complete. We define two variations of DFRS: a symbolic and an expanded version. A symbolic DFRS (s-DFRS) is a concise representation that inherently avoids an explicit representation of (possibly infinite) sets of states and, thus, the state space-explosion problem. We use s-DFRS as part of a technique for test-case generation from natural-language requirements. In our approach, an expanded DFRS (e-DFRS) is built dynamically from a symbolic one, possibly limited to some bound; in this way, bounded analysis (e.g., reachability, determinism, completeness) can be performed. We adopt the s-DFRS as an intermediary representation from which models, for instance, SCR and CSP, are obtained for the purpose of test generation. An e-DFRS can also be viewed as the semantics of the s-DFRS from which it is generated. In order to connect such a semantic representation to established ones in the literature, we show that an e-DFRS can be encoded as a TIOTS: an alternative timed model based on the widely used IOLTS and ioco. To validate our overall approach, we consider two toy examples and two examples from the aerospace and automotive industry. Test cases are independently created and we verify that they are all compatible with the corresponding e-DFRS models generated from symbolic ones. This verification is performed mechanically with the aid of the NAT2TEST tool, which supports the manipulation of such models.

Abstract In previous work we presented a CSP-based systematic approach that fosters the rigorous design of component-based development. Our approach is strictly defined in terms of composition rules, which are the only permitted way to compose components. These rules guarantee the preservation of properties (particularly deadlock freedom) by construction in component composition. Nevertheless, their application is allowed only under certain conditions whose verification via model checking turned out impracticable even for some simple designs, and particularly those involving cyclic topologies. In this paper, we address the performance of the analysis and present a significantly more efficient alternative to the verification of the rule side conditions, which are improved by carrying out partial verification on component metadata throughout component compositions and by using behavioural patterns. The use of metadata, together with behavioural patterns, demands new composition rules, which allow previous exponential time verifications to be carried out now in linear time. Two case studies (the classical dining philosophers, also used as a running example, and an industrial version of a leadership election algorithm) are presented to illustrate and validate the overall approach.

We propose a semantics for Sequence Diagrams based on the COMPASS Modelling Language (CML): a formal specification language to model systems of systems. A distinguishing feature of our semantics is that it is defined as part of a larger effort to define the semantics of several diagrams of SysML, a UML profile for systems engineering. We have defined a fairly comprehensive semantics for Sequence Diagrams, which comprises sequential and parallel constructors, loops, breaks, alternatives, synchronous and asynchronous messages. We illustrate our semantics with a scenario of a case study of a system of systems. We also discuss an analysis strategy which involves an integrated view of several diagrams.

Abstract We present a strategy for the automatic generation of test cases from parametrised use case templates that capture control flow, state, input and output. Our approach allows test scenario selection based on particular traces or states of the model. The templates are internally represented as CSP processes with explicit input and output alphabets, and test generation is expressed as counter-examples of refinement checking, mechanised using the FDR tool. Soundness is addressed through an input–output conformance relation formally defined in the CSP traces model. This purely process algebraic characterisation of testing has some potential advantages, mainly an easy automation of conformance verification and test case generation via model checking, without the need to develop any explicit algorithm.

SUMMARY This paper mechanises conformance verification in the setting of the CSP process algebra. The verification strategy is captured by a theorem stated as a process refinement expression, which can be verified by a model checker such as FDR. The conformance relation,cspio, distinguishes input and output events. The process algebraic framework of CSP is used to address compositional conformance verification by establishing compositionality properties forcspiowith respect to the CSP operators. Althoughcspiohas been defined in the standard CSP traces model, one can address quiescence situations using a special output event, in which case it is formally established thatcspiois equivalent to Tretmansioco. All the results have been mechanically proved using the CSP‐Prover. The proposed testing theory has been adopted in an industrial context involving collaboration with Motorola, on testing mobile applications. Several examples and a case study are presented to illustrate the overall approach. Copyright © 2013 John Wiley & Sons, Ltd.

Refactoring transformations are important for productivity and quality in software evolution. Modular reasoning about semantics preserving transformations is difficult even in typed class-based languages because transformations can change the internal representations for multiple interdependent classes and because encapsulation can be violated by pointers to mutable objects. In this paper, an existing theory of representation independence for a single class, based on a simple notion of ownership confinement, is generalized to a hierarchy of classes and used to prove several refactoring laws. Soundness of these laws was an open problem in an ongoing project on formal refactoring tools. The utility of the laws is shown in a case study. Shortcomings of the theory are described as a challenge to other approaches to heap encapsulation and relational reasoning for classes.

Abstract In this paper we describe an algebraic approach to construct provably correct compilers for object-oriented languages; this is illustrated for programs written in a language similar to a sequential subset of Java. It includes recursive classes, inheritance, dynamic binding, recursion, type casts and test, assignment, and class-based visibility, but a copy semantics. In our approach, we tackle the problem of compiler correctness by reducing the task of compilation to that of program refinement. Compilation is identified with the reduction of a source program to a normal form that models the execution of object code. The normal form is generated by a series of correctness-preserving transformations that are proved sound from the basic laws of the language; therefore it is correct by construction. The main advantages of our approach are the characterisation of compilation within a uniform framework, where comparisons and translations between semantics are avoided, and the modularity and extensibility of the resulting compiler.

Abstract Following the trend to combine techniques to cover several facets of the development of modern systems, an integration of Z and CSP, calledCircus, has been proposed as a refinement language; its relational model, based on the unifying theories of programming (UTP), justifies refinement in the context of both Z and CSP. In this paper, we introduceCircus Time, a timed extension ofCircus, and present a new UTP time theory, which we use to give semantics toCircus Timeand to validate some of its laws. In addition, we provide a framework for validation of timed programs based on FDR, the CSP model-checker. In this technique, a syntactic transformation strategy is used to split a timed program into two parallel components: an untimed program that uses timer events, and a collection of timers. We show that, with the timer events, it is possible to reason about time properties in the untimed language, and so, using FDR. Soundness is established using a Galois connection between the untimed UTP theory ofCircus(and CSP) and our time theory.

The order in which tests are executed can significantly impact the total test execution time. In this paper, we evaluate two test prioritization techniques (manual and automatic) in the context of mobile phone testing. The manual technique produces test sequences created by test experts, while the automatic one generates sequences mechanically based on the permutation of the tests. Both techniques take into account a data reuse: the more the data is reused among tests, the faster the sequence is executed. In order to evaluate the benefits of these two techniques, we carried out an experiment with 8 testers and 2 test suites arranged in a 2times2 Latin square design replicated four times. The automatic technique reduced approximately 25% of the data generation time and 13.5% of the execution time. The automatic technique is clearly better than the manual one with respect to the generation of sequences. Our experiment showed that the automatic technique also generates sequences whose execution is faster than those created manually by test experts.

Algebraic laws have been proposed to support program transformation in several paradigms. In general, and for object-orientation in particular, these laws tend to ignore possible aliasing resulting from reference semantics. This paper proposes a set of algebraic laws for object-oriented languages in the context of a reference semantics. Soundness of the laws is addressed, and a case study is also developed to show the application of the proposed laws for code refactoring.

The Software Test Program (STP) is a cooperation between Motorola and the Center for Informatics of the Federal University of Pernambuco. It has been conceived with inspiration on the Medical Residency, adjusted to the software development practice. A Software Residency includes the formal teaching of the relevant concepts and deep practice, with specialization on some specific subject; here the focus is on software testing. The STP has been of great benefit to all parties involved.

Framework composition, when used for designing and implementing applications, offers great potential for reuse and extensibility in large scale. However, the literature shows that composing frameworks may result in unexpected side-effects like, for instance, the introduction of deadlock. In this work, we use the process algebra CSP to formally characterize the framework composition problem, abstracting from implementation details or technology. We propose a framework composition strategy which guarantees that the properties of the compound frameworks are preserved after composition. The strategy is presented through a case study: a client/server application.

Abstract We present a refinement strategy for Circus , which is the combination of Z, CSP, and the refinement calculus in the setting of Hoare and He’s unifying theories of programming. The strategy unifies the theories of refinement for processes and their constituent actions, and provides a coherent technique for the stepwise refinement of concurrent and distributed programs involving rich data structures. This kind of development is carried out using Circus ’s refinement calculus, and we describe some of its laws for the simultaneous refinement of state and control behaviour, including the splitting of a process into parallel subcomponents. We illustrate the strategy and the laws using a case study that shows the complete development of a small distributed program.