Scaling Bottom-Up IFDS Taint Analysis with Optimized Data-Flow Encoding

Static taint analysis is an important technique for bug-finding and vulnerability detection on source-code. One commonly used technique to solve inter-procedural taint analysis problems is the well-studied Interprocedural Finite Distributive Subsets (IFDS) algorithm. However, when performing a whole-program analysis, IFDS-based taint analyses have trouble scaling to large target programs, mainly due to its huge memory consumption. A common technique to solve this issue is to modularize the analysis by visiting the call graph bottom-up, performing local sub-analyses in isolation. Still, bottom-up formulations of IFDS are rare due to their own scalability issues caused by over-approximating the analysis state at the beginning of a procedure. In this work we study how one can improve scalability for bottom-up taint analysis of C and C++ programs on millions of lines of code. We present MonoIFDS, a variant of the IFDS algorithm that combines IFDS-style procedure summaries with bottom-up inter-procedural propagation. It uses a modified encoding of the data-flow state and propagation to improve the efficiency of handling large analysis states, and to enable optimizations, such as optimizing the iteration order, that were not beneficial on IFDS analyses before. In our evaluation we show, how MonoIFDS performs compared to SparseIFDS when analyzing real-world C and C++ programs. Achieving a speedup of 6.17 on average with only consuming 51% of the memory compared to SparseIFDS, MonoIFDS drastically outperforms the state-of-the-art SparseIFDS and enables developers to target the analysis of large programs on consumer hardware.