1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

// This file is part of Substrate.

// Copyright (C) 2020-2021 Parity Technologies (UK) Ltd.
// SPDX-License-Identifier: Apache-2.0

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// 	http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! Fuzzing which ensures that running unbalanced sequential phragmen always produces a result
//! which satisfies our PJR checker.
//!
//! ## Running a single iteration
//!
//! Honggfuzz shuts down each individual loop iteration after a configurable time limit.
//! It can be helpful to run a single iteration on your hardware to help benchmark how long that time
//! limit should reasonably be. Simply run the program without the `fuzzing` configuration to run a
//! single iteration: `cargo run --bin phragmen_pjr`.
//!
//! ## Running
//!
//! Run with `HFUZZ_RUN_ARGS="-t 10" cargo hfuzz run phragmen_pjr`.
//!
//! Note the environment variable: by default, `cargo hfuzz` shuts down each iteration after 1 second
//! of runtime. We significantly increase that to ensure that the fuzzing gets a chance to complete.
//! Running a single iteration can help determine an appropriate value for this parameter.
//!
//! ## Debugging a panic
//!
//! Once a panic is found, it can be debugged with
//! `HFUZZ_RUN_ARGS="-t 10" cargo hfuzz run-debug phragmen_pjr hfuzz_workspace/phragmen_pjr/*.fuzz`.

#[cfg(fuzzing)]
use honggfuzz::fuzz;

#[cfg(not(fuzzing))]
use structopt::StructOpt;

mod common;
use common::{generate_random_npos_inputs, to_range};
use rand::{self, SeedableRng};
use sp_npos_elections::{pjr_check_core, seq_phragmen_core, setup_inputs, standard_threshold};

type AccountId = u64;

const MIN_CANDIDATES: usize = 250;
const MAX_CANDIDATES: usize = 1000;
const MIN_VOTERS: usize = 500;
const MAX_VOTERS: usize = 2500;

#[cfg(fuzzing)]
fn main() {
	loop {
		fuzz!(|data: (usize, usize, u64)| {
			let (candidate_count, voter_count, seed) = data;
			iteration(candidate_count, voter_count, seed);
		});
	}
}

#[cfg(not(fuzzing))]
#[derive(Debug, StructOpt)]
struct Opt {
	/// How many candidates participate in this election
	#[structopt(short, long)]
	candidates: Option<usize>,

	/// How many voters participate in this election
	#[structopt(short, long)]
	voters: Option<usize>,

	/// Random seed to use in this election
	#[structopt(long)]
	seed: Option<u64>,
}

#[cfg(not(fuzzing))]
fn main() {
	let opt = Opt::from_args();
	// candidates and voters by default use the maxima, which turn out to be one less than
	// the constant.
	iteration(
		opt.candidates.unwrap_or(MAX_CANDIDATES - 1),
		opt.voters.unwrap_or(MAX_VOTERS - 1),
		opt.seed.unwrap_or_default(),
	);
}

fn iteration(mut candidate_count: usize, mut voter_count: usize, seed: u64) {
	let rng = rand::rngs::SmallRng::seed_from_u64(seed);
	candidate_count = to_range(candidate_count, MIN_CANDIDATES, MAX_CANDIDATES);
	voter_count = to_range(voter_count, MIN_VOTERS, MAX_VOTERS);

	let (rounds, candidates, voters) =
		generate_random_npos_inputs(candidate_count, voter_count, rng);

	let (candidates, voters) = setup_inputs(candidates, voters);

	// Run seq-phragmen
	let (candidates, voters) = seq_phragmen_core::<AccountId>(rounds, candidates, voters)
		.expect("seq_phragmen must succeed");

	let threshold = standard_threshold(rounds, voters.iter().map(|voter| voter.budget()));

	assert!(
		pjr_check_core(&candidates, &voters, threshold).is_ok(),
		"unbalanced sequential phragmen must satisfy PJR",
	);
}