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.

Abstract Many critical codebases are written in C, and most of them use preprocessor directives to encode variability, effectively encoding software product lines. These preprocessor directives, however, challenge any static code analysis. SPLlift, a previously presented approach for analyzing software product lines, is limited to Java programs that use a rather simple feature encoding and to analysis problems with a finite and ideally small domain. Other approaches that allow the analysis of real-world C software product lines use special-purpose analyses, preventing the reuse of existing analysis infrastructures and ignoring the progress made by the static analysis community. This work presents VarAlyzer, a novel static analysis approach for software product lines. VarAlyzer first transforms preprocessor constructs to plain C while preserving their variability and semantics. It then solves any given distributive analysis problem on transformed product lines in a variability-aware manner. VarAlyzer ’s analysis results are annotated with feature constraints that encode in which configurations each result holds. Our experiments with 95 compilation units of OpenSSL show that applying VarAlyzer enables one to conduct inter-procedural, flow-, field- and context-sensitive data-flow analyses on entire product lines for the first time, outperforming the product-based approach for highly-configurable systems.

Global variables make software systems hard to maintain and debug, and break local reasoning. They also impose a non-trivial challenge to static analysis which needs to model its effects to obtain sound analysis results. However, global variable initialization, codes of corresponding constructors and destructors as well as dynamic library code executed during load and unload not only affect control flows but data flows, too. The PhASAR static data-flow analysis framework does not handle these special cases and also does not provide any functionalities to model the effects of globals. Analysis writers are forced to model the desired effects in an ad-hoc manner increasing an analysis’ complexity and imposing an additional repetitive task. In this paper, we present the challenges of modeling globals, elaborate on the impact they have on analysis information, and present a suitable model to capture their effects, allowing for an easier development of global-aware static data-flow analyses. We present an implementation of our model within the PhASAR framework and show its usefulness for an IDE-based linear-constant propagation that crucially requires correct modeling of globals for correctness.