grsecurity - Linux Kernel Alternatives

Today, we'll be discussing two new IDA Pro (Interactive Disassembler) plugins released on our new GitHub organization that simplify and enhance our work with Linux kernel binaries:

ida-rap-decode

This is a simple Python plugin allowing to automatically analyze code following JMP instructions. By default IDA considers this code to be dead (which it is) and ignores it. This is a useful heuristic when disassembling malware which attempts various anti-disassembly tricks, however, in the case of a Linux kernel compiled with the RAP plugin, disassembling these instructions improves readability.

ida-linux-alternatives

This is a more complex Python plugin allowing to automatically analyze and annotate Linux kernel alternatives. It automatically parses the contents of the .altinstructions and .altinstr_replacement sections (for details see below) and annotates disassembly listings with the identified alternatives. Additionally, it allows to modify (patch) IDA's view of a binary with the alternatives selected by CPU feature flags. These changes can then be applied to the original binary for analysis by outside tools via the Edit/Patch program/Apply patches to input file... menu.

What are Linux kernel alternatives for?

CPU architectures don't tend to stick to a fixed ISA (Instruction Set Architecture) but gain extensions over time. The x86 architecture is a prime example, getting a new set of extensions with almost every new CPU microarchitecure released. While the support of new features and extensions is advertised by the mechanism of the CPUID instruction, it becomes a challenge for system software to easily adapt and make efficient use of what is supported. Compile-time configuration is an easy solution, but who would like to compile and maintain dozens of build flavours for various CPUs? Also running the correct kernel version on the right hardware becomes a very complex problem. Sprinkling the entire code base with conditions detecting and selecting supported features is detrimental to performance and massively grows kernel binaries.

Linux kernel alternatives are a mechanism that the kernel uses to simplify the challenges. With the use of alternatives, the Linux kernel optimizes itself at early boot time. The kernel does that by checking what features are supported on the currently executing hardware (via the CPUID instruction or other means) and replacing all default instructions in all pre-defined locations with the optimal ones.

To facilitate this feature, Linux kernel binaries have at least two special sections: .altinstructions and altinstr_replacement:

.altinstructions - consists of entries of struct alt_instr type

The layout of this structure has changed several times throughout Linux kernel releases, but as of v5.13 looks like this:

struct alt_instr {
        s32 instr_offset;       /* original instruction */
        s32 repl_offset;        /* offset to replacement instruction */
        u16 cpuid;              /* cpuid bit set for replacement */
        u8  instrlen;           /* length of original instruction */
        u8  replacementlen;     /* length of new instruction */
} __packed;

The instr_offset relates to the location of the default instructions to be replaced with optimal ones. The repl_offset relates to the location of the optimal instructions. The cpuid field contains a CPU feature flag associated with the optimal instructions. The last two fields describe the corresponding size of the default and optimal instructions. In case of a difference between the default and optimal instruction set sizes, the replaced construct is padded with NOP instructions.

altinstr_replacement - consists of optimal instructions for various CPU feature flags

The Linux kernel runs apply_alternatives() during early boot to parse the sections and apply modifications to its code accordingly. As a result, a kernel self-modified that way behaves as if it was compiled for a given CPU with minimal overhead.

It is worth mentioning that nowadays, the alternatives mechanism is also used to efficiently patch CPU bugs. In the cpufeatures.h file one can find a distinct set of bug flags indicating which hardware vulnerability the CPU might be affected by (e.g. X86_BUG_SPECTRE_V2). In addition, some of the feature flags are pure software flags (e.g. X86_FEATURE_RETPOLINE or X86_FEATURE_RSB_CTXSW), derived from a combination of given CPU model, CPUID flags and kernel command-line options. The Linux kernel, using alternatives, will replace the impacted code locations with their safer variants when running on affected hardware.

Main features of ida-linux-alternatives

The ida-linux-alternatives plugin automates parsing, interpreting and annotating the content of a Linux kernel binary's alternatives sections. The plugin attempts to find as much required information as possible in the kernel binary being analyzed, thus required manual operations are kept to the bare minimum.

A brief description of supported features:

Annotation of alternative entries

Example:
Auto-detecting the layout of the alt_instr structure

If the Linux kernel binary has been compiled with DWARF debug information (CONFIG_DEBUG_INFO=y), the plugin will automatically use the information to reconstruct the layout of struct alt_instr.

If it is not present, the plugin attempts to heuristically determine the following properties of the structure:
- type and size of the first two structure members (offset or direct address of the default instructions and their optimal replacement)
- size of the structure
- offsets of the length field members
- size of the cpuid member
Analyzing existing CPU feature flag definitions in a binary

If the Linux kernel binary has been compiled with CPU feature names (CONFIG_X86_FEATURE_NAMES=y), the plugin will analyze and consume information available in two array symbols: x86_cap_flags and x86_bug_flags. Thereby, it can automatically find a mapping between CPU feature flag values and their corresponding names.

However, some of the feature flag names are deliberately kept away from the kernel binary (and /proc/cpuinfo output). In the arch/x86/kernel/cpu/mkcapflags.sh script, which the Linux kernel build system uses to construct the flag names arrays, you can find the following code:
```
# If the /* comment */ starts with a quote string, grab that.
VALUE="$(echo "$i" | sed -n 's@.*/\* *$"[^"]*"$.*\*/@\1@p')"
[ -z "$VALUE" ] && VALUE="\"$NAME\""
[ "$VALUE" = '""' ] && continue
```
It essentially prevents adding any feature flag names that are defined in a cpufeatures.h file with a comment starting with a double double-quote:
```
#define X86_FEATURE_RETPOLINE           ( 7*32+12) /* "" Generic Retpoline mitigation for Spectre variant 2 */
#define X86_FEATURE_RETPOLINE_AMD       ( 7*32+13) /* "" AMD Retpoline mitigation for Spectre variant 2 */
```
As a result, the X86_FEATURE_RETPOLINE and X86_FEATURE_RETPOLINE_AMD names will not be included into the binary or displayed in /proc/cpuinfo.
Supporting cpufeatures.h parsing

To overcome the limitation described above, we implemented a trivial parser of the cpufeatures.h file and added an option Edit/Linux Alternatives/Import cpufeatures.h file to let the user import the corresponding file and fill in the missing feature flag names. When such a file has been selected, it overrides any default names available in the binary.
Handling nested alternatives

Yes, there can be alternatives for alternative handling in the Linux kernel! Funny as it may sound, the main purpose here is to express more complex logic of CPU features and bug dependencies and handle it with minimal extra code complexity.
Patching the binary with selected alternatives

The main purpose of this feature is to simulate the presence of specified CPU feature flags and update (patch) the binary with their corresponding alternatives. This feature might be very useful for inspecting alternative entries for correctness and security or any other static analysis purpose, without the need to run the Linux kernel binary.

Upon clicking the Patch selected alternatives option in Edit/Linux Alternatives menu bar, the following prompt is displayed:

The user can specify a comma-separated list of feature flags either by their name (case-insensitive) or by their integer value as calculated in the typical cpufeatures.h file:

Clicking OK will automatically patch and re-analyze the entire database with alternatives selected with the feature flags:

Before After

Alternatives - more than meets the eye

Analyzing and debugging Linux kernel alternatives is possible at boot time with the following kernel command-line options: debug and debug-alternative. It might be a useful approach during development effort or debugging, but it is impractical for static analysis or security properties verification. Firstly, one needs to boot the kernel (what about kernels that already booted and ran?) with the right command-line options and then extract usually massive printked console output to find the interesting parts. It also becomes cumbersome to force the presence of relevant CPU features (it is possible to disable certain CPUID features with the kernel command-line option clearcpuid). Typically one needs to employ QEMU and its emulation capabilities.

Recently during our work on PaX/grsecurity features, we were faced with all these problems and decided to solve or at least significantly simplify them. Various PaX/grsecurity plugins and enhancements have to deal with Linux kernel alternatives and apply security measures to them.

It is crucial to thoroughly verify if the modifications of alternatives still hold correctness and security properties intended after they are applied in all the locations. One good example could be an SLS (Straight Line Speculation) barrier (typically in a form of an int3 instruction) applied after all indirect jumps in the binary. Regular disassembly is easily verifiable with objdump + grep, but alternatives are not that transparent. Depending on the code construct the SLS barrier might be part of the alternative replacement itself or just natively follow the replaceable location. Such static analysis becomes tedious and error-prone if one has to reason about dynamically applied alternatives. With the ida-linux-alternative plugin, one can patch in alternatives for relevant CPU feature flags and simply "grep" the binary for interesting patterns.

Security relevance

Alternatives could also be potentially (ab)used for more nefarious undertakings.

The format of Linux kernel alternative entries has changed several times already and very few tools (the Linux kernel itself and objtool only?) actually parse them. Such obscurity and difficulty in automatic analysis makes alternatives a ripe location to insert stealthy malicious changes that would avoid cursory on-disk inspection.

Similar to the method of abusing the relocation mechanism in ELF and PE binaries as described by the famous (15-year-old now!) paper: "Locreate: An Anagram for Relocate" by Matt Miller, one can think of modifying Linux kernel alternative sections (before boot, on-disk) in a similar way. Rewriting replacement instructions to add hidden backdoors (be it an extra load_module() call or potentially skipping capability checks), although limited (typical replacement sizes are somewhat small) is doable and presents a potential attack vector.

Therefore, it is important to keep an eye on your alternatives. With the ida-linux-alternatives plugin this task becomes a little bit easier.