"""Independent state-machine oracle; submitted C executes only in child processes.""" import copy import json from pathlib import Path import random import subprocess import sys import tempfile def plan_result(lines, count): if count < 0 or count > 8 or count and lines is None: return -1 chosen = set() for pin, low, value in lines or []: if not 0 <= pin < 24 or low not in (0, 1) or value not in (0, 1) or pin in chosen: return -1 chosen.add(pin) return 0 def scenario(seed): rng = random.Random(seed) commands = [] def add(name, *args): commands.append([name, *args]) def opened(lines, request=0, direction=0): add('O', len(lines), request, direction, *sum((list(x) for x in lines), [])) def planned(name, lines): add(name, len(lines), *sum((list(x) for x in lines), [])) add('N') add('C') add('A', 0, 0) for lo in (-32768, -1, 0, 1, 2, 32767): for value in (-1, 0, 1, 2): add('L', lo, value) for count in (-32768, -1, 0, 1, 8, 9, 32767): for op in range(4): add('N') add('Z', op, count) valid = [(23, 1, 1), (0, 0, 0), (11, 1, 0), (7, 0, 1)] for field in range(3): for index in range(len(valid)): for invalid in (-1, 2 if field else 24, 32767): lines = [list(item) for item in valid] lines[index][field] = invalid planned('V', lines) planned('M', lines) add('N') opened(lines, request=1, direction=1) for tail in (1, 2, 3): lines = [list(x) for x in valid] lines[tail][0] = lines[0][0] planned('V', lines) planned('M', lines) add('N') opened(lines) for count in range(9): lines = [(p, (p + count) % 2, rng.randrange(2)) for p in rng.sample(range(24), count)] planned('V', lines) planned('M', lines) for phase in ('request', 'direction'): for failure in range(1, 9): add('N') opened(lines, failure if phase == 'request' else 0, failure if phase == 'direction' else 0) add('C') opened(lines) add('C') add('N') opened(lines) opened(lines) add('O', -1, 1, 1) add('A', -1, 1) add('A', 9, 1) add('A', (count + 1) % 9, 0, *([0] * ((count + 1) % 9))) for failure in range(9): values = [rng.randrange(2) for _ in lines] add('A', count, 0, *values) desired = [1 - value for value in values] add('A', count, failure, *desired) for index in range(count): bad = desired[:] bad[index] = rng.choice((-32768, -1, 2, 32767)) add('A', count, failure, *bad) add('C') add('C') opened([]) add('A', 0, 8) add('C') opened(lines) add('C') for blocker in range(4): add('N') add('B', valid[blocker][0], blocker % 2) opened(valid) add('C') # Direct APIs run on active arrays too, including NULL/count precedence. add('N') opened(valid) for operation in range(4): for count in (-1, 0, 1, 8, 9): add('Z', operation, count) for _ in range(180): add('N') count = rng.randrange(9) lines = [(p, rng.randrange(2), rng.randrange(2)) for p in rng.sample(range(24), count)] if count and rng.randrange(3) == 0: add('B', rng.choice(lines)[0], rng.randrange(2)) opened(lines, rng.randrange(9), rng.randrange(9)) for _ in range(5): add('A', count, rng.randrange(9), *(rng.randrange(2) for _ in lines)) add('C') opened(lines) add('C') # Control-plane errors must not enter the library. add('N') for command in [['Q'], ['NN'], ['C', 1], ['V'], ['V', 2, 0, 0, 0], ['M', -1, 1], ['O', 1, -1, 0, 3, 0, 0], ['O', 0, 0, 9], ['A', 0, 9], ['A', 2, 0, 1], ['B', -1, 0], ['B', 24, 1], ['B', 0, 2], ['Z', 4, 0], ['L', 0], ['N', 1]]: if command[0] != 'NN': commands.append(command) opened(valid) add('B', 23, 0) add('C') add('N') return commands def oracle(commands): session = [0, 0, 0, [0] * 8, [0] * 8, [0] * 8] pins = [[0, 0, 0] for _ in range(24)] output = [] for sequence, command in enumerate(commands, 1): name, *a = command events = [] result = -4 def event(op, pin, raw, rc=0): events.append([op, pin, raw, rc]) def release(pin): event('X', pin, -1, 0 if pins[pin][0] == 1 else -1) if pins[pin][0] == 1: pins[pin] = [0, 0, 0] def parsed_plan(offset): count = a[0] if 0 <= count <= 8: if len(a) != offset + count * 3: return False, None return True, [a[i:i+3] for i in range(offset, len(a), 3)] return len(a) == offset, None if name == 'N' and not a: session = [0, 0, 0, [0] * 8, [0] * 8, [0] * 8] pins = [[0, 0, 0] for _ in range(24)] result = 0 elif name == 'C' and not a: if session[0]: for pin in reversed(session[3][:session[1]]): release(pin) session = [0, 0, session[2], [0] * 8, [0] * 8, [0] * 8] result = 0 elif name == 'L' and len(a) == 2: result = a[0] ^ a[1] if a[0] in (0, 1) and a[1] in (0, 1) else -1 elif name in ('O', 'V', 'M') and len(a) >= (3 if name == 'O' else 1): offset = 3 if name == 'O' else 1 accepted, lines = parsed_plan(offset) if name == 'O' and not (0 <= a[1] <= 8 and 0 <= a[2] <= 8): accepted = False if accepted: validation = plan_result(lines, a[0]) if name == 'V': result = validation elif name == 'M': result = sum(1 << item[0] for item in lines or []) if validation == 0 else 0 elif validation: result = -1 elif session[0]: result = -2 else: result = 0 acquired = [] for ordinal, (pin, low, initial) in enumerate(lines or [], 1): failed = ordinal == a[1] or pins[pin][0] != 0 event('R', pin, -1, -1 if failed else 0) if failed: result = -3 break pins[pin] = [1, 0, 0] acquired.append(pin) if result == 0: for ordinal, (pin, low, initial) in enumerate(lines or [], 1): failed = ordinal == a[2] event('D', pin, low ^ initial, -1 if failed else 0) if failed: result = -3 break pins[pin] = [1, 1, low ^ initial] if result: for pin in reversed(acquired): release(pin) else: n = a[0] session = [1, n, session[2] + 1, [item[0] for item in lines or []] + [0] * (8-n), [item[1] for item in lines or []] + [0] * (8-n), [item[2] for item in lines or []] + [0] * (8-n)] elif name == 'A' and len(a) >= 2 and 0 <= a[1] <= 8: count = a[0] accepted = len(a) == (count + 2 if 0 <= count <= 8 else 2) if accepted: values = a[2:] if not 0 <= count <= 8 or any(v not in (0, 1) for v in values): result = -1 elif not session[0]: result = -2 elif count != session[1]: result = -1 else: result = 0 completed = [] for index, value in enumerate(values): pin, low = session[3][index], session[4][index] failed = index + 1 == a[1] event('W', pin, low ^ value, -1 if failed else 0) if failed: result = -3 break pins[pin][2] = low ^ value completed.append(index) if result: for index in reversed(completed): pin, low = session[3][index], session[4][index] raw = low ^ session[5][index] event('W', pin, raw) pins[pin][2] = raw else: session[5][:count] = values elif name == 'B' and len(a) == 2: pin, raw = a if 0 <= pin < 24 and raw in (0, 1) and pins[pin][0] != 1: pins[pin] = [2, 1, raw] result = 0 elif name == 'Z' and len(a) == 2 and 0 <= a[0] <= 3: operation, count = a valid = count == 0 if operation == 0: result = 0 if valid else -1 elif operation == 1: result = 0 elif not valid: result = -1 elif operation == 2: result = -2 if session[0] else 0 if not session[0]: session = [1, 0, session[2]+1, [0]*8, [0]*8, [0]*8] elif not session[0]: result = -2 else: result = 0 if session[1] == 0 else -1 output.append(copy.deepcopy(dict(sequence=sequence, result=result, session=session, pins=pins, events=events, arguments=a))) return output def typed_equal(got, wanted): if type(got) is not type(wanted): return False if isinstance(wanted, dict): return got.keys() == wanted.keys() and all(typed_equal(got[k], wanted[k]) for k in wanted) if isinstance(wanted, list): return len(got) == len(wanted) and all(typed_equal(a, b) for a, b in zip(got, wanted)) return got == wanted def run(): private = Path(__file__).resolve().parent candidate = Path(sys.argv[1]) inputs = [] for seed in (102703, 772209): commands = scenario(seed) rows = [' '.join(map(str, c)) for c in commands] text = '# memory rehearsal\n\n' + '\n'.join((' \t' + row + ' # note') if i % 17 == 0 else row for i, row in enumerate(rows)) inputs.append((text.encode('ascii'), 0, oracle(commands))) # The parser's complete documented domain matches INPUT_BYTES and INPUT_VALUES. baseline = oracle([['N']]) for malformed in (b'L 0 x\n', b'NN\n', b'L 32768 0\n', b'L 1x 0\n', b'Q ' + b'0 ' * 33 + b'\n', b'#' + b'a' * 1023 + b'\n'): inputs.append((b'N\n' + malformed, 2, baseline)) inputs.append((b'N\n#' + b'a' * 1022, 0, baseline)) inputs.append((b'N\nQ ' + b'0 ' * 31 + b'0', 0, oracle([['N'], ['Q'] + [0] * 32]))) files = {name: (private/name).read_bytes() for name in ('array.h', 'simulator.h', 'console.h', 'simulator.c', 'console.c', 'main.c')} files['plan.c'] = (candidate/'src/plan.c').read_bytes() files['session.c'] = (candidate/'src/session.c').read_bytes() scratch = Path(tempfile.mkdtemp(prefix='array-observer-', dir=Path.cwd())) for name, data in files.items(): (scratch/name).write_bytes(data) # All scratch writes finish before the first untrusted child. The parent never # traverses, reads, writes or removes this directory after compiler execution. compiled = subprocess.run(['gcc', '-std=c11', '-O2', '-Wall', '-Wextra', '-Werror', '-I', str(scratch), str(scratch/'plan.c'), str(scratch/'session.c'), str(scratch/'simulator.c'), str(scratch/'console.c'), str(scratch/'main.c'), '-o', str(scratch/'observer')], capture_output=True, timeout=20) if compiled.returncode: sys.stderr.write(compiled.stderr.decode('utf-8', 'replace')) raise ValueError('candidate build failed') checks = 0 for input_bytes, returncode, expected in inputs: completed = subprocess.run([str(scratch/'observer')], input=input_bytes, capture_output=True, timeout=10) if completed.returncode != returncode: sys.stderr.write(completed.stderr.decode('utf-8', 'replace')) raise ValueError('candidate exit status differs') try: observed = [json.loads(line) for line in completed.stdout.decode('utf-8').splitlines()] except (UnicodeDecodeError, ValueError): raise ValueError('candidate observation is not JSON') if not typed_equal(observed, expected): mismatch = next((i for i, (got, want) in enumerate(zip(observed, expected)) if not typed_equal(got, want)), min(len(observed), len(expected))) raise ValueError('observation differs at record ' + str(mismatch+1)) checks += len(expected) print('checks', checks) print('PASS') if __name__ == '__main__': try: run() except (ValueError, OSError, subprocess.SubprocessError) as error: print('FAIL', str(error)) raise SystemExit(1)