AVL Function Table for LeafHooks Insertion With Obfuscated Control Flow Integrity

Control flow is the execution order of individual statements, instructions, or function calls within an imperative program. Malicious operation of control flow (e.g., tampering with normal function addresses) leads to severe consequences such as data leakage and system crash. Control Flow Integrity (CFI) is a defense restricting the execution order of program within Control Flow Graph (CFG). IndexHooks is an existing CFI solution designed against forward function calls tampering (including direct and indirect jump). This solution constructs a read-only linear function table that stores function addresses during compilation. Then, IndexHooks checks the table to make program jump to the correct target address during runtime. However, IndexHooks faces limitations in backtracking CFG construction, which can lead to excessive memory usage; the linear structure of the function table is vulnerable to brute force tampering. Addressing the limitations of IndexHooks, this study develops an obfuscated CFI solution called LeafHooks. LeafHooks is implemented during compilation by the LLVM compiler, which performs static analysis and instrumentation on the LLVM Intermediate Representation (IR) code of a program. We make the following three innovations: 1) we propose a speculation-free identification method for indirect function calls by linear traversing and analyzing codes to obtain legal function information (function address); 2) we save this information into a function table in the form of a Balanced Binary Tree (also known as AVL), enhancing the fuzzification of function addresses to defend against brute force; 3) we design a method to simulate control tamper attacks on ARM64 architecture to verify the ability of LeafHooks to protection. LeafHooks shows less overhead than state-of-the-art solutions and reduces 2.9% and 0.55% overhead on average using UnixBench and Phoronix, respectively.