Proving the shalls

Incomplete, inaccurate, ambiguous, and vola-tile requirements have plagued the software industry since its inception. The convergence of model-based development and formal methods offers developers of safety-critical systems a powerful new approach to the early validation of requirements. This paper describes an exercise conducted to determine if formal methods could be used to validate system requirements early in the lifecycle at reasonable cost. Several hundred functional and safety requirements for the mode logic of a typical flight guidance system were captured as natural language “shall” statements. A formal model of the mode logic was written in the RSML^−e language and translated into the NuSMV model checker and the PVS theorem prover using translators developed as part of the project. Each “shall” statement was manually translated into a NuSMV or PVS property and proven using these tools. Numerous errors were found in both the original requirements and the RSML^−e model. This demonstrates that formal models can be written for realistic systems and that formal analysis tools have matured to the point where they can be effectively used to find errors before implementation. This project was partially funded by the NASA Langley Research Center under contract NCC1-01001 of the Aviation Safety Program.     

RMS design methodology for automotive framing systems BIW

Today, markets increasingly require more customized products, with shorter life cycles. In response, manufacturing systems have evolved from mass production techniques, through flexible automation and mass customization, to produce at mass production costs. Manufacturing facilities must incorporate more flexibility and intelligence, evolving toward reconfigurable manufacturing systems (RMS). RMS are amid to posses such flexibility and responsiveness and said to be the next generation of world class systems. RMS are designed for rapid change in structure and for a quickly adjustable production capacity. This paper proposes a new methodology (high level process) of framework using flexible and reconfigurable manufacturing systems principles for automotive framing systems as well as to provide a guideline to support the structure of different stages of the design methodology. The proposed methodology is presented through a case study using data based on actual production systems of three different styles; (process and design data) which supports the hypothesis of the research.     

Intelligent systems in the automotive industry: applications and trends

There is a common misconception that the automobile industry is slow to adapt new technologies, such as artificial intelligence (AI) and soft computing. The reality is that many new technologies are deployed and brought to the public through the vehicles that they drive. This paper provides an overview and a sampling of many of the ways that the automotive industry has utilized AI, soft computing and other intelligent system technologies in such diverse domains like manufacturing, diagnostics, on-board systems, warranty analysis and design. Oleg Gusikhin received the Ph.D. degree from St. Petersburg Institute of Informatics and Automation of the Russian Academy of Sciences and the M.B.A. degree from the University of Michigan, Ann Arbor, MI. Since 1993, he has been with the Ford Motor Company, where he is a Technical Leader at the Ford Manufacturing and Vehicle Design Research Laboratory, and is engaged in different functional areas including information technology, advanced electronics manufacturing, and research and advanced engineering. He has also been involved in the design and implementation of intelligent control applications for manufacturing and vehicle systems. He is the recipient of the 2004 Henry Ford Technology Award. He holds two U.S. patents and has published over 30 articles in refereed journals and conference proceedings. He is an Associate Editor of the International Journal of Flexible Manufacturing Systems. He is also a Certified Fellow of the American Production and Inventory Control Society and a member of IEEE and SME. Nestor Rychtyckyj received the Ph.D. degree in computer science from Wayne State University, Detroit, MI. He is a technical expert in Artificial Intelligence at Ford Motor Company, Dearborn, MI, in Advanced and Manufacturing Engineering Systems. His current research interests include the application of knowledge-based systems for vehicle assembly process planning and scheduling. Currently, his responsibilities include the development of automotive ontologies, intelligent manufacturing systems, controlled languages, machine translation and corporate terminology management. He has published more than 30 papers in referred journals and conference proceedings. He is a member of AAAI, ACM and the IEEE Computer Society. Dimitar P. Filev received the Ph.D. degree in electrical engineering from the Czech Technical University, Prague, in 1979. He is a Senior Technical Leader, Intelligent Control and Information Systems with Ford Research and Advanced Engineering specializing in industrial intelligent systems and technologies for control, diagnostics and decision making. He is conducting research in systems theory and applications, modeling of complex systems, intelligent modeling and control, and has published 3 books and over 160 articles in refereed journals and conference proceedings. He holds 14 granted U.S. patents and numerous foreign patents in the area of industrial intelligent systems He is the recipient of the 1995 Award for Excellence of MCB University Press. He was awarded the Henry Ford Technology Award four times for development and implementation of advanced intelligent control technologies. He is an Associate Editor of International Journal of General Systems and International Journal of Approximate Reasoning. He is a member of the Board of Governors of the IEEE Systems, Man and Cybernetics Society and President of the North American Fuzzy Information Processing Society (NAFIPS).     

What Kind of Verification of Formal Navigation Modelling for Reliable and Usable Web Applications?

In this paper we introduce briefly a notation dedicated to model navigation of Web applications and we discuss some strategies to assess the usability over navigation models built with such as a notation. Our aim with this kind of evaluation is to ensure (prior to implementation) that important users tasks can (or cannot) be performed using the system.     

A model-driven and task-oriented method for the development of collaborative systems

Groupware systems are usually difficult to design when following traditional methodologies and approaches for single user systems. In this regard, model-driven approaches have been gaining attention in recent years. In accordance with this paradigm, we developed the SpacEclipse method in a previous work, which is a method for developing collaborative modeling groupware based on the plug-ins in the Eclipse Modeling Project. However, this method presents some deficiencies that we have tried to overcome in this work. In order to achieve this goal, we have chosen the CIAM methodology, which allows the modeling of collaboration, users, tasks, sessions and interactive issues and which is also supported by Eclipse-based tools. In this paper, we explain how the integration of CIAM elements in the SpacEclipse method has been carried out and resulted in a new method with its own methodological, conceptual and technological frameworks. To prove the validity of the method, we have applied it to a re-engineering process in the development of an existing tool.     

On the model-based approach to nonlinear networked control systems

The problem of model-based stabilization of a nonlinear system based on its approximate discrete-time model is addressed, under the assumption that both the feedforward and the feedback paths are subject to network-induced constraints. These constraints include irregularity of the transfer intervals, time-varying communication delays, and the possibility of packet losses. A communication protocol that copes with these constraints is proposed. A “Stability+performance recovery” result for the nonlinear model-based networked control system (NCS) is formulated and proven.Simulation results presented confirm that the proposed method improves the maximum allowable transfer interval.     

Functional specification and proof of correctness for time dependent behaviour of reactive systems

A functional formalism for describing and reasoning about the time dependent behaviour of reactive systems is presented. The model is event based and can describe the histories of events with finite duration. It is a generalisation of the model of Caspi and Halbwachs (1986). A set of tools with their operations are introduced in the formalism and structure theorems characterising the algebra of events are proved. The power of this extended model is illustrated through the formal specification and correctness proof for a problem chosen from robotics.     

A design methodology for switched discrete time linear systems with applications to automotive roll dynamics control

In this paper we consider the asymptotic stability of a class of discrete-time switching linear systems, where each of the constituent subsystems is Schur stable. We first present an example to motivate our study, which illustrates that the bilinear transform does not preserve the stability of a class of switched linear systems. Consequently, continuous time stability results cannot be transformed to discrete time analogs using this transformation. We then present a subclass of discrete-time switching systems that arise frequently in practical applications. We prove that global attractivity for this subclass can be obtained without requiring the existence of a common quadratic Lyapunov function (CQLF). Using this result, we present a synthesis procedure to construct switching stabilizing controllers for an automotive control problem, which is related to the stabilization of a vehicle’s roll dynamics subject to switches in the center of gravitys (CG) height.     

Safe controllers design for industrial automation systems

The design of safe industrial controllers is one of the most important domains related to Automation Systems research. To support it, synthesis and analysis techniques are available. Among the analysis techniques, two of the most important are Simulation and Formal Verification. In this paper these two techniques are used together in a complementary way. Understanding plant behaviour is essential for obtaining safe industrial systems controllers; hence, plant modelling is crucial to the success of these techniques. A two step approach is presented: first, the use of Simulation and, second, the use of Formal Verification of Industrial Systems Specifications. The specification and plant models used for each technique are described. Simulation and Formal Verification results are presented and discussed. The approach presented in the paper can be applied to real industrial systems, and obtain safe controllers for hybrid plants. The Modelica modelling language and Dymola simulation environment are used for Simulation purposes, and Timed Automata formalism and the UPPAAL real-time model-checker are used for Formal Verification purposes.     

Compositional design of isochronous systems

The synchronous modeling paradigm provides strong correctness guarantees for embedded system design while requiring minimal environmental assumptions. In most related frameworks, global execution correctness is achieved by ensuring the insensitivity of (logical) time in the program from (real) time in the environment. This property, called endochrony or patience, can be statically checked, making it fast to ensure design correctness. Unfortunately, it is not preserved by composition, which makes it difficult to exploit with component-based design concepts in mind. Compositionality can be achieved by weakening this objective, but at the cost of an exhaustive state-space exploration. This raises a trade-off between performance and precision. Our aim is to balance it by proposing a formal design methodology that adheres to a weakened global design objective: the non-blocking composition of weakly endochronous processes, while preserving local design objectives for synchronous modules. This yields an effective and cost-efficient approach to compositional synchronous modeling.     

Automated compositional proofs for real-time systems

We present a framework for formally proving that the composition of the behaviors of the different parts of a complex, real-time system ensures a desired global specification of the overall system. The framework is based on a simple compositional rely/guarantee circular inference rule, plus a methodology concerning the integration of the different parts into a whole system. The reference specification language is the TRIO metric linear temporal logic.     

A simple model of driver behaviour to sustain design and safety assessment of automated systems in automotive environments

This paper proposes a structure for an “active” model of driver that enables to predict behaviour and performances in dynamic changing traffic conditions, with potential application both offline and online. A simple prototype of the system has been realised in software, and has been compared against observed data in a rudimentary validation. The comparison reveals that the software's outputs accord reasonably with the observed values, not only in terms of central tendency but also in terms of capability to predict the between-driver variability. The next step is to create a system capable of identifying driver characteristics and state from observed data. However, further research is needed in order to expand the model in several dimensions, primarily to represent more complex scenarios in the presence of advanced automation technologies.     

Design and verification of fault tolerant systems with CSP

Summary By means of an example, we present a formal method based on CSP to design fault tolerant systems. This method combines algebraic and assertional techniques to achieve complete formal verification of the fault tolerant system's correctness properties. Verification steps are executed in parallel with top-down design, so that correctness proofs can be clearly structured and their completeness easily checked. In this way formal verification is applicable not only to small examples but to reasonably large systems. Jan Peleska was born in 1958 in Hamburg, received his Diploma in Mathematics from the University of Hamburg in 1981 and a Ph.D. in Mathematics in 1982. From 1981 to 1984 he worked in research and software development projects in the field of accoustics. Since 1984 he has been working with Philips and DST in Kiel in the field of distributed information systems. Peleska's current research interests include fault tolerant systems, distributed database systems and formal design and verification methods.     

On the interconnection of message passing systems

One of the most important abstractions for designing distributed programs is the broadcast facility. In this paper, we study the interconnection of distributed message passing systems. We have shown that totally ordered systems cannot be properly interconnected in any form. However, we have provided a simple protocol to properly interconnect FIFO ordered systems.     

On the model-based networked control for singularly perturbed systems with nonlinear uncertainties

In this paper, the model-based networked control is addressed for a class of singularly perturbed control systems with nonlinear uncertainties. An approximate linear slow and fast control system of the plant, which can be obtained by omitting the nonlinear uncertainties, are used as a model to estimate the state behavior of the plant between transmission times. The stability of model-based networked control systems is investigated under the assumption that the controller/actuator is updated with the sensor information at constant time intervals. It is shown that there exists the allowable upper bound of the singular perturbation parameter such that the model-based networked control system is globally exponentially stable.     

Modeling and verification of real-time embedded systems with urgency

Real-time embedded systems are often designed with different types of urgencies such as delayable or eager, that are modeled by several urgency variants of the timed automata model. However, most model checkers do not support such urgency semantics, except for the IF toolset that model checks timed automata with urgency against observers. This work proposes an Urgent Timed Automata (UTA) model with zone-based urgency semantics that gives the same model checking results as absolute urgency semantics of other existing urgency variants of the timed automata model, including timed automata with deadlines and timed automata with urgent transitions. A necessary and sufficient condition, called complete urgency, is formulated and proved for avoiding zone partitioning so that the system state graphs are simpler and model checking is faster. A novel zone capping method is proposed that is time-reactive, preserves complete urgency, satisfies all deadlines, and does not need zone partitioning. The proposed verification methods were implemented in the SGM CTL model checker and applied to real-time and embedded systems. Several experiments, comparing the state space sizes produced by SGM with that by the IF toolset, show that SGM produces much smaller state-spaces.     

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.     

The lean gap: A review of lean approaches to large-scale software systems development

Lean approaches to product development (LPD) have had a strong influence on many industries and in recent years there have been many proponents for lean in software development as it can support the increasing industry need of scaling agile software development. With it's roots in industrial manufacturing and, later, industrial product development, it would seem natural that LPD would adapt well to large-scale development projects of increasingly software-intensive products, such as in the automotive industry. However, it is not clear what kind of experience and results have been reported on the actual use of lean principles and practices in software development for such large-scale industrial contexts. This was the motivation for this study as the context was an ongoing industry process improvement project at Volvo Car Corporation and Volvo Truck Corporation.