Geekly articles weekly

La complétude inattendue de Turing partout

Un catalogue de constructions logicielles, de langages et d'API qui sont inopinément complets. les implications de cela pour la sécurité et la fiabilité. Application: combien d'ordinateurs dans votre ordinateur?

Tout programme C ou Fortran assez complexe contient une implémentation nouvellement écrite, non spécifiée, boguée et lente de la moitié du langage Common Lisp . - Dixième règle Greenspan

La complétude de Turing (TC) est une propriété du système pour implémenter n'importe quelle fonction calculable avec une représentation simple des entrées et des sorties.

Turing l'exhaustivité est un concept fondamental en informatique. Il aide à répondre à de nombreuses questions clés, par exemple, pourquoi il est impossible de créer le programme antivirus parfait. Mais en même temps, c'est une occurrence étonnamment commune . Il semblerait qu'il soit difficile pour un système informatique d'atteindre une telle universalité qu'il puisse exécuter n'importe quel programme, mais l'inverse est vrai: il est difficile d'écrire un système utile qui ne se transforme pas immédiatement en un Turing complet. Il s'avère que même un petit contrôle sur les données d'entrée et leur conversion en résultat, en règle générale, vous permet de créer un système complet. Il peut être drôle, utile (bien que ce ne soit généralement pas le cas ), nuisible ou extrêmement dangereux et un véritable cadeau pour un pirate informatique (voir «Sécurité théorique et linguistique» , qui étudie les méthodes de piratage de «machines étranges» 1). ) Des exemples étonnants de ce comportement nous rappellent que l'intégralité de Turing se cache partout et qu'il est extrêmement difficile de protéger le système.

Des langages de programmation trop puissants peuvent également déclencher des attaques DoS désagréables. Fazzer afl a trouvé une telle roff dans OpenBSD qu'il est capable de générer une boucle infinie , abusant de certaines règles de substitution de chaînes.

Probablement, ces exemples inattendus de systèmes complets de Turing sont mieux considérés comme un sous-ensemble des langages de programmation ésotériques «découverts» ou «trouvés». Le FRACTRAN extraordinairement minimaliste n'est donc pas considéré 2 , ainsi que le langage spécialement obscurci Malbolge (où l'écriture d'un programme trivial prendra des années), car ce sont des YaP ésotériques spécialement conçus. De plus, le jeu Life n'est pas inclus dans notre sous-ensemble, car des questions sur l'intégralité de Turing sont apparues immédiatement après sa sortie, et la reconnaissance de son Turing complet n'est pas une surprise. Et compte tenu de la complexité des réseaux avec routage et commutation de paquets, il n'est pas surprenant que vous puissiez construire un automate cellulaire ou programmer des schémas logiques sur ces réseaux, et la planification / validation des tickets n'est pas seulement une tâche difficile pour NP et même EXPSPACE, mais elle est complètement insoluble (en raison de règles complexes des compagnies aériennes).

De nombreuses configurations, langages spéciaux, outils ou jeux complexes, en fin de compte, violent la règle du moindre pouvoir et «deviennent accidentellement Turing complet» , comme le MediaWiki , les modèles sed ou les commandes répétées regexp / find-replace dans l'éditeur. En général, toute forme de remplacement de ligne ou de création de modèles ou de compilation à la volée avec une forte probabilité est un système Turing complet lui-même ou lorsqu'il est répété, car ils prennent souvent en charge le calcul lambda ou la réécriture des termes d'une langue ou d'une étiquette, par exemple, les langues ésotériques " /// " ou thue .

XSLT , Démineur Infini , Forteresse Naine 3 , Starcraft, Minecraft , Ant , Transport Tycoon , les modèles C ++ et les généralisations Java , les calculs d'ADN et ainsi de suite - tous ces systèmes sont Turing-complet, et cela n'est pas surprenant non plus. De nombreux jeux prennent en charge les scripts pour simplifier le développement et les mods personnalisés. Par conséquent, pour rendre le jeu Turing-complete élémentaire: il suffit d'activer la syntaxe pour appeler des langages plus connus tels que Perl.

Turing l'exhaustivité peut simplement être une partie peu connue du format standard. À notre époque, beaucoup ne savent probablement pas que TrueType et de nombreuses polices sont des programmes PostScript sur des machines empilées, similaires aux métadonnées ELF et aux informations de débogage DWARF . Ou que certains formats de musique dépassent le MIDI , prennent en charge les scripts et nécessitent une interprétation. Si vous connaissez l'intégralité de Turing des polices, alors l'intégralité des documents Turing de TeX n'est pas surprenant, ce qui entraîne naturellement de nombreuses failles de sécurité sérieuses et intéressantes dans les polices et les supports, telles que BLEND ou Linux SNES et NES . Dans d'autres formats comme PDF, il y a juste une quantité terrible de vulnérabilités 4 . Encore une fois, des réalisations exceptionnelles comme la création d'une petite machine de Turing à partir de blocs Lego ou de dominos 5 ne sont pas pris en compte, car nous savons depuis longtemps comment fonctionnent les ordinateurs mécaniques.

D'un autre côté, une ligne de recherche en sécurité informatique appelée machines étranges révèle souvent des systèmes vraiment incroyables et complets. De plus, ils provoquent la surprise à différents degrés chez différentes personnes: l'une semble inhabituelle et ne surprend pas les autres.


Peut-être que les systèmes suivants seront accidentellement terminés:

  • CSS sans clics
  • SVG: PostScript est TC par conception, mais qu'en est-il du format graphique vectoriel SVG plus moderne, qui est écrit en XML, c'est-à-dire dans un langage de document qui n'est (généralement) pas Turing-complet? Il semble qu'en combinaison avec XSLT, il puisse toujours en être ainsi, mais je n'ai trouvé aucune preuve ou démonstration de cela dans le contexte habituel d'un navigateur Web. La norme SVG est excellente et parfois terrifiante: une version infructueuse de la norme SVG 1.2 a essayé d'ajouter la possibilité d'ouvrir des sockets réseau dans des images SVG.
  • Unicode : Nicholas Seriot suggère que les algorithmes Unicode bidirectionnels (conçus pour afficher des scripts de droite à gauche, tels que l'arabe ou l'hébreu) ​​peuvent être suffisamment complexes pour prendre en charge un système de balises via des règles sensibles à la casse (par exemple, le turc)

Voir aussi



Les références



App


Combien d'ordinateurs compte votre ordinateur?


Certains s'enlisent dans des disputes sur des voitures étranges ou sur la taille d'un agent d'intelligence artificielle: un tel, deux, dix ou des millions seront créés. Cela n'a pas d'importance, car ce n'est qu'une question d'organisation. En fait, les entrées et sorties du système sont importantes: quelle est l'efficacité du système dans son ensemble et quelles ressources consomme-t-il? Personne ne se soucie si Google fonctionne sur 50 superordinateurs, 50 000 ordinateurs centraux, 5 millions de serveurs, 50 millions de processeurs intégrés / mobiles ou une combinaison de tous les éléments ci-dessus . Peu importe que Google utilise une variété de puces: des «processeurs tenseurs» faits maison aux processeurs au silicium uniques (Intel les vend sur des puces pour les processeurs Xeon pour un certain nombre de clients majeurs), FPGA, GPU, CPU, à des équipements encore plus exotiques comme les ordinateurs quantiques D-Wave . Il est seulement important qu'il reste compétitif et puisse fournir des services moyennant des frais modérés. En fin de compte, aujourd'hui, un supercalculateur ressemble généralement à un grand nombre de serveurs rack avec une énorme quantité de GPU et des connexions InfiniBand inhabituellement rapides. Autrement dit, le supercalculateur n'est pas si différent du centre de données, comme vous pourriez le penser. Tout équipement répertorié peut prendre en charge de nombreuses machines étranges, en fonction de sa dynamique interne et de sa connectivité.

De même, tout système d'IA peut être mis en œuvre sous la forme d'un réseau neuronal géant ou de nombreux réseaux neuronaux séparés fonctionnant de manière asynchrone, ou comme un ensemble hétérogène de microservices, ou comme une «société de l'esprit» et ainsi de suite. Tout cela n'est pas particulièrement important. Du point de vue de la complexité ou des risques, la façon dont le système est organisé pendant son fonctionnement n'est pas si importante. Le système peut être vu à plusieurs niveaux, chacun étant également invalide en soi, mais utile à différentes fins dans le système général.

Voici un exemple d'une question mal définie: combien d'ordinateurs avez-vous dans vos poches et sur votre bureau maintenant? Combien d'ordinateurs compte votre «ordinateur»? Pensez-en un seul? Examinons de plus près.

Il ne s'agit pas seulement du processeur: de nos jours, les transistors et les cœurs de processeur sont si bon marché qu'il est souvent logique d'allouer des cœurs séparés pour les tâches en temps réel, pour améliorer les performances, pour la sécurité, pour éviter de charger le système d'exploitation principal, pour la compatibilité avec l'ancienne architecture ou progiciel existant. Tout simplement parce qu'un DSP ou un noyau est plus rapide à programmer que la création d'un ASIC spécialisé, ou parce que c'est la solution la plus simple possible. De plus, bon nombre de ces composants peuvent être utilisés comme éléments de calcul, même s'ils ne sont pas prévus ou masquent même cette fonctionnalité.

Donc:

  • Dans un processeur Intel conventionnel, des milliards de transistors effectuent de nombreuses tâches:

    • Chacun des cœurs de processeur principal 2-8 est capable de fonctionner indépendamment, en s'allumant et en s'éteignant si nécessaire, il a son propre cache (plus grand que la RAM dans la plupart des ordinateurs jusqu'à récemment), et il doit être considéré comme un ordinateur indépendant.
    • Le processeur dans son ensemble est reprogrammé via un microcode, par exemple, pour éliminer les erreurs de conception des puces et affiche des objets de plus en plus opaques, tels que Intel Management Engine (avec JVM pour la programmation ; Rouen, 2014 et SGX ) ou le Platform Security Processor (PSP) d'AMD, ou Android TEE Ces modules matériels sont, en règle générale, des ordinateurs à part entière, fonctionnent indépendamment de l'hôte et peuvent interférer avec son fonctionnement.
    • Tout FPU peut devenir un système complet de Turing grâce à l'encodage dans des opérations en virgule flottante dans l'esprit de FRACTRAN.
  • La MMU peut être programmée dans une étrange machine à défaut de page, comme mentionné ci-dessus.
  • Blocs DSP , puces personnalisées. Les ASIC pour les formats vidéo comme h.264 ne seront probablement pas des systèmes complets (malgré la prise en charge de deltas complexes et de méthodes de compression qui peuvent permettre quelque chose comme les tuiles Van). Mais le SoC mobile Apple A9 va bien au-delà du processeur ARM dual-core habituel avec un GPU intégré. Comme les puces de bureau Intel ou AMD, il comprend un environnement sécurisé appelé Secure Enclave (cœurs de processeur physiquement dédiés), mais il contient également un coprocesseur pour les images, un coprocesseur pour la reconnaissance vocale (en partie pour prendre en charge Siri) et, apparemment, plusieurs autres cœurs. Ces ASIC existent parfois pour des tâches d'IA et, apparemment, se spécialisent dans les multiplications matricielles pour les réseaux de neurones, et puisque les réseaux de neurones récurrents sont Turing complets, alors ... vous comprenez. Motorola, Qualcomm et d'autres sociétés se sont également précipités pour étendre leur SoC.
  • BIOS de la carte mère et / ou puces de contrôle d'accès au réseau.

    • Mark Ermolov note:

      «Il est étonnant de voir combien de cœurs de processeurs hétérogènes sont intégrés dans Intel Silvermont Moorefield SoC (ANN): x86, ARC, LMT, 8051, Audio DSP, chacun avec son propre firmware et la prise en charge de l'interface JTAG

    Ces puces de contrôle ou de débogage peuvent «accidentellement» rester activées sur les appareils après la vente, comme l'ARM intégré dans la CPU Via C3 .
  • Le GPU a plusieurs centaines ou milliers de cœurs simples, chacun fonctionnant très bien avec les réseaux de neurones ou effectuant des calculs à usage général (bien que plus lent qu'un processeur).
  • Les contrôleurs de bande, de disque dur, de lecteur flash et de SSD s'exécutent généralement sur des processeurs ARM pour exécuter des utilitaires intégrés pour des tâches telles que masquer les secteurs défectueux du système d'exploitation. Ils peuvent être piratés. Mais les processeurs ARM sont utilisés dans la plupart des applications embarquées, donc ARM aime se vanter qu ' «un smartphone moderne contient de 8 à 14 processeurs ARM, dont l'un est un processeur d'application (fonctionnant sous Android ou iOS), et l'autre est un processeur pour la pile de bandes de fréquences (pile de bande de base) . "
  • les puces réseau effectuent un traitement indépendant pour DMA (grâce à des fonctions d'indépendance telles que Wake-on-LAN pour le travail de démarrage réseau ).
  • smartphones: en plus de tous les blocs mentionnés, il existe également un processeur de bande de base indépendant qui fonctionne sous son propre système d'exploitation en temps réel pour traiter les communications avec les tours de téléphonie cellulaire / GPS / etc. Ou même plus d'un si vous utilisez la virtualisation comme L4 . Des portes dérobées ont déjà été détectées dans les processeurs en bande de base, en plus d'autres vulnérabilités.
  • Les cartes SIM pour smartphones sont bien plus que de simples cartes mémoire avec l'enregistrement de vos données d'abonné. Ce sont des cartes à puce qui peuvent exécuter indépendamment des applications Java Card (probablement des puces NFC aussi). C'est comme une JVM dans IME. Naturellement, les cartes SIM peuvent être piratées et utilisées pour la surveillance, etc.
  • Les appareils connectés via USB ou à la carte mère peuvent être équipés de leurs propres processeurs. Par exemple, les adaptateurs WiFi, les claviers, les souris, etc. Théoriquement, la plupart d'entre eux sont isolés des interférences directes avec l'hôte via DMA et IOMMU, mais le diable est dans les détails ...
  • puces étranges aléatoires comme le MacBook Touch exécutant WatchOS .
  • ...

Ainsi, dans un smartphone ou un ordinateur de bureau classique, il y aura de quinze à plusieurs milliers d'ordinateurs dans le sens d'appareils complets. Chacun d'eux peut être programmé, il a suffisamment de puissance pour exécuter de nombreux programmes et peut être utilisé par un attaquant pour surveiller, exfiltrer ou attaquer le reste du système.

Il n'y a rien d'inhabituel dans le contexte historique, car même les tout premiers mainframes comprenaient généralement plusieurs ordinateurs où l'ordinateur principal effectue un traitement par lots, et les ordinateurs auxiliaires fournissent des opérations d'E / S à grande vitesse, qui autrement interféreraient avec la machine principale avec leurs interruptions.

En pratique, en plus de la communauté de la sécurité de l'information (puisque tous ces ordinateurs sont dangereux et, par conséquent, utiles pour les rédacteurs de virus et de NSA), tous les autres utilisateurs ne se soucient pas que sous le capot de nos ordinateurs se trouvent des systèmes incroyablement complexes qui sont plus précisément considérés comme une ménagerie hétéroclite de centaines ordinateurs embarrassants connectés les uns aux autres (ce n'est pas clair, "un réseau est un ordinateur" ou "un ordinateur est un réseau" ...?). L'utilisateur le perçoit et l'utilise comme un seul ordinateur.


1. Un domaine de recherche actif est la création de langages et de systèmes soigneusement conçus et garantis de ne pas être complets de Turing (par exemple, une programmation totalement fonctionnelle ). Pourquoi consacrer autant d'efforts à la création d'un langage que de nombreux programmes ne peuvent pas écrire? Le fait est que l'exhaustivité de Turing est étroitement liée au théorème d'incomplétude de Gödel et au théorème de Rice.. Par conséquent, si TC est autorisé, nous perdons toutes les propriétés de provabilité possibles. Au contraire, diverses choses utiles sont facilement prouvées dans un langage Turing-incomplet: par exemple, qu'un programme est complet, de type sécurisé ou non, qu'il est facile de convertir en un théorème logique, qu'il consomme une quantité limitée de ressources, que la mise en œuvre du protocole est vraie ou équivalente à une autre mise en œuvre. Il est facile de prouver qu'il n'y a pas d' effets secondaires et que le programme peut être converti en une option logiquement équivalente mais plus rapide (cela est particulièrement important pour les langages déclaratifs comme SQL, où la capacité de l' optimiseur à convertir des requêtes est la clé de performances acceptables. Bien que, bien sûr, des choses étonnantes puissent être faites avec SQL, commedescente de gradient pour les modèles d'apprentissage automatique , et certaines extensions SQL le rendent de toute façon complet , vous permettant soit de coder un système en boucle , ou modelDSL , ou d'appeler PL / SQL , etc.

Voici de la littérature sur les voitures étranges:


↑

2. Bien que les réseaux de neurones linéaires exploitent le mode virgule flottante avec arrondi à zéro pour coder un comportement potentiellement complet de Turing (pour RNN), il est invisible en fonctionnement normal, ce qui est également un comportement aléatoire de Turing complet et un bon exemple d'un langage sûr. ↑

3. La forteresse naine fournit une horloge, donc l'intégralité de Turing n'est pas surprenante. Mais l'eau est également implémentée comme un simple automate cellulaire, il y a donc encore plus de façons d'obtenir l'intégralité de turing! Maintenant, le wiki du jeu nomme quatre façons possibles de créer des portes logiques: les liquides, les mécanismes d'horlogerie, les chariots de mine et les portes logiques de créature / animal avec des portes et des capteurs de pression. ↑

4. La spécification PDF complète est exceptionnellement gonflée. Par exemple, dans une visionneuse PDF simple qui prend en charge une bonne quantité de spécifications PDF comme le navigateur Google Chrome, vous pouvez jouer à Breakout (car le PDF comprend son propre sous-ensemble étrange de JavaScript). La visionneuse officielle Adobe PDF prend en charge des fonctionnalités allant jusqu'à la CAO en trois dimensions. ↑

5. Voir les portes logiques domino sur Think Math et la démo d'un additionneur de jointure domino 4 bits . ↑

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

More articles:


All Articles