Scalable String Analysis: An Experience Report

Scalable String Analysis: An Experience Report

Kostyantyn Vorobyov, Yang Zhao, Padmanabhan Krishnan

19 June 2021

Static string analysis underpins many security-related analyses including detection of SQL injections and cross-site scripting. Even though string analysis received much attention, none of the known techniques are effective on large codebases. In this paper we present OLSA -- a tool for scalable static string analysis of large Java programs. OLSA analysis is based on intra-procedural string value flow graphs connected via call-graph edges. Formally, this uses a context-sensitive grammar to generate the set of possible strings. We evaluate our approach by using OLSA to detect SQL injections and unsafe use of reflection in DaCapo benchmarks and a large internal Java codebase and compare the performance of OLSA with the state-of-the-art string analyser called JSA. The results of this experimentation indicate that our approach can analyse industrial-scale codebases in a matter of hours, whereas JSA does not scale to many DaCapo programs. The set of potential strings generated by our string analysis can be used for checking the validity of the reported potential vulnerabilities.


Venue : SOAP 2021 (Workshop associated with PLDI: https://pldi21.sigplan.org/home/SOAP-2021)