String Analysis for Software Verification and Security

این کتاب تکنیک‌های تحلیل رشته‌ای خودکار را مورد بحث قرار می‌دهد، که به‌ویژه بر تجزیه و تحلیل رشته استاتیک مبتنی بر خودکار تمرکز دارد. این موضوعات زیر را پوشش می دهد: تجزیه و تحلیل رشته مبتنی بر خودکار، محاسبه پیش و پس شرایط عملیات رشته پایه با استفاده از خودکار، نمایش نمادین خودکار، تحلیل رشته رو به جلو و عقب با استفاده از نمایش خودکار نمادین، تحلیل رشته مبتنی بر محدودیت، حل کننده های محدودیت رشته، تجزیه و تحلیل رشته رابطه ای، تشخیص آسیب پذیری با استفاده از تجزیه و تحلیل رشته، انتزاع رشته، تجزیه و تحلیل رشته های تفاضلی، و سنتز پاکسازی خودکار با استفاده از تجزیه و تحلیل رشته ها.

دستکاری رشته ها بخش مهمی از سیستم های نرم افزاری مدرن است. به عنوان مثال، به طور گسترده در اعتبار سنجی ورودی و پاکسازی و در تولید کد پویا و پرس و جو استفاده می شود. هدف تکنیک‌های تحلیل رشته‌ای و این کتاب تعیین مجموعه‌ای از مقادیری است که عبارات رشته‌ای می‌توانند در طول اجرای برنامه بگیرند. تجزیه و تحلیل رشته می تواند برای حل بسیاری از مشکلات در سیستم های نرم افزاری مدرن که به دستکاری رشته مربوط می شود استفاده شود، مانند: (1) شناسایی آسیب پذیری های امنیتی با بررسی اینکه آیا یک تابع حساس امنیتی می تواند رشته ورودی حاوی یک اکسپلویت را دریافت کند یا خیر. (2) شناسایی رفتارهای ممکن یک برنامه با شناسایی مقادیر ممکن برای کد تولید شده به صورت پویا. (3) شناسایی خطاهای تولید html با محاسبه کد html تولید شده توسط برنامه های کاربردی وب. (4) شناسایی مجموعه پرس و جوهایی که با تجزیه و تحلیل کدی که پرس و جوهای SQL را ایجاد می کند به پایگاه داده پشتیبان ارسال می شود. (5) وصله اعتبار سنجی ورودی و توابع پاکسازی با سنتز خودکار تعمیرات نشان داده شده در این کتاب.

مانند بسیاری از مشکلات دیگر تحلیل برنامه، حل مشکل تحلیل رشته به طور دقیق امکان پذیر نیست (یعنی اینطور نیست. امکان تعیین دقیق مجموعه ای از مقادیر رشته ای که می توانند به یک نقطه برنامه برسند). با این حال، می توان بیش از حد یا کمتر از تقریب مقادیر رشته ممکن را محاسبه کرد. اگر تقریب ها به اندازه کافی دقیق باشند، می توانند توسعه دهندگان را قادر سازند تا وجود یا عدم وجود اشکال در کد دستکاری رشته را نشان دهند. تجزیه و تحلیل رشته در دهه گذشته یک حوزه تحقیقاتی فعال بوده است که منجر به طیف گسترده‌ای از تکنیک‌های تحلیل رشته‌ای شده است.

این کتاب عمدتاً محققان و متخصصانی را که در زمینه امنیت رایانه، تأیید نرم‌افزار، روش‌های رسمی، کار می‌کنند، هدف قرار می‌دهد. مهندسی نرم افزار و تحلیل برنامه دانش‌آموزان یا مدرسان سطح پیشرفته در حال تدریس یا مطالعه دروس امنیت رایانه، تأیید نرم‌افزار یا تجزیه و تحلیل برنامه، این کتاب را به عنوان یک متن ثانویه مفید خواهند یافت.

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 string values. If the approximations are precise enough, they can enable developers 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.

This book will primarily target researchers and professionals working in computer security, software verification, formal methods, software engineering and program analysis. Advanced level students or instructors teaching or studying courses in computer security, software verification or program analysis will find this book useful as a secondary text.