Fuzzing and Organisation for Runtime Arithmetic Types

[kianenigma]

• Relocate all the arithmetic stuff into a separate crate. Probably one file per each type defined in sr_arithmetic.rs.
• Create better and more fuzzing code for all tests that bombard the code with random values. A lot can be done here. Any taker's imagination is the limit. Nonetheless, the minimum is to remove all the tests that have a random number generator in them and replace them with fuzzing code.

Optionally

• Use the benchmarks to apply potentially any optimizations to the code
  • Some ideas of using LE ordering which were tried with @jimpo https://github.com/paritytech/substrate/tree/kiz-limb-arithmetic-2 (last two commits)
  • Use criterion and more comprehensive set of benchmarks.
  • Try and re-use memory: add_assign instead of add. Also read and apply the suggestions here.

[expenses]

Are you suggesting putting the contents of sr_arithmetic into a new core/sr-arithmetic crate? There's a cyclic dependency there as the arithmetic functions depend on the sr-primitives traits and the arithmetic types (Perbill etc) are dependended on in various places in sr-primitives.

I'm a little confused about what you suggest for fuzzing. Currently this is the only code that uses random values, and it seems to be checking more for accuracy than panics:

substrate/core/sr-primitives/src/sr_arithmetic.rs

Lines 1200 to 1243 in ddd7368

	fn do_fuzz_multiply_by_rational<F>(
	iters: usize,
	bits: u32,
	maximum_error: u128,
	do_print: bool,
	bounded: bool,
	mul_fn: F,
	) where F: Fn(u128, u128, u128) -> u128 {
	let mut rng = rand::thread_rng();
	let mut average_diff = 0.0;
	let upper_bound = 2u128.pow(bits);
	for _ in 0..iters {
	let a = rng.gen_range(0u128, upper_bound);
	let c = rng.gen_range(0u128, upper_bound);
	let b = rng.gen_range(
	0u128,
	if bounded { c } else { upper_bound }
	);
	let a: u128 = a.into();
	let b: u128 = b.into();
	let c: u128 = c.into();
	let truth = mul_div(a, b, c);
	let result = mul_fn(a, b, c);
	let diff = truth.max(result) - truth.min(result);
	let loss_ratio = diff as f64 / truth as f64;
	average_diff += loss_ratio;
	if do_print && diff > maximum_error {
	println!("++ Computed with more loss than expected: {} * {} / {}", a, b, c);
	println!("++ Expected {}", truth);
	println!("+++++++ Got {}", result);
	}
	}
	// print report
	println!(
	"## Fuzzed with {} numbers. Average error was {}",
	iters,
	average_diff / (iters as f64),
	);
	}

Should something like cargo fuzz be used?

[kianenigma]

@expenses

• No, I was thinking more like sr-primitives/arithmetic/per-things.rs and other files per type. I misused the word crate while I meant just filed modules.
• I don't have a strong opinion but I was told that the fuzzing tools in parity-codec are worthwhile.
  More fuzz-like code will come in the linked PR Multi-limb arithmetic for runtime #3743

@hacky1997
note that this issue is dependent on #3743 and should ideally be worked on once the PR is merged.

Also, I cannot be sure, but be aware that this issue might grow a bit as we might find some good bugs in the arithmetic code while fuzzing (hopefully!) :)

[gui1117]

I think the cyclic dependency could be overcome, it depends on what we actually need for our computation.
most the trait are coming from num_traits and core::ops. I'm not sure we actually need more than those for our perbill and stuff

[expenses]

What are we actually fuzzing for here? I've found accuracy problems with multiply_by_rational_best_effort such as this test that fails:

#[test]
fn mul_by_best_effort_is_accurate() {
    let a = 2475880078642818143838273536;
    let b = 18014399314788352;
    let c = 1190036353683150593851392;


    assert_eq!(multiply_by_rational_best_effort(a, b, c), mul_div(a, b, c));
}

but those sort of thing can be found easily by adding panic!(); to the end of this block:

substrate/core/sr-primitives/src/sr_arithmetic.rs

Lines 1230 to 1234 in 062748f

	if do_print && diff > maximum_error {
	println!("++ Computed with more loss than expected: {} * {} / {}", a, b, c);
	println!("++ Expected {}", truth);
	println!("+++++++ Got {}", result);
	}

[gui1117]

the fuzzing would be to detect abnormal accuracy. I think ideally accuracy should be proved to be good enough but in the current design it is not. I don't know what is multiply_by_rational_best_effort worst case.

We know best effort is not perfect but should be ok accurate. (and maybe replaced by multi limb arithmetic soon)

Also It could also detect some wrong implementation.

[kianenigma]

What are we actually fuzzing for here? I've found accuracy problems with multiply_by_rational_best_effort such as this test that fails:

#[test]
fn mul_by_best_effort_is_accurate() {
    let a = 2475880078642818143838273536;
    let b = 18014399314788352;
    let c = 1190036353683150593851392;


    assert_eq!(multiply_by_rational_best_effort(a, b, c), mul_div(a, b, c));
}

but those sort of thing can be found easily by adding panic!(); to the end of this block:

substrate/core/sr-primitives/src/sr_arithmetic.rs

Lines 1230 to 1234 in 062748f

	if do_print && diff > maximum_error {
	println!("++ Computed with more loss than expected: {} * {} / {}", a, b, c);
	println!("++ Expected {}", truth);
	println!("+++++++ Got {}", result);
	}

The current implementation,
multiply_by_rational_best_effort always returns but is inaccurate
multiply_by_rational might return but is always accurate

so the user can chose. The PR that I linked above will merge these two and hopefully there will be one that will always return accurately as long as the result fits in u128.

I think it will be good if whoever wants to work on this also keep track on the other PR.

[kianenigma]

and see here for details of the current impls #3456

[kianenigma]

@expenses the PR is merged. One can start working on this now, if desired :)

[expenses]

Thanks!