/*
 * DF-5718 evidence rig - overlapping strcpy reliance in the netgraph text
 * parser, a consumer of the kernel's unbounded strcpy
 * (sys/libkern/strcpy.c:36-42):
 *
 *   sys/netgraph/netgraph/ng_parse.c:1572  strcpy(p, p + 1);   (dst == src-1)
 *   sys/netgraph/netgraph/ng_parse.c:1621  strcpy(p, v);       (v > p)
 *   sys/netgraph7/netgraph/ng_parse.c:1764 strcpy(p, p + 1);
 *   sys/netgraph7/netgraph/ng_parse.c:1813 strcpy(p, v);
 *
 * The parser below is the VERBATIM ng_get_string_token() algorithm from
 * sys/netgraph/netgraph/ng_parse.c:1548-1625. Mechanical deviations only
 * (marked DEV): kmalloc->malloc, kfree->free, a guard-page placement
 * option, and strcpy routed through rig_strcpy(). Parsing logic is
 * UNCHANGED.
 *
 * Three compile modes:
 *
 *   MODE=INTREE  rig_strcpy = the VERBATIM sys/libkern/strcpy.c:36-42
 *                byte-forward loop, instrumented only to count overlapping
 *                src/dst invocations. Build with -O2 -fno-builtin so the
 *                compiler cannot fold the loop away.
 *                PASS = parse output correct AND overlap count > 0:
 *                the shipped algorithm really does call strcpy on
 *                overlapping regions and is only correct because strcpy.c
 *                is a forward byte loop.
 *
 *   MODE=LIBC    rig_strcpy = plain strcpy (libc / gcc builtin). Build with
 *                -O2 (no -fno-builtin) - the realistic "someone swapped in
 *                an optimized strcpy" scenario (cf. the in-tree precedent
 *   sys/dev/raid/hptrr/osm.h:168:  #define strcpy(dst, src)
 *				    __builtin_strcpy((dst), (src))
 *                ). Any output difference vs INTREE is the divergence.
 *
 *   MODE=BLOCK   rig_strcpy = a model of a vectorized/block-store strcpy
 *                (16-byte block loads and stores; the final partial block
 *                is stored WHOLE, i.e. bytes past the NUL are written -
 *                the documented behavior of SSE/AVX strcpy variants).
 *                The cbuf allocation is EXACTLY the kernel's size
 *                (kmalloc(strlen(s + start)), ng_parse.c:1559 - note: no
 *                "+1"; the leading-quote slot is the only slack), placed
 *                at the very end of a page followed by a PROT_NONE guard
 *                page.  EXPECTED: SIGSEGV in a forked child - the
 *                past-the-NUL block store crosses the guard page, i.e. an
 *                out-of-bounds write on the exact-size allocation.
 *
 * build: cc -O2 -fno-builtin -DMODE=1 -o rig_intree overlap_rig.c
 *        cc -O2             -DMODE=2 -o rig_libc   overlap_rig.c
 *        cc -O2             -DMODE=3 -o rig_block  overlap_rig.c
 * run:   ./rig_intree ; ./rig_libc ; ./rig_block
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#if !defined(MODE)
#define MODE 1
#endif
#define MODE_INTREE	1
#define MODE_LIBC	2
#define MODE_BLOCK	3
#define MODE_FIXED	4

#if MODE != MODE_INTREE && MODE != MODE_LIBC && MODE != MODE_BLOCK && MODE != MODE_FIXED
#error "MODE must be 1 (INTREE), 2 (LIBC), 3 (BLOCK) or 4 (FIXED)"
#endif

#if MODE == MODE_BLOCK
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <signal.h>
#endif

/* ------------------------------------------------------------------ */
/* MODE=INTREE: VERBATIM sys/libkern/strcpy.c:36-42 + overlap counter */
/* ------------------------------------------------------------------ */

#if MODE == MODE_INTREE
static unsigned long overlap_calls;	/* DEV: instrumentation           */

static char *
rig_strcpy(char *to, const char *from)	/* == sys/libkern/strcpy.c:36 */
{
	char *save = to;
	const char *src_start = from;		/* DEV: instrumentation only */
	size_t srclen = strlen(from);		/* DEV: instrumentation only */

	for (; (*to = *from) != 0; ++from, ++to)
		;
	/* DEV: count restrict-contract violations (range intersection):
	 * dst = [save, save+srclen), src = [src_start, src_start+srclen] */
	if (save < src_start + srclen + 1 &&
	    src_start < save + srclen)
		overlap_calls++;
	return (save);
}
#endif

#if MODE == MODE_LIBC
#define rig_strcpy strcpy			/* libc / gcc builtin          */
#endif

#if MODE == MODE_FIXED
/* only the two OVERLAP sites are switched to memmove (as in fix.diff);
 * the initial non-overlap copy keeps the verbatim in-tree strcpy. */
static char *
rig_strcpy(char *to, const char *from)	/* == sys/libkern/strcpy.c:36 */
{
	char *save = to;

	for (; (*to = *from) != 0; ++from, ++to)
		;
	return (save);
}
#endif

/* ------------------------------------------------------------------ */
/* MODE=BLOCK: model of a vectorized block-store strcpy               */
/* ------------------------------------------------------------------ */

#if MODE == MODE_BLOCK
static char *
rig_strcpy(char *dst, const char *src)
{
	size_t i = 0;

	for (;;) {
		char buf[16];
		int done;

		memcpy(buf, src + i, sizeof(buf));	/* block LOAD  */
		done = (memchr(buf, 0, sizeof(buf)) != NULL);
		memcpy(dst + i, buf, sizeof(buf));	/* block STORE */
		if (done)
			break;
		i += sizeof(buf);
	}
	return (dst);
}
#endif

/* ------------------------------------------------------------------ */
/* VERBATIM ng_get_string_token() - sys/netgraph/netgraph/ng_parse.c  */
/* 1548-1625 (mechanical deviations marked DEV)                        */
/* ------------------------------------------------------------------ */

#if MODE == MODE_BLOCK
static int use_guard = 1;			/* DEV: guard-page placement   */
#endif

static void *
rig_alloc(size_t n)		/* DEV: stands for kmalloc(strlen(s+start)) */
{
#if MODE == MODE_BLOCK
	size_t ps = 4096;
	char *base = mmap(NULL, 2 * ps, PROT_READ | PROT_WRITE,
			  MAP_ANON | MAP_PRIVATE, -1, 0);

	if (base == MAP_FAILED) {
		perror("mmap");
		exit(2);
	}
	if (mprotect(base + ps, ps, PROT_NONE) < 0) {
		perror("mprotect");
		exit(2);
	}
	return (base + ps - n);	/* buffer ENDS at the guard page */
#else
	return (malloc(n));
#endif
}

static char *					/* == ng_parse.c:1548 */
ng_get_string_token_rig(const char *s, int *startp, int *lenp)
{
	char *cbuf, *p;
	int start, off;

	while (isspace((unsigned char)s[*startp]))
		(*startp)++;
	start = *startp;
	if (s[*startp] != '"')
		return (NULL);
	cbuf = rig_alloc(strlen(s + start));		/* ng_parse.c:1559 */
	if (cbuf == NULL)
		return (NULL);
	rig_strcpy(cbuf, s + start + 1);		/* ng_parse.c:1562 */
	for (off = 1, p = cbuf; *p != '\0'; off++, p++) {
		if (*p == '"') {
			*p = '\0';
			*lenp = off + 1;
			return (cbuf);
		} else if (p[0] == '\\' && p[1] != '\0') {
			int x, k;
			char *v;

#if MODE == MODE_FIXED
			/* the fix.diff treatment: overlap-safe memmove */
			memmove(p, p + 1, strlen(p + 1) + 1);
#else
			rig_strcpy(p, p + 1);		/* ng_parse.c:1572 */
#endif
			v = p;
			switch (*p) {
			case 't':
				*v = '\t';
				off++;
				continue;
			case 'n':
				*v = '\n';
				off++;
				continue;
			case 'r':
				*v = '\r';
				off++;
				continue;
			case 'v':
				*v =  '\v';
				off++;
				continue;
			case 'f':
				*v = '\f';
				off++;
				continue;
			case '"':
				*v =  '"';
				off++;
				continue;
			case '0': case '1': case '2': case '3':
			case '4': case '5': case '6': case '7':
				for (x = k = 0;
				    k < 3 && *v >= '0' && *v <= '7'; v++) {
					x = (x << 3) + (*v - '0');
					off++;
				}
				*--v = (char)x;
				break;
			case 'x':
				for (v++, x = k = 0;
				    k < 2 && isxdigit((unsigned char)*v); v++) {
					x = (x << 4) +
					    (isdigit((unsigned char)*v) ?
					      (*v - '0') :
					      (tolower((unsigned char)*v) - 'a' + 10));
					off++;
				}
				*--v = (char)x;
				break;
			default:
				continue;
			}
#if MODE == MODE_FIXED
			/* the fix.diff treatment: overlap-safe memmove */
			memmove(p, v, strlen(v) + 1);
#else
			rig_strcpy(p, v);		/* ng_parse.c:1621 */
#endif
		}
	}
	return (NULL);		/* no closing quote */
}

/* ------------------------------------------------------------------ */

/*
 * Parser input: a netgraph text-format quoted string containing every
 * escape class:  \t (strcpy(p,p+1) only), \x41C (strcpy(p,p+1) AND
 * strcpy(p,v)), \" (p+1 only), \\ (p+1 only).
 *
 * NOTE on \x41C: the kernel's hex-escape loop (ng_parse.c:1609-1616)
 * declares "k < 2" but NEVER INCREMENTS k, so it consumes ALL consecutive
 * hex digits: "41C" -> 0x41c -> truncated to (char)0x1c. The octal loop
 * (ng_parse.c:1599-1606) has the same quirk. Our expected string matches
 * the REAL kernel semantics, quirk included.
 */
static const char input[] = "\"A\\tB\\x41C\\\"D\\\\E\"";
static const char expect[] = "A\tB\x1c\"D\\E";

static void
hexdump_line(const char *tag, const char *s)
{
	printf("%s: [", tag);
	for (; *s; s++)
		printf(*s >= 0x20 && *s < 0x7f ? "%c" : "\\x%02x",
		    (unsigned char)*s);
	printf("]\n");
}

int
main(void)
{
	int start = 0, len;

#if MODE == MODE_BLOCK
	/* BLOCK: the parse must ONLY run in the child (it is expected to
	 * die on the guard page). */
	fflush(stdout);
	{
		pid_t pid = fork();

		if (pid == 0) {
			char *r2 = ng_get_string_token_rig(input, &start, &len);

			printf("BLOCK : child survived (no OOB store) - %s\n",
			    r2 ? r2 : "(null)");
			_exit(0);
		}
		{
			int status;

			if (waitpid(pid, &status, 0) < 0) {
				perror("waitpid");
				return (2);
			}
			if (WIFSIGNALED(status) &&
			    WTERMSIG(status) == SIGSEGV) {
				printf("BLOCK : child killed by SIGSEGV:"
				    " block-store strcpy's past-the-NUL store"
				    " crossed the guard page\n");
				printf("BLOCK : cbuf allocated at exactly the"
				    " kernel size (ng_parse.c:1559 has no +1)"
				    " => equivalent to a kernel heap OOB"
				    " write\n");
				printf("RESULT : overlap/past-NUL reliance"
				    " CONFIRMED - the in-tree byte-forward"
				    " strcpy is load-bearing\n");
				return (0);
			}
			printf("BLOCK : FAIL - child status %d (no SIGSEGV)\n",
			    status);
			return (1);
		}
	}
#else	/* MODE_LIBC / MODE_FIXED */
	{
		char *res = ng_get_string_token_rig(input, &start, &len);

		if (res == NULL) {
			printf("MODE=%d: parser returned NULL\n", MODE);
			return (1);
		}
#if MODE == MODE_INTREE
		printf("INTREE: input    : %s\n", input);
		hexdump_line("INTREE: parsed  ", res);
		hexdump_line("INTREE: expected", expect);
		printf("INTREE: parse correct with verbatim byte-forward"
		    " strcpy: %s\n",
		    strcmp(res, expect) == 0 ? "YES" : "NO");
		printf("INTREE: overlapping strcpy invocations (restrict"
		    " violations at ng_parse.c:1572/1621): %lu\n",
		    overlap_calls);
		return (strcmp(res, expect) == 0 && overlap_calls > 0 ?
		    0 : 1);
#elif MODE == MODE_FIXED
		hexdump_line("FIXED  : parsed  ", res);
		hexdump_line("FIXED  : expected", expect);
		printf("FIXED  : memmove treatment output identical to"
		    " in-tree semantics: %s\n",
		    strcmp(res, expect) == 0 ? "YES" : "NO");
		return (strcmp(res, expect) == 0 ? 0 : 1);
#else	/* MODE_LIBC */
		hexdump_line("LIBC  : parsed  ", res);
		hexdump_line("LIBC  : expected", expect);
		printf("LIBC  : divergence vs in-tree strcpy: %s\n",
		    strcmp(res, expect) == 0 ? "none" : "DETECTED");
		return (0);
#endif
	}
#endif
}