Testing of Reactive Systems, Summer Term 2008
Type | Time | Place | Start | Lecturer |
V/Ü | Tue 11:45--13:15 | AH 3 | 15. April 2007 | |
V/Ü | Wed 10--11:30 | AH 6 | 9. April 2007 |
Note: The lecture is V3, the exercises Ü1. The exercises will be held bi-weekly in one of the two lecture slots. The first lecture will be held Wednesday, 9. April, in AH 6. On the schedule you can also find the material, as it will be given out.
News
1 Aug 2008 | The results and preliminary grades of the written exam are now available. Use the login/password announced on Wednesday. On Monday, August 4 2008 between 10:00 and 12:00 the participants can have a look at the solution and corrected exams, Room 4210 or 4201b. |
22 Jul 2008 | The exam, scheduled for Wednesday, July 30, 10:00, will take place in the lecture hall AH 6. Please bring means of identification (passport/id-card/drivers license) and a valid student card. |
22 Jul 2008 | Reminder: Copies of the solutions to the exercises can be made from one master copy available in the secretarial office. |
10 Jul 2008 | The last part of the script is now available. So is the script in one file. |
9 Jul 2008 | |
9 Jul 2008 | Updated planning:
|
9 Jul2008 | |
8 Jul 2008 | |
2 Jul 2008 | Some final planning:
|
1 Jul 2008 | The lecture on Wednesday, July 2, will take place in AH 6, but from 13:30--15:00. I hope everybody can attend. |
24 June 2008 | The fifth exercise sheet is available here. |
24 June 2008 | Come and get some TAN numbers for the lecture evaluation! Tomorrow! In the Exercise Class! |
12 June 2008 | Find below a few references to additional reading material. |
11 June 2008 | The fourth exercise sheet is available here. Please note the remark on the Master exam on the sheet. Do not forget to register at the ZPA. The solutions of the third sheet are available for copying in the secretarial office (E1, Room 4213). |
10 June 2008 | The fourth part of the script is available. See here. |
3 May 2008 | There is no lecture on June 4. Homework can be delivered to my office (E1, Room 4210) or the secretarial office (E1, Room 4213) until Friday. |
28 May 2008 | Script up to lecture 9 and exercise sheet 3 are now online. Solutions to exercise series 2 are available for copying. |
7 May 2008 | A hardcopy of the suggested solutions to the exercises will be available in the secretaries office of the Lehrstuhl Informatik 2 (probably tomorrow). |
4 May 2008 | The second part of the script and the second exercise sheet are online. |
23 April 2008 | About the homework: I failed to mention that it is quite all right to work on the homework (and hand it in, of course) in groups of up to maximally 3 people. Handing in alone is also ok, though. |
21 April 2008 | Mistake on the 1st exercise sheet: Points for homework: 1.5: 6. 1.6: 10. 1.7: 6 |
20 April 2008 | First part of script and first exercise sheet are online. |
31 Mar 2008 | A schedule is available now. |
18 Feb 2008 | Here we are! |
Schedule
...where you can find the material of the course, as it is released.
Additional Reading Material
In particular with respect to the ioco theory, the following reference might prove useful.
- Jan Tretmans. Testing Techniques. University of Twente, Radboud University Nijmegen, 2002/2004. Course notes of J. Tretmans, who developed the ioco theory. Thanks for sharing.
- Jan Tretmans. Model Based Testing with Labelled Transition Systems
In Hierons, R.M. and Bowen, J.P. and Harman, M. Formal Methods and Testing, LNCS 4949, Springer-Verlag, 2008. A tutorial-style introduction into ioco. Only freely accessible with an RWTH IP-Number.
Contents
Testing is one of the most natural approaches to find out about the
behavior of systems, be it Java classes, UNIX processes, or protocol
components. It is the primary tool to find bugs in implemented
systems, and it is used by everybody who is concerned with software
development.
However, manual, ad-hoc testing is time-consuming, error-prone, and
most of all, boring. In industrial settings, test-automation goes only
as far as automatic test-execution (if that), however, test-cases are
written mostly manually. Especially for reactive systems, which show
nondeterministic behavior due to concurrent execution, obtaining
test-suits with a satisfying coverage is a time consuming and thus
expensive task. Moreover, it has to be repeated and repeated again as
the system-under-test develops and mutates. Automatic test-case
generation is thus most desirable.
The primary target of this lecture is to introduce into the
specification-based approach of testing. In this approach, a system to
be tested is described as a formal model, and this model is used to
derive test-cases automatically. In order to come to this point, the
necessary theoretical groundwork is laid.
The approach is a formal one, rooted in automata theory.
The following issues are addressed:
behavior of systems, be it Java classes, UNIX processes, or protocol
components. It is the primary tool to find bugs in implemented
systems, and it is used by everybody who is concerned with software
development.
However, manual, ad-hoc testing is time-consuming, error-prone, and
most of all, boring. In industrial settings, test-automation goes only
as far as automatic test-execution (if that), however, test-cases are
written mostly manually. Especially for reactive systems, which show
nondeterministic behavior due to concurrent execution, obtaining
test-suits with a satisfying coverage is a time consuming and thus
expensive task. Moreover, it has to be repeated and repeated again as
the system-under-test develops and mutates. Automatic test-case
generation is thus most desirable.
The primary target of this lecture is to introduce into the
specification-based approach of testing. In this approach, a system to
be tested is described as a formal model, and this model is used to
derive test-cases automatically. In order to come to this point, the
necessary theoretical groundwork is laid.
The approach is a formal one, rooted in automata theory.
The following issues are addressed:
- Groundwork: Automata, Labelled Transitions systems, specification of processes.
- How to identify and distinguish processes by observation?
- What is conformance in our framework?
- how to derive test cases from a transition system?
- How far can we get with the derived test-cases?
- how to incorporated the quantitative notion of time into test cases?
A more accurate overview over the structure of the lecture will be available at the end of the semester. :-)
Material
There will be a script, provided in parts as PDF on this web page. This will be a similar, but extended version of the script from last year.
There will be no slides. The major part of the lecture is developed on the blackboard.
Extra Material
Extra material will be provided as the course progresses. Below are two references from last year. Brush up your knowledge on Automata Theory (especially everything related to regular languages). It will come in handy.
- A method to eliminate tau-transitions (= epsilon transitions) from LTS (= finite automata) Note that finite LTS are basically finite automata where every state can be seen as accepting state. The trace set is thus the language of the LTS. The method comes from "Lawson: Finite Automata. Chapman & Hall, 2004". Note that the pdf file is only accessible from within the rwth-aachen.de domain.
- The powerset construction mentioned in the exercise class of May 22 is described in "J.E. Hopcroft, R. Motwani, J.D. Ullmann: Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001". Also minimization of deterministic finite automata is explained, which also applicable to minimize LTS.
Errata
Mistakes in the script go here.
Language
The lecture will be given in english.
Literature
In General
Manfred Broy, Bengt Jonsson, Joost-Pieter Katoen, Martin Leucker, and
Alexander Pretschner, editors, Model-Based Testing of Reactive Systems
(Advanced Lectures), Volume 3472 of Lecture Notes in Computer
Science. Springer-Verlag, 2005.
Alexander Pretschner, editors, Model-Based Testing of Reactive Systems
(Advanced Lectures), Volume 3472 of Lecture Notes in Computer
Science. Springer-Verlag, 2005.
First Part
Chapter 5 of the Broy... book.
Second Part
coming soon
Third part
Prerequisites
Automata Theory (e.g. ATFS)
