Le modèle simplifié de Fil-C

• Une architecture qui suit les pointeurs C/C++ en leur associant des métadonnées AllocationRecord, et effectue une vérification des bornes mémoire lors du déréférencement
• Une méthode qui fait circuler ensemble la valeur d’origine du pointeur et les métadonnées associées, ou qui convertit les appels en appels spécifiques à Fil-C, depuis l’affectation de pointeurs, l’arithmétique, le passage d’arguments aux fonctions, les retours, jusqu’aux appels à malloc et free
• Les métadonnées des pointeurs dans la mémoire du tas sont stockées séparément dans invisible_bytes ; lors des chargements/stockages de pointeurs, la valeur et les métadonnées sont lues et écrites ensemble, avec en plus une vérification d’alignement
• filc_free ne libère que visible_bytes et invisible_bytes en conservant l’AllocationRecord lui-même ; le nettoyage ultérieur est pris en charge par le ramasse-miettes, et les variables locales dont l’adresse peut s’échapper sont promues sur le tas
• Même si des complexités d’implémentation réelles subsistent, comme les threads, les pointeurs de fonction ou les optimisations mémoire et performances, cela peut servir d’exemple de système concret pour la vérification de la sûreté mémoire de grands codes C/C++ ou pour la pointer provenance

---

Modèle simplifié de Fil-C

• Fil-C utilise une architecture qui suit des métadonnées AllocationRecord* avec les pointeurs afin de traiter du code C/C++ de manière sûre en mémoire
  • L’implémentation réelle repose sur une réécriture de l’IR LLVM, mais le modèle simplifié prend la forme d’une transformation automatique du code source C/C++
  • Pour chaque variable locale de type pointeur dans une fonction, une variable locale AllocationRecord* correspondante est ajoutée
  • Par exemple, pour T1* p1, on ajoute AllocationRecord* p1ar = NULL
• Les affectations simples et calculs sur les variables locales pointeurs déplacent aussi AllocationRecord* avec la valeur d’origine du pointeur
  • p1 = p2 est transformé en p1 = p2, p1ar = p2ar
  • p1 = p2 + 10 s’accompagne aussi de p1ar = p2ar
  • Un cast d’un entier vers un pointeur définit les métadonnées à NULL
  • Un cast d’un pointeur vers un entier reste inchangé
• Lors du passage d’arguments aux fonctions et des retours, AllocationRecord* est transmis en plus avec le pointeur, et certains appels de bibliothèque standard sont remplacés par des fonctions spécifiques à Fil-C
  • Les appels à malloc et free sont transformés respectivement en filc_malloc et filc_free
  • Par exemple, p1 = malloc(x); free(p1); devient {p1, p1ar} = filc_malloc(x); filc_free(p1, p1ar);
• filc_malloc n’alloue pas seulement la mémoire demandée, mais effectue trois allocations
  • Allocation d’un objet AllocationRecord
  • Allocation de visible_bytes pour les données réelles
  • Allocation par calloc de invisible_bytes pour stocker les métadonnées invisibles
  • AllocationRecord contient les champs visible_bytes, invisible_bytes et length

Déréférencement et vérification des bornes

• Lors du déréférencement d’un pointeur, une vérification des bornes est effectuée à l’aide de l’AllocationRecord* associé
  • Vérifier que les métadonnées du pointeur ne sont pas NULL
  • Calculer la différence entre la position courante du pointeur et l’adresse de début de visible_bytes
  • Vérifier que l’offset est inférieur à la longueur totale
  • Vérifier que la longueur restante est suffisante pour la taille de la cible du déréférencement
• La même procédure de vérification s’applique à la lecture comme à l’écriture
  • Une vérification est effectuée avant x = *p1
  • La même forme de vérification est effectuée avant *p2 = x
• Cette structure empêche les accès où la cible pointée sort de la plage allouée

Pointeurs dans le tas et invisible_bytes

• Les pointeurs stockés dans la mémoire du tas ne peuvent pas être gérés par le compilateur via des variables séparées comme les variables locales ; invisible_bytes est donc utilisé
  • S’il y a un pointeur à la position visible_bytes + i, l’AllocationRecord* correspondant est stocké à la position invisible_bytes + i
  • Autrement dit, invisible_bytes se comporte comme un tableau dont le type d’élément est AllocationRecord*
• Lorsqu’une valeur de pointeur est lue ou écrite en mémoire, une vérification d’alignement s’ajoute à la vérification de bornes habituelle
  • Vérifier que l’offset i est un multiple de sizeof(AllocationRecord*)
  • Cette condition doit être satisfaite pour pouvoir accéder en toute sûreté à invisible_bytes comme à un tableau de AllocationRecord**
• Lors d’un chargement de pointeur, les métadonnées sont chargées en même temps que le pointeur de données
  • p2 = *p1 est suivi de p2ar = *(AllocationRecord**)(p1ar->invisible_bytes + i)
• Lors d’un stockage de pointeur, les métadonnées correspondantes sont écrites en plus de la valeur du pointeur
  • *p1 = p2 effectue, après le stockage des données réelles, *(AllocationRecord**)(p1ar->invisible_bytes + i) = p2ar

filc_free et le ramasse-miettes

• Quand le pointeur n’est pas NULL, filc_free vérifie la cohérence avec AllocationRecord puis ne libère que deux zones mémoire
  • Vérifier par != NULL
  • Vérifier p == par->visible_bytes
  • Libérer visible_bytes et invisible_bytes
  • Puis définir visible_bytes et invisible_bytes à NULL, et length à 0
• Même si filc_malloc effectue trois allocations, filc_free ne libère pas l’objet AllocationRecord lui-même
  • Cette différence est gérée par le ramasse-miettes
• Dans le modèle simplifié, un GC stop-the-world suffit ; le vrai Fil-C utilise un collecteur parallèle, concurrent et incrémental
  • Le GC suit les objets AllocationRecord
  • Les AllocationRecord inaccessibles sont marqués pour libération
• Le GC effectue en plus deux tâches
  • Appeler filc_free lors de la libération d’un AllocationRecord inaccessible
  • Remplacer tous les pointeurs vers un AllocationRecord dont length vaut 0 par un unique AllocationRecord canonique de longueur 0
• Grâce à ce comportement, l’absence d’appel à free ne mène pas à une fuite mémoire
  • Le GC effectue la libération automatiquement
  • Mais l’appel à free permet une libération plus précoce que celle du GC
• Après free, l’AllocationRecord concerné finit de toute façon par devenir inaccessible et peut être nettoyé plus tard

Échappement d’adresse des variables locales et promotion sur le tas

• En présence d’un GC, la plage dans laquelle l’adresse d’une variable locale peut être manipulée en toute sûreté s’élargit
  • Si l’adresse d’une variable locale a été prise et que le compilateur ne peut pas prouver que cette adresse ne s’échappera pas au-delà de la durée de vie de la variable, elle est promue vers une allocation sur le tas
• Ces variables locales sont alors allouées via malloc au lieu de la pile
  • Il n’est pas nécessaire d’insérer un free correspondant
  • Le GC s’occupe de la récupération

Version Fil-C de memmove

• Le memmove de la bibliothèque standard C traite une mémoire arbitraire, ce qui pose le problème suivant : le compilateur ne peut pas savoir s’il y a des pointeurs à l’intérieur
• Pour cela, une heuristique est appliquée
  • Les pointeurs dans une mémoire arbitraire doivent y être entièrement contenus dans cette plage mémoire
  • Les pointeurs doivent être correctement alignés
• Cette règle entraîne des différences de comportement même pour le déplacement des mêmes 8 octets
  • Si 8 octets alignés sont déplacés d’un seul coup par memmove, la portion correspondante de invisible_bytes se déplace aussi
  • Si memmove est exécuté 8 fois octet par octet, invisible_bytes ne se déplace pas

Complexités supplémentaires dans l’implémentation réelle

• Threads

  • La concurrence augmente la complexité du GC
  • filc_free ne peut pas libérer immédiatement la mémoire
    • Car il peut y avoir une condition de course entre le thread qui libère et un autre thread accédant à la même mémoire
  • Les opérations atomiques sur les pointeurs nécessitent aussi un traitement supplémentaire
    • La réécriture de base remplace les chargements/stockages de pointeurs par deux chargements/stockages, ce qui brise l’atomicité

• Pointeurs de fonction

  • Des métadonnées supplémentaires dans AllocationRecord permettent d’indiquer que visible_bytes n’est pas une donnée ordinaire mais un pointeur vers du code exécutable
  • Un appel via un pointeur de fonction p1 vérifie p1 == p1ar->visible_bytes et contrôle aussi que p1ar représente bien un pointeur de fonction
  • Pour empêcher les attaques de confusion de type sur les pointeurs de fonction, une vérification de signature de type est aussi nécessaire dans l’ABI d’appel
  • Une méthode consiste à donner la même signature de type à toutes les fonctions
    • En traitant cela comme un passage en mémoire de tous les arguments regroupés dans une structure
    • À la frontière ABI, chaque fonction ne reçoit alors qu’un seul AllocationRecord correspondant à cette structure

• Optimisation de l’usage mémoire

  • On peut envisager que filc_malloc n’alloue pas immédiatement invisible_bytes, mais le fasse à la demande
  • On peut aussi envisager de placer AllocationRecord et visible_bytes ensemble dans une seule allocation
  • Si le malloc sous-jacent attache des métadonnées en tête de chaque allocation, on peut aussi envisager d’intégrer ces métadonnées à AllocationRecord

• Optimisation des performances

  • La sûreté mémoire de Fil-C a un coût en performances
  • Il existe une marge pour appliquer diverses techniques afin de récupérer une partie des performances perdues

Quand utiliser Fil-C

• Fil-C peut être utilisé pour de grands codes C/C++ qui semblent fonctionner mais sans vérification de sûreté mémoire, lorsque l’on peut accepter l’introduction d’un GC et une forte baisse de performances au nom de la sûreté mémoire
  • Il est mentionné comme mesure temporaire possible avant une réécriture en Java, Go ou Rust
• Comme ASan, Fil-C peut aussi être exécuté dans un but de détection de bugs mémoire
  • Il est possible d’exécuter du code C/C++ sous Fil-C pour vérifier la présence de bugs mémoire
• Dans les langages dont le langage de compilation et le langage d’exécution sont identiques, et dont la sûreté à la compilation est forte, cela peut servir à une évaluation sûre à la compilation
  • Zig est cité en exemple
  • Même si l’évaluation à l’exécution n’est pas sûre, l’évaluation à la compilation peut utiliser une configuration de type Fil-C
• Cela a aussi un intérêt comme exemple de système concret traitant la pointer provenance
  • La question est posée de savoir si, lorsque p1 et p2 ont le même type, l’optimisation consistant à transformer if (p1 == p2) { f(p1); } en if (p1 == p2) { f(p2); } est possible
  • Dans Fil-C, comme les AllocationRecord* transmis à f diffèrent, il est explicitement indiqué que la réponse est clairement non
  • En ce sens, Fil-C sert d’exemple de système concret doté de pointer provenance

[GN⁺]

Commentaires sur Hacker News

• Ce serait une expérience assez intéressante d’ajouter invisicaps à quelque chose comme chibicc ou slimcc
  Il y aurait aussi de quoi tester le comptage de références ou des variantes du invisible capability system, et on pourrait peut-être économiser de la mémoire en échange d’un léger coût d’indirection
• J’ai créé filc-bazel-template et je l’ai empaqueté comme cible Bazel
  J’espère que cela sera utile à ceux qui veulent utiliser les deux ensemble pour faire des builds hermétiques
• Je ne comprends pas bien le sens de cette phrase
  Upon freeing an unreachable AllocationRecord, call filc_free on it.
  À mon avis, ce que cela veut dire, c’est qu’avant de libérer un AR inaccessible, il faut d’abord libérer la mémoire pointée par les champs visible_bytes et invisible_bytes
• J’ai l’impression que Fil-C est l’un des projets les plus sous-estimés que j’aie vus jusqu’ici
  Le fait de pouvoir compiler des programmes C existants de manière entièrement memory-safe me paraît plus intéressant que de dire, pour la sûreté, « rewrite it in Rust »
  • À mon avis, il faut regarder plusieurs choses ensemble
    Premièrement, Fil-C est plus lent et plus volumineux. Si cela ne posait pas problème, on aurait aussi pu dire qu’au cours des dix dernières années il aurait mieux valu aller vers Java ou C# avant même Rust
    Deuxièmement, cela reste du C. C’est bien pour maintenir du code existant, mais si l’on écrit beaucoup de nouveau code, je trouve Rust bien plus agréable
    Troisièmement, Fil-C fournit une sûreté à l’exécution, tandis que Rust peut exprimer une partie des garanties à la compilation. Et des langages comme WUFFS vont encore plus loin en essayant de prouver la sûreté à la compilation sans vérifications à l’exécution, de sorte que le code peut être logiquement faux, mais sans provoquer de crash ni permettre l’exécution de code arbitraire
  • Je ne dirais pas que c’est sous-estimé ici. Il y a déjà eu pas mal de discussions à ce sujet
    Des fils comme Fil-Qt: A Qt Base build with Fil-C experience, Linux Sandboxes and Fil-C, Ported freetype, fontconfig, harfbuzz, and graphite to Fil-C, A Note on Fil-C, Notes by djb on using Fil-C, Fil-C: A memory-safe C implementation et Fil's Unbelievable Garbage Collector ont déjà existé
  • La principale limite de Fil-C, selon moi, c’est que c’est de la runtime memory safety
    On peut toujours écrire du code non memory-safe, sauf que maintenant le résultat sera plutôt un crash certain qu’une vulnérabilité
    Si l’on construit quelque chose comme une API web qui reçoit des entrées non fiables, ce genre de problème peut malgré tout finir en denial-of-service ; c’est mieux, mais difficile d’y voir quelque chose d’assez satisfaisant
    Je ne cherche pas à rabaisser le travail sur Fil-C lui-même, mais je pense que l’approche runtime a des limites claires
  • Merci pour l’intérêt
    Mais pour être juste, Fil-C est nettement plus lent que Rust et consomme aussi plus de mémoire
    En revanche, Fil-C prend en charge le safe dynamic linking et, à certains égards, on peut même dire qu’il est plus strictement sûr que Rust
    Au final, ce sont des compromis, donc autant choisir selon le contexte
  • J’ai l’impression que, quand on dit à des programmeurs C/C++ qu’ils peuvent ajouter un garbage collector à leur programme, leurs yeux s’illuminent rarement
    Donc, même si l’idée est techniquement intéressante, elle ne prend pas facilement sur le plan émotionnel
• À mon avis, Fil-C n’est pas memory-safe en cas de data race
  La capability et la valeur du pointeur peuvent être déchirées pendant une affectation ; avec un mauvais interleaving de threads, on peut alors accéder à un objet avec un pointeur erroné et provoquer un comportement arbitraire
  Cette limite en elle-même peut se comprendre, mais je trouve dommage l’ambiance où même des soutiens du projet s’en prennent vivement à ceux qui soulèvent le problème
  • D’après ce que je sais, ce point est géré avec des atomic ops
    Malheureusement, c’est aussi l’une des grandes causes du surcoût
• À mon avis, c’est au fond une autre variante des techniques de fat pointers
  Ce type d’approche a souvent été implémenté puis écarté à plusieurs reprises, parce que les garanties de sécurité n’étaient pas jugées suffisantes, qu’il était difficile de franchir des frontières ABI non fat, ou que le surcoût était trop élevé
  • Mais on voit aujourd’hui revenir une tendance où le matériel prend directement en charge les fat pointers, donc ce n’est peut-être pas une idée à rejeter trop vite
    En plus, je ne pense pas qu’on puisse résumer filc à de simples fat pointers
  • Je pense qu’il faut aussi tenir compte du fait que plusieurs plateformes fournissent déjà du hardware memory tagging