Universität Bremen  
  Universität Bremen FB3 TZI BISS  
  AG BS > Lehre > WiSe 2002/03 > Deutsch
English
 

Safety-Critical Systems 4: Engineering of Embedded Software Systems, WiSe 2002/03
 

Veranstalter / read by: Jan Bredereke

Termine:
V: Di. 15:15-16:45 Uhr, MZH 8090
Ü: Do. 10:00-12:00 Uhr, GW2 B2740 (geändert)

dates:
lecture: Tue 3:15-4:45 pm, MZH 8090
seminar: Thu 10:00 am - 12:00 noon, GW2 B2740 (changed)

ECTS: 6

Diese Veranstaltung wird wegen des internationalen Teilnehmerkreises in Englisch abgehalten. Trotzdem dürfen die Teilnehmer gerne Deutsch für ihre Aufgabenlösungen oder für Diskussionsbeiträge verwenden, falls sie möchten.

This course is held in English due to its international audience. Nevertheless, participants are welcome to choose German for handing in assignments or for discussions, if they like.

Context of the Safety-Critical Systems Lectures Series

This is a series of lectures and seminars of our initiative Graduate Studies in Safety-Critical Systems. It is intended for an international audience of engineers working in the field, graduate students working on their Diploma, Masters, PhD or Habilitation degrees in computer science or electrical engineering. Due to the international character of the initiative, lectures will be held in English. At present, the lecture series is divided into four parts, each part planned as a two plus two hours/week lecture for one term:

  • Safety-Critical Systems 1:
    Basic concepts - problems - methods - techniques (SoSe02 term)
  • Safety-Critical Systems 2:
    Management aspects - standards - V-Models - TQM - assessment - process improvement (SoSe01 term)
  • Safety-Critical Systems 3:
    Formal methods and tools - model checking - testing - partial verification - inspection techniques - case studies (WiSe01/02 term, SoSe03 term)
  • Safety-Critical Systems 4:
    Engineering of Embedded Software Systems     (new, this term)

These parts can be attended in any order.

The first three parts are read by Jan Peleska, the fourth one is read by Jan Bredereke.

Objectives of the Safety-Critical Systems 4 Lecture

I understand the term engineering as the systematic, rigorous working style of an engineer. An engineer produces and validates construction plans before building the actual system. A system is embedded if it is part of a larger system; we cannot choose its interfaces freely. I will present the software engineering approach of David Parnas for this kind of software systems. Particular problems arise when the construction plans must be extended and changed later. Examples from the telephone switching domain will demonstrate this. Treating all versions and variants as a family can help. I plan to cover the following major topics:

  • rigorous description of requirements
  • decomposition into modules and documentation of the module structure
  • design of the module interfaces and their documentation
  • hierarchical structures in programs
  • families of systems

The course is intended for advanced students of computer science or electrical engineering who already know to program and maybe have some first experience in a software project.

Using New Media in Education

This lecture is a part of the on-going MMiSS project (MultiMedia Instruction in Safe Systems).

Goal of MMiSS

The aim of the MMiSS project, which is supported by bmbf (German Ministry for Education and Research) in its programme "New Media in Education", is to set up a multimedia Internet-based adaptive educational system, covering the whole subject of Safe Systems.

Thanks to the uniform integration of hypermedia course materials and formal programming tools, teaching in this area will attain a level hitherto impossible in this form. The system will be as suitable for learning on campus and for distance-learning with their associated routine of assignments, as it is for supervised-, co-operative- and self-study.

The system is to be introduced step by step, during the duration of the project, into the normal teaching of the project partners: the University of Bremen, the Distance-University of Hagen, the University of Freiburg, LMU Munich and the University of the Saarland. However, as the "Open-Source" model is to be used and teaching materials and tools are to be made freely available, a much greater national and international take-up is to be expected. To assist this, within the project, a forum is to be founded with German, international, and industrial members, which will advise on what new subjects should be added to the system, and its development and distribution. The forum's advice will be in view of both academic and future industrial applications.

Detailed Contents of the Lecture
  • 0. introduction
    topic of this lecture - overview of SCS4 - formalities
  • 1. rigorous description of requirements
    • 1.1 system requirements
      environmental quantities - functions of time - monitored and controlled quantities - the relations REQ and NAT - black-box view - modes - mode classes - conditions - events - history - "simultaneous" events
    • 1.2 software requirements
      the four-variable approach - input and output quantities - the relations IN, SOF, and OUT - software acceptability - the relation SOFREQ
    • 1.3 further issues
      system modes vs. environmental modes - accuracy and tolerance - using discrete clocks - resolution of time - standard functions for time - useful event class notation - requirements feasibility - fail-soft behaviour - merit functions - limitations of the approach
    • 1.4 tabular expressions
      different types of tables: normal, inverted, vector, decision - header cells / grid cells - semantics - cell connection graph (CCG) case - table predicate rule - table relation rule - raw element relation - fitting mode transtion tables into the scheme - table layout conventions
  • 2. what information should be provided in computer system documentation?
    overview of the documents - system requirements document - system design document - software requirements document- software behaviour document - software module guide - module interface specification - uses-relation document - module internal design document - service specification document - protocol design document - dictionary - abstraction function - program - LD relation - the rational design process - how to organize documentation
  • 3. decomposition into modules
    • 3.1 the criteria to be used in decomposing systems into modules
      different meanings of "module" - write-time modules - KWIC example - identifying likely changes - secret of a module - information hiding principle - the interface between modules - efficiency and implementation
    • 3.2 structuring complex software with the module guide
      handling large software - finding a module - avoiding module responsibility overlap - ensuring module responsibility coverage - when to write the guide - restricted modules - hidden modules - primary/secondary secret - the unversal top-level decomposition for software - hardware-hiding module - behaviour-hiding module - software decision module - eliminating fuzziness in the classification of modules
    • 3.3 hierarchical software structures
      definition of structure - definition of hierarchical structure - different kinds of software hierarchies - module decomposition hierarchy - calls hierarchy - uses hierarchy - Courtois hierarchy - gives-work-to hierarchy - created hierarchy - resource allocation hierarchy - can-be-accessed-by hierarchy - the danger of confusing these kinds of software hierarchies - uses hierarchy and Courtois hierarchy
    • 3.4 designing software for ease of extension and contraction
      "super", average, independent, or subsettable "super" system - loops in the uses relation - steps for designing a subsettable system - how to identify the subsets - list of programs for each module - uses matrix - four conditions for allowing program A to use program B - constructing the uses hierarchy - conflict removal by sandwiching - a level is not a module - deriving subsets from the uses relation - levels and virtual machines - evaluation criteria for a uses hierarchy - the one, fixed, variable pattern - example: an address processing system, with subsets and with extensions
    • 3.5 design of abstract interfaces
      interface - abstraction - appropriateness of an abstraction - abstract interface - device interface module - secret of a device interface module - undesired event assumptions - approach for designing device interface modules - reviews - example: the A-7's air data computer - several more detailed design problems and tradeoffs - when won't it work? - the fundamental principles of abstract interface design - abstract interfaces for other kinds of modules
  • 4. families of systems
    • 4.1 motivation: maintenance problems in telephone switching
      background on telephone switching - Intelligent Network (IN) - basic call state model - feature interaction problems - causes for feature interactions - approaches for tackling feature interactions - requirements structuring problems - new architectures
    • 4.2 families of programs
      definition of a program family - "classical" method of producing program families - stepwise refinement and module specification for producing program families - family of products in other fields - product line - FAST approach - domain engineering and application engineering - three basic assumptions of FAST - stages towards an engineered family - predicting change - example: FAST applied to Commands and Reports - commonality analysis document - economics of FAST - finding domains where FAST is worth applying - applying FAST incrementally - transitioning to a FAST process
    • 4.3 families of requirements
      why focus on requirements - feature-oriented requirements specification approaches - formal incremental specification approaches and non-monotonous changes - formal approaches for feature specification - superimposition - CoRE method - key ideas on families of requirements specifications - overview of CSP-OZ - case study on telephone switching requirements - the "feature" construct and the "familymember" construct - generating family members - controlled non-monotonous changes - the "remove" construct - avoiding feature interactions by explicitly introduced concepts - detecting feature interactions by type checks - documenting dependences - hierarchical requirements specification - tool support - open issues - families of CSP test specifications

Slides

The complete set of 536 slides is available in pdf (1.9 MB) and in 8-per-page/ps/gzip (0.99 MB). This is the printout version (with italics instead of red for emphasizing).

You can also still get the slides in the chunks in which I put them online during the course. At Chapter 4.3 below, you will additionally find the three specifications in CSP-OZ which are not part of the slides.

Assignments
  • 1. bicycle odometer - environmental quantities (pdf - ps/gzip)
    issued: Oct. 15, 2002   due: Oct. 24, 2002
  • 2. bicycle odometer - system requirements specification (pdf - ps/gzip)
    issued: Oct. 22, 2002   due: Oct. 31, 2002
  • 3. bicycle odometer - software requirements specification (pdf - ps/gzip)
    issued: Oct. 29, 2002   due: Nov. 14, 2002
  • 4. bicycle odometer - software implementation (pdf - ps/gzip)
    issued: Nov. 12, 2002   due: Nov. 28, 2002
  • 5. bicycle odometer - module internal design document (pdf - ps/gzip)
    issued: Nov. 26, 2002   due: Dec. 5, 2002
  • 6. key words in context - initial system (pdf - ps/gzip)
    issued: Dec. 3, 2002   due: Dec. 12, 2002
  • 7. key words in context - maintenance of the system (pdf - ps/gzip)
    issued: Dec. 12, 2002   due: Jan. 9, 2003
  • 8. key words in context - uses hierarchy (pdf - ps/gzip)
    issued: Jan. 8, 2003   due: Jan. 16, 2003
  • 9. parsing dates - abstract interface design (pdf - ps/gzip)
    issued: Jan. 15, 2003   due: Jan. 21/Feb. 4, 2003

Please submit your solutions both on paper and by email to brederek@tzi.de (as a PostScript or Pdf file).

Mark ("Schein")

Criteria negotiated by lecturer and participants on Oct. 15, 2002:

  • n assignments during term, 7 <= n <= 14
  • assignments can be solved in groups of two
  • n-1 assignments must be handed in
  • average of n-1 best marks must be >= 60%
  • oral exam ("Fachgespräch") at end of term
    • 15-20 min
    • in the groups of two
    • individual marks

Text Worth Reading

The lecture is based on a number of research papers and one book. The list below will be extended during the course.

Papers not available online or in the library can be borrowed from our secretary in MZH 8190 for a short time to copy them.

Accessing papers online through the catalogue of the library of the University of Bremen:
take the above link, search for "numbers", enter the ISSN or ISBN number, then follow the links.

[PaMa95] David Lorge Parnas and Jan Madey.
Functional documents for computer systems. Sci. Comput. Programming, 25 no. 1 pp. 41-61, October 1995.
ISSN 0167-6423. Available online through the catalogue of the library of the University of Bremen.
[Pet00] Dennis K. Peters.
Deriving Real-Time Monitors from System Requirements Documentation. PhD thesis, McMaster Univ., Hamilton, Canada, January 2000. (ps/gzip - pdf)
Relevant: Chapters 1.1, 5, Appendix A
[Par72] David Lorge Parnas.
On the criteria to be used in decomposing systems into modules. Commun. ACM, 15 no. 12 pp. 1053-1058, 1972.
ISSN 0001-0782. Available on paper and online through the catalogue of the library of the University of Bremen, signature: z kyb 300 j/670.
Reprinted in [HoWe01].
[PCW85] David Lorge Parnas, Paul C. Clements, and David M. Weiss.
The modular structure of complex systems. IEEE Trans. Softw. Eng., 11 no. 3 pp. 259-266, March 1985.
Reprinted in [HoWe01].
ISSN 0098-5589. Available on paper through the library of the University of Bremen, signature: z kyb 400 j/062.
[Par74] David Parnas.
On a `buzzword': Hierarchical structure. In IFIP Congress 74, pages 336-339. North-Holland, 1974.
Reprinted in [HoWe01].
[Par79] David Lorge Parnas.
Designing software for ease of extension and contraction. IEEE Trans. Softw. Eng., SE-5 no. 2 pp. 128-138, March 1979.
ISSN 0098-5589. Available on paper through the library of the University of Bremen, signature: z kyb 400 j/062.
Reprinted in [HoWe01].
[HBPP81] Kathryn Heninger Britton, R. Alan Parker, and David L. Parnas.
A procedure for designing abstract interfaces for device interface modules. In Proc. of the 5th Int'l. Conf. on Software Engineering - ICSE 5, pages 195-204, March 1981.
Reprinted in [HoWe01].
[Par76] David Lorge Parnas.
On the design and development of program families. IEEE Trans. Softw. Eng., 2 no. 1 pp. 1-9, March 1976.
ISSN 0098-5589. Available on paper through the library of the University of Bremen, signature: z kyb 400 j/062.
Reprinted in [HoWe01].
[WeLa99] David M. Weiss and Chi Tau Robert Lai.
Software Product Line Engineering - a Family-Based Software Development Process. Addison Wesley Longman, 1999.
ISBN 0-201-69438-7. Not in the library of the University of Bremen.
[Bre01b] Jan Bredereke.
A tool for generating specifications from a family of formal requirements. In Myungchul Kim, Byoungmoon Chin, Sungwon Kang, and Danhyung Lee, editors, Formal Techniques for Networked and Distributed Systems, pages 319-334. Kluwer Academic Publishers, August 2001.

There is a book with several of Parnas' seminal papers. It has a 1-2 page introduction to each of these papers explaining the history and current relevance of the paper, and it has comments by Parnas for each chapter. The book contains, among others, [Par72], [PaCl86], [PCW85], [Par74], [Par79], [HBPP81], [Par76], and [PaWe85]. It does not contain, however, [PaMa95], [Pet00], the book on program families, and everything on requirements families.

[HoWe01] Daniel M. Hoffman and David M. Weiss, editors.
Software Fundamentals - Collected Papers by David L. Parnas. Addison-Wesley, March 2001.
ISBN 0-201-70369-6. Available on paper through the catalogue of the library of the University of Bremen, signature: td 3679 (cannot be borrowed; location: DL artec).

Additional Background Reading

[vSPM93] A. John van Schouwen, David Lorge Parnas, and Jan Madey.
Documentation of requirements for computer systems. In IEEE Int'l. Symposium on Requirements Engineering - RE'93, pages 198-207, San Diego, Calif., USA, 4-6 January 1993. IEEE Comp. Soc. Press.
[LaRö01] A. Lankenau and T. Röfer.
The Bremen Autonomous Wheelchair - a versatile and safe mobility assistant. IEEE Robotics and Automation Magazine, "Reinventing the Wheelchair", 7 no. 1 pp. 29-37, March 2001.
ISSN 1070-9932. Available on paper and online through the catalogue of the library of the University of Bremen.
[JaKh99] Ryszard Janicki and Ridha Khedri.
On a formal semantics of tabular expressions. CRL Report 379, McMaster University, Hamilton, Ontario, Canada, September 1999. (ps/gzip - pdf)
[PaCl86] David Lorge Parnas and Paul C. Clements.
A rational design process: how and why to fake it. IEEE Trans. Softw. Eng., 12 no. 2 pp. 251-257, February 1986.
ISSN 0098-5589. Available on paper through the library of the University of Bremen, signature: z kyb 400 j/062.
Reprinted in [HoWe01].
[Lam88] David Alex Lamb.
Software Engineering: Planning for Change. Prentice-Hall, 1988.
ISBN 0-13-822982-1. Not available through the library of the University of Bremen, but can be borrowed remotely from other libraries. Not available from the publisher anymore.
[Cou85] P.-J. Courtois.
On time an space decomposition of complex structures. Commun. ACM, 28 no. 6 pp. 590-603, June 1985.
ISSN 0001-0782. Available on paper and online through the catalogue of the library of the University of Bremen, signature: z kyb 300 j/670.
[Par77] David Lorge Parnas.
Use of abstract interfaces in the development of software for embedded computer systems. NRL Report 8047, Naval Research Lab., Washington DC, USA, 3 June 1977. Reprinted in Infotech State of the Art Report, Structured System Development, Infotech International, 1979.
[PaWe85] David L. Parnas and David M. Weiss.
Active design reviews: Principles and practices. In Proc. of the 8th Int'l Conf. on Software Engineering - ICSE 8, London, August 1985.
Reprinted in [HoWe01].
[Zav01] Pamela Zave.
Requirements for evolving systems: A telecommunications perspective. In 5th IEEE Int'l Symposium on Requirements Engineering, pages 2-9. IEEE Computer Society Press, 2001.
The paper can be downloaded from the author's site (follow the DFC link).
[Kat93] Shmuel Katz.
A superimposition control construct for distributed systems. ACM Trans. Prog. Lang. Syst., 15 no. 2 pp. 337-356, April 1993.
ISSN 0164-0925. Available on paper and online through the catalogue of the library of the University of Bremen.
[Mil98] Steven P. Miller.
Specifying the mode logic of a flight guidance system in CoRE and SCR. In Second Workshop on Formal Methods in Software Practice, Clearwater Beach, Florida, USA, 4-5 March 1998.
The paper can be downloaded from this site.

Related Activities of Other Groups and Organisations

 		 
   
Autor: jp 		 
  AG Betriebssysteme, Verteilte Systeme 
Zuletzt geändert am: 2. November 2022   Impressum