Est-il possible d'évaluer par programme la sécurité d'un code arbitraire?

J'ai beaucoup pensé récemment au code sûr. Thread-safe. Sans danger pour la mémoire. Ne va pas exploser dans votre visage avec un défaut de sécurité. Mais pour plus de clarté dans la question, utilisons le modèle de sécurité de Rust comme définition courante.

Souvent, assurer la sécurité est un peu un problème de taille, car, comme le démontre le besoin de Rust unsafe, il existe des idées de programmation très raisonnables, comme la concurrence, qui ne peuvent pas être implémentées dans Rust sans utiliser le unsafemot clé . Même si la simultanéité peut être parfaitement sécurisée avec des verrous, des mutex, des canaux et une isolation de la mémoire ou ce que vous avez, cela nécessite de travailler en dehors du modèle de sécurité de Rust avec unsafe, puis d'assurer manuellement au compilateur que, "Ouais, je sais ce que je fais Cela semble dangereux, mais j'ai prouvé mathématiquement que c'est parfaitement sûr. "

Mais généralement, cela revient à faire manuellement des modèles de ces choses et à prouver qu'ils sont sûrs avec des prouveurs de théorèmes . Du point de vue de l'informatique (est-ce possible) et du point de vue pratique (cela va-t-il prendre la vie de l'univers), est-il raisonnable d'imaginer un programme qui prend du code arbitraire dans un langage arbitraire et évalue s'il est " Antirouille "?

Mises en garde :

• Une solution simple à ce problème est de souligner que le programme pourrait être déstabilisant et que le problème d'arrêt nous échoue. Disons que tout programme envoyé au lecteur est garanti de s'arrêter
• Bien que "du code arbitraire dans un langage arbitraire" soit le but, je suis bien sûr conscient que cela dépend de la familiarité du programme avec le langage choisi, que nous considérerons comme une donnée

Ce dont nous parlons en fin de compte ici, c'est le temps de compilation par rapport à l'exécution.

Si vous y réfléchissez, les erreurs de temps de compilation reviennent en fin de compte à ce que le compilateur puisse déterminer les problèmes que vous rencontrez dans votre programme avant même qu'il ne soit exécuté. Ce n'est évidemment pas un compilateur "langage arbitraire", mais j'y reviendrai sous peu. Le compilateur, dans toute sa sagesse infinie, ne répertorie cependant pas tous les problèmes qui peuvent être déterminés par le compilateur. Cela dépend en partie de la qualité de l'écriture du compilateur, mais la principale raison en est que de nombreuses choses sont déterminées au moment de l' exécution .

Les erreurs d'exécution, comme vous le savez bien, je suis sûr que je le suis, sont tout type d'erreur qui se produit lors de l'exécution du programme lui-même. Cela comprend la division par zéro, les exceptions de pointeur nul, les problèmes matériels et de nombreux autres facteurs.

La nature des erreurs d'exécution signifie que vous ne pouvez pas anticiper ces erreurs au moment de la compilation. Si vous le pouviez, ils seraient presque certainement vérifiés au moment de la compilation. Si vous pouviez garantir qu'un nombre est égal à zéro au moment de la compilation, alors vous pourriez effectuer certaines conclusions logiques, telles que la division d'un nombre par ce nombre entraînera une erreur arithmétique causée par la division par zéro.

En tant que tel, d'une manière très réelle, l'ennemi de garantir par programme le bon fonctionnement d'un programme effectue des vérifications d'exécution par opposition à des vérifications de temps de compilation. Un exemple de ceci pourrait être une conversion dynamique vers un autre type. Si cela est autorisé, vous, le programmeur, êtes en train de remplacer la capacité du compilateur à savoir si c'est une chose sûre à faire. Certains langages de programmation ont décidé que cela était acceptable tandis que d'autres vous avertiraient au moins lors de la compilation.

Un autre bon exemple pourrait être d'autoriser les null à faire partie du langage, car des exceptions de pointeur null pourraient se produire si vous autorisez les null. Certains langages ont complètement éliminé ce problème en empêchant les variables non explicitement déclarées de pouvoir contenir des valeurs nulles sans être immédiatement affectées (prendre Kotlin par exemple). Bien que vous ne puissiez pas éliminer une erreur d'exécution d'exception de pointeur nul, vous pouvez l'empêcher de se produire en supprimant la nature dynamique de la langue. Dans Kotlin, vous pouvez forcer la possibilité de conserver des valeurs nulles bien sûr, mais il va sans dire qu'il s'agit d'un "acheteurs avertis" métaphoriques car vous devez le déclarer explicitement comme tel.

Pourriez-vous conceptuellement avoir un compilateur qui pourrait vérifier les erreurs dans toutes les langues? Oui, mais ce serait probablement un compilateur maladroit et très instable dans lequel vous devrez nécessairement fournir le langage en cours de compilation au préalable. Il ne pouvait pas non plus savoir beaucoup de choses sur votre programme, pas plus que les compilateurs pour des langues spécifiques ne savent certaines choses à ce sujet, comme le problème d'arrêt comme vous l'avez mentionné. Il s'avère que de nombreuses informations qui pourraient être intéressantes à connaître sur un programme sont impossibles à glaner. Cela a été prouvé, il est donc peu probable qu'il change de sitôt.

Revenons à votre point principal. Les méthodes ne sont pas automatiquement thread-safe. Il y a une raison pratique à cela, qui est que les méthodes thread-safe sont également plus lentes même lorsque les threads ne sont pas utilisés. Rust décide qu'ils peuvent éliminer les problèmes d'exécution en rendant les méthodes de threads sécurisées par défaut, et c'est leur choix. Cela a cependant un coût.

Il peut être possible de prouver mathématiquement l'exactitude d'un programme, mais ce serait avec la mise en garde que vous n'auriez littéralement aucune fonctionnalité d'exécution dans le langage. Vous pourrez lire cette langue et savoir ce qu'elle fait sans aucune surprise. La langue serait probablement de nature très mathématique, et ce n'est probablement pas une coïncidence. La deuxième mise en garde est que des erreurs d'exécution se produisent toujours , ce qui peut n'avoir rien à voir avec le programme lui-même. Par conséquent, le programme peut être prouvé correct, en supposant une série d'hypothèses sur l'ordinateur , il est en cours d' exécution sur l' exactitude et ne changent, ce qui bien sûr toujours ne se produit de toute façon et souvent.

Les systèmes de types sont des preuves automatiquement vérifiables de certains aspects de l'exactitude. Par exemple, le système de types de Rust peut prouver qu'une référence ne survit pas à l'objet référencé, ou qu'un objet référencé n'est pas modifié par un autre thread.

Mais les systèmes de types sont assez restreints:

• Ils rencontrent rapidement des problèmes de décidabilité. En particulier, le système de type lui-même devrait être décidable, mais de nombreux systèmes de type pratiques sont accidentellement Turing Complete (y compris C ++ à cause des modèles et Rust à cause des traits). De plus, certaines propriétés du programme qu'elles vérifient peuvent être indécidables dans le cas général, surtout si certains programmes s'arrêtent (ou divergent).

• De plus, les systèmes de type doivent fonctionner rapidement, idéalement en temps linéaire. Toutes les épreuves possibles ne doivent pas figurer dans le système de type. Par exemple, l'analyse d'un programme entier est généralement évitée et les preuves sont étendues à des modules ou fonctions uniques.

En raison de ces limitations, les systèmes de types ont tendance à ne vérifier que des propriétés assez faibles et faciles à prouver, par exemple qu'une fonction est appelée avec des valeurs de type correct. Pourtant, même cela limite considérablement l'expressivité, il est donc courant d'avoir des solutions de contournement (comme interface{}dans Go, dynamicen C #, Objecten Java, void*en C) ou même d'utiliser des langages qui évitent complètement le typage statique.

Plus les propriétés que nous vérifions sont fortes, moins le langage est typiquement expressif. Si vous avez écrit Rust, vous connaîtrez ces moments de «lutte avec le compilateur» où le compilateur rejette un code apparemment correct, car il n'a pas pu prouver l'exactitude. Dans certains cas, il n'est pas possible d'exprimer un certain programme dans Rust même si nous pensons pouvoir prouver son exactitude. Le unsafemécanisme en Rust ou C # vous permet d'échapper aux confins du système de type. Dans certains cas, le report des vérifications à l'exécution peut être une autre option - mais cela signifie que nous ne pouvons pas rejeter certains programmes invalides. C'est une question de définition. Un programme Rust qui panique est sûr en ce qui concerne le système de type, mais pas nécessairement du point de vue d'un programmeur ou d'un utilisateur.

Les langues sont conçues avec leur système de types. Il est rare qu'un nouveau système de type soit imposé à un langage existant (mais voir par exemple MyPy, Flow ou TypeScript). Le langage tentera de faciliter l'écriture de code conforme au système de types, par exemple en proposant des annotations de types ou en introduisant des structures de flux de contrôle faciles à prouver. Différentes langues peuvent aboutir à des solutions différentes. Par exemple, Java a le concept de finalvariables qui sont affectées exactement une fois, semblable aux non- mutvariables de Rust :

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

Java a des règles système de type pour déterminer si tous les chemins affectent la variable ou terminent la fonction avant que la variable ne soit accessible. En revanche, Rust simplifie cette preuve en n'ayant pas de variables déclarées mais non conçues, mais vous permet de renvoyer des valeurs à partir des instructions de flux de contrôle:

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

Cela ressemble à un point vraiment mineur lors de la détermination de l'affectation, mais la portée claire est extrêmement importante pour les preuves liées à la vie.

Si nous devions appliquer un système de type Rust à Java, nous aurions des problèmes bien plus importants que cela: les objets Java ne sont pas annotés avec des durées de vie, nous devrions donc les traiter comme &'static SomeClassou Arc<dyn SomeClass>. Cela affaiblirait les preuves qui en résulteraient. Java n'a pas non plus de concept d'immuabilité au niveau du type, nous ne pouvons donc pas faire de distinction entre les types &et &mut. Nous devrions traiter tout objet comme une cellule ou un mutex, bien que cela puisse supposer des garanties plus fortes que celles que Java offre réellement (la modification d'un champ Java n'est pas threadsafe à moins d'être synchronisée et volatile). Enfin, Rust n'a aucun concept d'héritage d'implémentation de style Java.

TL; DR: les systèmes de type sont des prouveurs de théorèmes. Mais ils sont limités par des problèmes de décidabilité et des problèmes de performances. Vous ne pouvez pas simplement prendre un système de types et l'appliquer à un autre langage, car la syntaxe du langage de la cible peut ne pas fournir les informations nécessaires et parce que la sémantique peut être incompatible.

Dans quelle mesure est-il sûr?

Oui, il est presque possible d'écrire un tel vérificateur: votre programme n'a qu'à retourner la constante UNSAFE. Vous aurez raison 99% du temps

Parce que même si vous exécutez un programme Rust sûr, quelqu'un peut toujours retirer le plug pendant son exécution: votre programme peut donc s'arrêter même s'il n'est théoriquement pas supposé le faire.

Et même si votre serveur s'exécute dans une cage faraday dans un bunker, un processus voisin peut exécuter un exploit de marteau et faire un peu basculer dans l'un de votre programme Rust soi-disant sûr.

Ce que j'essaie de dire, c'est que votre logiciel fonctionnera dans un environnement non déterministe et de nombreux facteurs extérieurs pourraient influencer l'exécution.

Blague à part, vérification automatisée

Il existe déjà des analyseurs de code statiques qui peuvent repérer des constructions de programmation risquées (variables non initialisées, débordements de buffer, etc ...). Ceux-ci fonctionnent en créant un graphique de votre programme et en analysant la propagation des contraintes (types, plages de valeurs, séquençage).

Ce type d'analyse est d'ailleurs également effectué par certains compilateurs dans un souci d'optimisation.

Il est certainement possible d'aller plus loin, d'analyser également la concurrence et de faire des déductions sur la propagation des contraintes sur plusieurs threads, la synchronisation et les conditions de course. Cependant, très rapidement, vous rencontreriez le problème de l'explosion combinatoire entre les chemins d'exécution et de nombreuses inconnues (E / S, planification du système d'exploitation, entrée utilisateur, comportement des programmes externes, interruptions, etc.) qui dilueront les contraintes connues à leur strict minimum. minimum et il est très difficile de tirer des conclusions automatisées utiles sur le code arbitraire.

Turing a abordé cette question en 1936 avec son article sur le problème de l'arrêt. L'un des résultats est que, juste qu'il est impossible d'écrire un algorithme que 100% du temps peut analyser le code et déterminer correctement s'il s'arrêtera ou non, il est impossible d'écrire un algorithme qui peut 100% du temps correctement déterminer si le code a une propriété particulière ou non, y compris la «sécurité» comme vous le souhaitez.

Cependant, le résultat de Turing n'exclut pas la possibilité d'un programme qui peut 100% du temps soit (1) déterminer absolument que le code est sûr, (2) absolument déterminer que le code est dangereux, ou (3) lever les mains anthropomorphiquement et dire "Zut, je ne sais pas.". Le compilateur de Rust, en général, est dans cette catégorie.

Si un programme est total (le nom technique d'un programme dont l'arrêt est garanti), il est théoriquement possible de prouver toute propriété arbitraire sur le programme avec suffisamment de ressources. Vous pouvez simplement explorer chaque état potentiel dans lequel le programme pourrait entrer et vérifier si l'un d'entre eux viole votre propriété. Le langage de vérification de modèle TLA + utilise une variante de cette approche, utilisant la théorie des ensembles pour comparer vos propriétés par rapport à des ensembles d'états de programme potentiels, plutôt que de calculer tous les états.

Techniquement, tout programme exécuté sur un matériel physique pratique est soit total, soit une boucle prouvable car vous ne disposez que d'une quantité limitée de stockage, il n'y a donc qu'un nombre fini d'états dans lesquels l'ordinateur peut se trouver. l'ordinateur est en fait une machine à états finis, pas Turing complète, mais l'espace d'état est si grand qu'il est plus facile de prétendre qu'ils tournent à leur terme).

Le problème avec cette approche est qu'elle a une complexité exponentielle à la quantité de stockage et à la taille du programme, le rendant impraticable pour autre chose que le cœur des algorithmes, et impossible à appliquer à des bases de code importantes dans leur intégralité.

La grande majorité des recherches se concentre donc sur les preuves. La correspondance de Curry-Howard déclare qu'une preuve de correction et un système de types sont une seule et même chose, donc la plupart des recherches pratiques vont sous le nom de systèmes de types. Coq et Idriss sont particulièrement pertinents pour cette discussion., en plus de Rust que vous avez déjà mentionné. Coq aborde le problème d'ingénierie sous-jacent dans l'autre sens. Prenant une preuve d'exactitude de code arbitraire dans le langage Coq, il peut générer du code qui exécute le programme éprouvé. Idriss utilise quant à lui un système de type dépendant pour prouver le code arbitraire dans un langage purement Haskell. Ce que ces deux langages font, c'est pousser les problèmes difficiles de générer une preuve exploitable sur le rédacteur, permettant au vérificateur de type de se concentrer sur la vérification de la preuve. La vérification de la preuve est un problème beaucoup plus simple, mais cela rend les langues beaucoup plus difficiles à travailler.

Ces deux langages ont été spécifiquement conçus pour faciliter les épreuves, en utilisant la pureté pour contrôler quel état est pertinent pour quelles parties du programme. Pour de nombreuses langues traditionnelles, la simple preuve qu'un élément de l'État n'est pas pertinent pour une preuve d'une partie du programme peut être un problème complexe en raison de la nature des effets secondaires et des valeurs modifiables.