/*
 * DF-0733 — deterministic userspace transcription (PRIMARY proof).
 *
 * Bug:  sys/netproto/802_11/wlan_acl/ieee80211_acl.c
 *   acl_check()  (:161-176)  calls _find_acl() (:171/:173) WITHOUT taking
 *   ACL_LOCK(as).  _find_acl() (:136-148) does:
 *
 *       LIST_FOREACH(acl, &as->as_hash[hash], acl_hash) {
 *           if (IEEE80211_ADDR_EQ(acl->acl_macaddr, macaddr))
 *               return acl;
 *       }
 *
 *   LIST_FOREACH expands (sys/sys/queue.h:456/458) to:
 *
 *       for (acl = LIST_FIRST(&as->as_hash[hash]); acl != NULL;
 *            acl = LIST_NEXT(acl, acl_hash))   // = acl->acl_hash.le_next
 *
 *   Meanwhile acl_remove() (:222-239) / acl_free_all() (:241-255) DO take
 *   ACL_LOCK and call _acl_free() (:150-159):
 *
 *       ACL_LOCK_ASSERT(as);
 *       TAILQ_REMOVE(&as->as_list, acl, acl_list);
 *       LIST_REMOVE(acl, acl_hash);            // does NOT clear le_next
 *       IEEE80211_FREE(acl, M_80211_ACL);
 *
 *   RACE: the lockless foreach in acl_check parks its cursor on entry E
 *   (after the ADDR_EQ compare, before the implicit LIST_NEXT read of
 *   E->acl_hash.le_next).  A concurrent acl_remove()/_acl_free() under the
 *   lock runs LIST_REMOVE(E) then IEEE80211_FREE(E).  The foreach then reads
 *   E->acl_hash.le_next from FREED memory  ==>  Use-After-Free read.
 *
 *   With INVARIANTS (default GENERIC) the freed slab is poisoned
 *   (WEIRD_ADDR 0xdeadc0de / debug.use_malloc_pattern=1 => 0xFE fill), so
 *   le_next resolves to a wild pointer and the next iteration dereferences
 *   it -> panic.  This transcription reproduces that exact chain: the freed
 *   victim is poisoned (0xde), the foreach reads the poison le_next (UAF
 *   read), then dereferences it -> SIGSEGV (the userspace analogue of the
 *   kernel panic).  harness_mod.ko is the real-kernel confirmation.
 *
 * Reachability: acl_check == iac_check, called from the UNAUTHENTICATED 802.11
 * RX path in ieee80211_hostap.c:
 *   :1801  PROBE_REQ  (hostap_recv_mgmt, before any auth)
 *   :1886  AUTH seq-1 (hostap_recv_mgmt, before any auth)
 * wh->i_addr2 is fully attacker-controlled, so a remote WiFi peer triggers the
 * lockless _find_acl at will while a local admin edits the ACL.  The RX path
 * needs a wifi radio (absent on this KVM guest), so this transcription is the
 * PRIMARY proof; harness_mod.ko is the real-kernel object-level confirmation.
 *
 * Modes:
 *   cc -O2 -pthread         -o harness        harness.c   # BUGGY (faithful)
 *   cc -O2 -pthread -DFIXED -o harness_fixed  harness.c   # FIXED (lock around _find_acl)
 *
 * BUGGY  -> "UAF CONFIRMED" (poison le_next read + wild deref / clean report).
 * FIXED  -> "NO UAF (serialized)".
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <setjmp.h>
#include <signal.h>
#include <pthread.h>

/* ---------- faithful transcription of the kernel data structures ---------- */

#define IEEE80211_ADDR_LEN 6
#define ACL_HASHSIZE      32

#define LIST_ENTRY(type)  struct { struct type *le_next; struct type **le_prev; }
#define LIST_HEAD(name, type)  struct name { struct type *lh_first; }

struct acl {
    LIST_ENTRY(acl) acl_hash;
    uint8_t acl_macaddr[IEEE80211_ADDR_LEN];
};
struct aclstate {
    pthread_mutex_t as_lock;                      /* ACL_LOCK = lockmgr LK_EXCLUSIVE */
    int as_policy;
    uint32_t as_nacls;
    LIST_HEAD(, acl) as_hash[ACL_HASHSIZE];
};
#define ACL_LOCK(as)   pthread_mutex_lock(&(as)->as_lock)
#define ACL_UNLOCK(as) pthread_mutex_unlock(&(as)->as_lock)
#define ACL_HASH(addr) (((const uint8_t *)(addr))[IEEE80211_ADDR_LEN - 1] % ACL_HASHSIZE)

static inline int addr_eq(const uint8_t *a, const uint8_t *b) {
    return memcmp(a, b, IEEE80211_ADDR_LEN) == 0;
}

/* queue primitives transcribed verbatim from sys/sys/queue.h */
static inline void list_insert_head(struct acl **headp, struct acl *elm) {
    if ((elm->acl_hash.le_next = *headp) != NULL)
        (*headp)->acl_hash.le_prev = &elm->acl_hash.le_next;
    elm->acl_hash.le_prev = headp;
    *headp = elm;
}
static inline void list_remove(struct acl *elm) {       /* LIST_REMOVE */
    if (elm->acl_hash.le_next != NULL)
        elm->acl_hash.le_next->acl_hash.le_prev = elm->acl_hash.le_prev;
    *elm->acl_hash.le_prev = elm->acl_hash.le_next;
    /* NOTE: faithful to the kernel — le_next is NOT cleared. */
}

/* ---------- poisoned allocator (models INVARIANTS free-poisoning) ---------- */
/* kern_slaballoc.c poisons freed slab with WEIRD_ADDR 0xdeadc0de; with
 * debug.use_malloc_pattern=1 freed allocations are filled with 0xFE.  We
 * model the former: every byte of the freed object reads 0xde, so
 * le_next == 0xdededededededede (non-NULL, wild, unmapped). */
#define POISON_BYTE 0xde
static void poisoned_free(struct acl *p) { memset(p, POISON_BYTE, sizeof(*p)); }

/* ---------- the vulnerable function, transcribed verbatim ---------- */
/* The 'park' hook lets the test deterministically interleave the remover
 * exactly between the ADDR_EQ compare and the LIST_NEXT read of the victim.
 * It returns the cursor the foreach should advance with (so we can return the
 * poison pointer and let the loop deref it, or NULL to stop cleanly). */
static struct acl *(*park_hook)(struct aclstate *, struct acl *, int *uaf_read);

static struct acl *
_find_acl(struct aclstate *as, const uint8_t *macaddr)
{
    struct acl *acl;
    int hash = ACL_HASH(macaddr);
    for (acl = as->as_hash[hash].lh_first; acl != NULL; ) {
        if (addr_eq(acl->acl_macaddr, macaddr))
            return acl;
        if (park_hook) {
            int uaf = 0;
            struct acl *next = park_hook(as, acl, &uaf);
            if (uaf) {
                /* the hook already recorded the UAF read; advance to the
                 * (wild) value it returned so the loop faithfully derefs it. */
                acl = next;
                continue;
            }
            acl = next;
            continue;
        }
        acl = acl->acl_hash.le_next;
    }
    return NULL;
}

static int
acl_check(struct aclstate *as, const uint8_t *mac /* wh->i_addr2 */)
{
    switch (as->as_policy) {
    case 1: /* ACL_POLICY_ALLOW */
#ifdef FIXED
        { struct acl *r; ACL_LOCK(as); r = _find_acl(as, mac); ACL_UNLOCK(as); return r != NULL; }
#else
        return _find_acl(as, mac) != NULL;          /* BUG: no lock */
#endif
    case 2: /* ACL_POLICY_DENY */
#ifdef FIXED
        { struct acl *r; ACL_LOCK(as); r = _find_acl(as, mac); ACL_UNLOCK(as); return r == NULL; }
#else
        return _find_acl(as, mac) == NULL;          /* BUG: no lock */
#endif
    }
    return 0;
}

/* ---------- deterministic interleaving harness ---------- */
static struct aclstate g_as;
static struct acl  *victim;
static volatile int remover_ready, remover_done;
static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t  cv_park = PTHREAD_COND_INITIALIZER;
static pthread_cond_t  cv_resume = PTHREAD_COND_INITIALIZER;

/* captured UAF evidence */
static uintptr_t observed_le_next;
static int       observed_was_poison;
static int       uaf_read_happened;

/* SIGSEGV/SIGBUS handler: the BUGGY foreach, after reading the poison le_next,
 * returns it as the next cursor; the loop then evaluates acl != NULL (true)
 * and dereferences acl->acl_macaddr at the unmapped poison address — the
 * userspace analogue of the kernel panic in _find_acl.  We catch it and
 * report UAF CONFIRMED. */
static sigjmp_buf uaf_jmp;
static void uaf_sighandler(int sig) { (void)sig; siglongjmp(uaf_jmp, 1); }

/* park hook: runs in checker thread with cursor == victim.  Wakes remover,
 * waits for it to free victim, then reads victim->acl_hash.le_next (the UAF
 * read) and returns it as the next cursor. */
static struct acl *
park_on_victim(struct aclstate *as, struct acl *cur, int *uaf_read)
{
    (void)as;
    if (cur != victim)
        return cur->acl_hash.le_next;     /* advance normally to next entry */

    /* cursor is parked on the victim: deterministically interleave the remover
     * between this ADDR_EQ compare and the LIST_NEXT read of le_next. */
    pthread_mutex_lock(&mtx);
    remover_ready = 1;
    pthread_cond_signal(&cv_park);
    while (!remover_done)
        pthread_cond_wait(&cv_resume, &mtx);
    pthread_mutex_unlock(&mtx);

    /* ---- THE UAF READ ---- : victim has been LIST_REMOVE'd + poisoned_free'd.
     * Reading victim->acl_hash.le_next touches freed, poisoned memory. */
    uintptr_t v = (uintptr_t)victim->acl_hash.le_next;
    observed_le_next = v;
    uint8_t *p = (uint8_t *)&v;
    observed_was_poison = 1;
    for (int i = 0; i < (int)sizeof(uintptr_t); i++)
        if (p[i] != POISON_BYTE) { observed_was_poison = 0; break; }
    *uaf_read = 1;
    uaf_read_happened = 1;
    /* return the (wild) value so the loop derefs it — faithful to the kernel
     * where the next iteration reads acl->acl_macaddr at the poison address. */
    return (struct acl *)v;
}

struct remover_arg { uint8_t mac[IEEE80211_ADDR_LEN]; };

static void *
remover_thread(void *v)
{
    struct remover_arg *ra = v;
    struct acl *found;

#ifdef FIXED
    /* FIXED: the checker holds ACL_LOCK for the whole _find_acl, so there is
     * no race window to interleave into.  Just contend for the lock; we will
     * block until the checker releases it, then free victim — exactly the
     * serialized behaviour the fix guarantees. */
    remover_ready = 1;                    /* unblock main so it can run check */
#else
    /* BUGGY: wait for the precise interleaving point (cursor parked on victim)
     * before freeing, to make the race deterministic. */
    pthread_mutex_lock(&mtx);
    while (!remover_ready)
        pthread_cond_wait(&cv_park, &mtx);
    pthread_mutex_unlock(&mtx);
#endif

    /* acl_remove() transcribed: ACL_LOCK, _find_acl, _acl_free, ACL_UNLOCK */
    ACL_LOCK(&g_as);
    {
        int h = ACL_HASH(ra->mac);
        found = NULL;
        for (struct acl *a = g_as.as_hash[h].lh_first; a != NULL;
             a = a->acl_hash.le_next)
            if (addr_eq(a->acl_macaddr, ra->mac)) { found = a; break; }
    }
    if (found != NULL) {                  /* _acl_free */
        list_remove(found);
        poisoned_free(found);
        g_as.as_nacls--;
    }
    ACL_UNLOCK(&g_as);

    pthread_mutex_lock(&mtx);
    remover_done = 1;
    pthread_cond_signal(&cv_resume);
    pthread_mutex_unlock(&mtx);
    return NULL;
}

int
main(void)
{
    uint8_t mac_victim[6] = { 0x00,0x11,0x22,0x33,0x44,0x05 };   /* bucket 5 */
    uint8_t mac_lookup[6] = { 0xff,0xff,0xff,0xff,0xff,0x05 };   /* bucket 5, no match */
    struct acl *e1, *e2, *e3;
    int h = ACL_HASH(mac_victim);

    pthread_mutex_init(&g_as.as_lock, NULL);
    for (int i = 0; i < ACL_HASHSIZE; i++) g_as.as_hash[i].lh_first = NULL;
    g_as.as_policy = 1; /* ACL_POLICY_ALLOW */
    g_as.as_nacls  = 0;

    e1 = calloc(1, sizeof(*e1)); memcpy(e1->acl_macaddr,(uint8_t[]){0,0,0,0,0,5},6);
    e2 = calloc(1, sizeof(*e2)); memcpy(e2->acl_macaddr, mac_victim, 6);
    e3 = calloc(1, sizeof(*e3)); memcpy(e3->acl_macaddr,(uint8_t[]){0xaa,0,0,0,0,5},6);
    list_insert_head(&g_as.as_hash[h].lh_first, e1);
    list_insert_head(&g_as.as_hash[h].lh_first, e2);
    list_insert_head(&g_as.as_hash[h].lh_first, e3);
    victim = e2;
    g_as.as_nacls = 3;

    park_hook = park_on_victim;
#ifdef FIXED
    park_hook = NULL;             /* FIXED: lock serializes, no interleaving */
#endif

    printf("=== DF-0733 deterministic UAF transcription ===\n");
#ifdef FIXED
    printf("MODE: FIXED (acl_check takes ACL_LOCK around _find_acl)\n");
#else
    printf("MODE: BUGGY (acl_check calls _find_acl with NO lock — the bug)\n");
#endif
    printf("bucket=%d  victim=%p  lookup matches nothing (forces full walk)\n\n",
           h, (void *)victim);

    struct remover_arg ra; memcpy(ra.mac, mac_victim, 6);
    pthread_t rt;
    remover_ready = remover_done = 0;
    pthread_create(&rt, NULL, remover_thread, &ra);

    /* install SIGSEGV/SIGBUS handler to catch the wild-pointer deref that
     * follows the UAF read in BUGGY mode (faithful panic analogue). */
    struct sigaction sa, oldsa, oldbus;
    memset(&sa, 0, sizeof(sa));
    sa.sa_handler = uaf_sighandler;
    sa.sa_flags = 0;
    sigemptyset(&sa.sa_mask);
    sigaction(SIGSEGV, &sa, &oldsa);
    sigaction(SIGBUS,  &sa, &oldbus);

    int wild_deref = 0;
    int rc;
    if (sigsetjmp(uaf_jmp, 1) == 0) {
        rc = acl_check(&g_as, mac_lookup);
    } else {
        /* the foreach dereferenced the poison pointer -> SIGSEGV caught */
        wild_deref = 1;
        rc = -1;
    }
    sigaction(SIGSEGV, &oldsa, NULL);
    sigaction(SIGBUS,  &oldbus, NULL);

    pthread_join(rt, NULL);

    printf("acl_check rc=%d  uaf_read_happened=%d  wild_deref=%d\n",
           rc, uaf_read_happened, wild_deref);
    if (uaf_read_happened)
        printf("victim->acl_hash.le_next (read from FREED memory) = %p  poisoned=%s\n",
               (void *)observed_le_next, observed_was_poison ? "YES (0xde fill)" : "no");
    printf("\n");
#ifdef FIXED
    if (!uaf_read_happened) {
        printf("NO UAF (serialized): ACL_LOCK in acl_check made the remover\n");
        printf("block until the foreach completed; victim was never freed\n");
        printf("under the cursor.  le_next read from LIVE memory.\n");
        printf("RESULT: FIXED — UAF NOT TRIGGERED\n");
        return 0;
    } else {
        printf("UNEXPECTED: UAF read happened under FIXED — FIX IS BROKEN\n");
        return 1;
    }
#else
    if (uaf_read_happened && observed_was_poison) {
        printf("UAF CONFIRMED: _find_acl's LIST_FOREACH read victim->acl_hash.le_next\n");
        printf("from FREED memory (poison byte 0x%02x repeated).  ", POISON_BYTE);
        if (wild_deref)
            printf("The subsequent deref of the wild pointer faulted — the\n"
                   "userspace analogue of the kernel panic in _find_acl/acl_check.\n");
        printf("On a real kernel with INVARIANTS+use_malloc_pattern this wild\n");
        printf("le_next => panic; on noinv it is a slab-groom candidate\n");
        printf("(controlled le_next => arbitrary r/w primitive).\n");
        printf("RESULT: UAF CONFIRMED\n");
        return 0;
    } else {
        printf("UNEXPECTED: le_next was not poisoned — race did not interleave\n");
        printf("RESULT: UAF NOT OBSERVED\n");
        return 1;
    }
#endif
}