Skip to content

Instantly share code, notes, and snippets.

@uint0
Created August 21, 2021 01:18
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Embed
What would you like to do?
Dynamically solves the bullet hell challenge by relying on the binary to do simulation.
import struct
import collections
import pwn
MAX_X = 30
MAX_Y = 40
WANTED_SCORE = 1337
def qol_patch():
elf = pwn.ELF('bullet_hell')
# Don't tick without input
elf.asm(elf.symbols['wtimeout'], 'ret')
# Become immortal
elf.asm(elf.symbols['die'], 'ret')
elf.save('./patched')
def get_state_addr(proc):
# Pretty sure you can get this more intelligently, but cbs
GAME_STATE_OFFSET = 0x2e040
maps = open(f'/proc/{proc.pid}/maps')
heap_line = next(m for m in maps if m.strip().endswith('[heap]'))
return int(heap_line.split('-')[0], 16) + GAME_STATE_OFFSET
def read_struct(proc, addr, struct_def, struct_name):
rep = collections.namedtuple(struct_name, struct_def.keys())
typ = ''.join(struct_def.values())
raw = proc.readmem(addr, count=struct.calcsize(typ))
return rep(*struct.unpack(typ, raw))
def read_arr(proc, addr, item_type, n_items):
return struct.unpack(item_type*n_items, proc.readmem(addr, count=n_items*struct.calcsize(item_type)))
def read_gamestate(proc, base_addr):
return read_struct(proc, base_addr, {
'player_x': 'i',
'player_y': 'i',
'score': 'i',
'bullets': 'P',
'bullets_len': 'N'
}, 'GameState')
def read_bullets(proc, game_state):
return [] if game_state.bullets == 0 else [
read_struct(proc, bullet_ptr, {
'x': 'i',
'y': 'i',
'dx': 'i',
'dy': 'i'
}, 'Bullet')
for bullet_ptr in read_arr(proc, game_state.bullets, 'P', game_state.bullets_len)
if bullet_ptr != 0
]
def provide_game_states(bin_path):
# Start the process
proc = pwn.process(bin_path, aslr=False)
proc.send(b'_')
game_state_addr = get_state_addr(proc)
game_state = read_gamestate(proc, game_state_addr)
pwn.log.info(f'Game State struct @ {game_state_addr:x}')
while game_state.score < WANTED_SCORE - 1:
if game_state.score % 100 == 0:
pwn.log.info(f'Up to frame {game_state.score}')
game_state = read_gamestate(proc, game_state_addr)
bullets = read_bullets(proc, game_state)
yield game_state, bullets
proc.send(b'_')
proc.clean()
def search_for_path(state_provider):
"""
We technically already have all the bullet positions from the state_provider
this automates generating inputs to solve the challenge, but you could just play
it by hand
"""
PADDING = 5
INV_MOVE_OFFSETS = {'_': (0, 0), 'l': (-1, 0), 'k': (0, 1), 'j': (0,-1), 'h': (1, 0)}
arr_get = lambda arr, i, j: arr[i][j] if PADDING <= i < len(arr) - PADDING and PADDING <= j < len(arr[0]) - PADDING else False
grid = lambda: [[False] * MAX_X for _ in range(MAX_Y)]
# Construct reachabilities for each frame going forward
init_state, _init_bullets = next(state_provider)
t = grid()
t[init_state.player_y][init_state.player_x] = True
layer_reachable = [t]
for _state, bullets in state_provider:
layer_bullets = set((b.x, b.y) for b in bullets)
last_layer = layer_reachable[-1]
cur_reachable = grid()
for y, row in enumerate(last_layer):
for x, _col in enumerate(row):
for dx, dy in INV_MOVE_OFFSETS.values():
if arr_get(last_layer, y+dy, x+dx) and (x, y) not in layer_bullets:
cur_reachable[y][x] = True
layer_reachable.append(cur_reachable)
# Back track over the frames to find a path
pos = next(
(x, y)
for x in range(PADDING, MAX_X - PADDING)
for y in range(PADDING, MAX_Y - PADDING)
if layer_reachable[-1][y][x]
)
steps = ''
for layer in reversed(layer_reachable):
x, y = pos
for move_key, (dx, dy) in INV_MOVE_OFFSETS.items():
new_pos = (x+dx, y+dy)
if arr_get(layer, new_pos[1], new_pos[0]):
steps += move_key
pos = new_pos
break
else:
raise "WTF?"
assert pos == (init_state.player_x, init_state.player_y)
# Algo is off by one, since there are no bullets initially we just ignore it hehe
return '_' + ''.join(reversed(list(steps)))
if __name__ == '__main__':
qol_patch()
provider = provide_game_states('./patched')
print(search_for_path(provider))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment