|
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.
- 0. introduction
- 1. rigorous description of requirements
- 2. what information should be provided in computer
system documentation?
(chapter 2, up to p. 139: pdf
- 8-per-page/ps/gzip)
(chapter 2, p. 140 to p. 148: pdf
- 8-per-page/ps/gzip)
- 3. decomposition into modules
- 4. families of systems
- 4.1 motivation: maintenance problems in telephone
switching
(chapter 4.1:
pdf
- 8-per-page/ps/gzip)
- 4.2 families of programs
(chapter 4.2:
pdf
- 8-per-page/ps/gzip)
- 4.3 families of requirements
- CSP-OZ demo: one very simple telephone
(pdf
- ps/gzip)
- excerpt from case study on a telephone switching system
(pdf
- ps/gzip)
- excerpt from generated family member
(pdf
- ps/gzip)
- 5. appendix (collected references)
(chapter 4.3 to 5:
pdf
- 8-per-page/ps/gzip)
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
|
|