Class: Ibex::Fuzz

Inherits:
Object
  • Object
show all
Defined in:
lib/ibex/fuzz.rb,
sig/ibex/fuzz.rbs

Overview

Bounded grammar-derived differential fuzzing without semantic execution.

Defined Under Namespace

Classes: BudgetExceeded, Mismatch

Constant Summary collapse

ALGORITHMS =

Signature:

  • Array[Symbol]

Returns:

  • (Array[Symbol]) 
%i[slr lalr ielr lr1].freeze
DEFAULT_MAX_ACTIONS =

Signature:

  • Integer

Returns:

  • (Integer) 
100_000
DEFAULT_MAX_STACK =

Signature:

  • Integer

Returns:

  • (Integer) 
10_000

Instance Method Summary collapse

Constructor Details

#initialize(grammar, seed: 0, count: 100, max_tokens: 32, max_depth: 16, max_expansions: Samples::DEFAULT_MAX_EXPANSIONS, max_actions: DEFAULT_MAX_ACTIONS, max_stack: DEFAULT_MAX_STACK, coverage_guided: false, path_length: 2, algorithms: ALGORITHMS, ielr_strategy: :partition, automata: nil, against: nil, against_description: nil) ⇒ Fuzz

rubocop:disable Metrics/ParameterLists

RBS:

  • (IR::Grammar grammar, ?seed: Integer, ?count: Integer, ?max_tokens: Integer, ?max_depth: Integer, ?max_expansions: Integer, ?max_actions: Integer, ?max_stack: Integer, ?coverage_guided: bool, ?path_length: Integer, ?algorithms: Array[Symbol], ?ielr_strategy: Symbol, ?automata: Hash[Symbol, IR::Automaton]?, ?against: (^(Array[String]) -> Symbol)?, ?against_description: Hash[Symbol, Object?]?) -> void

Parameters:

  • grammar (IR::Grammar)
  • seed: (Integer) (defaults to: 0)
  • count: (Integer) (defaults to: 100)
  • max_tokens: (Integer) (defaults to: 32)
  • max_depth: (Integer) (defaults to: 16)
  • max_expansions: (Integer) (defaults to: Samples::DEFAULT_MAX_EXPANSIONS)
  • max_actions: (Integer) (defaults to: DEFAULT_MAX_ACTIONS)
  • max_stack: (Integer) (defaults to: DEFAULT_MAX_STACK)
  • coverage_guided: (Boolean) (defaults to: false)
  • path_length: (Integer) (defaults to: 2)
  • algorithms: (Array[Symbol]) (defaults to: ALGORITHMS)
  • ielr_strategy: (Symbol) (defaults to: :partition)
  • automata: (Hash[Symbol, IR::Automaton], nil) (defaults to: nil)
  • against: (^(Array[String]) -> Symbol, nil) (defaults to: nil)
  • against_description: (Hash[Symbol, Object?], nil) (defaults to: nil) 


57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/ibex/fuzz.rb', line 57

def initialize(grammar, seed: 0, count: 100, max_tokens: 32, max_depth: 16,
               max_expansions: Samples::DEFAULT_MAX_EXPANSIONS, max_actions: DEFAULT_MAX_ACTIONS,
               max_stack: DEFAULT_MAX_STACK, coverage_guided: false, path_length: 2,
               algorithms: ALGORITHMS, ielr_strategy: :partition, automata: nil,
               against: nil, against_description: nil)
  raise ArgumentError, "count must be positive" unless count.positive?
  raise ArgumentError, "algorithms must not be empty" if algorithms.empty?
  unless LALR::Builder::IELR_STRATEGIES.include?(ielr_strategy.to_sym)
    raise ArgumentError, "unknown IELR construction strategy #{ielr_strategy.inspect}"
  end

  @grammar = grammar
  @seed = seed
  @count = count
  @random = Random.new(seed ^ 0x1BE)
  @max_tokens = max_tokens
  @max_depth = max_depth
  @max_expansions = max_expansions
  @max_actions = max_actions
  @max_stack = max_stack
  @coverage_guided = coverage_guided
  @path_length = path_length
  @algorithms = algorithms.map(&:to_sym).freeze
  @ielr_strategy = ielr_strategy.to_sym
  @automata = automata || build_automata
  @against = against
  @against_description = against_description
end

Instance Method Details

#budget_error?(error) ⇒ Boolean

RBS:

  • (Ibex::Error error) -> bool

Parameters:

Returns:

  • (Boolean) 


213
214
215
216
217
 
# File 'lib/ibex/fuzz.rb', line 213

def budget_error?(error)
  error.message.match?(
    /simulation exceeded|(?:limit|maximum|budget).*(?:exceed|exhaust)|exceed.*(?:limit|maximum|budget)/i
  )
end

#build_automata ⇒ Hash[Symbol, IR::Automaton]

RBS:

  • () -> Hash[Symbol, IR::Automaton]

Returns:



153
154
155
156
157
158
159
160
161
162
 
# File 'lib/ibex/fuzz.rb', line 153

def build_automata
  @algorithms.to_h do |algorithm|
    builder = LALR::Builder.new(
      @grammar,
      algorithm: algorithm,
      ielr_strategy: @ielr_strategy
    )
    [algorithm, builder.build]
  end
end

#compare!(tokens, kind:, sentence:) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[String] tokens, kind: Symbol, sentence: Integer) -> void

Parameters:

  • tokens (Array[String])
  • kind: (Symbol)
  • sentence: (Integer) 


165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
 
# File 'lib/ibex/fuzz.rb', line 165

def compare!(tokens, kind:, sentence:)
  outcomes = @algorithms.to_h do |algorithm|
    automaton = @automata.fetch(algorithm)
    simulator = TableSimulation::Simulator.new(
      automaton, max_steps: @max_actions, max_stack: @max_stack
    )
    [algorithm, simulator.simulate(tokens).status]
  rescue Ibex::Error => e
    if budget_error?(e)
      raise BudgetExceeded.new(
        message: e.message, tokens: tokens,
        bounds: { max_actions: @max_actions, max_stack: @max_stack }
      )
    end
    [algorithm, [:failure, e.class.name, e.message]]
  end
  outcomes[:external] = @against.call(tokens) if @against
  values = outcomes.values.uniq
  return if values.length == 1 && (kind != :generated || values.first == :accepted)

  raise Mismatch.new(tokens: tokens, kind: kind, sentence: sentence, outcomes: outcomes,
                     bounds: { max_actions: @max_actions, max_stack: @max_stack })
end

#generate_sentences ⇒ Array[Array[String]]

RBS:

  • () -> Array[Array[String]]

Returns:

  • (Array[Array[String]]) 


124
125
126
127
128
129
130
 
# File 'lib/ibex/fuzz.rb', line 124

def generate_sentences
  Samples.new(
    @grammar, seed: @seed, max_tokens: @max_tokens, max_depth: @max_depth,
              max_expansions: @max_expansions, strategy: @coverage_guided ? :coverage : :random,
              path_length: @path_length
  ).generate(count: @count)
end

#minimize(mismatch, max_trials: 1_000) ⇒ DeltaReducer::Result

Minimize one observed mismatch without changing its kind or outcomes.

RBS:

  • (Mismatch mismatch, ?max_trials: Integer) -> DeltaReducer::Result

Parameters:

  • mismatch (Mismatch)
  • max_trials: (Integer) (defaults to: 1_000)

Returns:



110
111
112
113
114
115
116
117
118
119
 
# File 'lib/ibex/fuzz.rb', line 110

def minimize(mismatch, max_trials: 1_000)
  details = mismatch.details
  original = details[:tokens]
  kind = details[:kind].to_sym
  sentence = details[:sentence]
  outcomes = details[:outcomes]
  DeltaReducer.new(max_trials: max_trials).minimize(original) do |candidate|
    mismatch_reproduced?(candidate, kind: kind, sentence: sentence, outcomes: outcomes)
  end
end

#mismatch_reproduced?(tokens, kind:, sentence:, outcomes:) ⇒ Boolean

RBS:

  • (Array[String] tokens, kind: Symbol, sentence: Integer, outcomes: Hash[Symbol, fuzz_outcome]) -> bool

Parameters:

  • tokens (Array[String])
  • kind: (Symbol)
  • sentence: (Integer)
  • outcomes: (Hash[Symbol, fuzz_outcome])

Returns:

  • (Boolean) 


204
205
206
207
208
209
210
 
# File 'lib/ibex/fuzz.rb', line 204

def mismatch_reproduced?(tokens, kind:, sentence:, outcomes:)
  compare!(tokens, kind: kind, sentence: sentence)
  false
rescue Mismatch => e
  e.details[:kind].to_sym == kind &&
    e.details[:outcomes] == outcomes
end

#mutations(tokens) ⇒ Array[Array[String]]

RBS:

  • (Array[String] tokens) -> Array[Array[String]]

Parameters:

  • tokens (Array[String])

Returns:

  • (Array[Array[String]]) 


190
191
192
193
194
195
196
197
198
199
200
 
# File 'lib/ibex/fuzz.rb', line 190

def mutations(tokens)
  terminals = @grammar.terminals.reject(&:reserved).map(&:name)
  replacement = terminals.fetch(@random.rand(terminals.length))
  index = tokens.empty? ? 0 : @random.rand(tokens.length)
  inserted = tokens.dup.insert(index, replacement)
  return [inserted] if tokens.empty?

  deleted = tokens.dup.tap { |items| items.delete_at(index) }
  replaced = tokens.dup.tap { |items| items[index] = replacement }
  [inserted, deleted, replaced].uniq
end

#run ⇒ Hash[Symbol, Object?]

RBS:

  • () -> Hash[Symbol, Object?]

Returns:

  • (Hash[Symbol, Object?]) 


88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'lib/ibex/fuzz.rb', line 88

def run
  sentences = generate_sentences
  mutation_count = 0
  sentences.each_with_index do |tokens, index|
    compare!(tokens, kind: :generated, sentence: index)
    mutations(tokens).each do |mutation|
      compare!(mutation, kind: :mutation, sentence: index)
      mutation_count += 1
    end
  end
  successful_report(sentences.length, mutation_count)
rescue Ibex::Error => e
  raise if e.is_a?(Mismatch) || e.is_a?(BudgetExceeded) || !budget_error?(e)

  raise BudgetExceeded.new(
    message: e.message,
    bounds: { max_expansions: @max_expansions, max_actions: @max_actions, max_stack: @max_stack }
  )
end

#successful_report(sentence_count, mutation_count) ⇒ Object

RBS:

  • (Integer sentence_count, Integer mutation_count) -> untyped

Parameters:

  • sentence_count (Integer)
  • mutation_count (Integer)

Returns:

  • (Object) 


133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/ibex/fuzz.rb', line 133

def successful_report(sentence_count, mutation_count)
  report = {
    ibex_report: "fuzz", schema_version: 1, seed: @seed,
    bounds: {
      sentences: @count, max_tokens: @max_tokens, max_depth: @max_depth,
      max_expansions: @max_expansions, max_actions: @max_actions, max_stack: @max_stack
    },
    strategy: @coverage_guided ? "coverage" : "random",
    path_length: @path_length,
    ielr_strategy: @ielr_strategy.to_s,
    algorithms: @algorithms.map(&:to_s),
    generated_sentences: sentence_count,
    mutated_sentences: mutation_count,
    result: "no_difference_within_bounds"
  }
  report[:external] = @against_description if @against_description
  IR.deep_freeze(report)
end