Das vereinfachte Modell von Fil-C

• Eine Struktur, die AllocationRecord-Metadaten zusammen mit C/C++-Zeigern verfolgt und beim Dereferenzieren Speichergrenzenprüfungen durchführt
• Ein Ansatz, bei dem bei Zeigerzuweisungen, Arithmetik, der Übergabe von Funktionsargumenten, Rückgaben sowie Aufrufen von malloc und free die ursprünglichen Zeigerwerte zusammen mit den zugehörigen Metadaten mitgeführt oder in Fil-C-spezifische Aufrufe umgewandelt werden
• Zeigermetadaten im Heap-Speicher werden separat in invisible_bytes abgelegt; beim Laden und Speichern von Zeigern werden Wert und Metadaten gemeinsam gelesen bzw. geschrieben, zusätzlich mit Ausrichtungsprüfung
• filc_free gibt nur visible_bytes und invisible_bytes frei und behält das AllocationRecord selbst bei; die spätere Bereinigung übernimmt der Garbage Collector, und lokale Variablen, deren Adresse entweichen könnte, werden per Heap-Promotion behandelt
• Es bleiben reale Implementierungskomplexitäten wie Threads, Funktionszeiger sowie Speicher- und Performance-Optimierungen, aber das Modell kann zur Prüfung der Speichersicherheit großer C/C++-Codebasen oder als konkretes Systembeispiel für Pointer Provenance dienen

---

Vereinfachtes Fil-C-Modell

• Fil-C verwendet eine Struktur, die zusammen mit Zeigern AllocationRecord*-Metadaten verfolgt, um C/C++-Code speichersicher zu behandeln
  • Die tatsächliche Implementierung arbeitet per LLVM-IR-Umschreibung, das vereinfachte Modell nimmt jedoch die Form einer automatischen Transformation von C/C++-Quellcode an
  • Für jede lokale Zeigervariable einer Funktion wird eine entsprechende lokale Variable vom Typ AllocationRecord* hinzugefügt
  • Zum Beispiel wird zu T1* p1 zusätzlich AllocationRecord* p1ar = NULL eingefügt
• Einfache Zuweisungen und Berechnungen mit lokalen Zeigervariablen verschieben AllocationRecord* zusammen mit dem ursprünglichen Zeigerwert
  • p1 = p2 wird zu p1 = p2, p1ar = p2ar transformiert
  • Auch bei p1 = p2 + 10 wird p1ar = p2ar mitgeführt
  • Bei einem Cast von Integer zu Zeiger werden die Metadaten auf NULL gesetzt
  • Ein Cast von Zeiger zu Integer bleibt unverändert
• Auch bei der Übergabe von Funktionsargumenten und bei Rückgaben wird zusätzlich AllocationRecord* mitgegeben, und bestimmte Aufrufe der Standardbibliothek werden durch Fil-C-spezifische Funktionen ersetzt
  • Aufrufe von malloc und free werden jeweils in filc_malloc bzw. filc_free umgewandelt
  • Beispielsweise wird p1 = malloc(x); free(p1); zu {p1, p1ar} = filc_malloc(x); filc_free(p1, p1ar);
• filc_malloc reserviert nicht nur einen angeforderten Speicherbereich, sondern führt drei Allokationen durch
  • Allokation eines AllocationRecord-Objekts
  • Allokation von visible_bytes für die eigentlichen Daten
  • Allokation von invisible_bytes per calloc zum Speichern unsichtbarer Metadaten
  • AllocationRecord enthält die Felder visible_bytes, invisible_bytes und length

Dereferenzierung und Grenzprüfungen

• Beim Dereferenzieren eines Zeigers wird das zugehörige AllocationRecord* verwendet, um Grenzprüfungen durchzuführen
  • Es wird geprüft, ob die Zeigermetadaten nicht NULL sind
  • Die Differenz zwischen der aktuellen Zeigerposition und der Startadresse von visible_bytes wird berechnet
  • Es wird geprüft, ob der Offset kleiner als die Gesamtlänge ist
  • Es wird geprüft, ob die verbleibende Länge für die Größe des Dereferenzierungsziels ausreicht
• Für Lese- und Schreibzugriffe gilt derselbe Prüfablauf
  • Auch vor x = *p1 wird geprüft
  • Ebenso vor *p2 = x
• So blockiert die Struktur Zugriffe, bei denen ein Zeiger außerhalb seines allokierten Bereichs zeigt

Zeiger im Heap und invisible_bytes

• Für im Heap-Speicher abgelegte Zeiger kann der Compiler nicht wie bei lokalen Variablen direkt separate Begleitvariablen verwalten; deshalb werden invisible_bytes verwendet
  • Befindet sich ein Zeiger an der Position visible_bytes + i, dann wird das zugehörige AllocationRecord* an der Position invisible_bytes + i gespeichert
  • Anders gesagt verhält sich invisible_bytes wie ein Array, dessen Elementtyp AllocationRecord* ist
• Beim Lesen oder Schreiben von Zeigerwerten im Speicher wird zusätzlich zur normalen Grenzprüfung eine Ausrichtungsprüfung durchgeführt
  • Es wird geprüft, ob der Offset i ein Vielfaches von sizeof(AllocationRecord*) ist
  • Nur dann kann sicher auf invisible_bytes wie auf ein AllocationRecord**-Array zugegriffen werden
• Beim Laden eines Zeigers werden Datenzeiger und Metadaten gemeinsam geladen
  • p2 = *p1 wird durch ein anschließendes p2ar = *(AllocationRecord**)(p1ar->invisible_bytes + i) ergänzt
• Beim Speichern eines Zeigers werden nicht nur der Zeigerwert, sondern auch die zugehörigen Metadaten geschrieben
  • *p1 = p2 führt nach dem eigentlichen Datenspeichern zusätzlich *(AllocationRecord**)(p1ar->invisible_bytes + i) = p2ar aus

filc_free und Garbage Collector

• filc_free gibt, wenn der Zeiger nicht NULL ist, nach einer Konsistenzprüfung mit dem AllocationRecord genau zwei Speicherbereiche frei
  • Prüfung von par != NULL
  • Prüfung von p == par->visible_bytes
  • Freigabe von visible_bytes und invisible_bytes
  • Danach werden visible_bytes und invisible_bytes auf NULL sowie length auf 0 gesetzt
• Obwohl filc_malloc drei Allokationen durchführt, gibt filc_free das AllocationRecord-Objekt selbst nicht frei
  • Diese Differenz wird vom Garbage Collector behandelt
• Für das vereinfachte Modell reicht ein Stop-the-World-GC aus; das tatsächliche Fil-C verwendet einen parallelen, nebenläufigen, inkrementellen Collector
  • Der GC verfolgt AllocationRecord-Objekte
  • Nicht mehr erreichbare AllocationRecord-Objekte werden zur Freigabe markiert
• Der GC führt zusätzlich zwei weitere Aufgaben aus
  • Beim Freigeben eines nicht erreichbaren AllocationRecord wird filc_free aufgerufen
  • Alle Zeiger, die auf ein AllocationRecord mit length == 0 zeigen, werden auf ein einzelnes kanonisches AllocationRecord der Länge 0 umgestellt
• Dadurch entsteht selbst ohne Aufruf von free kein Speicherleck
  • Der GC gibt den Speicher automatisch frei
  • Ein expliziter free-Aufruf ermöglicht jedoch eine frühere Freigabe als der GC
• Nach free wird das betreffende AllocationRecord schließlich unerreichbar und kann später bereinigt werden

Entweichende Adressen lokaler Variablen und Heap-Promotion

• Durch das Vorhandensein eines GC erweitert sich der Bereich, in dem Adressen lokaler Variablen sicher behandelt werden können
  • Wenn die Adresse einer lokalen Variablen genommen wurde und der Compiler nicht beweisen kann, dass diese Adresse nicht über die Lebensdauer der Variable hinaus entweicht, wird sie in eine Heap-Allokation promotet
• Solche lokalen Variablen werden dann per malloc statt auf dem Stack allokiert
  • Ein separates Einfügen von free ist nicht nötig
  • Das Aufräumen übernimmt der GC

Fil-C-Version von memmove

• Die memmove-Funktion der C-Standardbibliothek verarbeitet beliebigen Speicher, weshalb der Compiler nicht wissen kann, ob darin Zeiger enthalten sind
• Deshalb wird eine Heuristik verwendet
  • Zeiger in beliebigem Speicher müssen vollständig innerhalb dieses Speicherbereichs liegen
  • Zeiger müssen korrekt ausgerichtet sein
• Dadurch entstehen selbst bei derselben Verschiebung von 8 Byte Unterschiede im Verhalten
  • Werden ausgerichtete 8 Byte in einem Schritt mit memmove verschoben, dann werden die entsprechenden invisible_bytes mitverschoben
  • Werden 8 Byte einzeln in acht 1-Byte-memmove-Operationen verschoben, dann werden die invisible_bytes nicht mitverschoben

Zusätzliche Komplexität in der tatsächlichen Implementierung

• Threads

  • Nebenläufigkeit erhöht die GC-Komplexität
  • filc_free kann Speicher nicht sofort freigeben
    • Denn zwischen dem freigebenden Thread und einem anderen Thread, der auf denselben Speicher zugreift, kann ein Race Condition auftreten
  • Auch atomare Operationen auf Zeigern benötigen zusätzliche Behandlung
    • Die grundlegende Umschreibung ersetzt Zeiger-Loads/Stores durch je zwei Loads/Stores und zerstört damit die Atomarität

• Funktionszeiger

  • Zusätzliche Metadaten im AllocationRecord markieren, ob visible_bytes normale Daten oder ein ausführbarer Codezeiger sind
  • Ein Aufruf über den Funktionszeiger p1 prüft sowohl p1 == p1ar->visible_bytes als auch, ob p1ar tatsächlich einen Funktionszeiger repräsentiert
  • Um Type-Confusion-Angriffe auf Funktionszeiger zu verhindern, ist auch auf ABI-Ebene eine Prüfung der Typsignatur erforderlich
  • Ein möglicher Ansatz ist, allen Funktionen dieselbe Typsignatur zu geben
    • Etwa so, dass alle Argumente in eine Struktur gepackt und über den Speicher übergeben werden
    • An der ABI-Grenze empfängt jede Funktion dann nur ein einzelnes AllocationRecord, das dieser Struktur entspricht

• Optimierung der Speichernutzung

  • Es kann erwogen werden, dass filc_malloc invisible_bytes nicht sofort allokiert, sondern erst bei Bedarf
  • Ebenso kann AllocationRecord zusammen mit visible_bytes in einer einzigen Allokation platziert werden
  • Wenn das zugrunde liegende malloc Metadaten am Anfang jeder Allokation anfügt, könnten diese auch in das AllocationRecord übernommen werden

• Performance-Optimierung

  • Die Speichersicherheit von Fil-C bringt Performance-Kosten mit sich
  • Es gibt Spielraum für verschiedene Techniken, um einen Teil der verlorenen Leistung zurückzugewinnen

Einsatzszenarien für Fil-C

• Fil-C kann eingesetzt werden, wenn große C/C++-Codebasen zwar zu funktionieren scheinen, aber keine Prüfung der Speichersicherheit haben und man bereit ist, für Speichersicherheit GC-Einführung und deutliche Performance-Einbußen in Kauf zu nehmen
  • Es wird als mögliche Übergangslösung bis zu einer Neuschreibung in Java, Go oder Rust erwähnt
• Ähnlich wie ASan kann Fil-C auch zur Erkennung von Speicherfehlern ausgeführt werden
  • C/C++-Code kann unter Fil-C ausgeführt werden, um Speicherfehler zu überprüfen
• In Sprachen, bei denen Compile-Time-Sprache und Runtime-Sprache identisch sind und die starke Compile-Time-Sicherheit bieten, ist auch eine Nutzung für sichere Compile-Time-Auswertung möglich
  • Als Beispiel wird Zig erwähnt
  • Selbst wenn die Runtime-Auswertung unsicher ist, könnte die Compile-Time-Auswertung eine Fil-C-Konfiguration verwenden
• Auch als konkretes Systembeispiel für Pointer Provenance ist Fil-C von Bedeutung
  • Wenn p1 und p2 denselben Typ haben, stellt sich die Frage, ob eine Optimierung von if (p1 == p2) { f(p1); } zu if (p1 == p2) { f(p2); } zulässig ist
  • In Fil-C ist die Antwort eindeutig nein, weil sich das an f übergebene AllocationRecord* unterscheiden kann
  • In diesem Punkt dient Fil-C als konkretes Beispiel für ein System mit Pointer Provenance

[GN⁺]

Hacker-News-Kommentare

• Es wäre ein ziemlich interessantes Experiment, invisicaps an etwas wie chibicc oder slimcc anzubauen.
  Man könnte auch Referenzzählung oder Varianten des invisible capability system ausprobieren, und vielleicht sogar Speicher sparen – auf Kosten eines kleinen zusätzlichen Indirektionsaufwands.
• Ich habe filc-bazel-template erstellt und als Bazel target verpackt.
  Hoffentlich ist das hilfreich für Leute, die beides zusammen nutzen möchten, um hermetic builds zu erstellen.
• Ich verstehe die Bedeutung dieses Satzes nicht ganz.
  Upon freeing an unreachable AllocationRecord, call filc_free on it.
  So wie ich das sehe, soll damit wohl gemeint sein, dass man vor dem Freigeben eines nicht erreichbaren AR zuerst den Speicher freigibt, auf den die Felder visible_bytes und invisible_bytes zeigen.
• Für mich ist Fil-C eines der am stärksten unterschätzten Projekte, die ich bisher gesehen habe.
  Interessanter als das übliche „rewrite it in Rust“ im Namen der Sicherheit finde ich, dass sich bestehende C-Programme vollständig speichersicher kompilieren lassen.
  • Meiner Meinung nach muss man dabei ein paar Dinge zusammen betrachten.
    Erstens ist Fil-C langsamer und größer. Wenn das akzeptabel wäre, könnte man auch sagen, dass man in den letzten zehn Jahren eher zu Java oder C# als zu Rust hätte wechseln sollen.
    Zweitens verwendet man immer noch C. Für die Pflege bestehenden Codes ist das in Ordnung, aber wenn man viel neuen Code schreibt, finde ich Rust deutlich angenehmer.
    Drittens bietet Fil-C Laufzeitsicherheit, während Rust einen Teil davon schon zur Compile-Zeit ausdrücken kann. Und Sprachen wie WUFFS gehen noch weiter und versuchen, Sicherheit bereits beim Kompilieren ohne Laufzeitprüfungen zu beweisen; der Code kann dann zwar logisch falsch sein, aber Abstürze oder die Ausführung beliebigen Codes sollen verhindert werden.
  • Ich würde nicht sagen, dass es hier unterbewertet ist. Es gab bereits ziemlich viele Diskussionen dazu.
    Es gab Threads wie 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 und Fil's Unbelievable Garbage Collector.
  • Für mich ist die zentrale Einschränkung von Fil-C, dass es sich um runtime memory safety handelt.
    Man kann immer noch speicherunsicheren Code schreiben, nur ist das Ergebnis jetzt eher ein sicherer Absturz statt einer Schwachstelle.
    Wenn man etwa eine Web-API baut, die nicht vertrauenswürdige Eingaben annimmt, kann so ein Problem am Ende immer noch zu einem denial-of-service führen; das ist zwar besser, aber meiner Meinung nach noch nicht gut genug.
    Das soll die Arbeit an Fil-C nicht kleinreden, aber ich denke, Laufzeitansätze haben klare Grenzen.
  • Danke für dein Interesse.
    Fairerweise muss man aber sagen, dass Fil-C deutlich langsamer als Rust ist und auch mehr Speicher verbraucht.
    Andererseits unterstützt Fil-C safe dynamic linking und man könnte in mancher Hinsicht sogar sagen, dass es strenger sicher ist als Rust.
    Letztlich sind das Trade-offs, und man sollte je nach Situation auswählen.
  • Meinem Eindruck nach leuchten bei C/C++-Programmierern nur selten die Augen, wenn man ihnen sagt, dass sie ihrem Programm einen garbage collector hinzufügen können.
    Deshalb scheint diese Idee zwar technisch interessant zu sein, emotional aber nicht leicht anzukommen.
• Meiner Ansicht nach ist Fil-C bei data races nicht speichersicher.
  Capability- und Pointer-Werte können während einer Zuweisung zerrissen werden; wenn das Thread-Interleaving ungünstig ausfällt, kann dadurch mit einem falschen Pointer auf ein Objekt zugegriffen werden, was zu beliebigem Fehlverhalten führen kann.
  Mit dieser Einschränkung an sich könnte ich leben, aber schade finde ich die Atmosphäre, in der selbst Unterstützer hart gegen Leute vorgehen, die auf das Problem hinweisen.
  • Soweit ich weiß, wird das dort mit atomic ops behandelt.
    Leider ist das auch einer der großen Gründe für den Overhead.
• Für mich ist das letztlich einfach noch eine weitere Variante der fat pointers-Familie.
  Solche Ansätze wurden schon oft implementiert und dann wieder verworfen, weil die Sicherheitsgarantien nicht ausreichten, non-fat ABI boundaries schwer zu überqueren waren oder der Overhead zu hoch war.
  • Allerdings gibt es inzwischen wieder einen Trend dazu, dass fat pointers direkt durch Hardware unterstützt werden; vielleicht ist es also nicht fair, das vorschnell abzutun.
    Außerdem lässt sich filc meiner Meinung nach nicht allein durch einfache fat pointer erklären.
  • Man sollte auch berücksichtigen, dass hardware memory tagging auf mehreren Plattformen bereits verfügbar ist.