В информатике символическое выполнение (также символическая оценка или symbex ) — это средство анализа программы для определения того, какие входные данные заставляют каждую часть программы выполняться . Интерпретатор следует программе, предполагая символические значения для входных данных , а не получая фактические входные данные, как это было бы при обычном выполнении программы. Таким образом, он приходит к выражениям в терминах этих символов для выражений и переменных в программе, а также к ограничениям в терминах этих символов для возможных результатов каждой условной ветви. Наконец, возможные входные данные, которые запускают ветвь, могут быть определены путем решения ограничений.
Область символического моделирования применяет ту же концепцию к оборудованию. Символические вычисления применяют эту концепцию к анализу математических выражений.
Рассмотрим программу ниже, которая считывает значение и дает сбой, если введено значение 6.
целочисленный f () { ... у = читать (); z = y * 2 ; если ( z == 12 ) { неудача (); } еще { printf ( "ОК" ); }}Во время обычного выполнения («конкретного» выполнения) программа считывала бы конкретное входное значение (например, 5) и присваивала бы его y. Затем выполнение продолжилось бы умножением и условным переходом, который бы дал ложное значение и вывел OK.
Во время символического выполнения программа считывает символическое значение (например, λ) и присваивает его y. Затем программа продолжит умножение и присвоит λ * 2. zПри достижении ifоператора она оценит λ * 2 == 12. В этой точке программы λможет принимать любое значение, и символическое выполнение может, таким образом, продолжаться по обеим ветвям, «разветвляясь» на два пути. Каждому пути назначается копия состояния программы в инструкции ветвления, а также ограничение пути. В этом примере ограничение пути предназначено λ * 2 == 12для ifветви и λ * 2 != 12для elseветви. Оба пути могут быть символически выполнены независимо. Когда пути завершаются (например, в результате выполнения fail()или просто выхода), символическое выполнение вычисляет конкретное значение для , λрешая накопленные ограничения пути на каждом пути. Эти конкретные значения можно рассматривать как конкретные тестовые случаи, которые могут, например, помочь разработчикам воспроизвести ошибки. В этом примере решатель ограничений определит, что для достижения fail()оператора λнеобходимо будет равно 6.
Символическое выполнение всех возможных путей программы не масштабируется для больших программ. Количество возможных путей в программе растет экспоненциально с увеличением размера программы и может быть даже бесконечным в случае программ с неограниченными итерациями цикла. [1] Решения проблемы взрыва пути обычно используют либо эвристики для поиска пути для увеличения покрытия кода, [2] сокращают время выполнения путем распараллеливания независимых путей, [3] или путем слияния похожих путей. [4] Одним из примеров слияния является veritesting , который «использует статическое символическое выполнение для усиления эффекта динамического символического выполнения». [5]
Символическое выполнение используется для рассуждения о программе path-by-path, что является преимуществом по сравнению с рассуждениями о программе input-by-input, которые используются в других парадигмах тестирования (например, динамический анализ программ ). Однако, если несколько входов проходят по одному и тому же пути через программу, экономия невелика по сравнению с тестированием каждого из входов по отдельности.
Символическое выполнение становится сложнее, когда к одному и тому же участку памяти можно получить доступ через разные имена ( алиасинг ). Алиасинг не всегда может быть распознан статически, поэтому механизм символического выполнения не может распознать, что изменение значения одной переменной также изменяет другую. [6]
Поскольку массив представляет собой набор из множества различных значений, символические исполнители должны либо рассматривать весь массив как одно значение, либо рассматривать каждый элемент массива как отдельное местоположение. Проблема с обработкой каждого элемента массива по отдельности заключается в том, что ссылка, такая как "A[i]", может быть указана только динамически, когда значение для i имеет конкретное значение. [6]
Программы взаимодействуют со своей средой, выполняя системные вызовы , получая сигналы и т. д. Проблемы согласованности могут возникнуть, когда выполнение достигает компонентов, которые не находятся под контролем символического инструмента выполнения (например, ядра или библиотек). Рассмотрим следующий пример:
целочисленный основной () { ФАЙЛ * fp = fopen ( "doc.txt" ); ... если ( условие ) { fputs ( "некоторые данные" , fp ); } еще { fputs ( "некоторые другие данные" , fp ); } ... данные = fgets (..., fp ); }Эта программа открывает файл и, на основе некоторого условия, записывает в файл различные типы данных. Затем она позже считывает записанные данные. Теоретически символическое выполнение разделило бы два пути в строке 5, и каждый путь оттуда имел бы свою собственную копию файла. Таким образом, оператор в строке 11 вернул бы данные, которые соответствуют значению «условия» в строке 5. На практике файловые операции реализуются как системные вызовы в ядре и находятся вне контроля инструмента символического выполнения. Основные подходы к решению этой проблемы:
Выполнение вызовов к среде напрямую. Преимущество этого подхода в том, что он прост в реализации. Недостаток в том, что побочные эффекты таких вызовов будут затирать все состояния, управляемые символическим механизмом выполнения. В приведенном выше примере инструкция в строке 11 вернет "некоторые данныенекоторые другие данные" или "некоторые другие данныенекоторые данные" в зависимости от последовательного порядка состояний.
Моделирование среды. В этом случае движок инструментирует системные вызовы с помощью модели, которая имитирует их эффекты и сохраняет все побочные эффекты в хранилище для каждого состояния. Преимущество в том, что можно получить правильные результаты при символическом выполнении программ, которые взаимодействуют со средой. Недостаток в том, что нужно реализовать и поддерживать множество потенциально сложных моделей системных вызовов. Такие инструменты, как KLEE, [7] Cloud9 и Otter [8], используют этот подход, реализуя модели для операций файловой системы, сокетов, IPC и т. д.
Форкинг всего состояния системы. Инструменты символического выполнения на основе виртуальных машин решают проблему среды, форкинг всего состояния VM. Например, в S2E [9] каждое состояние является независимым снимком VM, который может быть выполнен отдельно. Такой подход устраняет необходимость в написании и поддержке сложных моделей и позволяет практически любому двоичному файлу программы выполняться символически. Однако он имеет более высокие накладные расходы на использование памяти (снимки VM могут быть большими).
Концепция символической казни была введена академически в 1970-х годах с описаниями: системы Select [12] , системы EFFIGY [13], системы DISSECT [14] и системы Кларка [15] .