String Analysis for Software Verification and Security [Hardcover]

This book discusses automated string-analysis techniques, focusing particularly on automata-based?static string analysis. It covers the following topics: automata-bases?string analysis, computing pre and post-conditions of basic string?operations using automata, symbolic representation of automata, forward?and backward string analysis using symbolic automata representation,?constraint-based string analysis, string constraint solvers, relational string?analysis, vulnerability detection using string analysis, string abstractions,?differential string analysis, and automated sanitization synthesis using?string analysis.

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 and this book?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?possible behaviors of a program by identifying possible values for?dynamically generated code; (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 illustrated in this book.

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 slӻ