"""Trusted Python oracle. Submitted code runs only in child processes.""" import copy import hashlib import json import os import random import re import subprocess import sys import tempfile from pathlib import Path NAMES = ['', 'range', 'absent', 'exists', 'busy', 'locked', 'page', 'syntax', 'limit'] DOMAINS = { 'RESET': [], 'INSPECT': [], 'ATTACH': [(0, 3), (0, 255)], 'DETACH': [(0, 3)], 'WREN': [(0, 3)], 'WRDI': [(0, 3)], 'PROGRAM': [(0, 3), (0, 127), (1, 16), (0, 255)], 'ERASE': [(0, 3), (0, 3)], 'ADVANCE': [(0, 3), (0, 8)], 'READ': [(0, 3), (0, 128), (0, 128)], 'WORD': [(0, 3), (0, 127), (1, 4)], 'STATUS': [(0, 3)]} BASE = {'RESET': [], 'INSPECT': [], 'ATTACH': [0, 10], 'DETACH': [0], 'WREN': [0], 'WRDI': [0], 'PROGRAM': [0, 0, 1, 0], 'ERASE': [0, 0], 'ADVANCE': [0, 1], 'READ': [0, 0, 1], 'WORD': [0, 0, 1], 'STATUS': [0]} EXPECTED_CODES = { 'RESET': {0, 7}, 'INSPECT': {0, 7}, 'ATTACH': {0, 1, 3, 7}, 'DETACH': {0, 1, 2, 4, 7}, 'WREN': {0, 1, 2, 4, 7}, 'WRDI': {0, 1, 2, 4, 7}, 'PROGRAM': {0, 1, 2, 4, 5, 6, 7}, 'ERASE': {0, 1, 2, 4, 5, 7}, 'ADVANCE': {0, 1, 2, 7}, 'READ': {0, 1, 2, 4, 7}, 'WORD': {0, 1, 2, 4, 7}, 'STATUS': {0, 1, 2, 7}} def result(code=0, fields=(), data=b''): return code, NAMES[code], list(fields), bytes(data) def render(item): code, error, fields, data = item return (str(code) + ' ' + str(len(error)) + ':' + error.encode().hex() + ' ' + str(len(fields)) + ''.join(' ' + str(x) for x in fields) + ' ' + str(len(data)) + ':' + data.hex() + '\n').encode() class Bank: def __init__(self): self.chips = [self.blank() for _ in range(4)] @staticmethod def blank(): return [0] * 9 + [bytearray(128)] def call(self, verb, args): before = copy.deepcopy(self.chips) item = self.perform(verb, args) if item[0]: assert self.chips == before, 'oracle failure atomicity' return item def perform(self, verb, args): if verb == 'RESET': self.__init__() return result() if verb == 'INSPECT': return result(fields=[n for c in self.chips for n in c[:9]], data=b''.join(bytes(c[9]) for c in self.chips)) if any(not low <= value <= high for value, (low, high) in zip(args, DOMAINS[verb])): return result(1) if verb in ('READ', 'WORD') and args[1] + args[2] > 128: return result(1) chip = self.chips[args[0]] if verb == 'ATTACH': if chip[0]: return result(3) chip[0] = 1 chip[9][:] = bytes([args[1]]) * 128 return result(fields=args) if not chip[0]: return result(2) if verb == 'STATUS': return result(fields=[args[0]] + chip[:9]) if verb not in ('ADVANCE',) and chip[2]: return result(4) if verb == 'DETACH': self.chips[args[0]] = self.blank() elif verb == 'WREN': chip[1] = 1 elif verb == 'WRDI': chip[1] = 0 elif verb in ('PROGRAM', 'ERASE'): if not chip[1]: return result(5) if verb == 'PROGRAM' and args[1] // 16 != (args[1] + args[2] - 1) // 16: return result(6) chip[1] = 0 if verb == 'PROGRAM': chip[2:7] = [2, 1] + args[1:] else: chip[2:7] = [3, 2, args[1] * 32, 32, 255] chip[7] += 1 elif verb == 'ADVANCE': busy = chip[2] chip[2] = max(0, busy - args[1]) if busy and not chip[2]: for address in range(chip[4], chip[4] + chip[5]): chip[9][address] = chip[9][address] & chip[6] if chip[3] == 1 else 255 chip[3:7] = [0] * 4 chip[8] += 1 return result(fields=args + [chip[2]]) elif verb == 'READ': return result(fields=args, data=chip[9][args[1]:args[1] + args[2]]) elif verb == 'WORD': value = int.from_bytes(chip[9][args[1]:args[1] + args[2]], 'little') return result(fields=args + [value]) return result(fields=args) class Coverage: def __init__(self): self.api_codes = {v: set() for v in DOMAINS} self.cli_codes = {v: set() for v in DOMAINS} self.ends = {kind: set() for kind in ('api', 'cli')} self.outside = {kind: set() for kind in ('api', 'cli')} self.calls = {'api': 0, 'cli': 0} self.failures = {'api': 0, 'cli': 0} self.cli_invocations = 0 def note(self, kind, verb, args, item): if verb not in DOMAINS: return getattr(self, kind + '_codes')[verb].add(item[0]) self.calls[kind] += 1 self.failures[kind] += bool(item[0]) for index, value in enumerate(args): low, high = DOMAINS[verb][index] if value in (low - 1, high + 1, -(2**63), 2**63 - 1): self.outside[kind].add((verb, index, value)) if item[0] == 0: for index, value in enumerate(args): low, high = DOMAINS[verb][index] if value in (low, high): self.ends[kind].add((verb, index, value)) def guard(self): required = {(v, i, x) for v, ds in DOMAINS.items() for i, pair in enumerate(ds) for x in pair} for kind in ('api', 'cli'): assert required <= self.ends[kind], (kind, required - self.ends[kind]) required_outside = {(v, i, x) for v, ds in DOMAINS.items() for i, (lo, hi) in enumerate(ds) for x in (lo-1, hi+1, -(2**63), 2**63-1)} for kind in ('api', 'cli'): assert required_outside <= self.outside[kind], (kind, required_outside - self.outside[kind]) assert self.api_codes == {v: codes - {7} for v, codes in EXPECTED_CODES.items()}, self.api_codes assert self.cli_codes == EXPECTED_CODES, self.cli_codes return {'calls': self.calls, 'failures': self.failures, 'numeric_parameters': sum(map(len, DOMAINS.values())), 'successful_endpoint_count': {k: len(v) for k, v in self.ends.items()}, 'cli_invocations': self.cli_invocations, 'outside_count': {k: len(v) for k, v in self.outside.items()}, 'api_codes': {k: sorted(v) for k, v in self.api_codes.items()}, 'cli_codes': {k: sorted(v) for k, v in self.cli_codes.items()}} def cli(bank, payload, coverage=None): bank.call('RESET', []) physical = processed = syntax = 0 limited = False output = bytearray() # LF only, with a final nonempty no-LF line accepted. lines = payload.split(b'\n') if lines[-1] == b'': lines.pop() for line in lines: physical += 1 if physical > 128: output.extend(render(result(8))); limited = True; break words = re.findall(rb'[^ \t\r]+', line) verb = words[0].decode('ascii', 'replace') if words else '' args = [] valid = verb in DOMAINS and len(words) == len(DOMAINS.get(verb, [])) + 1 if valid: for word in words[1:]: if re.fullmatch(rb'-?[0-9]+', word) is None: valid = False; break value = int(word) if not -(2**63) <= value < 2**63: valid = False; break args.append(value) item = bank.call(verb, args) if valid else result(7) if coverage is not None: coverage.note('cli', verb, args if valid else [], item) output.extend(render(item)); processed += 1; syntax += item[0] == 7 if coverage is not None: coverage.cli_invocations += 1 return (physical, processed, syntax, int(limited)), bytes(output) def text(command): return ' '.join(map(str, command)) def setup(verb, args): seq = [['RESET']] for id in range(4): seq += [['ATTACH', id, 165 + id], ['WREN', id], ['PROGRAM', id, 32, 4, 42], ['ADVANCE', id, 2]] target = args[0] if args and 0 <= args[0] <= 3 else 0 if verb == 'ATTACH': seq.append(['DETACH', target]) if verb in ('PROGRAM', 'ERASE', 'WRDI'): seq.append(['WREN', target]) if verb == 'ADVANCE': seq += [['WREN', target], ['PROGRAM', target, 0, 1, 0]] return seq def plan(): scripts = [] for verb, domains in DOMAINS.items(): if not domains: scripts.append(setup(verb, []) + [[verb]]) for index, (low, high) in enumerate(domains): for value in [low, high, low - 1, high + 1, -(2**63), 2**63 - 1]: args = BASE[verb][:]; args[index] = value if verb == 'PROGRAM': if index == 1: args[2] = 1 if index == 2: args[1] = 0 if verb in ('READ', 'WORD'): if index == 1: args[2] = 0 if verb == 'READ' and value == 128 else 1 if index == 2: args[1] = 0 seq = setup(verb, args) + [[verb] + args] if verb in ('PROGRAM', 'ERASE'): target = args[0] if 0 <= args[0] <= 3 else 0 seq += [['STATUS', target], ['ADVANCE', target, 8], ['READ', target, 0, 128]] scripts.append(seq) # Actual CLI/API paths for every documented error, in nonzero backgrounds. for verb in ('DETACH', 'WREN', 'WRDI', 'PROGRAM', 'ERASE', 'ADVANCE', 'READ', 'WORD', 'STATUS'): args = BASE[verb][:] scripts.append(setup('STATUS', [0]) + [['DETACH', 0], [verb] + args]) for verb in ('DETACH', 'WREN', 'WRDI', 'PROGRAM', 'ERASE', 'READ', 'WORD'): scripts.append(setup('STATUS', [0]) + [['WREN', 0], ['PROGRAM', 0, 0, 1, 0], [verb] + BASE[verb]]) scripts.append(setup('STATUS', [0]) + [['ATTACH', 0, 99]]) for verb in ('PROGRAM', 'ERASE'): scripts.append(setup('STATUS', [0]) + [[verb] + BASE[verb]]) scripts.append(setup('PROGRAM', [0]) + [['PROGRAM', 0, 15, 2, 0]]) # WEL acceptance, repeated writes, erase, canceled permits and atomic page failures. scripts.append(setup('STATUS', [0]) + [ ['WREN', 0], ['PROGRAM', 0, 0, 16, 0], ['STATUS', 0], ['ADVANCE', 0, 1], ['STATUS', 0], ['ADVANCE', 0, 1], ['PROGRAM', 0, 0, 1, 255], ['WREN', 0], ['ERASE', 0, 0], ['STATUS', 0], ['ADVANCE', 0, 3], ['ERASE', 0, 0], ['WREN', 0], ['WRDI', 0], ['WRDI', 0], ['ERASE', 0, 3], ['WREN', 0], ['WREN', 0], ['PROGRAM', 0, 15, 2, 0], ['STATUS', 0], ['PROGRAM', 0, 16, 1, 0], ['ADVANCE', 0, 8], ['READ', 0, 0, 128], ['WORD', 0, 14, 4]]) # Simultaneous predicates exercise each published conditional order. scripts.append(setup('STATUS', [0]) + [ ['WREN', 0], ['PROGRAM', 0, 0, 1, 0], ['ATTACH', 0, 256], ['ATTACH', 0, 1], ['DETACH', 4], ['PROGRAM', 0, 15, 2, 0], ['PROGRAM', 0, 15, 2, 256], ['ERASE', 0, 4], ['READ', 0, 128, 0], ['READ', 0, 128, 1], ['WORD', 0, 127, 2], ['WREN', 0], ['WRDI', 0], ['ADVANCE', 0, 0], ['STATUS', 0], ['ADVANCE', 0, 1], ['ADVANCE', 0, 0], ['ADVANCE', 0, 1], ['PROGRAM', 0, 15, 2, 0], ['DETACH', 0], ['PROGRAM', 0, 15, 2, 0], ['PROGRAM', 0, 128, 1, 0], ['READ', 0, 129, 0], ['ERASE', 0, 4], ['ADVANCE', 0, 9], ['WORD', 0, 128, 1]]) rng = random.Random(570115) for _ in range(12): seq = setup('STATUS', [0]) for _ in range(40): verb = rng.choice(list(DOMAINS)) seq.append([verb] + [rng.randint(low, high) for low, high in DOMAINS[verb]]) scripts.append(seq) return scripts def make_scenes(): coverage = Coverage(); banks = [Bank(), Bank()] commands = []; expected = bytearray() def observe(): for index, bank in enumerate(banks): expected.extend(('I' + str(index) + ' ').encode() + render(bank.call('INSPECT', []))) def api(which, command): verb, *args = command commands.append('A ' + str(which) + ' ' + text(command)) item = banks[which].call(verb, args) coverage.note('api', verb, args, item) expected.extend(b'A ' + render(item)); observe() def invoke(which, payload, flags=0): commands.append('C ' + str(which) + ' ' + str(flags) + ' ' + (payload.hex() or '-')) counters, output = cli(banks[which], payload, coverage) expected.extend(('C ' + ' '.join(map(str, counters)) + ' ' + str(len(output)) + ':' + output.hex() + '\n').encode()) observe() # Two live objects with the same chip ID and different data, retained throughout API work. api(1, ['ATTACH', 0, 73]); api(1, ['WREN', 0]); api(1, ['PROGRAM', 0, 7, 1, 8]) for seq in plan(): for command in seq: api(0, command) api(1, ['STATUS', 0]); api(1, ['ADVANCE', 0, 2]); api(1, ['READ', 0, 0, 128]); api(1, ['WORD', 0, 7, 1]) for index, seq in enumerate(plan()): expanded = [part for command in seq for part in (command, ['INSPECT'])] assert len(expanded) <= 128 invoke(0, ('\n'.join(map(text, expanded)) + ('\n' if index % 2 else '')).encode(), index % 2) # Each fixed verb has missing/extra arity and every numeric position has bad lexical forms. for verb, args in BASE.items(): prefix = '\n'.join(map(text, setup('STATUS', [0]))) + '\n' lines = [text([verb] + args + [0]), text(([verb] + args)[:-1])] for index in range(len(args)): for bad in ['+', '+0', '-', '1x', '0x10', '1e0', '9223372036854775808', '-9223372036854775809', '\x00']: values = args[:]; values[index] = bad lines.append(text([verb] + values)) invoke(0, (prefix + '\nINSPECT\n'.join(lines) + '\nINSPECT\nSTATUS 0\nREAD 0 0 128\n').encode(), 1) invoke(0, b'ATTACH 0 1\nWREN 0\nPROGRAM 0 0 1 0\nADVANCE 0 2\nREAD 0 0 1\n', 1) invoke(0, b'', 1); api(0, ['STATUS', 0]) invoke(0, b'ATTACH -0 000\nREAD 0 0 128\n\n \t\r\nreset\n\xff\nINSPECT\n'.replace(b'\xff', bytes([255])), 1) invoke(1, b'\tATTACH\t3\t000255\r\nWREN 3\nWRDI 3\nSTATUS 3', 1) smoke = b'ATTACH 0 255\nWREN 0\nPROGRAM 0 32 4 42\nADVANCE 0 2\nREAD 0 32 4\n' limit_lines = [b'ATTACH 0 170', b'WREN 0', b'PROGRAM 0 0 1 0', b'ADVANCE 0 2', b'UNKNOWN', b'ERASE 0 0'] limit_lines += [b'STATUS 0'] * (127 - len(limit_lines)) limit_lines += [b'WREN 0', b'PROGRAM 0 0 1 0', b'WRDI 0'] limit = b'\n'.join(limit_lines) + b'\n' invoke(0, b'\n'.join(limit_lines[:128]) + b'\n', 1) invoke(0, limit, 1); api(0, ['STATUS', 0]); api(0, ['READ', 0, 0, 1]) facts = coverage.guard() inputs = [('observer', ('\n'.join(commands) + '\n').encode(), bytes(expected))] for name, payload in [('empty', b''), ('smoke', smoke), ('limit', limit)]: _, output = cli(Bank(), payload) inputs.append((name, payload, output)) facts.update(observer_directives=len(commands), observer_output_bytes=len(expected), scenes=len(inputs)) return inputs, facts def signature(data): return [len(data), hashlib.sha256(data).hexdigest()[:16]] def execute(argv, payload, expected, timeout, metadata, cwd, build=False, name=""): entry = {'n': name, 'p': None, 'a': argv, 'x': None, 't': False, 'i': signature(payload), 'e': signature(expected)} try: proc = subprocess.Popen(argv, cwd=cwd, stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE) entry['p'] = proc.pid try: stdout, stderr = proc.communicate(payload, timeout=timeout) except subprocess.TimeoutExpired: entry['t'] = True; proc.kill(); stdout, stderr = proc.communicate() entry['x'] = proc.returncode except OSError as error: stdout, stderr = b'', str(error).encode() entry['o'] = signature(stdout); entry['r'] = signature(stderr) reasons = [] if entry['t']: reasons.append('timeout') if entry['x'] != 0: reasons.append('exit') if not build and stdout != expected: reasons.append('stdout') if not build and stderr: reasons.append('stderr') entry['f'] = reasons; metadata.append(entry) return not reasons def main(): candidate = Path(sys.argv[1]).resolve() inputs, facts = make_scenes() # Complete all trusted reads/writes before the first compiler subprocess. sources = {name: (candidate / name).read_bytes() for name in ('flash.hpp', 'flash.cpp', 'cli.cpp', 'main.cpp')} observer = Path(__file__).with_name('observer.cc').read_bytes() scratch = Path(tempfile.mkdtemp(prefix='flash-', dir=Path.cwd())) for name, data in sources.items(): (scratch / name).write_bytes(data) (scratch / 'observer.cc').write_bytes(observer) # After this point scratch is never accessed by the trusted Python process. base = ['g++', '-std=c++17', '-O2', '-Wall', '-Wextra', '-pedantic', '-I', str(scratch)] builds = [base + [str(scratch / 'flash.cpp'), str(scratch / 'cli.cpp'), str(scratch / 'observer.cc'), '-o', str(scratch / 'observer')], base + [str(scratch / 'flash.cpp'), str(scratch / 'cli.cpp'), str(scratch / 'main.cpp'), '-o', str(scratch / 'app')]] metadata = []; good = True for index, argv in enumerate(builds): good = execute(argv, b'', b'', 25, metadata, scratch, build=True, name="build" + str(index)) and good if good: for name, payload, expected in inputs: binary = 'observer' if name == 'observer' else 'app' good = execute([str(scratch / binary)], payload, expected, 12, metadata, scratch, name=name) and good packed = json.dumps({'v': 1, 'cwd': str(scratch), 'm': metadata}, separators=(',', ':')) if len(packed.encode()) >= 3900: raise RuntimeError('metadata budget exceeded: ' + str(len(packed.encode()))) sys.stderr.write(packed + '\n') print('PASS' if good else 'FAIL') if __name__ == '__main__': main()