Geekly articles weekly

Turings unerwartete Vollständigkeit überall

Ein Katalog von Softwarekonstrukten, Sprachen und APIs, die unerwartet vollständig sind. die Auswirkungen auf die Sicherheit und Zuverlässigkeit. Anwendung: Wie viele Computer in Ihrem Computer?

Jedes ziemlich komplexe C- oder Fortran-Programm enthält eine neu geschriebene, nicht spezifizierte, fehlerhafte und langsame Implementierung der Hälfte der Common Lisp-Sprache . - Zehnte Greenspan-Regel

Turing Completeness (TC) ist eine Eigenschaft des Systems, um jede berechenbare Funktion mit einer einfachen Darstellung von Eingabe und Ausgabe zu implementieren.

Die Vollständigkeit ist ein grundlegendes Konzept in der Informatik. Es hilft, viele wichtige Fragen zu beantworten, zum Beispiel, warum es unmöglich ist, das perfekte Antivirenprogramm zu erstellen. Gleichzeitig ist es ein auffallend häufiges Ereignis. Es scheint schwierig für ein Computersystem zu sein, eine solche Universalität zu erreichen, dass es jedes Programm ausführen kann, aber das Gegenteil ist der Fall: Es ist schwierig, ein nützliches System zu schreiben, das sich nicht sofort in ein vollständiges Turing verwandelt. Es stellt sich heraus, dass selbst ein wenig Kontrolle über die Eingabedaten und deren Umwandlung in ein Ergebnis in der Regel die Erstellung eines vollständigen Systems ermöglicht. Es kann lustig, nützlich (wenn auch normalerweise nicht ), schädlich oder extrem unsicher und ein echtes Geschenk für einen Hacker sein (siehe „Sprachtheoretische Sicherheit“ , in der Hacking-Methoden von „fremden Maschinen“ 1 untersucht werden ) Erstaunliche Beispiele für dieses Verhalten erinnern uns daran, dass die Vollständigkeit von Turing überall lauert und es äußerst schwierig ist, das System zu schützen.

Zu leistungsfähige Programmiersprachen können auch unangenehme DoS-Angriffe auslösen. Fazzer afl hat in OpenBSD einen solchen Fehler gefunden, dass es in der Lage ist, eine Endlosschleife zu generieren, wobei einige Regeln für die Ersetzung von Zeichenfolgen missbraucht werden.

Wahrscheinlich werden diese unerwarteten Beispiele für Turing-vollständige Systeme besser als Teilmenge der esoterischen Programmiersprachen „entdeckt“ oder „gefunden“ betrachtet. Der außerordentlich minimalistische FRACTRAN wird also nicht berücksichtigt 2 sowie die speziell verschleierte Sprache Malbolge (wo das Schreiben eines trivialen Programms Jahre dauern wird), da es sich um speziell entworfene esoterische YaP handelt. Außerdem ist das Life-Spiel nicht in unserer Untergruppe enthalten, da Fragen zur Vollständigkeit von Turing unmittelbar nach seiner Veröffentlichung auftauchten und die Anerkennung seines vollständigen Turing nicht überraschend war. Angesichts der Komplexität von Routing- und Paketvermittlungsnetzwerken ist es nicht überraschend, dass ein Mobilfunkautomat auf diesen Netzwerken aufgebaut oder Logikschemata programmiert werden können und die Ticketplanung / -validierung nicht nur eine NP-schwierige oder sogar EXPSPACE-schwierige Aufgabe ist, sondern auch völlig unlösbar (aufgrund von komplexe Fluglinienregeln).

Wie sich herausstellt, verstoßen viele Konfigurationen, spezielle Sprachen, Tools oder komplexe Spiele gegen die Regel der geringsten Leistung und werden „versehentlich vollständig“ , wie MediaWiki , sed Vorlagen oder wiederholte Befehle für reguläres Ausdrücken / Ersetzen im Editor. Im Allgemeinen ist jede Form des Ersetzens oder Templierens von Zeilen oder des schnellen Kompilierens mit hoher Wahrscheinlichkeit ein Turing-vollständiges System selbst oder bei Wiederholung, da sie häufig die Lambda-Berechnung oder das Umschreiben von Begriffen einer Sprache oder eines Etiketts unterstützen, z. B. esoterische Sprachen " /// ". oder thue .

XSLT , Infinite Minesweeper , Zwergenfestung 3 , Starcraft, Minecraft , Ant , Transport Tycoon , C ++ - Vorlagen und Java-Verallgemeinerungen , DNA-Berechnungen usw. - all dies sind Turing-vollständige Systeme, und dies ist auch nicht überraschend. Viele Spiele unterstützen Skripte, um die Entwicklung und benutzerdefinierte Mods zu vereinfachen. Um das Turing-vollständige Spiel elementar zu machen, aktivieren Sie einfach die Syntax, um bekanntere Sprachen wie Perl aufzurufen.

Die Vollständigkeit kann einfach ein wenig bekannter Teil des Standardformats sein. Wahrscheinlich wissen in unserer Zeit viele nicht, dass TrueType und viele Schriftarten PostScript-Programme auf gestapelten Computern sind, ähnlich wie ELF-Metadaten und DWARF-Debugging-Informationen . Oder dass einige Musikformate über MIDI hinausgehen, Skripte unterstützen und interpretiert werden müssen. Wenn Sie sich der Turing-Vollständigkeit von Schriftarten bewusst sind, ist die Vollständigkeit der TeX-Dokumentoptimierung nicht überraschend, was natürlich viele schwerwiegende und interessante Sicherheitslücken in Schriftarten und Medien wie BLEND- oder Linux- SNES- und NES- Exploits verursacht. In anderen Formaten wie PDF gibt es nur eine schreckliche Anzahl von Sicherheitslücken 4 . Wieder herausragende Leistungen wie das Erstellen einer kleinen Turing-Maschine aus Legoblöcken oder Dominosteinen 5 werden nicht berücksichtigt, da wir seit langem wissen, wie mechanische Computer funktionieren.

Auf der anderen Seite enthüllt eine Reihe von Untersuchungen zur Computersicherheit, die als seltsame Maschinen bezeichnet werden, oft wirklich erstaunliche Systeme, die vollständig sind. Darüber hinaus sorgen sie bei verschiedenen Menschen in unterschiedlichem Maße für Überraschungen: Eine scheint ungewöhnlich, die andere nicht überrascht.


Möglicherweise sind die folgenden Systeme versehentlich vollständig:

  • CSS ohne Klicks
  • SVG: PostScript ist von Natur aus TC, aber was ist mit dem moderneren SVG- Vektorgrafikformat, das in XML geschrieben ist, dh in einer Dokumentensprache, die (normalerweise) nicht vollständig ist? Es scheint, dass dies in Kombination mit XSLT immer noch der Fall ist, aber ich habe im üblichen Kontext eines Webbrowsers keine Beweise oder Beweise dafür gefunden. Der SVG-Standard ist großartig und manchmal furchterregend: Eine erfolglose Version des SVG 1.2-Standards hat versucht, die Möglichkeit zum Öffnen von Netzwerksockets in SVG-Bildern hinzuzufügen.
  • Unicode : Nicholas Seriot schlägt vor, dass bidirektionale Unicode-Algorithmen (zur Anzeige von Skripten von rechts nach links wie Arabisch oder Hebräisch) komplex genug sein können, um ein Tag-System durch Regeln zu unterstützen, bei denen zwischen Groß- und Kleinschreibung unterschieden wird (z. B. Türkisch).

Siehe auch



Referenzen



App


Wie viele Computer befinden sich in Ihrem Computer?


Einige geraten in Streitigkeiten über seltsame Autos oder darüber, wie „groß“ ein KI-Agent werden wird: Ein solcher, zwei, zehn oder Millionen werden geschaffen. Es spielt keine Rolle, weil es nur eine organisatorische Angelegenheit ist. Tatsächlich sind die Ein- und Ausgänge des Systems wichtig: Wie effizient ist das System insgesamt und welche Ressourcen verbraucht es? Es interessiert niemanden, ob Google auf 50 Supercomputern, 50.000 Mainframes, 5 Millionen Servern, 50 Millionen Embedded / Mobile-Prozessoren oder einer Kombination der oben genannten Funktionen ausgeführt wird . Es spielt keine Rolle, dass Google eine Vielzahl von Chips verwendet: von hausgemachten „Tensorprozessoren“ über einzigartige Siliziumprozessoren (Intel verkauft sie für eine Reihe von Großkunden auf Chips für Xeon-Prozessoren), FPGA, GPU, CPU bis hin zu noch exotischeren Geräten wie D-Wave- Quantencomputern. Es ist nur wichtig, dass es wettbewerbsfähig bleibt und Dienstleistungen gegen eine moderate Gebühr erbringen kann. Am Ende sieht ein Supercomputer heute normalerweise aus wie eine große Anzahl von Rack-Servern mit einer großen Anzahl von GPUs und ungewöhnlich schnellen InfiniBand-Verbindungen. Das heißt, der Supercomputer unterscheidet sich nicht so sehr vom Rechenzentrum, wie Sie vielleicht denken. Jedes der aufgelisteten Geräte kann abhängig von seiner internen Dynamik und Konnektivität zahlreiche seltsame Maschinen unterstützen.

In ähnlicher Weise kann jedes KI-System in Form eines riesigen neuronalen Netzwerks oder vieler separater neuronaler Netzwerke implementiert werden, die asynchron arbeiten, oder als heterogener Satz von Mikrodiensten oder als „Gesellschaft des Geistes“ und so weiter. All dies ist nicht besonders wichtig. Unter dem Gesichtspunkt der Komplexität oder der Risiken ist es nicht so wichtig, wie das System während der Arbeit organisiert ist. Das System kann auf vielen Ebenen gesehen werden, von denen jede für sich gleichermaßen ungültig ist, aber für verschiedene Zwecke im allgemeinen System nützlich ist.

Hier ist ein Beispiel für eine schlecht definierte Frage: Wie viele Computer haben Sie jetzt in Ihrer Tasche und auf Ihrem Schreibtisch? Wie viele Computer befinden sich in Ihrem „Computer“? Denkst du nur einen? Schauen wir uns das genauer an.

Es geht nicht nur um die CPU: Heutzutage sind Transistoren und Prozessorkerne so billig, dass es heutzutage oft sinnvoll ist, separate Kerne für Echtzeitaufgaben zuzuweisen, die Leistung zu verbessern, die Sicherheit zu gewährleisten, die Belastung des Hauptbetriebssystems zu vermeiden, die Kompatibilität mit der alten Architektur zu gewährleisten oder vorhandenes Softwarepaket. Nur weil ein DSP oder Kernel schneller zu programmieren ist als ein spezialisierter ASIC oder weil dies die einfachste mögliche Lösung ist. Darüber hinaus können viele dieser Komponenten als Rechenelemente verwendet werden, auch wenn sie nicht beabsichtigt sind oder diese Funktionalität sogar verbergen.

Also:

  • In einem herkömmlichen Intel-Prozessor führen Milliarden von Transistoren viele Aufgaben aus:

    • Jeder der 2-8 Hauptprozessorkerne kann unabhängig arbeiten und bei Bedarf ein- und ausgeschaltet werden. Er verfügt über einen eigenen Cache (bis vor kurzem bei den meisten Computern größer als RAM) und sollte als unabhängiger Computer betrachtet werden.
    • Die CPU als Ganzes wird beispielsweise über einen Mikrocode neu programmiert, um Chipdesignfehler zu beseitigen, und zeigt zunehmend undurchsichtige Objekte wie Intel Management Engine (mit JVM für die Programmierung ; Rouen, 2014 und SGX ) oder AMDs Platform Security Processor (PSP) oder Android TEE Diese Hardwaremodule sind in der Regel eigenständige Computer, arbeiten unabhängig vom Host und können dessen Betrieb beeinträchtigen.
    • Jede FPU kann durch Codierung in Gleitkommaoperationen im Sinne von FRACTRAN zu einem Turing-vollständigen System werden.
  • Die MMU kann wie oben erwähnt in eine seltsame Seitenfehlermaschine programmiert werden.
  • DSP- Blöcke, benutzerdefinierte Chips. Wahrscheinlich werden ASICs für Videoformate wie h.264 keine vollständigen Systeme sein (trotz der Unterstützung komplexer Deltas und Komprimierungsmethoden, die so etwas wie Van-Kacheln ermöglichen können). Der mobile Apple A9 SoC geht jedoch weit über den üblichen Dual-Core-ARM-Prozessor mit integrierter GPU hinaus. Wie Intel- oder AMD-Desktop-Chips enthält es eine sichere Umgebung namens Secure Enclave (physisch dedizierte Prozessorkerne), aber auch einen Coprozessor für Bilder, einen Coprozessor für die Spracherkennung (teilweise zur Unterstützung von Siri) und anscheinend mehrere andere Kerne. Diese ASICs existieren manchmal für KI-Aufgaben und sind anscheinend auf Matrixmultiplikationen für neuronale Netze spezialisiert. Da wiederkehrende neuronale Netze Turing-vollständig sind, ... kennen Sie sich selbst. Motorola, Qualcomm und andere Unternehmen beeilten sich ebenfalls, ihren SoC zu erweitern.
  • Motherboard-BIOS- und / oder Netzwerkzugriffskontrollchips.

    • Mark Ermolov bemerkt:

      „Es ist erstaunlich, wie viele heterogene Prozessorkerne in Intel Silvermont Moorefield SoC (ANN) integriert sind: x86, ARC, LMT, 8051, Audio-DSP, jeder mit seiner eigenen Firmware und Unterstützung für die JTAG-Schnittstelle

    Diese Steuerungs- oder Debugging-Chips können nach dem Verkauf auf Geräten wie dem integrierten ARM in der Via C3-CPU „versehentlich“ aktiviert bleiben.
  • Die GPU verfügt über mehrere hundert oder tausend einfache Kerne, von denen jeder sehr gut mit neuronalen Netzen zusammenarbeitet oder allgemeine Berechnungen durchführt (wenn auch langsamer als ein Prozessor).
  • Band-, Festplatten-, Flash-Laufwerk- und SSD-Controller werden normalerweise auf ARM-Prozessoren ausgeführt, um integrierte Dienstprogramme für Aufgaben wie das Ausblenden fehlerhafter Sektoren vor dem Betriebssystem auszuführen. Sie können gehackt werden. ARM-Prozessoren werden jedoch in den meisten eingebetteten Anwendungen verwendet. Daher rühmt sich ARM gern damit, dass „ein modernes Smartphone 8 bis 14 ARM-Prozessoren enthält, von denen einer ein Anwendungsprozessor (mit Android oder iOS) und der andere ein Prozessor für den Frequenzbandstapel ist (Basisbandstapel) . "
  • Netzwerkchips führen eine unabhängige Verarbeitung für DMA durch (dank solcher Unabhängigkeitsfunktionen wie Wake-on-LAN für Netboot-Arbeit ).
  • Smartphones: Zusätzlich zu allen genannten Blöcken gibt es einen unabhängigen Basisbandprozessor , der unter einem eigenen Echtzeitbetriebssystem ausgeführt wird, um die Kommunikation mit Mobilfunkmasten / GPS / usw. zu verarbeiten. Oder sogar mehr als eine, wenn Sie Virtualisierung wie L4 verwenden . Neben anderen Sicherheitslücken wurden bereits Backdoors in Basisbandprozessoren erkannt.
  • SIM-Karten für Smartphones sind viel mehr als nur Speicherkarten für die Aufzeichnung Ihrer Teilnehmerdaten. Hierbei handelt es sich um Smartcards, auf denen Java Card- Anwendungen unabhängig ausgeführt werden können (wahrscheinlich auch NFC-Chips). Es ist wie eine JVM in IME. Natürlich können SIM-Karten gehackt und zur Überwachung usw. verwendet werden.
  • Geräte, die über USB oder an das Motherboard angeschlossen sind, können mit eigenen Prozessoren ausgestattet werden. Zum Beispiel WiFi-Adapter, Tastaturen, Mäuse usw. Theoretisch sind die meisten von ihnen durch DMA und IOMMU von direkten Interferenzen mit dem Host isoliert, aber der Teufel steckt im Detail ...
  • zufällige seltsame Chips wie das MacBook Touch mit WatchOS .
  • ...

In einem normalen Smartphone oder Desktop-Computer gibt es also fünfzehn bis mehrere tausend Computer im Sinne von kompletten Geräten. Jedes von ihnen kann programmiert werden, es hat genug Leistung, um viele Programme auszuführen, und kann von einem Angreifer verwendet werden, um den Rest des Systems zu überwachen, zu filtern oder anzugreifen.

Im historischen Kontext gibt es nichts Ungewöhnliches, da selbst die allerersten Mainframes normalerweise mehrere Computer enthielten, auf denen der Hauptcomputer eine Stapelverarbeitung durchführt, und Zusatzcomputer Hochgeschwindigkeits-E / A-Operationen bereitstellen, die andernfalls die Hauptmaschine mit ihren Interrupts stören würden.

In der Praxis ist es allen anderen Benutzern neben der Community für Informationssicherheit (da alle diese Computer unsicher und daher für NSA- und Virenschreiber nützlich sind) egal, dass sich unter der Haube unserer Computer wahnsinnig komplexe Systeme befinden, die genauer als bunte Menagerie von Hunderten angesehen werden Computer, die peinlich miteinander verbunden sind (es ist nicht klar, "ein Netzwerk ist ein Computer" oder "ein Computer ist ein Netzwerk" ...?). Der Benutzer nimmt dies als einen Computer wahr und verwendet es.


1. Ein aktives Forschungsgebiet ist die Schaffung von Sprachen und Systemen, die sorgfältig entworfen wurden und garantiert nicht vollständig sind (z. B. voll funktionsfähige Programmierung ). Warum so viel Aufwand in die Erstellung einer Sprache investieren, die viele Programme nicht schreiben können? Die Tatsache , dass Turing Vollständigkeit eng verwandt ist Gödels Unvollständigkeitssatz und der Satz von Reis. Wenn TC erlaubt ist, verlieren wir daher alle möglichen Nachweisbarkeitseigenschaften. Im Gegenteil, verschiedene nützliche Dinge lassen sich in einer Turing-unvollständigen Sprache leicht beweisen: Zum Beispiel, dass ein Programm vollständig, typsicher ist oder nicht, dass es leicht in ein logisches Theorem konvertiert werden kann, dass es eine begrenzte Menge an Ressourcen verbraucht, dass die Protokollimplementierung wahr ist oder einer anderen Implementierung entspricht. Es ist leicht zu beweisen, dass es keine Nebenwirkungen gibt und dass das Programm in eine logisch äquivalente, aber schnellere Option konvertiert werden kann (dies ist besonders wichtig für deklarative Sprachen wie SQL, bei denen die Fähigkeit des Optimierers , Abfragen zu konvertieren, der Schlüssel zu einer akzeptablen Leistung ist. Obwohl mit SQL natürlich erstaunliche Dinge möglich sind, sowieGradientenabstieg für Modelle des maschinellen Lernens und einige SQL-Erweiterungen machen es ohnehin vollständig , sodass Sie entweder ein Schleifensystem oder modelDSL codieren oder PL / SQL usw. aufrufen können.

Hier ist einige Literatur zu seltsamen Autos:


↑

2. Obwohl lineare neuronale Netze den Gleitkommamodus mit Rundung auf Null nutzen , um potenziell Turing-vollständiges Verhalten (für RNN) zu codieren, ist es im normalen Betrieb unsichtbar. Dies ist auch ein zufälliges Turing-vollständiges Verhalten und ein gutes Beispiel für eine sichere Sprache. ↑

3. Die Zwergenfestung bietet ein Uhrwerk, daher ist die Vollständigkeit von Turing nicht überraschend. Wasser wird aber auch als einfacher zellularer Automat implementiert, sodass es noch mehr Möglichkeiten gibt, die Vollständigkeit zu gewährleisten! Das Spiel-Wiki nennt nun vier mögliche Möglichkeiten, um Logikgatter zu erstellen: Flüssigkeiten, Uhrwerkmechanismen, Minenwagen und Logikgatter für Tiere / Tiere mit Türen und Drucksensoren. ↑

4. Die vollständige PDF-Spezifikation ist außergewöhnlich aufgebläht. In einem einfachen PDF-Viewer, der genügend PDF-Spezifikationen unterstützt, wie z. B. dem Google Chrome-Browser, können Sie beispielsweise Breakout abspielen (da PDF eine eigene seltsame Teilmenge von JavaScript enthält). Der offizielle Adobe PDF Viewer unterstützt Funktionen bis zu dreidimensionalem CAD. ↑

5. Sehen Sie sich die Domino-Logikgatter in Think Math und die Demo eines 4-Bit-Domino-Knöcheladdierers an . ↑

Source: https://habr.com/ru/post/de429602/

More articles:


All Articles