Page MenuHomePhabricator

[InterleavedAccessAnalysis] Fix integer overflow in insertMember.
ClosedPublic

Authored by fhahn on Dec 10 2018, 6:10 PM.

Details

Summary

Without checking for integer overflow, invalid members can be added
e.g. if the calculated key overflows, becomes positive and the largest key.

This fixes

https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=7560
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=13128
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=13229

Diff Detail

Repository
rL LLVM

Event Timeline

fhahn created this revision.Dec 10 2018, 6:10 PM

I guess it would be even safer to use fixed sized integer types here, but that would have a larger impact.

I don't understand the implications of returning false here...

I'd like to see a general plan for eventually excising the use of "int" from all the interleaving code before we start making changes here, so it's clear we're heading in the right direction.

fhahn added a comment.Dec 19 2018, 2:16 PM

I don't understand the implications of returning false here...

I'd like to see a general plan for eventually excising the use of "int" from all the interleaving code before we start making changes here, so it's clear we're heading in the right direction.

Right, I'll take a look at that.

fhahn updated this revision to Diff 189113.Mar 3 2019, 7:41 PM
fhahn edited the summary of this revision. (Show Details)

Updated to catch more cases. This now fixes 4 fuzzer failures

Herald added a project: Restricted Project. · View Herald TranscriptMar 3 2019, 7:41 PM
fhahn added a comment.Mar 3 2019, 7:52 PM

Sorry for the long delay....

I don't understand the implications of returning false here...

It indicates to the caller that the instruction wasn't added to the interleave group. It's checked in analyzeInterleaving (in VectorUtils.cpp), to see if we should add the group to InterleaveGroupMap for the instruction. Returning false and not inserting the member should always be safe.

I'd like to see a general plan for eventually excising the use of "int" from all the interleaving code before we start making changes here, so it's clear we're heading in the right direction.

I've put up D58889, which switches to fixed size integer types. Is that along the lines you were thinking?

If it's safe to conservatively return false here, and we're convinced realistic code isn't going to require larger strides/indexes, it's fine to just reject anything that won't fit into a 32-bit integer, I guess.

llvm/include/llvm/Analysis/VectorUtils.h
261 ↗(On Diff #189113)

Not part of your patch, I guess, but do we have any particular reason to expect that Stride does not equal INT_MIN?

284 ↗(On Diff #189113)

Not sure I understand the "-2" and "+2" here; is the issue that it collides with the default DenseMap tombstone otherwise? Can we use some map that doesn't randomly reserve certain integers? Otherwise, please add an explicit note, and check for the tombstone/empty keys separately from the overflow check.

Do we have some overflow-checked addition helper we could use instead of writing out the overflow check here?

fhahn added inline comments.Mar 5 2019, 6:35 PM
llvm/include/llvm/Analysis/VectorUtils.h
284 ↗(On Diff #189113)

Yep it's a tombstone check. I guess we could use std::unordered_map, will that have a perf impact?

I'll check again if there are some overflow helpers anywhere, but if not then it might be worth adding some.

fhahn updated this revision to Diff 189587.Mar 6 2019, 2:01 PM

Use helpers from CheckedArithmetic.h for overflow checks, split out tombstone issue.

fhahn edited the summary of this revision. (Show Details)Mar 6 2019, 2:03 PM
fhahn marked 3 inline comments as done.
fhahn added inline comments.
llvm/include/llvm/Analysis/VectorUtils.h
261 ↗(On Diff #189113)

I don't think so, I'll check and address it separately.

284 ↗(On Diff #189113)

I've split out the tombstone handling to D59050 and updated the code to use CheckedArithmetic.h's helper functions.

efriedma accepted this revision.Mar 6 2019, 3:05 PM

LGTM

This revision is now accepted and ready to land.Mar 6 2019, 3:05 PM
This revision was automatically updated to reflect the committed changes.