1  /*
2   * Copyright (C) 2019 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  
17  #include "fuzzing/RandomGraphGenerator.h"
18  
19  #include <gtest/gtest.h>
20  
21  #include <algorithm>
22  #include <cmath>
23  #include <memory>
24  #include <set>
25  #include <string>
26  #include <unordered_map>
27  #include <utility>
28  #include <vector>
29  
30  #include "TestHarness.h"
31  #include "TestNeuralNetworksWrapper.h"
32  #include "fuzzing/OperationManager.h"
33  #include "fuzzing/RandomGraphGeneratorUtils.h"
34  #include "fuzzing/RandomVariable.h"
35  
36  namespace android {
37  namespace nn {
38  namespace fuzzing_test {
39  
40  using test_wrapper::Result;
41  using namespace test_helper;
42  
43  // Construct a RandomOperand from OperandSignature.
RandomOperand(const OperandSignature & operand,TestOperandType dataType,uint32_t rank)44  RandomOperand::RandomOperand(const OperandSignature& operand, TestOperandType dataType,
45                               uint32_t rank)
46      : type(operand.type), finalizer(operand.finalizer) {
47      NN_FUZZER_LOG << "Operand: " << type;
48      if (operand.constructor) operand.constructor(dataType, rank, this);
49  }
50  
getDimensions() const51  std::vector<uint32_t> RandomOperand::getDimensions() const {
52      std::vector<uint32_t> result(dimensions.size(), 0);
53      for (uint32_t i = 0; i < dimensions.size(); i++) result[i] = dimensions[i].getValue();
54      return result;
55  }
56  
areValuePropertiesCompatible(int guaranteed,int required)57  static bool areValuePropertiesCompatible(int guaranteed, int required) {
58      return !(~guaranteed & required);
59  }
60  
61  // Check if an edge between [this, other] is valid. If yes, add the edge.
createEdgeIfValid(const RandomOperand & other) const62  bool RandomOperand::createEdgeIfValid(const RandomOperand& other) const {
63      if (other.type != RandomOperandType::INPUT) return false;
64      if (dataType != other.dataType || dimensions.size() != other.dimensions.size() ||
65          scale != other.scale || zeroPoint != other.zeroPoint || doNotConnect ||
66          other.doNotConnect || !areValuePropertiesCompatible(valueProperties, other.valueProperties))
67          return false;
68      return RandomVariableNetwork::get()->setEqualIfCompatible(dimensions, other.dimensions);
69  }
70  
getNumberOfElements() const71  uint32_t RandomOperand::getNumberOfElements() const {
72      uint32_t num = 1;
73      for (const auto& d : dimensions) num *= d.getValue();
74      return num;
75  }
76  
getBufferSize() const77  size_t RandomOperand::getBufferSize() const {
78      return kSizeOfDataType[static_cast<int32_t>(dataType)] * getNumberOfElements();
79  }
80  
81  // Construct a RandomOperation from OperationSignature.
RandomOperation(const OperationSignature & operation)82  RandomOperation::RandomOperation(const OperationSignature& operation)
83      : opType(operation.opType), finalizer(operation.finalizer) {
84      NN_FUZZER_LOG << "Operation: " << opType;
85  
86      // Determine the data type and rank of the operation and invoke the constructor.
87      TestOperandType dataType = getRandomChoice(operation.supportedDataTypes);
88      uint32_t rank = getRandomChoice(operation.supportedRanks);
89  
90      // Initialize operands and operation.
91      for (const auto& op : operation.inputs) {
92          inputs.emplace_back(new RandomOperand(op, dataType, rank));
93      }
94      for (const auto& op : operation.outputs) {
95          outputs.emplace_back(new RandomOperand(op, dataType, rank));
96      }
97      if (operation.constructor) operation.constructor(dataType, rank, this);
98  
99      // Add constraints on the number of elements.
100      if (RandomVariable::defaultValue > 10) {
101          for (auto in : inputs) RandomVariableNetwork::get()->addDimensionProd(in->dimensions);
102          for (auto out : outputs) RandomVariableNetwork::get()->addDimensionProd(out->dimensions);
103      }
104      // The output operands should have dimensions larger than 0.
105      for (auto out : outputs) {
106          for (auto& dim : out->dimensions) dim.setRange(1, kInvalidValue);
107      }
108  }
109  
generate(uint32_t seed,uint32_t numOperations,uint32_t dimensionRange)110  bool RandomGraph::generate(uint32_t seed, uint32_t numOperations, uint32_t dimensionRange) {
111      RandomNumberGenerator::generator.seed(seed);
112      // The generator may (with low probability) end up with an invalid graph.
113      // If so, regenerate the graph until a valid one is produced.
114      while (true) {
115          RandomVariableNetwork::get()->initialize(dimensionRange);
116          mOperations.clear();
117          mOperands.clear();
118          if (generateGraph(numOperations) && generateValue()) break;
119          std::cout << "[ Retry    ]   The RandomGraphGenerator produces an invalid graph.\n";
120      }
121      return true;
122  }
123  
generateGraph(uint32_t numOperations)124  bool RandomGraph::generateGraph(uint32_t numOperations) {
125      NN_FUZZER_LOG << "Generate Graph";
126      // Randomly generate a vector of operations, this is a valid topological sort.
127      for (uint32_t i = 0; i < numOperations; i++) {
128          mOperations.emplace_back(OperationManager::get()->getRandomOperation());
129      }
130  
131      // Randomly add edges from the output of one operation to the input of another operation
132      // with larger positional index.
133      for (uint32_t i = 0; i < numOperations; i++) {
134          for (auto& output : mOperations[i].outputs) {
135              for (uint32_t j = i + 1; j < numOperations; j++) {
136                  for (auto& input : mOperations[j].inputs) {
137                      // For each [output, input] pair, add an edge with probability prob.
138                      // TODO: Find a better formula by first defining what "better" is.
139                      float prob = 0.1f;
140                      if (getBernoulli(prob)) {
141                          if (output->createEdgeIfValid(*input)) {
142                              NN_FUZZER_LOG << "Add edge: operation " << i << " -> " << j;
143                              input = output;
144                              output->type = RandomOperandType::INTERNAL;
145                          }
146                      }
147                  }
148              }
149          }
150      }
151      return true;
152  }
153  
asConstant(const std::shared_ptr<RandomOperand> & operand,float prob=0.5f)154  static bool asConstant(const std::shared_ptr<RandomOperand>& operand, float prob = 0.5f) {
155      if (operand->type == RandomOperandType::CONST) return true;
156      if (operand->type != RandomOperandType::INPUT) return false;
157      // Force all scalars to be CONST.
158      if (kScalarDataType[static_cast<int32_t>(operand->dataType)]) return true;
159      if (getBernoulli(prob)) return true;
160      return false;
161  }
162  
163  // Freeze the dimensions to a random but valid combination.
164  // Generate random buffer values for model inputs and constants.
generateValue()165  bool RandomGraph::generateValue() {
166      NN_FUZZER_LOG << "Generate Value";
167      if (!RandomVariableNetwork::get()->freeze()) return false;
168  
169      // Fill all unique operands into mOperands.
170      std::set<std::shared_ptr<RandomOperand>> seen;
171      auto fillOperands = [&seen, this](const std::vector<std::shared_ptr<RandomOperand>>& ops) {
172          for (const auto& op : ops) {
173              if (seen.find(op) == seen.end()) {
174                  seen.insert(op);
175                  mOperands.push_back(op);
176              }
177          }
178      };
179      for (const auto& operation : mOperations) {
180          fillOperands(operation.inputs);
181          fillOperands(operation.outputs);
182      }
183  
184      // Count the number of INPUTs.
185      uint32_t numInputs = 0;
186      for (auto& operand : mOperands) {
187          if (operand->type == RandomOperandType::INPUT) numInputs++;
188      }
189  
190      auto requiresBufferAllocation = [](std::shared_ptr<RandomOperand>& operand) -> bool {
191          return operand->type != RandomOperandType::INTERNAL &&
192                 operand->type != RandomOperandType::NO_VALUE;
193      };
194  
195      for (auto& operand : mOperands) {
196          // Turn INPUT into CONST with probability prob. Need to keep at least one INPUT.
197          float prob = 0.5f;
198          if (asConstant(operand, prob) && numInputs > 1) {
199              if (operand->type == RandomOperandType::INPUT) numInputs--;
200              operand->type = RandomOperandType::CONST;
201          }
202          if (requiresBufferAllocation(operand)) {
203              if (operand->buffer.empty()) operand->resizeBuffer<uint8_t>(operand->getBufferSize());
204              // If operand is set by randomBuffer, copy the frozen values into buffer.
205              if (!operand->randomBuffer.empty()) {
206                  int32_t* data = reinterpret_cast<int32_t*>(operand->buffer.data());
207                  for (uint32_t i = 0; i < operand->randomBuffer.size(); i++) {
208                      data[i] = operand->randomBuffer[i].getValue();
209                  }
210              }
211              if (operand->finalizer) operand->finalizer(operand.get());
212          }
213      }
214  
215      for (auto& operation : mOperations) {
216          for (auto operand : operation.inputs) {
217              if (requiresBufferAllocation(operand)) {
218                  NN_FUZZER_CHECK(!operand->buffer.empty())
219                          << " input operand has no allocated buffer!";
220              }
221          }
222  
223          for (auto& operand : operation.outputs) {
224              if (requiresBufferAllocation(operand)) {
225                  NN_FUZZER_CHECK(!operand->buffer.empty())
226                          << " output operand has no allocated buffer!";
227              }
228          }
229  
230          if (operation.finalizer) operation.finalizer(&operation);
231      }
232      return true;
233  }
234  
convertToTestOperandLifeTime(RandomOperandType type)235  static TestOperandLifeTime convertToTestOperandLifeTime(RandomOperandType type) {
236      switch (type) {
237          case RandomOperandType::INPUT:
238              return TestOperandLifeTime::SUBGRAPH_INPUT;
239          case RandomOperandType::OUTPUT:
240              return TestOperandLifeTime::SUBGRAPH_OUTPUT;
241          case RandomOperandType::INTERNAL:
242              return TestOperandLifeTime::TEMPORARY_VARIABLE;
243          case RandomOperandType::CONST:
244              return TestOperandLifeTime::CONSTANT_COPY;
245          case RandomOperandType::NO_VALUE:
246              return TestOperandLifeTime::NO_VALUE;
247      }
248  }
249  
createTestModel()250  TestModel RandomGraph::createTestModel() {
251      NN_FUZZER_LOG << "Create Test Model";
252      TestModel testModel;
253  
254      // Set model operands.
255      for (auto& operand : mOperands) {
256          operand->opIndex = testModel.main.operands.size();
257          TestOperand testOperand = {
258                  .type = static_cast<TestOperandType>(operand->dataType),
259                  .dimensions = operand->getDimensions(),
260                  // It is safe to always set numberOfConsumers to 0 here because
261                  // this field is not used in NDK.
262                  .numberOfConsumers = 0,
263                  .scale = operand->scale,
264                  .zeroPoint = operand->zeroPoint,
265                  .lifetime = convertToTestOperandLifeTime(operand->type),
266                  .isIgnored = operand->doNotCheckAccuracy,
267          };
268  
269          // Test buffers.
270          switch (testOperand.lifetime) {
271              case TestOperandLifeTime::SUBGRAPH_OUTPUT:
272                  testOperand.data = TestBuffer(operand->getBufferSize());
273                  break;
274              case TestOperandLifeTime::SUBGRAPH_INPUT:
275              case TestOperandLifeTime::CONSTANT_COPY:
276              case TestOperandLifeTime::CONSTANT_REFERENCE:
277                  testOperand.data = TestBuffer(operand->getBufferSize(), operand->buffer.data());
278                  break;
279              case TestOperandLifeTime::TEMPORARY_VARIABLE:
280              case TestOperandLifeTime::NO_VALUE:
281                  break;
282              default:
283                  NN_FUZZER_CHECK(false) << "Unknown lifetime";
284          }
285  
286          // Input/Output indexes.
287          if (testOperand.lifetime == TestOperandLifeTime::SUBGRAPH_INPUT) {
288              testModel.main.inputIndexes.push_back(operand->opIndex);
289          } else if (testOperand.lifetime == TestOperandLifeTime::SUBGRAPH_OUTPUT) {
290              testModel.main.outputIndexes.push_back(operand->opIndex);
291          }
292          testModel.main.operands.push_back(std::move(testOperand));
293      }
294  
295      // Set model operations.
296      for (auto& operation : mOperations) {
297          NN_FUZZER_LOG << "Operation: " << operation.opType;
298          TestOperation testOperation = {.type = static_cast<TestOperationType>(operation.opType)};
299          for (auto& op : operation.inputs) {
300              NN_FUZZER_LOG << *op;
301              testOperation.inputs.push_back(op->opIndex);
302          }
303          for (auto& op : operation.outputs) {
304              NN_FUZZER_LOG << *op;
305              testOperation.outputs.push_back(op->opIndex);
306          }
307          testModel.main.operations.push_back(std::move(testOperation));
308      }
309      return testModel;
310  }
311  
312  }  // namespace fuzzing_test
313  }  // namespace nn
314  }  // namespace android
315