[Atom] [Mail] [Twitter]
Liens : C · git · hacks · divers · cabale · à propos +
Au menu
\/

Compile-time conditionals and unique constants using C11 _Generic

#. Par rz0. Mis à jour le 16.05 2012 à 18:58. Aucun commentaire.
c c11 c99 generic preprocessor

About a month ago, I started playing around with the new C standard, namely C11, and its new features. While I have always been fond of some of them, such as explicit alignment support, others never really caught my interest. One of those not-so-interesting additions was the new _Generic construct, which allows rather limited ad-hoc compile-time type-based dispatching. While I reckon it was necessary in order to support the <tgmath.h> header in a meaningful way, as well as, perhaps, the growing number of integral types, I’d never seen it as anything more than that: an implementor’s device given standard blessing.

Well, that was until a few days ago. While experimenting with a macro of mine, I tried to improve it by using C11 features, and, in doing so, stumbled upon a rather less boring use of _Generic: compile-time "type-level" constants, and conditional compilation based on it! (Well, maybe it sounds obvious to some of you; for the rest, please read on!)

The basics of _Generic constants

Usually, symbolic constants are some arbitrary literal cast to an appropriate type, like this:

#define MY_MAGIC_PONY ((pony_t)-1)

This works for integer and floating point values, but is not guaranteed by the standard to work for pointers (except for 0, which yields a null pointer constant). You might want to try anyway, or you may take the address of some private dummy object instead.

#define MY_MAGIC_PONY (&my_magic_pony_)
extern struct pony my_magic_pony_;

Well, the bad news is that if you need that constant at run time, there’s not much I can do for you; you’ll have to keep using that. On the bright side, if the constant is only needed at compile time (e.g. if it is always generated by some macro, to induce a specific path in a conditional), there may be hope still.

With _Generic, you can now specify conditions based on types, which means, you can use dummy types instead of dummy values for your symbolic compile-time-only constants:

#define MY_MAGIC_PONY ((struct dummy_magic_pony *)NULL)
struct dummy_magic_pony;

#define MY_MAGIC_MACRO(..., p, ...)                   \
        ... _Generic((p),                             \
            struct dummy_magic_pony *: ...,           \
            default: ...) ...

OK, so what does this bring us? Well, three things:

  • We don’t need to create random objects for pointer constants.
  • We don’t need to set aside a special value.
  • And we don’t need to rely on the compiler eliminating spurious dead branches everywhere because of macro expansion.

Sample application 1: default arguments

So, we’ve seen how it’s done; sounds trivial, looks trivial, but what can we use it for? If this were just for me, I’d say "it comes in handy when you write complex macros sometimes", but I tried to come up with a simple enough example for this short article: default arguments. In case you may be wondering, though, this is for demonstration purposes only; don’t try this at home… well, what I mean is that probably nobody is going to use this, which is totally fine.

Anyway, while it is well-known(?) that default arguments were possible in C99 using preprocessor hacks, all solutions I’ve seen were rather cumbersome to implement (you’re welcome to prove me wrong; I haven’t tried too hard to look for the nicest way).

Probably the most usable solution comes with free keyword arguments (called named parameters, in some languages, as well) as a bonus. Just use a structure as your last parameter and stuff it with a compound literal. The disadvantage is that your defaults are all zeros (or whatever default initializer you get for the field type)… unless you name all of your arguments and include defaults in the compound literal; but that’s not what we’re aiming for here: we’re looking for plain old optional positional parameters.

You could also count the number of arguments in the variable argument list of a macro, but this requires a lot of boilerplate to define a version for each possible number of arguments.

Lastly, you could use arbitrary symbols and test for equality using preprocessor logic (for those who don’t know, it is possible with the standard C99 preprocessor to macro-branch on whether a given argument is equal to a few different things… it just requires quite a lot of work in the background and has some limitations as well — read the sources of any heavyweight preprocessor library and you’ll see; e.g. the one provided with COS). However, this has some quirks (which are outside of the scope of this article) and is definitely not for the casual preprocessor user. But the overall design is rather appealing, so we’ll keep with that except…

We can now use _Generic type constants instead of symbols. Let’s look at some code:

/* Generic definitions, for all functions thereafter. */
struct dflarg_;
#define DFLARG ((struct dflarg_ *)NULL)
#define IFDFL(arg, dflval)                                    \
        _Generic((arg),                                       \
            struct dflarg_ *: dflval,                         \
            default: (arg))

/*
 * Some function foobar with two optional arguments.
 * We take the second (non-optional) argument as part of
 * __VA_ARGS__ so the list is never empty.
 */
int foobar(int, int, int, int);
#define foobar(x, ...)                                        \
        foobar_((x), __VA_ARGS__, DFLARG, DFLARG)
#define foobar_(x, y, z, t, ...)                              \
        (foobar)((x), (y), IFDFL((z), 42), IFDFL((t), 36))

And here you go! Default arguments in C11 using _Generic.

Sample application 2: argument list length check

In our previous example, you’ve probably noticed that foobar now accepts extra arguments, which is not exactly ideal. More generally, it happens quite often with variadic macros (in my experience, especially "helper" macros that tend to be buried under more user-friendly ones, and that may need to handle the results of concatenating, splitting, mapping, and other operations on previous argument lists) that there’s a limit to how many arguments you actually want to handle.

Again, it is possible with the C99 preprocessor to check for the argument list length, but this typically involves even more heavy preprocessor logic than before, as you’ll want to do arithmetic with the preprocessor. There are ways to avoid the arithmetics, but as far as I know, they all require quite a bit of preprocessor metaprogramming in their own right.

With C11 and _Generic, however, you could just use a type-level constant… how? This is really just more of the above (well, it is the same trick, after all):

/* Our end-of-list marker is really just another default. */
#define EOARGS DFLARG
#define ISEOARGS(arg)                                         \
        _Generic((arg),                                       \
            struct dflarg_ *: true,                           \
            default: false)

#define foobar(x, ...)                                        \
        foobar_((x), __VA_ARGS__, DFLARG, DFLARG, EOARGS)
#define foobar_(x, y, z, t, eoargs, ...)                      \
        (_Static_assert(ISEOARGS(eoargs),                     \
            "too many arguments to foobar"),                  \
        (foobar)((x), (y), IFDFL((z), 42), IFDFL((t), 36)))

If you try this code… it should fail. That is because _Static_assert is a declaration according to the C11 grammar. This can be worked around by wrapping the _Static_assert in an inline structure declaration within a compound literal, like so:

#define inline_static_assert(x, s)                            \
        ((void)(const struct { int _unused;                   \
            _Static_assert((x), s); }){ 0 })

Unfortunately, this (supposedly corrected) code does not compile with Clang 3.0. Otherwise, we’d get the following final macro for foobar_:

#define foobar_(x, y, z, t, eoargs, ...)                      \
        (inline_static_assert(ISEOARGS(eoargs),               \
            "too many arguments to foobar"),                  \
        (foobar)((x), (y), IFDFL((z), 42), IFDFL((t), 36)))

I only have the N1570 draft so I can’t say for sure that this is correct, but my copy specifically states that a _Static_assert can occur inside a structure declaration (§ 6.7.2.1).

Hence we’re left with emulating _Static_assert, with the traditional negative array size trick, for example:

#define inline_static_assert(x, s)                            \
        ((void)(char * [(x) ? 1 : -1]){ s })

Now, the following call will fail to compile, although with an ugly message — can’t have it all, I guess:

foobar(6, 7, 1+1, 3*4, 5/5);

Conclusion

Well, this is it. _Generic is not widely supported yet, but hopefully support will come soon enough (and in the meantime, you can use P99 if you’re so inclined), at least for people living outside of the C-hater kingdom that Visual Studio has become. And once it does, I think it will help with simplifying some preprocessor hacks that used to require a lot of added ma^Wlogic in order to branch at macro-expansion time.

[ tag:blog.huoc.org,2009:posts/conditionals-constants-c11-generic ]
Aucun commentaire · Commenter

/\ \/

À la découverte d'Emacs (Lisp) 24

#. Par rz0. Publié le 14.05 2012 à 18:46. Aucun commentaire.
elisp emacs fonctionnel libre programmation

Depuis quelques jours, j’ai décidé de migrer vers Emacs 24, la version en développement d’Emacs. Le changement s’est effectué sans trop de difficultés, une ou deux extensions mineures devenues incompatibles, quelques options de configuration qui ne font plus tout à fait ce que je veux, mais globalement, une mise à jour tout en douceur, comme d’habitude… après tout, un ancêtre comme Emacs ne doit plus tellement évoluer… si ?

Bah, en fait… non, pas vraiment ; côté fonctionnalités, Emacs 24 n’apporte rien de révolutionnaire, à vrai dire… des améliorations des modes existants : une meilleure prise en charge des gestionnaires de versions distribués, la possibilité de manipuler des fichiers 7-zip, ou encore une meilleure indentation pour certains modes de programmation, par exemple. Il faut aller chercher du côté du programmeur pour trouver les nouveautés de cette version, car il y en a ! Du moins, quelques unes qui ont retenu mon attention, et qui constituent, selon moi, tout autant de petits signes qu’Elisp mûrit encore, lentement mais sûrement, en tant que langage.

Cela ne surprendra probablement personne si je dis qu’Elisp — Emacs Lisp, le dialecte de Lisp utilisé par Emacs, n’est pas tout à fait dans l’air du temps… c’est un Lisp historique, auquel il manque toutes sortes de petits plus qui contribuent à notre confort. Bien qu’il possède des fermetures et des fonctions d’ordre supérieur, on ne peut pas dire qu’Elisp encourage vraiment un style de programmation fonctionnel, tel que ses partisans le défendent aujourd’hui… pas de portée lexicale pour les symboles, pas de types algébriques, ni de récursion terminale optimisée, bref, pas exactement idéal pour faire du fonctionnel…

Du moins, cela a toujours été le cas… jusqu’à Emacs 24. Non, non, je vous rassure, il n’y a toujours pas de typage algébrique en Elisp, mais cette version apporte son lot de changements intéressants qui font d’Elisp un langage un peu plus respectable aux yeux des vrais, des durs. Tour d’horizon des choses nouvelles et moins nouvelles.

Je profite de l’occasion pour parler un peu plus généralement d’Elisp comme langage de programmation ; j’évoque, bien évidemment, les nouveautés d’Emacs 24, mais également des choses plus générales qui pourraient intéresser les curieux, ou les non-initiés, bref, les innocents qui voudraient se lancer dans scriptage de leur Emacs.

Visite guidée : à votre droite, les fondations…

Flots de contrôle

Parmi les constructions de base du langage, rien de nouveau dans Emacs 24 (ou 23, ou 22, etc.) ; on retrouve les conditionnelles du Lisp, if (et ses variantes when et unless) et cond, ainsi qu’une simple boucle while, implémentée comme une primitive dans Elisp. Comme dit plus haut, la récursion terminale n’est pas prise en charge en temps constant, et il vaut mieux utiliser une boucle quand on peut.

Le module cl-macs apporte son lot de macros complémentaires empruntées à Common Lisp (mais utilisées dans quasiment tous les paquetages Emacs), notamment do et ses variantes (dolist et dotimes) ainsi que le tout-puissant loop (dans une forme quelque peu amoindrie).

Le problème des macros Common Lisp dans Emacs est qu’elles sont généralement très succinctement documentées, et le manuel Elisp n’en parle pas. Il faudra donc regarder ailleurs pour apprendre à s’en servir…

Variables, fonctions et fermetures

Côté variables, depuis Emacs 24, Elisp a enfin renoué avec le vingt-et-unième siècle et propose désormais des variables à portée lexicale ! À activer via un petit commentaire en haut du fichier source (il s’agit de mettre la variable lexical-binding, locale au fichier à t), celles-ci se comportent un peu comme en Common Lisp : les variables définies globalement (avec defvar) sont à portée dynamique, tandis que les constructions locales telles que let et letrec introduisent des variables lexicales.

-*- lexical-binding: t -*-
;; À mettre en première ligne de vos fichiers Elisp, avec les autres
;; variables locales au fichier.

Assez traditionnellement, les variables en Elisp sont mutables, comme en Common Lisp ou en Scheme, mais pas comme en ML. L’affectation se fait avec setq ; on trouve setf dans cl-macs, mais il n’est pas d’usage de l’employer à la place de setq.

En ce qui concerne les fonctions, il faut tout d’abord mentionner qu’Elisp est un Lisp-2, ce qui signifie que les noms de fonctions existent dans un espace différent de ceux des variables (on peut avoir une variable list et une fonction list). La déclaration au niveau global se fait par defun ; localement, on dispose des lambda-expressions avec le mot-clé lambda, qui introduit une fonction anonyme.

Les macros Common Lisp labels et flet n’ont malheureusement pas l’air d’avoir été mises à jour pour profiter de la nouvelle prise en charge de la portée lexicale, et utilisent encore l’ancienne émulation via lexical-let — en fait, il n’est pas clair si ce nouveau mécanisme de portée lexicale s’applique également aux fonctions (a priori, ce n’est pas le cas, puisque seul let expose cette nouvelle fonctionnalité, et celui-ci n’affecte pas l’espace des fonctions). Étant donné que labels et flet ne profitent pas du nouveau mécanisme de portée lexicale, la déclaration de fonctions (lexicalement) locales doit se faire préférablement par le biais de let ou letrec, comme suit :

(letrec ((fun
          (lambda (args...)
            body...)))
  body...)

Pas exactement ce que j’appellerais élégant, surtout que cela oblige à utiliser funcall pour l’appel, mais on va dire que l’on fait avec… Je m’attends à ce qu’à mesure que les programmeurs adoptent la portée lexicale, l’usage en devienne plus souple, poussant ainsi les développeurs d’Emacs à ajouter ce genre de support dans une révision future.

Structures de données

Comme tout langage de haut niveau qui se respecte, Elisp prend en charge nativement un certain nombre de structures de données, telles que :

  • les listes, bien sûr, naturellement notées (elts...) ou (elts . tail) ; avec leurs usages idiomatiques (piles, listes associatives, listes de propriétés, etc.) ;

  • mais également les vecteurs et chaînes de caractères, mutables, mais de taille constante (bien que les chaînes de caractères soient mutables, il n’est pas d’usage de les modifier directement) ; les chaînes s’écrivent entre guillemets doubles " et les vecteurs entre crochets [] ;

  • ou encore les tableaux associatifs (depuis Emacs 21), sous forme de tables de hachage, avec la syntaxe (depuis Emacs 23) #s(hash-table data (key val ...)) ou juste #s(hash-table) pour une table vide ; pas des plus jolies, m’enfin, elle est là quand on en a besoin ;

  • plus inhabituel, mais logique quand on y réfléchit, Emacs offre à ses programmeurs des buffers qui peuvent contenir plus ou moins des données quelconques, éventuellement beaucoup de données, et sont adaptés aux opérations d’édition (insertion et suppression de segments) ; il n’est pas choquant de voir les buffers utilisés un peu à tort et à travers, mais une caractéristique importante de ceux-ci est qu’ils existent en dehors du ramasse-miettes ; il faut donc penser à les éliminer explicitement quand on n’en a plus besoin (ou utiliser une macro telle que with-temp-buffer, qui fait le job pour vous) ;

  • du reste, on trouve d’autres structures spécialisées pour l’édition (tables de syntaxe, keymaps, etc.) et dont l’intérêt général est tout à fait discutable au-delà de leur fonction première ;

  • pour finir, des bibliothèques incluses par défaut dans Emacs implémentent des conteneurs supplémentaires telles que des tampons circulaires (ring) ou des arbres AVL (avl-tree).

Globalement, les ressources sont multiples et bien présentes, quoique les interfaces soient parfois un peu archaïques et pas forcément très agréables à utiliser…

Dans « Emacs Lisp », il y a « Lisp »…

Et qui dit Lisp, dit macros. Elisp a un mécanisme de macros simple mais tout à fait fonctionnel, qui ressemble un peu à celui de Common Lisp, en moins évolué. La définition se fait avec defmacro, on peut générer des symboles avec make-symbol, et les opérateurs `, ,, et ,@ sont disponibles avec leur sémantique habituelle (quasi-littéral, substitution d’éléments évalués dans un quasi-littéral, et substitution et aplatissement).

Par rapport à des systèmes plus sophistiqués, on peut remarquer, par exemple, que les macros ne peuvent être déclarées qu’avec un seul niveau de paramètres (ceux-ci peuvent bien entendu prendre n’importe quelle valeur) ; la structure interne des arguments doit être décortiquée à la main dans le code de la macro.

En pratique, les macros en Elisp sont largement utilisées ; on en voit un peu partout, tous les jours. Cependant, un détail à garder en tête lorsque l’on emploie des macros complexes : Elisp, contrairement à la plupart des implémentations de Common Lisp, ne compile pas ses fonctions au fur et à mesure, et par là j’entends que le code n’est même pas traduit en bytecode. Cela signifie que les macros seront réévaluées à chaque exécution de la fonction… une des raisons pour lesquelles la plupart des gros paquetages Emacs vous demandent de compiler avant usage. À titre d’exemple, l’utilisation des macros fournies par cl-macs ou pcase (dont nous reparlerons un peu plus loin) sont de bons indicateurs pour identifier les candidats à la compilation obligatoire…

Et le fonctionnel dans tout ça ? Et la POO ?

Après ce petit tour des fondamentaux du langage, l’heure est venue de poser la question qui fâche : c’est bien joli, tout ça, mais quels possibilités Emacs offre-t-il en termes de programmation pour les hommes (et les femmes), les vrais, qui mangent du fonctionnel au petit déjeuner (et des objets au goûter) ?

Fonctions anonymes et fonctions d’ordre supérieur

Commençons par les choses triviales : Elisp dispose de fonctions anonymes (avec lambda) et de valeurs-fonctions de première classe, ce qui rend possible les fonctions d’ordre supérieur — telles que mapcar — dont l’usage est cependant peut-être un peu moins populaire que dans d’autres dialectes de Lisp, du fait du manque de variété de tels opérateurs présents par défaut.

Avec Emacs 24 et la portée lexicale, les fermetures sont maintenant également lexicales lorsque lexical-binding est actif ; les variables globales (dites spéciales) demeurent dynamiques quoi qu’il en soit.

Comme Elisp est un Lisp-2, on ne peut pas tout simplement appeler une fermeture contenue dans une variable par son nom ; il faut utiliser funcall ou apply. Elisp offre plusieurs possibilités de traitement des arguments (par le biais des mots-clés &optional et &rest, ainsi que &key avec les extensions Common Lisp), mais la curryfication n’en fait pas partie ; on notera toutefois la présence de la fonction apply-partially qui, exactement comme son nom l’indique, retourne le résultat de l’application partielle d’une fonction à une liste (éventuellement incomplète) d’arguments.

Oh, les jolis motifs…

Les fonctions anonymes, ça ne fait pas tout ; s’il y a un truc que les fonctionnelleux comme gasche aiment bien, c’est le pattern matching, ou le filtrage par motifs, en français. C’est traditionnellement le domaine des langages de la famille ML, qui ont des types algébriques, et pas franchement le fort d’Elisp, qui a un typage dynamique assez primitif. Malgré cela, Emacs 24 introduit une petite nouveauté, sous la forme de la macro pcase. Celle-ci permet un filtrage par motifs sur les listes et les constantes, prend en charge les gardes booléennes et les affectations de variables ; que demande le peuple ? Illustration :

(pcase '(foo (0 1 2) 3)
  (`(foo ,(and `(0 1 2) xs) ,x)
   (cons x xs)))
     => (3 0 1 2)

Deux détails qui peuvent porter à confusion au départ :

  • l’utilisation des quasi-apostrophes ` qui introduisent les quasi-littéraux ; la virgule sert, comme d’habitude, à échapper à la quasi-apostrophe — dans ce contexte, « échapper » signifie revenir au format de motif général, qui permet notamment d’attacher des variables ;

  • la présence de la conjonction and dans les motifs (en plus du plus classique or) ; and est utilisée notamment pour affecter des variables à un sous-motif, comme as en Caml.

Avec pcase, on peut imaginer coder simplement un semblant d’union typée annotée avec des listes et des symboles :

;; Un arbre binaire...
(defun leaf (x) `(leaf ,x))
(defun node (left right) `(node ,left ,right))

(defun height (tree)
  (pcase tree
    (`(leaf ,_) 0)
    (`(node ,left ,right)
     (1+ (max (height left) (height right))))))

(height (node (leaf 1)
              (node (node (leaf 2)
                          (leaf 3))
                    (leaf 4))))
     => 3

Bien sûr, on pourrait se coder une petite macro pour rendre la définition de telles unions un peu moins vilaine (mais là n’est pas vraiment l’objectif de ce billet) :

(defmacro defunion (&rest alternatives)
  `(progn
     ,@(mapcar (lambda (alt)
                 `(defun ,(car alt) ,(cdr alt)
                    (list ',(car alt) ,@(cdr alt))))
               alternatives)))

(defunion
  (leaf x)
  (node left right))

Des objets, en veux-tu ? EIEIO

Pour finir sur une note rigolote, pour ceux qui souhaitent se faire du mal, Elisp dispose depuis la version 23.2 d’EIEIO, sa propre couche de compatibilité avec CLOS, le système d’objets de Common Lisp. Je n’ai jamais touché moi-même, mais il paraît que c’est assez complet. On y retrouve defclass, defgeneric et compagnie. De quoi satisfaire les envies les plus folles…

Trop chouette, je veux m’y mettre !

Si après cette petite visite guidée, vous êtes encore devant votre écran, n’avez pas régurgité votre quatre-heures, ou mieux, êtes pris d’une envie irrésistible de vous essayer à ce langage, ce ne sont pas vraiment les ressources qui manquent ; il y a un manuel Elisp (consultable avec info, C-h i). EmacsWiki a également des ressources dont l’Elisp Cookbook, pour quelques recettes de base. Alternativement, vous pouvez tout simplement vous lancer dans l’aventure en lisant et modifiant votre extension préférée ; quelque part, c’est joindre l’utile à l’apprentissage (agréable ou pas, selon les personnes). Restez raisonnable — cc-mode n’est probablement pas le meilleur choix pour commencer — et tout ira bien ! Et bienvenue dans le monde merveilleux d’Emacs !

[ tag:blog.huoc.org,2009:posts/decouverte-emacs-lisp-24 ]
Aucun commentaire · Commenter

/\ \/

Appeler Emacs depuis un navigateur, sous un Debian-like

#. Par gasche dans Administrivia. Mis à jour le 04.12 2011 à 13:29. 4 commentaires.
<. Utiliser et configurer XMonad
administration emacs firefox navigateurs

Un petit billet dans la section administrativia pour me souvenir d’une astuce qui pourra resservir.

Aujourd’hui j’ai voulu reproduire sur un ordinateur une fonctionnalité que j’ai sur le mien et qui m’arrange bien : pouvoir facilement appeler Emacs depuis un navigateur web (en l’occurence Firefox) pour remplir un champ de texte.

Je ne prétends pas faire de la façon la plus efficace ou commode possible ; n’hésitez pas à le signaler si vous pensez qu’il y a une manière plus « propre » de faire.

L’idée d’ensemble est la suivante :

  1. J’utilise l’extension It's All Text qui permet d’appeler n’importe quel éditeur pour remplir un champ de texte ; si vous n’utilisez pas Firefox, il faudra trouver une extension correspondante.

  2. Je m’arrange pour que la commande editor, gérée par update-alternatives sous Debian (et Ubuntu), appelle Emacs, en utilisant emacsclient pour qu’il s’ouvre rapidement.

La première étape est simple, et marche sous toutes les versions de Firefox que j’ai testées. La seconde est un peu plus délicate, et détaillée ci-ensuite.

Pour commencer, le système update-alternatives n’accepte qu’un nom d’exécutable, sans qu’on puisse lui passer de paramètres. C’est dommage parce que pour que emacsclient soit agréable à utiliser, il faut passer l’option -c, ou --create-frame, pour qu’il crée une nouvelle fenêtre au lieu d’aller embêter une fenêtre existante.1 Il est donc nécessaire de se créer un petit script intermédiaire, à placer où vous voulez, chez moi c’est $HOME/etc/emacs.sh :

#!/bin/sh
emacsclient --create-frame $@

1 NdRZ : Personnellement, j’aime bien ouvrir ça dans une fenêtre existante. Two cents.

Ensuite il faut convaincre update-alternatives qu’on a envie d’utiliser ce script comme alternative préférée pour le programme editor — qui existe déjà et est géré par update-alternatives sur les Debian et Ubuntu récentes ; sur la machine cible il pointait vers nano par défaut. Il faut commencer par « installer » l’alternative, puis la choisir. La syntaxe d’installation est la suivante:

sudo update-alternatives --install <link> <name> <path> <priority>

<link> désigne le chemin de l’exécutable final, ici /usr/bin/editor, <name> son nom, editor, <path> le chemin du vrai programme à exécuter, donc votre script, et <priority> un nombre arbitraire, le plus grand est choisi par défaut. Chez moi les autres programmes étaient entre -100 et 20, donc j’ai mis 20, mais de toute façon ensuite je fais un choix manuel.

sudo update-alternatives --install /usr/bin/editor editor $HOME/etc/emacs.sh 20
sudo update-alternatives --set editor $HOME/etc/emacs.sh

Vous l’aurez compris, la dernière ligne désactive le choix automatique (par les priorités) pour forcer un choix manuel. Je ne sais pas pourquoi il faut répéter deux fois ce chemin, c’est un peu mal fichu, mais c’est la vie. On peut vérifier que tout a bien marché en lui demandant ce qu’il a en base pour editor :

% update-alternatives --display editor
editor - manual mode
  link currently points to /home/gabriel/etc/emacs.sh
/bin/ed - priority -100
  slave editor.1.gz: /usr/share/man/man1/ed.1.gz
/bin/nano - priority 40
  slave editor.1.gz: /usr/share/man/man1/nano.1.gz
/home/gabriel/etc/emacs.sh - priority 10
/usr/bin/emacs23 - priority 0
  slave editor.1.gz: /usr/share/man/man1/emacs.emacs23.1.gz
/usr/bin/emacsclient - priority 10
Current 'best' version is '/bin/nano'.

J’ai retiré quelques alternatives et quelques « esclaves » pour raccourcir la sortie, mais vous voyez l’idée. Maintenant il suffit de donner /usr/bin/editor à votre extension It’s All Text, et le tour est joué.

emacsclient s’utilise en ayant lancé au moins une fois, au démarrage de votre ordinateur, la commande emacs --daemon ; elle n’ouvre pas de fenêtre emacs mais lance un serveur en fond de tâche pour les clients suivants. Vous pouvez l’ajouter à vos scripts de démarrage de session X, ou ce que vous voulez. Si vous l’oubliez, It’s All Text se plaindra poliment d’une erreur à l’ouverture de l’éditeur (code de retour -1).

Avec cette configuration, emacs est facile et rapide à ouvrir depuis Firefox, et tout marche bien. Je m’en sers pour rédiger des messages un peu longs, en particulier tout ce qui est technique ; j’utilise beaucoup les facilités d’Emacs pour taper des caractères unicodes (M-x set-input-mode,2 TeX). C’est aussi utile quand on rédige un message avec des bouts de code : on peut tester dans un buffer, et facilement ouvrir des buffers déjà ouverts depuis une autre fenêtre.

2 NdRZ : M-x set-input-mode qui s’active aussi avec la commande C-x RET C-\. Une fois sélectionné, vous pouvez basculer entre le mode choisi et le mode normal par défaut avec C-\. Si votre disposition de touches ne permet pas un accès rapide et aisé à C-\, je vous conseille de vous créer un alias de touches, vers C-4 par exemple :

(define-key key-translation-map (kbd "C-4") (kbd "C-\\"))
[ tag:blog.huoc.org,2009:posts/convenient-browser-emacs ]
Voir les commentaires · Commenter

/\ \/

Génération de tests, compilateurs, et preuve formelle

#. Par gasche dans Réactions. Publié le 19.04 2011 à 23:09. 12 commentaires.
<. Sécurité et interface utilisateur
analyse_statique bugs compilation réaction

Quand il est sorti sur Lambda the Ultimate, j’ai lu avec intérêt l’article Finding and Understanding Bugs in C Compilers (PDF, 12 pages), de Xuejun Yang, Yang Chen, Eric Eide, et John Regehr, 2011. Je compte en faire un petit résumé, mentionner quelques points de l’article qui m’ont intéressé, et surtout faire une longue digression sur un sujet très légèrement abordé par l’article mais qui m’intéresse beaucoup : les rapports entre tests de fonctionnement et preuves de correction dans le développement logiciel.

Pendant la relecture, rz0 fait des remarques sur la forme et des choses à reformuler pour améliorer l’article, mais parfois il se contente de donner simplement son avis. J’ai décidé de garder ses remarques dans le texte, au lieu de me contenter de les lire pour moi et, si l’inspiration vient, d’y répondre par mail.

Le cœur de l’article

L’idée de base est de générer aléatoirement des programmes C, pour trouver des bugs dans les compilateurs. L’efficacité de la technique repose sur deux bonnes idées, une déjà connue et une nouvelle.

Concrètement, générer des programmes aléatoires permet de repérer les plantages (le compilateur lance une exception au lieu de produire un résultat), mais si le compilateur produit du code, comment savoir s’il est correct ? Alors déjà, il faut bien comprendre qu’on ne regarde pas directement le programme assembleur produit pour savoir s’il est correct ; cela demanderait de savoir raisonner sur du code assembleur quelconque, ce qui est bien trop compliqué. Non, on exécute le programme généré, et on regarde le résultat de l’exécution (donc le résultat du résultat du générateur de programmes…).

Que peut-on déduire du résultat de cette exécution ? D’habitude, on génère des tests dont on connaît le résultat (« l’exécution de ce programme va afficher 3 »), mais là on ne sait pas forcément prévoir le résultat correct à partir du programme C généré (pour cela, il faudrait dans le cas général avoir à disposition un compilateur C sans bugs…). C’est là qu’entre en jeu la première idée : on va comparer les sorties des différents compilateurs (GCC, Clang/LLVM, ICC, MSVC…), et supposer l’existence d’un bug quand ils se contredisent. Comme ça, on n’a pas besoin d’un « oracle » qui connaît la bonne réponse. C’est le principe des « tests différentiels » (differential testing).

Mais ce n’est pas aussi simple qu’il y paraît. Dans un grand nombre de cas, quand le programme en entrée n’est pas un « bon » programme, la norme ne définit pas uniquement le comportement que les compilateurs doivent adopter. Par exemple, si le programme commet une erreur grave comme une divison par 0 ou un accès hors d’un tableau, les compilateurs sont autorisés à produire un programme qui fait n’importe quoi (undefined behavior). Dans d’autres cas, il y a plusieurs choix possibles, comme par exemple pour l’ordre d’évaluation, et la norme ne tranche pas entre les différentes possibilités, elle laisse cet aspect non spécifié (unspecified behavior). Les auteurs de l’article ont recensé, dans la norme C99, 191 situations de undefined behavior et 52 cas de unspecified behavior. Si on prend un code C qui contient de tels comportements mal définis, deux compilateurs peuvent produire des résultats différents et être tout de même corrects, puisqu’ils respectent la norme.

La deuxième bonne idée de l’article est alors de vérifier que les programmes générés ne contiennent pas de comportement mal déterminé. Pour cela, ils utilisent une combinaison d’analyse statique du programme et des tests à l’exécution.

Les tests n’utilisent pas toutes les fonctionnalités du langage C, mais seulement un sous-ensemble raisonnable du langage pour lequel ils ont su mettre ces analyses au point. Ils ont sorti le grand jeu : data flow analysis pour déterminer le comportement des pointeurs, typage (qui prend en compte const et volatile), analyses d’effets… Il faut choisir des analyses qui rejettent tous les programmes mal définis ; mais elles rejettent alors nécessairement, on ne peut pas tout avoir dans la vie, certains programmes bien définis. Plus l’analyse est fine, moins elle rejette de programmes corrects, plus ils génèrent des tests compliqués et plus ils trouvent de bugs.

En pratique, ça marche bien : ils ont trouvé « des centaines de bugs » dans les compilateurs testés, dont 79 dans GCC et 202 dans LLVM ; certains des bugs trouvés sont détaillés dans l’article. Ces derniers correspondent en général à des optimisations trop aggressives des compilateurs, qui négligent certains cas et changent la sémantique, ou parfois à des erreurs d’implémentation dans le code de l’optimisation.

Quelques points de détail

Leur outil s’est révélé plus efficace quand il génère de gros programmes : « the largest number of bugs is found at a surprisingly large program size: about 81 KB ». Il n’y a pas de méthode complètement automatique pour réduire un programme-test en un programme plus petit qui préserve le bug sans introduire de comportement mal spécifié ; ils ont dû faire ça à la main. Ça pourrait s’automatiser, mais c’est sans doute un problème aussi difficile que la génération initiale de tests corrects.

Ils profitent de leur article pour critiquer gentiment certaines méthodologies de test, en particulier la métrique de couverture de code (code coverage). C’est une pratique très répandue dans l’industrie du test (et utilisée comme critère par exemple par les autorités de certification de code critique), qui consiste à utiliser un jeu de tests tel que chaque instruction du programme est exécutée au moins une fois (c’est le critère instruction coverage ; il y a d’autres critères de couverture, cf. Wikipédia) ; le terme « couverture » désigne ici la proportion du code du programme qui est exécuté au moins une fois par la batterie de tests. Ils montrent que leurs tests générés aléatoirement n’améliorent pas la couverture obtenue par les batteries de tests déjà existantes des compilateurs, c’est-à-dire qu’ils ont trouvé plein de bugs sans améliorer la couverture.

Enfin, ils ont même évalué le « retour sur investissement » de leur méthode : ils ont additionné les salaires de tous les chercheurs et étudiants qui ont travaillé sur cette méthode, le coût de l’équipement, de l’administration, etc., et obtenu un « coût » de $1000 par bug. Visiblement c’est considéré comme très rentable dans cette industrie (on imagine que les bugs dans les compilateurs peuvent être critiques et très difficiles à trouver) ; et maintenant que les outils sont développés, ils peuvent être utilisés à bien moindre coût.

Je suis quand même étonné de la quantité de bugs qui persistent dans ces compilateurs utilisés industriellement. Il ne s’agit pas de nouvelles fonctionnalités C99 qui viennent d’être implémentées (leur outil ne les prend pas en compte) mais de comportements bizarres sur un overflow dans une optimisation arithmétique, le genre de chose qu’on teste depuis des années. Pour la petite touche historique, ils mentionnent la longue histoire des tests par génération aléatoire de programme, qui a commencé en 1962 sur des compilateurs COBOL.

Remarque de rz0 :

Ça m’étonne pas, en vrai ; je pense que la plupart des programmes tendent à se cantonner à une partie plutôt bien huilée du langage et c’est ça qu’on teste bien. D’autre part, les programmes ont eux-mêmes des bugs, et en général, on n’accuse pas le compilo, du coup, il peut persister des problèmes que les gens workaround plutôt que de passer des heures à fouiller dans les normes et les forums pour savoir si c’est effectivement légal, pas légal, bien, mal défini, etc. La norme est sujette à interprétation, comme tu le sais, et sans être spécialiste, c’est très dur de savoir si ce que tu fais est légitime ou pas, et c’est nettement plus rentable de contourner le problème…

Le point le plus difficile de leur travail est la conception de ces analyses qui évitent les comportements mal définis et leur intégration dans le générateur de programmes. On peut se demander si cette difficulté est inhérente au langage C, et s’il faut prendre cet aspect en compte lors de la conception d’un langage de programmation : définir une sémantique déterministe rend le compilateur plus facile à tester. Sur la discussion de Lambda the Ultimate, un membre indique que les générateurs aléatoires de programme ont été très utiles pour les implémentations du langage Common Lisp ; est-ce lié à un plus petit nombre de comportement mal définis dans ce langage ?

Pour ma part, l’idée qu’un programme puisse se mettre à faire absolument n’importe quoi en cas d’erreur me semble désastreuse, mais je suis plutôt favorable à certains unspecified behavior, comme par exemple le fait de ne pas spécifier l’ordre d’évaluation des arguments d’une fonction, pour décourager les programmeurs d’écrire du mauvais code qui reposerait sur cet ordre. Mais des gens plus expérimentés que moi ne sont pas d’accord ; je crois que certains des concepteurs de Caml, par exemple, considèrent comme une erreur le fait de ne pas avoir fixé un ordre d’évaluation. La question n’est pas tranchée.

Remarque de rz0 :

C’est pas exactement dans le sujet, mais en fait, je pense qu’il faut mitiger cet aspect « comportement mal défini », parce qu’au final, du point de vue de l’implémenteur, il y a un choix à faire, et ce choix est rarement « on fait n’importe quoi ». Ce que je veux dire par là, c’est que l’implémenteur restreint fortement le nombre de comportements vraiment « désastreux », comme tu dis, et surspécifie le langage qu’il va prendre en charge, par rapport à la norme. Par exemple, Clang compile vers de l’assembleur intermédiaire LLVM, qui a des types entiers fixés (i8, i16, i32, etc.) avec une représentation prédéterminées (complément à deux) et des opérations arithmétiques bien définies dans tous les cas. Donc le fait que le langage C lui-même ne spécifie pas toutes ces choses-là ne devrait pas du tout affecter la qualité de l’implémentation.

CompCert, tests et preuves de correction

L’article mentionne le compilateur CompCert, un compilateur prouvé correct écrit en Coq. Je ne suis pas tout à fait d’accord avec le traitement qui en est fait, et je voudrais développer un peu ce point.

The striking thing about our CompCert results is that the middle- end bugs we found in all other compilers are absent. As of early 2011, the under-development version of CompCert is the only compiler we have tested for which Csmith cannot find wrong-code errors. This is not for lack of trying: we have devoted about six CPU-years to the task. The apparent unbreakability of CompCert supports a strong argument that developing compiler optimizations within a proof framework, where safety checks are explicit and machine-checked, has tangible benefits for compiler users.

Aucun bug trouvé dans un compilateur certifié. C’est normal, mais vous étiez quand même un peu inquiets, non ? Il se trouve qu’ils ont en fait trouvé des bugs, avant « early 2011 », dans le front-end de Coq, qui utilise CIL, une bibliothèque externe codée en OCaml qui parse le code C et lui applique quelques transformations. Cette bibliothèque non vérifiée semble effectivement contenir quelques bugs. Depuis, Xavier Leroy a réécrit cette partie de CompCert pour rétrécir la partie non-prouvée ; mais il en reste un peu, car pour l’instant on ne sait même pas vraiment comment spécifier un parseur (décrire formellement son comportement).

Les auteurs du présent article concluent en substance : bon, la vérification c’est très sympa et ça enlève plein de bugs, mais ça reste complémentaire au test, parce qu’il y a toujours des petits détails qui coincent. On se souvient de la célèbre phrase de Knuth : « Beware of bugs in the above code ; I have only proved it correct, not tried it. » Mais fondamentalement, ils ne semblent pas vraiment convaincus ; ils font aussi remarquer, à juste titre, qu’on est encore loin d’avoir un compilateur certifié pour un langage aussi délirant que C++0X (la prochaine norme du langage C++, en cours de finalisation ces mois-ci).

Cette attitude sceptique par défaut se retrouve aussi chez les autorités de certification de logiciel critique. Les gens qui travaillent là-bas sont chargés d’expertiser du logiciel pour vérifier son respect de normes de qualité très strictes, permettant ensuite l’utilisation dans les avions, voitures, centrales nucléaires, etc. Les expertises consistent essentiellement à analyser le code et les tests qui l’accompagnent mais aussi le processus de conception, la documentation produite, etc. Il y a des critères de tests divers ; l’idée n’est même pas vraiment de vérifier que les tests passent correctement (c’est une évidence), mais que leur présence montre l’existence d’une démarche qualité appropriée chez les gens qui ont écrit le code.

Ces autorités de certification n’ont pas d’expérience en vérification formelle : les outils d’analyse de programme sont déjà utilisés dans l’industrie pour trouver des erreurs, mais jusqu’à présent aucun programme n’était entièrement certifié. Les outils formels prouvaient par exemple l’absence d’overflow, mais pas un lien entre le code et une spécification. L’idée commence à germer et des questions se posent : quel degré de confiance accorder à un programme prouvé en Coq ? Une preuve remplace-t-elle la construction des jeux de tests (processus qui a sa part de coûts et de lourdeurs) ? Il y a un début de débat, mais la question est loin d’être tranchée, et ce sont des milieux évidemment assez conservateurs.

À l’opposé, j’ai rencontré des utilisateurs de Coq pour qui la réponse était claire : quand un programme est « prouvé en Coq », il ne peut évidemment pas contenir d’erreur, et il est inutile de le tester. Pour eux, le test est une méthode peu coûteuse (il est facile d’écrire un test) mais peu fiable (un test qui passe ne garantit en rien l’absence de bugs) de prendre confiance en la correction d’un logiciel, et la preuve formelle est une méthode coûteuse (il est très difficile d’écrire une preuve complète) mais absolument fiable.

Ce point de vue est malheureusement un leurre ; ce n’est pas un idéal qu’on veut atteindre un jour et pour lequel on fait des progrès, c’est tout simplement un état qui ne pourra jamais exister. La preuve formelle permet de s’assurer que tel théorème (théorème qui mentionne le programme que l’on veut vérifier) est absolument, mathématiquement juste. Mais le théorème peut être une trivialité qui dit « le programme marche, ou bien le programme ne marche pas ». Quand on a une preuve d’un théorème vérifiée par ordinateur, on est sûr que la preuve est juste, mais il faut toujours vérifier que le théorème est bien celui que l’on croit. On aurait très bien pu se tromper dans sa formulation (et c’est déjà arrivé en pratique), même si le fait d’écrire une preuve permet la plupart du temps de détecter des incohérences dans l’énoncé.

Je pense donc que l’idée de tester un programme prouvé n’est pas la bonne approche, et que les six ans de CPU n’ont pas été très utiles. On devrait plutôt essayer de tester la spécification établie par la preuve, l’énoncé du théorème de correction. Qu’est-ce que ça veut dire, tester une formule mathématique ? Je ne sais pas exactement, mais j’ai quelques idées. Par exemple, on pourrait montrer à la main qu’un système simple et faux ne vérifie pas cette spécification. On a inversé la situation : au lieu de tester le programme en disant « telle entrée est acceptée par le programme comme prévu », on teste la spécification en disant « la spécification rejette tel programme comme prévu ».

Bref, je pense que oui, il faut continuer à « tester » un programme prouvé correct, mais qu’on ne le teste pas de la même façon. En substance, prouver un programme revient à réduire sa « surface de confiance » : au lieu de devoir mettre en doute l’ensemble du programme (lire le code et se convaincre qu’il fait bien ce qu’on pense), on doit ausculter sa spécification qui est, espère-t-on, plus abstraite, plus simple et plus concise. Mais la possibilité d’erreur est toujours là, et elle ne disparaîtra jamais : il y aura toujours un gouffre entre la description mécanique du programme donnée à l’ordinateur et l’idée informelle que s’en font ses concepteurs et utilisateurs ; ce sont deux mondes différents.

Une force de la preuve formelle que je n’ai pas mentionnée est son aspect progressif. On peut commencer par ne rien montrer du tout sur un programme, puis prouver qu’il vérifie telle propriété plus ou moins simple (par exemple qu’il termine sur toutes les entrées bien formées), puis une autre propriété un peu plus subtile. Par exemple, pour un programme qui renvoie les racines d’un polynôme, on peut commencer par montrer que tous les résultats renvoyés sont bien des racines, car c’est nettement plus facile que de montrer que toutes les racines sont bien renvoyées. Petit à petit, on peut progresser vers la preuve de correction « totale » où la spécification décrit exactement ce que le concepteur aimerait que son programme fasse. Une autre façon de s’assurer d’une spécification est alors de vérifier qu’elle implique les énoncés plus faibles précédents ; par opposition aux tests précédents, c’est une forme de preuve de spécification.

De nombreux articles d’opinions ont été écrits sur la question de la vérification formelle des logiciels. Je vous recommande chaudement la lecture de Social Process and Proofs of Theorems and Programs, Richard De Millo, Richard Lipton et Alan Perlis, 1979. Cet article explique avec fermeté que la vérification formelle est un rêve qui n’existe pas en réalité, même chez les mathématiciens, et que nous n’arriverons jamais à prouver formellement de « vrais programmes ». Je ne suis pas d’accord, mais ça le rend d’autant plus intéressant à lire. Plus neutre, et moins pessimiste, j’ai apprécié le court article de vulgarisation Formal Proof – Theory and Practice, de John Harrison, 2008.

[ tag:blog.huoc.org,2009:posts/generation-aleatoire-bugs-compilateurs-C ]
Voir les commentaires · Commenter

/\ \/

Un peu de crypto

#. Par bluestorm. Publié le 03.04 2011 à 00:52. Un commentaire.
cryptographie débutants sécurité

Cette année, j’ai eu l’occasion de faire un peu de cryptologie.

Alors moi, dans l’idée, calculer n^(pq) dans un groupe cyclique d’ordre d, ou décaler-xorer les bits 17 fois pour calculer un hash cryptographique, ça ne me tente pas du tout.

J’ai cependant découvert qu’il y a d’autres aspects de la crypto qui ne concernent pas l’analyse technique des algorithmes, mais plutôt une analyse « sémantique » de leur utilisation. Par exemple, on a beau avoir un super algorithme de chiffrement, si on envoie la clé en clair avec le message chiffré, ce n’est pas sécurisé. Il y a des façons moins évidentes de se tromper et des gens qui cherchent comment éviter ces pièges.

Dans ce billet, je présenterai juste un exemple assez simple. Ne vous attendez pas à des merveilles tout de suite, mais elles viendront peut-être plus tard.

Étude formelle des protocoles cryptographiques

On fait une différence entre l’étude « formelle » et l’étude « calculatoire » des systèmes utilisant la cryptographie. Dans le modèle formel, on considère les algorithmes cryptographiques comme des boîtes noires, qui marchent toujours et sont incassables, et on étudie l’utilisation qui est faite de ces boîtes noires : sous des conditions données, est-ce que telle utilisation est sûre ?

Dans le modèle calculatoire, on met les mains dans le cambouis en regardant dans les boîtes, dans le but d’avoir des estimations quantitatives de la difficulté calculatoire pour casser une utilisation aux paramètres de sécurité (taille des clés, etc.) donnés. Par exemple, si vous utilisez tel algorithme de telle façon et espérez garantir telle propriété de sécurité, il faudra au moins 280 calculs à un attaquant pour la casser.

Je me limiterai au modèle formel, en utilisant certaines des boîtes noires et notations suivantes :

chiffrement symétrique

On peut encoder ou décoder un message M avec la clé K. Sans la clé, il n’y aucun moyen de décoder le message. Je note senc(M,K) le message chiffré.

chiffrement asymétrique

Un utilisateur U possède une clé publique pk(U) et une clé secrète sk(U). Il diffuse la clé publique, et garde la clé secrète… secrète. On peut chiffrer un message avec une clé publique pk(X), et alors pour le déchiffrer il faut avoir sk(X). Cela permet de faire des échanges sans partager un secret commun, comme dans le cas symétrique. Je note aenc(M,pk(X)) le message chiffré.

signature

Toujours dans un cadre asymétrique, U peut « signer » un message M dans le but de garantir qu’il vient bien de lui. Il utilise pour cela sa clé secrète, et obtient une signature qui peut être vérifiée par tout possesseur de la clé publique pk(U). On note sign(M, sk(X)) la signature, et il y a une opération check(M, S, pk(X)) qui renvoie vrai si et seulement si S est bien la signature du message M avec la clé privée correspondant à pk(X). Bien sûr, on ne peut pas récupérer sk(X) à partir de sign(M, sk(X))

Ça c’est ce que peut faire tout le monde, en particulier les « gentils », pour utiliser la crypto en espérant arriver à leurs fins. Mais que peuvent faire les méchants ? On fait en général des hypothèses paranoïaques : on considère que tout message envoyé sur le réseau peut être lu et même stoppé (avant qu’il arrive à son destinataire) par un méchant attaquant.

Un cas d’école : le protocole d’authentification de Needham-Schroeder

Le cas d’école d’étude des protocoles cryptographiques est le protocole d’authentification de Needham-Schroeder. C’est un protocole destiné à « authentifier » des agents qui communiquent entre eux, c’est-à-dire à garantir qu’ils sont bien en train de parler à la personne à laquelle ils pensent parler.

L’idée générale est d’envoyer un « défi » (challenge) à la personne avec laquelle on parle : un nombre aléatoire qu’on vient de générer, donc introuvable (on appelle un tel nombre un nonce, affreux anglicisme proche du mot « hapax »), chiffré avec la clé de la personne avec laquelle on pense parler. Si elle arrive à déchiffrer ce nonce et à nous le renvoyer, elle est authentifiée.

Pour toute paire d’agents A et B, le protocole procède comme suit :

A → B : aenc((N_A, A), pk(B))
B → A : aenc((N_A, N_B), pk(A))
A → B : aenc(N_B, pk(B))

A génère un nonce N_A et envoie la paire (N_A, A) (ici A représente une donnée qui l’identifie : son nom, son adresse mail…) à B. Il génère à son tour un nonce N_B et renvoie les deux à A, qui répond en renvoyant N_B. Si tout se passe bien, les deux ont bien répondu à leurs défis respectifs et se sont mutuellement authentifiés.

Il est crucial que les défis soient générés aléatoirement, à chaque session d’authentification. Sinon un attaquant pourrait écouter les messages et les « rejouer » ensuite dans le futur, en se faisant passer pour l’un des participants. Par exemple si N_B était une constante choisie une fois pour toute par B, un attaquant C ayant observé cet échange pourrait entamer la session en prétendant être A, et à la troisième étape renvoyer le message aenc(N_B, pk(B)), faisant ainsi croire à B qu’il est à nouveau en train de parler avec A.

La notation que j’ai utilisée pour le protocole est relativement informelle. On peut la formaliser un peu mieux, ou encore passer à des descriptions plus fines, qui décrivent par exemple précisément le moment de génération d’un nonce. Les cryptographes utilisent pour cela des variantes du π-calcul, un calcul de processus développé au départ comme base théorique de la programmation distribuée.

Il y a aussi de l’implicite au niveau du lien entre une identité A, et ses clés pk(A) et sk(A). En particulier, sk n’est pas une simple fonction, car on veut que seul A puisse calculer sk(A). La façon dont on associe pk(A) à A peut aussi être modélisée. Ici j’ai considéré que les participants « connaissent » les clés publiques, mais on peut aussi supposer un (ou plusieurs) serveurs de certifications, supposés de confiance, et qui indiquent la clé publique associée à une identité. Cela complique un peu le protocole, de façon inessentielle ici.

Enfin, il convient de faire une dernière remarque sur ce protocole : après l’authentification, N_A et N_B sont des secrets partagés entre A et B. Il a donc été suggéré d’utiliser ces secrets partagés pour une communication entre A et B, par exemple comme clé d’un chiffrage symétrique. En plus d’authentifier A et B, on souhaiterait donc garantir le secret de ces nonces.

… pas si sûr qu’il n’y paraît

Le protocole que j’ai décrit plus haut est en fait non sûr : il ne garantit pas l’authenticité des participants. Imaginons un ensemble d’agents qui s’authentifient mutuellement en utilisant ce protocole. Certains, comme A et B, sont honnêtes, mais d’autres, comme I, sont mauvais et cherchent à subvertir le protocole à leurs fins propres.

Si A entame une communication avec I en essayant de s’authentifier, I peut en profiter pour se faire passer pour A auprès de B. Je noterai Î pour l’agent I se faisant passer pour A ; c’est toujours I, mais l’intention est différente :

A → I : aenc((N_A, A), pk(I))
Î → B : aenc((N_A, A), pk(B))
B → Î : aenc((N_A, N_B), pk(A))
I → A : aenc((N_A, N_B), pk(A))
A → I : aenc(N_B, pk(I))
Î → B : aenc(N_B, pk(B))

L’idée de I est proche des man in the middle attacks : transférer les paquets sans trop y toucher, dans le but que les personnes aux deux bouts ne se rendent pas compte du problème et fassent tout le travail pour lui. Il envoie la demande de connexion de A à B, et attend la réponse de B. Il ne peut pas la lire puisqu’elle est chiffrée avec la clé de A (B pense parler à A). Mais il peut se servir de A pour la déchiffrer à sa place ! Il envoie ainsi la réponse de B, qui contient le défi N_B, à A, comme si c’était son propre défi. A le déchiffre et renvoie N_B à I, qui peut alors répondre triomphalement à B.

L’authentification est brisée, puisque B pense avoir conclu une session avec A alors que ce dernier n’a jamais parlé à B. De plus, si les nonce étaient ensuite utilisés comme clé de chiffrement de messages post-authentification, cela pourrait avoir des conséquences graves. Par exemple si B est une banque et A un de ses clients :

Î → B : senc("I'm A, please transfer all my money to I", (N_A, N_B))

Quand on parle de « cas d’école », on veut dire qu’il a été très étudié, pas que c’est un exemple fait sur mesure pour les étudiants. Le protocole de Needham-Schroeder a été publié en 1978, et la faille n’a été découverte par Gavin Lowe qu’en 1995. Inutile de dire que les personnes ayant utilisé le protocole entre temps ont dû être très, très stressées…

Gavin Lowe, simultanément à son attaque, a proposé de corriger le protocole de la façon suivante :

A → B : aenc((N_A, A), pk(B))
B → A : aenc((N_A, B, N_B), pk(A))
A → B : aenc(N_B, pk(B))

Dans la deuxième étape, B envoie son identité en plus du défi. Ainsi, A peut bien vérifier qu’il provient bien de la personne auprès de laquelle elle essaie de s’authentifier. Dans le cas de l’attaque, où A pense parler à I qui s’en sert pour le mettre en communication avec B, la réponse de I à A, issue de B, deviendrait alors :

I → A : aenc((N_A, B, N_B), pk(A))

et A, voyant que le message ne provient pas de I, interromprait immédiatement la tentative d’authentification.

Gavin Lowe conclut ainsi son article (PS, 5 pages) :

We conjecture that the revised protocol is safe against all attacks — at least, those attacks not dependent upon properties of the encryption method used. Proving this formally is the topic of current research.

C’était current research en 1995, maintenant on sait faire… tant qu’on sait ce qu’on doit prouver. Ce sera peut-être le sujet d’un prochain billet.

[ tag:blog.huoc.org,2009:posts/cryptographie-semantique ]
Voir les commentaires · Commenter

/\

Cofoja contracts, checkpoints and recursion

#. Par rz0. Publié le 20.03 2011 à 10:51. 3 commentaires.
cofoja contracts java

Since the release of Cofoja, there have been several changes, some important, some less so. One of the major things I’ve been working on recently (and which is, as I write, under review and should make it to the main branch shortly) is a new implementation of contract checkpoints: that is, where contracts are checked at run time in the final code.

In this short blog post, I will go through the various options we have considered, what we did before, what we will do now, and how it is implemented.

A matter of semantics

On the surface, contract semantics are pretty straightforward, even more so in Cofoja as we have tried to keep it simple by sticking to the most fundamental constructs:

  • preconditions must hold just before the call;
  • postconditions must hold just after the call;
  • and invariants act as both pre-and-postconditions.

While preconditions and postconditions are mostly just that, this description of invariants hides a small but important issue: they act as both pre-and-postconditions to what? Since invariants are characteristic of a class and not a method, we can legitimately ask: should invariants apply to all methods within the given class? And the answer is, as with most matters of fine semantics, that there is no definite answer, it depends on what we want. The general idea is that we want invariants to hold at those points in time where the object is in a "stable" state, one where it is expected to be behave consistently with respect to its specification. So we want to preclude any internal manipulation that goes on inside our object from checking invariants: they most probably wouldn’t hold there. The real question is thus what constitutes an internal operation. I am pretty sure the question has been discussed to death in contract programming circles; since I am not really a contract programming specialist, here I will simply give a not-so-brief overview of the different options that have been considered for Cofoja, with some Java examples to illustrate what problems they tried to address, and what we settled with in the end.

Perhaps the most important distinction that can be made between strategies lies in the decision to treat all calls to a method in the same way or apply invariant checks to some and not others. It should be noted that while it is tempting to associate whole-method semantics to a compile-time choice and per-call discrimination to a run-time behavior, some call-site-oriented approaches do not require information beyond what would be (easily) accessible to a compiler (such an example is given below).

A simple static strategy

Originally, Cofoja, similarly to its predecessor Modern Jass, used a simple rule: invariants would apply to all public or package-private methods. I know, True Java Hackers will probably hate us because of the inconsistency of that rule: package-private methods have a lesser scope than protected methods, so why check contracts on these and not protected ones? It doesn’t make sense!

The reason we had such a rule was because, we’ve noticed that, in practice, classes with methods internal to a package have their own intra-package specifications that we want to enforce with regard to other classes in the package. Conversely, protected methods, even though strictly broader in scope than their package-private counterparts, are most often used to provide utility routines to implementors who may want to write child classes; in such cases, these protected methods are likely to be called from deep within child classes, when the object is possibly in an inconsistent state. Hence the weird rule. But as awkward as it is, it did work pretty well. There were a few shortcomings, though, that we set out to fix.

Most issues with this strategy revolved around the idea that you may have public methods that may also be called from within child classes. Of course, the workaround is to make a protected method and call that from your public one, but it wasn’t totally satisfactory, especially in the case of constructors. It’s often the case that the default constructor is public; this means that child constructors can pull the invariant checking by calling the default parent constructor implicitly!

A static per-call approach

A possibly better strategy could be to consider all calls originating from a class that shares an ancestry link with the target to be internal, and all others external. This characterization has the advantage that it can be determined locally and without running the program. Its main limitation is that it requires call sites rather than methods to be altered in order to insert contract checks.

Instrumenting call sites is perfectly doable but suffers from a number of unwanted side effects. There are a few ways call sites can be modified to add contracts: we can rewrite internal calls to point to a shadow method that does not have contracts enabled, or we make external calls refer to a wrapper method (which can be inlined, in which case the method implementing the contracts are invoked directly from the caller).

In any case, the transformation means that it is impossible to distribute pre-woven libraries that check their contracts even against an application that does not, since all new call sites need to be instrumented. (New external call points appear naturally as the class is used, and new internal call sites are the result of users extending library classes.)

Another issue, which is perhaps more problematic, is interoperability with other tools that are not aware of our little splitting and wrapping tricks. Beside potentially polluting the stack trace with user-unfriendly names and references, the risk would be confusing other bytecode-reading citizens of the Java world, such as profilers and boilerplate-laying frameworks.

For these reasons, this solution was not retained and a totally dynamic strategy that could be implemented on the caller’s side was considered instead.

A dynamic per-call scheme

In the end, we decided on a dynamic strategy that can be described simply as: invariants are checked the first time we enter a contracted object. By "enter", I mean that it is the first call dispatched to that object from another object; if in the middle of one of its methods, execution leaves the instance and then comes back (A calls B, which calls A), it is not counted as "entering" the object.

Obviously, this is most easily accomplished dynamically, when information about instances is fully available. The problem of checking whether we are entering an object is equivalent to determining whether the current instance is already present in the stack trace. A straightforward way to implement that behavior is by means of a per-object flag that we set to true on entry and false on exit of the method that set it to true. Such a technique implies however that the flagged object cannot have its methods called concurrently from different threads. Such a constraint is fine for most classes and object, but for those that need it, let’s take a look at a thread-safe alternative.

The basic idea here is that we want to associate a flag per object and per thread. Making the per-object flag a ThreadLocal object is not a solution since it would introduce an unbearable number of thread-local variables to manage. Instead, it is possible to maintain our own thread-local set of currently entered objects: this map only needs to hold all contracted objects currently on the stack, which hopefully isn’t so many. My soon-to-be-merged patch implements this exclusion mechanism through a per-thread IdentityHashMap that records which objects have been seen in the current stack trace.

Actually, Cofoja will only use the thread-safe version. While the cost of accessing a thread-local variable is high compared to a simple field, it is shared with another flag, which must already reside in per-thread storage: the recursion prevention flag.

A word about recursion

Another issue with contract checking is the matter of contract recursion: when contracts access other objects, should these objects have their contracts enforced? If there is no other mechanism preventing it, we may end up in an infinite loop trying to check contracts in circle.

Hence, a simple solution is to prevent all kinds of contracts within contracts from activating: this requires a per-thread variable.

But you may ask: doesn’t the same-object exclusion rule presented in the previous section disallow recursion already? Indeed, should the same contract be checked twice in the same trace, the second one will be inhibited. However, it is true only of invariants and it is easy to write postconditions that reference each others’ methods, for example.

Nonetheless, I decided to test without the flag and came upon an interesting situation. The problem was revealed by the following excerpt from the Cofoja source code (when running Cofoja with its own contracts enabled):

@Invariant({
  "getEnclosingElement() == null " +
      "|| getEnclosingElement().getEnclosedElements().contains(this)",
  "Iterables.all(getEnclosedElements(), isValidEnclosedElement())"
})
public abstract class ElementModel

What it does is check that the current element is effectively a child of its parent and has children of its own of the proper kind. When considered alone, this contract is quite nice and very local: it examines the direct parent and children of one node. However, if contracts within contracts are honored, the invariant will trigger itself on the parent as well as all the child objects.

A quick glance at the contract may suggest that this extends the check to the full tree, which is not such a bad thing per se. But a closer look will reveal that it actually introduces many redundant checks. The core of the issue lies in the first clause: the one targeting the parent; it is hidden in the method contains. contains will scan through the entire list of children of the parent object (which are siblings of the current object) in search of one that is equal to the current element. Unfortunately, such a traversal will trigger contracts on each visited instance, hence spawning a new check that will scan all of its siblings. This scan is bound to stop once all the siblings have been seen once in the current trace; it will however repeat the same idiotic ritual with the next, and so on and so forth. This will also propagate to the whole tree.

If there is something to be learnt from this experience, for me, it was that a seemingly very legitimate contract could wreck havoc assuming the new rule only. And it was also very difficult to debug: the program just seemed to hang forever, and if stopped, it would just show a normal stack trace with a couple of nodes being checked, nothing unusual. Hence we decided that even if we could extend the same-object exclusion mechanism to pre-and-postconditions, we shouln’t do it, and instead keep the simple flag that excludes all contracts within contracts, because there shouldn’t be such an easy way for our users to write innocent-looking contracts that would blow the system.

[ tag:blog.huoc.org,2009:posts/contracts-checkpoints-recursion ]
Voir les commentaires · Commenter

>> Page : 0 1 2 3 4 5 6 7 8 9 10 11 12 13