nn_divapprox_classical_preinv_c sometimes over-reads input `a`

[percontation]

The tests cause 1-word over-reads in nn_divapprox_classical_preinv_c.

The following patch makes this condition visible:

diff --git a/nn_quadratic.c b/nn_quadratic.c
index 9a71d5e..2a5c63c 100644
--- a/nn_quadratic.c
+++ b/nn_quadratic.c
@@ -312,6 +312,9 @@ word_t nn_divapprox_classical_preinv_c(nn_t q, nn_t a, len_t m, nn_src_t d,
    word_t cy = 0, d1 = d[n - 1];
    len_t s = m - n + 1;

+   nn_t orig_a = a;
+   nn_src_t orig_d = d;
+
    ASSERT(q != a);
    ASSERT(q != d);
    ASSERT(a != d);
@@ -352,7 +355,16 @@ word_t nn_divapprox_classical_preinv_c(nn_t q, nn_t a, len_t m, nn_src_t d,
       a--;
       /* rare case where truncation ruins normalisation */
       if (ci > d[s] || (ci == d[s] && nn_cmp_m(a - s + 1, d, s) >= 0))
+      {
+         // word_t xxx = (a-s)+1 + s+1  -  (orig_a + m);
+         // if(xxx > 0 && xxx < 9999)
+         //   printf(">>>%zx\n", xxx); // xxx should never be positive... but is sometimes 1.
+
+         // These asserts are the conditions for the nn_sub_m in _nn_divapprox_helper *not* accessing OOB
+         ASSERT(orig_a <= (a-s)+1 && (a-s)+1 + s+1 <= orig_a + m); // The second clause here is violated.
+         ASSERT(orig_d <= d && d + s+1 <= orig_d + n);
          return _nn_divapprox_helper(q, a - s, d, s);
+      }

       divapprox21_preinv2(q[s - 1], ci, a[0], dinv);

(Not sure what the fix is; reading math code is hard.)

[wbhart]

You have

…

On 31 January 2018 at 02:30, Ryan Goulden ***@***.***> wrote: The tests cause 1-word over-reads in nn_divapprox_classical_preinv_c. The following patch makes this condition visible: diff --git a/nn_quadratic.c b/nn_quadratic.c index 9a71d5e..f929801 100644 --- a/nn_quadratic.c +++ b/nn_quadratic.c @@ -312,6 +312,9 @@ word_t nn_divapprox_classical_preinv_c(nn_t q, nn_t a, len_t m, nn_src_t d, word_t cy = 0, d1 = d[n - 1]; len_t s = m - n + 1; + nn_t orig_a = a; + nn_src_t orig_d = d; + ASSERT(q != a); ASSERT(q != d); ASSERT(a != d); @@ -352,7 +355,14 @@ word_t nn_divapprox_classical_preinv_c(nn_t q, nn_t a, len_t m, nn_src_t d, a--; /* rare case where truncation ruins normalisation */ if (ci > d[s] || (ci == d[s] && nn_cmp_m(a - s + 1, d, s) >= 0)) + { + // word_t xxx = (a-s)+1 + s+1 - (orig_a + m); + // if(xxx > 0 && xxx < 9999) + // printf(">>>%zx\n", xxx); // xxx should never be positive... but is sometimes 1. + ASSERT(orig_a <= (a-s)+1 && (a-s)+1 + s+1 <= orig_a + m); // The second clause here is violated. + ASSERT(orig_d <= d && d + s+1 <= orig_d + n); return _nn_divapprox_helper(q, a - s, d, s); + } divapprox21_preinv2(q[s - 1], ci, a[0], dinv); (Not sure what the fix is; reading math code is hard.) — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#19>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAOzppNus8nZbs4KgjMiqM0RbIthElHhks5tP8IegaJpZM4RzSQ6> .

[wbhart]

You have ASSERT(orig_a <= (a-s)+1 && (a-s)+1 + s+1 <= orig_a + m); // The second clause here is violated. But a - s + 1 + s + 1 = a + 2, whereas the actual code only accesses words before a - s + 1 + s = a + 1. So I think your ASSERT is wrong in this case. It should be (a-s)+1 + s <= orig_a + m

[percontation]

I think the assert is correct. I believe the code is actually accessing a + 1 (aka only words before a + 2).

We invoke _nn_divapprox_helper with a = a-s and s = s; _nn_divapprox_helper does nn_sub_m(a + 1, a + 1, d, s + 1);. This is nn_sub_m((a-s) + 1, (a-s) + 1, d, (s) + 1);, making ((a-s) + 1) + ((s) + 1) = a+2 the one-past-the-last-word accessed.

[wbhart]

Ok, yeah, I see now. I'll try to fix it.

[percontation]

👍 (FYI: dunno if I mentioned it, this and the other issue I filed came from me compiling & running tests with some -fsanitize args. Mostly because I was trying to debug the functions I added, but I figured I should report the other things that popped up too.)

[wbhart]

It seems that replacing line 3 of _nn_divapprox_helper with: nn_sub_m(a + 1, a + 1, d, s + (s <= 1)); fixes the problem. But I am not sure if it is correct or not. It does seem like the s + 1 that was here before couldn't possibly be correct. But just changing it to s breaks the tests because the following lines expect everything up to a[2] to be adjusted. I suspect the real problem is there is a corner case that is not being dealt with correctly, and it was masked by using s + 1 instead of s. It needs a more careful look. But I'm finding it difficult to find time to do that at the moment.