Systems engineering principles for the design of biomedical signal processing systems

Systems engineering aims to produce reliable systems which function according to specification. In this paper we follow a systems engineering approach to design a biomedical signal processing system. We discuss requirements capturing, specification definition, implementation and testing of a classification system. These steps are executed as formal as possible. The requirements, which motivate the system design, are based on diabetes research. The main requirement for the classification system is to be a reliable component of a machine which controls diabetes. Reliability is very important, because uncontrolled diabetes may lead to hyperglycaemia (raised blood sugar) and over a period of time may cause serious damage to many of the body systems, especially the nerves and blood vessels. In a second step, these requirements are refined into a formal CSP‖ B model. The formal model expresses the system functionality in a clear and semantically strong way. Subsequently, the proven system model was translated into an implementation. This implementation was tested with use cases and failure cases.Formal modeling and automated model checking gave us deep insight in the system functionality. This insight enabled us to create a reliable and trustworthy implementation. With extensive tests we established trust in the reliability of the implementation.     

A systematic approach to embedded biomedical decision making

An embedded decision making is a key feature for many biomedical systems. In most cases human life directly depends on correct decisions made by these systems, therefore they have to work reliably. This paper describes how we applied systems engineering principles to design a high performance embedded classification system in a systematic and well structured way. We introduce the structured design approach by discussing requirements capturing, specifications refinement, implementation and testing. Thereby, we follow systems engineering principles and execute each of these processes as formal as possible. The requirements, which motivate the system design, describe an automated decision making system for diagnostic support. These requirements are refined into the implementation of a support vector machine (SVM) algorithm which enables us to integrate automated decision making in embedded systems. With a formal model we establish functionality, stability and reliability of the system. Furthermore, we investigated different parallel processing configurations of this computationally complex algorithm. We found that, by adding SVM processes, an almost linear speedup is possible. Once we established these system properties, we translated the formal model into an implementation. The resulting implementation was tested using XMOS processors with both normal and failure cases, to build up trust in the implementation. Finally, we demonstrated that our parallel implementation achieves the speedup, predicted by the formal model.     

Modeling and formal verification of embedded systems based on a Petri net representation

In this paper we concentrate on aspects related to modeling and formal verification of embedded systems. First, we define a formal model of computation for embedded systems based on Petri nets that can capture important features of such systems and allows their representation at different levels of granularity. Our modeling formalism has a well-defined semantics so that it supports a precise representation of the system, the use of formal methods to verify its correctness, and the automation of different tasks along the design process. Second, we propose an approach to the problem of formal verification of embedded systems represented in our modeling formalism. We make use of model checking to prove whether certain properties, expressed as temporal logic formulas, hold with respect to the system model. We introduce a systematic procedure to translate our model into timed automata so that it is possible to use available model checking tools. We propose two strategies for improving the verification efficiency, the first by applying correctness-preserving transformations and the second by exploring the degree of parallelism characteristic to the system. Some examples, including a realistic industrial case, demonstrate the efficiency of our approach on practical applications.     

Knowledge representation and reasoning in the design of compositesystems

The design process that spans the gap between the requirements acquisition process and the implementation process, in which the basic architecture of a system is defined, and functions are allocated to software, hardware, and human agents. is studied. The authors call this process composite system design. The goal is an interactive model of composite system design incorporating deficiency-driven design, formal analysis, incremental design and rationalization, and design reuse. They discuss knowledge representations and reasoning techniques that support these goals for the product (composite system) that they are designing, and for the design process. To evaluate the model, the authors report on its use to reconstruct the design of two existing composite systems rationally     

Distributed Computation Multi-agent System

This article addresses a formal model of a distributed computation multi-agent system. This model has evolved from the experimental research on using multi-agent systems as a ground for developing fuzzy cognitive maps. The main paper contribution is a distributed computation multi-agent system definition and mathematical formalization based on automata theory. This mathematical formalization is tested by developing distributed computation multi-agent systems for fuzzy cognitive maps and artificial neural networks – two typical distributed computation systems. Fuzzy cognitive maps are distributed computation systems used for qualitative modeling and behavior simulation, while artificial neural networks are used for modeling and simulating complex systems by creating a non-linear statistical data model. An artificial neural network encapsulates in its structure data patterns that are hidden in the data used to create the network. Both of these systems are well suited for formal model testing. We have used evolutionary incremental development as an agent design method which has shown to be a good approach to develop multi-agent systems according to the formal model of a distributed computation multi-agent system.     

Evolutionary planning of virtualized cyber-physical compute and control clusters

Virtualization technology has the potential to notably advance the automation process in the domain of cyber-physical systems (CPS). It can improve both dependability and availability as well as significantly reduce the procurement, operation and maintenance costs of such systems. However, in the context of virtualization, research has put the most emphasis on topics of hardware utilization and fault-tolerance. There is little literature on how to model, integrate and consolidate a CPS by means of virtualization. In this paper we present a methodology for planning safe and efficient virtualized cyber-physical compute and control clusters – execution platforms for time-constrained virtual machines (VMs) that encapsulate CPS applications. We discuss the used methods, describe the corresponding models and the required system architecture. In contrast to typical resource allocation problems from other domains (e.g. cloud computing), in this case, the planning process must take real-time requirements of applications into account. In order to achieve this, we combine evolutionary algorithms with formal system performance analysis – in particular algorithms considered in classical scheduling theory. Such an approach allows not only to optimally dimension the compute and control clusters, but also provides strict guarantees regarding the timing predictability of the integrated CPS. Further, the embedment of a formal performance analysis technique notably eases the modeling of a system. As a consequence, the modeling process is fast, flexible and accessible not only to experts but also to system designers as they do not have to struggle with complex and time consuming mathematical formulations. Finally, our approach also provides answers to several practical questions that arise when integrating a CPS by means of virtualization.     

Model-based design of supervisory controllers for baggage handling systems

The complexity of airport baggage handling systems in combination with the required high level of robustness makes designing supervisory controllers for these systems a challenging task.We show how a state of the art, formal, model-based design framework has been successfully used for model-based design of supervisory controllers for an actual industrial baggage handling system, and for a real-time emulation model of an actual international airport.The high level modeling elements of the applied CIF model-based design framework allow the modeler to concentrate on implementing the baggage handling system design requirements, instead of programming PLC code. It also allows a modular and hierarchical design of the supervisory controller, and provides flexibility in adapting and extending the model. Validation of the controller and the uncontrolled plant by means of simulation and visualization made it possible to catch all modeling errors, leading to very short modeling, testing and error correction iteration loops.To the best of our knowledge, this is the first successful employment of formal, model-based design in the context of supervisory control for actual, industrial size baggage handling systems, that covers the entire development process from requirements up to and including validation, real-time PLC code generation and implementation.We give an overview of the model-based design framework, discuss several modeling issues, and analyze the results of the industrial applications. We do not go into full technical detail, due to nondisclosure agreements, but tell the story, and give lessons learned that we consider useful for practitioners.     

Methods for the Development of Distributed Real-Time Embedded Systems Using VDM

The development of distributed real-time embedded systems presents a signi-ffcant practical challenge both because of the complexity of distributed computation and because of the need to rapidly assess a wide variety of design alternatives in early stages when requirements are often volatile. Formal methods can address some of these challenges but are often thought to require greater initial investment and longer development cycles than is desirable for the development of noncritical systems in highly competitive markets.In this paper we propose an approach that takes advantage of formal modelling and analysis technology in a lightweight way, making signi cant use of readily available tools. We describe an incremental approach in which detail is progressively added to abstract system-level speci cations of functional and timing properties via intermediate models that express system architecture, concurrency and distribution. The approach is illustrated using a modelof a home automation system. The models are expressed using the Vienna Development Method (VDM) and are validated primarily by scenario-based tests.     

Aspect-Oriented Modeling and Verification with Finite State Machines

Aspect-oriented programming modularizes crosscutting concerns into aspects with the advice invoked at the specified points of program execution. Aspects can be used in a harmful way that invalidates desired properties and even destroys the conceptual integrity of programs. To assure the quality of an aspect-oriented system, rigorous analysis and design of aspects are highly desirable. In this paper, we present an approach to aspect-oriented modeling and verification with finite state machines. Our approach provides explicit notations (e.g., pointcut, advice and aspect) for capturing crosscutting concerns and incremental modification requirements with respect to class state models. For verification purposes, we compose the aspect models and class models in an aspect-oriented model through a weaving mechanism. Then we transform the woven models and the class models not affected by the aspects into FSP (Finite State Processes), which are to be checked by the LTSA (Labeled Transition System Analyzer) model checker against the desired system properties. We have applied our approach to the modeling and verification of three aspect-oriented systems. To further evaluate the effectiveness of verification, we created a large number of flawed aspect models and verified them against the system requirements. The results show that the verification has revealed all flawed models. This indicates that our approach is effective in quality assurance of aspect-oriented state models. As such, our approach can be used for model-checking state-based specification of aspect-oriented design and can uncover some system design problems before the system is implemented.     

Consolidating and applying the SDL-pattern approach: a detailed case study

This paper is on design methodology for communication systems. The SDL-pattern approach proposed recently is consolidated and applied rigorously and in detail to the design of a typical communication system on two levels of abstraction. The design is decomposed into a number of steps, each of which is carried out systematically, building on well-proven, generic pieces of solutions that have proven useful in previous projects. These generic solutions—termed SDL patterns—support reuse-driven design of communication systems, raise the vocabulary of protocol engineer to a problem-oriented level, assist the discovery and exploitation of commonalities, and lead to well-justified designs. The selection and use of SDL patterns is supported by a fine-grained incremental design process, the pattern definition takes advantage of formal design languages, and a set of heuristics addresses the decomposition of communication requirements. All these elements are presented and applied in detail to the design of a simple, but functionally complete communication system.     

Improving reliability of cooperative concurrent systems with exception flow analysis

Developers of fault-tolerant distributed systems need to guarantee that fault tolerance mechanisms they build are in themselves reliable. Otherwise, these mechanisms might in the end negatively affect overall system dependability, thus defeating the purpose of introducing fault tolerance into the system. To achieve the desired levels of reliability, mechanisms for detecting and handling errors should be developed rigorously or formally. We present an approach to modeling and verifying fault-tolerant distributed systems that use exception handling as the main fault tolerance mechanism. In the proposed approach, a formal model is employed to specify the structure of a system in terms of cooperating participants that handle exceptions in a coordinated manner, and coordinated atomic actions serve as representatives of mechanisms for exception handling in concurrent systems. We validate the approach through two case studies: (i) a system responsible for managing a production cell, and (ii) a medical control system. In both systems, the proposed approach has helped us to uncover design faults in the form of implicit assumptions and omissions in the original specifications.     

通信系统软件开发环境技术研究

通信系统的开发变得越来越复杂,各种技术侧重于系统开发的某个局部阶段,阻碍了这些技术的实际应用。该文从通信系统的特点出发,指出了开发这类系统的需求,分析了当前存在的技术对开发通信系统的支持,试图把这些方法统一到一个完整开发环境中。并从结构建模、行为建模、时间模型、系统验证和开发过程等几个方面重点分析了两类通信系统开发工具,指出某些存在的问题。最后进行总结并拟定了今后的研究重点。     

Formal models for user interface design artefacts

There are many different ways of building software applications and of tackling the problems of understanding the system to be built, designing that system and finally implementing the design. One approach is to use formal methods, which we can generalise as meaning we follow a process which uses some formal language to specify the behaviour of the intended system, techniques such as theorem proving or model-checking to ensure the specification is valid (i.e., meets the requirements and has been shown, perhaps by proof or other means of inspection, to have the properties the client requires of it) and a refinement process to transform the specification into an implementation. Conversely, the approach we take may be less structured and rely on informal techniques. The design stage may involve jotting down ideas on paper, brainstorming with users etc. We may use prototyping to transform these ideas into working software and get users to test the implementation to find problems. Formal methods have been shown to be beneficial in describing the functionality of systems, what we may call application logic, and underlying system behaviour. Informal techniques, however, have also been shown to be useful in the design of the user interface to systems. Given that both styles of development are beneficial to different parts of the system we would like to be able to use both approaches in one integrated software development process. Their differences, however, make this a challenging objective. In this paper we describe models and techniques which allow us to incorporate informal design artefacts into a formal software development process.     

Measuring and analyzing real-time performance

To satisfy the deadline requirements of hard real-time systems, programmers must be able to determine the maximum execution time of any task. The use of Flex, an experimental real-time language being developed for the Concord project, is examined. The Flex system embodies an empirical approach that first measures the actual timing behavior and then uses the measurement results to determine the parameters of a programmer-supplied timing model. This timing model gives the system the programmer's understanding of the program's timing behavior in terms of its asymptotic time complexity. The measurement system determines the exact values of model parameters using sophisticated statistical methods to derive the program's timing characteristics precisely. Flex is better than performance analyzers that examine only code because it can cope with more kinds of program structures and its does not depend on an underlying hardware model. The integration of measurement and formal analysis is discussed     

Model checking Trampoline OS: a case study on safety analysis for automotive software

Model checking is an effective technique used to identify subtle problems in software safety using a comprehensive search algorithm. However, this comprehensiveness requires a large number of resources and is often too expensive to be applied in practice. This work strives to find a practical solution to model‐checking automotive operating systems for the purpose of safety analysis, with minimum requirements and a systematic engineering approach for applying the technique in practice. The paper presents methods for converting the Trampoline kernel code into formal models for the model checker SPIN, a series of experiments using an incremental verification approach, and the use of embedded C constructs for performance improvement. The conversion methods include functional modularization and treatment for hardware‐dependent code, such as memory access for context switching. The incremental verification approach aims at increasing the level of confidence in the verification even when comprehensiveness cannot be provided because of the limitations of the hardware resource. We also report on potential safety issues found in the Trampoline operating system during the experiments and present experimental evidence of the performance improvement using the embedded C constructs in SPIN. Copyright © 2012 John Wiley & Sons, Ltd.     

Ready for testing: ensuring conformance to industrial standards through formal verification

The design of distributed, safety-critical real-time systems is challenging due to their high complexity, the potentially large number of components, and complicated requirements and environment assumptions that stem from international standards. We present a case study that shows that despite those challenges, the automated formal verification of such systems is not only possible, but practicable even in the context of small to medium-sized enterprises. We considered a wireless fire alarm system, regulated by the EN 54 standard. We performed formal requirements engineering, modeling and verification and uncovered severe design flaws that would have prevented its certification. For an improved design, we provided dependable verification results which in particular ensure that certification tests for a relevant regulation standard will be passed. In general we observe that if system tests are specified by generalized test procedures, then verifying that a system will pass any test following those test procedures is a cost-efficient approach to improve the product quality based on formal methods. Based on our experience, we propose an approach useful to integrate the application of formal methods to product development in SME.     

Optimized implementation of synchronous models on industrial LTTA systems

Synchronous models are used to specify embedded systems functions in a clear and unambiguous way and allow verification of properties using formal methods. The implementation of a synchronous specification on a distributed architecture must preserve the model semantics to retain the verification results. Globally synchronized time-triggered architectures offer the simplest implementation path, but can be inefficient or simply unavailable. In past work, we defined a mapping of synchronous models on a general class of distributed asynchronous architectures, for which the only requirement is a lower bound on the rate of activation of tasks. In this paper, we set tighter requirements on task execution rates, and we include a realistic modeling of communication delays, task scheduling delays and schedulability conditions, discussing the timing characteristics of an implementation on a system with a Controller Area Network (CAN). Next, the semantics preservation conditions are formulated as constraints in an architecture optimization problem that defines a feasible task model with respect to timing constraints. An automotive case study shows the applicability of the approach and provides insight on the software design elements that are critical for a feasible implementation.