Post Compile-Time RandStruct

[Jasper Niebuhr]

Hi,
my name is York Jasper Niebuhr and I am currently approaching the
finish line of by bachelor's thesis at the Technical University of
Munich. My supervisor and I addressed an issue with grsecurity's
RandStruct (structure layout randomization). Millions of end-users of
any distros - that pre-compile the kernel - are given a kernel with
the same randomization seed, or simply no randomization at all.
Furthermore, distros usually need to publish this seed to ensure
compatibility with separately built components.

We came up with the idea to apply structure layout randomization to
the kernel AFTER it was compiled. In theory, this can be done by
disassembling machine instructions to check if they access a member of
a struct we want to randomize. If so, we can change the according
operand's displacement to reflect the new position of that member.
Additionally, any initial data of objects can be reordered in the
kernel's data segments.

To explore this concept a little further, I spent the past 3 months
building a prototype. This prototype uses only the kernel's debug
information (32 bit DWARF 4, not 32 bit kernel!), especially stuff
like the location descriptions, to get an idea of any entities in the
program. Then, a scanner goes through any function's machine code to
check if the instructions access one such object. Any access is logged
in an intermediate file (pretty much just a binary list). A second
program loads this file, randomizes a few chosen structures and
updates the kernel accordingly. This separation into two programs was
done to lift some load from the end-users machine. Everything up to a
complete intermediate file can be done by the distributor, as it is
fully independent of randomizations. The distributor can then publish
this file, so the end-user's machine can resume with only the
randomization and update process.

In practice, this concept seems to have a lot of potential. Among
other structs, the prototype is currently able to randomize
approximately 70% of the task_struct, including its cred member. This
requires about 20 seconds to run the first program (distributor), as
well as less than 10 milliseconds for the randomization and changes to
the kernel (end-user). These 10 milliseconds include all the file
operations in the kernel's binary file. The prototype detects more
than 11000 instructions that access the task_struct and replaces many
thousands that are relevant to the part it can currently randomize. In
the end, the kernel boots in qemu just fine and system calls like fork
and setuid/getuid produce the expected results.

Unfortunately, debug information turned out to be inaccurate and
incomplete at times. Combined with the kernel's quadrillion edge
cases, this prevented me from taking the prototype any further until
the deadline. We can see this concept fully shine with, for example, a
compiler plugin to log any accesses, instead of a tool that deals with
debug info. The second part of the prototype (or a mature, later
version of it) can be integrated into distro installers or run
whenever the kernel is updated. Even integration into the kernel's
boot process would be an option.

Since I am now in the writing phase of my thesis (deadline mid
January), I thought I'd share our thoughts to hopefully get some
feedback. Do you think this approach solves some of the issues that
RandStruct currently comes with? Can you see such a system actually
being deployed once it's fully functional?

I am of course open to any further questions or suggestions!

Kind Regards,
Jasper