"""Protected independent oracle for the original format-buffer exercise.""" import base64 import hashlib import json import math import os from pathlib import Path import random import subprocess import sys import tempfile import time import zlib # Candidate-identity execution only. This program has no business expectations. SUPERVISOR = r''' import base64,ctypes,hashlib,json,os,selectors,signal,subprocess,sys,time,zlib config=json.load(sys.stdin) errors=[] started=time.monotonic() me=os.getpid() tracked={} reaped=[] def table(): result={} for entry in os.scandir('/proc'): if not entry.name.isdigit():continue try: raw=open(entry.path+'/stat','rb').read() fields=raw[raw.rfind(b')')+2:].split() result[int(entry.name)]=(int(fields[1]),int(fields[19]),fields[0].decode()) except (FileNotFoundError,ProcessLookupError):pass return result def closure(tab, identities): # Roots must still have the same starttime; stale PIDs never confer ownership. roots={pid for pid,start in identities.items() if pid in tab and tab[pid][1]==start} found=set(roots) while True: extra={pid for pid,(parent,start,state) in tab.items() if parent in found} new=found|extra if new==found:return found found=new def discover(): tab=table() roots={me:tab[me][1]} roots.update({pid:start for pid,start in tracked.items() if pid in tab and tab[pid][1]==start}) current=closure(tab,roots)-{me} for pid in current:tracked[pid]=tab[pid][1] return tab,current def signal_owned(): tab,current=discover() for pid in current: token=tracked[pid] try: now=table().get(pid) if now is not None and now[1]==token: os.kill(pid,signal.SIGKILL) except ProcessLookupError:pass except BaseException as exc:errors.append('signal:'+type(exc).__name__+':'+str(exc)) def pack(data): if not data:return ['empty'] for n in (1,2,4,16,256): if len(data)>=n and len(data)%n==0 and data==data[:n]*(len(data)//n): return ['repeat',base64.b64encode(data[:n]).decode(),len(data)//n] return ['zlib',base64.b64encode(zlib.compress(data,9)).decode()] process=None leader=None leader_start=None leader_rc=None leader_reaped=False timed_out=False out=bytearray();err=bytearray() try: if ctypes.CDLL(None,use_errno=True).prctl(36,1,0,0,0)!=0: raise OSError(ctypes.get_errno(),'subreaper') process=subprocess.Popen(config['argv'],cwd=config['cwd'],stdin=subprocess.PIPE, stdout=subprocess.PIPE,stderr=subprocess.PIPE,start_new_session=True) leader=process.pid leader_start=table()[leader][1] tracked[leader]=leader_start selector=selectors.DefaultSelector() for stream,tag in ((process.stdout,'out'),(process.stderr,'err')): os.set_blocking(stream.fileno(),False) selector.register(stream,selectors.EVENT_READ,tag) data=base64.b64decode(config['input']) position=0 os.set_blocking(process.stdin.fileno(),False) selector.register(process.stdin,selectors.EVENT_WRITE,'in') deadline=started+config['deadline'] finishing=None while True: # Popen owns its real leader. Poll before reaping adopted descendants. if leader_rc is None: observed=process.poll() if observed is not None: leader_rc=observed;leader_reaped=True;finishing=time.monotonic() if leader_reaped: while True: try: pid,status=os.waitpid(-1,os.WNOHANG) if pid==0:break reaped.append([pid,status]) except ChildProcessError:break tab,current=discover() if time.monotonic()>=deadline and not leader_reaped: timed_out=True signal_owned() if leader_reaped and current: signal_owned() for key,mask in selector.select(.01): stream=key.fileobj if key.data=='in': try: if positiondeadline+5: errors.append('recovery_deadline');break if not leader_reaped: signal_owned() try:leader_rc=process.wait(timeout=1);leader_reaped=True except BaseException as exc:errors.append('wait:'+type(exc).__name__+':'+str(exc)) except BaseException as exc: errors.append('execute:'+type(exc).__name__+':'+str(exc)) finally: if process is not None: try: signal_owned() if not leader_reaped: leader_rc=process.wait(timeout=1);leader_reaped=True until=time.monotonic()+1 while time.monotonic() 0: return base64.b64decode(packed[1], validate=True) * packed[2] if len(packed) == 2 and packed[0] == 'zlib': return zlib.decompress(base64.b64decode(packed[1], validate=True)) raise ValueError('IO encoding') def validate(wire, phase, nonce, argv, deadline): if type(wire) is not dict: raise ValueError('metadata object') required = ('phase nonce argv deadline supervisor_pid leader_pid leader_start leader_rc leader_reaped timeout ' 'controlled_rc uid gid groups elapsed descendants group_absent errors tracked reaped ' 'stdout_len stderr_len stdout_sha stderr_sha stdout stderr stdin_len stdin_sha stdin').split() if any(name not in wire for name in required): raise ValueError('missing metadata') if wire['phase'] != phase or wire['nonce'] != nonce or wire['argv'] != argv or type(wire['argv']) is not list: raise ValueError('metadata binding') if type(wire['deadline']) is not int or wire['deadline'] != deadline: raise ValueError('deadline metadata') for key in ('supervisor_pid', 'leader_pid', 'leader_start'): if type(wire[key]) is not int or wire[key] <= 0: raise ValueError('PID/start metadata') if wire['supervisor_pid'] == wire['leader_pid']: raise ValueError('leader/supervisor identity') for key in ('leader_rc', 'controlled_rc', 'uid', 'gid'): if type(wire[key]) is not int: raise ValueError('integer metadata') expected_uid = 65534 if os.environ.get('ROLLOUT_GRADE_ISOLATION') == 'uid65534' else os.getuid() expected_gid = 65534 if expected_uid == 65534 else os.getgid() expected_groups = [] if expected_uid == 65534 else os.getgroups() if wire['uid'] != expected_uid or wire['gid'] != expected_gid: raise ValueError('execution identity') if type(wire['groups']) is not list or any(type(v) is not int for v in wire['groups']) or wire['groups'] != expected_groups: raise ValueError('execution groups') for key in ('timeout', 'leader_reaped', 'group_absent'): if type(wire[key]) is not bool: raise ValueError('boolean metadata') elapsed = wire['elapsed'] if type(elapsed) not in (int, float) or not math.isfinite(elapsed) or not 0 <= elapsed <= deadline + RECOVERY_MARGIN: raise ValueError('elapsed metadata') if wire['controlled_rc'] != (124 if wire['timeout'] else wire['leader_rc']): raise ValueError('returncode consistency') if wire['timeout'] and (elapsed < deadline or wire['leader_rc'] == 0): raise ValueError('timeout consistency') for key, width in (('tracked', 2), ('reaped', 2), ('descendants', 3)): if type(wire[key]) is not list or any(type(row) is not list or len(row) != width or any(type(value) is not int for value in row) for row in wire[key]): raise ValueError('process list metadata') if any(pid <= 0 or start <= 0 for pid, start in wire['tracked']): raise ValueError('tracked identity range') if any(pid <= 0 or status < 0 for pid, status in wire['reaped']): raise ValueError('reaped identity range') if [wire['leader_pid'], wire['leader_start']] not in wire['tracked']: raise ValueError('tracked leader identity') if type(wire['errors']) is not list or any(type(value) is not str for value in wire['errors']): raise ValueError('exception metadata') io = [] for kind in ('stdout', 'stderr', 'stdin'): if type(wire[kind+'_len']) is not int or wire[kind+'_len'] < 0: raise ValueError('IO length metadata') raw = unpack(wire[kind]) if len(raw) != wire[kind+'_len'] or digest(raw) != wire[kind+'_sha']: raise ValueError('IO digest metadata') io.append(raw) if wire['errors'] or not wire['leader_reaped'] or wire['descendants'] or not wire['group_absent']: raise ValueError('execution cleanup metadata') if wire['timeout'] or wire['leader_rc'] != 0 or wire['controlled_rc'] != 0: raise ValueError('controlled exit %s timeout=%s' % (wire['leader_rc'], wire['timeout'])) return io[:2] EVIDENCE = [] def execute(phase, argv, cwd, input_data, deadline): nonce = os.urandom(12).hex() config = dict(phase=phase, nonce=nonce, argv=argv, cwd=str(cwd), input=base64.b64encode(input_data).decode(), deadline=deadline) wrapper = [sys.executable, '-I', '-c', SUPERVISOR] child = subprocess.Popen(wrapper, stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE) stdout, stderr = child.communicate(json.dumps(config, separators=(',', ':')).encode(), timeout=deadline+RECOVERY_MARGIN+3) # Preserve real wrapper facts before attempting to parse malformed wire. record = dict(phase=phase, wrapper_pid=child.pid, wrapper_rc=child.returncode, wire_len=len(stdout), wire_sha=digest(stdout), wrapper_stderr=base64.b64encode(stderr).decode(), wire_raw=base64.b64encode(zlib.compress(stdout, 9)).decode()) EVIDENCE.append(record) if child.returncode != 0: raise ValueError('supervisor exit '+str(child.returncode)) wire = json.loads(stdout) record['metadata'] = wire record.pop('wire_raw') io = validate(wire, phase, nonce, argv, deadline) if wire['supervisor_pid'] != child.pid or unpack(wire['stdin']) != input_data: raise ValueError('wrapper identity/input binding') return io def escaped(value): return b''.join(bytes([v]) if 32 <= v <= 126 and v not in b'\\=;' else ('\\x%02X' % v).encode() for v in value) def token(value): return value.hex() or '-' def scenarios(): commands = ['Q', 'A 78', 'X', 'C', 'O 128', 'K label 67726f7761626c652d627566', 'Q', 'C', 'C'] commands += ['O 80', 'A '+token(b'first'), 'A '+token(b'-second'*5), 'A '+token(b'1234567890'*3), 'Y 2', 'Y 81', 'X', 'R 80', 'A '+token(b'\0\xff;='), 'E '+token(b'\0\\;=\xff'), 'I count -9223372036854775808', 'C'] commands += ['O 0', 'A -', 'R 0', 'K x -', 'N 1', 'N 0', 'Y 1', 'C', 'O 65536', 'O 48', 'F', 'R 48', 'R 48', 'X', 'A '+token(b'a'*48), 'A 62', 'O 9', 'K - 78', 'K bad-key 78', 'C'] commands += ['O 511', 'E '+token(bytes(range(32))), 'K all '+token(bytes(range(32,64))), 'I hi 9223372036854775807', 'X', 'I zero 0', 'N 0', 'Y 512', 'C'] rng = random.Random(150081) for limit in (1, 17, 256): commands.append('O '+str(limit)) for _ in range(9): choice = rng.randrange(5) value = bytes(rng.randrange(256) for _ in range(rng.randrange(5))) commands.append(['A '+token(value), 'E '+token(value), 'K k '+token(value), 'X', 'Y 257'][choice]) commands += ['C', 'Q'] commands += ['O 65535', 'R 65535', 'A '+token(b'x'*65535), 'A 79', 'X', 'E '+token(b'\0'*16384), 'A -', 'Y 1', 'C', 'Q'] return commands def compare(commands, output): lines = output.decode('ascii').splitlines() if len(lines) != len(commands): raise ValueError('row count %d expected %d' % (len(lines), len(commands))) active = 0 limit = 0 content = b'' fields = 0 capacity = 0 arm = 0 for index, (command, line) in enumerate(zip(commands, lines), 1): parts = line.split() if len(parts) != 14: raise ValueError('row %d protocol' % index) ints = [int(v) for v in parts[:10]] rc, observed_active, length, cap, observed_limit, observed_fields, live, live_bytes, errors, observed_arm = ints raw = bytes.fromhex(parts[10]) if parts[10] != '-' else b'' term, written = int(parts[11]), int(parts[12]) copied = bytes.fromhex(parts[13]) if parts[13] != '-' else b'' kind, *args = command.split() result = 0 next_content = content next_fields = fields needed = 0 copy_want = b'' copy_written = 0 if kind == 'F': arm = 1 elif kind == 'C': active, limit, content, fields, capacity = 0, 0, b'', 0, 0 next_content = content next_fields = fields elif kind == 'Q': pass elif kind == 'O': if active: result = 2 elif int(args[0]) > 65535: result = 1 else: active, limit = 1, int(args[0]) elif not active: result = 2 if kind == 'Y': copy_written, copy_want = 7, b'\xa7'*7 elif kind == 'X': next_content, next_fields = b'', 0 elif kind == 'Y': if int(args[0]) <= len(content): result = 3 copy_written, copy_want = 7, b'\xa7'*7 else: copy_written, copy_want = len(content), content elif kind == 'R': needed = int(args[0]) if needed > limit: result = 3 elif kind == 'N': result = 1 if int(args[0]) != 0 else 0 else: payload = b'' if kind in ('K', 'I'): key = args[0] if key == '-' or len(key) > 24 or not all(c.isascii() and (c.isalnum() or c == '_') for c in key): result = 1 else: value = str(int(args[1])).encode() if kind == 'I' else bytes.fromhex(args[1]) if args[1] != '-' else b'' payload = key.encode()+b'='+escaped(value)+b';' next_fields += 1 else: value = bytes.fromhex(args[0]) if args[0] != '-' else b'' payload = value if kind == 'A' else escaped(value) if result == 0: next_content += payload needed = len(next_content) if needed > limit: result = 3 grows = result == 0 and needed != 0 and needed+1 > capacity if grows and arm: result, arm = 4, 0 if result != 0: next_content, next_fields = content, fields if grows and result == 0: if not needed+1 <= cap <= limit+1: raise ValueError('row %d allocation bound' % index) capacity = cap if (rc, observed_active, length, cap, observed_limit, observed_fields, live, live_bytes, errors, observed_arm, raw, term, written, copied) != ( result, active, len(next_content), capacity, limit, next_fields, int(capacity>0), capacity, 0, arm, next_content, 1, copy_written, copy_want): raise ValueError('row %d %s mismatch rc=%d/%d length=%d/%d cap=%d/%d live=%d/%d' % (index, command[:50], rc, result, length, len(next_content), cap, capacity, live, int(capacity>0))) content, fields = next_content, next_fields return len(commands) def main(): scratch = None failures = [] count = 0 try: context = json.loads(Path(__file__).with_name('context.json').read_text()) commands = scenarios() input_data = ('\n'.join(commands)+'\n').encode() candidate = (Path(sys.argv[1])/'buffer.c').read_bytes() scratch = Path(tempfile.mkdtemp(prefix='resource-format-buffer-', dir='/tmp')) # All support, inputs and candidates are prepared before any child is started. for name, text in context.items(): target = scratch/name target.parent.mkdir(parents=True, exist_ok=True) target.write_text(text) (scratch/'buffer.c').write_bytes(candidate) (scratch/'input.txt').write_bytes(input_data) for directory in [scratch/'docs']: os.chmod(directory, 0o777) compiler = ['gcc', '-std=c11', '-O2', '-Wall', '-Wextra', '-pedantic', 'buffer.c', 'ledger.c', 'observe.c', '-o', 'format-observe'] execute('compiler', compiler, scratch, b'', COMPILER_DEADLINE) output, diagnostics = execute('candidate', [str(scratch/'format-observe')], scratch, input_data, CANDIDATE_DEADLINE) count = compare(commands, output) except BaseException as exc: failures.append('main:'+type(exc).__name__+':'+str(exc)) finally: if scratch is not None: try: execute('cleanup', [sys.executable, '-I', '-c', CLEANUP, str(scratch)], '/', b'', CLEANUP_DEADLINE) except BaseException as exc: failures.append('cleanup:'+type(exc).__name__+':'+str(exc)) try: execute('absence', [sys.executable, '-I', '-c', ABSENCE, str(scratch)], '/', b'', ABSENCE_DEADLINE) except BaseException as exc: failures.append('absence:'+type(exc).__name__+':'+str(exc)) bundle = dict(stages=EVIDENCE, failures=failures, rows=count) encoded = base64.b64encode(zlib.compress(json.dumps(bundle,separators=(',',':')).encode(),9)).decode() print('FORMAT_EVIDENCE '+encoded, file=sys.stderr) if failures or count == 0: print('FAIL '+('; '.join(failures) or 'no observations')) return 1 print('PASS') return 0 if __name__ == '__main__': raise SystemExit(main())