The engineering of industrial systems, particularly in safety-critical domains such as railways, demands rigorous verification and validation processes to ensure system dependability. Formal methods have emerged as powerful tools to complement traditional software engineering practices. In the railway sector, which increasingly relies on complex, distributed, and cyber-physical control systems, formal methods have demonstrated particular value for many decades now. In this article, we provide a retrospective overview of the application of formal methods and tools in the railway domain, with emphasis on two prominent verification approaches and one frequently verified railway system: modeling and validation with the B method and tools and formal verification of interlocking systems by model checking. We explore their role in the design and development of key railway systems, highlighting both academic research and industrial success stories, as witnessed by international projects and initiatives. We conclude with an outlook on the potential of integrating AI and formal methods to enhance the efficiency of next-generation railway systems.

Previous work has investigated the adequacy of LLMs to detect inconsistencies in requirements documents, but has also shown their limitations with real case studies. In this paper, we propose a hybrid approach, which exploits traditional clustering techniques to help LLMs focus on potential inconsistencies. The approach was evaluated using a large security requirements document from the RE Open Data Initiative, with injected inconsistencies. Results show that combining LLM-based detection with rule-based clustering enhances both precision and recall.

We focus on the integration of Formal Methods as mandatory theme in any Computer Science University curriculum. In particular, when considering the ACM Curriculum for Computer Science, the inclusion of Formal Methods as a mandatory Knowledge Area needs arguing for why and how does every computer science graduate benefit from such knowledge. We do not agree with the sentence “While there is a belief that formal methods are important and they are growing in importance, we cannot state that every computer science graduate will need to use formal methods in their career.” We argue that formal methods are and have to be an integral part of every computer science curriculum. Just as not all graduates will need to know how to work with databases either, it is still important for students to have a basic understanding of how data is stored and managed efficiently. The same way, students have to understand why and how formal methods work, what their formal background is, and how they are justified. No engineer should be ignorant of the foundations of their subject and the formal methods based on these. In this article, we aim at highlighting why every computer scientist needs to be familiar with formal methods. We argue that education in formal methods plays a key role by shaping students' programming mindset, fostering an appreciation for underlying principles, and encouraging the practice of thoughtful program design and justification, rather than simply writing programs without reflection and deeper understanding. Since integrating formal methods into the computer science curriculum is not a straightforward process, we explore the additional question: what are the tradeoffs between one dedicated knowledge area of formal methods in a computer science curriculum versus having formal methods scattered across all knowledge areas? Solving problems while designing software and software-intensive systems demands an understanding of what is required, followed by a specification and formalizing a solution in a programming language. How to do this systematically and correctly on solid grounds is exactly supported by formal methods.

Context: Attack-Defense Trees (ADTs) are a graphical notation used to model and evaluate security requirements. ADTs are popular because they facilitate communication among different stakeholders involved in system security evaluation and are formal enough to be verified using methods like model checking. The understandability and user-friendliness of ADTs are claimed as key factors in their success, but these aspects, along with user acceptance, have not been evaluated empirically. Objectives: This paper presents an experiment with 25 subjects designed to assess the understandability and user acceptance of the ADT notation, along with an internal replication involving 49 subjects. Methods: The experiments adapt the Method Evaluation Model (MEM) to examine understandability variables (i.e., effectiveness and efficiency in using ADTs) and user acceptance variables (i.e., ease of use, usefulness, and intention to use). The MEM is also used to evaluate the relationships between these dimensions. In addition, a comparative analysis of the results of the two experiments is carried out. Results: With some minor differences, the outcomes of the two experiments are aligned. The results demonstrate that ADTs are well understood by participants, with values of understandability variables significantly above established thresholds. They are also highly appreciated, particularly for their ease of use. The results also show that users who are more effective in using the notation tend to evaluate it better in terms of usefulness. Conclusion: These studies provide empirical evidence supporting both the understandability and perceived acceptance of ADTs, thus encouraging further adoption of the notation in industrial contexts, and development of supporting tools.

Technological advances in modern Train Control Systems (TCSs) promise to improve dependability of railway transportation in terms of safety, availability, and capacity, notably by employing novel distancing policies such as Moving Block (MB) signaling and Virtual Coupling (VC), fueled by advanced train localization methods such as satellite positioning. At the same time, these technological advances raise notable concerns about the effects that uncertainty in critical TCS parameters (such as train position and speed) may have on dependability-related attributes. Recently, various approaches have been proposed to characterize such effects through quantitative measures, leveraging formal stochastic modeling and evaluation of the TCS behavior. In this paper, we illustrate the results of a systematic review of the literature on quantitative evaluation of dependability-related attributes of TCSs under uncertainty on vital parameters. Specifically, we have finally selected 42 relevant papers, published between 2011 and 2023, that succeed in giving, through an empirical perspective and classification, a comprehensive view of current research and practice in quantitative dependability assessment of TCSs.

Modal Transition Systems (MTS) are a well-known formalism that extend Labelled Transition Systems (LTS) with the possibility of specifying necessary and permitted behaviour. Coherent MTS (CMTS) have been introduced to model Software Product Lines (SPL) based on a correspondence between the necessary and permitted modalities of MTS transitions and their associated actions, and the core and optional features of SPL. In this paper, we address open problems of the coherent fragment of MTS and introduce the notions of refinement and thorough refinement of CMTS. Most notably, we prove that refinement and thorough refinement coincide for CMTS, while it is known that this is not the case for MTS. We also define (thorough) equivalence and strong bisimilarity of both MTS and CMTS. We show their relations and, in particular, we prove that also strong bisimilarity and equivalence coincide for CMTS, whereas they do not for MTS. Finally, we extend our investigation to CMTS equipped with Constraints (MTSC), originally introduced to express alternative behaviour, and we prove that novel notions of refinement and strong thorough refinement coincide for MTSC, and so do their extensions to strong (thorough) equivalence and strong bisimilarity.

With the rapid advancement of tools based on Artificial Intelligence, it is interesting to assess their usefulness in requirements engineering. In early experiments, we have seen that ChatGPT can detect inconsistency defects in natural language (NL) requirements, that traditional NLP tools cannot identify or can identify with difficulties even after domain-focused training. This study is devoted to specifically measuring the performance of ChatGPT in finding inconsistency in requirements. Positive results in this respect could lead to the use of ChatGPT to complement existing requirements analysis tools to automatically detect this important quality criterion. For this purpose, we consider GPT-3.5, the Generative Pretrained Transformer language model developed by OpenAI. We evaluate its ability to detect inconsistency by comparing its predictions with those obtained from expert judgments by students with a proven knowledge of RE issues on a few example requirements documents.

Model checking techniques have often been applied to the verification of railway interlocking systems, responsible for guiding trains safely through a given railway network. However, these techniques fail to scale to the interlocking systems controlling large stations, composed of hundreds and even thousands of controlled entities, due to the state space explosion problem. Indeed, interlocking systems exhibit a certain degree of locality that allows some reasoning only on the mere set of entities that regard the train movements, but safe routing through a complex station layout requires a global reservation policy, which can require global state conditions to be taken into account. In this article, we present a compositional approach aimed at chopping the verification of a large interlocking system into that of smaller fragments, exploiting in each fragment a proper abstraction of the global information on routing state. A proof is given of the thesis that verifying the safety of the smaller fragments is sufficient to verify the safety of the whole network. Experiments using this compositional approach have shown important gains in performance of the verification, as well as in the size of affordable station layouts.

Abstract The substitution of traditional occupancy detecting sensors with an Autonomous Positioning System (APS) is a promising solution to contain costs and improve performance of current tramway signalling systems. APS is an onboard system using satellite positioning and other inertial platforms to autonomously estimate the position of the tram with the needed levels of uncertainty and protection. However, autonomous positioning introduces, even in absence of faults, a quantitative uncertainty with respect to traditional sensors. This paper investigates this issue in the context of an industrial project: a model of the envisaged solution is proposed, and it is analysed using Uppaal Statistical Model Checker. A novel model-driven hazard analysis approach to the exploration of emerging hazards is proposed. The analysis emphasises how the virtualisation of legacy track circuits and on-board satellite positioning equipment may give rise to new hazards, not present in the traditional system.

No abstract available.

Formal methods and tools have a long history of successful applications in the design of safety-critical railway products. However, most of the experiences focused on the application of a single method at once, and little work has been performed to compare the applicability of the different available frameworks to the railway context. As a result, companies willing to introduce formal methods in their development process have little guidance on the selection of tools that could fit their needs. To address this goal, this paper presents a comparison between 9 different formal tools, namely Atelier B, CADP, FDR4, NuSMV, ProB, Simulink, SPIN, UMC, and UPPAAL SMC. We performed a judgment study, involving 17 experts with experience in formal methods applied to railways. In the study, part of the experts were required to model a railway signaling problem (a moving-block train distancing system) with the different tools, and to provide feedback on their experience. The information produced was then synthesized, and the results were validated by the remaining experts. Based on the outcome of this process, we provide a synthesis that describes when to use a certain tool, and what are the problems that may be faced by modelers. Our experience shows that the different tools serve different purposes, and multiple formal methods are required to fully cover the needs of the railway system design process.

The engineering of software product lines begins with the identification of the possible variation points. To this aim, natural language (NL) requirement documents can be used as a source from which variability-relevant information can be elicited. In this paper, we propose to identify variability issues as a subset of the ambiguity defects found in NL requirement documents. To validate the proposal, we single out ambiguities using an available NL analysis tool, QuARS, and we classify the ambiguities returned by the tool by distinguishing among false positives, real ambiguities, and variation points, by independent analysis and successive agreement phase. We consider three different sets of requirements and collect the data that come from the analysis performed.

A product line perspective may help to understand the possible variants in interactions between the subsystems of a large, cyber-physical system. This observation is exemplified in this paper by proposing a feature model of the family of ERTMS/ETCS train control systems and their foreseen extensions. This model not only shows the different components that have to be installed when deploying the system at the different levels established by the ERTMS/ETCS standards, but it also helps to identify and discuss specific issues, such as the borders between onboard and wayside equipment, different manufacturers of the subsystems, interoperability among systems developed at different levels, backward compatibility of trains equipped with higher level equipment running on lines equipped with lower level equipment, and evolution towards future trends of railway signalling. The feature model forms the basis for formal modelling of the behaviour of the critical components of the system and for evaluating the overall cost, effectiveness and sustainability, for example by adding cost and performance attributes to the feature model.

The current trend of distributing computations over a network is here, as a novelty, applied to a safety critical system, namely a railway interlocking system. We show how the challenge of guaranteeing safety of the distributed application has been attacked by formally specifying and model checking the relevant distributed protocols. By doing that we obey the safety guidelines of the railway signalling domain, that require formal methods to support the certification of such products. We also show how formal modelling can help designing alternative distributed solutions, while maintaining adherence to safety constraints.

Engineering a Collective Adaptive System (CAS) requires the support of a framework for quantitative modeling and analysis of the system. In order to jointly address variability and quantitative analysis, we apply the Product Lines paradigm, considered at the level of system engineering, to a case study of the European project QUANTICOL, by first defining a reference feature model and then adding feature attributes and global quantitative constraints, in the form of a Clafer attributed feature model. ClaferMOOVisualizer is subsequently used for quantitative analyses and multi-objective optimization of the resulting attributed feature model.

We show how the FMC model checker can successfully be used to model and analyze behavioural variability in Software Product Lines. FMC accepts parameterized specifications in a process-algebraic input language and allows the verification of properties of such models by means of efficient on-the-fly model checking. The properties can be expressed in a logic that allows to correlate the parameters of different actions within the same formula. We show how this feature can be used to tailor formulas to the verification of only a specific subset of products of a Software Product Line, thus allowing for scalable family-based analyses with FMC. We present a proof-of-concept that shows the application of FMC to an illustrative Featured Transition System from the literature.

We address a category of systems whose deployment requires a configuration according to topological information. Although inspired by the case of railway interlocking systems, we give a general definition of topologically configurable control systems. We consider the application of product line engineering principles to the development of these systems, by discussing the adoption of different approaches to achieve a flexible configuration of products, able to factorise most of the design effort, as typical in a product line approach.

Automated monitoring and the recognition of activities of daily living (ADLs) is a key challenge in ambient-assisted living (AAL) for the assistance of the elderly. Within this context, a formal approach may provide a means to fill the gap between the low-level observations acquired by sensing devices and the high-level concepts that are required for the recognition of human activities. We describe a system named ARA (Automated Recognizer of ADLs) that exploits propositional temporal logic and model checking to support automated real-time recognition of ADLs within a smart environment. The logic is shown to be expressive enough for the specification of realistic patterns of ADLs in terms of basic actions detected by a sensorized environment. The online model checking engine is shown to be capable of processing a stream of detected actions in real time. The effectiveness and viability of the approach are evaluated within the context of a smart kitchen, where different types of ADLs are repeatedly performed.

We introduce a logical verification methodology for checking behavioral properties of service-oriented computing systems. Service properties are described by means of SocL, a branching-time temporal logic that we have specifically designed for expressing in an effective way distinctive aspects of services, such as, acceptance of a request, provision of a response, correlation among service requests and responses, etc. Our approach allows service properties to be expressed in such a way that they can be independent of service domains and specifications. We show an instantiation of our general methodology that uses the formal language COWS to conveniently specify services and the expressly developed software tool CMC to assist the user in the task of verifying SocL formulas over service specifications. We demonstrate the feasibility and effectiveness of our methodology by means of the specification and analysis of a case study in the automotive domain.

We present a research agenda on an emerging topic in software engineering, namely the synergy between Software Product Line Engineering (SPLE) and Service-Oriented Computing (SOC). Our proposal is to develop rigorous modelling techniques as well as analysis and verification support tools for assisting organisations to plan, optimise, and control the quality of 'software service' provision, both at design time and at run time. We foresee a flexible engineering methodology according to which 'software service line organisations' can develop novel classes of service-oriented applications that can easily be adapted to customer requirements as well as to changes in the context in which, and while, they execute. By superposing variability mechanisms on current languages for service engineering, based on policies and strategies defined by service providers, we envision the possibility of identifying variability points that can be triggered at run time to increase adaptability and optimise the (re)use of resources.

We illustrate how to manage variability in a single logical framework consisting of a Modal Transition System (MTS) and an associated set of formulae expressed in the branching-time temporal logic MHML interpreted in a deontic way over such MTSs. We discuss the commonalities and differences with the framework of Classen et al. based on Featured Transition Systems and Linear-time Temporal Logic.

This article presents the experience of a railway signaling manufacturer in introducing the technologies of model based testing and abstract interpretation as part of its development process. Preliminary results show the better performance of these techniques with respect to the previously employed structural coverage based testing.

Requirements analysis is an important phase in a software project. Automatic evaluation of natural language (NL) requirements documents has been proposed as a means to improve the quality of the system under development. QuARS Express is an automatic analyzer of natural language (NL) requirements able to manage complex and structured requirement documents containing metadata, and to produce an analysis report rich of information that points out linguistic defects and indications about the writing style of NL requirements.

In this paper we propose a behavioural model, namely the generalized extended modal transition systems, as a basis for the formalization of different notions of variability usually present in product families definitions. In particular, a GEMTS is able to define a family of products by telling at any state of the system whether some (and how many) transitions are optional or mandatory for any derived products of the family. The proposed model is compared with previous proposals also based on labelled transition systems, showing its higher generality, but also pointing out weaknesses that still need to be addressed with more expressive models. Hints on the solution of such weaknesses are given by the use of constraints expressed as temporal logic formulae.

In this paper we propose a behavioural model, namely the Extended Modal Labeled Transition Systems, as a basis for the formalization of the different notions of variability usually present in product families definitions. In particular, an EMLTS is able to define a family of products by telling at any state of the system whether transitions are optional or compulsory for the products of the family. Based on this model, verification that a product belongs to a family can be carried out by means of automatic tools.

The development of computer controlled Railway Interlocking Systems has seen an increasing interest in the use of Formal Methods, due to their ability to precisely specify the logical rules that guarantee the safe establishment of routes for trains through a railway yard. Recently, a trend has emerged about the use of statecharts as a standard formalism to produce precise specifications of these systems.A problem that arises in the practical application of such formalization is that each produced interlocking system is dependent on the physical layout of the controlled yard. This has strong effects on development costs and especially on validation, which has to be repeated for each product. Validating formalized interlocking principles first, and then instantiating them to a specification which is tailored to the considered layout is a solution that we investigate in this paper.

The experience reported in this paper relates to an evaluation of the automatic generation of C code from the Specification and Description Language (SDL) specification of embedded applications. The evaluation has been carried out by comparing the automatically generated code with the manually implemented code, both compliant to the same SDL specification: this comparison is based on a selection of metrics measured on both codes by means of commercial static analysis tools. Notwithstanding the different structure of the two codes, we appropriately selected and aggregated the obtained results in order to use them as indicators of code size, control flow complexity and integration flow complexity. For a better comparison of the two codes, we have also introduced a novel complexity metric, which compares the control flow complexity with the integration flow of the two different software architectures. The aim of the paper is not merely to evaluate the code generator used, but rather to propose a set of techniques that can be used to conduct similar evaluations. Copyright © 2005 John Wiley & Sons, Ltd.

The Use Case formalism is an effective way of capturing both business process and functional system requirements in a very simple and easy-to-learn way. Use Cases may be modeled in a graphical way (e.g. using the UML notation), mainly serving as a table of content for Use Cases. System behavior can more effectively be specified by structured natural language (NL) sentences. The use of NL as a way to specify the behavior of a system is however a critical point, due to the inherent ambiguity originating from different interpretations of natural language descriptions. We discuss the use of methods, based on a linguistic approach, to analyze functional requirements expressed by means of textual (NL) Use Cases. The aim is to collect quality metrics and detect defects related to such inherent ambiguity. In a series of preliminary experiments, we applied a number of tools for quality evaluation of NL text (and, in particular, of NL requirements documents) to an industrial Use Cases document. The result of the analysis is a set of metrics that aim to measure the quality of the NL textual description of Use Cases. We also discuss the application of selected linguistic analysis techniques that are provided by some of the tools to semantic analysis of NL expressed Use Case.

Abstract This paper proposes a modelling approach suitable for formalizing fault tolerant systems, taking into account different fault scenarios. Verification of the properties of such systems is then performed using model checking. A general framework for the formal specification and verification of fault tolerant systems is defined starting from these principles, and experience with its application to two case studies is then presented. Copyright © 2002 John Wiley & Sons, Ltd.

In this paper we present a verification framework to check properties of full CCS terms. These properties are expressed in an action-based logic, and the proof technique is model checking, based on the transition system corresponding to the CCS term. Our approach also allows some kinds of properties to be proved if the transition systems are infinite. Of course, in these cases we only have a semi-decision method. The idea is to use (a sequence of) finite-state transition systems which approximate the, possibly infinite, transition system corresponding to a term. To this end we define a particular notion of approximation, suitable in proving liveness and safety properties of the process terms. Then we show that the class of provable properties might also depend on the way chains of approximations are built and we provide a set of notions to compare and choose among different approximation chains.

This paper presents an approach for the specification and the verification of the correctness of fault tolerant system designs achieved by the application of fault tolerant techniques. The approach is based on process algebras, equivalence theory and temporal logic. The behaviour of the system in the absence of faults is formally specified and faults are assumed as random events which interfere with the system by modifying its behaviour. The fault tolerant technique is formalized by a context that specifies how replicas of the system cooperate to deal with faults. The system design is proved to behave correctly under a given fault hypothesis by proving the observational equivalence between the system design specification and the fault-free system specification. Additionally, model checking of a temporal logic formula which gives an abstract notion of correct behaviour can be applied to verify the correctness of the design. The opportunities given by the expression of the fault hypothesis using temporal logic are discussed. The actual usability of the approach in real case studies is supported by the availability of automatic tools for equivalence checking and for proving the temporal logic properties by model checking.

The development and validation of fault-tolerant computers for critical real-time applications are currently both costly and time consuming. Often, the underlying technology is out-of-date by the time the computers are ready for deployment. Obsolescence can become a chronic problem when the systems in which they are embedded have lifetimes of several decades. This paper gives an overview of the work carried out in a project that is tackling the issues of cost and rapid obsolescence by defining a generic fault-tolerant computer architecture based essentially on commercial off-the-shelf (COTS) components (both processor hardware boards and real-time operating systems). The architecture uses a limited number of specific, but generic, hardware and software components to implement an architecture that can be configured along three dimensions: redundant channels, redundant lanes, and integrity levels. The two dimensions of physical redundancy allow the definition of a wide variety of instances with different fault tolerance strategies. The integrity level dimension allows application components of different levels of criticality to coexist in the same instance. The paper describes the main concepts of the architecture, the supporting environments for development and validation, and the prototypes currently being implemented.

The paper presents an approach for the specification and verification of the correctness of dependable system designs achieved by the application of fault tolerant techniques based on equivalence relations and model checking techniques. The behaviour of the system in absence of faults is formally specified and faults are assumed as random events which interfere with the system by modifying its behaviour. The fault tolerant technique is formalized by a context, which specifies how replicas of the system cooperate to deal with faults. The system design is proved to satisfy the correctness property under a given fault hypothesis, by proving the observational equivalence between the system design specification and the fault free system specification. Additionally, model checking of a temporal logic formula which gives an abstract notion of correct behaviour can be applied to verify the correctness of the design.