Class: OneGadget::Emulators::Processor

Inherits:
Object
  • Object
show all
Includes:
Conditional
Defined in:
lib/one_gadget/emulators/processor.rb

Overview

Base of the per-architecture instruction emulators, used to symbolically execute a candidate and solve its constraints. A subclass implements the arch's supported instructions, calling convention and stack model; the shared branch/compare machinery comes from Conditional.

To add an architecture, see docs/adding-an-architecture.md.

Direct Known Subclasses

ArmFamily, X86

Constant Summary collapse

TERMINAL_CALL_RE =

Function names whose call ends a gadget: the real exec* entry points. Deliberately excludes the posix_spawn setup helpers (+posix_spawnattr_*+, posix_spawn_file_actions_*), which merely share the posix_spawn prefix.

Examples:

matches posix_spawn, execve, execveat, execlp; not posix_spawnattr_init

/\A(?:posix_spawnp?|exec(?:ve|l|v)[a-z]*)\z/
CLOBBERED =

Marks a register holding whatever a call returned or left behind; see #clobber_caller_saved.

'$clobbered'
ADDRESS_TYPES =

Constraint types whose payload is an address Lambda asserting the target is mapped -- :writable (a store target) and :readable (an unconditional dereference, see #finalize_deferred_reads). Both are keyed, offset- normalised, and imply non-NULL identically; they differ only in how they render (see #render_constraint). The remaining type, :raw, carries a ready-made constraint string that keys on itself, and :cmp a comparison recorded as its [lhs, operator, rhs] parts (see Conditional), so it can be inspected rather than re-parsed from the rendered text.

%i[writable readable].freeze
POINTER_REQUIREMENTS =

SafeCalls requirements naming what a callee does with a pointer argument, each recorded as something the caller must arrange (see #record_pointer), as opposed to a precondition read off the value as it stands.

%i[writable deref nullable_deref null].freeze
NULLABLE_REQUIREMENTS =

The POINTER_REQUIREMENTS a NULL argument already satisfies: both ask for a pointer the callee will leave alone, and NULL is how that is asked for.

%i[nullable_deref null].freeze

Constants included from Conditional

Conditional::COMPARE_OPS, Conditional::NEGATE, Conditional::RELATION

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Conditional

#branch_on_bit, #branch_on_compare, #branch_on_zero, #comparisons_on, #handle_compare, #mnemonic, #operand_str, #record_compare, #resolve_pending_branch, #satisfiable?, #value_str

Constructor Details

#initialize(registers, sp) ⇒ Processor

Instantiate a OneGadget::Emulators::Processor object.

Parameters:

  • registers (Array<String>) —

    Registers that supported in the architecture.

  • sp (String) —

    The stack register.



38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/one_gadget/emulators/processor.rb', line 38

def initialize(registers, sp)
  @registers = RegisterFile.build(registers, OneGadget::ABI::NARROW_VIEWS.fetch(arch_name, {})) do |reg|
    to_lambda(reg)
  end
  @sp = sp
  @constraints = []
  @deferred_reads = [] # pointer args of safe calls, resolved once emulation ends
  @closed_fds = []     # where each descriptor closed before the terminal call comes from
  @flags = nil     # last compare, for a following conditional branch
  @pending = nil   # a conditional branch awaiting one-line-ahead resolution
end

Instance Attribute Details

#bp ⇒ String? (readonly)

Returns Frame pointer, or nil when this arch tracks none.

Returns:

  • (String, nil) —

    Frame pointer, or nil when this arch tracks none.



25
26
27
 
# File 'lib/one_gadget/emulators/processor.rb', line 25

def bp
  @bp
end

#pc ⇒ String (readonly)

Returns Program counter.

Returns:

  • (String) —

    Program counter.



24
25
26
 
# File 'lib/one_gadget/emulators/processor.rb', line 24

def pc
  @pc
end

#refused_line ⇒ String? (readonly)

The line this emulator could not run at all: an instruction outside #instructions. Only what #parse reads decides that -- the mnemonic and the operands, never the state the emulator holds -- so the same line stops every emulation that reaches it.

Returns:

  • (String, nil) 


147
148
149
 
# File 'lib/one_gadget/emulators/processor.rb', line 147

def refused_line
  @refused_line
end

#registers ⇒ RegisterFile (readonly)

Returns The current registers' state.

Returns:



22
23
24
 
# File 'lib/one_gadget/emulators/processor.rb', line 22

def registers
  @registers
end

#sp ⇒ String (readonly)

Returns Stack pointer.

Returns:

  • (String) —

    Stack pointer.



23
24
25
 
# File 'lib/one_gadget/emulators/processor.rb', line 23

def sp
  @sp
end

Class Method Details

.bits ⇒ Integer

32 or 64.

Returns:

  • (Integer) —

    32 or 64.

Raises:

  • (NotImplementedError) 


720
721
 
# File 'lib/one_gadget/emulators/processor.rb', line 720

def bits; raise NotImplementedError
end

.instruction_table ⇒ (Array<Instruction>, Hash{String => Instruction})

The architecture's supported instructions, and the same set indexed by mnemonic, built on first use and shared by every emulator of that architecture: the set is fixed, while an emulator is made for each of the thousands of windows a candidate yields.

Yield Returns:

  • (Array<Instruction>) —

    The table, asked for only on first use.

Returns:



120
121
122
123
124
125
 
# File 'lib/one_gadget/emulators/processor.rb', line 120

def instruction_table
  @instruction_table ||= begin
    list = yield
    [list, list.each_with_object({}) { |i, h| h[i.inst] ||= i }]
  end
end

.line_memo(kind) ⇒ Hash

What a line always reads as, remembered per architecture and kind of reading: a candidate is emulated once for every window it yields, so the same line is read thousands of times, and nothing about how it reads depends on the state the emulator holds.

Parameters:

  • kind (Symbol)

Returns:

  • (Hash) 


110
111
112
 
# File 'lib/one_gadget/emulators/processor.rb', line 110

def line_memo(kind)
  (@line_memo ||= Hash.new { |memo, k| memo[k] = {} })[kind]
end

Instance Method Details

#address_deref0?(type, obj) ⇒ Boolean

Whether (type, obj) is an address constraint on a bare (deref-0) target, i.e. one carrying a base register and offset to normalise.

Returns:

  • (Boolean) 


222
223
224
 
# File 'lib/one_gadget/emulators/processor.rb', line 222

def address_deref0?(type, obj)
  ADDRESS_TYPES.include?(type) && obj.deref_count.zero?
end

#argument(_idx) ⇒ Lambda, Integer

To be inherited.

Parameters:

  • _idx (Integer) —

    The idx-th argument.

Returns:

  • (Lambda, Integer) —

    Return value can be a Lambda or an Integer.

Raises:

  • (NotImplementedError) 


172
173
 
# File 'lib/one_gadget/emulators/processor.rb', line 172

def argument(_idx); raise NotImplementedError
end

#bp_based_stack ⇒ Hash{Integer => Lambda}?

Returns Memory written through #bp, or nil when the arch has none.

Returns:

  • (Hash{Integer => Lambda}, nil) —

    Memory written through #bp, or nil when the arch has none.



31
 
# File 'lib/one_gadget/emulators/processor.rb', line 31

def bp_based_stack = bp && get_corresponding_stack(bp)

#closed_fds ⇒ Array<String>

Returns Where each descriptor this candidate closes is read from, in the order they are closed, without repeats.

Returns:

  • (Array<String>) —

    Where each descriptor this candidate closes is read from, in the order they are closed, without repeats.



200
201
202
 
# File 'lib/one_gadget/emulators/processor.rb', line 200

def closed_fds
  @closed_fds.uniq
end

#constraint_key(type, obj) ⇒ Object

De-duplication key: an address constraint collapses per (type, base) so constraints of different types on the same register stay distinct; a raw constraint keys on its own text.



229
230
231
232
233
 
# File 'lib/one_gadget/emulators/processor.rb', line 229

def constraint_key(type, obj)
  return obj unless ADDRESS_TYPES.include?(type)

  [type, obj.deref_count.zero? ? obj.obj.to_s : obj.to_s]
end

#constraints ⇒ Array<String>

Returns Extra constraints found during execution.

Returns:

  • (Array<String>) —

    Extra constraints found during execution.



206
207
208
209
210
211
212
213
214
215
216
217
218
 
# File 'lib/one_gadget/emulators/processor.rb', line 206

def constraints
  finalize_deferred_reads
  return [] if @constraints.empty?

  # An address constraint is keyed by its base register (deref-0) or full
  # expression (compound); several through one base (e.g. stores at reg+0x0
  # and reg+0x8) impose the same requirement, so keep just the smallest
  # offset (sort ascending, then uniq keeps that first).
  cons = @constraints.sort_by { |type, obj| address_deref0?(type, obj) ? obj.immi : 0 }
                     .uniq { |type, obj| constraint_key(type, obj) }
  cons = drop_restated_null(drop_implied_nonzero(cons))
  cons.map { |type, obj| render_constraint(type, obj) }.sort
end

#drop_implied_nonzero(cons) ⇒ Array<[Symbol, Object]>

Drop a " != 0x0" branch constraint that another constraint already implies: an address constraint (+writable: +imm+ store target, or readable: <reg>) forces to be a valid (mapped, non-NULL) pointer, so a NULL-check branch on the same register adds nothing. Keeps the emitted set minimal.

Parameters:

  • cons (Array<[Symbol, Object]>) —

    The de-duplicated constraint list.

Returns:

  • (Array<[Symbol, Object]>) 


252
253
254
255
256
257
258
259
260
261
 
# File 'lib/one_gadget/emulators/processor.rb', line 252

def drop_implied_nonzero(cons)
  nonzero_regs = cons.filter_map do |type, obj|
    obj.obj.to_s if address_deref0?(type, obj)
  end
  return cons if nonzero_regs.empty?

  cons.reject do |type, obj|
    type == :cmp && obj[1] == '!=' && obj[2] == ZERO && nonzero_regs.include?(obj[0])
  end
end

#drop_restated_null(cons) ⇒ Array<[Symbol, Object]>

Drop a " == 0x0" branch constraint that a NULL requirement on the same value already states (see #require_null). Both ask for the same zero, and the one naming it NULL is the one that says what the zero is for.

Parameters:

  • cons (Array<[Symbol, Object]>) —

    The de-duplicated constraint list.

Returns:

  • (Array<[Symbol, Object]>) 


268
269
270
271
272
273
274
275
 
# File 'lib/one_gadget/emulators/processor.rb', line 268

def drop_restated_null(cons)
  nulls = cons.filter_map { |type, obj| obj[/\A(.+) == NULL\z/, 1] if type == :raw }
  return cons if nulls.empty?

  cons.reject do |type, obj|
    type == :cmp && obj[1] == '==' && obj[2] == ZERO && nulls.include?(obj[0])
  end
end

#get_corresponding_stack(base) ⇒ Hash{Integer => Lambda}?

The memory base addresses: what this candidate has written through it, keyed by offset. Every base gets one -- the stack pointer, the frame pointer, any other register, and a value no register names at all (a pointer the candidate derived and then built an array through).

Keyed by how the base renders, which is what makes one store enough: a register that gets reassigned addresses somewhere else and renders differently, so it lands on a different key without any invalidation to arrange. Only a store overwriting what the base itself reads from would break that, which a candidate short enough to be a gadget doesn't do.

Examples:

a register

get_corresponding_stack('x21')

a pointer rounded down before use

get_corresponding_stack(Lambda.parse('(rsi & 0xfffffffffffffff0)'))

Parameters:

  • base (String, Lambda) —

    A base, as #resolve_address yields it -- not an offset expression, whose offset belongs in the key it indexes.

Returns:

  • (Hash{Integer => Lambda}, nil) —

    nil when base names nothing this emulator tracks memory for.



310
311
312
313
314
 
# File 'lib/one_gadget/emulators/processor.rb', line 310

def get_corresponding_stack(base)
  return nil unless base.is_a?(OneGadget::Emulators::Lambda) || registers.key?(base.to_s)

  tracked_memory[base.to_s]
end

#instructions ⇒ Array<Instruction>

Method need to be implemented in inheritors.

Returns:

Raises:

  • (NotImplementedError) 


162
163
 
# File 'lib/one_gadget/emulators/processor.rb', line 162

def instructions; raise NotImplementedError
end

#parse(cmd) ⇒ (Instruction, Array<String>)

Parse one command into instruction and arguments.

Parameters:

  • cmd (String) —

    One line of result of objdump.

Returns:

  • ((Instruction, Array<String>)) —

    The parsing result.



90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/one_gadget/emulators/processor.rb', line 90

def parse(cmd)
  self.class.line_memo(:parse)[cmd] ||= begin
    list, index = self.class.instruction_table { instructions }
    mnem = cmd[/\A[0-9a-f]+:\s*(\S+)/, 1] || cmd[/\A\s*(\S+)/, 1]
    inst = index[mnem]
    # Fall back to the original scan for any mnemonic that isn't a bare word.
    inst ||= list.find { |i| i.match?(cmd) }
    raise Error::UnsupportedInstructionError, "Not implemented instruction in #{cmd}" if inst.nil?

    [inst, inst.fetch_args(cmd)]
  end
end

#process(cmd) ⇒ Boolean

Process one command, without raising any exceptions.

Parameters:

  • cmd (String) —

    See #process! for more information.

Returns:

  • (Boolean) 


132
133
134
135
136
137
138
139
140
 
# File 'lib/one_gadget/emulators/processor.rb', line 132

def process(cmd)
  process!(cmd)
# rescue OneGadget::Error::UnsupportedError => e; p e # for debugging
rescue OneGadget::Error::UnsupportedInstructionError
  @refused_line = cmd
  false
rescue OneGadget::Error::Error
  false
end

#process!(_cmd) ⇒ Boolean

Method need to be implemented in inheritors.

Process one command. Will raise exceptions when encounter unhandled instruction.

Parameters:

  • _cmd (String) —

    One line from result of objdump.

Returns:

  • (Boolean) —

    If successfully processed.

Raises:

  • (NotImplementedError) 


157
158
 
# File 'lib/one_gadget/emulators/processor.rb', line 157

def process!(_cmd); raise NotImplementedError
end

#reach_terminal_call(addr) ⇒ Symbol

Record a reached terminal exec* call as the gadget's effect and stop emulating: it is the gadget's goal, and any following instruction would clobber the argument registers that #resolve reads to describe it.

Parameters:

  • addr (String) —

    The call target.

Returns:

  • (Symbol) —

    :fail, the sentinel #process! maps to "stop".



81
82
83
84
 
# File 'lib/one_gadget/emulators/processor.rb', line 81

def reach_terminal_call(addr)
  registers[pc] = addr
  :fail
end

#render_constraint(type, obj) ⇒ Object

Render a constraint to its output string.



236
237
238
239
240
241
242
243
 
# File 'lib/one_gadget/emulators/processor.rb', line 236

def render_constraint(type, obj)
  case type
  when :writable then "writable: #{obj}"
  when :readable then "readable: #{obj}"
  when :cmp then obj.join(' ')
  else obj
  end
end

#resolve_address(address) ⇒ (Hash{Integer => Lambda}?, Integer)

Where address lands in the memory this emulator tracks: the stack it falls in and its offset within it. A load or store passes the address it dereferences, i.e. its operand with that dereference peeled off.

Examples:

an offset from a register

resolve_address(Lambda.parse('rsp+0x10')) #=> [sp_based_stack, 0x10]

an offset from a pointer no register names

resolve_address(Lambda.parse('[rbp-0x48]+0x8')) #=> [the "[rbp-0x48]" stack, 0x8]

Parameters:

  • address (Lambda, String) —

    An address.

Returns:

  • ((Hash{Integer => Lambda}?, Integer)) —

    The stack, nil if none tracks this address, and the offset to index it at.



287
288
289
290
 
# File 'lib/one_gadget/emulators/processor.rb', line 287

def resolve_address(address)
  base, offset = address_base(address)
  [get_corresponding_stack(base), offset]
end

#setup_frame_pointer(bp) ⇒ void

This method returns an undefined value.

Enable frame-pointer stack tracking with bp as the frame register, so a gadget staging data at +[bp+imm]+ (e.g. an argv array off the frame pointer) is recovered instead of collapsing to a bare writable:. A nil bp leaves the arch +sp+-only. Call from the arch initializer after super.



55
56
57
 
# File 'lib/one_gadget/emulators/processor.rb', line 55

def setup_frame_pointer(bp)
  @bp = bp
end

#sp_based_stack ⇒ Hash{Integer => OneGadget::Emulators::Lambda}

Returns Memory written through sp.

Returns:



28
 
# File 'lib/one_gadget/emulators/processor.rb', line 28

def sp_based_stack = get_corresponding_stack(sp)

#terminal_call?(addr) ⇒ Boolean

Whether addr calls a terminal exec* entry point (see #reach_terminal_call). Matches the resolved symbol name exactly so a setup helper isn't mistaken for the call it precedes.

Parameters:

  • addr (String) —

    The call target, e.g. "10c7d0 <posix_spawn@@GLIBC_2.15>".

Returns:

  • (Boolean) 


71
72
73
74
 
# File 'lib/one_gadget/emulators/processor.rb', line 71

def terminal_call?(addr)
  name = addr[/<([^@>]+)/, 1]
  !name.nil? && TERMINAL_CALL_RE.match?(name)
end