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-
YafeiXie1 commented at 12:09 pm on August 21, 2023: noneThanks 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 knowssize >= 32
)? If so, then theif (size>=32) {
branch is unnecessary, and could be replaced withCHECK(size >= 32);
instead, or thesize
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 casedata
andsize
arguments probably need to be made pointers (const uint8_t **data, size_t *size
), so they can be updated byfuzz_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 iffuzz_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:Thesize
pass here is incorrect, because the array pointed to bydata + 32
only has lengthsize - 32
. See also my comment about responsibility of guaranteeing length onfuzz_field_construct
.Merge branch 'bitcoin-core:master' into master bd19a5fcd1Merge branch 'master' of https://github.com/YafeiXie1/secp256k1 a89cc3822d1 6f4f78229fMerge branch 'master' of https://github.com/YafeiXie1/secp256k1 f6930b202amodified the function to construct field
and fuzzing tests of group operations
YafeiXie1 commented at 2:12 pm on August 29, 2023: noneThanks 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 inr->n[0]
even when unnecessary, making certain values unreachable. E.g. it’ll turnr->n[0] = 0x1000003d1
intor->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 like0 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: typoin 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 doesgef
refer to?Changed functions for the construction of
field and group elements
YafeiXie1 commented at 5:55 pm on August 30, 2023: noneThis 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 - Does it lie with the caller (e.g. is it only allowed to call