Attempt at avoiding falsely flagged buffer overruns by erikbern · Pull Request #455 · spotify/annoy

erikbern · 2020-02-23T22:46:24Z

Just a quick shot at addressing jlmelville/uwot#50

erikbern · 2020-02-23T22:47:44Z

src/annoylib.h

      const double reallocation_factor = 1.3;
      S new_nodes_size = std::max(n, (S) ((_nodes_size + 1) * reallocation_factor));
-      void *old = _nodes;
+      void *new_nodes = NULL;


oops this was something that was irrelevant to this PR, let me revert

eddelbuettel

Using MAX_ARRAY_SIZE should work, and I can test it.

eddelbuettel · 2020-02-23T22:53:05Z

Could we ever run over MAX_ARRAY_SIZE ?

eddelbuettel · 2020-02-23T23:03:21Z

Oh, gosh, I had thought MAX_ARRAY_SIZE had been defined. Woulnd't

#define MAX_ARRAY_SIZE (1<<30)

together with

T v[MAX_ARRAY_SIZE];

put massive arrays on the stack?

Confused...

erikbern · 2020-02-23T23:04:51Z

put massive arrays on the stack?

No because the Node object is actually never allocated if you read the code. So it should be fine!

eddelbuettel · 2020-02-23T23:08:23Z

Testing now at rhub. Old code gave

   ../inst/include/annoylib.h:364:24: runtime error: index 1 out of bounds for type 'float [1]'         
   ../inst/include/annoylib.h:364:46: runtime error: index 1 out of bounds for type 'float [1]'                                                                                                                    
   ../inst/include/annoylib.h:364:13: runtime error: index 1 out of bounds for type 'float [1]'                                                                                                                    
   ../inst/include/annoylib.h:359:24: runtime error: index 1 out of bounds for type 'float [1]'          
   ../inst/include/annoylib.h:359:46: runtime error: index 1 out of bounds for type 'float [1]'                                                                                                                    
   ../inst/include/annoylib.h:359:13: runtime error: index 1 out of bounds for type 'float [1]'                                                                                                                    
   ../inst/include/annoylib.h:736:21: runtime error: index 1 out of bounds for type 'float [1]'                                                                                                                    
   ../inst/include/annoylib.h:736:31: runtime error: index 1 out of bounds for type 'float [1]'                                                                                                                    
   ../inst/include/annoylib.h:736:11: runtime error: index 1 out of bounds for type 'float [1]'                                                                                                                    
   ../inst/include/annoylib.h:394:9: runtime error: index 1 out of bounds for type 'float [1]'                                                                                                                     
   ../inst/include/annoylib.h:740:20: runtime error: index 1 out of bounds for type 'float [1]'                                                                                                                    
   ../inst/include/annoylib.h:740:31: runtime error: index 1 out of bounds for type 'float [1]'                                                                                                                    
   ../inst/include/annoylib.h:740:41: runtime error: index 1 out of bounds for type 'float [1]'

Will know in a moment if this helps. Not a perfect test (as we don't have the exact setup CRAN uses).

eddelbuettel · 2020-02-23T23:09:49Z

Part of me has the vague feeling that we once had a constant there, also got yelled at, and later went to v[1]. But that was a while back and it is all a little fuzzy...

erikbern · 2020-02-23T23:14:37Z

Part of me has the vague feeling that we once had a constant there, also got yelled at, and later went to v[1]. But that was a while back and it is all a little fuzzy...

I think it was zero for a long time. It's like the old saying that in computer science there's only three numbers, 0, 1, and n. And we went from 0 to 1 to now n :)

eddelbuettel · 2020-02-23T23:20:17Z

Sadly it didn't yet work.

   ../inst/include/annoylib.h:368:24: runtime error: index 1 out of bounds for type 'float [1]'
   ../inst/include/annoylib.h:368:46: runtime error: index 1 out of bounds for type 'float [1]'
   ../inst/include/annoylib.h:368:13: runtime error: index 1 out of bounds for type 'float [1]'
   ../inst/include/annoylib.h:363:24: runtime error: index 1 out of bounds for type 'float [1]'
   ../inst/include/annoylib.h:363:46: runtime error: index 1 out of bounds for type 'float [1]'
   ../inst/include/annoylib.h:363:13: runtime error: index 1 out of bounds for type 'float [1]'
   ../inst/include/annoylib.h:740:21: runtime error: index 1 out of bounds for type 'float [1]'
   ../inst/include/annoylib.h:740:31: runtime error: index 1 out of bounds for type 'float [1]'
   ../inst/include/annoylib.h:740:11: runtime error: index 1 out of bounds for type 'float [1]'          
   ../inst/include/annoylib.h:398:9: runtime error: index 1 out of bounds for type 'float [1]'
   ../inst/include/annoylib.h:744:20: runtime error: index 1 out of bounds for type 'float [1]'          
   ../inst/include/annoylib.h:744:31: runtime error: index 1 out of bounds for type 'float [1]'          
   ../inst/include/annoylib.h:744:41: runtime error: index 1 out of bounds for type 'float [1]'

jlmelville · 2020-02-23T23:29:18Z

Is it possible that the declaration needs to be changed in more places, e.g.:

annoy/src/annoylib.h

Line 517 in d6dc805

    
           T v[1]; // We let this one overflow intentionally. Need to allocate at least 1 to make GCC happy

jlmelville · 2020-02-24T01:05:29Z

If I replace all declarations of T v[1] with T [V_ARRAY_SIZE] in annoylib.h, then when running the GCC UBSAN checker via rhub::check_with_sanitizers() with the RcppAnnoy project, I no longer see the ../inst/include/annoylib.h:872:11: runtime error: index 1 out of bounds for type 'float [1]' errors. For reference in the new version of annoylib.h, that line is:

annoy/src/annoylib.h

Line 897 in d6dc805

n->v[z] = w[z];

However, I now see a new runtime error:

../inst/include/annoylib.h:662:18: runtime error: load of misaligned address 0x55d2429c5424 for type 'const long unsigned int', which requires 8 byte alignment
0x55d2429c5424: note: pointer points here
  00 00 00 00 00 00 00 00  00 00 00 00 01 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00

the line referenced is:

annoy/src/annoylib.h

Line 662 in d6dc805

    
           return (y[chunk] & (static_cast<T>(1) << (n_bits - 1 - (n->v[0] % n_bits)))) != 0;

eddelbuettel · 2020-02-24T01:52:48Z

Good thinking about replacing the other assignments! I was rushing things before making dinner.

@erikbern Any magic for that line 662?

erikbern · 2020-02-24T02:17:12Z

Turns out there's actually 4 places this had to be modified, and I had just fixed it in one of them.

Can you check if it works now? Thanks!

jlmelville · 2020-02-24T02:59:01Z

Sorry for any confusion @erikbern, my previous comment was for what is now change 81648fb, i.e. I had changed those four locations already.

As of 81648fb, the old error has disappeared, but a new one has appeared, related to line 662.

erikbern · 2020-02-24T03:01:44Z

../inst/include/annoylib.h:662:18: runtime error: load of misaligned address 0x55d2429c5424 for type 'const long unsigned int', which requires 8 byte alignment

Actually this PR won't fix that issue, and I'm not sure how to even fix it. Some thoughts:

Make sure that the memory is always aligned to 8 byte offsets, possibly using something like http://man7.org/linux/man-pages/man3/posix_memalign.3.html
Rewrite the hamming code to use 4 byte ints instead of 8 byte ints
Change the few places where we access v[i] to not use an array dereference

None of these are entirely trivial, but I think the last one is reasonably simple since there's only a few places where this really happens. I'll take a look at it in the next few days.

jlmelville · 2020-02-24T03:27:53Z

Fair enough. I would be happy to see the current PR merged, as it does localize the UBSAN complaints to just the Hamming calculation, which is an improvement.

I'd like to open a separate issue to cover the new misalignment problem, even if there isn't an obvious fix.

erikbern · 2020-02-24T03:50:40Z

Cool will handle the Hamming issue in a separate PR, thanks

jlmelville · 2020-02-24T03:51:56Z

Thanks for your work on this @erikbern, it is much appreciated.

eddelbuettel · 2020-02-24T13:34:45Z

Very much seconded. That was excellent help, and really timely :)

erikbern commented Feb 23, 2020

View reviewed changes

Attempt at avoiding falsely flagged buffer overruns

113867c

erikbern force-pushed the annoy-v-array-length branch from 46a0ce6 to 113867c Compare February 23, 2020 22:49

eddelbuettel approved these changes Feb 23, 2020

View reviewed changes

make it a bit smaller to please MSVC

d6dc805

use it in all 4 places

81648fb

This was referenced Feb 24, 2020

UBSAN issue with Hamming due misalignment #456

Open

Work around Annoy UBSAN issues jlmelville/uwot#50

Closed

erikbern merged commit f6d7b0f into master Feb 24, 2020

erikbern deleted the annoy-v-array-length branch February 24, 2020 03:50

Conversation

erikbern commented Feb 23, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

erikbern Feb 23, 2020

Choose a reason for hiding this comment

Uh oh!

eddelbuettel left a comment

Choose a reason for hiding this comment

Uh oh!

eddelbuettel commented Feb 23, 2020

Uh oh!

eddelbuettel commented Feb 23, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

erikbern commented Feb 23, 2020

Uh oh!

eddelbuettel commented Feb 23, 2020

Uh oh!

eddelbuettel commented Feb 23, 2020

Uh oh!

erikbern commented Feb 23, 2020

Uh oh!

eddelbuettel commented Feb 23, 2020

Uh oh!

jlmelville commented Feb 23, 2020

Uh oh!

jlmelville commented Feb 24, 2020

Uh oh!

eddelbuettel commented Feb 24, 2020

Uh oh!

erikbern commented Feb 24, 2020

Uh oh!

jlmelville commented Feb 24, 2020

Uh oh!

erikbern commented Feb 24, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jlmelville commented Feb 24, 2020

Uh oh!

erikbern commented Feb 24, 2020

Uh oh!

jlmelville commented Feb 24, 2020

Uh oh!

eddelbuettel commented Feb 24, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

erikbern commented Feb 23, 2020 •

edited

Loading

eddelbuettel commented Feb 23, 2020 •

edited

Loading

erikbern commented Feb 24, 2020 •

edited

Loading