Control Flow Verification Tool Design Document

Control Flow Verification Tool Design Document

Objective

This document provides an overview of an external tool to verify the protectionmechanisms implemented by Clang’s Control Flow Integrity (CFI) schemes(-fsanitize=cfi). This tool, provided a binary or DSO, should infer whetherindirect control flow operations are protected by CFI, and should output theseresults in a human-readable form.

This tool should also be added as part of Clang’s continuous integration testingframework, where modifications to the compiler ensure that CFI protectionschemes are still present in the final binary.

Location

This tool will be present as a part of the LLVM toolchain, and will reside inthe “/llvm/tools/llvm-cfi-verify” directory, relative to the LLVM trunk. It willbe tested in two methods:

Unit tests to validate code sections, present in“/llvm/unittests/tools/llvm-cfi-verify”.
Integration tests, present in “/llvm/tools/clang/test/LLVMCFIVerify”. Theseintegration tests are part of clang as part of a continuous integrationframework, ensuring updates to the compiler that reduce CFI coverage onindirect control flow instructions are identified.

Background

This tool will continuously validate that CFI directives are properlyimplemented around all indirect control flows by analysing the output machinecode. The analysis of machine code is important as it ensures that any bugspresent in linker or compiler do not subvert CFI protections in the finalshipped binary.

Unprotected indirect control flow instructions will be flagged for manualreview. These unexpected control flows may simply have not been accounted for inthe compiler implementation of CFI (e.g. indirect jumps to facilitate switchstatements may not be fully protected).

It may be possible in the future to extend this tool to flag unnecessary CFIdirectives (e.g. CFI directives around a static call to a non-polymorphic basetype). This type of directive has no security implications, but may presentperformance impacts.

Design Ideas

This tool will disassemble binaries and DSO’s from their machine code format andanalyse the disassembled machine code. The tool will inspect virtual calls andindirect function calls. This tool will also inspect indirect jumps, as inlinedfunctions and jump tables should also be subject to CFI protections. Non-virtualcalls (-fsanitize=cfi-nvcall) and cast checks (-fsanitize=cfi-cast)are not implemented due to a lack of information provided by the bytecode.

The tool would operate by searching for indirect control flow instructions inthe disassembly. A control flow graph would be generated from a small buffer ofthe instructions surrounding the ‘target’ control flow instruction. If thetarget instruction is branched-to, the fallthrough of the branch should be theCFI trap (on x86, this is a ud2 instruction). If the target instruction isthe fallthrough (i.e. immediately succeeds) of a conditional jump, theconditional jump target should be the CFI trap. If an indirect control flowinstruction does not conform to one of these formats, the target will be notedas being CFI-unprotected.

Note that in the second case outlined above (where the target instruction is thefallthrough of a conditional jump), if the target represents a vcall that takesarguments, these arguments may be pushed to the stack after the branch butbefore the target instruction. In these cases, a secondary ‘spill graph’ inconstructed, to ensure the register argument used by the indirect jump/call isnot spilled from the stack at any point in the interim period. If there are nospills that affect the target register, the target is marked as CFI-protected.

Other Design Notes

Only machine code sections that are marked as executable will be subject to thisanalysis. Non-executable sections do not require analysis as any executionpresent in these sections has already violated the control flow integrity.

Suitable extensions may be made at a later date to include analysis for indirectcontrol flow operations across DSO boundaries. Currently, these CFI features areonly experimental with an unstable ABI, making them unsuitable for analysis.

The tool currently only supports the x86, x86_64, and AArch64 architectures.