A Hybrid Alias Analysis and Its Application to Global Variable Protection in the Linux Kernel

Global variables in the Linux kernel have been a common target of memory corruption attacks to achieve privilege escalation. Several potential defense mechanisms can be employed to safeguard global variables. One approach involves placing global variables in read-only pages after kernel initialization (ro_after_init), while another involves employing software fault isolation (SFI) to dynamically block unintended writes to these variables. To deploy such solutions in practice, a key building block is a sound, precise, and scalable alias analysis that is capable of identifying all the pointer aliases of global variables, as any pointer alias may be used for intended writes to a global variable. Unfortunately, the two existing styles of data-flow-based (e.g., Andersen-style) alias analysis and type-based alias analysis have serious limitations in scalability and precision when applied to the Linux kernel.

This paper proposes a novel and general hybrid alias analysis that unifies the two complementary approaches in a graph reachability framework using context-free-language, also known as CFL-reachability. We show our hybrid alias analysis is extremely effective, significantly and simultaneously outperforming the data-flow-based alias analysis in scalability and the type-based alias analysis in precision. Under the same time budget, our hybrid analysis finds 42% of the Linux kernel global variables protectable as ro_after_init, whereas the two separate analyses find a combined 16% only.