Re: Uninitialized memory bug found in /mpn/generic/mod_1_1.c
I have dug deeper into understanding what happens with both versions (method 1
& 2).
If the divisor has a high bit set, then pre[2] is not initialized inside
mpn_mod_1_1p_cps(), but it is also not used inside mpn_mod_1_1p() as there are
no leading zeroes.
In the other scenario, if the high bit is set, pre[2] is set to its appropriate
value, and it is used inside mpn_mod_1_1p().
Some commenting could be placed inside /mpn/generic/mod_1.c around lines 248
and 261, or pre[4] can be initialized to all 0's on both 248 & 261: mp_limb_t
pre[4] = { 0 };
-Brett Kuntz
From: "Vincent Lefevre"
To: "marco bodrato"
Cc: "Brett Kuntz" , gmp-bugs@gmplib.org
Sent: Thursday, August 31, 2023 11:06:51 AM
Subject: Re: Uninitialized memory bug found in /mpn/generic/mod_1_1.c
On 2023-08-31 17:03:12 +0200, marco.bodr...@tutanota.com wrote:
> Ciao,
>
> 31 ago 2023, 16:30 da ku...@shaw.ca:
>
> > 1) Edit line 248 mpn/generic/mp_limb_t pre[4]; into:
> >
> ~/src/gmp$ hg diff mpn/generic/
> diff -r 3ac5afa36be5 mpn/generic/mod_1.c
> --- a/mpn/generic/mod_1.c Wed Nov 02 13:48:37 2022 +0100
> +++ b/mpn/generic/mod_1.c Thu Aug 31 16:46:35 2023 +0200
> @@ -245,7 +245,7 @@
> }
> else
> {
> - mp_limb_t pre[4];
> + mp_limb_t pre[4] = {-1, -1, -1, -1};
> mpn_mod_1_1p_cps (pre, b);
> return mpn_mod_1_1p (ap, n, b, pre);
> }
>
I don't think that this is sufficient for the test.
The code Brett mentioned is for MOD_1_1P_METHOD = 2.
So, in mpn/generic/mod_1_1.c, I also changed
# define MOD_1_1P_METHOD 1 /* need to make sure this is 2 for asm testing */
to
# define MOD_1_1P_METHOD 2 /* need to make sure this is 2 for asm testing */
and at the beginning of
mpn_mod_1_1p (mp_srcptr ap, mp_size_t n, mp_limb_t b, const mp_limb_t bmodb[4])
I added
ASSERT (bmodb[2] != -1);
(if bmodb[2] is not set, this would fail).
Then I configured with
./configure --disable-assembly --enable-assert
to enable the code and the assert, then "make" and "make check".
But even with that, I don't get any failure.
--
Vincent Lefèvre - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Uninitialized memory bug found in /mpn/generic/mod_1_1.c
> Looking at mpn/generic/mod_1_1.c, > if MOD_1_1P_METHOD == 1, the value[2] in the array is always set and always > used; > if MOD_1_1P_METHOD == 2, the value[2] is set only if cnt!=0, and it is used > only if cnt!=0. > There are also some assembler code implementations, each one with its couple > of functions. I concluded the same just now. -Brett Kuntz From: "marco bodrato" To: "Vincent Lefevre" Cc: "Brett Kuntz" , gmp-bugs@gmplib.org Sent: Thursday, August 31, 2023 12:33:46 PM Subject: Re: Uninitialized memory bug found in /mpn/generic/mod_1_1.c Ciao, 31 ago 2023, 18:06 da vinc...@vinc17.net: I don't think that this is sufficient for the test. The code Brett mentioned is for MOD_1_1P_METHOD = 2. The code Brett mentioned is mixed, I fear. Looking at mpn/generic/mod_1_1.c, if MOD_1_1P_METHOD == 1, the value[2] in the array is always set and always used; if MOD_1_1P_METHOD == 2, the value[2] is set only if cnt!=0, and it is used only if cnt!=0. There are also some assembler code implementations, each one with its couple of functions. BQ_BEGIN So, in mpn/generic/mod_1_1.c, I also changed # define MOD_1_1P_METHOD 1 /* need to make sure this is 2 for asm testing */ BQ_END Not enough, MOD_1_1P_METHOD may be defined by gmp-mparam.h One should also check how MOD_1N_TO_MOD_1_1_THRESHOLD interact with the tests. BQ_BEGIN ASSERT (bmodb[2] != -1); BQ_END BQ_BEGIN But even with that, I don't get any failure. BQ_END Actually it is possible to trigger this, if you put it in the wrong place, I mean, outside the branch actually using the value... but it is not interesting. Ĝis, Marco ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Uninitialized memory bug found in /mpn/generic/mod_1_1.c
Ciao, 31 ago 2023, 18:06 da vinc...@vinc17.net: > I don't think that this is sufficient for the test. > The code Brett mentioned is for MOD_1_1P_METHOD = 2. > The code Brett mentioned is mixed, I fear. Looking at mpn/generic/mod_1_1.c,if MOD_1_1P_METHOD == 1, the value[2] in the array is always set and always used; if MOD_1_1P_METHOD == 2, the value[2] is set only if cnt!=0, and it is used only if cnt!=0. There are also some assembler code implementations, each one with its couple of functions. > So, in mpn/generic/mod_1_1.c, I also changed > # define MOD_1_1P_METHOD 1/* need to make sure this is 2 for asm testing > */ > Not enough, MOD_1_1P_METHOD may be defined by gmp-mparam.h One should also check how MOD_1N_TO_MOD_1_1_THRESHOLD interact with the tests. > ASSERT (bmodb[2] != -1); > > But even with that, I don't get any failure. > Actually it is possible to trigger this, if you put it in the wrong place, I mean, outside the branch actually using the value... but it is not interesting. Ĝis, Marco ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Uninitialized memory bug found in /mpn/generic/mod_1_1.c
On 2023-08-31 17:03:12 +0200, marco.bodr...@tutanota.com wrote:
> Ciao,
>
> 31 ago 2023, 16:30 da ku...@shaw.ca:
>
> > 1) Edit line 248 mpn/generic/mp_limb_t pre[4]; into:
> >
> ~/src/gmp$ hg diff mpn/generic/
> diff -r 3ac5afa36be5 mpn/generic/mod_1.c
> --- a/mpn/generic/mod_1.c Wed Nov 02 13:48:37 2022 +0100
> +++ b/mpn/generic/mod_1.c Thu Aug 31 16:46:35 2023 +0200
> @@ -245,7 +245,7 @@
> }
> else
> {
> - mp_limb_t pre[4];
> + mp_limb_t pre[4] = {-1, -1, -1, -1};
> mpn_mod_1_1p_cps (pre, b);
> return mpn_mod_1_1p (ap, n, b, pre);
> }
>
I don't think that this is sufficient for the test.
The code Brett mentioned is for MOD_1_1P_METHOD = 2.
So, in mpn/generic/mod_1_1.c, I also changed
# define MOD_1_1P_METHOD 1/* need to make sure this is 2 for asm testing */
to
# define MOD_1_1P_METHOD 2/* need to make sure this is 2 for asm testing */
and at the beginning of
mpn_mod_1_1p (mp_srcptr ap, mp_size_t n, mp_limb_t b, const mp_limb_t bmodb[4])
I added
ASSERT (bmodb[2] != -1);
(if bmodb[2] is not set, this would fail).
Then I configured with
./configure --disable-assembly --enable-assert
to enable the code and the assert, then "make" and "make check".
But even with that, I don't get any failure.
--
Vincent Lefèvre - Web:
Re: Uninitialized memory bug found in /mpn/generic/mod_1_1.c
Ciao,
31 ago 2023, 16:30 da ku...@shaw.ca:
> 1) Edit line 248 mpn/generic/mp_limb_t pre[4]; into:
>
~/src/gmp$ hg diff mpn/generic/
diff -r 3ac5afa36be5 mpn/generic/mod_1.c
--- a/mpn/generic/mod_1.c Wed Nov 02 13:48:37 2022 +0100
+++ b/mpn/generic/mod_1.c Thu Aug 31 16:46:35 2023 +0200
@@ -245,7 +245,7 @@
}
else
{
- mp_limb_t pre[4];
+ mp_limb_t pre[4] = {-1, -1, -1, -1};
mpn_mod_1_1p_cps (pre, b);
return mpn_mod_1_1p (ap, n, b, pre);
}
> 2) Recompile GMP.
>
~/src/gmp$ mkdir testbuild; (cd testbuild/;../configure&) >/dev/null
> 3) Use the mpn_mod_1() function as described on the following page and you
> will now get incorrect results:
>
~/src/gmp$ (cd testbuild/;make TESTS="t-mod_1" check -C tests/mpn; )|tail -n 15
PASS: t-mod_1
Testsuite summary for GNU MP 6.2.99
# TOTAL: 1
# PASS: 1
# SKIP: 0
# XFAIL: 0
# FAIL: 0
# XPASS: 0
# ERROR: 0
Even the modified library passes the tests.
Sorry, I'm not able to reproduce your bug report, not even with an arbitrarily
modified source code.
~/src/gmp$ hg revert mpn/generic/
sto ripristinando mpn/generic/mod_1.c
I'd say that when the limb you are looking at is not initialized, then a
function not using it is called.
I'd suggest: when reading mpn/generic/mod_1_1.c, pay attention to #if and
#endif .
Ĝis,
Marco
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Uninitialized memory bug found in /mpn/generic/mod_1_1.c
Brett Kuntz writes:
Go to line 248 inside mpn/generic/mod_1.c
mp_limb_t pre[4];
There is no such thing on an unedited version of GMP 6.3, not on line
248 not anyplace else in that file.
mpn_mod_1_1p_cps (pre, b);
Only initializes pre[0], pre[1], and pre[3]. ***NOT*** pre[2].
Your point?
The final line:
return mpn_mod_1_1p (ap, n, b, pre);
Reads from pre[2] erroneously and gives incorrect results if your
stack memory has anything other than a 0 there.
That line does not read any elements from pre[]. You have misunderstood
the semantics of C.
But if you actually claim that an unedited GMP has a bug here, please
construct a test case which uses documented interfaces, and which
demonstrates the claimed bug.
1) Edit line 248 mpn/generic/mp_limb_t pre[4]; into:
There is no file with that name.
mp_limb_t pre[4] = { -1, -1, -1, -1 };
2) Recompile GMP.
3) Use the mpn_mod_1() function as described on the following page and
you will now get incorrect results:
It is clear that you have not tried that yourself.
--
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Uninitialized memory bug found in /mpn/generic/mod_1_1.c
> It does not exist, only pre[0] through pre[3] does.
pre[4] **IS** pre[0] through pre[3]
Go to line 248 inside mpn/generic/mod_1.c
mp_limb_t pre[4];
That is NOT initialized.
The next line:
mpn_mod_1_1p_cps (pre, b);
Only initializes pre[0], pre[1], and pre[3]. ***NOT*** pre[2].
The final line:
return mpn_mod_1_1p (ap, n, b, pre);
Reads from pre[2] erroneously and gives incorrect results if your stack memory
has anything other than a 0 there.
> But if you actually claim that an unedited GMP has a bug here, please
construct a test case which uses documented interfaces, and which
demonstrates the claimed bug.
1) Edit line 248 mpn/generic/mp_limb_t pre[4]; into:
mp_limb_t pre[4] = { -1, -1, -1, -1 };
2) Recompile GMP.
3) Use the mpn_mod_1() function as described on the following page and you will
now get incorrect results:
https://gmplib.org/manual/Low_002dlevel-Functions
-Brett Kuntz
From: "Torbjörn Granlund"
To: "Brett Kuntz"
Cc: gmp-bugs@gmplib.org
Sent: Thursday, August 31, 2023 3:40:47 AM
Subject: Re: Uninitialized memory bug found in /mpn/generic/mod_1_1.c
Brett Kuntz writes:
Take a look at function mpn_mod_1() in /mpn/generic/ mod_1.c on lines 248 - 250
mp_limb_t pre[4];
mpn_mod_1_1p_cps (pre, b);
mp_limb_t pre[4] is not initialized
It does not exist, only pre[0] through pre[3] does.
and the mpn_mod_1_1p_cps() function
never writes to pre[2]. So if we change that to mp_limb_t pre[4] = { -1,
-1, -1, -1 }; as a test we'll quickly see that inside mpn_mod_1_1p_cps()
the value cps[2] (pre[2]) is never written to and if we print out pre[4]
after running it we'll get output like: 0x21CFE6CFC938B36BU,
0xU, 0xU, 0x9581CA13918612E1U (pre[2] is
-1)
/mpn/generic/mod_1_1.c lines 260-266:
if (LIKELY (cnt != 0))
{
mp_limb_t B1modb = -b;
B1modb *= ((bi >> (GMP_LIMB_BITS-cnt)) | (CNST_LIMB(1) << cnt));
ASSERT (B1modb <= b); /* NB: not fully reduced mod b */
cps[2] = B1modb >> cnt;
}
cnt will ALWAYS equal 0 since there will be NO leading 0's when this is
called since /mpn/generic/mod_1_1.c checks for the high bit being SET
before calling.. which means this function only ever gets called with NO
leading zeros!!!
Why are you so worked up?
The logic seems perfectly fine.
ALSO there are unexplained differences between MOD_1_1P_METHOD 1 and
MOD_1_1P_METHOD 2 when it comes to the function mpn_mod_1_1p_cps(). In
one of them pre[4] is always set and in the other (method 2) pre[2] is
skipped! Why are these two functions different? It looks like their job
is to calculate the inverses for the following mod functions so one
would expect them to be the same.
There are lots of "unexplained" things in the GMP internal functions.
But trust me, the GMP developers understand the sources.
ALSO the x64 assembly versions of these codes also does not always set
all 4 values of pre[4] and this has lead to incorrect results when using
the exported function mpn_mod_1().
You hypothesise things here. And you're wrong.
I benevolent reading of your claims here is that things will be bad if
you use one variant of the internal _cps function with another variant
of the corresponding internal mod function. If that's what you're
trying to say, then you're right. GMP is not edit proof, local user
edits might break it in all sorts of ways,
But if you actually claim that an unedited GMP has a bug here, please
construct a test case which uses documented interfaces, and which
demonstrates the claimed bug.
I do not understand these functions enough
Shouting from the top of your lungs about a bug which is just the result
of reading the sources, without allowing yourself time to understand the
logic fully, is somewhat unfair.
--
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Uninitialized memory bug found in /mpn/generic/mod_1_1.c
Brett Kuntz writes:
Take a look at function mpn_mod_1() in /mpn/generic/ mod_1.c on lines 248 -
250
mp_limb_t pre[4];
mpn_mod_1_1p_cps (pre, b);
mp_limb_t pre[4] is not initialized
It does not exist, only pre[0] through pre[3] does.
and the mpn_mod_1_1p_cps() function
never writes to pre[2]. So if we change that to mp_limb_t pre[4] = { -1,
-1, -1, -1 }; as a test we'll quickly see that inside mpn_mod_1_1p_cps()
the value cps[2] (pre[2]) is never written to and if we print out pre[4]
after running it we'll get output like: 0x21CFE6CFC938B36BU,
0xU, 0xU, 0x9581CA13918612E1U (pre[2] is
-1)
/mpn/generic/mod_1_1.c lines 260-266:
if (LIKELY (cnt != 0))
{
mp_limb_t B1modb = -b;
B1modb *= ((bi >> (GMP_LIMB_BITS-cnt)) | (CNST_LIMB(1) << cnt));
ASSERT (B1modb <= b); /* NB: not fully reduced mod b */
cps[2] = B1modb >> cnt;
}
cnt will ALWAYS equal 0 since there will be NO leading 0's when this is
called since /mpn/generic/mod_1_1.c checks for the high bit being SET
before calling.. which means this function only ever gets called with NO
leading zeros!!!
Why are you so worked up?
The logic seems perfectly fine.
ALSO there are unexplained differences between MOD_1_1P_METHOD 1 and
MOD_1_1P_METHOD 2 when it comes to the function mpn_mod_1_1p_cps(). In
one of them pre[4] is always set and in the other (method 2) pre[2] is
skipped! Why are these two functions different? It looks like their job
is to calculate the inverses for the following mod functions so one
would expect them to be the same.
There are lots of "unexplained" things in the GMP internal functions.
But trust me, the GMP developers understand the sources.
ALSO the x64 assembly versions of these codes also does not always set
all 4 values of pre[4] and this has lead to incorrect results when using
the exported function mpn_mod_1().
You hypothesise things here. And you're wrong.
I benevolent reading of your claims here is that things will be bad if
you use one variant of the internal _cps function with another variant
of the corresponding internal mod function. If that's what you're
trying to say, then you're right. GMP is not edit proof, local user
edits might break it in all sorts of ways,
But if you actually claim that an unedited GMP has a bug here, please
construct a test case which uses documented interfaces, and which
demonstrates the claimed bug.
I do not understand these functions enough
Shouting from the top of your lungs about a bug which is just the result
of reading the sources, without allowing yourself time to understand the
logic fully, is somewhat unfair.
--
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
Uninitialized memory bug found in /mpn/generic/mod_1_1.c
Hello, today I found a bug in the latest GMP (6.3) using uninitialized memory
in /mpn/generic/mod_1_1.c while trying to understand some functions like
mpn_mod_1_1p_cps.
Take a look at function mpn_mod_1() in /mpn/generic/ mod_1.c on lines 248 - 250
mp_limb_t pre[4];
mpn_mod_1_1p_cps (pre, b);
return mpn_mod_1_1p (ap, n, b, pre);
mp_limb_t pre[4] is not initialized and the mpn_mod_1_1p_cps() function never
writes to pre[2]. So if we change that to mp_limb_t pre[4] = { -1, -1, -1, -1
}; as a test we'll quickly see that inside mpn_mod_1_1p_cps() the value cps[2]
(pre[2]) is never written to and if we print out pre[4] after running it we'll
get output like: 0x21CFE6CFC938B36BU, 0xU, 0xU,
0x9581CA13918612E1U (pre[2] is -1)
/mpn/generic/mod_1_1.c lines 260-266:
if (LIKELY (cnt != 0))
{
mp_limb_t B1modb = -b;
B1modb *= ((bi >> (GMP_LIMB_BITS-cnt)) | (CNST_LIMB(1) << cnt));
ASSERT (B1modb <= b); /* NB: not fully reduced mod b */
cps[2] = B1modb >> cnt;
}
cnt will ALWAYS equal 0 since there will be NO leading 0's when this is called
since /mpn/generic/mod_1_1.c checks for the high bit being SET before calling..
which means this function only ever gets called with NO leading zeros!!!
ALSO there are unexplained differences between MOD_1_1P_METHOD 1 and
MOD_1_1P_METHOD 2 when it comes to the function mpn_mod_1_1p_cps(). In one of
them pre[4] is always set and in the other (method 2) pre[2] is skipped! Why
are these two functions different? It looks like their job is to calculate the
inverses for the following mod functions so one would expect them to be the
same.
Method 2 is the function that was written in x64 asm.
ALSO the x64 assembly versions of these codes also does not always set all 4
values of pre[4] and this has lead to incorrect results when using the exported
function mpn_mod_1().
/mpn/x86_64/mod_1_1.asm
neg %r12
mov %r12, %r8
mov %rax, (%rbx)C store bi
mov %rbp, 8(%rbx) C store cnt
imul%rax, %r12
mov %r12, 24(%rbx) C store B2modb
mov R32(%rbp), R32(%rcx)
testR32(%rcx), R32(%rcx)
jz L(z)
mov $1, R32(%rdx)
ifdef(`SHLD_SLOW',`
C Destroys %rax, unlike shld. Otherwise, we could do B1modb
C before B2modb, and get rid of the move %r12, %r8 above.
shl R8(%rcx), %rdx
neg R32(%rcx)
shr R8(%rcx), %rax
or %rax, %rdx
neg R32(%rcx)
shldR8(%rcx), %rax, %rdx
imul%rdx, %r8
shr R8(%rcx), %r8
mov %r8, 16(%rbx) C store B1modb
L(z):
pop %r12
pop %rbx
pop %rbp
FUNC_EXIT()
ret
Notice on line 230 of the asm file (mov %r8, 16(%rbx) // C store B1modb) gets
skipped over when count is 0 (which it will be 100% of the time when the
high-bit is set).
I checked mod_1_2.c, mod_1_3.c, and mod_1_4.c and they do not seem to have this
problem.
Also note that most compilers and run-times for me seem to have a flukey '0'
here in memory (which will be the correct value when the high-bit is set) so
that might be why no one has stumbled upon this bug yet or why it might pass
tests.
I do not understand these functions enough to suggest a fix. I do not know if
initializing pre[4] to all 0's will produce correct results.
Which is the correct version of mpn_mod_1_1p_cps() to use for now? (Method 1 or
Method 2)
My apologies if this is not the best bug report ever.
-Brett Kuntz
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
