Adding diversity for security (llvm)

[yln]

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.

[rinon]

• Removed LLVM_ENABLE_RNG setting.
• Fixing debug outputs
• Various formatting to comply with coding style

[alexr]

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 <[e-mail]> 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
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[rinon]

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]

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.

[tmroeder]

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]

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]

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]

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.

[tmroeder]

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]

• Added a comment to note block size assumptions.

[rinon]

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

[nadav]

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]

• Replaced OpenSSL AES RNG with an MD5 HMAC_DRBG RNG
• Updating test cases for new RNG
• Formatting and comments for the RNG

[nadav]

Hi Stephen,

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

Thanks,
Nadav

[yln]

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]

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]

Move patch forward to ToT.

[silvas]

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]

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]

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]

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

[atrick]

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]

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]

Is this deterministic for multi-threaded builds?

Alex

[yln]

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.

[alexr]

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]

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]

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]

Adapt tests after changing RNG seed.

[yln]

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

lib/LTO/LTOCodeGenerator.cpp

void LTOCodeGenerator::setTargetOptions(TargetOptions options) {
   Options.NoZerosInBSS = options.NoZerosInBSS;
   Options.GuaranteedTailCallOpt = options.GuaranteedTailCallOpt;
   Options.DisableTailCalls = options.DisableTailCalls;
   Options.StackAlignmentOverride = options.StackAlignmentOverride;
   Options.TrapFuncName = options.TrapFuncName;
   Options.PositionIndependentExecutable = options.PositionIndependentExecutable;
   Options.EnableSegmentedStacks = options.EnableSegmentedStacks;
   Options.UseInitArray = options.UseInitArray;
+  Options.NOPInsertion = options.NOPInsertion;
 }
 
 void LTOCodeGenerator::setDebugInfo(lto_debug_model debug) {
   switch (debug) {
   case LTO_DEBUG_MODEL_NONE:
     EmitDwarfDebugInfo = false;
     return;
 

lib/Support/RandomNumberGenerator.cpp

 static ManagedStatic<sys::SmartMutex<true> > InstanceCountMutex;
 
 #define AES_KEY_LENGTH 16 // bytes
 #define AES_BLOCK_SIZE 16
 #define PBKDF_ITERATIONS 1000
 #define SEEDLEN 32
 
 /// This RNG is an implementation of the standard NIST SP 800-90A
 /// CTR_DRBG random number generator, with AES128 as the block
 /// cipher. In addition, the initial seed and an additional salt from
 /// the list of command-line arguments are ran through a standard
 /// PBKDF2 key stretching algorithm to produce enough bits to
 /// initialize the RNG.
 ///
 /// Since entropy is provided only by the (hopefully random, up to the
 /// build system) 64-bit seed, we therefore must conclude that the RNG
 /// has only 64 bits of entropy, rather than the 128 that AES-128
 /// could provide.
 ///
 /// Note: We do NOT perform reseeding due to constrained entropy
 /// data. Since we need reproducibility, we can only use the given
 /// 64-bit seed as entropy, and therefore have no additional entropy
 /// to reseed with. This means that we assume less than 2^48 calls to
 /// Random(). However, it is unlikely that compromise of the RNG is
 /// even possible in practice since the actual random stream is not
 /// exposed to an attacker.
 class OpenSSLRandomNumberGenerator : public RandomNumberGenerator {
 private:
   unsigned char Key[AES_KEY_LENGTH];
   unsigned char V[AES_BLOCK_SIZE];
   AES_KEY AESKey;
 
   // Noncopyable.
   OpenSSLRandomNumberGenerator(
       const OpenSSLRandomNumberGenerator &other) LLVM_DELETED_FUNCTION;
   OpenSSLRandomNumberGenerator &
   operator=(const OpenSSLRandomNumberGenerator &other) LLVM_DELETED_FUNCTION;
 
   // Set up OpenSSL to be thread-safe
   void InitializeGlobals() {
     // create enough mutexes for OpenSSL
     // CRYPTO_num_locks() returns the maximum number of locks which
     // will be required
     OpenSSLMutexes = new sys::SmartMutex<true>[CRYPTO_num_locks()];
 
     // set up callbacks which OpenSSL needs to provide thread-safety
     CRYPTO_set_locking_callback(OpenSSLLockingFunction);
     CRYPTO_set_id_callback(OpenSSLThreadIDFunction);
   }
 
   void Seed(StringRef Salt, uint64_t Seed) {
     DEBUG(dbgs() << "Re-Seeding AES RNG context from salt and seed\n");
     DEBUG(dbgs() << "Salt: " << Salt << "\n");
     DEBUG(dbgs() << "Seed: " << Seed << "\n");
 
     unsigned char SeedMaterial[SEEDLEN];
 
     // Hash salt with seed into SeedBuffer to get more bytes to
     // initialize the AES construction
     PKCS5_PBKDF2_HMAC_SHA1((char *)&Seed, sizeof(Seed),
                            (unsigned char *)Salt.data(), Salt.size(),
                            PBKDF_ITERATIONS, SEEDLEN,
                            SeedMaterial);
 
     memset(Key, 0, AES_KEY_LENGTH);
     memset(V, 0, AES_BLOCK_SIZE);
-    AES_set_encrypt_key((unsigned char *)&Key, AES_KEY_LENGTH * 8, &AESKey);
+    AES_set_encrypt_key(Key, AES_KEY_LENGTH * 8, &AESKey);
     CTR_DRBG_Update(SeedMaterial);
   }
 
   void CTR_DRBG_Update(unsigned char *Data = NULL) {
     unsigned char Temp[SEEDLEN];
     for (unsigned i = 0; i < SEEDLEN / AES_BLOCK_SIZE; ++i) {
       // Increment 128bit V
       uint64_t *V0 = (uint64_t *)(V), *V1 = (uint64_t *)(V + 8);
       *V0 += 1;
       if (*V0 == 0)
         *V1 += 1;
 
       AES_encrypt(V, Temp + i * AES_BLOCK_SIZE, &AESKey);
     }
 
     // If data is null, assume it is initialized to all zeros
     if (Data != NULL) {
       for (unsigned i = 0; i < SEEDLEN; ++i) {
         Temp[i] ^= Data[i];
       }
     }
 
     memcpy(Key, Temp, AES_KEY_LENGTH);
     memcpy(V, Temp + AES_KEY_LENGTH, AES_BLOCK_SIZE);
     AES_set_encrypt_key(Key, AES_KEY_LENGTH * 8, &AESKey);
   }
 

lib/Target/X86/NOPInsertion.cpp

for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
       for (unsigned int i = 0; i < MaxNOPsPerInstruction; i++) {
         unsigned int Roll = RandomNumberGenerator::Generator()->Random(100);
         if (Roll >= NOPInsertionPercentage)
           continue;
 
         int NOPCode = RandomNumberGenerator::Generator()->Random(MAX_NOPS);
 
         MachineInstr *NewMI = NULL;
-        unsigned reg = nopRegs[NOPCode][!!is64Bit];
+        unsigned reg = nopRegs[NOPCode][is64Bit];
         switch (NOPCode) {
         case NOP:
           NewMI = BuildMI(*BB, I, I->getDebugLoc(), TII->get(X86::NOOP));
           break;
         case MOV_EBP:
         case MOV_ESP: {
           unsigned opc = is64Bit ? X86::MOV64rr : X86::MOV32rr;
           NewMI = BuildMI(*BB, I, I->getDebugLoc(), TII->get(opc), reg)

tools/llvm-lto/llvm-lto.cpp

int main(int argc, char **argv) {
   Options.NoZerosInBSS = DontPlaceZerosInBSS;
   Options.GuaranteedTailCallOpt = EnableGuaranteedTailCallOpt;
   Options.DisableTailCalls = DisableTailCalls;
   Options.StackAlignmentOverride = OverrideStackAlignment;
   Options.TrapFuncName = TrapFuncName;
   Options.PositionIndependentExecutable = EnablePIE;
   Options.EnableSegmentedStacks = SegmentedStacks;
   Options.UseInitArray = UseInitArray;
+  Options.NOPInsertion = NOPInsertion;
 
   unsigned BaseArg = 0;
 
   LTOCodeGenerator CodeGen;
 
   CodeGen.setCodePICModel(LTO_CODEGEN_PIC_MODEL_DYNAMIC);
   CodeGen.setDebugInfo(LTO_DEBUG_MODEL_DWARF);
   CodeGen.setTargetOptions(Options);