2#include "barretenberg/numeric/uint256/uint256.hpp"
3#include "barretenberg/proof_system/circuit_builder/standard_circuit_builder.hpp"
10#define EXPAND(arg) EXPAND1(EXPAND1(EXPAND1(EXPAND1(arg))))
11#define EXPAND1(arg) EXPAND2(EXPAND2(EXPAND2(EXPAND2(arg))))
12#define EXPAND2(arg) EXPAND3(EXPAND3(EXPAND3(EXPAND3(arg))))
13#define EXPAND3(arg) EXPAND4(EXPAND4(EXPAND4(EXPAND4(arg))))
14#define EXPAND4(arg) arg
16#define FOR_EACH(macro, ...) __VA_OPT__(EXPAND(FOR_EACH_HELPER(macro, __VA_ARGS__)))
17#define FOR_EACH_HELPER(macro, a1, ...) macro(a1) __VA_OPT__(FOR_EACH_AGAIN PARENS(macro, __VA_ARGS__))
18#define FOR_EACH_AGAIN() FOR_EACH_HELPER
20#define ALL_POSSIBLE_OPCODES \
21 CONSTANT, WITNESS, CONSTANT_WITNESS, ADD, SUBTRACT, MULTIPLY, DIVIDE, ADD_TWO, MADD, MULT_MADD, MSUB_DIV, SQR, \
22 ASSERT_EQUAL, ASSERT_NOT_EQUAL, SQR_ADD, ASSERT_EQUAL, ASSERT_NOT_EQUAL, SQR_ADD, SUBTRACT_WITH_CONSTRAINT, \
23 DIVIDE_WITH_CONSTRAINTS, SLICE, ASSERT_ZERO, ASSERT_NOT_ZERO, COND_NEGATE, ADD_MULTI, ASSERT_VALID, \
24 COND_SELECT, DOUBLE, RANDOMSEED, SELECT_IF_ZERO, SELECT_IF_EQ, REVERSE, GET_BIT, SET_BIT, SET, INVERT, AND, \
25 OR, XOR, MODULO, SHL, SHR, ROL, ROR, NOT
28 size_t GEN_LLVM_POST_MUTATION_PROB;
29 size_t GEN_MUTATION_COUNT_LOG;
31 size_t GEN_STRUCTURAL_MUTATION_PROBABILITY;
33 size_t GEN_VALUE_MUTATION_PROBABILITY;
34 size_t ST_MUT_DELETION_PROBABILITY;
35 size_t ST_MUT_DUPLICATION_PROBABILITY;
36 size_t ST_MUT_INSERTION_PROBABILITY;
37 size_t ST_MUT_MAXIMUM_DELETION_LOG;
38 size_t ST_MUT_MAXIMUM_DUPLICATION_LOG;
39 size_t ST_MUT_SWAP_PROBABILITY;
40 size_t VAL_MUT_LLVM_MUTATE_PROBABILITY;
41 size_t VAL_MUT_MONTGOMERY_PROBABILITY;
43 size_t VAL_MUT_NON_MONTGOMERY_PROBABILITY;
45 size_t VAL_MUT_SMALL_ADDITION_PROBABILITY;
46 size_t VAL_MUT_SMALL_MULTIPLICATION_PROBABILITY;
47 size_t VAL_MUT_SPECIAL_VALUE_PROBABILITY;
48 std::vector<size_t> structural_mutation_distribution;
50 std::vector<size_t> value_mutation_distribution;
58extern "C" size_t LLVMFuzzerMutate(uint8_t* Data,
size_t Size,
size_t MaxSize);
71 state =
static_cast<uint32_t
>(
72 (
static_cast<uint64_t
>(state) *
static_cast<uint64_t
>(363364578) +
static_cast<uint64_t
>(537)) %
73 static_cast<uint64_t
>(3758096939));
76 void reseed(uint32_t seed)
94 } -> std::convertible_to<uint32_t>;
104 std::make_tuple(T::CONSTANT,
117 T::SUBTRACT_WITH_CONSTRAINT,
118 T::DIVIDE_WITH_CONSTRAINTS,
122 } -> std::same_as<std::tuple<size_t>>;
134 std::make_tuple(T::GEN_MUTATION_COUNT_LOG, T::GEN_STRUCTURAL_MUTATION_PROBABILITY)
135 } -> std::same_as<std::tuple<size_t>>;
136 T::GEN_MUTATION_COUNT_LOG <= 7;
145 typename T::ArgSizes;
146 typename T::Instruction;
147 typename T::ExecutionState;
148 typename T::ExecutionHandler;
161 } -> std::same_as<bool>;
171template <
typename T,
typename Composer,
typename Context>
174 T::postProcess(&composer, context)
175 } -> std::same_as<bool>;
186 typename T::InstructionWeights;
187 T::InstructionWeights::_LIMIT;
199template <
typename T,
typename FF>
200inline static FF mutateFieldElement(
FF e, T& rng)
206 bool convert_to_montgomery = (rng.next() & 1);
209#define MONT_CONVERSION_LOCAL \
210 if (convert_to_montgomery) { \
211 value_data = uint256_t(e.to_montgomery_form()); \
213 value_data = uint256_t(e); \
216#define INV_MONT_CONVERSION_LOCAL \
217 if (convert_to_montgomery) { \
218 e = FF(value_data).from_montgomery_form(); \
220 e = FF(value_data); \
225 const size_t choice = rng.next() % 4;
229 MONT_CONVERSION_LOCAL
231 LLVMFuzzerMutate(
reinterpret_cast<uint8_t*
>(&value_data),
sizeof(
uint256_t),
sizeof(
uint256_t));
232 INV_MONT_CONVERSION_LOCAL
233 }
else if (choice < 3) {
236 if (convert_to_montgomery) {
237 e = e.to_montgomery_form();
239 if (rng.next() & 1) {
240 value_data = e +
FF(rng.next() & 0xff);
242 value_data = e -
FF(rng.next() & 0xff);
244 if (convert_to_montgomery) {
245 e = e.from_montgomery_form();
250 MONT_CONVERSION_LOCAL
251 switch (rng.next() % 8) {
262 e = FF::one().sqrt().second;
265 e = FF::one().sqrt().second.invert();
268 e = FF::get_root_of_unity(8);
274 e =
FF((FF::modulus - 1) / 2);
280 INV_MONT_CONVERSION_LOCAL
301 inline static void swapTwoInstructions(std::vector<typename T::Instruction>& instructions,
FastRandom& rng)
303 const size_t instructions_count = instructions.size();
304 if (instructions_count <= 2) {
307 const size_t first_element_index = rng.next() % instructions_count;
308 size_t second_element_index = rng.next() % instructions_count;
309 if (first_element_index == second_element_index) {
310 second_element_index = (second_element_index + 1) % instructions_count;
312 std::iter_swap(instructions.begin() +
static_cast<int>(first_element_index),
313 instructions.begin() +
static_cast<int>(second_element_index));
323 inline static void deleteInstructions(std::vector<typename T::Instruction>& instructions,
328 const size_t instructions_count = instructions.size();
329 if (instructions_count == 0) {
332 if ((rng.next() & 1) != 0U) {
333 instructions.erase(instructions.begin() + (rng.next() % instructions_count));
336 const size_t max_deletion_log =
337 std::min(
static_cast<size_t>(64 - __builtin_clzll(
static_cast<uint64_t
>(instructions_count)) - 1),
338 havoc_settings.ST_MUT_MAXIMUM_DELETION_LOG);
340 if (max_deletion_log == 0) {
343 const size_t deletion_size = 1 << (rng.next() % max_deletion_log);
344 const size_t start = rng.next() % (instructions_count + 1 - deletion_size);
345 instructions.erase(instructions.begin() +
static_cast<int>(start),
346 instructions.begin() +
static_cast<int>(start + deletion_size));
356 inline static void duplicateInstruction(std::vector<typename T::Instruction>& instructions,
360 const size_t instructions_count = instructions.size();
361 if (instructions_count == 0) {
364 const size_t duplication_size = 1 << (rng.next() % havoc_settings.ST_MUT_MAXIMUM_DUPLICATION_LOG);
365 typename T::Instruction chosen_instruction = instructions[rng.next() % instructions_count];
367 instructions.begin() + (rng.next() % (instructions_count + 1)), duplication_size, chosen_instruction);
369 inline static void insertRandomInstruction(std::vector<typename T::Instruction>& instructions,
373 (void)havoc_settings;
374 instructions.insert(instructions.begin() +
static_cast<int>(rng.next() % (instructions.size() + 1)),
375 T::Instruction::template generateRandom<FastRandom>(rng));
384 inline static void mutateInstructionStructure(std::vector<typename T::Instruction>& instructions,
388 const size_t structural_mutators_count = havoc_settings.structural_mutation_distribution.size();
389 const size_t prob_pool = havoc_settings.structural_mutation_distribution[structural_mutators_count - 1];
390 const size_t choice = rng.next() % prob_pool;
391 if (choice < havoc_settings.structural_mutation_distribution[0]) {
392 deleteInstructions(instructions, rng, havoc_settings);
393 }
else if (choice < havoc_settings.structural_mutation_distribution[1]) {
395 duplicateInstruction(instructions, rng, havoc_settings);
396 }
else if (choice < havoc_settings.structural_mutation_distribution[2]) {
397 insertRandomInstruction(instructions, rng, havoc_settings);
400 swapTwoInstructions(instructions, rng);
410 inline static void mutateInstructionValue(std::vector<typename T::Instruction>& instructions,
415 const size_t instructions_count = instructions.size();
416 if (instructions_count == 0) {
419 const size_t chosen = rng.next() % instructions_count;
420 instructions[chosen] =
421 T::Instruction::template mutateInstruction<FastRandom>(instructions[chosen], rng, havoc_settings);
424 static void mutateInstructionVector(std::vector<typename T::Instruction>& instructions,
FastRandom& rng)
428 const size_t mutation_count = 1 << fuzzer_havoc_settings.GEN_MUTATION_COUNT_LOG;
430 const size_t mutation_count = 1 << T::HavocConfig::MUTATION_COUNT_LOG;
434 for (
size_t i = 0; i < mutation_count; i++) {
435 uint32_t val = rng.next();
436 if ((val % (fuzzer_havoc_settings.GEN_STRUCTURAL_MUTATION_PROBABILITY +
437 fuzzer_havoc_settings.GEN_VALUE_MUTATION_PROBABILITY)) <
438 fuzzer_havoc_settings.GEN_STRUCTURAL_MUTATION_PROBABILITY) {
440 mutateInstructionStructure(instructions, rng, fuzzer_havoc_settings);
444 mutateInstructionValue(instructions, rng, fuzzer_havoc_settings);
459 const std::vector<typename T::Instruction>& vecA,
460 const std::vector<typename T::Instruction>& vecB,
464 const size_t vecA_size = vecA.size();
465 const size_t vecB_size = vecB.size();
467 if (vecA_size == 0) {
470 if (vecB_size == 0) {
473 std::vector<typename T::Instruction> result;
475 const size_t final_result_size = rng.next() % (vecA_size + vecB_size) + 1;
478 size_t* inIndex = &indexA;
479 size_t inSize = vecA_size;
480 auto inIterator = vecA.begin();
481 size_t current_result_size = 0;
482 bool currentlyUsingA =
true;
484 while (current_result_size < final_result_size && (indexA < vecA_size || indexB < vecB_size)) {
486 size_t result_size_left = final_result_size - current_result_size;
488 if (*inIndex < inSize) {
490 size_t inSizeLeft = inSize - *inIndex;
491 size_t maxExtraSize = std::min(result_size_left, inSizeLeft);
492 if (maxExtraSize != 0) {
494 size_t copySize = (rng.next() % maxExtraSize) + 1;
495 result.insert(result.begin() +
static_cast<long>(current_result_size),
496 inIterator +
static_cast<long>((*inIndex)),
498 inIterator +
static_cast<long>((*inIndex) + copySize));
500 *inIndex += copySize;
501 current_result_size += copySize;
505 inIndex = currentlyUsingA ? &indexB : &indexA;
506 inSize = currentlyUsingA ? vecB_size : vecA_size;
507 inIterator = currentlyUsingA ? vecB.begin() : vecA.begin();
508 currentlyUsingA = !currentlyUsingA;
522 std::vector<typename T::Instruction> fuzzingInstructions;
524 auto* pData =
const_cast<uint8_t*
>(Data);
525 size_t size_left = Size;
526 while (size_left != 0) {
527 uint8_t chosen_operation = *pData;
532#define PARSE_OPCODE(name) \
533 if constexpr (requires { T::ArgSizes::name; }) \
534 if constexpr (T::ArgSizes::name != size_t(-1)) { \
535 if (chosen_operation == T::Instruction::OPCODE::name) { \
536 if (size_left < T::ArgSizes::name) { \
537 return fuzzingInstructions; \
539 fuzzingInstructions.push_back( \
540 T::Parser::template parseInstructionArgs<T::Instruction::OPCODE::name>(pData)); \
541 size_left -= T::ArgSizes::name; \
542 pData += T::ArgSizes::name; \
547#define PARSE_ALL_OPCODES(...) FOR_EACH(PARSE_OPCODE, __VA_ARGS__)
549 PARSE_ALL_OPCODES(ALL_POSSIBLE_OPCODES)
551 return fuzzingInstructions;
565 uint8_t* pData = Data;
566 size_t size_left = MaxSize;
567 for (
auto& instruction : instructions) {
569#define WRITE_OPCODE_IF(name) \
570 if constexpr (requires { T::ArgSizes::name; }) \
571 if constexpr (T::ArgSizes::name != (size_t)-1) { \
572 if (instruction.id == T::Instruction::OPCODE::name) { \
573 if (size_left >= (T::ArgSizes::name + 1)) { \
574 T::Parser::template writeInstruction<T::Instruction::OPCODE::name>(instruction, pData); \
575 size_left -= (T::ArgSizes::name + 1); \
576 pData += (T::ArgSizes::name + 1); \
578 return MaxSize - size_left; \
584#define WRITE_ALL_OPCODES(...) FOR_EACH(WRITE_OPCODE_IF, __VA_ARGS__)
586 WRITE_ALL_OPCODES(ALL_POSSIBLE_OPCODES)
588 return MaxSize - size_left;
597 template <
typename Composer>
603 typename T::ExecutionState state;
605 bool circuit_should_fail =
false;
606 size_t total_instruction_weight = 0;
607 (void)total_instruction_weight;
608 for (
auto& instruction : instructions) {
610#define EXECUTE_OPCODE_IF(name) \
611 if constexpr (requires { T::ArgSizes::name; }) \
612 if constexpr (T::ArgSizes::name != size_t(-1)) { \
613 if (instruction.id == T::Instruction::OPCODE::name) { \
614 if constexpr (InstructionWeightsEnabled<T>) { \
615 if (!((total_instruction_weight + T::InstructionWeights::name) > T::InstructionWeights::_LIMIT)) { \
616 total_instruction_weight += T::InstructionWeights::name; \
617 if (T::ExecutionHandler::execute_##name(&composer, state, instruction)) { \
625 if (T::ExecutionHandler::execute_##name(&composer, state, instruction)) { \
631#define EXECUTE_ALL_OPCODES(...) FOR_EACH(EXECUTE_OPCODE_IF, __VA_ARGS__)
633 EXECUTE_ALL_OPCODES(ALL_POSSIBLE_OPCODES)
635 bool final_value_check =
true;
638 final_value_check = T::postProcess(&composer, state);
639#ifdef SHOW_INFORMATION
640 if (!final_value_check) {
641 std::cerr <<
"Final value check failed" << std::endl;
645 bool check_result = composer.check_circuit() && final_value_check;
647 if (check_result && circuit_should_fail) {
651 if ((!check_result) && (!circuit_should_fail)) {
652 if (!final_value_check) {
653 std::cerr <<
"Final value check failed" << std::endl;
655 std::cerr <<
"Circuit failed" << std::endl;
675 mutateInstructionVector(instructions, rng);
681template <
template <
typename>
class Fuzzer,
typename Composer>
682constexpr void RunWithBuilder(
const uint8_t* Data,
const size_t Size,
FastRandom& VarianceRNG)
684 VarianceRNG.reseed(0);
689template <
template <
typename>
class Fuzzer, uint64_t Composers>
690constexpr void RunWithBuilders(
const uint8_t* Data,
const size_t Size,
FastRandom& VarianceRNG)
693 RunWithBuilder<Fuzzer, proof_system::StandardCircuitBuilder>(Data, Size, VarianceRNG);
A templated class containing most of the fuzzing logic for a generic Arithmetic class.
Definition: fuzzer.hpp:293
static size_t writeInstructionsToBuffer(std::vector< typename T::Instruction > &instructions, uint8_t *Data, size_t MaxSize)
Write instructions into the buffer until there are no instructions left or there is no more space.
Definition: fuzzer.hpp:561
static std::vector< typename T::Instruction > parseDataIntoInstructions(const uint8_t *Data, size_t Size)
Parses a given data buffer into a vector of instructions for testing the arithmetic.
Definition: fuzzer.hpp:520
static size_t MutateInstructionBuffer(uint8_t *Data, size_t Size, size_t MaxSize, FastRandom &rng)
Interpret the data buffer as a series of arithmetic instructions and mutate it accordingly.
Definition: fuzzer.hpp:670
static std::vector< typename T::Instruction > crossoverInstructionVector(const std::vector< typename T::Instruction > &vecA, const std::vector< typename T::Instruction > &vecB, FastRandom &rng)
Splice two instruction vectors into one randomly.
Definition: fuzzer.hpp:458
static void executeInstructions(std::vector< typename T::Instruction > &instructions)
Execute instructions in a loop.
Definition: fuzzer.hpp:600
Class for quickly deterministically creating new random values. We don't care about distribution much...
Definition: fuzzer.hpp:64
Definition: uint256.hpp:25
Definition: standard_composer.hpp:14
Concept specifying the class used by the fuzzer.
Definition: fuzzer.hpp:144
Fuzzer uses only composers with check_circuit function.
Definition: fuzzer.hpp:158
Concept for Havoc Configurations.
Definition: fuzzer.hpp:131
Concept for forcing ArgumentSizes to be size_t.
Definition: fuzzer.hpp:102
This concept is used when we want to limit the number of executions of certain instructions (for exam...
Definition: fuzzer.hpp:185
The fuzzer can use a postprocessing function that is specific to the type being fuzzed.
Definition: fuzzer.hpp:172
Concept for a simple PRNG which returns a uint32_t when next is called.
Definition: fuzzer.hpp:91
Definition: fuzzer.hpp:27