A Path Sensitive and Scalable Approach for Mapping the Capabilities Required for Linux Kernel Defined System Calls Using Static Analysis Techniques

This paper outlines an analysis method for automatically identifying the required capabilities for the system calls defined by the Linux Kernel. Integrated in the LLVM compiler infrastructure, the static and path sensitive approach used aims to generate a complete set of logical equations, expressed in terms of the syscalls' argument configurations, that describe the relation between system calls and capabilities. In order to achieve the desired syscall to capability mapping a four stage analysis pipeline is proposed, each stage complimenting one of the abstraction layers used by the LLVM compiler. First, all possible execution paths, in terms of functions, are identified by the first stage, which is followed by the identification of the control flow blocks leading to calls to ensuing functions in the chain. Once all such paths are known, the third stage is tasked with solving the path explosion problem and to eliminate all control flow blocks that do not influence overall analysis goals. The final stages are responsible with instruction level analysis which binds each path to a constant equation verifying the arguments passed to the system call. By means of a scalable synthetic test program generator four sets of test-benches are constructed. Each test-bench is responsible to validate its corresponding stage of the analysis pipeline. They consists of programs that are scaled on the dimensions identified through mathematical analysis of the tested algorithm and problem.