• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# Copyright 2018 the V8 project authors. All rights reserved.
2# Use of this source code is governed by a BSD-style license that can be
3# found in the LICENSE file.
4
5from collections import namedtuple
6import time
7
8from . import base
9
10
11class FuzzerConfig(object):
12  def __init__(self, probability, analyzer, fuzzer):
13    """
14    Args:
15      probability: of choosing this fuzzer (0; 10]
16      analyzer: instance of Analyzer class, can be None if no analysis is needed
17      fuzzer: instance of Fuzzer class
18    """
19    assert probability > 0 and probability <= 10
20
21    self.probability = probability
22    self.analyzer = analyzer
23    self.fuzzer = fuzzer
24
25
26class Analyzer(object):
27  def get_analysis_flags(self):
28    raise NotImplementedError()
29
30  def do_analysis(self, result):
31    raise NotImplementedError()
32
33
34class Fuzzer(object):
35  def create_flags_generator(self, rng, test, analysis_value):
36    """
37    Args:
38      rng: random number generator
39      test: test for which to create flags
40      analysis_value: value returned by the analyzer. None if there is no
41        corresponding analyzer to this fuzzer or the analysis phase is disabled
42    """
43    raise NotImplementedError()
44
45
46# TODO(majeski): Allow multiple subtests to run at once.
47class FuzzerProc(base.TestProcProducer):
48  def __init__(self, rng, count, fuzzers, disable_analysis=False):
49    """
50    Args:
51      rng: random number generator used to select flags and values for them
52      count: number of tests to generate based on each base test
53      fuzzers: list of FuzzerConfig instances
54      disable_analysis: disable analysis phase and filtering base on it. When
55        set, processor passes None as analysis result to fuzzers
56    """
57    super(FuzzerProc, self).__init__('Fuzzer')
58
59    self._rng = rng
60    self._count = count
61    self._fuzzer_configs = fuzzers
62    self._disable_analysis = disable_analysis
63    self._gens = {}
64
65  def setup(self, requirement=base.DROP_RESULT):
66    # Fuzzer is optimized to not store the results
67    assert requirement == base.DROP_RESULT
68    super(FuzzerProc, self).setup(requirement)
69
70  def _next_test(self, test):
71    if self.is_stopped:
72      return
73
74    analysis_subtest = self._create_analysis_subtest(test)
75    if analysis_subtest:
76      self._send_test(analysis_subtest)
77    else:
78      self._gens[test.procid] = self._create_gen(test)
79      self._try_send_next_test(test)
80
81  def _create_analysis_subtest(self, test):
82    if self._disable_analysis:
83      return None
84
85    analysis_flags = []
86    for fuzzer_config in self._fuzzer_configs:
87      if fuzzer_config.analyzer:
88        analysis_flags += fuzzer_config.analyzer.get_analysis_flags()
89
90    if analysis_flags:
91      analysis_flags = list(set(analysis_flags))
92      return self._create_subtest(test, 'analysis', flags=analysis_flags,
93                                  keep_output=True)
94
95
96  def _result_for(self, test, subtest, result):
97    if not self._disable_analysis:
98      if result is not None:
99        # Analysis phase, for fuzzing we drop the result.
100        if result.has_unexpected_output:
101          self._send_result(test, None)
102          return
103        self._gens[test.procid] = self._create_gen(test, result)
104
105    self._try_send_next_test(test)
106
107  def _create_gen(self, test, analysis_result=None):
108    # It will be called with analysis_result==None only when there is no
109    # analysis phase at all, so no fuzzer has it's own analyzer.
110    gens = []
111    indexes = []
112    for i, fuzzer_config in enumerate(self._fuzzer_configs):
113      analysis_value = None
114      if analysis_result and fuzzer_config.analyzer:
115        analysis_value = fuzzer_config.analyzer.do_analysis(analysis_result)
116        if not analysis_value:
117          # Skip fuzzer for this test since it doesn't have analysis data
118          continue
119      p = fuzzer_config.probability
120      flag_gen = fuzzer_config.fuzzer.create_flags_generator(self._rng, test,
121                                                             analysis_value)
122      indexes += [len(gens)] * p
123      gens.append((p, flag_gen))
124
125    if not gens:
126      # No fuzzers for this test, skip it
127      return
128
129    i = 0
130    while not self._count or i < self._count:
131      main_index = self._rng.choice(indexes)
132      _, main_gen = gens[main_index]
133
134      flags = next(main_gen)
135      for index, (p, gen) in enumerate(gens):
136        if index == main_index:
137          continue
138        if self._rng.randint(1, 10) <= p:
139          flags += next(gen)
140
141      flags.append('--fuzzer-random-seed=%s' % self._next_seed())
142      yield self._create_subtest(test, str(i), flags=flags)
143
144      i += 1
145
146  def _try_send_next_test(self, test):
147    if not self.is_stopped:
148      for subtest in self._gens[test.procid]:
149        self._send_test(subtest)
150        return
151
152    del self._gens[test.procid]
153    self._send_result(test, None)
154
155  def _next_seed(self):
156    seed = None
157    while not seed:
158      seed = self._rng.randint(-2147483648, 2147483647)
159    return seed
160
161
162class ScavengeAnalyzer(Analyzer):
163  def get_analysis_flags(self):
164    return ['--fuzzer-gc-analysis']
165
166  def do_analysis(self, result):
167    for line in reversed(result.output.stdout.splitlines()):
168      if line.startswith('### Maximum new space size reached = '):
169        return int(float(line.split()[7]))
170
171
172class ScavengeFuzzer(Fuzzer):
173  def create_flags_generator(self, rng, test, analysis_value):
174    while True:
175      yield ['--stress-scavenge=%d' % (analysis_value or 100)]
176
177
178class MarkingAnalyzer(Analyzer):
179  def get_analysis_flags(self):
180    return ['--fuzzer-gc-analysis']
181
182  def do_analysis(self, result):
183    for line in reversed(result.output.stdout.splitlines()):
184      if line.startswith('### Maximum marking limit reached = '):
185        return int(float(line.split()[6]))
186
187
188class MarkingFuzzer(Fuzzer):
189  def create_flags_generator(self, rng, test, analysis_value):
190    while True:
191      yield ['--stress-marking=%d' % (analysis_value or 100)]
192
193
194class GcIntervalAnalyzer(Analyzer):
195  def get_analysis_flags(self):
196    return ['--fuzzer-gc-analysis']
197
198  def do_analysis(self, result):
199    for line in reversed(result.output.stdout.splitlines()):
200      if line.startswith('### Allocations = '):
201        return int(float(line.split()[3][:-1]))
202
203
204class GcIntervalFuzzer(Fuzzer):
205  def create_flags_generator(self, rng, test, analysis_value):
206    if analysis_value:
207      value = analysis_value / 10
208    else:
209      value = 10000
210    while True:
211      yield ['--random-gc-interval=%d' % value]
212
213
214class CompactionFuzzer(Fuzzer):
215  def create_flags_generator(self, rng, test, analysis_value):
216    while True:
217      yield ['--stress-compaction-random']
218
219
220class ThreadPoolSizeFuzzer(Fuzzer):
221  def create_flags_generator(self, rng, test, analysis_value):
222    while True:
223      yield ['--thread-pool-size=%d' % rng.randint(1, 8)]
224
225
226class InterruptBudgetFuzzer(Fuzzer):
227  def create_flags_generator(self, rng, test, analysis_value):
228    while True:
229      limit = 1 + int(rng.random() * 144)
230      yield ['--interrupt-budget=%d' % rng.randint(1, limit * 1024)]
231
232
233class DeoptAnalyzer(Analyzer):
234  MAX_DEOPT=1000000000
235
236  def __init__(self, min_interval):
237    super(DeoptAnalyzer, self).__init__()
238    self._min = min_interval
239
240  def get_analysis_flags(self):
241    return ['--deopt-every-n-times=%d' % self.MAX_DEOPT,
242            '--print-deopt-stress']
243
244  def do_analysis(self, result):
245    for line in reversed(result.output.stdout.splitlines()):
246      if line.startswith('=== Stress deopt counter: '):
247        counter = self.MAX_DEOPT - int(line.split(' ')[-1])
248        if counter < self._min:
249          # Skip this test since we won't generate any meaningful interval with
250          # given minimum.
251          return None
252        return counter
253
254
255class DeoptFuzzer(Fuzzer):
256  def __init__(self, min_interval):
257    super(DeoptFuzzer, self).__init__()
258    self._min = min_interval
259
260  def create_flags_generator(self, rng, test, analysis_value):
261    while True:
262      if analysis_value:
263        value = analysis_value / 2
264      else:
265        value = 10000
266      interval = rng.randint(self._min, max(value, self._min))
267      yield ['--deopt-every-n-times=%d' % interval]
268
269
270FUZZERS = {
271  'compaction': (None, CompactionFuzzer),
272  'deopt': (DeoptAnalyzer, DeoptFuzzer),
273  'gc_interval': (GcIntervalAnalyzer, GcIntervalFuzzer),
274  'interrupt_budget': (None, InterruptBudgetFuzzer),
275  'marking': (MarkingAnalyzer, MarkingFuzzer),
276  'scavenge': (ScavengeAnalyzer, ScavengeFuzzer),
277  'threads': (None, ThreadPoolSizeFuzzer),
278}
279
280
281def create_fuzzer_config(name, probability, *args, **kwargs):
282  analyzer_class, fuzzer_class = FUZZERS[name]
283  return FuzzerConfig(
284      probability,
285      analyzer_class(*args, **kwargs) if analyzer_class else None,
286      fuzzer_class(*args, **kwargs),
287  )
288