Ist es möglich, die Sicherheit für beliebigen Code programmgesteuert zu bewerten?

Ich habe in letzter Zeit viel über sicheren Code nachgedacht. Gewindesicher. Speichersicher. Nicht-explodieren-in-deinem-Gesicht-mit-einem-Segfault-Safe. Aus Gründen der Klarheit in der Frage verwenden wir jedoch das Sicherheitsmodell von Rust als unsere Definition.

Die Gewährleistung der Sicherheit ist häufig ein Problem, wie groß das Netz ist, da es, wie Rusts Bedarf zeigt unsafe, einige sehr vernünftige Programmierideen wie die Parallelität gibt, die in Rust nicht ohne Verwendung des Schlüsselworts implementiert werden könnenunsafe . Auch wenn die Parallelität mit Sperren, Mutexen, Kanälen und Speicherisolation oder was auch immer Sie sicher machen können, müssen Sie außerhalb des Sicherheitsmodells von Rust arbeiten unsafeund dem Compiler dann manuell versichern, dass "Ja, ich weiß, was ich tue Das sieht unsicher aus, aber ich habe mathematisch bewiesen, dass es absolut sicher ist. "

In der Regel kommt es jedoch darauf an, Modelle dieser Dinge manuell zu erstellen und zu beweisen, dass sie mit Theoremprüfern sicher sind . Ist es sowohl aus Sicht der Informatik (ist es möglich) als auch aus Sicht der Praktikabilität (wird es das Leben des Universums kosten) vernünftig, sich ein Programm vorzustellen, das beliebigen Code in einer beliebigen Sprache verwendet und bewertet, ob es " Rost sicher "?

Vorsichtsmaßnahmen :

• Eine einfache Möglichkeit besteht darin, darauf hinzuweisen, dass das Programm möglicherweise nicht mehr funktioniert und das Problem mit dem Anhalten daher fehlschlägt. Nehmen wir an, jedes Programm, das dem Leser zugeführt wird, wird garantiert angehalten
• Während "beliebiger Code in einer beliebigen Sprache" das Ziel ist, ist mir natürlich bewusst, dass dies von der Vertrautheit des Programms mit der gewählten Sprache abhängt, die wir als gegeben annehmen

Worüber wir hier letztendlich sprechen, ist Kompilierungszeit gegen Laufzeit.

Wenn Sie darüber nachdenken, führen Kompilierungszeitfehler letztendlich dazu, dass der Compiler feststellen kann, welche Probleme Sie in Ihrem Programm haben, bevor es überhaupt ausgeführt wird. Es ist offensichtlich kein Compiler für "beliebige Sprachen", aber ich werde gleich darauf zurückkommen. Der Compiler listet jedoch in all seiner unendlichen Weisheit nicht jedes Problem auf, das vom Compiler bestimmt werden kann. Dies hängt teilweise davon ab, wie gut der Compiler geschrieben ist. Der Hauptgrund dafür ist jedoch, dass zur Laufzeit viele Dinge bestimmt werden .

Laufzeitfehler sind, wie Sie sicher wissen, jede Art von Fehler, der während der Ausführung des Programms selbst auftritt. Dies umfasst das Teilen durch Null, Nullzeigerausnahmen, Hardwareprobleme und viele andere Faktoren.

Aufgrund der Art der Laufzeitfehler können Sie diese Fehler beim Kompilieren nicht vorhersehen. Wenn Sie könnten, würden sie mit ziemlicher Sicherheit zur Kompilierungszeit überprüft. Wenn Sie garantieren können, dass eine Zahl zur Kompilierungszeit Null ist, können Sie bestimmte logische Schlussfolgerungen ziehen. Wenn Sie beispielsweise eine Zahl durch diese Zahl dividieren, wird ein Rechenfehler verursacht, der durch die Division durch Null verursacht wird.

Als solches führt der Feind der programmgesteuerten Gewährleistung des ordnungsgemäßen Funktionierens eines Programms auf sehr reale Weise Laufzeitprüfungen durch, anstatt Zeitprüfungen zu kompilieren. Ein Beispiel hierfür könnte eine dynamische Umwandlung in einen anderen Typ sein. Wenn dies zulässig ist, überschreiben Sie als Programmierer im Wesentlichen die Fähigkeit des Compilers, zu wissen, ob dies eine sichere Sache ist. Einige Programmiersprachen haben entschieden, dass dies akzeptabel ist, während andere Sie zumindest beim Kompilieren warnen.

Ein weiteres gutes Beispiel könnte sein, dass Nullen Teil der Sprache sein dürfen, da Nullzeigerausnahmen auftreten können, wenn Sie Nullen zulassen. Einige Sprachen haben dieses Problem vollständig beseitigt, indem sie verhindert haben, dass Variablen, die nicht explizit deklariert wurden, Nullwerte enthalten können, die deklariert werden sollen, ohne sofort einen Wert zugewiesen zu bekommen (z. B. Kotlin). Sie können einen Laufzeitfehler für eine Nullzeigerausnahme zwar nicht beseitigen, aber Sie können dies verhindern, indem Sie die Dynamik der Sprache entfernen. In Kotlin können Sie natürlich die Möglichkeit erzwingen , Nullwerte zu halten, aber es versteht sich von selbst, dass dies eine metaphorische "Käufer aufgepasst" ist, da Sie dies ausdrücklich als solche angeben müssen.

Könnten Sie konzeptionell einen Compiler haben, der Fehler in jeder Sprache überprüfen kann? Ja, aber es wäre wahrscheinlich ein klobiger und höchst instabiler Compiler, in dem Sie unbedingt die Sprache angeben müssten, die zuvor kompiliert werden soll. Es konnte auch nicht viel über Ihr Programm wissen, genauso wenig wie Compiler für bestimmte Sprachen bestimmte Dinge darüber wissen, wie zum Beispiel das von Ihnen erwähnte Problem des Anhaltens. Wie sich herausstellt, sind viele Informationen, die interessant sein könnten, um etwas über ein Programm zu erfahren, unmöglich zu finden. Dies wurde bewiesen, so dass es sich wahrscheinlich nicht so schnell ändern wird.

Zurück zu Ihrem Hauptpunkt. Methoden sind nicht automatisch threadsicher. Dafür gibt es einen praktischen Grund: Thread-sichere Methoden sind auch dann langsamer, wenn keine Threads verwendet werden. Rust entscheidet, dass sie Laufzeitprobleme beseitigen können, indem sie Methoden standardmäßig threadsicher machen, und das ist ihre Wahl. Es hat jedoch einen Preis.

Es mag möglich sein, die Richtigkeit eines Programms mathematisch zu beweisen, aber mit der Einschränkung, dass Sie buchstäblich keine Laufzeitfunktionen in der Sprache haben würden. Sie können diese Sprache lesen und wissen, was sie ohne Überraschungen tut. Die Sprache würde wahrscheinlich sehr mathematisch aussehen, und das ist dort wahrscheinlich kein Zufall. Der zweite Nachteil ist , dass Laufzeitfehler noch passieren, die nichts haben , kann sich mit dem Programm zu tun. Daher kann das Programm korrekt nachgewiesen werden, eine Reihe von Annahmen über den Computer unter der Annahme , es auf ausgeführt wird, genau und nicht ändern, was natürlich immer nicht sowieso und oft passieren.

Typensysteme sind automatisch überprüfbare Nachweise für einige Aspekte der Korrektheit. Beispielsweise kann das Typsystem von Rust beweisen, dass eine Referenz das referenzierte Objekt nicht überlebt oder dass ein referenziertes Objekt nicht von einem anderen Thread geändert wird.

Typsysteme sind jedoch recht eingeschränkt:

• Sie stoßen schnell auf Entscheidungsprobleme. Insbesondere sollte das Typsystem selbst entscheidbar sein, dennoch sind viele praktische Typsysteme versehentlich Turing Complete (einschließlich C ++ aufgrund von Vorlagen und Rust aufgrund von Merkmalen). Außerdem können bestimmte Eigenschaften des Programms, das sie überprüfen, im allgemeinen Fall unentscheidbar sein, vor allem, ob ein Programm anhält (oder abweicht).

• Darüber hinaus sollten Typsysteme schnell laufen, idealerweise in linearer Zeit. Nicht alle möglichen Nachweise sollten im Typensystem enthalten sein. Beispielsweise wird eine Analyse des gesamten Programms normalerweise vermieden, und Proofs werden auf einzelne Module oder Funktionen beschränkt.

Aufgrund dieser Einschränkungen neigen Typsysteme dazu, nur ziemlich schwache Eigenschaften zu überprüfen, die leicht zu beweisen sind, z. B. dass eine Funktion mit Werten des richtigen Typs aufgerufen wird. Doch selbst das schränkt die Ausdruckskraft erheblich ein. Daher ist es üblich, Problemumgehungen zu verwenden (wie interface{}in Go, dynamicin C #, Objectin Java, void*in C) oder sogar Sprachen zu verwenden, die statische Typisierung vollständig meiden.

Je stärker die Eigenschaften sind, die wir überprüfen, desto weniger ausdrucksstark wird die Sprache normalerweise. Wenn Sie Rust geschrieben haben, kennen Sie diese Momente des „Kampfes mit dem Compiler“, in denen der Compiler scheinbar korrekten Code ablehnt, weil er die Korrektheit nicht beweisen konnte. In einigen Fällen ist es nicht möglich , ein bestimmtes Programm in Rust auszudrücken, selbst wenn wir glauben, dass wir seine Richtigkeit beweisen können. Mit dem unsafeMechanismus in Rust oder C # können Sie sich den Grenzen des Typsystems entziehen. In einigen Fällen kann es eine andere Option sein, Überprüfungen auf die Laufzeit zu verschieben. Dies bedeutet jedoch, dass wir einige ungültige Programme nicht ablehnen können. Dies ist eine Frage der Definition. Ein Rust-Programm, das in Panik gerät, ist für das Typsystem sicher, aber nicht unbedingt aus der Sicht eines Programmierers oder Benutzers.

Sprachen werden zusammen mit ihrem Typensystem entworfen. Es ist selten, dass einer vorhandenen Sprache ein neues Typsystem auferlegt wird (siehe z. B. MyPy, Flow oder TypeScript). Die Sprache wird versuchen, das Schreiben von Code zu vereinfachen, der dem Typsystem entspricht, z. B. indem sie Typanmerkungen anbietet oder einfach zu beweisende Kontrollflussstrukturen einführt. Unterschiedliche Sprachen können zu unterschiedlichen Lösungen führen. finalZum Beispiel hat Java das Konzept von Variablen, die genau einmal zugewiesen werden, ähnlich wie bei Rusts Nichtvariablen mut:

final int x;
if (...) { ... }
else     { ... }
doSomethingWith(x);

Java verfügt über Typsystemregeln, mit denen bestimmt wird, ob alle Pfade die Variable zuweisen oder die Funktion beenden, bevor auf die Variable zugegriffen werden kann. Im Gegensatz dazu vereinfacht Rust diesen Beweis, indem es keine deklarierten, aber nicht entworfenen Variablen hat, sondern Sie können Werte aus Kontrollflussanweisungen zurückgeben:

let x = if ... { ... } else { ... };
do_something_with(x)

Dies scheint ein wirklich kleiner Punkt bei der Ermittlung der Zuordnung zu sein, aber ein klares Scoping ist für lebenslange Beweise äußerst wichtig.

Wenn wir ein System vom Typ Rust auf Java anwenden würden, hätten wir viel größere Probleme: Java-Objekte sind nicht mit Lebensdauern versehen, daher müssten wir sie als &'static SomeClassoder behandeln Arc<dyn SomeClass>. Das würde die daraus resultierenden Beweise schwächen. Java hat auch kein Konzept der Unveränderlichkeit auf Typebene, sodass wir nicht zwischen &und &mutTypen unterscheiden können. Wir müssten jedes Objekt als Zelle oder Mutex behandeln, obwohl dies möglicherweise stärkere Garantien voraussetzt, als Java tatsächlich bietet (das Ändern eines Java-Felds ist nur dann threadsicher, wenn es synchronisiert und flüchtig ist). Schließlich hat Rust kein Konzept für die Vererbung von Implementierungen im Java-Stil.

TL; DR: Typsysteme sind Theorembeweiser. Sie sind jedoch durch Entscheidbarkeitsprobleme und Leistungsprobleme begrenzt. Sie können nicht einfach ein Typsystem verwenden und es auf eine andere Sprache anwenden, da die Sprachsyntax des Ziels möglicherweise nicht die erforderlichen Informationen liefert und die Semantik möglicherweise nicht kompatibel ist.

Wie sicher ist sicher?

Ja, es ist fast möglich, einen solchen Verifizierer zu schreiben: Ihr Programm muss nur die Konstante UNSAFE zurückgeben. Sie haben 99% der Zeit Recht

Denn selbst wenn Sie ein sicheres Rust-Programm ausführen, kann während der Ausführung noch jemand den Stecker ziehen. Daher wird Ihr Programm möglicherweise angehalten, selbst wenn dies theoretisch nicht vorgesehen ist.

Und selbst wenn Ihr Server in einem Faradayschen Käfig in einem Bunker läuft, kann ein Nachbarprozess einen Rowhammer-Exploit ausführen und ein bisschen in einem Ihrer vermeintlich sicheren Rust-Programme umdrehen.

Ich versuche zu sagen, dass Ihre Software in einer nicht deterministischen Umgebung ausgeführt wird und viele externe Faktoren die Ausführung beeinflussen können.

Scherz beiseite, automatisierte Überprüfung

Es gibt bereits statische Codeanalysatoren , die riskante Programmierkonstrukte erkennen können (nicht initialisierte Variablen, Pufferüberläufe usw.). Diese funktionieren, indem Sie ein Diagramm Ihres Programms erstellen und die Ausbreitung von Einschränkungen (Typen, Wertebereiche, Sequenzierung) analysieren.

Diese Art der Analyse wird übrigens auch von einigen Compilern zur Optimierung durchgeführt.

Es ist sicherlich möglich, noch einen Schritt weiter zu gehen, die Parallelität zu analysieren und Rückschlüsse auf die Ausbreitung von Einschränkungen über mehrere Threads, die Synchronisation und die Rennbedingungen zu ziehen. Sehr schnell würden Sie jedoch auf das Problem der kombinatorischen Explosion zwischen den Ausführungspfaden und vielen Unbekannten (E / A, Betriebssystemplanung, Benutzereingaben, Verhalten externer Programme, Unterbrechungen usw.) stoßen, die bekannte Einschränkungen auf den Punkt bringen Minimum und machen es sehr schwierig, nützliche automatisierte Schlussfolgerungen zu beliebigem Code zu ziehen.

Turing ging darauf bereits 1936 mit seiner Arbeit über das Problem des Stillstands ein. Eines der Ergebnisse ist, dass es unmöglich ist, einen Algorithmus zu schreiben, der 100% der Zeit Code analysieren und korrekt bestimmen kann, ob er anhält oder nicht. Es ist unmöglich, einen Algorithmus zu schreiben, der 100% der Zeit korrekt ist Bestimmen Sie, ob Code eine bestimmte Eigenschaft hat oder nicht, einschließlich "Sicherheit", wie auch immer Sie sie definieren möchten.

Das Ergebnis von Turing schließt jedoch nicht die Möglichkeit eines Programms aus, das 100% der Zeit entweder (1) absolut sicher sein kann, dass Code sicher ist, (2) absolut feststellt, dass Code unsicher ist, oder (3) anthropomorph die Hände hochwirft und sagt "Mist, ich weiß es nicht." Rusts Compiler gehört im Allgemeinen zu dieser Kategorie.

Wenn ein Programm vollständig ist (der technische Name für ein Programm, das garantiert angehalten wird), ist es theoretisch möglich, eine beliebige Eigenschaft über das Programm zu beweisen, wenn genügend Ressourcen vorhanden sind. Sie können einfach jeden potenziellen Status untersuchen, in den das Programm eintreten könnte, und prüfen, ob einer von ihnen Ihr Eigentum verletzt. Die TLA + -Modellprüfsprache verwendet eine Variante dieses Ansatzes und verwendet die Mengenlehre, um Ihre Eigenschaften anhand von Mengen potenzieller Programmzustände zu überprüfen, anstatt alle Zustände zu berechnen.

Technisch gesehen ist jedes Programm, das auf einer praktischen physischen Hardware ausgeführt wird, entweder vollständig oder eine nachweisbare Schleife, da nur eine begrenzte Menge an Speicher verfügbar ist, sodass der Computer nur eine begrenzte Anzahl von Zuständen haben kann. (Beliebig praktisch Computer ist eigentlich eine endliche Zustandsmaschine, nicht Turing vollständig, aber der Zustandsraum ist so groß, dass es einfacher ist, so zu tun, als würden sie vollständig werden.

Das Problem bei diesem Ansatz besteht darin, dass die Menge an Speicherplatz und Größe des Programms exponentiell komplex ist, was es für alles andere als den Kern von Algorithmen unpraktisch macht und unmöglich ist, es vollständig auf signifikante Codebasen anzuwenden.

Die überwiegende Mehrheit der Forschung konzentriert sich daher auf Beweise. Die Curry-Howard-Korrespondenz besagt, dass ein Korrektheitsnachweis und ein Typensystem ein und dasselbe sind, so dass der größte Teil der praktischen Forschung unter dem Namen Typensysteme geführt wird. Besonders relevant für diese Diskussion sind Coq und Idriss, zusätzlich zu Rust, den Sie bereits erwähnt haben. Coq nähert sich dem zugrunde liegenden technischen Problem aus der anderen Richtung. Wenn ein Beweis für die Richtigkeit von beliebigem Code in der Coq-Sprache erbracht wird, kann Code generiert werden, der das bewährte Programm ausführt. Idriss verwendet mittlerweile ein abhängiges Typsystem, um beliebigen Code in einer reinen Haskell-ähnlichen Sprache zu beweisen. Beide Sprachen übertragen die schwierigen Probleme beim Generieren eines funktionsfähigen Proofs auf den Writer, sodass sich die Typprüfung auf die Überprüfung des Proofs konzentrieren kann. Das Überprüfen des Beweises ist ein viel einfacheres Problem, aber dies erschwert die Arbeit mit den Sprachen erheblich.

Beide Sprachen wurden speziell entwickelt, um Beweise zu vereinfachen und mithilfe der Reinheit zu steuern, welcher Status für welche Teile des Programms relevant ist. Für viele gängige Sprachen kann der bloße Nachweis, dass ein Teil des Staates für den Nachweis eines Teils des Programms irrelevant ist, aufgrund der Art der Nebenwirkungen und der veränderlichen Werte ein komplexes Problem sein.