Funktionskorrektheit

Funktionskorrektheit ist die Eigenschaft eines Programms oder einer Funktion, die sicherstellt, dass das erzielte Ergebnis den Anforderungen der Spezifikation entspricht, soweit das Programm zulässige Eingaben verarbeitet und die Spezifikation eine Terminierung verlangt.

Man unterscheidet zwischen partieller und totaler Korrektheit. Partielle Korrektheit bedeutet, dass das Programm bei jeder zulässigen Eingabe eine korrekte Ausgabe liefert, vorausgesetzt es terminiert; totale Korrektheit fordert sowohl Korrektheit der Ausgabe als auch Gewährleistung der Terminierung für alle zulässigen Eingaben.

Zur Beschreibung der erwarteten Beziehung zwischen Eingaben und Ausgaben dienen Spezifikationen in Form von Vorbedingungen (P) und Nachbedingungen (Q). In der Praxis werden oft Invarianten verwendet, um Schleifen zu kontrollieren. Eine Spezifikation gibt also an, welche Eigenschaften vor der Ausführung gelten und welche nach der Ausführung erfüllt sein müssen.

Formale Beweise und formale Verifikationsmethoden versuchen, Funktionskorrektheit rigoros zu belegen. Typische Ansätze verwenden Hoare-Triple {P} C {Q}, wobei C ein Programmabschnitt ist, und P/Q die Vor-/Nachbedingungen festlegen. Weitere Methoden umfassen Model Checking, abstrakte Interpretation und Beweissysteme, die Schleifeninvarianten und Terminierungsbeweise formulieren.

Im praktischen Softwarebau dient Funktionskorrektheit als Grundlage für Verifikation und Tests. Tests prüfen oft Teilaspekte, während formale Beweise vollständige Korrektheit gewährleisten können. Die Anwendung hängt von Anforderungen, Komplexität und Sicherheitsanforderungen ab.