Proceedings of ISP RAS


Inter-procedural buffer overflows detection in C/C++ source code via static analysis

I. Dudina (ISP RAS, Moscow, Russia, MSU, Moscow, Russia)

Abstract

We propose inter-procedural static analysis tool for buffer overflow detection. It is based on previously developed intra-procedural algorithm which uses symbolic execution with state merging. This algorithm is path-sensitive and supports tracking several kinds of value relations such as arithmetic operations, cast instructions, binary relations from constraints. In this paper we provide a formal definition for inter-procedural buffer overflow errors and discuss different kinds of such errors. We use function summaries for inter-procedural analysis, so it provides natural path-sensitivity in some degree. This approach allowed us to improve intra-procedural algorithm by tracking inter-procedural value dependencies. Furthermore, we introduce a technique to extract the sufficient condition of buffer overflow for a function, which is supposed to be stored in the summary of this function and checked at every call site. This approach was implemented for Svace static analyzer as the new buffer overflow detector, and it has shown 64% true-positive ratio on Android 5.0.2.

Keywords

static analysis, software error detection, buffer overflow, path-sensitivity, symbolic execution, context-sensitivity, inter-procedural analysis

Edition

Proceedings of the Institute for System Programming, vol. 28, issue 5, 2016, pp. 119-134.

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

DOI: 10.15514/ISPRAS-2016-28(5)-7

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