As part of post-link-time optimization, BOLT needs to perform a range of analyses on binaries such as reconstructing control flow graphs, and more.
The llvm-bolt-binary-analysis tool enables running requested analyses on binaries, and generating reports. It does this by building on top of the analyses implemented in the BOLT libraries.
For now, the only analysis implemented is validation of Pointer Authentication hardening on AArch64, more types of analyses can be added later.
For the past 25 years, a large numbers of exploits have been built and used in the wild to undermine computer security. The majority of these exploits abuse memory vulnerabilities in programs, see evidence from Microsoft, Chromium and Android.
It is not surprising therefore, that a large number of mitigations have been added to instruction sets and toolchains to make it harder to build an exploit using a memory vulnerability. Examples are: stack canaries, stack clash, pac-ret, shadow stacks, arm64e, and many more.
These mitigations guarantee a so-called “security property” on the binaries they produce. For example, for stack canaries, the security property is roughly that a canary is located on the stack between the set of saved registers and the set of local variables. For pac-ret, it is roughly that either the return address is never stored/retrieved to/from memory; or, there are no writes to the register containing the return address between an instruction authenticating it and a return instruction using it.
From time to time, however, a bug gets found in the implementation of such mitigations in toolchains. Also, code that is manually written in assembly requires the developer to ensure these security properties by hand.
In short, it is sometimes found that a few places in the binary code are not protected as well as expected given the requested mitigations. Attackers could make use of those places (sometimes called gadgets) to circumvent the protection that the mitigation should give.
One of the reasons that such gadgets, or holes in the mitigation implementation, exist is that typically the amount of testing and verification for these security properties is limited to checking results on specific examples.
In comparison, for testing functional correctness, or for testing performance, toolchain and software in general typically get tested with large test suites and benchmarks. In contrast, this typically does not get done for testing the security properties of binary code.
Unlike functional correctness where compilation errors result in test failures, and performance where speed and size differences are measurable, broken security properties cannot be easily observed using existing testing and benchmarking tools.
The security scanners implemented in llvm-bolt-binary-analysis aim to enable the testing of security hardening in arbitrary programs and not just specific examples.
Pointer Authentication is intended to make it harder for an attacker to replace pointers at run time. This is achieved by making it possible for the compiler or the programmer to produce a signed pointer from a raw one, and then to probabilistically authenticate the signature at another site in the program. On AArch64 this is achieved by injecting a cryptographic hash, called a “Pointer Authentication Code” (PAC), to the upper bits of the pointer. While this approach can be applied to any pointers in the program, the most frequent use case, at least in C and C++, is protecting the code pointers. The language rules for such pointers are more restrictive, thus allowing the compiler to implement various hardenings transparently to the programmer.
Probably the most simple variant of hardening based on Pointer Authentication is pac-ret, a security hardening scheme implemented in compilers such as GCC and Clang, which can be enabled with a command line option like -mbranch-protection=pac-ret. On AArch64, pac-ret hardening is enabled by default on most widely used Linux distributions. The hardening scheme mitigates Return-Oriented Programming (ROP) attacks by making sure that return addresses are only ever stored to memory in a signed form. This makes it substantially harder for attackers to divert control flow by overwriting a return address with a different value.
It is possible to link object files with different pac-ret hardening modes together, as each particular function is responsible for signing the LR value in the prologue and authenticating it in the epilogue. Other hardening variants exist that break ABI compatibility, see the description of PAuth ABI Extensions for details. While pac-ret hardens (signs and authenticates) return addresses, PAuth ABI may harden most other code pointers as well, such as function pointers and labels used as the destination of computed goto.
The approach to validation of Pointer Authentication hardening implemented in llvm-bolt-binary-analysis is tracking register properties using dataflow analysis. At each program point it is computed whether the particular register can be controlled and whether it can be inspected by an attacker under the Pointer Authentication threat model. Then, for a number of sensitive instruction kinds (such as function calls and pointer signing instructions), the properties of input or output operands are inspected to check if the particular instruction is emitted in a safe manner. As an example, for a return instruction this usually means that either the link register (x30, which is also referred to as LR on AArch64) was never clobbered in the function, or that it was authenticated at some point and never written to since then:
foo:
; x30 is assumed to be trusted on function entry
cbnz x0, .L1
; For every possible execution path leading to this point, x30 was never
; clobbered and is thus safe to be used by `ret`.
ret
.L1:
paciasp
stp x29, x30, [sp, #-16]!
mov x29, sp
bl bar
ldp x29, x30, [sp], #16
autiasp
; At this point, x30 was never written to since `autiasp`.
ret
The real rules being used by llvm-bolt-binary-analysis are somewhat more complex, see the below sections for the detailed explanation.
llvm-bolt-binary-analysis --scanners=<list> [options] <binary>
The --scanners= option accepts a comma-separated list of analyses to run on the provided binary. The binary to be analyzed can be either an ELF executable or a shared object. Similar to other BOLT tools, llvm-bolt-binary-analysis expects binary to be unstripped and preferably linked with --emit-relocs linker option.
In addition to options printed by llvm-bolt-binary-analysis --help-hidden, other relevant BOLT options can generally be passed, see llvm-bolt --help-hidden. Incomplete help message is a known issue and is tracked in #176969.
The only analysis which is currently implemented is validation of a number of Pointer Authentication-based hardening schemes such as pac-ret and PAuth ABI. The specific set of gadget kinds which are searched for depends on command line options. Each gadget found by PtrAuth gadget scanner results in a plain text report printed at the end of the analysis. Furthermore, an attempt is made to provide additional information on the instructions that made the register unsafe. Please note that this extra information is provided on a best-effort basis and is not expected to be as accurate as the reports themselves.
Here is an example of the report:
GS-PAUTH: signing oracle found in function function_name, basic block .LBB08, at address 102b8
The instruction is 000102b8: pacda x0, x1
The 1 instructions that write to the affected registers after any authentication are:
1. 000102b4: ldr x0, [x1]
This happens in the following basic block:
000102b4: ldr x0, [x1]
000102b8: pacda x0, x1
000102bc: ret
A similar report without the associated extra information looks like this:
GS-PAUTH: signing oracle found in function function_name, basic block .LBB016, at address 10384 The instruction is 00010384: pacda x0, x1 The 0 instructions that write to the affected registers after any authentication are:
Pointer Authentication analysis is able to search for a number of gadget kinds, with the specific set depending on command line options:
ptrauth-pac-ret - non-protected return instructionptrauth-tail-calls - performing a tail call with an untrusted value in the link registerptrauth-forward-cf - non-protected destination of branch or call instructionptrauth-sign-oracles - signing of untrusted value (signing oracle)ptrauth-auth-oracles - revealing the result of authentication without crashing the program on failure (authentication oracle)Validation is performed by llvm-bolt-binary-analysis on a per-function basis. First, the register properties are computed by analyzing the function as a whole. Then, the instructions are considered in isolation. For each kind of gadget, the set of susceptible instructions is computed. The properties of input or output registers of each such instruction are analyzed and reports are produced for each detected gadget.
Each gadget kind that is searched for can be characterized by the combination of
Currently, three properties can be computed for each register at any given program point:
Generally, BOLT strives to reconstruct the control-flow graph of each function, which is important for dataflow analysis. However, when BOLT fails to recognize some control flow in the particular function, that function ends up being represented as a flat list of instructions - in such cases llvm-bolt-binary-analysis computes register properties using a fallback analysis implementation, which is less precise.
The below sub-sections describe the particular detectors. Please note that while the descriptions refer to AArch64 for simplicity, the implementation of gadget detectors in llvm-bolt-binary-analysis attempts to be target-neutral by isolating AArch64 specifics in target-dependent hooks.
ptrauth-pac-ret)Instructions: Return instructions without built-in authentication: either ret (implicit x30 register) or ret <reg>, but not retaa and similar instructions.
Property: The register holding the return address must be safe-to-dereference.
Notes: Cross-exception-level return instructions (eret) are not analyzed yet.
A report is generated for a return instruction whose destination is possibly attacker-controlled.
Examples:
authenticated_return: pacibsp ; ... ; ... some code here ... ; ... retab ; Built-in authentication, thus out of scope. good_leaf_function: ; x30 is implicitly safe-to-dereference (s-t-d) and trusted at function entry. mov x0, #42 ; x30 was not written to by this function, thus remains s-t-d. ret good_non_leaf_function: pacibsp ; Spilling signed return address. stp x29, x30, [sp, #-16]! mov x29, sp bl callee ; Re-loading signed return address. ; LDP writes to x30 and thus resets it to neither s-t-d nor trusted state. ldp x29, x30, [sp], #16 ; Checking that signature is valid. ; AUTIBSP sets "s-t-d" property of x30, but not "trusted" (unless FEAT_FPAC ; is known to be implemented). autibsp ; x30 is s-t-d at this point. ret bad_spill: ; x30 is implicitly s-t-d at function entry. stp x29, x30, [sp, #-16]! mov x29, sp bl callee ; Spilled x30 may have been overwritten on stack. ; Writing to x30 resets its s-t-d property. ldp x29, x30, [sp], #16 ; x30 is unsafe by the time it is used by ret, thus generating a report. ret bad_clobber: pacibsp ; ... ; ... some code here ... ; ... autibsp mov x30, x1 ; The value in LR is unsafe, even though there was autibsp above. ret
ptrauth-tail-calls)Instructions: Branch instructions (both direct and indirect, regular or with built-in authentication), classified as tail calls either by BOLT or by PtrAuth gadget scanner's heuristic.
Property: link register (x30 on AArch64) must be trusted.
Notes: Heuristics are involved to classify instructions either as a tail call or as another kind of branch (such as jump table or computed goto).
A report is generated if a tail call is performed with an untrusted link register. This basically means that the tail-called function would have the link register untrusted on its entry (unlike the inherently correct address placed in the link register by one of the bl* instructions when a non-tail call is performed).
non_protected_tail_call: stp x29, x30, [sp, #-16]! mov x29, sp bl callee ldp x29, x30, [sp], #16 ; x30 is neither trusted nor safe-to-dereference at this point. b tail_callee non_checked_tail_call: pacibsp stp x29, x30, [sp, #-16]! mov x29, sp bl callee ldp x29, x30, [sp], #16 autibsp ; x30 is safe-to-dereference, but not fully trusted at this point. b tail_callee tail_callee: pacibsp ; ...
Even though x30 is likely to be safe-to-dereference before exit from a function (whether via return or tail call) in a consistently pac-ret-protected program, with respect to this gadget kind it further must be fully “trusted”. This corresponds to the way tail calls are emitted when --aarch64-authenticated-lr-check-method= option is specified with an argument other than none, or when such checks are requested for the particular subtarget by default.
Properly mitigating this issue would usually require inserting an explicit check after a regular authentication instruction, which may be either too expensive (if a fully-generic XPAC-based sequence is being used) on one hand, or not required at all (if FEAT_FPAC is known to be implemented) on the other hand.
ptrauth-forward-cf)Instructions: Indirect call and branch instructions without built-in authentication: either blr <reg> or br <reg>, but not blraa, braa and similar instructions.
Property: The call or branch target register must be safe-to-dereference.
A report is generated for an indirect branch or call instruction whose destination is possibly attacker-controlled.
Examples:
direct_call: ; ... bl callee ; Direct call, thus out of scope. ; ... authenticated_call: ; ... ldr x2, [x1] blraa x2, x1 ; Built-in authentication, thus out of scope. ; ... good_call: ; ... ldr x2, [x1] autia x2, x1 blr x2 ; ... bad_call: ; ... ldr x2, [x1] autia x2, x1 ; Store unprotected address. str x2, [x3] ; ... ; The callee address may have been overwritten in memory. ldr x2, [x3] blr x2 ; ... good_call_dataflow: cbz x0, .L1 ldr x2, [x1] autia x2, x1 b .L2 .L1: adrp x2, callee add x2, x2, :lo12:callee .L2: ; Dataflow analysis can deduce that x2 is s-t-d on any possible execution ; path leading to the below "br x2" instruction. br x2 bad_call_dataflow: cbz x0, .L3 adrp x2, callee add x2, x2, :lo12:callee .L3: ; x2 is untrusted if x0 is 0. br x2
ptrauth-sign-oracles)Instructions: Address-signing instructions.
Property: The address being signed must be trusted.
Reports signing of untrusted values, as this could make arbitrary and possibly attacker-controlled values indistinguishable from perfectly trusted and protected ones.
Note that in absence of --auth-traps-on-failure command line option, this detector reports auth+sign pairs unless an explicit check is emitted to make sure the authentication operation succeeded. This corresponds to the way LLVM emits instructions on AArch64.
Examples:
good_sign_constant: ; ... adrp x0, sym add x0, x0, :lo12:sym pacda x0, x1 ; ... good_resign: ; ... autda x0, x1 ; x0 is s-t-d here. ldr x2, [x0] ; If we got here without crashing on the above ldr, x0 is fully trusted. pacdb x0, x1 ; ... bad_resign_if_not_fpac: ; ... autda x0, x1 ; x0 is only s-t-d, but not trusted here, unless autda raises an error on failure. pacdb x0, x1 ; ... very_bad_function: pacda x0, x1 ret
ptrauth-auth-oracles)Instructions: Standalone authentication instructions: autda, autdb, etc. (i.e. not those built into corresponding memory-accessing instructions, such as ldraa or blraa).
Property: The result of authentication must be written to a register that cannot escape unchecked.
Reports authentication instructions, whose result (success or failure) can be observed by the attacker and used to guess the correct PAC field by trial-and-error.
The authentication oracles searched for by this detector are impossible if all authentication instructions are known to generate an irrecoverable error on failure. On AArch64 this is the case if CPU is known to implement FEAT_FPAC (though recoverability depends on the OS: for example, on Linux such errors result in signals that can be handled if configured accordingly). This check is disabled by --auth-traps-on-failure command line option.
Examples:
; The descriptions assume FEAT_FPAC is not implemented. good_auth_call: paciasp stp x29, x30, [sp, #-16]! mov x29, sp ; The result of authentication is inevitably dereferenced by blr. ; If autia returns a non-canonical address due to incorrect signature, ; the program crashes when the resulting address is jumped-to by blr. cbz x2, .L1 autia x0, x1 blr x0 .L1: ldp x29, x30, [sp], #16 autiasp ret bad_auth_call: paciasp stp x29, x30, [sp, #-16]! mov x29, sp ; x0 may be observed by the caller of bad_auth_call if x2 is 0. autia x0, x1 cbz x2, .L2 blr x0 .L2: ldp x29, x30, [sp], #16 autiasp ret bad_leaks_to_callee: paciasp stp x29, x30, [sp, #-16]! mov x29, sp ldr x20, [x0] autda x20, x0 ; The result of authentication is leaked to the called function. bl callee ; The below ldr instruction would properly check x20 if placed above the call. ldr x0, [x20] ldp x29, x30, [sp], #16 autiasp ret
The analysis quality is degraded if BOLT is unable to reconstruct control-flow graph of the function correctly.
When reconstructing CFG for a particular function, it is possible that BOLT finds a code pattern that it is unable to handle. In that case PtrAuth validator processes a function containing a flat list of instructions (as opposed to interlinked basic blocks) and the reports (if any) are printed without the , basic block <name> part in the first line.
Furthermore, it is possible that CFG information is returned by BOLT for a function, even though the graph is imprecise. Inaccurate CFG information may result in false positives and false negatives, thus PtrAuth gadget scanner produces warning messages (at most once per function) for non-entry basic blocks without any predecessors in CFG: while unreachable basic blocks are technically correct, truly unreachable blocks are unlikely to exist in an optimized code.
Known gadget scanner issues related to CFG reconstruction are tracked in #177761, #178058, #178232.
Some of the reports contain extra information along these lines
The 1 instructions that write to the affected registers after any authentication are:
1. 000102b4: ldr x0, [x1]
This happens in the following basic block:
000102b4: ldr x0, [x1]
000102b8: pacda x0, x1
000102bc: ret
This information is provided on a best-effort basis and is less reliable than gadget reports themselves.
On AArch64, signing and authentication operations are parameterized by the pair of the key identifier and a 64-bit discriminator value. The key is one of IA, IB, DA, or DB, and its identifier is directly encoded into the instruction (the GA key differs significantly and is thus out of scope here). The discriminator, on the other hand, is computed at run-time and is intended to be derived independently at the signing and authentication sites.
There is a common pattern on AArch64 to compute the discriminator as a blend of an address and an integer modifier by inserting a compile-time constant value into the top 16 bits of the storage address. It is not necessarily possible to prevent an attacker from modifying the storage address, but the insertion of 16-bit constant modifier can always be performed immediately before the discriminator value is used by signing or authentication instruction.
While not as bad as signing an arbitrary untrusted pointer, spilling a “ready-to-use” discriminator and then reloading a potentially modified value later is something we would rather avoid. On the other hand, using an arbitrary value as the discriminator should probably be allowed, making it hard to distinguish the below patterns:
; Valid and not reported. good_store_with_address_and_constant_diversity: mov x16, x1 movk x16, #1234, lsl #48 pacda x0, x16 str x0, [x1] ret ; Valid and not reported. good_store_with_address_diversity: pacda x0, x1 str x0, [x1] ret ; Spilled discriminator. Not critically wrong, but could rather be avoided. ; Not reported, but probably should (false negative). bad_spilling: mov x16, x1 movk x16, #1234, lsl #48 ; Spilling the discriminator to memory. str x16, [x2] ; Reloaded value could have been modified by an attacker. ldr x16, [x2] pacda x0, x16 str x0, [x1] ret ; Not reported (and should probably not). better_spilling: mov x16, x1 str x16, [x2] ; Reloaded value could have been modified by an attacker. ldr x16, [x2] movk x16, #1234, lsl #48 pacda x0, x16 str x0, [x1] ret
While (PC-relative) address constants are tracked as “trusted” register state by SrcSafetyAnalysis, constant values are not generally accounted for.
This results in false-positives like reporting
; Let assume FEAT_FPAC is implemented. autda x16, x22 mov x17, #0x128 add x16, x16, x17 pacda x16, x22
as a signing oracle, even though
; Let assume FEAT_FPAC is implemented. autda x16, x22 add x16, x16, #8 pacda x16, x22
is not reported, because add Xdst, Xsrc, #imm is recognized as a safe address computation.
As an example of false-negative, it is possible that an instruction like add x0, x0, #1 could be called in a loop with an attacker-controlled number of iterations, making it technically possible for an attacker to replace a valid pointer with a pointer to an arbitrary address.
ptrauth-tail-calls detector uses a heuristic to guess which branch instructions (both direct and indirect) correspond to performing tail calls, as opposed to other kinds of control flow.
Most other parts of BOLT should not break code when rewriting. Unlike them, this analyzer tries to keep reasonable balance between false positive reports and missed issues. For this reason, it inspects some other branch instructions in addition to those BOLT is sure about.
While it should provide reasonable balance between false positives and false negatives on general code, this may not be the case for some specific patterns. An example of a generally uncommon code pattern that is likely to yield false positives is labels-as-values GCC extension which is also supported by Clang.
ptrauth-tail-calls, see issue #186204 for the details.-Oz optimization level produces a lot of reports due to outlining. Many such reports could probably be considered false negatives as long as an attacker is unable to call OUTLINED_FUNCTIONs as ROP gadgets in the first place.pac-ret, nor by arm64e or pauthtest.To implement the detection of a new gadget kind, add new shouldReport*Gadget function to bolt/lib/Passes/PAuthGadgetScanner.cpp and call it either from FunctionAnalysisContext::findUnsafeUses or FunctionAnalysisContext::findUnsafeDefs.
To improve overall analysis quality by better computing register properties, either modify one of *SafetyAnalysis classes in PAuthGadgetScanner.cpp (if the improvement is target-neutral), or one of target-specific hooks in the subclass of MCPlusBuilder corresponding to your target (if an analysis of target-specific instruction patterns is to be improved).
To add support for a new target, if one eventually implements similar pointer protection technique, implement PtrAuth-related hooks in the subclass of MCPlusBuilder corresponding to your target. Ideally, no changes should be needed in PAuthGadgetScanner.cpp, as it is intended to be reasonably target- independent, though it is possible that some amount of further generalization may be required.
TODO: this section needs to be written. Ideally, we should have a simple “example” or “template” analysis that can be the starting point for implementing custom analyses