1#
2# Copyright (C) 2016 The Android Open Source Project
3#
4# Licensed under the Apache License, Version 2.0 (the "License");
5# you may not use this file except in compliance with the License.
6# You may obtain a copy of the License at
7#
8#      http://www.apache.org/licenses/LICENSE-2.0
9#
10# Unless required by applicable law or agreed to in writing, software
11# distributed under the License is distributed on an "AS IS" BASIS,
12# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13# See the License for the specific language governing permissions and
14# limitations under the License.
15#
16
17import random
18
19REPLICATION_COUNT_IF_NEW_COVERAGE_IS_SEEN = 5
20REPLICATION_PARAM_IF_NO_COVERAGE_IS_SEEN = 10
21
22
23def CreateGenePool(count, generator, fuzzer, **kwargs):
24  """Creates a gene pool, a set of test input data.
25
26  Args:
27    count: integer, the size of the pool.
28    generator: function pointer, which can generate the data.
29    fuzzer: function pointer, which can mutate the data.
30    **kwargs: the args to the generator function pointer.
31
32  Returns:
33    a list of generated data.
34  """
35  genes = []
36  for index in range(count):
37    gene = generator(**kwargs)
38    genes.append(fuzzer(gene))
39  return genes
40
41
42class Evolution(object):
43  """Evolution class
44
45  Attributes:
46    _coverages_database: a list of coverage entities seen previously.
47    _alpha: replication count if new coverage is seen.
48    _beta: replication parameter if no coverage is seen.
49  """
50
51  def __init__(self, alpha=REPLICATION_COUNT_IF_NEW_COVERAGE_IS_SEEN,
52               beta=REPLICATION_PARAM_IF_NO_COVERAGE_IS_SEEN):
53    self._coverages_database = []
54    self._alpha = alpha
55    self._beta = beta
56
57  def _IsNewCoverage(self, coverage, add=False):
58    """Returns True iff the 'coverage' is new.
59
60    Args:
61      coverage: int, a coverage entity
62      add: boolean, true to add coverage to the db if it's new.
63
64    Returns:
65      True if new, False otherwise
66    """
67    is_new_coverage = False
68    new_coverage_entities_to_add = []
69    for entity in coverage:
70      if entity not in self._coverages_database:
71        is_new_coverage = True
72        if add:
73          new_coverage_entities_to_add.append(entity)
74        else:
75          return True
76    if add:
77      self._coverages_database.extend(new_coverage_entities_to_add)
78    return is_new_coverage
79
80  def Evolve(self, genes, fuzzer, coverages=None):
81    """Evolves a gene pool.
82
83    Args:
84      genes: a list of input data.
85      fuzzer: function pointer, which can mutate the data.
86      coverages: a list of the coverage data where coverage data is a list which
87        contains IDs of the covered entities (e.g., basic blocks).
88
89    Returns:
90      a list of evolved data.
91    """
92    new_genes = []
93    if not coverages:
94      for gene in genes:
95        # TODO: consider cross over
96        new_genes.append(fuzzer(gene))
97    else:
98      for gene, coverage in zip(genes, coverages):
99        if self._IsNewCoverage(coverage, add=True):
100          for _ in range(self._alpha):
101            new_genes.append(fuzzer(gene))
102        elif random.randint(0, self._beta) == 1:
103          new_genes.append(fuzzer(gene))
104    return new_genes
105