Testen van race conditions met memory access tracing en stack-based delay injection

Veel beveiligingsbugs zijn race conditions, waarbij multi-threaded uitvoering in een specifieke volgorde moet plaatsvinden voordat een negatief effect optreedt. Dit zorgt voor uitdagingen in verschillende scenario's:

  • Het bevestigen van bug-kandidaten die handmatig of via statische analyse zijn ontdekt.
  • Regressietests: Na het oplossen van een race condition bug is er vaak geen goede manier om een regressietest te schrijven die de bug betrouwbaar triggert als onderdeel van een testsuite.
  • Automatische bug-detectie, zoals fuzzing: Voor een fuzzer is het moeilijk om alle interessante interleavings (vervlechtingen) van gelijktijdige operaties te testen, of om codepaden te bereiken die alleen worden uitgevoerd wanneer operaties racen.

Ik ontdek bugs meestal door handmatig code te lezen. Wanneer ik denk een bug te hebben gevonden, schrijf ik normaal gesproken een testcase om te bewijzen of te weerleggen dat de bug bestaat. Bij race conditions kan het moeilijk zijn om een van beide resultaten te bereiken. Voor Linux-kernelbugs grijp ik vaak terug op het opnieuw compileren van de kernel nadat ik conditionele mdelay()-aanroepen (die ongeveer de opgegeven tijd in een spinloop wachten) heb toegevoegd op geschikte plaatsen; ik maak deze meestal afhankelijk van de naam van de draaiende thread, hoewel soms complexere condities nodig zijn.

Op platforms die DTrace ondersteunen (zoals macOS en Windows), is het mogelijk om DTrace-probes te gebruiken die chill() aanroepen voor een soortgelijk effect. De bruikbaarheid hiervan is echter beperkt, aangezien DTrace alleen kan tracen op non-inline functiegrenzen of expliciete trace-punten, en niet op elke instructie. Ongeacht het platform kan deze aanpak tijdrovend zijn en vereist het vaak trial-and-error om definitief vast te stellen of code buggy is.

Daarnaast worden fixes voor race condition bugs in de Linux-kernel vaak vergezeld door handgeschreven ASCII-diagrammen die problematische thread-interleavings laten zien met call graphs en relevante geheugentoegangen (zie bijvoorbeeld de recente rtspinunlock UAF-fix of de recente jbd2 deadlock-fix). Het zou handig zijn om developer tooling te hebben die potentieel kwetsbare code kan analyseren en de resultaten in een soortgelijke representatie kan tonen.

Samenvatting

Ik heb tools geschreven voor het verkennen van mogelijke interleavings van multi-threaded testcases voor de Linux-kernel:

  • Een tool die automatisch alle mogelijke A-B-A interleavings van een testcase test.
  • Een terminal UI (TUI) voor handmatige exploratie van mogelijke interleavings.
  • Een GUI voor handmatige exploratie van mogelijke interleavings.

Het kernel-gedeelte hiervan is ook bedoeld om bruikbaar te zijn voor het ontdekken van race conditions via fuzzing, maar de userspace-tooling daarvoor moet nog worden geïmplementeerd.

De tools zijn beschikbaar op GitHub onder de naam MAccConc (kort voor “Memory Access Concurrency”). Zie de README daar voor installatie- en gebruiksinstructies.

Voorgaand werk

Dit project is geïnspireerd door discussies met Ned Williamson, wiens sockfuzzer-project concurrency-bugs exploreerde door een aangepaste scheduler te gebruiken die kan reschedulen bij synchronisatie-primitieven.

Mijn tooling is grotendeels gebaseerd op ideeën die vergelijkbaar zijn met SKI, maar SKI gebruikt een andere implementatie: het registreert geheugentoegangen en controleert de scheduling van vCPU's met een gepatchte versie van QEMU in TCG-modus, en gebruikt VM-snapshots om verschillende uitvoeringsinterleavings te verkennen.

Het ontdekken van geheugentoegangen die kunnen bijdragen aan race conditions (communicatiepunten)

Zoals beschreven in het SKI-paper, kunnen interessante uitvoeringsinterleavings van een gegeven multi-threaded testcase worden ontdekt door de geheugentoegangen van alle threads te tracen en te zoeken naar paren toegangen op twee threads die met elkaar kunnen interageren. Dit betekent grofweg dat minstens één van hen een schrijfoperatie is en dat ze overlappende geheugenbereiken benaderen. Het SKI-paper noemt dergelijke geheugentoegangen communication points.

Dit vereist een mechanisme om geheugentoegang-coverage te verzamelen. Waar SKI dit deed door QEMU's TCG-modus te patchen, vertrouw ik op ASAN-instrumentatie in "outline"-modus (compiler backend flag asan-instrumentation-with-call-threshold=0, geselecteerd door CONFIGKASANOUTLINE in de Linux-kernel), die helper-functieaanroepen genereert bij geheugentoegang. Ik geloof dat de kernel de juiste plek is om deze data te verzamelen, omdat dit de kernel in staat stelt om ook hogere-niveau informatie te verschaffen over lock acquire/release-gebeurtenissen, hoewel ik dit op dit moment nog niet heb geïmplementeerd. Implementatie in de kernel betekent theoretisch ook dat testen op bare-metal hardware mogelijk is, in plaats van alleen binnen VM's.

Aangezien Linux al KCOV heeft als mechanisme om basis-block kernel coverage informatie naar userspace te sturen, heb ik besloten hetzelfde mechanisme te gebruiken om informatie over geheugentoegangen te registreren. Een alternatief zou ftrace zijn, maar ik koos voor KCOV vanwege de eenvoudigere in-memory representatie van trace-data (relevant voor het herstellen van data uit gecrashte VM's), het gebruik van statische always-on instrumentatie in plaats van runtime-enabled instrumentatie, en omdat mijn indruk is dat KCOV is ontworpen voor hogere-frequentie trace-events dan ftrace.

Implementatiedetail: ASAN en TSAN

ASAN voegt normaal gesproken helper-aanroepen voor opeenvolgende geheugentoegangen samen. Om per geheugentoegang één callback te ontvangen, schakelen de kernel-patches deze compiler-optimalisatie expliciet uit met de asan-opt-same-temp backend flag.

ASAN is bedoeld voor het identificeren van UAF (Use-After-Free), dus het genereert geen helper-aanroepen bij directe stack-geheugentoegang, tenzij er potentieel sprake is van out-of-bounds toegang. Dit betekent dat sommige race conditions met on-stack objecten, zoals wait queues, mogelijk niet detecteerbaar zijn. ASAN genereert standaard ook geen helper-aanroepen voor toegang tot globals, maar deze optimalisatie kan worden uitgeschakeld met de asan-opt-globals backend flag.

Een alternatief zou TSAN-instrumentatie zijn, die is ontworpen voor het detecteren van data races en informatie biedt over access atomicity. Het nadeel is dat compilers niet ondersteunen om zowel ASAN- als TSAN-hooks tegelijkertijd te genereren. Om memory safety violations (zoals UAF) te blijven detecteren bij gebruik van TSAN-hooks, zou het nodig zijn om de ASAN-implementatie van de kernel te laten draaien op de TSAN-hooks of de compiler te wijzigen.

Implementatiedetail: KCOV en achtergrondwerk

Sommige race conditions betrekken achtergrondwerk, bijvoorbeeld:

  • Verwerkingsloopback van netwerkpakketten.
  • RCU-callbacks.

KCOV kan optioneel remote coverage verzamelen voor achtergrondwerk in sommige subsystems; echter, in de upstream Linux zijn de meeste soorten achtergrondwerk die interessant zijn voor mij nog niet geïntegreerd met dit mechanisme. Het inschakelen hiervan voor andere delen van de kernel zou relatief eenvoudig moeten zijn, en ik heb een concept-patch om dit te doen voor RCU-callbacks.

Stabiele identificatoren voor geheugentoegang over runs: count-augmented stack traces

Om verschillende volgordes van geheugentoegang te testen, is een manier nodig om interessante geheugentoegangen stabiel te identificeren over verschillende executies van een testcase. Identificatie op basis van het data-adres werkt niet als het adres zich bevindt in een object dat bij elke executie opnieuw wordt gealloceerd; identificatie enkel via het instructie-adres werkt niet goed als de toegang plaatsvindt in een functie zoals memcpy() of spin_lock().

SKI lost dit op met VM-state snapshots, zodat elke executie start vanuit dezelfde globale staat.

Ik identificeer geheugentoegangen in plaats daarvan met count-augmented stack traces. Hierbij bestaat elk element van de stack trace in essentie uit een adres van een aangeroepen functie en een getal dat aangeeft hoeveel aanroepen naar deze functie in het huidige stack-frame moeten worden overgeslagen.

Een voorbeeld van de semantiek van een count-augmented stack trace zou zijn: "Op deze thread, kijk naar de tweede aanroep naar x64sysrecvfrom, dan daarbinnen naar de eerste aanroep naar sysrecvfrom, dan daarbinnen naar de eerste aanroep naar sockrecvmsg, dan daarbinnen naar de eerste aanroep naar unixstreamrecvmsg, dan daarbinnen naar de eerste aanroep naar unixstreamreadgeneric, dan daarbinnen naar de tweede aanroep naar rawspinunlock, en vervolgens naar de eerste geheugentoegang op instructie-adres X".

Dit identificeert ondubbelzinnig een punt in een execution trace, is onafhankelijk van concrete data-adressen en is relatief stabiel bij wijzigingen in de control flow van irrelevante delen van de trace.

Om dit mogelijk te maken, moet KCOV informatie verschaffen over function entry/exit-gebeurtenissen, zodat userspace bij het parsen van de KCOV-output kan bijhouden hoe de call stack verandert. Dit vereist compiler-ondersteuning als onderdeel van SanitizerCoverage; ik heb hiervoor een LLVM-feature patch ingediend, die is opgenomen in de LLVM 23.1.0 release.

Het afdwingen van uitvoeringsvolgordes met delay injection

Om specifieke uitvoeringsvolgordes via KCOV af te dwingen, heb ik een ioctl KCOVSETDI geïmplementeerd. Hiermee kan userspace verzoeken dat acties (essentieel: wait/wake) worden ondernomen bij geheugentoegangen op specifieke count-augmented stack traces. Elke actie zet ofwel een flag, of wacht tot een flag is gezet, op een door userspace opgegeven index in een gedeelde array van flags.

De mogelijke actietypes zijn:

  • DISTACKWAKE_PRE: vóór de geheugentoegang, zet flag N.
  • DISTACKWAIT: vóór de geheugentoegang, spin-wait tot flag N is gezet.
  • DISTACKWAKE_POST: ná de geheugentoegang, zet flag N.

Met dezelfde ioctl configureert userspace ook een bovengrens voor spin-wait iteraties. Daarnaast zijn er ioctls voor userspace om direct met dezelfde flags te communiceren.

Deze API maakt twee verschillende manieren van delay injection mogelijk: constraint-style delay injection en fully-specified ordering.

Constraint-style delay injection (A-gebeurt-vóór-B)

Userspace kan een reeks "A-gebeurt-vóór-B" constraints instellen. Elke constraint wordt geïmplementeerd als een paar acties in verschillende threads die op dezelfde flag opereren:

  1. DISTACKWAKE_POST voor de toegang die als eerste moet gebeuren.
  2. DISTACKWAIT voor de toegang die als tweede moet gebeuren.

Bij deze aanpak blijft de uitvoeringsvolgorde gedeeltelijk non-deterministisch. Dit is wat de GUI en TUI tools momenteel implementeren. Een voordeel is dat dit intuïtiever is voor eenvoudige gevallen, maar het vereist het registreren van timing-informatie om te tonen in welke volgorde gebeurtenissen ongeveer plaatsvonden. Het maakt de execution trace vaak complexer en vereist vaker meer constraints dan een volledig gespecificeerde volgorde.

Fully specified ordering (context-switch-stijl)

Userspace kan een specifieke volgorde bepalen waarin gebeurtenissen moeten plaatsvinden door punten te kiezen waarop de uitvoering moet overgaan van de ene context naar de andere. Voor het eenvoudige geval met twee contexten betekent dit dat thread A start met een syscall, terwijl thread B begint met het spin-wachten op een flag. Wanneer thread A een bepaalde count-augmented stack trace bereikt, gebruikt thread A een combinatie van DISTACKWAKEPRE en DISTACK_WAIT om de eigen uitvoering te pauzeren en thread B verder te laten gaan; later kan thread B hetzelfde doen om terug te schakelen.

Dit is de aanpak die ik heb gebruikt voor de automatische A-B-A interleaving tester.

Demo: automatische tests

Hieronder volgt een voorbeeld van het gebruik van de automatische A-B-A interleaving tester op een testcase met gelijktijdige dup(5) en close(5) aanroepen:

#define _GNU_SOURCE
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

static int test_fd;
static int dup_res, dup_errno;

void test_setup(void) {
    test_fd = open("/", O_PATH);
}

void test_thread1(void) {
    dup_res = dup(test_fd);
    dup_errno = errno;
}

void test_thread2(void) {
    close(test_fd);
}

void test_end(void) {
    printf("dup(%d) = %d (%s)\n",
           test_fd,
           dup_res,
           dup_res == -1 ? strerror(dup_errno) : "success");
}

De tool ontdekt één volgorde waarbij dup(5) 5 retourneert, wat werkt zoals bedoeld maar een verrassend resultaat kan zijn:

sh-5.3# ./kcov-autorace testcase/demo-dup-vs-close.so
loading kallsyms
RCU state (excluded): base=ffffffff82970100 len=500
loading testcase
initializing kcov
collecting A-B coverage
dup(5) = 6 (success)
testing candidates
dup(5) = -1 (Bad file descriptor)
dup(5) = -1 (Bad file descriptor)
dup(5) = -1 (Bad file descriptor)
dup(5) = 5 (success)
dup(5) = 6 (success)
dup(5) = 6 (success)
dup(5) = 6 (success)
dup(5) = 6 (success)
dup(5) = 6 (success)
dup(5) = 6 (success)
dup(5) = 6 (success)
stats:  injection-failed:0  wait-timeout:7  reordered:4
sh-5.3#

Demo: GUI

Hier is een voorbeeld van het gebruik van de GUI op dezelfde testcase, om handmatig een volgorde af te dwingen waarbij dup(7) 7 retourneert.

Eerst start ik de GUI en voer ik de testcase één keer uit in de guest: sh-5.3# ./kcov-vsock-client testcase/demo-dup-vs-close.so → dup(7) = 8 (success)

Op dit punt zijn er nog geen constraints; dup() en close() racen willekeurig. De GUI toont in welke volgorde de uitvoering plaatsvond via function call graphs van beide threads (thread 1 in het zwart, thread 2 in het rood).

Het aanvinken van "filter to communication points" toont geheugentoegangen in het blauw. Dit zijn communicatiepunten (lees: reads van locaties waar andere threads naar schrijven en writes naar locaties die andere threads benaderen; kfree() telt als een write). Door over een toegang te hoveren, worden alle overlappende toegangen geel gemarkeerd.

Door op een geheugentoegang te klikken, wordt een weergave getoond die gefilterd is op alleen de overlappende toegangen. Door op een functienaam te klikken, opent een broncode-weergave aan de rechterkant, waarin trace-data is verweven. Gegevens geladen door memory reads worden in het rood getoond; writes worden gemarkeerd met een rode "WRITE"; communicatiepunten krijgen de prefix "INTERFERENCE" in het oranje.

Door met de rechtermuisknop op twee geheugentoegangen in de call graph te klikken, kan een ordering constraint worden gemaakt. De kernel zal dan proberen de eerste geselecteerde toegang vóór de tweede te laten plaatsvinden.

In dit specifieke geval heb ik twee constraints gemaakt:

  1. De tweede file descriptor table toegang in fgetfilesrcu() (inlined in fgetfiles()) moet vóór de verwijdering van de entry in fileclosefdlocked() (inlined in fileclosefd()) plaatsvinden. Dit zorgt ervoor dat de lookup in dup() succesvol is voordat de entry door close() wordt gewist.
  2. De spinunlock(&files->filelock) in fileclosefd() moet vóór de spinlock(&files->filelock) in alloc_fd() plaatsvinden, zodat de entry is vrijgegeven voordat dup() zoekt naar een ongebruikte entry.

Na het opnieuw uitvoeren van de testcase met deze constraints: sh-5.3# ./kcov-vsock-client testcase/demo-dup-vs-close.so → dup(7) = 7 (success)

In de UI verschijnt de nieuwe trace met bruine "DELAY INJECTION" lijnen die tonen hoe de constraints zijn toegepast.

Status van de implementatie

  • LLVM: De benodigde patch is opgenomen in LLVM 23.1.0.
  • Linux kernel: De patches zijn nog niet upstream. Ik heb een git branch met mijn patches beschikbaar op GitHub. Om deze tooling te testen, is mijn kernel branch momenteel vereist.

De kernel-patches zijn in een schone staat; de userspace-tooling (met name de GUI) is wat minder gepolijst. De command-line tooling kan slechts twee gelijktijdige threads aan, terwijl de GUI extra execution contexts kan afhandelen (bijv. achtergrondwerk gestart door thread A via de kcov-vsock-client harness).

Toekomstig werk

  • Fully specified orderings voor handmatige tooling: De huidige handmatige tools gebruiken constraint-style injection, maar fully-specified orderings zijn deterministischer.
  • Type-informatie voor leesbare traces: Het zou helpen om te weten welke object-types worden benaderd. Ik heb een feature voorgesteld aan de DWARF-standaard (DWATalloc_type), die is opgenomen in de huidige DWARF 6 draft.
  • Hogere-niveau feedback voor geheugentoegang: Momenteel krijgt userspace geen informatie over de semantiek van locking. Het zou nuttig zijn als de kernel "lock acquired" en "lock about to be released" events zou leveren.
  • Snellere detectie van onmogelijke volgordes (Deadlock detection): Momenteel resulteert een onmogelijke volgorde in een timeout. Integratie met lock debugging-infrastructuur zou dit kunnen versnellen.
  • Fuzzing: Het bouwen van testcases met potentiële communicatiepunten, vergelijkbaar met het Snowboard-project.
  • KCOV-output naar host-shared memory: Momenteel gaat de KCOV-output verloren als de kernel paniekt. Het zou nuttig zijn om de host direct toegang te geven tot de KCOV-output buffer (bijv. via virtiofs met DAX).