L Dependable Cefnputing
`and Feult
`V
`-Tolerant Systerrge
`
`
`
`
`__IQ:-H-ow:an-soIjgflflflflflllflflllllfifll
`
`
`AHVHEI1WNUWEH?fiEH.l1'|IOS3l'l
`
`
`
`
`
`
` meme
`Diversity
`in Computerized
` Vflentrel Systems
`
`BOEING Ex. 1029, p. i
`
`

`
`
`
`Dependable Computing
`and Fault-Tolerant Systems
`
`§
`Edited by
`A. Aviiienis, H. Kopetz, J. C. Laprie
`
`Volume 2
`
`BOEING Ex. 1029, p. ii
`
`

`
`U. Voges (ed.)
`
`Software Diversity
`in Computerized
`Control Systems
`
`Springer-Verlag Wien tNew York
`
`BOEING Ex. 1029, p.
`
`iii
`
`

`
`
`
`Dipl.-Math. Udo Voges, Kernforschungszentrum Karlsruhe GmbH,
`Karlsruhe, Federal Republic of Germany
`
`With 41 Figures
`
`This work is subject to copyright.
`All rights are reserved,
`whether the whole or part of the material is concerned,
`specifically those of translation, reprinting, re-use of illustrations,
`broadcasting, reproduction by photocopying machine or similar means,
`and storage in data banks.
`© 1988 by Springer-Verlag/Wien
`Printed in Austria
`
`Library of Congress Cataloging-in-Publication Data
`Software diversity in computerized control systems.
`
`(Dependable computing and fault-tolerant systems ;
`Vol.2)
`Contents: Introduction I U.Voges — Railway
`applications / G. Haglin - Nuclear applications I
`U. Voges. P. Bishop — [etc.]
`1. Fault-tolerant computing. 2. Computer software-
`Reliability. 3. Automatic conuol—Data processing.
`1. Vegas, Udo, 1946-
`. l1.Ser|es.
`QA’i6.9.F38Sfi5
`1988
`005
`87-32367
`ISBN 0-387-82014-0 (U.S.)
`
`ISSN 0932-5581
`
`ISBN 3-211-82014-0 Springer-Verlag Wien-New York
`ISBN 0-387-82014-0 Springer-Verlag New York-Wien
`
`BOEING EX. 1029, p. iv
`
`

`
`Preface
`
`Software Diversity is one of the fault-tolerance means to achieve dependable
`systems.
`
`In this volume, some experimental systems as well as real—life applications
`of software diversity are presented. The history, the current state-of—the-rart
`and future perspectives are given.
`
`‘
`
`Although this technique is used quite successfully in industrial applications,
`further research is necessary to solve some open questions. We hope to
`report on new results and applications in another volume of this series within
`some years.
`
`Acknowledgements
`
`The idea of the workshop was put forward by me ohairpersons of JFIP WG
`10.4, J.-C. Laprie, .I. F. Meyer and Y. Tohrna, in January 1986, and the edi-
`tor of this volume was asked to organize the workshop.
`
`This volume was edited with the assistance of-the editors of the series, A.
`Aviiienis, H. Kopetz and J.-C. Laprie, who also had the function of
`reviewers.
`
`Karlsruhe, October 1987
`
`"
`
`U. Voges, Editor
`
`BOEING Ex. 1029. D. V
`
`

`
`Table of Contents
`
`. Introduction
`U. Voges
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. Railway Applications
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`ERICSSON Safety System for Railway Control .
`G. Hagelin
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`1
`
`. 7
`
`. 11
`
`. 23
`
`. Nuclear Applications
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Use of Diversity in Experimental Reactor Safety Systems
`U. Voges
`
`The PODS Diversity Experiment
`P. G. Bishop
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 29
`
`. 51
`
`. 85
`
`. Flight Applications
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`AIRBUS and ATR System Architecture and Specification .
`P. Traverse
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 95
`
`. University Research .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Tolerating Software Design Faults in a Command and
`.
`.
`.
`Control System .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`T. Anderson, P. A. Barrett, D. N. Halliwell, M. R. Moulding
`
`DEDIX 87 —— A Supervisory System for Design Diversity
`Experiments at UCLA .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`A. Aviz"ienz's, M. R. T. Lyu, W. Schiitz, K.-S. Tso, U. Voges
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 105
`
`. 109
`
`. 129
`
`. 169
`
`. Modellinglssues
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Reliability Modelling for Fault-Tolerant Software
`Report on a Workshop Held in Badgasteih, Austria, July 1986
`B. Littlewood, T. Anderson
`
`. Conclusion
`U. Voges
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. Annotated Bibliography
`U. Voges
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 173
`
`. 183
`
`. 189
`
`BOEING EX. 1029, p. Vi
`
`

`
`Tl
`
`BOEING EX. 1029, p. Vii
`
`

`
`1
`
`Introduction
`
`BOEING Ex. 1029, p. 1
`
`

`
`BOEING EX. 1029, p. 2
`
`

`
`Dependable computing is an issue which was already of much concern
`before this term got accepted and more widely used [Laprie 1985]. Espe-
`cially the aspects of safety and reliability made the application of fault toler-
`ance techniques necessary, since complete fault avoidance was impossible to
`achieve in general applications.
`
`As the causes for software failures are different from those of hardware, dif-
`
`ferent fault tolerance techniques are necessary. Software diversity is one of
`them.
`
`Software Diversity has many faces and many names. It probably started by
`simply naming it fault-tolerant programming [Ehnendorf 1972] and later
`redundant programming [Aviiienis 1975], but inorder to put more emphasis
`on the difference of the solutions, also distinct software (e. g.
`[Fischler
`1975] ), dissimilar software (e. g.
`[Martin 1982] ), and dual programming
`(e. g.
`[Ramamoorthy 1981] ) were used. In the course of further applica-
`tion of this technique, N-Version Programming (NVP) (e. g.
`[Aviiienis
`1977] ) and Multi-Version-Software (MVS) (e. g.
`[Kelly 1982] ) were
`other terms which were used. Besides Software Diversity NVP and MVS
`are now the most often used terms.
`
`Another technique which is very much related to NVP is the Recovery Block
`technique [Randell 1975]. The main difference between these two
`approaches is that the Recovery Block approach makes use of an acceptance
`test and activates the secondary alternate only in case of. a detected error,
`while in NVP all versions are activated all the time, and the acceptance test
`is replaced by a comparison of the different outputs. For a more complete
`comparison see Table 1.
`"'
`
`As an extension and generalization of this technique‘, the term Design Diver-
`sity is emerging, including not only Software Diversity, but also Hardware
`Diversity [Aviiienis 1986].
`
`The idea of applying diversity is not as new as it might be expected after
`
`BOEING Ex. 1029, p. 3
`
`

`
`
`
`4
`
`Voges
`
`Table 1. Comparison Between N-Version Programming and Recovery Blocks
`
`1
`
`Recovery Blocks
`L N-Version Programming
`error detection by comparison _| error detection by acceptance. testing
`error correction by masking
`error correction by recovery
`and voting
`and activation of secondary alternate
`voting and majority decision
`acceptance testing
`(relative test)
`(absolute test)
`A
`majority required
`one accepted alternate required
`always execution of all alternates
`execution of n+1 alternates
`only if n are erroneous
`serial execution normal
`parallel execution possible
`L dynamic redundancy
`
`L
`
`_L
`
`parallel execution normal
`serial execution possible
`static rerlttndancy
`
`|__—
`
`these remarks. In 1834, Dionysius Lardner writes ( [Lardner 1961] p. 177):
`The most certain and efiectual check upon errors which arise in the pro-
`cess of computation. is to cause the same computations to be made by
`separate and independent computers; and this check is rendered still
`more decisive if they make their computations by different methods.
`But it was also realized that this is not the only solution and that this solution
`still contains drawbacks and so Lardner continues:
`It is, nevertheless, a remarkable fact, that several computers, working
`separately and independently, do frequently commit precisely the same
`error; so that falsehood in this case assumes that character of con-.
`sistency, which is regarded as the exclusive attribute of truth. Instances
`of this are familiar to most persons who have had the management of the
`computation of tables.
`But because of the application of computer systems in application areas with
`high dependability requirements the interest
`in software diversity has
`increased.
`This volume contains as a main part written versions of presentations given
`on a one-antlua-half day Workshop on "Design Diversity in Action", which
`was organized by the IFIP Working Group 10.4 "Reliable Computing and
`Fault Tolerance" on June 27 and 28, 1986 in Badenfvienna in Austria.
`
`BOEING EX. 1029, p. 4
`
`

`
`Introduction
`
`5
`
`The aim of this workshop was to bring together the greatest diversity of peo-
`ple who use software diversity in industrial applications as well as those
`which are conducting experiments and evaluations. A list of questions was
`sent to the speakers of the workshop in order to have some of the main
`points covered from different perspectives.
`
`Since not all experiments and. applications of Software Diversity neither
`could be presented at the Workshop nor could be included with separate
`papers in this volume, an annotated bibliography is included. Some histori-
`cal remarks as well as references to a wide scope of experiments and appli-
`cations related to software diversity are mentioned.
`'
`
`In addition, a report on a workshop .on "Reliability Modelling for Fault-
`Tolerant Software" is included in this volume. It contains a list of open
`research issues in this area.
`
`It is hoped that in some future time a new workshop on this topic is organ-
`ized to draw together further application areas of software diversity, to show
`new ways to use it and to inform on gathered experiences. The editor will be
`happy to receive any information on additional experiments and applica-
`tions.
`
`References
`
`A. Aviiiienis, "Fault-Tolerance and Fault-Intolerance: Complemen-
`[Aviiicnis 1975]
`tary Approaches to Reliable Computing,” in Proe. Intern. Conf. on Reliable Software,
`Los Angelcs, CA, USA: 21-23 April 1975, pp. 458-464.
`
`A. Aviiienis and L. Chen, “On the Implementation of N-Version
`[Aviiienis 197?]
`Programming for Software Fault-Tolerance During Program Execution." in Proc. Comp-
`sac7.7, Chicago, IL, USA: November 1977, pp. 149-155.
`
`A. Aviaienis and J.-C. Laprie, “Dependable Computing: From Con-
`[Aviiiienis 1986]
`cepts to Design Diversity,” IEEE Proceedings, Vol. 74, No. 5. May 1986, pp. 629-638.
`
`[Elmendorf 1972] W. R. Elrnendorf, "Fault-Tolerant Programming,” in Proc. 2nd
`Intern. Syrup. on Fault-Tolerant Computing FTCS’2, Newton, MA, USA: 19-21 June
`1972, pp. 79-83.
`
`[Fischler 1975] M. A. Fischler, 0. Firschein, and D. L. Drew, "Distinct Software: An
`Approach to Reliable Computing," in Proc. Second USA-Japan Computer Conference,
`1975, pp. 573-579.
`
`I. P. J. Kelly, “Specification of Fault-Tolerant Multi-Version Software:
`[Kelly 1982]
`Experimental Studies of a Design Diversity Approach," UCLA, Computer Science
`Department, Dos Angeles, CA. USA, Tech. Rep. CSD-320927, September 1982.
`
`BOEING Ex. 1029, p. 5
`
`

`
` 6
`
`Voges
`
`J.-C. Laprie, "Dependable Computing and Fault Tolerance: Concepts
`[Lnprle 1985]
`and Terminology,” in Proc. 15th Intern. Symp. on Fouft~To£eront Computing FTCS‘ 15,
`Ann Arbor, MI, USA: 19-21 June 1985, pp. 2-11.
`
`D. Lardner, “Bebbage’s Calculating Engine; From the Edinburgh
`[Lardner 1961]
`Review, July, 1834, No. CXX," in Charles Babbage and His Calculating Engines, E.
`Morrison, Ed. Dover Publications, Inc. New York, 1961.
`
`D. J. Martin, “Dissimilar Software in High Integrity Applications in
`[Martin 1982]
`Flight Controls," in Proc. AGARD Symp. on Software Avionics, CPP—330, The Hague,
`The Netherlands: September 1982. pp. 36.1—36.13.
`
`C. V. Rnmarnoorthy, Y. R. Molc, F. B. Bastani, G. H. Chin. and
`[Ramamoorthy 1981}
`K. Suzuki, "Application of 5: Methodology for the Development and Validation of Reli-
`able Process Control Software," IEEE Trans. on Software Engineering, Vol. SE-‘F. No.
`6, November 1981, pp. 537-555.
`
`B. Randell, “System Structure for Software Fault Tolerance,” IEEE
`[Randell 1975}
`Trans. on Software Eng., Vol. SE~1, No. 2, June 1975, pp. 220-232.
`
`BOEING EX. 1029, p. 6
`
`

`
`2
`
`Railway Applications
`
`BOEING Ex. 1029, p. 7
`
`

`
`WI
`
`BOEING Ex. 1029, p. 8
`
`

`
`The application of Software Diversity in industrial applications beyond an
`experimental stage was apparently done first in a railway system. This first
`system as well as newer developments are described in the following paper
`by Hagelin.
`
`Bengt Sterner from the Statens Jamvagar (Swedish State Railways) was one
`who encouraged the use of diversity in the Gothenburg system. His involve-
`ment in this project can also be seen by the formal specification language
`used for the interlocking system [Sterner 1978], which was named STER-
`NOL.
`
`In an Italian train control system functionally diverse programs are running
`in sequence, and theirresults are compared for error detection [Frullini
`1984].
`
`For the Singapore Mass Rapid Transit Railway, part of the system is realized
`with two diverse redundant microprocessors having different design objec-
`tives and diverse software in order to minimize the number of common
`
`mode failures [Davies 1984].
`
`For licensing purposes for a railway safety system in Germany, not a parallel
`development, but an independent reverse development
`- from program
`object code to requirement specification - was performed with final com-
`parison of the two documents, original requirements specification and the
`back translated one. This is another kind of application of the diversity prin-
`
`ciple [Krebs 1984].
`
`The General Railway Signal Co. of Rochester, NY, USA, designed its com-
`puterized interlocking system called Vital Processor Interlocking with a sin-
`gle Intel8086 processor running two”: diverse programs written in assembly
`language.
`In case of a failure, a second back-up system (standby spare)
`takes over. The system is in operation in two railway companies in USA
`[Turner 1987].
`'
`
`A similar design is used by the Union Switch & Signal Co. of Pittsburgh,
`
`BOEING EX. 1029, p. 9
`
`

`
`10
`
`PA, USA [Turner 1987].
`
`Vogcs
`
`There exist some further applications of Software Diversity in the railway
`environment, which, however, have not left the experimental stage, e. g. sys-
`tems for a subway train control in Germany [Kapp 1981] and also in France.
`
`Some experimentation was made in Germany by Siemens and the federal
`railway systems (DB) with the use of diversity. but up to now the general
`opinion has been to rely on identical hardware and software, using simple
`redundancy means and applying a rather strict verification and validation
`procedure [Schwier 1987].
`
`References
`
`P. A. Davies, “The Latest Developments in Automatic Train Conn-"o .”
`[Davies 1934]
`in Proc. Intern. Com’. on Railway Safety Conrroi and Automation Towards the 21:: Con-
`tury, London, UK: 25-27 September 1984, pp. 272-279.
`
`,
`
`R. Frullini and A. Lazzari, "Use of Microprocessor in Fail-Safe on
`[Fruilini 1984]
`Board Equipment,” in Proc. Intern. Conf. on Railway Safety Control‘ and Automation
`Towards the 21.5‘: Century, London, UK: 25~2”.-' September 1984, pp. 292-299.
`
`K.-H. Kapp, R. Baum, E. Sartori, and R. I-Iarms, "Sicherheit durch
`[Kapp 1981]
`vollstiindige Diversitiit (Safety through complete Diversity - in German),’’ in Proc.
`Focitragttng Prozefirecitner 1981, Miinchen, FRG: Springer-Verlag BerIin«Heide1berg-
`New York, 10-11 March 1981, pp. 216-229.
`
`, H. Krebs and U. Haspel, “Ein Verfaluen zur Software-Verifikarion (A
`[Krebs 1984]
`Technique for Software Verification - in German]," Regelungsrechnische Praxis, Vol.
`26, 1984, pp. 73-78.
`
`[Schwier 1987] W. Schwier, Private communication, 1987.
`
`B. J. Sterner. “Computerised Interlocking System - a Mu'1Iidimen—
`[Sterner 1978]
`sional Structure in the Pursuit of Safety," IMer:i:E Railway Engineer Inrernarionai,
`November/December 1978, pp. 29-30.
`
`D. B. Turner, R. D. Burns. and H. Hecht. "Designing Micro-Based
`[Turner 1987]
`Systems for Fail-Safe 'I‘raveI," IEEE Spectrum, Vol. 24, No. 2, February 1987, pp. 58-
`63.
`
`BOEING EX. 1029, p. 10
`
`

`
`ERICSSON Safety System
`for Railway Control
`
`Gurmar Hagelin
`ERICSSON SIGNAL SYSTEMS AB
`P.0. Box 42 505
`S-126 12 Stockholm
`Sweden
`
`1. Introduction
`
`Traditionally, equipment used by railways have been grouped in vital and
`non-vital equipment. Vital equipment shall work in a fail-safe way. Inter-
`lockings and level crossing units are examples of vital equipment, and the
`train dispatching panel is an example of non-vital equipment.
`
`Fail-safe is in signalling industry defined as "a characteristic of a system
`which ensures that any malfunction affecting safety will cause thesystem to
`revert to a state that is generally known to be safe". A safe state is for
`instance a signal showing a stop aspect (red light).
`
`In a very strict way, railway systems can be defined to be fault tolerant.
`
`The fail—safe requirements have forced railway equipment designers to use
`special techniques and special components. You cannot use a standard (tele-
`phone) relay in fail-safe circuits because there is a risk that two contacts
`weld together in a way that carmot be detected. Therefore, special Safety
`Relays have been developed.
`
`Special components however are more expensive than standard components
`
`BOEING EX. 1029, p. 11
`
`

`
`12
`
`Ijagelin
`
`and relays are nowadays more expensive than electronic components.
`Therefore there is a demand to put electronics and computers into vital
`equipment. But how do you handle the fail-safe requirement in computer
`hardware and software? It is quite impossible to completely avoid faults in
`complex software systems, especially in real-time systems. And even if the
`software is fault-free, how do you prove that? Therefore you must accept
`that there always remain faults in software systems. In vital systems the
`effects of these faults must be detected and made non-dangerous.
`
`The ERICSSON solution of this problem is DIVERSITY. This means that
`we design two different packages of software. They are both executed in the
`process and the results are compared and must be equal. This principle is
`now used in computerized Interlockings and Automatic Train Control sys-
`tems in use in several countries. In the following chapters I will give short
`descriptions of these systems and after that discuss the methods we use at
`ERICSSON to" achieve safe systems-.
`
`2. Interlockings
`
`Interlockings are used in railway stations. The purposes of interlockings are
`to
`
`0
`
`0
`
`0
`
`0
`0
`
`safeguard the movements of the trains,
`
`prevent dangerous situations,
`
`handle operator commands,
`
`inform the operator(s),
`control and supervise wayside equipment,
`machines.
`
`like signals and point
`
`Traditionally, interlockings have been designed with mechanical or electro-
`mechanical components. ERICSSON started to work with computerized
`interlockings in the middle of the 19'?0’s. The first installation was put into
`commercial operation in 1978 in Gothenburg (Sweden).
`
`In 1978 we still used relays in parts of the system to interface the signals and
`points. Now we have a second generation of the system in operation. This
`second generation is fully electronic.
`The basic design of ERICSSON computer interlocltings is shown in Fig. 1.
`In the signal box we have the Central Equipment with
`0
`interlocking computer(s)
`
`BOEING Ex. 1029. p. 12
`
`

`
`Railway Control
`
`13
`
`r-....—_..—. — — — — — — — — — — — * — — — — — — —..—.1
`CENTRAL EQUIPMENT
`
`INTERLOCKING
`COMPUTER
`
`H OT
`
`
`
`
`I/O-UNITS
`
`I I I I I I I I l I I I I I I
`
`
`
`CONCENTRATOR
`
`
`
`Concentrators are connected to loops
`
`CONCENTRATOR
`
`coNcENTRATon
`
`CONCE NTRATOR
`
`
`
`
`CONCENTRATOR
`
`Fig. 1. Interlocking System Layout
`
`0
`
`0
`
`operator interface (VDU’s and keyboards)
`
`power supplies.
`
`Outdoors in the station area we have concentrators. Signals, point machines
`etc are connected to the concentrator. Between the concentrators and the
`central equipment we use a serial transmission system, organized in loops.
`The concentrators are located close to the controlled objects (to reduce cable
`
`lengths etc). In the concentrators we have
`
`0
`
`transmission equipment and
`
`0
`object controllers.
`In the first generation we designed the object controllers with relays, in the
`second generation they are fully electronic.
`
`The software in the interlocking computer can be divided into three parts
`
`BOEING EX. 1029, p. 13
`
`

`
`I4
`
`Hagelin
`
`(see Fig. 2). The programs to handle transmission, operator communication
`etc are written in assembler. These programs are "universal" in all installa-
`tions.
`
`;1B5ytes
`
`110
`ray...
`
`M,
`in fntlit Installations
`
`I TRANSMISSION
`OPERATOR com.
`
`PROGRAMS
`
`‘I
`
`INTERLOCKING
`
`sma
`
`D
`
`O N
`
`Fig. 2. Interlocking Memory Layout
`
`The interlocking programs are handling the interlocking conditions in the
`stations. These programs are the same in all stations in each market.
`Because of different signalling requirements, these programs have to be
`adopted to each market (country, railway, company). The interlocking pro-
`grams are written in a language.called STERNOL, which is specially
`designed to handle signalling problems. STERNOL is a language, restricted
`to handle Boolean variables and some very simple arithmetic calculations.
`The programs are documented in a way which is similar to traditional relay
`diagrams (see Fig. 3).
`
`In the object controllers we use electronics and microprocessors today. The
`software in these are written in Assembler and PL/M. Site data, which are
`
`the site description for the general programs, are produced by an off-line sys-
`tem. This is the part varying from installation to installation. All site depen-
`dent information is contained in this description.
`
`BOEING EX. 1029, p. 14
`
`

`
`Railway Control
`
`15
`
`E] -—U6-B—K-3-
`
`Q —K-4
`
`R2-I
`Tea-2
`R2-3
`
`1215-i—u|a<>2—-—ua<>3—R4-7 —-R6-6
`1215-a
`ua-1
`Tc-a ja-
`
`Tc-a
`1'2-ta
`
`f
`
`ua-a
`
`ue-1 —[l2BS-l—-UH-l
`T2-B —-izas-Ia
`
`[Z]
`
`K-4
`H<>3—MH-B
`
`rue-2
`K-DJ ua-3
`K-S
`
`K-El
`rc-a
`T2-a—12a5-a
`Ia-a—1aa5-a
`
`E] —K-4-ua-3——Ic-i
`
`T2-1
`xzas-1
`
`TB-1
`was-1
`
`]—
`
`—U8-4 —-TC-1-—K-4
`
`El
`
`T2-l
`T0-1
`IDES-IITIZBS-1}-
`
`[:1 —R2-6 —K-4 —u2<>2 —U2<>3 -—[R6-I
`
`RG-2
`as-3
`
`U6-5
`U2-B —us-a —PK-B
`
`ua-5
`
`E] —ua-5
`’
`
`K-4
`H<>3—-MM-a
`
`K-B U2-2]
`—[K-5]-[U2-3
`
`Fig. 3. Examples of STERNOL statements
`
`3. ATC
`
`In Railway Technology ATC stands for Automatic Train Control. ATC
`shall
`
`0
`
`help and supervise the drivers,
`
`0 warn the drivers and/or apply the brakes in all situations that can be
`dangerous.
`
`ATC systems normally have three parts:
`
`0 wayside equipment to pick up information from signals, interlockings
`etc,
`
`0
`
`0
`
`on-board equipment to supervise the driving,
`
`transmission between wayside equipment and on-board equipment.
`
`The basic design of the system is shown in Fig. 4. The information from the
`signals and interlockings is handled by electronic encoders. In the case of
`
`BOEING EX. 1029, p. 15
`
`

`
`I 6
`
`Hagelin
`
`computer interlocking, data is fed directly to the beacons without the use of
`encoders. The beacons, which are powered from the passing trains, are send-
`ing the information to the locomotives. On board of the train microproces-
`sors handle the information from the antenna, indicate it to the driver and
`
`together with information from the brake conduit. and the
`process it
`speedometer.
`
` Beacons
`
`Fig. 4. ATC System Layout
`
`The software in the ATC computer is written in Assembler and PL/NI. The
`size of thesoftware is about 32k byte.
`
`ERICSSON modern ATC-systems now are in operation in many countries.
`The first was operating in Sweden starting 1978.
`
`4. Methods
`
`The basic design principle in ERICSSON Safety Systems is DIVERSITY.
`In software this means that vital functions are designed independently by
`two teams. Both systems are executed in the processors. The results of the
`calculations have to match before they are regarded to be correct.
`
`Fig. 5 shows how diversity is used in the interlocking system. The two
`interlocking systems (A and B) are running in the interlocking computer.
`The comparators and detectors are built together into units (= object con-
`trollers) located in the concentrators. Each signal and point machine in the
`station has an individual object controller.
`
`BOEING EX. 1029, p. 16
`
`

`
`it
`
`Railway Control
`
`17
`
`CONTROL SYSTEM
`
`INTERLOCKING
`
`INTERLOCKING
`
`SYSTEM
`
`A
`
`SYSTEM
`
`B
`
`COMPARATOR
`
`DETECTION
`SYSTEM
`
`SIGNALS
`POINTS
`
`Fig. 5. Safety Layout of Computer Based Interlocking Systems JZS 750 and JZS 850
`
`Diversity is achieved by
`0
`terms and
`
`0
`
`design rules.
`
`Diversity is enforced by
`
`0
`
`external coding of data and
`
`,
`data organization.
`b
`External coding is achieved by coding the status messages from the object
`controllers. The Hamming distance between A- and B-messages is in most
`cases equal to 4. The two design teams are manned with different peopie.
`People are not allowed to move between the teams: in one of our projects
`they were even located in different cities. The teams are producing their own
`set of documentation.
`
`However, DIVERSITY is not the only method used in ERICSSON Safety
`
`BOEING EX. 1029, p. 17
`
`

`
`18
`
`Hagelin
`
`Systems. Other methods are
`
`use of closed loops,
`
`time (age) checks,
`
`verification and validation,
`
`two redundant clocks, and
`
`HW-checks.
`
`It is very important that safety systems are designed as closed loops. How-T
`ever you can never be sure that a loop. really is closed. Therefore it is neces-
`sary that any break in the loop is detected and actions are taken towards "the
`safe directions". This is handled in the following way in the interlocking. A
`command to signals etc has to be recalculated and retransmitted cyclically.
`The object controllers "know" this _ and are expecting commands to be
`repeated. If the retransmission will stop, for any reason, the object controll-
`ers will put signals to stop as a fail-safe operation. To handle the problem
`with "too old data", all messages in the transmission network, and some data
`in the computers have time tags. These are supervised. Too old data is
`regarded as faulty and will cause signals to go to stop.
`
`Safety validations are performed during all phases in development work (see
`Fig. 6). Validations are based on Hearings. We also use Fault Tree Analysis
`and Fault Effect Analysis. Fault Tree Analysis is based on the questions
`"what can be dangerous and what can cause danger". Fault Effect Analysis
`is based on the questions "what happens if
`Fault Effect Analysis is used
`both for safety and reliability, but is mostly used for hardware.
`
`is very important to have a stringent
`We also want to point out that it
`development method. In our systems diversity has been used to the greatest
`extend within software design. We have very few hardware units which are
`designed in a diversified way (just some I/0 circuits).
`
`5. Specifications
`
`A common questions is "How were your products specified". The answer is
`that the" specifications mostly were written in clear Swedish language (writ-
`ten text). Talking about specifications you must however realize that a
`specification can be divided into at least
`
`0
`
`0
`
`functional requirements and
`
`quality requirements (MTBF, probability of dangerous errors etc).
`
`BOEING EX. 1029, p. 18
`
`

`
`Railway Control
`
`19
`
`Activity
`
`Documents
`
`Safety
`Safety
`Reviewing Documents
`
`Requirgmgnts
`Specification
`
`System
`Description
`
`J
`
`Block
`5Pe¢5
`A
`
`Block
`5P°C5
`A
`
`Addition
`
`.
`
`.
`
`.
`Review
`
`P
`
`ro97:_"‘
`?;:ic;r:-
`
`Inspection
`Record
`
`Inspection
`Record
`
`Inspection
`Record
`
`Check
`Report,
`Descr. of
`Principles
`for Progr.
`
`_
`
`m °s::=:*
`
`Routines
`
`Lists
`
`Module Tests
`Block Tests
`
`Test Report
`(Checked)
`
`Fig. 6. Work Organization
`
`The last point was (and still is) crucial when we started the work in the
`1970’s. Some customers said "New systems shall be as good or better than
`old systems". The problem is that nobody can give figures about the old sys-
`tems.
`
`BOEING Ex. 1029, p. 19
`
`

`
`20
`
`Hagelin
`
`6. Experience
`
`Today, the systems described above are in operation in many installations in
`Sweden, Norway, Denmark and Finland. Within the next years they will be
`put into operation in some other countries like Switzerland, Turkey and Bul-
`garia.
`
`‘The answer to the
`ERICSSON experience is that diversity DOES pay.
`question "Would we do it again?" is definitely YES. Up till now we have,
`after commissioning, detected one error that could have been dangerous in a
`Non-Diversity solution.
`
`A common argument against Diversity is that it doubles the development
`cost. This is not true for two reasons. The first reason is that the system
`development is divided into steps. The cost of the steps
`
`!
`
`5
`
`0
`
`0
`
`0
`
`program specification,
`
`coding and
`
`program test
`
`is doubled, but the cost of the steps
`
`0
`
`0
`
`0
`
`0
`
`requirement specification,
`
`system specification,
`
`test specification and
`
`system test
`
`is NOT doubled.
`
`The second reason is that within a safety system you always find parts that
`have no safety requirements, for instance the printer interface. You must do
`some measurements to isolate these non-fail-safe from the fail-safe parts, but
`the work that has to be doubled is reduced.
`
`7. Future
`
`Our future work will go into two directions. The first is to introduce elec-
`tronics and computers into fail-safe products that still are designed with
`relays. The second will be to introduce more modern techniques into our
`existing products. An example here is to use more high-level languages. We
`also must put more efforts into specification techniques.
`
`BOEING Ex. 1029, p. 20
`
`

`
`Railway Control
`
`21
`
`References
`
`H. Andersson and G. Hagelin: Computer Controlled Interlocking
`[Andersson 1981]
`System, Ericsson Review, No. 2, 1981.
`
`H. Andersson: Experience from the Introduction of ATC in
`[Andersson 1983]
`Sweden, Ericsson Review, No. 1, 1983.
`
`O. Berg von Lind: Computers Can Now Perform Vital Functions Safely,
`[Lind 1979]
`Railway Gazette International, Nov. 1979.
`
`[Nordenfors 1986] D. Nordenfors and A. Sjiiberg: Computer-Controlled Electronic
`Interlocking System. ERILOCK 850, Ericsson Review, No. 1, 1986.
`
`[Sj6berg 1981]
`1981.
`
`A. Sjfibergz Automatic Train Control, Ericsson Review, No. 1,
`
`BOEING Ex. 1029, p. 21
`
`

`
`*1
`
`BOEING EX. 1029, p.22
`
`

`
`Ty
`
`Wnw
`
`3
`
`Nuclear Applications
`
`BOEING EX. 1029, p. 23
`
`

`
`BOEING EX. 1029, p. 24
`
`

`
`In the nuclear field, there have been several experiments with the application
`of software diversity. Three of them will be described in more detail in the
`following two papers. Voges reports on the results gathered in the early
`BPI-experiment and the design of the later MIRA-system, both done in
`Karlsruhe. Bishop then explains -an experiment conducted by three coun-
`tries. Besides these experiments, the following ones should be mentioned.
`
`EPRI
`
`In the late l970’s and early 1980’s, under the direction of the Electric Power
`Research Institute (EPRI) of the USA an experiment was made which used
`diversity as one of different
`techniques to be applied in the project
`[Rarnamoorthy 1981, Saib 1982]. The aim of the project was to develop a
`method for the construction of reliable software, which should be applied to
`
`a realistic nuclear power plant problem.
`
`In this project participants came from The Babcock & Wilcox Company,
`Science Applications, Inc., University of California at Berkeley, and General
`Research Corporation.
`
`Starting from the functional requirements, two teams developed indepen-
`dently a design, using the formal specification language RSL. After the
`verification of these designs, each team continued the development with
`detailed design, implementation, testing as well as validation and verification
`efforts. The final step was the comparison of the outputs of the two pro-
`grams.
`
`The main results of this project were: _\
`
`-
`
`-
`
`-
`
`The use of automated tools can largely assist the development process.
`
`The savings in testing far outweigh the cost of dual program develop-
`ment.
`
`The methods applied improved the likelihood of detecting errors when
`introduced.
`
`BOEING Ex. 1029. p. 25
`
`

`
`26
`
`Voges
`
`The interface problems were reduced.
`
`The software correctness was increased compared to more conventional
`experience.
`
`CANDU
`
`For the Darlington Generation Station (4x85O MW), which is currently
`under construction, a computerized reactor safety shutdown system is
`developed. It consists of two components, SDSl and SDS2. Each component
`has a similar computer configuration, but is from different manufacturers.
`Separate design teams develop the systems. Two programming languages
`are used: Fortran and Pascal. The complete system consists of 15 computers
`[Popovic 1986].
`
`The previous design, which consisted of a different layout, is also using
`diverse hardware, but identical programming languages. So far no shutdown
`was due to a software error in those reactors which are