Formal Aspects of Component Software

This paper focuses on generating test cases from timed symbolic transition systems. At the heart of the generation process are symbolic execution techniques on data and time. Test cases look like finite symbolic trees with verdicts on their leaves and are based on a user-specified finite symbolic path playing the role of a test purpose. Generated test cases handle data involved in time constraints and uninitialized parameters, leveraging the advantages of symbolic execution techniques.

Programmable controllers are gaining prevalence even in distributed safety-critical infrastructures, e.g., in the railway and aerospace industries. Such systems are generally integrated using multiple loosely-coupled reactive components and must satisfy various critical requirements. Thus, their systematic testing is an essential task, which can be encumbered by their distributed characteristics. This paper presents a model-based integration test generation approach leveraging hidden formal methods based on the collaborating statechart models of the components. Statecharts can be integrated using various composition modes (e.g., synchronous and asynchronous) and then transformed (via a symbolic transition systems formalism – XSTS) into the input formalisms of model checker back-ends, namely UPPAAL, Theta and Spin in an automated way. The model checkers are utilized for test generation based on multiple coverage criteria. The approach is implemented in our open source Gamma Statechart Composition Framework and evaluated on industrial-scale distributed controller subsystems from the railway industry.

Many visions for model-driven component-based development emphasize models as the “single source of truth” by which different forms of analysis, specification, verification, and code generation are integrated. Such a vision depends strongly on a clear modeling language semantics that provides different tools and stakeholders with a common understanding of a model’s meaning. In this paper, we report on a mechanization of a formal semantics in the Isabelle theorem prover for key aspects of the SAE standard AADL modeling language. A primary goal of this semantics is to support component-oriented contract specification and verification as well as code generation implemented in the HAMR AADL model-driven development tool chain. We provide formal definitions of run-time system state, execution steps, reachable states, and property verification. Use of the mechanization for real-world applications is supported by automated HAMR translation from AADL models into the Isabelle specifications. In addition to general verification support, we define well-formedness properties and associated proofs for models, system states, and traces that are automatically proven for HAMR-generated Isabelle models.

Deciding how data should be transferred among Web services is an important part of their architecture design. Basically, each piece of data is transferred in either PUSH or PULL style. The architect’s selection of data transfer methods generally has a great impact on both the overall structure and performance of Web services. However, little work has been done on helping architects to select suitable data transfer methods. In this paper, we present a formal model to abstract some parts of Web services architecture that are not affected by the selection of data transfer methods, and based on the model, we propose an architecture level refactoring for changing data transfer methods. Also, we present an algorithm to generate prototypes of Web services from the architecture model and selected data transfer methods, and proved the correctness of the algorithm. Furthermore, we developed a tool that provides a graph-based UI for the refactoring and can generate executable prototypes of Web services. To evaluate our method, we conducted case studies for several Web applications and confirmed that the generated prototypes can be used to estimate the performance.

Modeling and verifying the behavior of Cyber-Physical Systems (CPS) with complex interactions is challenging. Traditional languages such as SysML diagrams are not enough to capture CPS coordination. In this paper, we propose a novel approach called SysReo, which extends SysML diagrams (RD, BDD, IBD, SD) with the Reo coordination language. Our main objective is to enhance the interoperability of CPS by providing a more precise representation of system behavior and interaction protocols. To achieve this goal, we extend the SysML sequence diagram (SD) with Reo to create the SysReo SD. Through this integration, we bridge the gap between traditional modeling languages and the coordination demands of CPS. We develop an algorithm to generate Constraint Automata (CA) from SysReo SD, which ensures that CPS components can seamlessly work together. These automata are used in a verification tool that checks formulas expressed in Linear Temporal Logic (LTL). By leveraging LTL and Constraint Automata, we enhance the precision and rigor of CPS verification processes, while guaranteeing that CPS components can seamlessly work together. Furthermore, we apply our approach to a medical CPS case study, illustrating its effectiveness in identifying design flaws early and ensuring system behavior aligns with desired properties.

The reliability of concurrent and distributed systems often depends on some well-known techniques for fault tolerance. One such technique is based on checkpointing and rollback recovery. Checkpointing involves processes to take snapshots of their current states regularly, so that a rollback recovery strategy is able to bring the system back to a previous consistent state whenever a failure occurs. In this paper, we consider a message-passing concurrent programming language and propose a novel rollback recovery strategy that is based on some explicit checkpointing operators and the use of a (partially) reversible semantics for rolling back the system.

A promising way of integrating formal methods into industrial system design is to endow industrial modeling tools with automatic formal analyses. In this paper we identify some challenges for providing such formal methods “backends” for cyber-physical systems (CPSs), and argue that Maude could meet these challenges. We then give an overview of our research on integrating Maude analysis into the OSATE tool environment for the industrial CPS modeling standard AADL.

Since many critical distributed CPSs are “logically synchronous,” a key feature making automatic formal analysis practical is the use of synchronizers for CPSs. We identify a sublanguage of AADL to describe synchronous CPS designs. We can then use Maude to effectively verify such synchronous designs, which under certain conditions also verifies the corresponding asynchronous distributed systems, with clock skews and communication delays. We then explain how we have extended our methods to multirate systems and to CPSs with continuous behaviors.

We illustrate the effectiveness of Maude-based formal model engineering of industrial CPSs on avionics control systems and collections of drones. Finally, we identify future directions in this line of research.

Component-based software engineering (CBSE) is a widely used software development paradigm. With software systems becoming increasingly sophisticated, CBSE provides an effective approach to construct reusable, extensible, and maintainable software systems. Formal verification provides a rigorous and systematic approach to validate the correctness of software systems by mathematically proving properties or checking them exhaustively against specified requirements. Using formal verification techniques in component-based development can further enhance the correctness of the development process. However, the adoption of component-based development supported by formal methods is hardly widespread in the industry. It serves to a limited extent in domains with stringent requirements for safety and reliability. In this paper, we aim to analyze the successful application scenarios of formal methods in component-based development, identify the challenges faced during their application, and explore methods to further broaden their adoption.

The International Symposium on Formal Aspects of Component Software (FACS) was inaugurated two decades ago in response to the major software development paradigm shift from structured development and object-oriented development to component-based software development (CBSD) and service-oriented architecture (SOA). FACS is dedicated to fostering a deeper understanding of the distinctive aspects, promoting research, education, technological advancement, and the practical application of CBSD technology. On the 20th anniversary of FACS, it is appropriate to briefly recall its background and history, thereby highlighting its contributions to the community. Taking this opportunity, we focus on the discussion to elucidate the important aspects of component software that require to be and have been considered in formal theories. Leveraging the refinement of component and object-oriented systems (rCOS) as a framework, we provide an overview of these formal theories and discuss their relationships. We intend to express a vision that different theories and methods are required for different aspects in a CBSD process, and also different formal theories are required even for a particular aspect. However, ensuring their consistent application remains a major challenge and this is a main barrier to the effective industry adoption of CBSD. Furthermore, we delineate emerging challenges and prospects associated with integrating formal methods for modelling and design human-cyber-physical systems (HCPS) - hybrid integration encompassing cyber systems, physical systems, and the mixed human and machine intelligence.

This paper provides an overview on recent work on Team Automata, whereby a network of automata interacts by synchronising actions from multiple senders and receivers. We further revisit this notion of synchronisation in other well known concurrency models, such as Reo, BIP, Choreography Automata, and Multiparty Session Types.

We address realisability of Team Automata, i.e., how to infer a network of interacting automata from a global specification, taking into account that this realisation should satisfy exactly the same properties as the global specification. In this analysis we propose a set of interesting directions of challenges and future work in the context of Team Automata or similar concurrency models.

In 2009, the Simple Language of Communicating Objects (Slco) Domain-Specific Language was designed. Since then, a range of tools have been developed around this language to conduct research on a wide range of topics, all related to the construction of complex, component-based software, with formal verification being applied in every development step. In this paper, we present this range, and draw connections between the various, at first glance disparate, research results. We discuss the current status of the Slco framework, i.e., the language in combination with the tools, and plans for future work.