Modified fuzz tests about field operations #1407

pull YafeiXie1 wants to merge 8 commits into bitcoin-core:master from YafeiXie1:master changing 1 files +1254 −0
  1. 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?
  2. modify the fuzzing tests of field operations 3874a937a9
  3. modified the fuzzing tests of field operations. a0b3d0a0de
  4. real-or-random added the label assurance on Aug 21, 2023
  5. sipa cross-referenced this on Aug 21, 2023 from issue add fuzz tests about field operations. by YafeiXie1
  6. 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).
  7. 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).
  8. 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?
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. Merge branch 'bitcoin-core:master' into master bd19a5fcd1
  16. Merge branch 'master' of https://github.com/YafeiXie1/secp256k1 a89cc3822d
  17. 1 6f4f78229f
  18. Merge branch 'master' of https://github.com/YafeiXie1/secp256k1 f6930b202a
  19. modified the function to construct field
    and fuzzing tests of group operations
    ebfb2cf6a4
  20. 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?
  21. 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.
  22. 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.
  23. 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.

  24. 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
  25. 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.
  26. 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

  27. 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?
  28. Changed functions for the construction of
    field and group elements
    76d1fa5e3d
  29. 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?


github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin-core/secp256k1. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-10-31 23:15 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me