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