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. Some of the topics we plan to discuss in this course include grammar-based string analysis, automata-based symbolic string analysis, string constraint solving, string abstractions, relational string analysis, vulnerability detection using string analysis, differential string analysis, and automated repair using string analysis.