Les techniques de vérification des programmes pourraient-elles empêcher les bogues du genre Heartbleed de se produire?

9

Concernant le bug Heartbleed, Bruce Schneier écrivait dans son Crypto-Gram du 15 avril: «Catastrophique» est le bon mot. Sur une échelle de 1 à 10, il s'agit d'un 11. » J'ai lu il y a plusieurs années qu'un noyau d'un certain système d'exploitation a été rigoureusement vérifié avec un système de vérification de programme moderne. Pourrait donc empêcher les bugs du genre Heartbleed de se produire via l'application des techniques de vérification de programme aujourd'hui ou est-ce encore irréaliste ou même principalement impossible?

cryptography correctness-proof security software-verification program-correctness Mok-Kong Shen
la source
2
Here is an interesting analysis of this question by J. Regehr.
Martin Berger

Réponses:

6

To answer your question in the most concise way - yes, this bug could have potentially been caught by formal verification tools. Indeed, the property "never send a block which is bigger than the size of the hearbeat that was sent" is fairly simple to formalize in most specification languages (e.g. LTL).

The problem (which is a common criticism against formal methods) is that the specifications you use are written by humans. Indeed, formal methods only shift the bug-hunting challenge from finding the bugs to defining what bugs are. This is a difficult task.

Also, formally verifying software is notoriously difficult due to the state-explosion problem. In this case, it is especially relevant, since many times in order to avoid the state explosion, we abstract away bounds. For example, when we want to say "every request is followed by a grant, within 100000 steps", we need a very long formula, so we abstract it to the formula "every request is eventually followed by a grant".

Ainsi, dans le cas ému, même en essayant de formaliser les exigences, la limite en question aurait pu être résumée, ce qui aurait entraîné le même comportement.

Pour résumer, ce bogue aurait pu être évité en utilisant des méthodes formelles, mais il aurait fallu qu'un humain spécifie cette propriété à l'avance.

Shaull
la source
5

Les vérificateurs de programmes commerciaux comme Klocwork ou Coverity ont peut-être pu trouver Heartbleed car il s'agit d'une erreur de vérification des limites relativement simple, qui est l'un des principaux problèmes pour lesquels ils sont conçus. Mais il existe un moyen beaucoup plus simple: utilisez des types de données abstraits opaques qui sont bien testés pour être exempts de dépassement de tampon.

There are a number of "safe string" abstract data types available for C programming. The one I'm most familiar with is Vstr. The author, James Antill, has a great discussion about why you need a string abstract data type with its own constructors/factory methods and also a list of other string abstract data types for C.

Logique errante
la source
2
Coverity ne trouve pas Heartbleed, voir cette analyse de John Regehr.
Martin Berger
Joli lien! Cela démontre la vraie morale de l'histoire: la vérification du programme ne peut pas compenser les abstractions mal conçues (ou inexistantes).
Wandering Logic
2
Cela dépend de ce que vous entendez par vérification du programme. Si vous parlez d'analyse statique, alors oui, c'est toujours une approximation, comme conséquence directe du théorème de Rice. Si vous vérifiez le comportement complet dans un processeur de théorème interactif, vous obtenez une garantie en fonte que le programme répond à ses spécifications, mais c'est extrêmement laborieux. Et vous êtes toujours confronté au problème que vos spécifications peuvent être erronées (voir par exemple l'explosion d'Ariane 5).
Martin Berger
1
@MartinBerger: Coverity finds it now.
Reinstate Monica - M. Schröder
4

If you count as a " program verification technique " the combination of runtime bound-checking and fuzzing, yes this particular bug could have been caught.

Proper fuzzing will cause the now infamous memcpy(bp, pl, payload); to read across the limit of the memory block pl belongs to. Runtime bound-checking can in principle catch any such access, and in practice, in this particular case, even a debug version of malloc that cares to bound-check the parameters of memcpy would have done the job (no need to mess with the MMU here). Problem is, performing fuzzing tests on each kind of network packet takes effort.

fgrieu
la source
1
While true in general, IIRC, in OpenSSL's case the authors implemented their own internal memory management such that it was much less likely for memcpy to hit the true boundary of the (large) region originally requested from the system malloc.
William Price
Oui, dans le cas d'OpenSSL tel qu'il était au moment du bogue, memcpy(bp, pl, payload)aurait dû vérifier les limites utilisées par le mallocremplacement d'OpenSSL , pas le système malloc. Cela exclut la vérification automatisée des limites au niveau binaire (au moins sans connaissance approfondie du mallocremplacement). Il doit y avoir une recompilation avec la magie au niveau de la source en utilisant par exemple des macros C remplaçant le jeton mallocou tout autre remplacement utilisé par OpenSSL; et il semble que nous ayons besoin de la même chose, memcpysauf avec des astuces MMU très intelligentes.
fgrieu
4

Using a tighter language doesn't just move goal posts around from getting implementation correct to getting the spec right. It is hard to make something that is very wrong yet consistent logically; which is why compilers catch so many bugs.

Pointer Arithmetic as it is normally formulated is unsound because the type system doesn't actually mean what it is supposed to mean. You can avoid this problem completely by working in a garbage collected language (the normal approach that makes you also pay for abstraction). Or you can be much more specific about what kinds of pointers you are using, so that the compiler can reject anything that is inconsistent or just can't be proven correct as written. This is the approach of some languages like Rust.

Les types construits sont équivalents aux preuves, donc si vous écrivez un système de types qui oublie cela, alors toutes sortes de choses tournent mal. Supposons un instant que lorsque nous déclarons un type, nous voulons en fait dire que nous affirmons la vérité sur ce qui est dans la variable.

  • int * x; // Une fausse affirmation. x existe et ne pointe pas vers un int
  • int * y = z; // Uniquement vrai s'il est prouvé que z pointe vers un int
  • * (x + 3) = 5; // Seulement vrai si (x + 3) pointe vers un int dans le même tableau que x
  • int c = a / b; // Uniquement vrai si b n'est pas nul, comme: "non nul int b = ...;"
  • nullable int * z = NULL; // nullable int * n'est pas la même chose qu'un int *
  • int d = * z; // Une fausse assertion, car z est nullable
  • if (z! = NULL) {int * e = z; } // Ok car z n'est pas nul
  • gratuit (y); int w = * y; // Fausse affirmation, car y n'existe plus à w

Dans ce monde, les pointeurs ne peuvent pas être nuls. Les déréférences NullPointer n'existent pas et les pointeurs n'ont pas besoin d'être vérifiés pour la nullité n'importe où. Au lieu de cela, un "nullable int *" est un type différent qui peut avoir sa valeur extraite à null ou à un pointeur. Cela signifie qu'au point où l' hypothèse non nulle commence, vous allez enregistrer votre exception ou descendre une branche nulle.

Dans ce monde, les erreurs de tableau hors limites n'existent pas non plus. Si le compilateur ne peut pas prouver qu'il est dans des limites, essayez de réécrire pour que le compilateur puisse le prouver. Si ce n'est pas le cas, vous devrez alors introduire manuellement l'Assomption à cet endroit; le compilateur peut y trouver une contradiction ultérieurement.

De plus, si vous ne pouvez pas avoir de pointeur qui n'est pas initialisé, vous n'aurez pas de pointeurs vers la mémoire non initialisée. Si vous avez un pointeur sur la mémoire libérée, il doit être rejeté par le compilateur. Dans Rust, il existe différents types de pointeurs pour rendre ces types de preuves raisonnables. Il existe des pointeurs appartenant exclusivement (c'est-à-dire: pas d'alias), des pointeurs vers des structures profondément immuables. Le type de stockage par défaut est immuable, etc.

Il y a aussi le problème de l'application d'une grammaire bien définie sur les protocoles (qui inclut les membres de l'interface), pour limiter la surface d'entrée exactement à ce qui est prévu. La chose à propos de "l'exactitude" est: 1) Débarrassez-vous de tous les états indéfinis 2) Assurez la cohérence logique . La difficulté d'y arriver a beaucoup à voir avec l'utilisation d'un outillage extrêmement mauvais (du point de vue de l'exactitude).

C'est exactement pourquoi les deux pires pratiques sont les variables globales et les gotos. Ces choses empêchent de mettre des conditions pré / post / invariantes autour de quoi que ce soit. C'est aussi pourquoi les types sont si efficaces. Au fur et à mesure que les types se renforcent (en utilisant finalement les types dépendants pour prendre en compte la valeur réelle), ils se rapprochent d'être des preuves de correction constructives en elles-mêmes; faire échouer la compilation des programmes incohérents.

Gardez à l'esprit qu'il ne s'agit pas seulement d'erreurs stupides. Il s'agit également de défendre la base de code contre les infiltrés intelligents. Il y aura des cas où vous devrez rejeter une soumission sans une preuve convaincante générée par la machine de propriétés importantes comme "suit le protocole formellement spécifié".

Rob
la source
1

la vérification logicielle automatisée / formelle est utile et peut aider dans certains cas, mais comme d'autres l'ont souligné, ce n'est pas une solution miracle. on pourrait souligner qu'OpenSSL est vulnérable en ce que son open source et pourtant utilisé commercialement et à l'échelle de l'industrie, largement utilisé et non fortement évalué par les pairs avant la sortie (on se demande s'il y a même des développeurs rémunérés sur le projet). le défaut a été découvert essentiellement lors de la révision du code après la publication, et le code a apparemment été révisé avant la publication (notez qu'il n'y a probablement aucun moyen de suivre qui a effectué la révision du code interne). le «moment propice à l'apprentissage» avec heartbleed (parmi beaucoup d'autres) est fondamentalement une meilleure révision de code, idéalement avant la sortie, en particulier de code très sensible, peut-être mieux suivi. peut-être qu'OpenSSL fera maintenant l'objet d'un examen plus approfondi.

plus de bkg des médias détaillant ses origines:

vzn
la source