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.

Branches are resolved with one line of look-ahead: at the branch we record a pending decision, and on the next line we compare that line's address to the branch target to learn whether the stitched path took the branch.

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. Value is [relation, signedness], where signedness (+nil+/+:u+/+:s+) selects the operand cast. :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 -- its flags reflect that result. Each entry says whether magnitude conditions (anything beyond +eq+/+ne+) are sound afterwards (+ordered+) and names the method that renders its constraint text. An arch maps its own mnemonics onto these ops (its COMPARES), so adding an arch needs no change here; adding a genuinely new ALU op means one entry plus its render_* method.

{
  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

Instance Method Summary collapse

Instance Method Details

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

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.



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

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:) ⇒ Object

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.



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

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) ⇒ Object

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).



247
248
249
 
# File 'lib/one_gadget/emulators/conditional.rb', line 247

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) ⇒ Object

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:



230
231
232
233
234
235
236
237
238
239
240
 
# File 'lib/one_gadget/emulators/conditional.rb', line 230

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) 


258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
 
# File 'lib/one_gadget/emulators/conditional.rb', line 258

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