Audit preparedness: assessing key cases

[michaeljklein]

Problem

Given listing from: #5360

• Break out into sub-lists, according to size (e.g. group bitwise ops together)
• Assess the state of unit tests for each
• List desired tests for each
• Split Audit preparedness: implement unit tests #5362 into multiple parts

Happy Case

Add the lists of tests to the omnibus issue for implementation

Project Impact

None

Impact Context

No response

Workaround

None

Workaround Description

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[michaeljklein]

Assorted TODO's:

• Make dummy-ID for (monomorphizer) FuncId (other than 0)
• Make monomorphizer AST's Program::take_function_body error when called twice on the same function (FuncId)

Places to Test

Top-level Groups

• Binary
• Arithmetic
• Crypto
• Memory access
• Arrays/slices
• Semantic (EnableSideEffects, IsUnconstrained, etc)
• Other

// acvm-repo/acir/src/circuit/opcodes.rs
pub enum Opcode<F> {

• AssertZero(Expression<F>): Test on different expression types
• BlackBoxFuncCall(BlackBoxFuncCall)
• Directive(Directive<F>)
• MemoryOp { op: MemOp<F>, .. }: Read/write memory test
• MemoryInit { .. }: Ensure all initialized memory actually initialized and is required for memory operations
• BrilligCall { .. }
• Call { .. }

// ssa/ir/instruction.rs
pub(crate) enum Intrinsic {

• ArrayLen

• AsSlice: good coverage

• SlicePushBack

• SlicePushFront

• SlicePopBack

• SlicePopFront

• SliceInsert

• SliceRemove

• AssertConstant: good coverage

• StaticAssert: good coverage

• ApplyRangeConstraint

• AsWitness

• IsUnconstrained

• DerivePedersenGenerators

• StrAsBytes

• ToBits(Endian)

• ToRadix(Endian)

• BlackBox(BlackBoxFunc)

• FromField: isomorphism with AsField

• AsField

// ssa/ir/instruction.rs
pub(crate) enum Instruction {

• Binary(Binary): See Binary enum below

• Cast(ValueId, Type): test that it's effectively a no-op when allowed / ensure unsafe casts disallowed

• Not(ValueId): not ONES == ZEROES; not ZEROES == ONES; not (not x) == x; not x != x

• Truncate { value: ValueId, bit_size: u32, max_bit_size: u32 }: ensure result has expected max_bit_size

• Constrain(ValueId, ValueId, Option<ConstrainError>): sanity-check successful/failing cases

• RangeCheck { value: ValueId, max_bit_size: u32, assert_message: Option<String> }: sanity-check successful/failing cases

• Allocate: 1) ensure an allocation happens, 2) check that an Allocate is required to Load/Store

• Load { address: ValueId }: Load/store random-access memory test.
  For all logs of (Read(Index) | Write(Index, Value)),
  all reads return the Value of the last Write to that Index,
  otherwise the default value if there is no last Write.

• Store { address: ValueId, value: ValueId }: see Load

• ArrayGet { array: ValueId, index: ValueId }: get/set random-access memory test

• ArraySet { array: ValueId, index: ValueId, value: ValueId, mutable: bool }: see ArraySet

• IncrementRc { value: ValueId }: 1) ensure Brillig RC is incremented, 2) ensure no-op in ACIR

• DecrementRc { value: ValueId }: 1) ensure Brillig RC is decremented, 2) ensure no-op in ACIR

• EnableSideEffects { condition: ValueId }: ensure it enables/disables side effects in affected block

• Call { func: ValueId, arguments: Vec<ValueId> }: ensure call to failing function fails

• IfElse { then_condition: ValueId, then_value: ValueId, else_condition: ValueId, else_value: ValueId }:

  1. ensure that else_condition == !then_condition
  2. ensure only the passing branch is executed.
     Use a) always-failing asserts, b) mutable array setting

// "kind" in binary::Binary (op)
pub(crate) enum BinaryOp {

• Sanity-check that behavior of these match for example inputs 0..8 (or are None): get_field_function, get_u128_function, get_i128_function

Automorphisms:

• Test associativity

• Test (anti-)commutativity

• Test identity

• Add

• Sub

• Mul

• Div

• Mod

• And

• Or

• Xor

• Shl

• Shr

Comparisons:

• Test (anti-)reflexivity
• Test transitivity
• Test (anti-)commutativity
• Eq
• Lt

pub enum Directive<F> {

• ToLeRadix

pub enum BlackBoxFunc {

• AES128Encrypt

• SHA256

• Blake2s

• Blake3

• SchnorrVerify

• PedersenCommitment

• PedersenHash

• EcdsaSecp256k1

• EcdsaSecp256r1

• Keccak256

• Keccakf1600

• Poseidon2Permutation

• Sha256Compression

• RecursiveAggregation

• AND

• XOR

• RANGE

• MultiScalarMul

• EmbeddedCurveAdd

• BigIntAdd

• BigIntSub

• BigIntMul

• BigIntDiv

• BigIntFromLeBytes

• BigIntToLeBytes

acir-gen Cases:

• Ssa::into_acir(self, brillig: &Brillig)
• convert_acir_main
• convert_brillig_main
• convert_ssa_block_params (test against behavior from docstring)
• add_numeric_input_var (check range constraint)
• handle_constant_index (ensure equivalent to when not used / slow-version of adding a constant, constraining to equivalent with var, etc. see docstring)
• handle_array_operation get/set
• convert_array_operation_inputs (test with a couple types of nesting / included tuples/struct-types)
• array_get / array_set (get gets last set value)
• array_get_value / array_set_value (get gets last set value)
• init_element_type_sizes_array (check_array_is_initialized on result)
• copy_dynamic_array (check_array_is_initialized on result)
• initialize_array (check_array_is_initialized on result)
• flattened_slice_size / flattened_value_size (various nesting)
• convert_ssa_binary (test expected operation occurs)
• check_unsigned_overflow (1. test key successful/failing cases, 2. ensure non-tested operations cannot exceed size) ((consider adding a bool argument to unconditionally range-constrain var, then test that both versions are equivalent))
• type_of_binary_operation (see docstring for cases)
• convert_ssa_intrinsic_call
• array_element_type (test docstring properties)

SSA Passes:

• Ssa::defunctionalize
• Ssa::remove_paired_rc
• Ssa::separate_runtime
• Ssa::resolve_is_unconstrained
• Ssa::inline_functions
• Ssa::mem2reg
• Ssa::as_slice_optimization
• Ssa::evaluate_static_assert_and_assert_constant
• Ssa::unroll_loops_iteratively
• Ssa::simplify_cfg
• Ssa::flatten_cfg
• Ssa::remove_bit_shifts
• Ssa::mem2reg
• Ssa::inline_functions_with_no_predicates
• Ssa::remove_if_else
• Ssa::fold_constants
• Ssa::remove_enable_side_effects
• Ssa::fold_constants_using_constraints
• Ssa::dead_instruction_elimination
• Ssa::array_set_optimization

Monomorphizer:

• constructor
• unpack_pattern / unpack_tuple_pattern (ensure they convert key examples to expected accesses)
• resolve_trait_method_reference (ensure it handles assumed traits)
• function_call
• try_evaluate_call
• try_evaluate_call: "modulus_num_bits"
• try_evaluate_call: "zeroed"
• try_evaluate_call: "modulus_le_bits"
• try_evaluate_call: "modulus_be_bits"
• try_evaluate_call: "modulus_be_bytes"
• try_evaluate_call: "modulus_le_bytes"
• lambda_with_setup (test key cases of zero/trivial/two-var env, as well as 2-3 lambdas in a row / nested)
• zeroed_value_of_type: sanity-check that result is all-zero, ensure it's constant
• create_zeroed_function: ensure it behaves as described in docstring
• perform_instantiation_bindings
• undo_instantiation_bindings (ensure it reverses the effect of perform_instantiation_bindings)