llvm dev - Sep 2019 - Side-channel resistant values

Hi Chandler,

The data-invariant feature sounds great but what about the general case? When
performance tuning code, people sometimes need the ability to reliably generate
CMOV, and right now the best advice is either “use inline assembly” or “keep
refactoring until CMOV is emited” (and hope that future compilers continue to
generate CMOV).

Given that a patch already exists to reliably generate CMOV, are there any good
arguments against adding the feature?

Dave

> On Sep 12, 2019, at 10:21 PM, Chandler Carruth <chandlerc at
google.com> wrote:
> 
> On Thu, Sep 12, 2019 at 9:18 AM Finkel, Hal J. via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> On 9/12/19 5:06 AM, David Zarzycki via llvm-dev wrote:
>> I think adding a builtin to force CMOV or similar instructions on other
architectures is long overdue. It’s generally useful, even if one isn’t
mitigating speculative execution.
> 
> I believe that you can currently get this effect using
__builtin_unpredictable in Clang. __builtin_unpredictable wasn't added for
this purpose, and it's a hint not a forced behavior, but I believe that it
causes the backend to prefer cmov to branches during lowering.
> 
> I want to strongly advise against relying on this for anything to do with
cryptography. There are a lot of optimizations that I think will undo this....
> 
> Sadly, I don't think we have any builtins that I think are reliable in
this way. I agree this is a critically important thing, but it isn't as
simple as exposing cmov IMO.
> 
> +Matthew Riley <mailto:mattdr at google.com> on my team is actually
hoping to start working on getting a real data-invariant programming model
moving for C++ and part of that will involve adding support to LLVM as well, so
I suspect he'd be interested in this topic as well. Not sure what the
timelines on any of our lpans are at this point though, so can't really
promise much.
> 
> For now, I'd really suggest using the techniques used by BoringSSL and
OpenSSL. Sadly, these predominantly rely on assembly. They do have some
constructs to use C/C++ code and ensure it remains data-invariant, but it
isn't because the constructs are actually reliable. Instead, they have
testing infrastructure that they continually run and that checks the specific
instruction stream produced by the compiler. Given the current state, that's
about the only reliable approach I know of.
> 
> -Chandler
> 
>  
>  -Hal
> 
> 
> 
>> 
>>> On Sep 12, 2019, at 12:30 PM, Daan Sprenkels via llvm-dev
<llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>
wrote:
>>> 
>>> PS. Perhaps, would there be interest to add such a feature to LLVM?
>>> I found this repository on GitHub[2], adding a
`__builtin_ct_choose`
>>> intrinsic to clang. But as far as I know, this has never been
upstreamed.
>>> 
>>> [1]: Chandler Carruth described this trick at CppCon15:
>>> <https://youtu.be/nXaxk27zwlk?t=2472
<https://youtu.be/nXaxk27zwlk?t=2472>>. See it in practice:
>>> <https://godbolt.org/z/UMPeku
<https://godbolt.org/z/UMPeku>>
>>> [2]: <https://github.com/lmrs2/ct_choose
<https://github.com/lmrs2/ct_choose>>,
>>>
<https://github.com/lmrs2/llvm/commit/8f9a4d952100ae03d06f10aee237bf8b3331da89
<https://github.com/lmrs2/llvm/commit/8f9a4d952100ae03d06f10aee237bf8b3331da89>>.
>>> Later published at S&P18.
>> 
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> -- 
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190913/517e5b8b/attachment.html>

On Fri, Sep 13, 2019 at 1:33 AM David Zarzycki via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi Chandler,
>
> The data-invariant feature sounds great but what about the general case?
> When performance tuning code, people sometimes need the ability to reliably
> generate CMOV, and right now the best advice is either “use inline
> assembly” or “keep refactoring until CMOV is emited” (and hope that future
> compilers continue to generate CMOV).
>
> Given that a patch already exists to reliably generate CMOV, are there any
> good arguments against adding the feature?
>
For *performance* tuning, the builtin that Hal mentioned is IMO the correct
design.

Is there some reason why it doesn't work?
>
> Dave
>
>
> On Sep 12, 2019, at 10:21 PM, Chandler Carruth <chandlerc at
google.com>
> wrote:
>
> On Thu, Sep 12, 2019 at 9:18 AM Finkel, Hal J. via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> On 9/12/19 5:06 AM, David Zarzycki via llvm-dev wrote:
>>
>> I think adding a builtin to force CMOV or similar instructions on other
>> architectures is long overdue. It’s generally useful, even if one isn’t
>> mitigating speculative execution.
>>
>>
>> I believe that you can currently get this effect using
>> __builtin_unpredictable in Clang. __builtin_unpredictable wasn't
added for
>> this purpose, and it's a hint not a forced behavior, but I believe
that it
>> causes the backend to prefer cmov to branches during lowering.
>>
> I want to strongly advise against relying on this for anything to do with
> cryptography. There are a lot of optimizations that I think will undo
> this....
>
> Sadly, I don't think we have any builtins that I think are reliable in
> this way. I agree this is a critically important thing, but it isn't as
> simple as exposing cmov IMO.
>
> +Matthew Riley <mattdr at google.com> on my team is actually hoping
to start
> working on getting a real data-invariant programming model moving for C++
> and part of that will involve adding support to LLVM as well, so I suspect
> he'd be interested in this topic as well. Not sure what the timelines
on
> any of our lpans are at this point though, so can't really promise
much.
>
> For now, I'd really suggest using the techniques used by BoringSSL and
> OpenSSL. Sadly, these predominantly rely on assembly. They do have some
> constructs to use C/C++ code and ensure it remains data-invariant, but it
> isn't because the constructs are actually reliable. Instead, they have
> testing infrastructure that they continually run and that checks the
> specific instruction stream produced by the compiler. Given the current
> state, that's about the only reliable approach I know of.
>
> -Chandler
>
>
>
>>  -Hal
>>
>>
>>
>> On Sep 12, 2019, at 12:30 PM, Daan Sprenkels via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>> PS. Perhaps, would there be interest to add such a feature to LLVM?
>> I found this repository on GitHub[2], adding a `__builtin_ct_choose`
>> intrinsic to clang. But as far as I know, this has never been
upstreamed.
>>
>> [1]: Chandler Carruth described this trick at CppCon15:
>> <https://youtu.be/nXaxk27zwlk?t=2472>. See it in practice:
>> <https://godbolt.org/z/UMPeku>
>> [2]: <https://github.com/lmrs2/ct_choose>,
>> <
>>
https://github.com/lmrs2/llvm/commit/8f9a4d952100ae03d06f10aee237bf8b3331da89
>> >.
>> Later published at S&P18.
>>
>>
>>
>> _______________________________________________
>> LLVM Developers mailing listllvm-dev at
lists.llvm.orghttps://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>> --
>> Hal Finkel
>> Lead, Compiler Technology and Programming Languages
>> Leadership Computing Facility
>> Argonne National Laboratory
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190913/66d364c1/attachment.html>

> On Sep 13, 2019, at 10:45 AM, Chandler Carruth <chandlerc at
gmail.com> wrote:
> 
> On Fri, Sep 13, 2019 at 1:33 AM David Zarzycki via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> Hi Chandler,
> 
> The data-invariant feature sounds great but what about the general case?
When performance tuning code, people sometimes need the ability to reliably
generate CMOV, and right now the best advice is either “use inline assembly” or
“keep refactoring until CMOV is emited” (and hope that future compilers continue
to generate CMOV).
> 
> Given that a patch already exists to reliably generate CMOV, are there any
good arguments against adding the feature?
> 
> For *performance* tuning, the builtin that Hal mentioned is IMO the correct
design.
> 
> Is there some reason why it doesn't work?
I wasn’t aware of __builtin_unpredictable() until now and I haven’t debugged why
it doesn’t work, but here are a couple examples, one using the ternary operator
and one using a switch statement:

https://godbolt.org/z/S46I_q <https://godbolt.org/z/S46I_q>

Dave
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190913/88b2e14f/attachment.html>