File size: 10,082 Bytes
f8c1da5 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #!/usr/bin/env python3
"""Compose stopped native area/cluster loops and probe leaf access guards."""
import gzip
import hashlib
import json
from pathlib import Path
import re
from analyze_area_queries import run,site
from analyze_chat_paths import native_string
from analyze_collision_composition import get_word,put_word
from analyze_engine_control import control_flow
from analyze_native import elf
from analyze_qvm import write_json
from analyze_vm_extensions import native_functions,verified
def sequence(pattern,count):
if pattern=='absent':return [-1]*count,[-1]*count
if pattern=='duplicates':return [1]*count,[7]*count
if pattern=='mixed':return [[1,2,3,-1][i%4] for i in range(count)],[[-1,7,7,9][i%4] for i in range(count)]
if pattern=='unique':return list(range(1,count+1)),list(range(100,100+count))
raise ValueError('unknown metadata pattern')
def main():
out={'native':{},'limitations':'Synthetic stopped native instruction compositions. Every area/cluster '
'return and diagnostic continuation is supplied; original callees, BSP traversal and original '
'runtime never execute. Leaf accessor probes omit PUSH/POP stack traffic explicitly and stop '
'before error calls/returns. ABI/clobber/lifetime, actual maps/counts, complete metadata consumers '
'and all-platform conformance remain open.'}
record,stack,obj=0x20000,0x40000,0x10000
for label in ['linux--Quake3-UrT-Ded.x86_64','linux--Quake3-UrT.x86_64']:
r=json.loads(Path(f'docs/research/native/{label}.json').read_text());data=verified((Path('.cache/UrbanTerror43')/r['source']['path']).read_bytes(),r['source']['sha256'])
a=r['artifacts']['disassembly.txt'];fs=native_functions(verified(gzip.open(a['path'],'rb').read(),a['uncompressed_sha256']).decode());metadata,_=elf(data)
graphs={n:control_flow(fs[n]) for n in ['SV_LinkEntity','CM_LeafArea','CM_LeafCluster','CM_BoxLeafnums','CM_StoreLeafs']};g=graphs['SV_LinkEntity'];rows=g['instructions']
call_index=next(i for i,x in enumerate(rows) if '<CM_BoxLeafnums>' in x['operands']);start=rows[call_index+1]['address'];placement=site(g,'addl','$0x1, 0x1a4(%rbx)');cleanup=site(g,'addq','$0x228, %rsp')
calls={};debug={}
for i,x in enumerate(rows):
for service in ['CM_LeafArea','CM_LeafCluster']:
if x['opcode']=='callq' and '<'+service+'>' in x['operands']:calls[x['address']]={'service':service,'after':rows[i+1]['address']}
if x['opcode']=='callq' and '<Com_DPrintf>' in x['operands']:
# Each diagnostic block begins at its first CVTSS2SD, not its nearby previous block.
begin=next(k for k in range(max(0,i-8),i) if rows[k]['opcode']=='cvtss2sd')
debug[rows[begin]['address']]={'call':x['address'],'after':rows[i+1]['address']}
if len(debug)!=8:raise ValueError('diagnostic lane count changed')
sv_ins=next(x for x in rows if x['opcode']=='cmpl' and x['operands'].startswith('$0x1,') and '(%rip)' in x['operands']);sv_address=int(re.search(r'#\s*0x([0-9a-f]+)',sv_ins['operands'])[1],16)
stops=list(calls)+list(debug)+[placement,cleanup];compositions=[]
for count in [0,1,2,3,4,5,6,7,8,15,16,17,128]:
for pattern in ['absent','duplicates','mixed','unique']:
for sv_state in [0,1]:
areas,clusters=sequence(pattern,count);m={};put_word(m,sv_address,sv_state);put_word(m,stack+0x21c,1000)
for off,val in [(0xe0,0),(0x124,0),(0x128,-1),(0x12c,-1)]:put_word(m,record+off,val)
for i in range(16):put_word(m,record+0xe4+4*i,0xaabbccdd)
for i in range(count):put_word(m,stack+0x10+4*i,100+i)
regs={'%rax':count,'%rsp':stack,'%r12':record,'%rbx':obj,'%rcx':0};pc=start;trace=[];requests=[];segments=0
while pc not in [placement,cleanup]:
if segments>500:raise ValueError('metadata composition bound')
t=run(g,pc,stops,m,regs);m=t['memory'];regs=t['registers'];pc=t['stop'];trace+=t['trace'];segments+=1
if pc in calls:
c=calls[pc];leaf=regs['rdi']&0xffffffff
if leaf==1000 and c['service']=='CM_LeafCluster':value=777
elif 100<=leaf<100+count:value=(areas if c['service']=='CM_LeafArea' else clusters)[leaf-100]
else:raise ValueError('unexpected requested leaf')
requests.append([c['service'],leaf,value,pc]);regs['rax']=value&0xffffffff;pc=c['after']
elif pc in debug:
requests.append(['Com_DPrintf',None,None,debug[pc]['call']]);pc=debug[pc]['after']
compositions.append({'count':count,'pattern':pattern,'sv_state_word':sv_state,'supplied_areas':areas,'supplied_clusters':clusters,
'area_words':[get_word(m,record+0x128),get_word(m,record+0x12c)],'cluster_count':get_word(m,record+0xe0),
'cluster_words':[get_word(m,record+0xe4+4*i) for i in range(16)],'fallback_word':get_word(m,record+0x124),
'requests':requests,'reaches_placement':pc==placement,'trace':trace if count<=3 else None,
'trace_instruction_count':len(trace),'trace_sha256':hashlib.sha256(json.dumps(trace,separators=(',',':')).encode()).hexdigest()})
accessors={}
for name in ['CM_LeafArea','CM_LeafCluster']:
original=graphs[name];model=dict(original);model['instructions']=[dict(x) for x in original['instructions']];omitted=[]
for x in model['instructions']:
if x['opcode'] in ['pushq','popq']:
if x['operands']!='%rbx':raise ValueError('unexpected accessor stack traffic')
omitted.append(x['address']);x['opcode']='nop';x['operands']=''
if len(omitted)!=2:raise ValueError('accessor frame changed')
rows2=original['instructions'];cmp=next(x for x in rows2 if x['opcode']=='cmpl' and '(%rip)' in x['operands']);count_address=int(re.search(r'#\s*0x([0-9a-f]+)',cmp['operands'])[1],16)
base_load=next(x for x in rows2 if x['opcode']=='movq' and '(%rip)' in x['operands']);base_address=int(re.search(r'#\s*0x([0-9a-f]+)',base_load['operands'])[1],16)
error=next(x['address'] for x in rows2 if '<Com_Error>' in x['operands']);end=next(x['address'] for x in rows2 if x['opcode']=='retq');probes=[]
for leaf_count in [0,1,3]:
for index in [-1,0,1,2,3]:
m={};put_word(m,count_address,leaf_count);put_word(m,base_address,0x80000,8)
for i in range(3):put_word(m,0x80000+24*i,100+i);put_word(m,0x80004+24*i,200+i)
t=run(model,model['entry'],[error,end],m,{'%rdi':index,'%rax':0})
probes.append({'leaf_count':leaf_count,'index':index,'error_requested':t['stop']==error,'result_bits':None if t['stop']==error else t['registers']['rax'],'error_code':t['registers']['rdi'] if t['stop']==error else None,'trace':t['trace']})
msg=next(x for x in rows2 if x['opcode']=='movl' and x['operands'].split('#')[0].strip().endswith(', %esi'));address=int(msg['operands'].split(',')[0][1:],0)
accessors[name]={'count_address':count_address,'base_address':base_address,'omitted_stack_instructions':omitted,
'error_text':native_string(data,metadata['sections'],address),'probes':probes}
store=graphs['CM_StoreLeafs'];ret_stops=[x['address'] for x in store['instructions'] if x['opcode']=='retq']
callback=next(x for x in graphs['CM_BoxLeafnums']['instructions'] if x['opcode']=='movq' and x['operands'].split('#')[0].strip().endswith(', 0x38(%rsp)'))
if int(callback['operands'].split(',')[0][1:],0)!=store['entry']:raise ValueError('leaf callback changed')
list_record,output=0x60000,0x90000;store_traces=[];base_slot=accessors['CM_LeafCluster']['base_address']
for index in [0,1,2]:
for cluster in [-1,7]:
for count,capacity in [(0,0),(0,1),(1,1),(1,2),(127,128),(128,128)]:
m={};put_word(m,base_slot,0x80000,8);put_word(m,0x80000+24*index,cluster)
for off,val,width in [(0,count,4),(4,capacity,4),(8,0,4),(16,output,8),(48,999,4)]:put_word(m,list_record+off,val,width)
t=run(store,store['entry'],ret_stops,m,{'%rdi':list_record,'%rsi':(~index)&0xffffffff})
store_traces.append({'index':index,'cluster':cluster,'count_before':count,'capacity':capacity,
'count_after':get_word(t['memory'],list_record),'overflow_word':get_word(t['memory'],list_record+8),
'last_leaf_word':get_word(t['memory'],list_record+48),'output_writes':[{'address':w['address'],'value':get_word(t['memory'],w['address'],w['bytes']),'bytes':w['bytes']} for w in t['writes'] if w['address']>=output], 'trace':t['trace']})
first_debug_call=next(x for x in rows if x['address']==next(iter(debug.values()))['call'])
first_debug_index=next(i for i,x in enumerate(rows) if x['address']==first_debug_call['address'])
fmt=next(x for x in rows[first_debug_index-8:first_debug_index] if x['opcode']=='movl' and x['operands'].split('#')[0].strip().endswith(', %edi'))
fmt_address=int(fmt['operands'].split(',')[0][1:],0)
out['native'][label]={'source':r['source'],'disassembly_sha256':a['uncompressed_sha256'],'graphs':graphs,
'sv_state_address':sv_address,'service_sites':calls,'diagnostic_sites':debug,'compositions':compositions,'accessors':accessors,'store_leaf_traces':store_traces,'diagnostic_text':native_string(data,metadata['sections'],fmt_address)}
write_json(Path('docs/research/leaf-metadata.json'),out)
print('Recovered 208 area/cluster compositions, 60 guarded accessors and 72 leaf-store probes')
if __name__=='__main__':main()
|