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: " << toString(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: " << toString(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: " << toString(operation.opType);
298         TestOperation testOperation = {.type = static_cast<TestOperationType>(operation.opType)};
299         for (auto& op : operation.inputs) {
300             NN_FUZZER_LOG << toString(*op);
301             testOperation.inputs.push_back(op->opIndex);
302         }
303         for (auto& op : operation.outputs) {
304             NN_FUZZER_LOG << toString(*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