Proceedings of ISP RAS


Comparative analysis of two approaches to the static taint analysis

M.V. Belyaev (ISP RAS, Moscow, Russia)
N.V. Shimchik (ISP RAS, Moscow, Russia)
V.N. Ignatyev (ISP RAS, Moscow, Russia)
A.A. Belevantsev (ISP RAS, Moscow, Russia; MSU, Moscow, Russia)

Abstract

Currently, one of the most efficient ways to find software security problems is taint analysis. It can be based on static analysis and successfully detect errors that lead to vulnerabilities, such as code injection or leaks of private information. Several different ways exist for the implementation of the algorithm for the taint data propagation through the program intermediate representation: based on the dataflow analysis (IFDS) or symbolic execution. In this paper, we describe how to implement both approaches within the existing static analyzer infrastructure to find errors in C# programs, and compare these approaches in different aspects: the scope of application, practical completeness, results quality, performance and scalability. Since both approaches use a common infrastructure for accessing information about the program and are implemented by a single development team, the results of the comparison are significant and can be used to select the best option in the context of the task. Our experiments show that it’s possible to achieve the same completeness regardless of chosen approach. IFDS-based implementation has higher performance comparing with symbolic execution for detectors with small amount of taint data sources. In the case of multiple detectors and a large amount of sources the scalability of IFDS approach is worse than the scalability of symbolic execution.

Keywords

taint analysis; static analysis; IFDS; symbolic execution

Edition

Proceedings of the Institute for System Programming, vol. 29, issue 3, 2017, pp. 99-116.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2017-29(3)-7

Full text of the paper in pdf (in Russian) Back to the contents of the volume