Wie erstelle ich geschäftskritische Software?

Ich lerne selbst formale Methoden. Ich habe gehört, dass formale Methoden verwendet werden (und in der Regel nur verwendet werden), um unternehmenskritische Software zu erstellen (z. B. Nuklearreaktor-Controller, Flugzeug-Flug-Controller, Raumsonden-Controller). Deshalb bin ich daran interessiert, es zu lernen: p

Nach dem Erlernen der formalen Methoden (insbesondere LTL, CTL und ihre Geschwister) kann ich sie jedoch nur verwenden, um die Richtigkeit der Spezifikation (Sicherheit, Lebendigkeit, Fairness usw.) zu überprüfen.

Aber wie kann man dann überprüfen, ob die Software (nicht nur die Spezifikation) tatsächlich korrekt ist?

Haftungsausschluss: Ich bin zu 90% ein Idiot, wenn es um theoretische Informatik geht. Also sei bitte barmherzig, wenn du antwortest.

Die Frage ist ziemlich weit gefasst. Um es in einem angemessenen Raum zu beantworten, werde ich viele Vereinfachungen vornehmen.

Lassen Sie uns die Terminologie vereinbaren. Ein Programm ist korrekt, wenn es seine Spezifikation impliziert. Diese vage Aussage wird in vielerlei Hinsicht präzisiert, indem festgehalten wird, was genau ein Programm und was genau eine Spezifikation ist. Beispielsweise ist das Programm bei der Modellprüfung eine Kripke-Struktur und die Spezifikation ist häufig eine LTL- Formel. Oder das Programm könnte eine Liste von PowerPC-Anweisungen sein, und die Spezifikation könnte ein Satz von Hoare-Floyd-Behauptungen sein, die beispielsweise in Logik erster Ordnung geschrieben sind. Es gibt sehr viele mögliche Variationen. Es ist verlockend zu folgern, dass wir in einem Fall (Kripke-Struktur) kein tatsächliches Programm verifizieren, während wir dies im zweiten Fall (Liste der PowerPC-Anweisungen) tun. Es ist jedoch wichtig zu erkennen, dass wir uns in beiden Fällen wirklich mit mathematischen Modellen befassen, und dies ist vollkommen in Ordnung. (Die Situation ist der Physik sehr ähnlich, in der zum Beispiel die klassische Mechanik ein mathematisches Modell der Realität ist.)

Die meisten Formalisierungen unterscheiden zwischen der Syntax und der Semantik eines Programms. das heißt, wie es dargestellt wird und was es bedeutet. Die Semantik eines Programms ist das, was aus Sicht der Programmüberprüfung zählt. Aber es ist natürlich wichtig, eine klare Art der Zuordnung von Bedeutungen zu (syntaktischen Darstellungen von) Programmen zu haben. Zwei beliebte Möglichkeiten sind die folgenden:

• (kleiner Schritt) Operative Semantik : Dies ähnelt der Definition einer Programmiersprache, indem ein Interpreter dafür geschrieben wird. Dazu müssen Sie den Status angeben, der von jeder Anweisung in der Sprache beeinflusst wird. (Sie fragen sich vielleicht, in welcher Sprache Sie den Dolmetscher schreiben, aber ich werde so tun, als ob Sie das nicht tun.)
• Axiomatische Semantik : Hier wird jeder Anweisungstyp mit einem Axiomschema geliefert. Wenn also eine bestimmte Aussage dieses Typs verwendet wird, bedeutet dies ungefähr, dass bestimmte Axiome verwendet werden können. Zum Beispiel kommt die Zuweisung mit dem Schema { P [ x / e ] ${\bf x}:={\bf e}$ ; die besondere Zuordnung x : = x + 1 kommt mit dem Axiom { x + 1 = 1 $\{P[{\bf x}/{\bf e}]\}\,{\bf x}:={\bf e}\,\{P\}$$x:=x+1$ wenn wir das Schema mit P = ( x = 1 ) instanziieren.$\{x+1=1\}\,x:=x+1\,\{x=1\}$$P=(x=1)$

(Es gibt andere. Ich fühle mich besonders schlecht, wenn ich die Denotationssemantik weglasse, aber diese Antwort ist bereits lang.) Maschinencode plus operationale Semantik kommen dem sehr nahe, was die meisten Leute ein "echtes Programm" nennen würden. Hier ist eine wegweisende Abhandlung, die zufällig die operative Semantik für eine Teilmenge des DEC Alpha-Maschinencodes verwendet:

• Lee Necula, Proof-Carrying Code , 1996

Warum würden Sie jemals eine höhere Semantik verwenden, wie die axiomatischen? Wenn Sie nicht möchten, dass Ihr Korrektheitsnachweis von der Hardware abhängt, auf der Sie ausgeführt werden. Der Ansatz besteht dann darin, die Korrektheit eines Algorithmus in Bezug auf eine geeignete Semantik auf hoher Ebene zu beweisen und dann zu beweisen, dass die Semantik in Bezug auf eine Semantik auf niedrigerer Ebene klingt, die näher an tatsächlichen Maschinen liegt.

Zusammenfassend kann ich drei Gründe nennen, die zu Ihrer Frage geführt haben:

1. Sie haben nur Semantik auf hoher Ebene gesehen, die nicht so aussieht, wie Sie es gewohnt sind, ein Programm aufzurufen, und Sie fragen sich, ob es solche auf niedriger Ebene gibt. Die Antwort ist ja.
2. Sie fragen sich, wie Sie beweisen, dass ein Modell der Realität entspricht. Wie in der Physik nicht. Man erfindet einfach bessere Modelle und vergleicht sie mit der Realität.
3. Sie haben nicht die Unterscheidung zwischen Syntax und Semantik sowie verschiedene Möglichkeiten zur Zuordnung von Bedeutungen zu Programmen gesehen. In zwei vorherigen Fragen sind einige Bücher aufgelistet.

Diese Antwort versucht lediglich drei verschiedene Arten zu identifizieren, auf die ich die Frage verstanden habe. Wenn Sie in einen dieser Punkte eintauchen, ist viel Platz erforderlich.

Ein Ansatz, um die Lücke zwischen einem Programm und seiner Spezifikation zu schließen, ist die Verwendung einer Sprache mit einer formalen Semantik. Ein interessantes Beispiel wäre hier Esterel . Auf der Webseite von Gérard Berry finden Sie einige interessante Vorträge über seine Arbeit, die formale Methoden in die Realität umsetzt. http://www-sop.inria.fr/members/Gerard.Berry/

ps Warst du in einem Airbus? Sie sind mit formellen Methoden geflogen!

Die Wissenschaft des Erstellens zuverlässiger Software in der "realen Welt" befindet sich noch in der Entwicklung und grenzt in gewissem Maße an eine inhärente kulturelle oder anthropologische Untersuchung, da Computer und Software keine Fehler "verursachen" - Menschen tun dies! Diese Antwort konzentriert sich auf allgemeine Q / A-Ansätze, bei denen die formale Softwareverifizierung als ein Element betrachtet werden kann.

Eine bemerkenswerte Beobachtung ist, dass Software, die "gut genug" und dennoch "fehlerhaft" ist, häufig besser getestete Software mit geringerer Funktionalität auf dem Markt verkauft. Mit anderen Worten, der Markt legt nicht immer einen hohen Wert auf Softwarequalität, und die modernen Techniken des Software-Engineerings, die nicht immer die Qualität betonen, spiegeln dies in gewisser Weise wider. Darüber hinaus kann die Qualität das Endprodukt häufig erheblich verschlechtern. mit diesen einschränkungen sind hier einige der grundlagen:

• redundante / fehlertolerante Systeme. Dies ist ein weites Feld des Studiums. Fehlertoleranz und Redundanz können in die vielen Schichten eines Systems integriert werden. zB ein Router, ein Server, ein Festplattenlaufwerk usw.

• Testen . Alle Typen - Komponententests, Integrationstests, Benutzerakzeptanztests, Regressionstests usw.

• Heutzutage ist das automatisierte Testen über Testsuiten, die unbeaufsichtigt ausgeführt werden können, weiter entwickelt / wichtig. Testsuiten, die ausgeführt werden, sind häufig mit dem Build-Tool gekoppelt.

• Ein wichtiges Konzept beim Testen ist die Codeabdeckung . dh welcher Code wird durch den Test ausgeübt . Ein Test kann keinen Fehler in Code finden, der vom Test nicht "berührt" wird.

• Ein weiteres Schlüsselkonzept beim Testen ist das Testen des Trainingscodes, auf den nicht direkt zugegriffen werden kann.

• Tests sollten alle Ebenen der Software ausüben. Wenn die Software gut modularisiert ist, ist dies nicht schwierig. Übergeordnete Tests sollten tief in den Code eindringen. Tests, die große Mengen an Code mit kleinen Testaufbauten ausführen, erhöhen den "Testhebel" .

• Für das Testen ist es wichtig , den Code so einfach wie möglich zu gestalten. Das Testen sollte bei der Architekturgestaltung berücksichtigt werden. Häufig gibt es mehrere Möglichkeiten, dasselbe Feature zu implementieren. Einige davon haben jedoch sehr unterschiedliche Auswirkungen auf die Testabdeckung / -nutzung. Für jeden Zweig im Code ist es oft ein anderer Testfall. Zweige in Zweigen eskalieren zu einer exponentiellen Zunahme der Codepfade. Das Vermeiden stark verschachtelter / bedingter Logik verbessert daher die Testfähigkeit.

• Das Studium berühmter (massiver) Softwarefehler, für die es viele Beispiele und Fallstudien gibt, ist hilfreich, um die Geschichte zu verstehen und eine Denkweise zu entwickeln, die sich an Qualitätsaspekten orientiert.

• man kann sich mit dem Testen hinreißen lassen! Es gibt ein Problem mit zu wenig oder zu viel Testen. Es gibt einen "Sweet Spot". Die Software kann in keinem Extremfall erfolgreich erstellt werden.

• Nutze alle grundlegenden Werkzeuge auf die effektivste Art und Weise. Debugger, Code-Profiler, Test-Code-Coverage-Tools, Fehlerverfolgungssysteme usw.! verpflichten Sie sich nicht unbedingt zur Fehlerbehebung, sondern verfolgen Sie selbst die kleinsten Fehler in der Tracking-Software.

• Der sorgfältige Einsatz von SCM, Quellcodeverwaltung und Verzweigungstechniken ist wichtig, um Regressionen, das Isolieren und Fortschreiten von Fixes usw. zu vermeiden

• N-Version-Programmierung : eine Praxis, die häufig für die Entwicklung unternehmenskritischer Software verwendet wird. Die Prämisse dieser Praxis ist, dass N unabhängig entwickelte Programme wahrscheinlich nicht denselben gemeinsamen Fehler aufweisen. Dies wurde in einigen Veröffentlichungen kritisiert. NVP ist jedoch keine theoretische Praxis.

Ich glaube, der Physiker Feynman hat in seinem Buch "Was kümmert es dich, was andere Leute denken?" Eine Beschreibung der Methode, mit der die NASA die Zuverlässigkeit der Space-Shuttle-Systeme garantiert. - Er sagte, sie hätten zwei Teams, sagen Team A und Team B. Team A hat die Software erstellt. Team B verfolgte eine kontroverse Herangehensweise an Team A und versuchte, die Software zu brechen.

Es hilft, wenn Team B über einen guten softwaretechnischen Hintergrund verfügt, dh selbst Code-Harness, programmatische Tests usw. schreiben kann. In diesem Fall verfügte Team B über nahezu die gleichen Ressourcen wie Team A. Dieser Ansatz ist jedoch teuer, da sich die Kosten für die Erstellung der Software nahezu verdoppeln können. Typischerweise gibt es ein kleineres QA-Team als das Entwicklungsteam.

Ein alter Ansatz (der in einigen Anwendungen immer noch verwendet wird) ist die Programmierung in der N-Version

Aus Wikipedia:

Die N-Version-Programmierung ( NVP ), auch als Multiversion-Programmierung bezeichnet , ist ein Verfahren oder ein Prozess in der Softwareentwicklung, bei dem mehrere funktional äquivalente Programme unabhängig voneinander aus denselben anfänglichen Spezifikationen generiert werden. Das Konzept der N-Version-Programmierung wurde 1977 von Liming Chen und Algirdas Avizienis mit der zentralen Vermutung eingeführt, dass die "Unabhängigkeit des Programmieraufwands die Wahrscheinlichkeit des Auftretens identischer Softwarefehler in zwei oder mehr Versionen des Programms erheblich verringern wird" von NVP besteht darin, die Zuverlässigkeit des Softwarebetriebs zu verbessern, indem Fehlertoleranz oder Redundanz eingebaut werden.
....

Siehe zum Beispiel: " Herausforderungen beim Bau von Flugzeugen - Tolerantes Flugsteuerungssystem für zivile Flugzeuge "

Fajrian, diese Frage, die Sie gestellt haben, befasst sich mit zwei der größten Probleme in der Forschung des Software-Ingenieurs: der Konformität zwischen der Spezifikation und dem Modell sowie zwischen dem Modell und dem Code. Modellieren Sie hier eine Darstellung dessen, was das System macht oder wie es gemacht wird. Es gibt viele Ebenen, um ein System zu modellieren.

Es gibt also einige Leute, die versuchen, die beste Antwort auf Ihre Frage zu finden. Weil es sehr schwierig ist, die Richtigkeit einer Software anhand eines Modells zu überprüfen, beispielsweise mit formalen Methoden. Ich weiß, dass JML ein Weg ist, es zu tun, aber ich kenne die Grenzen seiner Verwendung nicht.

Um zusammenzufassen, wie schwierig es ist, die Korrektheit von Code zu überprüfen, versuchen die Leute, formale Methoden und Tests zu mischen und Tests beispielsweise automatisch anhand von Spezifikationen zu erstellen. Ein Beispiel für Echtzeitsysteme sind die TIOSTS , die auf zeitgesteuerten Ein- / Ausgabeereignissen basieren.

Nur testen ist kein formaler Methodenansatz, da dies die Zuverlässigkeit verbessert, aber nicht die Korrektheit überprüft.

Vor zwei oder drei Jahren beschäftigte ich mich mit formalen Methoden für Software. Dies war eine Suche, die von Neugier getrieben war und von dem Gefühl, dass ich Programmiertools und -methoden mit längeren Zeitspannen erlernen musste. Obwohl ich wunschgemäß von einer Silberkugel geträumt habe , dachte ich wirklich, dass es keine Antwort auf die Frage gibt: "Wie kann ich ein korrektes Programm schreiben?".

Nachdem ich einige Tools ausprobiert habe (Z, B, VHDL und Estelle), verwende ich TLA + . Dies ist eine Variante der zeitlichen Logik mit Softwaretools zur Modellprüfung und für mechanische Beweise. Ich glaube, ich habe diesen Ansatz gewählt, weil L. Lamport dahintersteckte, die Syntax einfach war, es gab viele Beispiele, es gab eine Community, die sich darum kümmerte, und die Sprache und die Tools waren ziemlich gut dokumentiert.

In Bezug auf meine erste Frage denke ich, dass es keine vollständige Antwort gibt. Es lohnt sich jedoch zu lernen, dass es sich auszahlt, einige Teile eines Systems formal zu spezifizieren. Es ist auch ziemlich nützlich, einige komplexe zurückzuentwickeln. Das heißt, es ist effektiv, einen Entwurf für die schwierigen und kritischen Teile zu erstellen. Ich glaube jedoch nicht, dass es eine effektive Methode gibt, um die Spezifikation automatisch in eine Programmiersprache oder ein Framework zu übersetzen (es sei denn, Sie beschränken das Projekt auf eine bestimmte Umgebung). Ich denke auch nicht, dass eine formale Spezifikation Sie daran hindern sollte, die Software zu testen.

Kurz gesagt, ich denke, dass die folgende Metapher (von Lamport) wirklich mächtig ist: "Erwarten Sie, dass ein Haus automatisch aus einer Blaupause gebaut wird? Kaufen Sie ein Haus, das noch nicht gebaut wurde und keine Blaupause hat?" .

Während dieser Suche habe ich die folgenden Ressourcen nützlich gefunden:

• Methoden zur Softwarespezifikation . Dieses Buch bietet einen umfassenden Überblick über die vorhandenen Methoden und Werkzeuge. Dort finden Sie grundlegende Erklärungen und Beispiele zu Z, SDL, TLA +, Petri Nets, Coq usw.
• Wenn Sie der Meinung sind, dass TLA + Ihren Anforderungen entspricht, empfehle ich das Buch Specifying Systems . Sie können das Buch kostenlos herunterladen und es enthält Beispiele zum Spielen :).
• Kürzlich las ich einige verwandte Artikel, die den Stand der formalen Methoden aus zwei verschiedenen Perspektiven beleuchteten: The Case for Formal Methods und Formally Verified Mathematics .

Viel Glück!

Die bisherigen Antworten deckten bereits den größten Teil dessen ab, was über die Grundlagen der Beziehung zwischen Spezifikation und Code gesagt werden sollte. Ich möchte nur einen praktischeren Punkt hinzufügen, der sich der Frage im Header dieses Threads nähert:

Wie erstelle ich geschäftskritische Software?

Es gibt Tools, die Ihren Code automatisch auf Fehler analysieren (Verstöße gegen die Spezifikation oder "typische Fehler"). Meines Wissens bauen diese Methoden größtenteils auf statischen Analysen auf und stehen nicht unmittelbar mit den Theorien in Zusammenhang, die Sie erwähnt haben (LTL / CTL / ...), aber sie finden Fehler in echtem Code und es ist aus praktischer Sicht bereits machbar Ansicht, solche Werkzeuge in industriellen Projekten zu verwenden. Ich persönlich habe nicht viele von ihnen benutzt, aber es scheint, dass diese Werkzeuge von den Praktizierenden akzeptiert werden. Zum weiterlesen kann ich folgenden Blogartikel empfehlen:

http://www.altdevblogaday.com/2011/12/24/static-code-analysis/

Zertifizierungsalgorithmen können beim Erstellen unternehmenskritischer Software hilfreich sein.

Ein Zertifizierungsalgorithmus ist ein Algorithmus, der mit jeder Ausgabe ein Zertifikat oder ein Zeugnis (einfach zu überprüfender Beweis) erstellt, dass die jeweilige Ausgabe nicht durch einen Fehler beeinträchtigt wurde.

Lesen Sie mehr in dieser Umfrage. Zertifizierungsalgorithmen von McConnell, RM und Mehlhorn, K. und Naher, S. und Schweitzer, P.

Aber wie kann man dann überprüfen, ob die Software (nicht nur die Spezifikation) tatsächlich korrekt ist?

Unit-Test? Schreiben Sie einen Test für jede einzelne Anforderung in der Spezifikation und testen Sie dann jede einzelne Methode in Ihrer Implementierung, um festzustellen, ob ihre Ausgabe / Eingabe der Spezifikation entspricht. Dies kann automatisiert werden, sodass diese Tests fortlaufend ausgeführt werden, um sicherzustellen, dass keine Änderungen zuvor funktionierende Funktionen beeinträchtigen.

Theoretisch sollte Ihre Software korrekt sein, wenn Ihre Komponententests eine Codeabdeckung von 100% haben (dh jede einzelne Methode in Ihrem Code wird getestet), vorausgesetzt, die Tests selbst sind genau und realistisch.