Influence: A Quantitative Approach for Data Integrity (CMU-CyLab-08-005)

A number of systems employ dynamic taint analysis to detect overwrite attacks in commodity software. These systems are based on the premise that low-integrity inputs should not control values such as function pointers and return addresses. Unfortunately, there are several programming constructs that can cause false positives and false negatives in these systems, which are currently handled by manual annotation, ad-hoc rules, or not at all. In this work we propose to use channel capacity, a quantitative measure of information flow, as a quantitative measure of control. When measuring control, we refer to this measure as influence. We use influence as a theoretical tool to formally investigate programming constructs known to be problematic for dynamic taint analysis. While calculating influence in arbitrary programs is undecidable in the general case, we propose and implement practical techniques for automatically bounding and probabilistically estimating influence in x86 programs. We show that this tool is able to automatically find useful influence bounds in code constructs known to be problematic in dynamic taint analysis. We also use it to analyze a dynamic taint analysis alert in samba, showing that it is a false positive, and another alert in SQL Server, showing that it is a true positive.