Module: OneGadget::Emulators::Conditional

Included in:
Processor
Defined in:
lib/one_gadget/emulators/conditional.rb

Overview

Shared modelling of compare instructions and conditional branches.

A gadget candidate may cross a conditional branch: the fetcher stitches the actual taken/not-taken path (see Fetchers::Base#candidates), and the emulator turns the branch decision into a gadget constraint.

The including class (an Processor subclass) must provide registers and register? (operand lookup), operands(cmd) (the arch's operand splitter), self.class.bits (32/64, for the signedness cast), and the +@flags+/+@pending+/+@constraints+ state Processor#initialize sets up.

Examples:

A b.ne whose branch is not taken becomes the constraint x2 == 0x1

#   c7a4c: cmp  x2, 1
#   c7a50: b.ne c7a9c    # stitched path falls through (does not jump)
# => emitted gadget constraint:  x2 == 0x1

Constant Summary collapse

RELATION =

Taken-semantics of each supported branch condition, keyed by a predicate named after the comparison it encodes (the LLVM icmp names): a leading u = unsigned, s = signed.

Examples:

The value is the relation, and the cast its operands take.

RELATION[:eq]  #=> ['==', nil]
RELATION[:ult] #=> ['<', :u]
RELATION[:sge] #=> ['>=', :s]
:eq  :ne                equality
:ult :ule :ugt :uge     unsigned  <  <=  >  >=
:slt :sle :sgt :sge     signed    <  <=  >  >=
{
  eq: ['==', nil], ne: ['!=', nil],
  ult: ['<', :u], ule: ['<=', :u], ugt: ['>', :u], uge: ['>=', :u],
  slt: ['<', :s], sle: ['<=', :s], sgt: ['>', :s], sge: ['>=', :s]
}.freeze
NEGATE =

Relation under the not-taken branch.

{ '==' => '!=', '!=' => '==', '>=' => '<', '<' => '>=', '>' => '<=', '<=' => '>' }.freeze
COMPARE_OPS =

The flag-setting compares we model, keyed by the ALU operation the compare performs. An arch maps its own mnemonics onto these (its COMPARES), so adding one needs no change here.

Examples:

Whether magnitude conditions are sound after it, and what renders

its constraint text.
COMPARE_OPS[:sub] #=> { ordered: true, render: :render_sub }
COMPARE_OPS.keys  #=> [:sub, :add, :and]
{
  sub: { ordered: true,  render: :render_sub },  # subtraction: flags from  lhs - rhs
  add: { ordered: true,  render: :render_add },  # addition:    flags from  lhs + rhs
  and: { ordered: false, render: :render_and }   # bitwise AND: flags from  lhs & rhs (zero flag)
}.freeze
ZERO =

A value comparison's zero literal, always hex. Pointer operands render NULL (chosen by the arg resolvers); every value-context zero here is 0x0, so a bare 0 (and objdump's arch-specific #0 vs 0x0) never leaks into a constraint. Recorded here and read back by OneGadget::Emulators::Constraints, whose drop rules recognise a compare against zero by it.

'0x0'

Instance Method Summary collapse

Instance Method Details

#branch_on_bit(target, operand, bit, negate:) ⇒ true

Register a self-contained branch that tests a single bit of a register: also carries its own test, so no preceding compare is needed. Renders a bitmask test.

Examples:

aarch64 tbz w0, #4, 4a200 - branch taken when bit 4 of w0 is 0

branch_on_bit(0x4a200, 'w0', 4, negate: false) #=> true
# taken path emits  (w0 & 0x10) == 0 ; fall-through emits  (w0 & 0x10) != 0

Parameters:

  • target (Integer) —

    Destination address of the branch.

  • operand (String) —

    The tested register, as the instruction writes it (see #branch_on_zero).

  • bit (Integer) —

    The bit index being tested.

  • negate (Boolean) —

    false = branch when the bit is zero, true = when it's set.

Returns:

  • (true) —

    Registering the branch is how the line is handled.



210
211
212
213
214
215
216
217
 
# File 'lib/one_gadget/emulators/conditional.rb', line 210

def branch_on_bit(target, operand, bit, negate:)
  reg = operand_str(operand)
  mask = OneGadget::Helper.hex(1 << bit)
  hit = negate ? '!=' : '=='
  miss = negate ? '==' : '!='
  @pending = { target:, compare: ->(taken) { ["(#{reg} & #{mask})", taken ? hit : miss, ZERO] } }
  true
end

#branch_on_compare(cond, target) ⇒ true, :fail

Register a branch on the last recorded compare's flags, resolved on the next line. Call it from handle_branch; cond is the comparison predicate and target is the branch's direct destination address.

Examples:

After cmp x2, #1, a following b.ne 4a200 (arch maps b.ne to :ne)

branch_on_compare(:ne, 0x4a200) #=> true
# if the stitched path FALLS THROUGH (doesn't reach 0x4a200) the not-taken
# relation of +:ne+ is emitted:  x2 == 0x1 ; if it jumps there:  x2 != 0x1

No preceding compare -> the path is unsound and is aborted

branch_on_compare(:ne, 0x4a200) #=> :fail   # when @flags is nil

Parameters:

  • cond (Symbol) —

    The comparison predicate, a RELATION key. Each arch first maps its own branch mnemonic to it via its adapter table.

  • target (Integer) —

    Destination address of the branch.

Returns:

  • (true, :fail) —

    :fail (abort the path) when it cannot be expressed soundly: no compare was seen, or a magnitude condition follows an equality-only compare (a COMPARE_OPS op with ordered: false).



163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/one_gadget/emulators/conditional.rb', line 163

def branch_on_compare(cond, target)
  return :fail if @flags.nil?

  rel = RELATION[cond]
  return :fail if rel.nil?
  # A magnitude condition needs a compare whose flags reflect a full ordering
  # (+:sub+/+:add+); an equality-only compare (+:and+) supports just eq/ne.
  return :fail unless COMPARE_OPS.fetch(@flags[:op])[:ordered] || %i[eq ne].include?(cond)

  op = @flags[:op]
  lhs = @flags[:lhs]
  rhs = @flags[:rhs]
  @pending = { target:, compare: ->(taken) { compare_triple(op, lhs, rhs, rel, taken) } }
  true
end

#branch_on_zero(target, operand, negate:) ⇒ true

Register a self-contained branch that tests a register against zero. It carries its own compare, so no preceding compare is needed. negate: selects the sense: false branches when the register is zero, true when it isn't.

Examples:

aarch64 cbz x0, 4a200 - branch taken when x0 == 0

branch_on_zero(0x4a200, 'x0', negate: false) #=> true
# fall-through path emits  x0 != 0 ; taken path emits  x0 == 0

x86 reuses it for +jrcxz+/+jecxz+/+jcxz+ (always branch-if-zero)

branch_on_zero(0x4a200, 'rcx', negate: false)

Parameters:

  • target (Integer) —

    Destination address of the branch.

  • operand (String) —

    The tested register, as the instruction writes it; rendered here, so a value the caller cannot reason about stops the path.

  • negate (Boolean) —

    false = branch when it is zero, true = when it isn't.

Returns:

  • (true) —

    Registering the branch is how the line is handled.



192
193
194
195
196
197
198
 
# File 'lib/one_gadget/emulators/conditional.rb', line 192

def branch_on_zero(target, operand, negate:)
  reg = operand_str(operand)
  hit = negate ? '!=' : '==' # taken (not negated) => reg == 0
  miss = negate ? '==' : '!='
  @pending = { target:, compare: ->(taken) { [reg, taken ? hit : miss, ZERO] } }
  true
end

#comparisons_on(expr) ⇒ Array<(String, String, String)>

Every comparison recorded so far on expr, the left side as rendered. Matching on that text is what makes this sound: the renderer substitutes each register's current value, so two constraints printing the same left side really are about the same tracked value (and a differing signedness cast is part of that text, keeping incomparable ones apart).

Parameters:

  • expr (String) —

    The left side, as rendered.

Returns:

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

    The comparisons recorded on it.



254
255
256
 
# File 'lib/one_gadget/emulators/conditional.rb', line 254

def comparisons_on(expr)
  @constraints.filter_map { |type, obj| obj if type == :cmp && obj.first == expr }
end

#handle_compare(op, cmd) ⇒ true

Model a compare line: record its two operands' current values under the compare's ALU op, so a following conditional branch can be rendered.

Call this from process! when the mnemonic is one of the arch's compares (its COMPARES maps the mnemonic to the op), before dispatching to the inst_* handlers.

Examples:

Wiring in an arch's process! (its COMPARES holds the mnemonic map)

return handle_compare(COMPARES[mnem], cmd) if COMPARES.key?(mnem)

What it records for cmp x2, 1 (x2 currently 0x30)

handle_compare(:sub, '4a1c0: cmp x2, 1') #=> true
# records op :sub, lhs = 0x30, rhs = 0x1, ready for the next branch

Parameters:

  • op (Symbol) —

    The compare's ALU operation (a COMPARE_OPS key), which the arch resolves from the mnemonic.

  • cmd (String) —

    Passed to the arch's operands splitter, so it is whatever that splitter expects (a full objdump line, or just its operand part).

Returns:

  • (true) 


98
99
100
101
 
# File 'lib/one_gadget/emulators/conditional.rb', line 98

def handle_compare(op, cmd)
  lhs, rhs = operands(cmd)
  record_compare(op, operand_str(lhs), operand_str(rhs))
end

#mnemonic(cmd) ⇒ String

The mnemonic of an objdump line. Use it at the top of process! to decide whether a line is a compare or a branch.

Examples:

mnemonic('4a1c0: cmp x2, 1')           #=> 'cmp'
mnemonic('4a1d0: b.ne 4a200 <foo>')    #=> 'b.ne'
mnemonic('4a1d4: je   4a200')          #=> 'je'
mnemonic('')                           #=> ''

Parameters:

  • cmd (String) —

    One objdump line.

Returns:

  • (String) —

    The mnemonic, or '' when the line has none.



112
113
114
 
# File 'lib/one_gadget/emulators/conditional.rb', line 112

def mnemonic(cmd)
  cmd[/\A[0-9a-f]+:\s*(\S+)/, 1] || ''
end

#operand_str(operand) ⇒ String

Render an operand for a constraint: a register becomes its current value, an immediate becomes hex, anything else (a memory operand) stays as-is. #handle_compare uses it on each compare operand; call it yourself only when writing a bespoke branch_on_* helper.

Examples:

(assuming register x2 currently holds the immediate 0x1)

operand_str('x2')       #=> '0x1'       # a register -> its current value
operand_str('0x40')     #=> '0x40'      # a hex immediate -> unchanged
operand_str('16')       #=> '0x10'      # a decimal immediate -> hex
operand_str('[sp+0x8]') #=> '[sp+0x8]'  # a memory operand -> unchanged

Parameters:

  • operand (String) —

    A single operand string from a compare/branch line.

Returns:

  • (String) —

    The rendered operand.



127
128
129
130
131
132
133
134
135
136
137
 
# File 'lib/one_gadget/emulators/conditional.rb', line 127

def operand_str(operand)
  if register?(operand)
    raise Error::ClobberedRegisterError, operand if clobbered?(registers[operand])

    return value_str(registers[operand])
  end

  OneGadget::Helper.hex(Integer(operand))
rescue ArgumentError
  operand
end

#record_compare(op, lhs, rhs) ⇒ true

Record a compare so a following conditional branch can be rendered. Normally reached through #handle_compare; call it directly only when an arch models a flag-setting instruction that #handle_compare doesn't cover.

Examples:

Record cmp x2, 0x1 (subtraction), readying the next branch

record_compare(:sub, '0x1', '0x1') #=> true
# a following +b.ne+ not taken renders  0x1 == 0x1  (a stripped tautology)

Parameters:

  • op (Symbol) —

    The ALU operation the compare performs -- a COMPARE_OPS key (+:sub+/+:add+/+:and+). Its flags reflect this result, which decides both which branch conditions are expressible and how the constraint is rendered. Each arch maps its own mnemonics to these ops (their COMPARES); a new arch adds a COMPARE_OPS entry only for a genuinely new operation.

  • lhs (String) —

    Rendered left operand: a register's current value, or an immediate in hex.

  • rhs (String) —

    Rendered right operand.

Returns:

  • (true) 


77
78
79
80
 
# File 'lib/one_gadget/emulators/conditional.rb', line 77

def record_compare(op, lhs, rhs)
  @flags = { op:, lhs:, rhs: }
  true
end

#resolve_pending_branch(cmd) ⇒ void

This method returns an undefined value.

Resolve the pending branch using +cmd+'s address: if it equals the branch target the stitched path took the branch, else it fell through. On resolution the rendered relation is appended to the gadget's constraints. Must be called at the top of process! for every line (a no-op when nothing is pending), so the branch registered on the previous line sees this line's address.

Examples:

The fixed first line of every arch's process!

def process!(cmd)
  resolve_pending_branch(cmd)
  ...
end
# if the previous line did +branch_on_compare(:ne, 0x4a200)+ and this
# +cmd+ sits at 0x4a200, the branch was taken; otherwise it fell through

Parameters:

  • cmd (String) —

    The current objdump line.

Raises:



235
236
237
238
239
240
241
242
243
244
245
 
# File 'lib/one_gadget/emulators/conditional.rb', line 235

def resolve_pending_branch(cmd)
  return if @pending.nil?

  taken = branch_addr(cmd) == @pending[:target]
  triple = @pending[:compare].call(taken)
  @pending = nil
  @constraints << [:cmp, triple]
  return if satisfiable?(comparisons_on(triple.first))

  raise Error::InfeasiblePathError, "cannot hold together: #{triple.first}"
end

#satisfiable?(triples) ⇒ Boolean

Whether some value satisfies every comparison in triples at once, by intersecting the range each one allows. Comparisons against anything but an integer are ignored rather than guessed at, so an undecidable one never makes a path look impossible.

Examples:

x != 0x0 together with x == 0x0 #=> false

Parameters:

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

    Comparisons on one expression.

Returns:

  • (Boolean) 


265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
 
# File 'lib/one_gadget/emulators/conditional.rb', line 265

def satisfiable?(triples)
  low = nil
  high = nil
  excluded = []
  triples.each do |_expr, op, rhs|
    next unless OneGadget::Helper.integer?(rhs)

    value = Integer(rhs)
    case op
    when '=='
      low = [low, value].compact.max
      high = [high, value].compact.min
    when '!=' then excluded << value
    when '<' then high = [high, value - 1].compact.min
    when '<=' then high = [high, value].compact.min
    when '>' then low = [low, value + 1].compact.max
    when '>=' then low = [low, value].compact.max
    end
  end
  return false if low && high && (low > high || (low == high && excluded.include?(low)))

  true
end

#value_str(val) ⇒ String

A value as a constraint reads it: a concrete one in hex, whichever side of a compare it came from, and anything else as it renders itself.

Examples:

value_str(1) #=> '0x1', so a folded register reads like an immediate

Parameters:

  • val (Object) —

    The value to render.

Returns:

  • (String) —

    Its constraint form.



144
145
146
 
# File 'lib/one_gadget/emulators/conditional.rb', line 144

def value_str(val)
  val.is_a?(Integer) ? OneGadget::Helper.hex(val) : val.to_s
end