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 <cmath> 22 #include <string> 23 #include <unordered_map> 24 #include <vector> 25 26 #include "TestNeuralNetworksWrapper.h" 27 #include "fuzzing/OperationManager.h" 28 #include "fuzzing/RandomGraphGeneratorUtils.h" 29 #include "fuzzing/RandomVariable.h" 30 31 namespace android { 32 namespace nn { 33 namespace fuzzing_test { 34 35 using test_wrapper::Result; 36 using test_wrapper::Type; 37 38 // Construct a RandomOperand from OperandSignature. 39 RandomOperand::RandomOperand(const OperandSignature& operand, Type dataType, uint32_t rank) 40 : type(operand.type), finalizer(operand.finalizer) { 41 NN_FUZZER_LOG << "Operand: " << toString(type); 42 if (operand.constructor) operand.constructor(dataType, rank, this); 43 } 44 45 std::vector<uint32_t> RandomOperand::getDimensions() const { 46 std::vector<uint32_t> result(dimensions.size(), 0); 47 for (uint32_t i = 0; i < dimensions.size(); i++) result[i] = dimensions[i].getValue(); 48 return result; 49 } 50 51 // Check if an edge between [this, other] is valid. If yes, add the edge. 52 bool RandomOperand::createEdgeIfValid(const RandomOperand& other) const { 53 if (other.type != RandomOperandType::INPUT) return false; 54 if (dataType != other.dataType || dimensions.size() != other.dimensions.size() || 55 scale != other.scale || zeroPoint != other.zeroPoint || doNotConnect || other.doNotConnect) 56 return false; 57 return RandomVariableNetwork::get()->setEqualIfCompatible(dimensions, other.dimensions); 58 } 59 60 uint32_t RandomOperand::getNumberOfElements() const { 61 uint32_t num = 1; 62 for (const auto& d : dimensions) num *= d.getValue(); 63 return num; 64 } 65 66 size_t RandomOperand::getBufferSize() const { 67 return kSizeOfDataType[static_cast<int32_t>(dataType)] * getNumberOfElements(); 68 } 69 70 // Construct a RandomOperation from OperationSignature. 71 RandomOperation::RandomOperation(const OperationSignature& operation) 72 : opType(operation.opType), finalizer(operation.finalizer) { 73 NN_FUZZER_LOG << "Operation: " << kOperationNames[static_cast<int32_t>(opType)]; 74 75 // Determine the data type and rank of the operation and invoke the constructor. 76 Type dataType = getRandomChoice(operation.supportedDataTypes); 77 uint32_t rank = getRandomChoice(operation.supportedRanks); 78 79 // Initialize operands and operation. 80 for (const auto& op : operation.inputs) { 81 inputs.emplace_back(new RandomOperand(op, dataType, rank)); 82 } 83 for (const auto& op : operation.outputs) { 84 outputs.emplace_back(new RandomOperand(op, dataType, rank)); 85 } 86 if (operation.constructor) operation.constructor(dataType, rank, this); 87 88 // Add constraints on the number of elements. 89 if (RandomVariable::defaultValue > 10) { 90 for (auto in : inputs) RandomVariableNetwork::get()->addDimensionProd(in->dimensions); 91 for (auto out : outputs) RandomVariableNetwork::get()->addDimensionProd(out->dimensions); 92 } 93 // The output operands should have dimensions larger than 0. 94 for (auto out : outputs) { 95 for (auto& dim : out->dimensions) dim.setRange(1, kInvalidValue); 96 } 97 } 98 99 bool RandomGraph::generate(uint32_t seed, uint32_t numOperations, uint32_t dimensionRange) { 100 RandomNumberGenerator::generator.seed(seed); 101 // The generator may (with low probability) end up with an invalid graph. 102 // If so, regenerate the graph until a valid one is produced. 103 while (true) { 104 RandomVariableNetwork::get()->initialize(dimensionRange); 105 mOperations.clear(); 106 mOperands.clear(); 107 if (generateGraph(numOperations) && generateValue()) break; 108 std::cout << "[ Retry ] The RandomGraphGenerator produces an invalid graph.\n"; 109 } 110 return true; 111 } 112 113 bool RandomGraph::generateGraph(uint32_t numOperations) { 114 NN_FUZZER_LOG << "Generate Graph"; 115 // Randomly generate a vector of operations, this is a valid topological sort. 116 for (uint32_t i = 0; i < numOperations; i++) { 117 mOperations.emplace_back(OperationManager::get()->getRandomOperation()); 118 } 119 120 // Randomly add edges from the output of one operation to the input of another operation 121 // with larger positional index. 122 for (uint32_t i = 0; i < numOperations; i++) { 123 for (auto& output : mOperations[i].outputs) { 124 for (uint32_t j = i + 1; j < numOperations; j++) { 125 for (auto& input : mOperations[j].inputs) { 126 // For each [output, input] pair, add an edge with probability prob. 127 // TODO: Find a better formula by first defining what "better" is. 128 float prob = 0.1f; 129 if (getBernoulli(prob)) { 130 if (output->createEdgeIfValid(*input)) { 131 NN_FUZZER_LOG << "Add edge: operation " << i << " -> " << j; 132 input = output; 133 output->type = RandomOperandType::INTERNAL; 134 } 135 } 136 } 137 } 138 } 139 } 140 return true; 141 } 142 143 static bool asConstant(const std::shared_ptr<RandomOperand>& operand, float prob = 0.5f) { 144 if (operand->type == RandomOperandType::CONST) return true; 145 if (operand->type != RandomOperandType::INPUT) return false; 146 // Force all scalars to be CONST. 147 if (kScalarDataType[static_cast<int32_t>(operand->dataType)]) return true; 148 if (getBernoulli(prob)) return true; 149 return false; 150 } 151 152 // Freeze the dimensions to a random but valid combination. 153 // Generate random buffer values for model inputs and constants. 154 bool RandomGraph::generateValue() { 155 NN_FUZZER_LOG << "Generate Value"; 156 if (!RandomVariableNetwork::get()->freeze()) return false; 157 158 // Fill all unique operands into mOperands. 159 std::set<std::shared_ptr<RandomOperand>> seen; 160 auto fillOperands = [&seen, this](const std::vector<std::shared_ptr<RandomOperand>>& ops) { 161 for (const auto& op : ops) { 162 if (seen.find(op) == seen.end()) { 163 seen.insert(op); 164 mOperands.push_back(op); 165 } 166 } 167 }; 168 for (const auto& operation : mOperations) { 169 fillOperands(operation.inputs); 170 fillOperands(operation.outputs); 171 } 172 173 // Count the number of INPUTs. 174 uint32_t numInputs = 0; 175 for (auto& operand : mOperands) { 176 if (operand->type == RandomOperandType::INPUT) numInputs++; 177 } 178 179 for (auto& operand : mOperands) { 180 // Turn INPUT into CONST with probability prob. Need to keep at least one INPUT. 181 float prob = 0.5f; 182 if (asConstant(operand, prob) && numInputs > 1) { 183 if (operand->type == RandomOperandType::INPUT) numInputs--; 184 operand->type = RandomOperandType::CONST; 185 } 186 if (operand->type != RandomOperandType::INTERNAL) { 187 if (operand->buffer.empty()) operand->resizeBuffer<uint8_t>(operand->getBufferSize()); 188 // If operand is set by randomBuffer, copy the frozen values into buffer. 189 if (!operand->randomBuffer.empty()) { 190 int32_t* data = reinterpret_cast<int32_t*>(operand->buffer.data()); 191 for (uint32_t i = 0; i < operand->randomBuffer.size(); i++) { 192 data[i] = operand->randomBuffer[i].getValue(); 193 } 194 } 195 if (operand->finalizer) operand->finalizer(operand.get()); 196 } 197 } 198 199 for (auto& operation : mOperations) { 200 if (operation.finalizer) operation.finalizer(&operation); 201 } 202 return true; 203 } 204 205 void RandomGraph::createModel(test_wrapper::Model* model) { 206 NN_FUZZER_LOG << "Create Model"; 207 208 // Set model operands. 209 std::vector<uint32_t> modelInputs; 210 std::vector<uint32_t> modelOutputs; 211 for (auto& operand : mOperands) { 212 // TODO: Model operands are always fully-specified at model construction time. 213 test_wrapper::OperandType type(operand->dataType, operand->getDimensions(), operand->scale, 214 operand->zeroPoint); 215 operand->opIndex = model->addOperand(&type); 216 217 // For INPUT/OUTPUT, prepare vectors for identifyInputsAndOutputs(...). 218 // For CONST, set operand buffer. 219 if (operand->type == RandomOperandType::INPUT) { 220 operand->ioIndex = modelInputs.size(); 221 modelInputs.push_back(operand->opIndex); 222 } else if (operand->type == RandomOperandType::OUTPUT) { 223 operand->ioIndex = modelOutputs.size(); 224 modelOutputs.push_back(operand->opIndex); 225 } else if (operand->type == RandomOperandType::CONST) { 226 model->setOperandValue(operand->opIndex, operand->buffer.data(), 227 operand->getBufferSize()); 228 } 229 } 230 231 // Set model operations. 232 for (auto& operation : mOperations) { 233 NN_FUZZER_LOG << "Operation: " << kOperationNames[static_cast<int32_t>(operation.opType)]; 234 std::vector<uint32_t> inputIndices, outputIndices; 235 for (auto& op : operation.inputs) { 236 NN_FUZZER_LOG << toString(*op); 237 inputIndices.push_back(op->opIndex); 238 } 239 for (auto& op : operation.outputs) { 240 NN_FUZZER_LOG << toString(*op); 241 outputIndices.push_back(op->opIndex); 242 } 243 model->addOperation(operation.opType, inputIndices, outputIndices); 244 } 245 246 // Set model inputs and outputs. 247 model->identifyInputsAndOutputs(modelInputs, modelOutputs); 248 } 249 250 void RandomGraph::createRequest(test_wrapper::Execution* execution, 251 std::vector<OperandBuffer>* buffers) { 252 NN_FUZZER_LOG << "Create Request"; 253 if (buffers != nullptr) buffers->clear(); 254 for (const auto& operand : mOperands) { 255 if (operand->type == RandomOperandType::INPUT) { 256 EXPECT_EQ(execution->setInput(operand->ioIndex, operand->buffer.data(), 257 operand->getBufferSize(), nullptr), 258 Result::NO_ERROR); 259 } else if (operand->type == RandomOperandType::OUTPUT) { 260 if (buffers == nullptr) { 261 EXPECT_EQ(execution->setOutput(operand->ioIndex, operand->buffer.data(), 262 operand->getBufferSize(), nullptr), 263 Result::NO_ERROR); 264 } else { 265 // The order of the output buffers corresponds to the order in mOperands. 266 buffers->emplace_back(operand->buffer.size()); 267 EXPECT_EQ(execution->setOutput(operand->ioIndex, buffers->back().data(), 268 operand->getBufferSize(), nullptr), 269 Result::NO_ERROR); 270 } 271 } 272 } 273 } 274 275 // Check if the actual results meet the accuracy criterion. 276 constexpr uint32_t kMaxNumberOfPrintedErrors = 5; 277 template <typename T> 278 void expectNear(const RandomOperand& op, const OperandBuffer& test, 279 const AccuracyCriterion& criterion) { 280 constexpr uint32_t kMinNumberOfElementsToTestBiasMSE = 10; 281 const T* actualBuffer = reinterpret_cast<const T*>(test.data()); 282 const T* expectedBuffer = reinterpret_cast<const T*>(op.buffer.data()); 283 uint32_t len = op.getNumberOfElements(); 284 uint32_t numSkip = 0, numErrors = 0; 285 double bias = 0.0f, mse = 0.0f; 286 for (uint32_t i = 0; i < len; i++) { 287 SCOPED_TRACE(testing::Message() << "When comparing element " << i); 288 289 // Compare all data types in double for precision and signed arithmetic. 290 double actual = static_cast<double>(actualBuffer[i]); 291 double expected = static_cast<double>(expectedBuffer[i]); 292 double tolerableRange = criterion.atol + criterion.rtol * std::fabs(expected); 293 294 // Skip invalid floating point values. 295 if (std::isnan(expected) || std::isinf(expected) || std::isnan(actual) || 296 std::isinf(actual) || std::fabs(expected) > 1e3) { 297 numSkip++; 298 continue; 299 } 300 301 // Accumulate bias and MSE. Use relative bias and MSE for floating point values. 302 double diff = actual - expected; 303 if constexpr (NN_IS_FLOAT(T)) { 304 diff /= std::max(1.0, std::abs(expected)); 305 } 306 bias += diff; 307 mse += diff * diff; 308 309 // Print at most kMaxNumberOfPrintedErrors errors by EXPECT_NEAR. 310 if (numErrors < kMaxNumberOfPrintedErrors) EXPECT_NEAR(expected, actual, tolerableRange); 311 if (!(std::fabs(diff) <= tolerableRange)) numErrors++; 312 } 313 EXPECT_EQ(numErrors, 0u); 314 315 // Test bias and MSE. 316 if (len < numSkip + kMinNumberOfElementsToTestBiasMSE) return; 317 bias /= static_cast<double>(len - numSkip); 318 mse /= static_cast<double>(len - numSkip); 319 EXPECT_LE(std::fabs(bias), criterion.bias); 320 EXPECT_LE(mse, criterion.mse); 321 } 322 323 // For boolean values, we expect the number of mismatches does not exceed a certain ratio. 324 void expectBooleanNearlyEqual(const RandomOperand& op, const OperandBuffer& test, 325 float allowedErrorRatio) { 326 const bool8* actual = reinterpret_cast<const bool8*>(test.data()); 327 const bool8* expected = reinterpret_cast<const bool8*>(op.buffer.data()); 328 uint32_t len = op.getNumberOfElements(); 329 uint32_t numErrors = 0; 330 std::stringstream errorMsg; 331 for (uint32_t i = 0; i < len; i++) { 332 if (expected[i] != actual[i]) { 333 if (numErrors < kMaxNumberOfPrintedErrors) 334 errorMsg << " Expected: " << expected[i] << ", actual: " << actual[i] 335 << ", when comparing element " << i << "\n"; 336 numErrors++; 337 } 338 } 339 // When |len| is small, the allowedErrorCount will intentionally ceil at 1, which allows for 340 // greater tolerance. 341 uint32_t allowedErrorCount = static_cast<uint32_t>(std::ceil(allowedErrorRatio * len)); 342 EXPECT_LE(numErrors, allowedErrorCount) << errorMsg.str(); 343 } 344 345 void RandomGraph::checkResults(const std::vector<OperandBuffer>& buffers, 346 const AccuracyCriteria& criteria) const { 347 NN_FUZZER_LOG << "Check Results"; 348 // Make sure to keep the same order as the buffers are created. 349 int i = 0; 350 for (const auto& op : mOperands) { 351 if (op->type == RandomOperandType::OUTPUT) { 352 SCOPED_TRACE(testing::Message() 353 << "When comparing output " << op->ioIndex << " (op" << op->opIndex << ")" 354 << " of type " << toString(op->dataType)); 355 if (!op->doNotCheckAccuracy) { 356 switch (op->dataType) { 357 case Type::TENSOR_FLOAT32: 358 expectNear<float>(*op, buffers[i], criteria.float32); 359 break; 360 case Type::TENSOR_FLOAT16: 361 expectNear<_Float16>(*op, buffers[i], criteria.float16); 362 break; 363 case Type::TENSOR_INT32: 364 expectNear<int32_t>(*op, buffers[i], criteria.int32); 365 break; 366 case Type::TENSOR_QUANT8_ASYMM: 367 expectNear<uint8_t>(*op, buffers[i], criteria.quant8Asymm); 368 break; 369 case Type::TENSOR_QUANT8_SYMM: 370 expectNear<int8_t>(*op, buffers[i], criteria.quant8Symm); 371 break; 372 case Type::TENSOR_QUANT16_ASYMM: 373 expectNear<uint16_t>(*op, buffers[i], criteria.quant16Asymm); 374 break; 375 case Type::TENSOR_QUANT16_SYMM: 376 expectNear<int16_t>(*op, buffers[i], criteria.quant16Symm); 377 break; 378 case Type::TENSOR_BOOL8: 379 expectBooleanNearlyEqual(*op, buffers[i], /*allowedErrorRatio=*/0.01); 380 break; 381 default: 382 NN_FUZZER_CHECK(false) << "Data type not supported."; 383 } 384 } 385 i++; 386 } 387 } 388 } 389 390 void RandomGraph::dumpSpecFile(std::string filename, std::string testname = "") { 391 NN_FUZZER_LOG << "Dump Spec File to " << filename; 392 SpecWriter writer(filename, testname); 393 ASSERT_TRUE(writer.isOpen()); 394 writer.dump(mOperations, mOperands); 395 } 396 397 } // namespace fuzzing_test 398 } // namespace nn 399 } // namespace android 400
