{'fraction_non_alphanumeric': 0.027075169219807623, 'fraction_numerical': 0.0003562522265764161, 'mean_word_length': 5.425629290617849, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Synchronized pushdown systems for pointer and data-flow analysis

Static data-flow analysis reasons about behaviour of software without executing it. A precise data-flow analysis transforms the program into context-sensitive, flow-sensitive, and field-sensitive approximation of the software. It is challenging to design an analysis of this precision efficiently. Contextand field-sensitive data-flow analysis, if fully precise, is undecidable, and any model of such precision cannot avoid an approximation. This thesis presents a new data-flow approximation for context-, fieldand flowsensitive data-flow analysis. The solution, called synchronized pushdown systems (SPDS), solves precise distributive data-flow analysis problems by relying on two pushdown systems, one system models field-sensitivity, the other one contextsensitivity. The SPDS then only accepts results that are contextand fieldsensitive. SPDS approximates only in corner cases that are rare in practice: at statements where both problems are satisfied but not along the same data-flow path. Experiments comparing SPDS to the standard model for field-sensitivity, k-limited access path, show that SPDS are almost as efficient as k-limiting with k = 1 although their precision equals to k =∞. Static data-flow analysis needs to resolve pointer relations when data escapes to the heap. Flows of pointers are difficult and costly to resolve because pointer relations are non-distributive. Nevertheless, this thesis shows that pointer analysis can be solved by subdividing pointer relations into multiple distributive computations, for each computation a SPDS can be consulted. Based on this design, the thesis presents the demand-driven pointer analysis Boomerang. Apart from relying on efficiently coordinating multiple SPDS, Boomerang minimizes it computational effort by only resolving the minimal part of pointer relations necessary to answer a points-to query. Another contribution of this thesis is IDE, a generic and efficient framework for data-flow analyses, e.g., typestate analysis or mining of application programming interfaces (APIs). IDE resolves pointer relations automatically and efficiently by the help of Boomerang. This reduces the burden of implementing pointer relations into an analysis. Further on, IDE performs strong updates which makes the analysis sound and precise. Apart from the fundamental problem of finding the right balance between precision and efficiency of a general static data-flow analysis, this thesis elaborates on a concrete application of Boomerang and IDE within a data-flow analysis that detects complex security vulnerabilities. Applying this data-flow analysis on large scale shows once more that synchronized pushdown systems enable a promising compromise between efficiency and precision.