1

Empirische Softwaretechnik

Prof. Dr. Walter F. TichyDr. Frank Padberg

Sommersemester 2007

2

Gestaltung von Experimenten

oder

“Was man alles falsch machen kann”

3

Ein Beispiel für ein missglücktes Experiment:

“Formal Methods Application:An Empirical Tale of Software

Development”

Ann E. Sobel, Michael R. Clarkson,IEEE Trans. Software Engineering, März 2002

Zusätzlich: A.E.K Sobel, “Empirical Results of a Software Engineering Curriculum Incorporating Formal Methods”, ACM Inroads, Vol.32, no. 1, März 2000.

Comments on “Formal Methods Application…..”, Berry, Tichy and Response to Comments, Sobel, Clarkson, IEEE Trans. SE, June 2003

4

Zusammenfassung des Experiments

Forschungsfrage: Nützen formale Methoden?

Offensichtlich eine wichtige Frage.

Zwei Gruppen von zwei-Personen-Teams von Studenten implementierten Programme zu einem Fahrstuhlsimulations-Problem.

Eine Gruppe ohne, die andere mit formaler Spezifikation (Logik erster Ordnung).

Ergebnis: Die Lösungen der Gruppe mit formalen Methoden waren weit korrekter als die informellen Lösungen.

5

Vorbereitung Die Studenten waren im Grundstudium.

Die formale Gruppe wurde speziell in formalen Methoden ausgebildet; die andere nicht.

die Studenten konnten ihre Gruppen frei wählen.

Bis auf die formalen Methoden wurden beide Gruppen gleich ausgebildet (gleiche Dozenten, gleiche Themen, gleiche Reihenfolge, gleiche Beispiele, gleiche Aufgaben, gleiche Klausuren)

Aufgrund eines standardisierten Tests (ACT) unterschieden sich die Studenten zwischen den Gruppen zu Beginn um weniger als 1%.

6

Lehrpläne

Formale Gruppe:1.Einführung in formale

Programmherleitung

2.Semantik von Datenstrukturen

3.Objektorientierter Entwurf

4.formale Analyse nebenläufiger Programme

5.Softwaretechnik

6.Software-Praktikum

Informelle Gruppe1.(nichts)

2.Datenstrukturen

3.Objektorientierter Entwurf

4.(nichts)

5.Softwaretechnik

6.Software-Praktikum

Die Experimentaufgabe wurde im

OO-Entwurfskursbearbeitet

7

Aufgabe

You are to create a program that allows a user to issue a set of elevator requests, floor and direction. These are entered through menus and dialogs and are displayed in the “request” view. A request contains the floor at which the request is made and also the floor to which the user wants to go. In another view, the elevator and floors are graphically displayed. When the user presses the “GO” button in this graphic view, the elevator proceeds to process the requests that have been entered via the other view. The application shows the elevator going from one floor to another processing these requests. The current request, current floor, and status of elevator (stopped, moving up, moving down) should be displayed in text at the bottom of this graphic display. While the elevator is processing these requests, the user may enter other requests in the other view. The elevator scheduling algorithm should examine all current requests to determine the next floor and direction. When a new request is added, the algorithm should recalculate the next floor and direction. (use C++, Microsoft MFC)

8

Auswertung (1)

Die Programme wurden bewertet nach Codezeilen (insgesamt, Eingabeverarbeitung, Ablaufplanung), Komplexität (bedingte Anweisungen, Fallunterscheidungs-Anweisungen, maximale Schachtelungstiefe)

Kein statistisch signifikanter Unterschied auf dem Niveau 0,1 wurde entdeckt.

9

Auswertung (2)

Funktionale Korrektheit wurde mit 6 Testfällen überprüft.

Alle 6 der 6 formalen Implementierungen, also 100%, absolvierten alle 6 Testfälle erfolgreich.

Von den 11 informellen Lösungen waren nur 5 korrekt, also 45%. Drei versagten an allen Testfällen, drei an mindestens einem.

„These results support the hypothesis that the use of formal analysis led to better solutions...“

„...the formal methods group had increased complex problem solving skills.“

10

Welche Probleme können Sie in dem Experiment identifizieren?

11

Schlimmstes Problem: keine zufällige Zuweisung zu

Gruppen.1. Statistische Tests erfordern zufällige Zuweisung.

Andernfalls ein Quasi-Experiment.

2. Die Annahme, dass aufgrund von Vortests und gleichmäßiger Ausbildung äquivalente Gruppen entstehen, ist falsch. Die Gruppen könnten sich aufgrund anderer Variablen unterscheiden, z.B. Motivation.

3. Nicht äquivalente Gruppen gestatten es nicht, den Effekt der experimentellen Behandlung zu isolieren, da es rivalisierende Hypothesen gibt.

12

Beispiel für alternative, rivalisierende Hypothesen

Unterschiedliche MotivationDie Studenten meldeten sich freiwillig für einen schwierigeren Lehrplan (zwei extra Kurse, ein schwierigerer und längerer Datenstrukturkurs). Der Datenstrukturkurs musste sogar außerhalb der Vorlesungszeit gehalten werden, um den Stoff zu schaffen. Im Inroads Papier steht:

„The [experimental] group remained highly motivated and committed to the educational experience. The students formed a fraternal bond...group identity...scheduled a reunion…nuptials of two members“

Außerdem gab es vier Studenten der formalen Gruppe, die später freiwillig eine komplett formale Herleitung des Programms leisteten.

13

Alternative Hypothesen (2)

Unterschiedliche AusbildungDie formale Gruppe beschäftigte sich wesentlich intensiver mit dem Stoff. Die informelle Gruppe verbrachte deutlich weniger Zeit mit Datenstrukturen und dem Verstehen von Algorithmen--kein Wunder, dass sie schlechter abschnitt.Alle Studenten hätten eigentlich die formalen Methoden studieren sollen, oder die informelle Gruppe hätte mit alternativem Material (Algorithmen, Entwurfsmuster, systematisches Testen, etc.) arbeiten sollen.

14

Alternative Hypothesen (3)

Unterschiedlicher LernstilIm Inroads-Artikel steht, dass die formale Gruppe einen Fragebogen ausfüllte, der sie als kollaborative und wettbewerbsorientierte Studenten auswies. Die Kontrollgruppe nahm nicht teil.

Daher kann es sein, dass die formale Gruppe besser lernte oder sich mehr anstrengte.

15

Alternative Hypothesen (4)

Unterschiedliche analytische Fähigkeiten:Bei einer Untermenge von Fragen aus dem analytischen Teil des GRE nach dem Kurs beantwortete die formale Gruppe 36% mehr Fragen korrekt als die Kontrollgruppe.Das kommt wohl nicht nur von formalen Methoden, sondern möglicherweise einfach von besseren Studenten.

16

Hawthorne- undNeuigkeits-Effekte

Der Hawthorne-Effekt besagt, dass Teilnehmer sich anders verhalten, wenn sie wissen, dass sie in einem Experiment sind. Sie sind bereit, Dinge zu machen, die sie sonst ungern oder gar nicht machen würden, oder sie arbeiten sorgfältiger.

Der Neuigkeitseffekt besagt, dass Teilnehmer sich anders verhalten, wenn sie an etwas Neuem oder Ungewöhnlichem teilhaben. Nachdem der Neuigkeitswert verbraucht ist, verschwinden plötzlich auch die Effekte, nach denen man sucht.

17

Erwartungen des Experimentators

Die Erwartungen des Experimentators kann die Teilnehmer bewusst oder unbewusst beeinflussen. Studenten wollen dem Dozenten gefallen oder gute Noten erhalten, und benehmen sich deshalb so, wie der Dozent es wünscht.

Es ist schwierig, die Erwartungen des Experimentators geheim zu halten; meist erraten sie die Teilnehmer, auch wenn man sie nicht verrät.

18

Erwartungen des Experimentators

Es ist nicht zu vermeiden, und völlig legitim, dass der Experimentator Erwartungen hat. Man muss aber versuchen, die Auswirkungen zu begrenzen.

Lösung:

• zufällige Zuweisung zum Aufgabentyp in letzter Minute,

• Automatisierung des Experimentablaufs (anonyme Zuweisung der Aufgaben),

• Unvoreingenommener Dritter für die Durchführung

• Verschleierung der echten Hypothese mit anderen (Z.B. „das ist eine ganz normale Klausur“).

• Fragebogen am Schluss, der fragt, was das Experiment wohl bezweckte, was der Experimentator erwartete, wie andere im Experiment reagieren würden.

19

Wie wirkten sich diese Effekte im Sobel-Experiment aus?

„The students involved [in the experimental group] formed a fraternal bond among themselves and their group identity extended well beyond the classroom. We have already scheduled a reunion and all members will be attending the upcoming nuptials of two members“

Da es zwei Lehrpläne gab, ist zum einen der Neuigkeitseffekt gegeben und der Zweck der Übung auch offensichtlich. Dazu kommt der Enthusiasmus der Dozenten zu formalen Methoden.

20

Kontrollgruppe Die Kontrollgruppe soll Vergleiche ermöglichen.

Aber es ist unklar, welche Techniken die Teilnehmer in der Kontrollgruppe durchführten. Es gibt keine Unterlagen außer dem Programmcode; auch keine UML-Diagramme. Da es eine Hausaufgabe war, ist anzunehmen, dass sie die Aufgabe mit dem Minimalaufwand anpackten. (d.h.: wenig/kein Entwurf, gleich programmieren)

Alle formalen Teams lieferten Spezifikationen und die Hälfte auch UML-Diagramme ab.

21

Kontrollgruppe (2) Hypothese 1: die informelle Gruppe codierte sofort,

ohne nennnenswerten Entwurf.

Hypothese 2: die informelle Gruppe entwickelte keine Spezifikation, informelle Spezifikation, formale Spezifikation, oder eine Mixtur.

Wir wissen nicht, was in der Kontrollgruppe vorging, also ist sie als Vergleichsbasis nicht brauchbar.

Lösung: führe Test im Labor durch; überwache; protokolliere automatisch die Vorgänge am Rechner

22

Hypothesentest

Eine klare Hypothese ist nicht formuliert worden.

• Hypothese A: Formale Methoden verbessern das Problemlösungsverhalten von Studenten

• Hypothese B: Anwendung formaler Methoden führt zu „besseren“ Programmen

Unterschiedlicher Experimentaufbau notwendig

Funktionalitätstests eher geeignet für Hypothese B.

23

Hypothesentest (2)

Die Programme waren im Schnitt 130 Zeilen lang.

Glauben Sie, dass zur Korrktheitsüberprüfung sechs Testsfälle ausreichen?

Statt dessen sollten viele hunderte oder noch mehr von Testfällen zufällig im Eingaberaum ausgewählt und überprüft worden sein (evtl. mit Hilfe des formal hergeleiteten Programms).

Möglicherweise wären dann auch die „korrekten“ Programme als fehlerhaft erkannt worden…

24

Erkenntnisse Der Aufbau eines Experiments ist wichtig.

Bei falschem Aufbau kann man aufgrund unkontrollierter Variablen keine gültigen Aussagen treffen.

Überlege den Aufbau vor dem Experiment!

(Aus fehlerhaften Experimenten kann man etwas über das Experimentieren lernen.)

Mehr über experimentelle Methoden in Christensen, „Experimental Methodology“, Allyn and Bacon, 1994.

25

Eine Fallstudie zu formalen Methoden:„Investigating the Influence of Formal

Methods“ S.Pfleeger, L.Hatton, IEEE Computer, 30(2), Feb. 1997, 33-

43

Fallstudie: Genaue Untersuchung eines Vorgangs, Organisation oder Individuum

Fallstudie kann ein Gegenbeispiel für akzeptierte Prinzipien liefern; bietet Möglichkeiten, neue Hypothesen zu formulieren

Kausaler Zusammenhang nicht sicher feststellbar.

Generalisierung i.d.R. nicht möglich.

26

Studienobjekt: Flugsicherungs- Informationssystem CDIS

Entwickelt für Londons Flugsicherung

Entwickler: Praxis

ca. 200,000 Zeilen Code

benutzt wurden zur Spezifikation die Vienna Definition Method (VDM), Zustandsautomaten (FSM), Kombination von VDM und Milners Calculus of Communicating Sequential Processes (CCS), und Pseudocode (informell)

27

Nutzung formaler Methoden Spezifikation: Entity-Relationship Modelle,

strukturierte Analyse, VDM, FSM, CCS

Entwurf:

• verfeinerte Spezifikation des Anwendungscodes mittels VDM (zehn Entwickler)

• Nebenläufigkeit wird mit Zustandsautomaten spezifiziert (ein Entwickler)

• Software für lokales Netz wird mit VMD+CCS spezifiziert (zwei Entwickler)

• Benutzerschnittstelle wird mit Pseudocode beschrieben (vier Entwickler)

28

Studie

Auszuführender Code wurde von Hand aus den Spezifikationen erzeugt (keine formale Herleitung)

Entwicklung: 1990 -1992; ca. 3000 Defektmeldungen

Nach Inbetriebnahme 1992 wurden weitere 147 Defekte protokolliert (Zeitraum von etwa 2 Jahren).

Für jeden Defekte wurde untersucht, wieviele Module bei der Korrektur geändert wurden.

Diese Daten wurden für die verschiedenen Spezifikationsmethoden verglichen.

29

Defekte während EntwicklungAnzahl geänderter

Module

„ ..., the changes to informaly designed delivered modules are not significantly higher or lower than changes to formally designed modules (21.0 vs. 19.6)“

30

Änderungsintensive Module(mit mehr als 5 bzw. 10 Änderungen

„Informally designed modules required fewer changes than those designed using formal methods, but as with Table 1, the overall difference between informal and formal methods is insignificant.“

(Anmerkung: Diskrepanz zw. 1. Zeile von Tabelle 2 mit vorletzterZeile von Tabelle 1. Druckfehler?)

31

Zeitliche Betrachtung der Änderungen in geliefertem Code

während der Entwicklung.„[the spikes] may have nothing to dowith the designmethod, but may reflect the organization of the development team.The FSM andVDM/CCS code were developed byfewer people (oneand two) than theother ... The largerspikes may reflectthe more complexcommunicationproblems ...“(Weitere Analyse der Spitzen war nicht möglich.)

32

Defekte während ModultestVon allen Defekten vor Lieferung wurden 340 während Codedurchsichten, 725 während Modultest und 2200 während Systemtest gefunden.

„The faults discovered during unit testing, ..., occurred in informally designedmodules more often than in formally designed ones. ...This suggests that formal design may have helped minimize errors or aidedfault discovery early in development.“

33

Defekte nach Inbetriebnahme

„..., far fewer changes were required after delivery to formally designed parts, making the formal code more reliable than the informal code.

34

Zuverlässigkeit im Vergleich

„CDIS code exhibits a remarkably low 0.81 failure per KLOC.The table also shows the general trend of higher reliability insystems that used formal methods.“

Anmerkung: könnte ein Effekt der Zuverlässigkeitskultur beiPraxis sein.

35

Konklusion„On the one hand, we found no compelling quantitative evidence that formal design techniques alone produced code of higher quality than informal design techniques. The predelivery fault profile showed no difference between formally and informally designed code. On the other hand, the unit testing data showed fewer errors in formally designed code, and postdelivery failures were significantly less for formally designed code. Thus we can conclude that formal design, combined with other techniques, yielded highly reliable code....Moreover, formal methods may be more effective in acting as a catalyst for other techniques, especially testing, by virtue of producing testable components or by providing a structure on which to base comprehensive system testing.“