Modified fuzz tests about field operations

YafeiXie1 commented at 12:09 pm on August 21, 2023: none

Thanks for the previous review. This PR: Added a function to construct valid field elements with random magnitude. Added the constraint in each field operation test based on the magnitude and normalization. Could you give me some suggestions?

modify the fuzzing tests of field operations 3874a937a9

modified the fuzzing tests of field operations. a0b3d0a0de

real-or-random added the label assurance on Aug 21, 2023

sipa cross-referenced this on Aug 21, 2023 from issue add fuzz tests about field operations. by YafeiXie1

sipa commented at 2:25 pm on August 21, 2023: contributor

@YafeiXie1 Just FYI, you don’t need to open a new pull request when you make changes. You can push again to the same branch with more commits (or if you modified existing commits, you’d need a force push, but it’s still possible).

in src/fuzz.c:220 in 3874a937a9 outdated

215+        }
216+        secp256k1_fe_clear(&zero);
217+        secp256k1_fe_negate(&zero, &zero, 0);
218+        secp256k1_fe_mul_int_unchecked(&zero, rand_magnitude - 1);
219+        secp256k1_fe_add(r, &zero);         
220+    }

sipa commented at 9:42 pm on August 24, 2023:

It’s unclear where the responsibility lies for making sure the input is big enough:

Does it lie with the caller (e.g. is it only allowed to call fuzz_field_construct when the caller knows size >= 32)? If so, then the if (size>=32) { branch is unnecessary, and could be replaced with CHECK(size >= 32); instead, or the size argument could be dropped from this function entirely even.
Does it lie with the fuzz_field_construct function? If so then the function needs to have a means of returning success/failure if the size is too small. Also, in that case data and size arguments probably need to be made pointers (const uint8_t **data, size_t *size), so they can be updated by fuzz_field_construct (otherwise the caller is still responsible for updating them).

in src/fuzz.c:223 in 3874a937a9 outdated

218+        secp256k1_fe_mul_int_unchecked(&zero, rand_magnitude - 1);
219+        secp256k1_fe_add(r, &zero);         
220+    }
221+}
222+
223+#ifdef VERIFY

sipa commented at 9:43 pm on August 24, 2023:

Why?

in src/fuzz.c:229 in 3874a937a9 outdated

224+/* Test the field element comparison operations. */
225+static void fuzz_field_comparison(const uint8_t *data, size_t size) {
226+    if (size >= 32) {
227+        secp256k1_fe a;    
228+        fuzz_field_construct(data, size, &a);
229+        if (a.normalized) {

sipa commented at 9:47 pm on August 24, 2023:

The test could be a lot more efficient if fuzz_field_construct had an input argument that can guarantee it only produces normalized field elements (because as-is, in many cases no test will be performed at all). Alternatively, there could be a separate function for just that.

in src/fuzz.c:214 in 3874a937a9 outdated

209+        secp256k1_fe a, zero;      
210+        secp256k1_fe_set_b32_mod(r, data);
211+        int rand_magnitude = data[31] % 33;
212+        secp256k1_fe_normalize(r);
213+        if (rand_magnitude == 0) {
214+            return;

sipa commented at 9:48 pm on August 24, 2023:

In this case, the returned field element will not have magnitude 0. In fact, it’ll be unspecified, making the code that uses it below have undefined behavior. For magnitude 0, you should set the output to just be the 0 field element.

in src/fuzz.c:211 in 3874a937a9 outdated

206+/* Construct a valid field element from fuzzer with random magnitude  */
207+static void fuzz_field_construct(const uint8_t *data, size_t size, secp256k1_fe *r) {    
208+    if (size>=32) {
209+        secp256k1_fe a, zero;      
210+        secp256k1_fe_set_b32_mod(r, data);
211+        int rand_magnitude = data[31] % 33;

sipa commented at 9:49 pm on August 24, 2023:

I don’t think it’s a good idea to reuse fuzz input bytes for two distinct meanings (here: magnitude and the lowest byte of the field element representation). It may also be better to let the caller decide the magnitude (or at least max magnitude), and then let the function construct it.

in src/fuzz.c:218 in 3874a937a9 outdated

213+        if (rand_magnitude == 0) {
214+            return;
215+        }
216+        secp256k1_fe_clear(&zero);
217+        secp256k1_fe_negate(&zero, &zero, 0);
218+        secp256k1_fe_mul_int_unchecked(&zero, rand_magnitude - 1);

sipa commented at 9:50 pm on August 24, 2023:

The approach here does not reach all possible field element representations; only ones that can be represented as “normalized_number times integer in range 1 to 31”.

I think it would be better if you’d read a full 40 bytes, and then use masking (using bitwise AND to set certain bits to zero) and/or rejection (just give up if the resulting value has bad magnitude) to obtain field elements of the desired magnitude.

YafeiXie1 commented at 2:30 pm on August 25, 2023:

Thanks for your suggestions! I will modify this fuzz_field_construct function and other errors.

in src/fuzz.c:330 in 3874a937a9 outdated

325+/* Test addition of field element and its negative value */ 
326+static void fuzz_field_add_negate(const uint8_t *data, size_t size) {
327+    if (size >= 32) {        
328+        secp256k1_fe a, negate;
329+        fuzz_field_construct(data, size, &a);
330+        if (a.magnitude >= 32) {

sipa commented at 9:52 pm on August 24, 2023:

This test is unnecessary; fuzz_field_construct only constructs values with magnitude at most 32.

in src/fuzz.c:270 in 3874a937a9 outdated

265+/* Test commutativity of addition on two field elements */ 
266+static void fuzz_field_add_commutativty(const uint8_t *data, size_t size) {
267+    if (size >= 64) {        
268+        secp256k1_fe a, b, r1, r2;
269+        fuzz_field_construct(data, size, &a);
270+        fuzz_field_construct(data + 32, size, &b);

sipa commented at 9:53 pm on August 24, 2023:

The size pass here is incorrect, because the array pointed to by data + 32 only has length size - 32. See also my comment about responsibility of guaranteeing length on fuzz_field_construct.

Merge branch 'bitcoin-core:master' into master bd19a5fcd1

Merge branch 'master' of https://github.com/YafeiXie1/secp256k1 a89cc3822d

1 6f4f78229f

Merge branch 'master' of https://github.com/YafeiXie1/secp256k1 f6930b202a

modified the function to construct field

and fuzzing tests of group operations

ebfb2cf6a4

YafeiXie1 commented at 2:12 pm on August 29, 2023: none

Thanks for the previous review. This PR: Modified the field construct function to build more valid field elements. Modified and added the fuzzing tests for the group operations. Could you give me some suggestions?

in .vscode/settings.json:1 in ebfb2cf6a4 outdated

0@@ -0,0 +1,5 @@
1+{

sipa commented at 2:31 pm on August 29, 2023:

Don’t add this file, please. It’s for your local setup, not everyone’s.

in src/fuzz.c:242 in ebfb2cf6a4 outdated

237+    r->n[3] &= mask1;
238+    r->n[4] &= mask2;
239+    if (r->normalized) {
240+        if ((r->n[4] == 0x0FFFFFFFFFFFFULL) && ((r->n[3] & r->n[2] & r->n[1]) == 0xFFFFFFFFFFFFFULL)) {
241+            uint64_t mask3 = 0xFFFFEFFFFFC2FULL - 1;
242+            r->n[0] &= mask3;

sipa commented at 5:46 pm on August 29, 2023:

I believe this is inaccurate, as it will unconditionally wipe some bits in r->n[0] even when unnecessary, making certain values unreachable. E.g. it’ll turn r->n[0] = 0x1000003d1 into r->n[0] = 0.

in src/fuzz.c:212 in ebfb2cf6a4 outdated

207+*
208+* On input, 'data' must have 42 bytes at least. If 'normalized' != 0, this function will only construct normalized field elements.
209+* If 'normalized' = 0, this function will construct normalized or non-normalized field elements depending on the fuzzer data.
210+* On output, r will be a valid field element
211+**/
212+static void fuzz_field_construct(const uint8_t *data, int normalized, secp256k1_fe *r) {

sipa commented at 6:08 pm on August 29, 2023:

I think the effectiveness of some of the tests below could be increased further by passing a max magnitude argument to fuzz_field_construct, so that things like

0        fuzz_field_construct(data, 0, &a);
1        fuzz_field_construct(data + 42, 0, &b);         
2        if (a.magnitude + b.magnitude <= 32) {

could become

0        fuzz_field_construct(data, 0, 32, &a);
1        fuzz_field_construct(data + 42, 0, 32 - a.magnitude, &b);

It’d also remove the need for fuzz_ge_fe_construct.

in src/fuzz.c:306 in ebfb2cf6a4 outdated

301+        CHECK(secp256k1_fe_cmp_var(&a, &b) == 0);
302+    }
303+}
304+
305+/* Test commutativity of addition on two field elements */ 
306+static void fuzz_field_add_commutativty(const uint8_t *data, size_t size) {

sipa commented at 6:14 pm on August 29, 2023:

Nit: typo

in src/fuzz.c:529 in ebfb2cf6a4 outdated

524+        secp256k1_fe a, r1, r2;
525+        fuzz_field_construct(data, 0, &a);
526+        if (a.magnitude <= 10) {
527+            int m = a.magnitude;
528+            r1 = a;
529+            secp256k1_fe_mul_int(&r1, 3);

sipa commented at 6:19 pm on August 29, 2023:

It’s a bit limiting to only test multiplication by 3.

in src/fuzz.c:724 in ebfb2cf6a4 outdated

719+    secp256k1_fe x, y;
720+    secp256k1_ge ge;
721+    fuzz_ge_fe_construct(data, 1, &x);
722+    if (secp256k1_ge_x_on_curve_var(&x)) {
723+        int odd = data[42] % 2;
724+        secp256k1_ge_set_xo_var(&ge, &x, odd);

sipa commented at 7:02 pm on August 29, 2023:

It would be nice if the y coordinate could also be given a nontrivial normalization/magnitude here.

As a stretch, it could be interesting to (optionally) also construct the group element by reading the Y coordinate from the fuzz input, and then construct the corresponding X coordinate (it needs a cube root, but that’s relatively simple for our field). I can give you some pointers if you’re interested in that.

YafeiXie1 commented at 1:01 pm on August 30, 2023:

Thanks for the comments! Yes, I’m interested in constructing the group element by reading the Y coordinates from fuzzer data (find X from the elliptic curve equation).

In addition, I changed the fuzz_field_construct function (add another input argument to determine the max magnitude) and fixed the mask errors. Currently, I’m working on the fuzzing test about the function related to point multiplication operation, is this a good part to carry on, or do you have a better recommendation?

sipa commented at 1:05 pm on August 30, 2023:

I’ll have a look over your changes soon. In the mean time, yes, having some fuzzing of EC multiplication would be good.

To compute cube roots modulo 2^256-2^32-977 (or field size), see this explanation here: https://github.com/bitcoin/bips/blob/cc177ab7bc5abcdcdf9c956ee88afd1052053328/bip-0324/reference.py#L165L191

in src/fuzz.c:744 in ebfb2cf6a4 outdated

739+    CHECK(secp256k1_fe_equal(&a->x, &b->x));
740+    CHECK(secp256k1_fe_equal(&a->y, &b->y));
741+}
742+
743+/* Test transformation of group element between the affine coordinates and jacobian coordinates */
744+static void fuzz_ge_gef(const uint8_t *data, size_t size) {

sipa commented at 7:03 pm on August 29, 2023:

What does gef refer to?

Changed functions for the construction of

field and group elements

76d1fa5e3d

YafeiXie1 commented at 5:55 pm on August 30, 2023: none

This PR: Field element construct function: Added another input argument to determine the max magnitude. Changed the mask for special case when the field element is normalized.

Group element construct function: Remove fuzz_ge_fe_construct function. Give Y coordinate the normalization/magnitude depending on the fuzz input.

I found an interesting situation: when I run the fuzzing test ‘fuzz_field_equal’ for the ‘secp256k1_fe_equal(a, b)’ (the magnitude of a and b cannot exceed 1 and 31 respectively), the test failed when the magnitude of ‘b’ equals to 31. In the implementation of ‘secp256k1_fe_equal’ (in ‘field_impl.h’ file), after the negating function, the magnitude of ‘a’ increases to 2. Maybe the max magnitude for ‘b’ should be 30 in this function?

Modified fuzz tests about field operations #1407