This is an archive of the discontinued LLVM Phabricator instance.

Fixed Noop insertion
Needs RevisionPublic

Authored by rinon on Jan 14 2015, 4:39 PM.

Details

Reviewers
jfb
Summary

Fixes build and test failures from r225908. Replaces std::uniform_real_distribution in Noop insertion.

std::uniform_real_distribution is not consistent across platforms. This
patch implements a simple integer unbiased random number range
distribution.

Original description:

A pass that adds random noops to X86 binaries to introduce diversity with the goal of increasing security against most return-oriented programming attacks.

Command line options:

-noop-insertion Enable noop insertion.
-noop-insertion-percentage=X
X% of assembly instructions will have a noop prepended (default: 50%, requires -noop-insertion)
-max-noops-per-instruction=X // Randomly generate X noops per instruction. ie. roll the dice X times with probability set above (default: 1). This doesn't guarantee X noop instructions.

In addition, the following 'quick switch' in clang enables basic diversity using default settings (currently: noop insertion and schedule randomization; it is intended to be extended in the future).

-fdiversify

Diff Detail

Event Timeline

rinon updated this revision to Diff 18192.Jan 14 2015, 4:39 PM
rinon retitled this revision from to Fixed Noop insertion.
rinon updated this object.
rinon edited the test plan for this revision. (Show Details)
rinon updated this object.Jan 14 2015, 4:40 PM
rinon edited the test plan for this revision. (Show Details)
rinon added a reviewer: jfb.
rinon added subscribers: ahomescu, perl, Unknown Object (MLST).
rinon updated this revision to Diff 18194.Jan 14 2015, 4:45 PM
  • Replace uint_fast64_t with result_type
rinon added inline comments.Jan 14 2015, 4:46 PM
lib/Support/RandomNumberGenerator.cpp
57

This seems like a strange way to break this line, but it's what clang-format seems to think is right...

rinon added a comment.Jan 15 2015, 3:54 PM

Verified that tests pass on Linux now (Ubuntu 14.04, current master). Having completely removed the dependence on the Distribution member, there shouldn't be any build problems on Windows. Just needs someone to look over the new ranged RNG operator(Max) function.

jfb added inline comments.Jan 19 2015, 8:22 PM
lib/Support/RandomNumberGenerator.cpp
69

Do you think you could create a utility that effectively meets the uniform_int_distribution requirements of the standard, while offering an implementation that doesn't change from one standard library to another? This would make it easier to convince readers of the code that the RNG+distribution is actually doing what they expect.

The obvious fix is to simply include libc++'s implementation since the license is the same:

template<class _IntType>
template<class _URNG>
typename uniform_int_distribution<_IntType>::result_type
uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
{
    typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
                                            uint32_t, uint64_t>::type _UIntType;
    const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1);
    if (_Rp == 1)
        return __p.a();
    const size_t _Dt = numeric_limits<_UIntType>::digits;
    typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
    if (_Rp == 0)
        return static_cast<result_type>(_Eng(__g, _Dt)());
    size_t __w = _Dt - __clz(_Rp) - 1;
    if ((_Rp & (_UIntType(~0) >> (_Dt - __w))) != 0)
        ++__w;
    _Eng __e(__g, __w);
    _UIntType __u;
    do
    {
        __u = __e();
    } while (__u >= _Rp);
    return static_cast<result_type>(__u + __p.a());
}

The duplication is unfortunate, but generating the same sequence independently of stdlib implementation kind of makes duplication a requirement.

rinon added inline comments.Jan 26 2015, 4:02 PM
lib/Support/RandomNumberGenerator.cpp
69

Sorry, I missed your comment. Somehow it slipped by my email.

Yes, I think we could use libc++'s implementation (from the spec it seems that independent_bits_engine should be stable). However, I think the only thing we really gain with this is efficiency. The libc++ implementation is faster, at the expense of readability and code size.

I'm happy to integrate this optimized implementation into the current RNG class, but I'd be adverse to creating a completely duplicate uniform_int_distribution utility class. That seems like a lot of code duplication for a simple feature.

jfb added inline comments.Jan 26 2015, 6:02 PM
lib/Support/RandomNumberGenerator.cpp
69

My main concern is convincing myself that your implementation indeed has the advertised uniform distribution. When I read the code I don't find this obvious, and there's no unit test for this function to check the distribution is indeed uniform.

It's indeed even less obvious from the libc++ implementation, but having the same implementation means that we can rely on libc++'s {test suite / users / following the spec} to make sure it's correct. AFAICT libc++ doesn't have a unit test on its distribution either...

rinon added inline comments.Jan 28 2015, 4:48 PM
lib/Support/RandomNumberGenerator.cpp
69

On closer inspection, we can't use the libc++ implementation. It depends on independent_bits_engine taking the number of bits as a constructor parameter, not as a template parameter as the standard dictates. Since the range should be a parameter, this makes life difficult.

I'll see if I can't find a solid reference or implementation so we don't need to worry about this bit. It really shouldn't be bad.

rinon added inline comments.Feb 18 2015, 2:19 PM
lib/Support/RandomNumberGenerator.cpp
69

If you want a "more-tested" implementation, how would you feel about using OpenBSD's arc4random_uniform implementation (http://cvsweb.openbsd.org/cgi-bin/cvsweb/~checkout~/src/lib/libc/crypt/arc4random_uniform.c?rev=1.1&content-type=text/plain)? It's BSD licensed and a super simple uniform distribution.

jfb added inline comments.Feb 18 2015, 2:28 PM
lib/Support/RandomNumberGenerator.cpp
69

I'd make sure it's initialized first :-p

But sure, as long as the implementation is license-compatible and well tested then that sounds acceptable.

rinon updated this revision to Diff 20226.Feb 18 2015, 2:57 PM
  • Replace uniform random implementation with OpenBSD's
rinon added inline comments.Feb 18 2015, 3:00 PM
lib/Support/RandomNumberGenerator.cpp
56

There is precedent for using OpenBSD libc code in LLVM: see lib/Support/regstrlcpy.c.

joerg added a subscriber: joerg.Feb 18 2015, 3:42 PM

Please don't mix in completely unrelated changes to the support library. Start a separate review for those.

jfb requested changes to this revision.May 7 2018, 10:17 PM

Is there interest in moving program diversification efforts forward, or should we close this work and rely on others to take it on?

This revision now requires changes to proceed.May 7 2018, 10:17 PM
rinon added a comment.May 9 2018, 2:28 PM

If there's no external interest that I am unaware of, I think we should close this. I've still been working in this space. However due to deployment constraints, load-time rather than compile-time diversity is far more practical and interesting to everyone I've talked to. Fuzz testing micro-architectures may still be an exception to this, but I don't know of anyone who wants to use these type of features for that currently.

That said, if anyone does still want this, I'm happening to fix up and modernize these patches.