22nd ACM SIGSOFT International Symposium on the Foundations of Software Engineering (FSE 2014), November 16–21, 2014, Hong Kong, China

Desktop Layout

String Analysis
Hall 2
String Analysis
Tevfik Bultan, Fang Yu, and Muath Alkhalaf
Abstract: String manipulation is a crucial part of modern software systems; for example, it is used extensively in input validation and sanitization and in dynamic code and query generation. The goal of string-analysis techniques is to determine the set of values that string expressions can take during program execution. String analysis can be used to solve many problems in modern software systems that relate to string manipulation, such as: (1) Identifying security vulnerabilities by checking if a security sensitive function can receive an input string that contains an exploit; (2) Identifying behaviors of JavaScript code that use the eval function by computing the string values that can reach the eval function; (3) Identifying html generation errors by computing the html code generated by web applications; (4) Identifying the set of queries that are sent to back-end database by analyzing the code that generates the SQL queries; (5) Patching input validation and sanitization functions by automatically synthesizing repairs. Like many other program-analysis problems, it is not possible to solve the string analysis problem precisely (i.e., it is not possible to precisely determine the set of string values that can reach a program point). However, one can compute over- or under-approximations of possible string values. If the approximations are precise enough, they can enable us to demonstrate existence or absence of bugs in string manipulating code. String analysis has been an active research area in the last decade, resulting in a wide variety of string-analysis techniques. In this tutorial, we will discuss automated string-analysis techniques, focusing particularly on automata-based static string analysis. We plan to cover the following topics: computing pre and post-conditions of basic string operations using automata, symbolic representation of automata, forward and backward string analysis using symbolic automata representation, relational string analysis, vulnerability detection using string analysis, differential string analysis, and automated repair using string analysis.


Time stamp: 2019-04-25T07:52:56+02:00