pwnlib.regsort — Register sorting

Topographical sort

pwnlib.regsort.check_cycle(reg, assignments)

Walk down the assignment list of a register, return the path walked if it is encountered again.

Returns:The list of register involved in the cycle. If there is no cycle, this is an empty list.

Example

>>> check_cycle('a', {'a': 1})
[]
>>> check_cycle('a', {'a': 'a'})
['a']
>>> check_cycle('a', {'a': 'b', 'b': 'a'})
['a', 'b']
>>> check_cycle('a', {'a': 'b', 'b': 'c', 'c': 'b', 'd': 'a'})
[]
>>> check_cycle('a', {'a': 'b', 'b': 'c', 'c': 'd', 'd': 'a'})
['a', 'b', 'c', 'd']

pwnlib.regsort.extract_dependencies(reg, assignments)

Return a list of all registers which directly depend on the specified register.

Example

>>> extract_dependencies('a', {'a': 1})
[]
>>> extract_dependencies('a', {'a': 'b', 'b': 1})
[]
>>> extract_dependencies('a', {'a': 1, 'b': 'a'})
['b']
>>> extract_dependencies('a', {'a': 1, 'b': 'a', 'c': 'a'})
['b', 'c']

pwnlib.regsort.regsort(in_out, all_regs, tmp=None, xchg=True, randomize=None)

Sorts register dependencies.

Given a dictionary of registers to desired register contents, return the optimal order in which to set the registers to those contents.

The implementation assumes that it is possible to move from any register to any other register.

If a dependency cycle is encountered, one of the following will occur:

• If xchg is True, it is assumed that dependency cyles can be broken by swapping the contents of two register (a la the xchg instruction on i386).
• If xchg is not set, but not all destination registers in in_out are involved in a cycle, one of the registers outside the cycle will be used as a temporary register, and then overwritten with its final value.
• If xchg is not set, and all registers are involved in a dependency cycle, the named register temporary is used as a temporary register.
• If the dependency cycle cannot be resolved as described above, an exception is raised.

Parameters:

• in_out (dict) – Dictionary of desired register states. Keys are registers, values are either registers or any other value.
• all_regs (list) – List of all possible registers. Used to determine which values in in_out are registers, versus regular values.
• tmp (obj, str) – Named register (or other sentinel value) to use as a temporary register. If tmp is a named register and appears as a source value in in_out, dependencies are handled appropriately. tmp cannot be a destination register in in_out. If bool(tmp)==True, this mode is enabled.
• xchg (obj) – Indicates the existence of an instruction which can swap the contents of two registers without use of a third register. If bool(xchg)==False, this mode is disabled.
• random (bool) – Randomize as much as possible about the order or registers.

Returns:

A list of tuples of (src, dest).

Each register may appear more than once, if a register is used as a temporary register, and later overwritten with its final value.

If xchg is True and it is used to break a dependency cycle, then reg_name will be None and value will be a tuple of the instructions to swap.

Example

>>> R = ['a', 'b', 'c', 'd', 'x', 'y', 'z']

If order doesn’t matter for any subsequence, alphabetic order is used.

>>> regsort({'a': 1, 'b': 2}, R)
[('mov', 'a', 1), ('mov', 'b', 2)]
>>> regsort({'a': 'b', 'b': 'a'}, R)
[('xchg', 'a', 'b')]
>>> regsort({'a': 'b', 'b': 'a'}, R, tmp='X') 
[('mov', 'X', 'a'),
 ('mov', 'a', 'b'),
 ('mov', 'b', 'X')]
>>> regsort({'a': 1, 'b': 'a'}, R) 
[('mov', 'b', 'a'),
 ('mov', 'a', 1)]
>>> regsort({'a': 'b', 'b': 'a', 'c': 3}, R) 
[('mov', 'c', 3),
 ('xchg', 'a', 'b')]
>>> regsort({'a': 'b', 'b': 'a', 'c': 'b'}, R) 
[('mov', 'c', 'b'),
 ('xchg', 'a', 'b')]
>>> regsort({'a':'b', 'b':'a', 'x':'b'}, R, tmp='y', xchg=False) 
[('mov', 'x', 'b'),
 ('mov', 'y', 'a'),
 ('mov', 'a', 'b'),
 ('mov', 'b', 'y')]
>>> regsort({'a':'b', 'b':'a', 'x':'b'}, R, tmp='x', xchg=False) 
Traceback (most recent call last):
...
PwnlibException: Cannot break dependency cycles ...
>>> regsort({'a':'b','b':'c','c':'a','x':'1','y':'z','z':'c'}, R) 
[('mov', 'x', '1'),
 ('mov', 'y', 'z'),
 ('mov', 'z', 'c'),
 ('xchg', 'a', 'b'),
 ('xchg', 'b', 'c')]
>>> regsort({'a':'b','b':'c','c':'a','x':'1','y':'z','z':'c'}, R, tmp='x') 
[('mov', 'y', 'z'),
 ('mov', 'z', 'c'),
 ('mov', 'x', 'a'),
 ('mov', 'a', 'b'),
 ('mov', 'b', 'c'),
 ('mov', 'c', 'x'),
 ('mov', 'x', '1')]
>>> regsort({'a':'b','b':'c','c':'a','x':'1','y':'z','z':'c'}, R, xchg=0) 
[('mov', 'y', 'z'),
 ('mov', 'z', 'c'),
 ('mov', 'x', 'a'),
 ('mov', 'a', 'b'),
 ('mov', 'b', 'c'),
 ('mov', 'c', 'x'),
 ('mov', 'x', '1')]
 >>> regsort({'a': 'b', 'b': 'c'}, ['a','b','c'], xchg=0)
 [('mov', 'a', 'b'), ('mov', 'b', 'c')]

pwnlib.regsort.resolve_order(reg, deps)

Resolve the order of all dependencies starting at a given register.

Example

>>> want = {'a': 1, 'b': 'c', 'c': 'd', 'd': 7, 'x': 'd'}
>>> deps = {'a': [], 'b': [], 'c': ['b'], 'd': ['c', 'x'], 'x': []}
>>> resolve_order('a', deps)
['a']
>>> resolve_order('b', deps)
['b']
>>> resolve_order('c', deps)
['b', 'c']
>>> resolve_order('d', deps)
['b', 'c', 'x', 'd']