This is an archive of the discontinued LLVM Phabricator instance.

Adding diversity for security (llvm)
AbandonedPublic

Authored by yln on Oct 1 2013, 3:13 PM.

Details

Reviewers
ahomescu
rinon
Summary

This patch was split into multiple, smaller patches (see dependencies).
clang parts: D3391, D3393, D3395

Old (outdated) summary:
Adds the capability to randomly insert NOPs, permuting the code layout, as well as the option to randomize scheduling decisions. Includes an OpenSSL-linked RNG to provide secure random number generation.

Diff Detail

Event Timeline

rinon updated this revision to Unknown Object (????).Oct 1 2013, 4:56 PM
  • Removed LLVM_ENABLE_RNG setting.
  • Fixing debug outputs
  • Various formatting to comply with coding style
alexr added a comment.Oct 2 2013, 6:34 AM

I'm not a crypto geek but... I think the choices of seeds need to be explained in the comments.

For example, the result of malloced memory is likely to be just zeros on some platforms and the addresses of command line argument pointers is likely to be constant between runs.

Alex

On Oct 1, 2013, at 3:13 PM, Stephen Crane <sjcrane@uci.edu> wrote:

Adds the capability to randomly insert NOPs, permuting the code layout, as well as the option to randomize scheduling decisions. Includes an OpenSSL-linked RNG to provide secure random number generation.

http://llvm-reviews.chandlerc.com/D1802

Files:
CMakeLists.txt
Makefile.config.in
autoconf/configure.ac
cmake/config-ix.cmake
cmake/modules/LLVM-Config.cmake
configure
include/llvm/CodeGen/CommandFlags.h
include/llvm/CodeGen/MachineInstr.h
include/llvm/Config/config.h.cmake
include/llvm/Config/config.h.in
include/llvm/MC/MCRegisterInfo.h
include/llvm/Support/RandomNumberGenerator.h
include/llvm/Target/TargetOptions.h
lib/CodeGen/LLVMBuild.txt
lib/CodeGen/MachineBasicBlock.cpp
lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
lib/LTO/LTOCodeGenerator.cpp
lib/LTO/LTOModule.cpp
lib/Support/CMakeLists.txt
lib/Support/RandomNumberGenerator.cpp
lib/Target/X86/CMakeLists.txt
lib/Target/X86/NOPInsertion.cpp
lib/Target/X86/X86.h
lib/Target/X86/X86TargetMachine.cpp
test/CodeGen/X86/nop-insert-percentage.ll
test/CodeGen/X86/nop-insert.ll
test/CodeGen/X86/sched-rnd-test.ll
test/Makefile
test/lit.cfg
test/lit.site.cfg.in
tools/llc/llc.cpp
tools/opt/opt.cpp
<D1802.1.patch>


llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

rinon added a comment.Oct 2 2013, 11:16 AM

Discussion of the existing OpenSSL RNG and thread safety brings up another important point: The RNG needs to store state in some thread-local way. Should RNG state be stored in the LLVMContext? I didn't want to mess with LLVMContext without advice from someone who knows the multi-threading roadmap better. It doesn't seem to be the right place, but we need some way to guarantee that only one RNG will be initialized per-thread, rather than using the current static singleton.

rinon updated this revision to Unknown Object (????).Oct 8 2013, 12:32 AM

Thread safe and commented

  • Cleaned up coding style.
  • Removed unnecessary copy constructors for RNG
  • Made OpenSSL thread-safe
  • Reorganized RNGs.
  • Added virtual destructor.
  • Added comments to describe RNG construction.

I'm glad you were able to set up the OpenSSL locking. I have a few comments on the code; see below. My high-level comment about the algorithm is that it looks like this is not an exact implementation of of SP 800-90A; see my comments for some (not all) of the differences.

Also, someone familiar with the details of the X86 Target and other backend code should look at this, too, since I don't know much about the backend details.

include/llvm/Support/RandomNumberGenerator.h
17 ↗(On Diff #4727)

This should follow the style LLVM_SUPPORT_RANDOMNUMBERGENERATOR_H (see other files in include/llvm)

69 ↗(On Diff #4727)

Looks like the style here should be a semi-colon alone on a line. See, e.g., lib/CodeGen/MachineBasicBlock.cpp around the changes in this diff.

include/llvm/Target/TargetOptions.h
53–55 ↗(On Diff #4727)

It looks like this diff is missing at least one place that uses TargetOptions: in tools/lto/lto.cpp, there is a function lto_set_target_options that sets values in TargetOptions based on the command-line flags. Please change that too.

lib/Support/RandomNumberGenerator.cpp
77–80

You should probably note, then, that the entropy here depends almost entirely on the entropy in the seed, since the command-line arguments aren't going to have much, I assume. Do you have a sense of how many bits of entropy are needed here to make this construction secure in a given context?

From Table 3 in SP 800-90A, it looks like the minimum entropy required for the construction that uses a key derivation function is the required security strength.

91–92

80-char limit (here and in a couple other places). Maybe reformat with clang-format --style=LLVM ?

112

AFAICT from SP 800-90A, the initial key is supposed to be 0, and subsequent reseeding operations are supposed to use the existing key to generate a new one.

153–154

See the description of the CTR_DRBG algorithm on page 58-59 of NIST SP 800-90A: the randomness generation process also needs to call an update function to change the secret state, including the key, each time. This is step 6 of CTR_DRBG Generate Process.

Also, it looks like there is supposed to be a reseed count that forces reseeding after a certain interval. Table 3 in SP 800-90A gives the recommended number of iterations for a given security strength.

lib/Target/X86/NOPInsertion.cpp
103

!! on bool is unnecessary

tools/opt/opt.cpp
600–609 ↗(On Diff #4727)

I think something similar to this will have to be added to llvm-lto to support nop code generation there, too. Maybe instead of repeating the same snippet everywhere, you could make this a function in RandomNumberGenerator. Something like AddSeedData?

ahomescu added inline comments.Oct 10 2013, 4:02 PM
lib/Target/X86/NOPInsertion.cpp
103

This is supposed to be a bool->int cast (false->0, true->1). I think I might have been getting compilation errors without it, have to check...

rinon updated this revision to Unknown Object (????).Oct 11 2013, 10:34 AM

Rewrote the RNG somewhat to comply with CTR_DRBG. Generation now complies with the spec, although without reseeding. Since we need predictability and only have a single entropy source (command line flag), we cannot reseed with additional entropy.
Also added TargetOption updates in a few places where it got forgotton and fixed a bool cast.

rinon added inline comments.Oct 11 2013, 10:44 AM
lib/Support/RandomNumberGenerator.cpp
153–154

The existing RNG we were using was based on CTR_DRBG, but missing a few pieces which you very correctly point out. Thanks! I've tried to make it as complying as possible, without reseeding now.

tools/opt/opt.cpp
600–609 ↗(On Diff #4727)

I've added a function, but also removed this setting everywhere but clang. This "EntropyData" (now called more correctly SaltData) is only needed during a larger build so that every compilation can use the same seed, but still result in a different random stream. Clang now sets this SaltData based on input filenames, to make each invocation unique.

LGTM now, other than a minor comment fix. The crypto RNG implementation now looks to be a special case of CTR_DRBG. However, I'm new to LLVM, so someone other than me should still look at the code and approve it.

CC'ing Nadav as the owner of the X86 backend: Nadav, can you please look at this?

Thanks,

Tom

lib/Support/RandomNumberGenerator.cpp
141

This code depends on the fact that AES_BLOCK_SIZE divides SEEDLEN exactly. This is probably OK to assume, but it should be documented in a comment on the definition of SEEDLEN.

rinon updated this revision to Unknown Object (????).Oct 15 2013, 1:35 PM
  • Added a comment to note block size assumptions.
rinon updated this revision to Unknown Object (????).Oct 15 2013, 1:40 PM

Trying to convince arcanist to upload the correct diffs...

nadav added a comment.Oct 15 2013, 1:51 PM

Hi Stephen,

Thanks for submitting the patch. I have a few questions. It is not clear to me why you need cryptographically strong randomization at *compile* time. You absolutely do need this kind of randomization when distributing the binary, not when compiling it. To the best of my understanding in order to predict a safe jump location you need to read the binary data anyway, so using a strong crypto is not better than any pseudo random number generator.

Thanks,
Nadav

rinon updated this revision to Unknown Object (????).Oct 16 2013, 5:30 PM
  • Replaced OpenSSL AES RNG with an MD5 HMAC_DRBG RNG
  • Updating test cases for new RNG
  • Formatting and comments for the RNG
nadav added a comment.Oct 16 2013, 5:50 PM

Hi Stephen,

Why did you need to add a new NOP flag and the isInsertedNOP function ?

Thanks,
Nadav

ahomescu commandeered this revision.Jan 16 2014, 2:53 PM
ahomescu added a reviewer: rinon.
yln commandeered this revision.Jan 22 2014, 1:09 PM
yln added a reviewer: ahomescu.

Hello everyone!
A lot of time has passed since someone was actively pursuing this issue.
I will try to push this forward and incorporate any remarks you might have.

yln updated this revision to Unknown Object (????).Jan 22 2014, 1:20 PM

Nadav mentioned that we do not want to slow down users by adding a flag 'isInsertedNOP' to the MachineInst class and checking against it in the MachineBasicBlock::getFirstTerminator methods.

This update addresses this concern by simply not inserting NOPs between terminators (less secure, but simplest solution for now).

yln updated this revision to Unknown Object (????).Jan 23 2014, 3:08 PM

Move patch forward to ToT.

Was there ever consensus that we want to maintain this in LLVM? I just
looked back at the original thread on llvmdev, and it looked like basically:

  • A number of security folks having an inconclusive, wandering,

back-and-forth discussion about various security things that should have
been done on a security mailing list.

  • Lots of "this seems maybe interesting, but ..." with the "but ..." not

clearly addressed in any way. Often times the "but ..." was an alternative
approach that would be more maintainable, effective, and/or fit in better
with existing deployment processes.

  • No concrete use cases. Who is going to be deploying this? If nobody is

deploying, then how do we know it will be maintained? It seems like the
initial patch submitter has already jumped ship on this patch; doesn't
exactly inspire confidence.

It seems like basically nobody who participated in the original discussion
on llvmdev is participating in this patch review either. Especially the
people who had doubts don't seem to be participating; those doubts need to
be addressed.

Also, at the very least, adding the RNG should be split out into a separate
patch.

  • Sean Silva
jfb added a comment.Jan 27 2014, 11:24 AM

I discussed this change with the UCI folks offline: the PNaCl team is interested in their approach (binary diversity) And we'd like to help with the reviews to get this upstream into LLVM.

The current main point of contention seems to be the RNG. Now that LLVM is slowly moving to C++11 would it be acceptable to use one of <random>'s pseudo-random number generators, and use std::random_device when a random seed is needed? Chandler was asking folks to hold off on using C++11 features for the near future (to make sure the switchover is clean), and I'm not sure <random> is whitelisted, but I'd like to get the discussion going.

Once we settle the RNG issue we could commit the RNG's state as its own change, and handle NOP insertion in a different change?

jfb added a comment.Feb 28 2014, 7:15 PM

C++11 now seems to be OK with LLVM (see http://llvm-reviews.chandlerc.com/D2905). Could we start the discussion about using it for this patch instead of having a separate RNG?

Bikeshed *which* RNG to use, and how to use random_device and such to seed things, as well as being able to feed randomness for an external file (which Geremy suggested offline).

perl added a comment.Mar 1 2014, 2:23 PM

Thanks for getting back to us on that. Agree wholeheartedly that we should
use the C++11 RNG for now in the interest of landing the initial patch.
Stay tuned for an updated patch.

Best,
Per

I'm completely ignoring RNG, which should be a separate patch.

I don't think we should add a dependence from CodeGen to Instrumentation. Is that necessary?

RandomizeSchedule can be a separate patch from random nops. Doing this in the SelectionDAG scheduler may not be very effective because the MachineScheduler and PostRA scheduler can undo it. I think the right way to handle this is for the target to schedule a PostRA scheduling pass that just does the randomization.

There is currently an option, -misched-postra, that enables the MachineScheduler as a postRA pass. Alternatively, a target could schedule the pass itself using one of the TargetPassConfig hooks and calling:

addPass(&PostMachineSchedulerID);

Then the target can override TargetPassConfig::createPostMachineScheduler and instantiate a scheduler something like this:

return new ScheduleDAGMI(C, new PostRandomScheduler(C), /*IsPostRA=*/true);

Where PostRandomScheduler would be a MachineSchedStrategy implemented very similar to InstructionShuffler.

Alternatively, this can be done for all targets by adding an option that forces
PostMachineScheduler::createPostMachineScheduler to use the PostRandomScheduler.

I don't understand the nop insertion percentage math. Each instruction gets MaxNOPsPerInstruction rolls. If I allow 8 nops per instruction, then the chance an instruction does NOT have a nop is 1/256. I don't think you should retry after a failed roll--then the percentage would make sense.

Juergen Ributzka recently added MI level support for inserting variable sized x86 nops. You might want to look at that.

yln updated this revision to Unknown Object (????).Apr 13 2014, 8:27 PM

The updated replaces the custom RNG implementation with C++11 facilities.
Andrew Trick made good suggestions on how to improve the patch.
I will try to incorporate those (starting with splitting RNG - NOP insertion - schedule randomization int separate patches).

alexr added a comment.Apr 14 2014, 7:34 AM

Is this deterministic for multi-threaded builds?

Alex

yln added a comment.Apr 14 2014, 10:41 AM

You are referring to the fact that the RNG instance id is part of the seed, right?

Seeds[2] = InstanceID;

The initial patch had this so I left it in, but indeed this looks strange from the angle of reproducible builds.
I will remove it.

I was referring to the call to AtomicIncrement as a way to get a seed for each thread. The threads aren't guaranteed to enter that code in the same order, so there is no guarantee of determinism for a given seed.

Alex

yln added a comment.Apr 15 2014, 3:19 PM

Does anyone have an authoritative answer whether or not the C++11 <random> facilities are thread save?
The docs (http://en.cppreference.com/w/cpp/numeric/random) do not mention thread safety, so I assume they are not.

yln updated this revision to Unknown Object (????).Apr 15 2014, 7:16 PM

Do not include RNG instance ID in the seed value.

This enables reproducible builds in a multi-threaded environment.
It might also reduce security, but this is not our topmost concern
as we are not using a cryptographically secure RNG to start with.

yln updated this revision to Unknown Object (????).Apr 15 2014, 8:41 PM

Adapt tests after changing RNG seed.

yln added a comment.Apr 15 2014, 11:21 PM

This patch is now split into smaller, more manageable chunks.
Please subscribe if you are interested in participating, thanks.

yln abandoned this revision.Aug 15 2017, 4:07 PM