Bug 188556 – [JSC] Should not rotate constant with 64

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Yusuke Suzuki]

[JSC] Should not rotate constant with 64

[Yusuke Suzuki]

Created attachment 347080 [details]
Patch

[Don Olmstead]

Comment on attachment 347080 [details]
Patch

Informal review is r+. This issue was found within a run of ARES6 using UBSan. This will prevent the undefined behavior.

[Mark Lam]

Comment on attachment 347080 [details]
Patch

r=me

[Yusuke Suzuki]

(In reply to Don Olmstead from comment #2)
> Comment on attachment 347080 [details]
> Patch
> 
> Informal review is r+. This issue was found within a run of ARES6 using
> UBSan. This will prevent the undefined behavior.

Yeah, this is nice.

(In reply to Mark Lam from comment #3)
> Comment on attachment 347080 [details]
> Patch
> 
> r=me

Thanks :)

[Yusuke Suzuki]

Committed r234852: <https://trac.webkit.org/changeset/234852>

[Radar WebKit Bug Importer]

<rdar://problem/43291961>

[WebKit Commit Bot]

Re-opened since this is blocked by bug 188736

[Darin Adler]

Comment on attachment 347080 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=347080&action=review

> Source/JavaScriptCore/assembler/MacroAssembler.h:1298
> +        // Generate the seed in [0, widthInBits). We should not generate widthInBits
> +        // since it leads to `<< widthInBits`, which is an undefined behavior.
> +        return random() % (widthInBits - 1);

I don’t understand the original bug, nor do I understand how this change will fix it.

The comment doesn’t agree with the code.

Let’s consider the case where widthInBits is 64. This code then does (u % 63), where u is a 32-bit unsigned integer. That operation should result in an integer in the range [0, 63). The existing code that does (u % 64) already should yield a number in the range [0, 64). The theory of the bug doesn’t make sense. The result of (u % 64) should not ever be 64.

Is there a bug here in the original code? How did we come to suspect there was?

[Darin Adler]

(In reply to Don Olmstead from comment #2)
> This issue was found within a run of ARES6 using
> UBSan. This will prevent the undefined behavior.

I’d like to know more about exactly what UBSan reported.

[Saam Barati]

Comment on attachment 347080 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=347080&action=review

>> Source/JavaScriptCore/assembler/MacroAssembler.h:1298
>> +        return random() % (widthInBits - 1);
> 
> I don’t understand the original bug, nor do I understand how this change will fix it.
> 
> The comment doesn’t agree with the code.
> 
> Let’s consider the case where widthInBits is 64. This code then does (u % 63), where u is a 32-bit unsigned integer. That operation should result in an integer in the range [0, 63). The existing code that does (u % 64) already should yield a number in the range [0, 64). The theory of the bug doesn’t make sense. The result of (u % 64) should not ever be 64.
> 
> Is there a bug here in the original code? How did we come to suspect there was?

Isn't the bug here just that a shift by a number >= 64 UB?

[Saam Barati]

Comment on attachment 347080 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=347080&action=review

>>> Source/JavaScriptCore/assembler/MacroAssembler.h:1298
>>> +        return random() % (widthInBits - 1);
>> 
>> I don’t understand the original bug, nor do I understand how this change will fix it.
>> 
>> The comment doesn’t agree with the code.
>> 
>> Let’s consider the case where widthInBits is 64. This code then does (u % 63), where u is a 32-bit unsigned integer. That operation should result in an integer in the range [0, 63). The existing code that does (u % 64) already should yield a number in the range [0, 64). The theory of the bug doesn’t make sense. The result of (u % 64) should not ever be 64.
>> 
>> Is there a bug here in the original code? How did we come to suspect there was?
> 
> Isn't the bug here just that a shift by a number >= 64 UB?

I just read the original code. I also don't see how there is a bug. Since we already were doing % 64, we'd end up with a number in the range of [0, 63].

[Darin Adler]

(In reply to Saam Barati from comment #11)
> I just read the original code. I also don't see how there is a bug. Since we
> already were doing % 64, we'd end up with a number in the range of [0, 63].

Yes, that matches my understanding.

Since UBSan complained, I would like to know what it complained about. If it complained about a shift of 64, then I would like to know the details because the results of a % 64 should never be 64.

[Yusuke Suzuki]

Comment on attachment 347080 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=347080&action=review

>>>> Source/JavaScriptCore/assembler/MacroAssembler.h:1298
>>>> +        return random() % (widthInBits - 1);
>>> 
>>> I don’t understand the original bug, nor do I understand how this change will fix it.
>>> 
>>> The comment doesn’t agree with the code.
>>> 
>>> Let’s consider the case where widthInBits is 64. This code then does (u % 63), where u is a 32-bit unsigned integer. That operation should result in an integer in the range [0, 63). The existing code that does (u % 64) already should yield a number in the range [0, 64). The theory of the bug doesn’t make sense. The result of (u % 64) should not ever be 64.
>>> 
>>> Is there a bug here in the original code? How did we come to suspect there was?
>> 
>> Isn't the bug here just that a shift by a number >= 64 UB?
> 
> I just read the original code. I also don't see how there is a bug. Since we already were doing % 64, we'd end up with a number in the range of [0, 63].

Yeah, the problem is, >> 64 AND << 64 are both undefined behavior.
https://wiki.sei.cmu.edu/confluence/display/c/INT34-C.+Do+not+shift+an+expression+by+a+negative+number+of+bits+or+by+greater+than+or+equal+to+the+number+of+bits+that+exist+in+the+operand
We should generate a seed [1, 63] to make `value = (value << rotation) | (value >> (sizeof(void*) * 8 - rotation));` safe.

[Yusuke Suzuki]

Comment on attachment 347080 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=347080&action=review

>>>>> Source/JavaScriptCore/assembler/MacroAssembler.h:1298
>>>>> +        return random() % (widthInBits - 1);
>>>> 
>>>> I don’t understand the original bug, nor do I understand how this change will fix it.
>>>> 
>>>> The comment doesn’t agree with the code.
>>>> 
>>>> Let’s consider the case where widthInBits is 64. This code then does (u % 63), where u is a 32-bit unsigned integer. That operation should result in an integer in the range [0, 63). The existing code that does (u % 64) already should yield a number in the range [0, 64). The theory of the bug doesn’t make sense. The result of (u % 64) should not ever be 64.
>>>> 
>>>> Is there a bug here in the original code? How did we come to suspect there was?
>>> 
>>> Isn't the bug here just that a shift by a number >= 64 UB?
>> 
>> I just read the original code. I also don't see how there is a bug. Since we already were doing % 64, we'd end up with a number in the range of [0, 63].
> 
> Yeah, the problem is, >> 64 AND << 64 are both undefined behavior.
> https://wiki.sei.cmu.edu/confluence/display/c/INT34-C.+Do+not+shift+an+expression+by+a+negative+number+of+bits+or+by+greater+than+or+equal+to+the+number+of+bits+that+exist+in+the+operand
> We should generate a seed [1, 63] to make `value = (value << rotation) | (value >> (sizeof(void*) * 8 - rotation));` safe.

The first fix was wrong, since it does not produce 64 without this patch. I thought the UB is caused by `value << 64`. But in fact, it is caused by `value >> (sizeof(void*) * 8 - rotation)` part if `rotation` is 0.
I'll upload a patch, which generates a seed within [1, 63].

[Yusuke Suzuki]

Created attachment 347474 [details]
Patch

[EWS Watchlist]

Comment on attachment 347474 [details]
Patch

Attachment 347474 [details] did not pass win-ews (win):
Output: https://webkit-queues.webkit.org/results/8913070

New failing tests:
http/tests/security/contentSecurityPolicy/video-with-https-url-allowed-by-csp-media-src-star.html

[EWS Watchlist]

Created attachment 347478 [details]
Archive of layout-test-results from ews206 for win-future

The attached test failures were seen while running run-webkit-tests on the win-ews.
Bot: ews206  Port: win-future  Platform: CYGWIN_NT-6.1-2.9.0-0.318-5-3-x86_64-64bit

[Yusuke Suzuki]

Committed r235160: <https://trac.webkit.org/changeset/235160>