Random Number Generator (clang)

[yln]

Summary

Provides an abstraction for a random number generator (RNG) that produces a stream of pseudo-random numbers.
The current implementation uses C++11 facilities and is therefore not cryptographically secure.

The RNG is salted with the text of the current command line invocation.
In addition, a user may specify a seed (reproducible builds).

In clang, the seed can be set via

-frandom-seed=X

In the back end, the seed can be set via

-rng-seed=X

This is the clang part of the patch.
LLVM part: D3390

[yln]

Remove unused variable, minimize diff.

[yln]

Remove unused variable, minimize diff. (fixed context)

[jfb]

lib/Frontend/CompilerInvocation.cpp

1682

std::accumulate instead of the loop.

I think you should also add a comment that explains why this is a desirable salt value compared to, say, timestamp. It gives a predictable outcome per clang invocation from one local build to another, but different developers will get different results if they had a different path for the code, and different clang invocations get different salt (e.g. each TU will have different salt).

Is it worth throwing in other things that differ between developers, but are the same from one build to the next for a particular developer? Say the moral equivalent of /proc/cpuinfo, some OS information, and/or the git hash of the LLVM master that LLVM was built from?

[ahomescu]

lib/Frontend/CompilerInvocation.cpp

1682

We want the build to be repeatable over time and across machines. If two developers use the same seed, same source tree and same build options, they should get exactly the same binary. On a per-project basis, you can use the timestamp to build the seed, or any of the other things you mentioned.

[jfb]

lib/Frontend/CompilerInvocation.cpp

1682

Using getAllArgValues doesn't meet what you want then: it'll contain pathes, and those will be different between machines.

The LLVM git source hash would meet this requirement.

[yln]

Refine construction of salt string.

[yln]

lib/Frontend/CompilerInvocation.cpp

1678

@ahomescu
Are we sure that we want repeatable builds across machines?

@jfb
"The LLVM git source hash would meet this requirement."
I am not sure I understand, can you elaborate?

[jfb]

lib/Frontend/CompilerInvocation.cpp

1678

I do think you want repeatable builds across machines, otherwise one developer can't ask another developer to reproduce a bug.

For git hash I mean something like baking the result of `git rev-parse HEAD` into the build, maybe by passing it in from the command line through -DFOO=${HASH) or something.
I'm not sure git is LLVM's source of truth though, SVN still is, so the rev number would be the salt then, until that changes.

[rinon]

lib/Frontend/CompilerInvocation.cpp

1678

Producing different random streams per- compilation unit (file) is the entire point of the salt. We originally determined that if a single file in a build leaks to the attacker, the attacker can reproduce the random stream and thus reproduce any other part of a larger build process (make, etc.). Thus, we want a unique random stream for each file.

I agree that getAllArgValues is not ideal for this, since it could contain arbitrary paths. Is there some way we can filter this out? Even simply using the input filename (without the full path) could work here. A previous version I saw filtered out the -o filepath flag, but I'm not sure this is necessarily sufficient.

I'm also not sure that adding a llvm version-specific salt is helpful here. I can see how changing other optimization decisions would affect the compiled results, but current best-practices dictate matching compiler versions already if you want to reproduce a build.

[jfb]

lib/Frontend/CompilerInvocation.cpp

1678

git rev-parse HEAD would give you a salt that identifies the exact LLVM source base that the compiler was based on. I think it's a good thing to throw in, but it indeed doesn't give a different stream for each compilation unit. Throwing it in means that you will only get a deterministic build if both developers have the exact same LLVM source.

On the per-compilation unit side, maybe you can iterate through the command line options but only pick out non-string values? Even then I'm not sure that's good enough since the build architecture could be an enum. Thinking about it, I don't think the command line is good...

Here's another line of thought: you're trying to have unique salt per compilation unit, which is equivalent to an LLVM Module. Could you salt at Module creation time? There are things like triple, datalayout that aren't Module-specific but useful, and the Module does have a ModuleIdentifier which should be unique. You could also iterate through function names and global names and accumulate those, but you'd have to do so in a stable way.

The one issue with this idea is that it prevents one Module from kicking off multiple threads (since the RNG would be shared if that were the case) but that's what LLVM currently imposes, you'd merely be following this.

Do you think setting the salt from Module would work?

[rinon]

lib/Frontend/CompilerInvocation.cpp

1678

@ahomescu and I were just discussing this yesterday, in fact. Yes I think this seems like a good idea. It looks to me like the ModuleID should work great as a seed. @ahomescu, @yln what do you think? I think we should go ahead and rip out the current salting and just use getModuleIdentifier().

[yln]

lib/Frontend/CompilerInvocation.cpp

1678

ModuleID seems to be the simplest thing that fits our needs.
Maybe other reviewers can comment on jfb's/rinon's one RNG per module (or context) suggestion.

[ahomescu]

lib/Frontend/CompilerInvocation.cpp

1678

I just checked to see what ModuleID is when compiling with clang.
$ clang -O2 -emit-llvm -S -o test2.ll /home/andrei/temp/cpp/test2.c
gives ModuleID = "/home/andrei/temp/cpp/test2.c", AKA the full path.
Using the ModuleID is still not good enough.
We should strip the path from the ID, and keep only the base file name.

[rinon]

lib/Frontend/CompilerInvocation.cpp

1678

After more offline discussions, I think we've come up with a workable proposal. Hopefully this will fit well into the rest of the llvm infrastructure.

Since an LLVMContext is thread-specific, we could just create an RNG instance for the context when it is constructed. Then add a bit of code to LLVMContext::addModule to resalt the RNG with each added ModuleID as follows in pseudo-code:

LLVMContext() {
  rng = new RandomNumberGenerator(seed);
}

LLVMContext::addModule(M) {
  rng->seed(rng->Random() + M.getModuleIdentifier());
}

There is a small difficulty with ModuleID though. This appears to sometimes be the full path the source file, so we will need to grab just the filename out of it, instead of the full path.

Will adding an RNG instance to the context be acceptable to the llvm community at large? I've tried to stay away from adding anything to core classes, but I think this really makes the most sense.

[jfb]

lib/Frontend/CompilerInvocation.cpp

1678

Is it also useful to mix other things into the salt, like datalayout? It's not file specific, but does provide more than just the file name.

1678

+1 on just using basename. Note that filename isn't unique, but I don't think we can reliably determine the "full path of a file from the project's root directory", so I think it's the best we have to work with.

[rinon]

lib/Frontend/CompilerInvocation.cpp

1678

I'm not sure it is necessary to add any other salts. We are relying on the seed to have sufficient entropy to be unpredictable. If we want to make any other aspects of the build result in differing binaries, then more salting would be required. However, as is I don't see a use case for this offhand. Maybe you've got one that we haven't considered?

[jfb]

lib/Frontend/CompilerInvocation.cpp

1678

Sounds good to me then. I can't think of one, but figured it would be better to ask.

[yln]

Refactor RNG to be non-static and make it available via LLVMContext.

[jfb]

Trying to wrap things up, this change LGTM if the other changes aren't contentious with other reviewers.

include/clang/Driver/Options.td

 def fpch_preprocess : Flag<["-"], "fpch-preprocess">, Group<f_Group>;
 def fpic : Flag<["-"], "fpic">, Group<f_Group>;
 def fno_pic : Flag<["-"], "fno-pic">, Group<f_Group>;
 def fpie : Flag<["-"], "fpie">, Group<f_Group>;
 def fno_pie : Flag<["-"], "fno-pie">, Group<f_Group>;
 def fprofile_arcs : Flag<["-"], "fprofile-arcs">, Group<f_Group>;
 def fprofile_generate : Flag<["-"], "fprofile-generate">, Group<f_Group>;
 def framework : Separate<["-"], "framework">, Flags<[LinkerInput]>;
-def frandom_seed_EQ : Joined<["-"], "frandom-seed=">, Group<clang_ignored_f_Group>;
+def frandom_seed_EQ : Joined<["-"], "frandom-seed=">, Group<f_Group>, Flags<[CC1Option]>;
 def freg_struct_return : Flag<["-"], "freg-struct-return">, Group<f_Group>, Flags<[CC1Option]>,
   HelpText<"Override the default ABI to return small structs in registers">;
 def frtti : Flag<["-"], "frtti">, Group<f_Group>;
 def : Flag<["-"], "fsched-interblock">, Group<clang_ignored_f_Group>;
 def fshort_enums : Flag<["-"], "fshort-enums">, Group<f_Group>, Flags<[CC1Option]>,
   HelpText<"Allocate to an enum type only as many bytes as it needs for the declared range of possible values">;
 def : Flag<["-"], "freorder-blocks">, Group<clang_ignored_f_Group>;
 def fshort_wchar : Flag<["-"], "fshort-wchar">, Group<f_Group>, Flags<[CC1Option]>,

lib/Driver/Tools.cpp

if (Arg *A = Args.getLastArg(options::OPT_mno_unaligned_access,
         CmdArgs.push_back("-arm-strict-align");
       } else {
         CmdArgs.push_back("-backend-option");
         CmdArgs.push_back("-arm-no-strict-align");
       }
     }
   }
 
+  // Translate -frandom-seed to seed the LLVM RNG
+  if (Args.hasArg(options::OPT_frandom_seed_EQ)) {
+    StringRef seed = Args.getLastArgValue(options::OPT_frandom_seed_EQ);
+    CmdArgs.push_back("-backend-option");
+    CmdArgs.push_back(Args.MakeArgString("-rng-seed=" + seed));
+  }
+
   if (Arg *A = Args.getLastArg(options::OPT_mrestrict_it,
                                options::OPT_mno_restrict_it)) {
     if (A->getOption().matches(options::OPT_mrestrict_it)) {
       CmdArgs.push_back("-backend-option");
       CmdArgs.push_back("-arm-restrict-it");
     } else {
       CmdArgs.push_back("-backend-option");
       CmdArgs.push_back("-arm-no-restrict-it");

lib/Frontend/CompilerInvocation.cpp

 #include "llvm/Option/ArgList.h"
 #include "llvm/Option/OptTable.h"
 #include "llvm/Option/Option.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Host.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Process.h"
+#include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/system_error.h"
 #include <atomic>
 #include <memory>
 #include <sys/stat.h>
 using namespace clang;
 
 //===----------------------------------------------------------------------===//
 // Initialization.
static void ParseTargetArgs(TargetOptions &Opts, ArgList &Args) {
   Opts.LinkerVersion = Args.getLastArgValue(OPT_target_linker_version);
   Opts.Triple = llvm::Triple::normalize(Args.getLastArgValue(OPT_triple));
 
   // Use the default target triple if unspecified.
   if (Opts.Triple.empty())
     Opts.Triple = llvm::sys::getDefaultTargetTriple();
 }
 
+static void SaltRNG(ArgList &Args) {
+  std::vector<std::string> Inputs = Args.getAllArgValues(OPT_INPUT);
+  std::string SaltString;
+  for (std::vector<std::string>::iterator I = Inputs.begin(), E = Inputs.end();
+       I != E; ++I) {
+    SaltString += *I;
+  }
+  llvm::RandomNumberGenerator::SetSalt(SaltString);
+}
+
 bool CompilerInvocation::CreateFromArgs(CompilerInvocation &Res,
                                         const char *const *ArgBegin,
                                         const char *const *ArgEnd,
                                         DiagnosticsEngine &Diags) {
   bool Success = true;
 
   // Parse the arguments.
   std::unique_ptr<OptTable> Opts(createDriverOptTable());
bool CompilerInvocation::CreateFromArgs(CompilerInvocation &Res,
   // FIXME: ParsePreprocessorArgs uses the FileManager to read the contents of
   // PCH file and find the original header name. Remove the need to do that in
   // ParsePreprocessorArgs and remove the FileManager 
   // parameters from the function and the "FileManager.h" #include.
   FileManager FileMgr(Res.getFileSystemOpts());
   ParsePreprocessorArgs(Res.getPreprocessorOpts(), *Args, FileMgr, Diags);
   ParsePreprocessorOutputArgs(Res.getPreprocessorOutputOpts(), *Args,
                               Res.getFrontendOpts().ProgramAction);
+  SaltRNG(*Args);
+
   return Success;
 }
 
 namespace {
 
   class ModuleSignature {
     SmallVector<uint64_t, 16> Data;
     unsigned CurBit;