SAST (Static Application Security Testing) — метод тестирования защищенности приложений, который анализирует исходный код с помощью разных алгоритмов и технологий. Одной из них является абстрактная интерпретация, а если точнее — символьное выполнение. Их подробное описание можно найти здесь:
- Symbolic Execution. 17-355/17-665/17-819O: Program Analysis (Spring 2018)
- Ищем уязвимости в коде: теория, практика и перспективы SAST
- Abstract interpretation, Wikipedia
Упрощенно говоря, абстрактная интерпретация — интерпретация кода без его конкретного выполнения для сбора семантической информации о коде (потоки передачи данных, передачи управления и т. д.). Если при абстрактной интерпретации входные данные — аргументы функций точек входа, обращение к файловой системе, к внешним сервисам и др. — считать неизвестными и помечать как символьные значения, которые могут принимать любые доступные значения, пока не наложены ограничительные условия, мы получим определение символьного выполнения.
Для простоты понимания будем использовать следующие термины:
- Вариантом мы будем называть пару
, где 
— некое значение, а 
— условие достижимости этого значения. Обозначать будем как 
. - Вариативным множеством будем называть множество всех вариантов выражения. Обозначать будем как
Количество вариантов выражения
В момент формирования некоторого выражения языка, состоящего из подвыражений (например, конкатенации), которым соответствуют какие-то вариативные множества (см. рис. 1), количество вариантов получаемого выражения будет велико:
- вариативные множества: 
мерная функция языка, в частности, определенно 
, тогда количество вариантов выражения будет равно количеству элементов декартова произведения вариативных множеств подвыражений этого выражения:
Отсюда следует, что количество вариантов выражения, как функция от вариативных множеств, имеет показательную скорость роста. Если в основании степени будет значение, равное экспоненте, скорость будет экспоненциальной. В дальнейшем мы будем говорить, что оперируем экспоненциальной скоростью роста, держа в уме, что в действительности — показательной.
Экспоненциальное количество вариантов выражения сильно сказывается на ресурсах: памяти и времени. Как следствие, реальный объем используемой памяти может превышать желаемый на порядки, а время выполнения анализа может достигать нескольких часов, дней и даже более. В реальности мы не готовы выделять так много ресурсов, чтобы добиться результата.
Фундаментальная проблема
В одной из прошлых статей мы рассматривали частные случаи, где было показано, что количество вариантов имеет верхнюю грань — сильно меньшую, нежели экспоненциальное значение. Также были случаи, где эта верхняя грань вовсе имела линейное значение.
К сожалению, это были частные случаи: в основном количество вариантов имеет экспоненциальную скорость роста. Это фундаментальная проблема алгоритма анализа, которая приводит к увеличению объема используемых ресурсов. Увы, с этим приходиться мириться.
Только и остается, что увеличивать ресурсы за счет расширения объема доступной памяти или увеличения быстродействия вычислительных устройств. Либо огрублять алгоритм анализа, в пределе выбирая алгоритмы классом ниже, которые потребляют меньше ресурсов (например, анализ потоков данных или сопоставление с образцом). Посему далее будут рассмотрены эвристические подходы к огрублению символьного выполнения с целью уменьшения используемых ресурсов ценой точности анализа. Но при этом мы постараемся оставаться в рамках символьного выполнения и не опускаться на алгоритмы анализа класса ниже.
Эвристические подходы
Символьный анализ оперирует двумя сущностями: анализируемым исходным кодом и данными, которые получаются в ходе его анализа. Соответственно, к этим сущностям можно применить какие-либо эвристические подходы, направленные на огрубление анализа. Поэтому ниже мы рассмотрим подходы, оперирующие покрытием кода и объемом данных.
Уменьшение покрытия кода
Есть несколько подходов по уменьшению покрытия кода. Первый из них — при анализе исходного кода можно учитывать такое свойство функций, как чистота. Чистой функцией называется детерминированная функция без побочных эффектов, зависящая только от параметров (см. рис. 2). Подробнее с определением можно ознакомиться здесь.
Преимущество чистых функций в том, что благодаря их свойствам к ним при реальном выполнении можно применять такой способ оптимизации, как мемоизация. Она подразумевает создание кэша значений результатов выполнения функции от набора входных аргументов, который выступает ключом в кэше (см. рис. 3).
Благодаря этому все последующие вызовы этой функции от набора входных аргументов, для которого результат уже вычислен и записан в кэш, не требуют вычисления функции и выполнения большого количества операций, описанных в ней. Это приводит к ускорению времени работы, если выполнение функции занимает больше времени, чем поиск значения в кэше.
Эту оптимизацию можно адаптировать к символьному анализу чистых функций. Для этого чистая функция символьно анализируется один раз без учета внешнего контекста. При этом предполагается, что параметры функции являются символьными неизвестными, которые могут принимать любые допустимые значения в начале анализа функции. Проанализировав функцию, получим кэш, где ключами будут переменные, которые изменялись в этой функции при анализе, а значениями в кэше — значения этих переменных, которые зависят от параметров функции, являющихся символьными значениями (см. рис. 4).
Данный кэш есть таблица суммаризации функции — коль угодно, символьный шаблон функции. И всякий раз, когда при анализе других функций будет встречаться вызов проанализированной функции таким способом, вместо повторного анализа будет использоваться таблица суммаризации. Оттуда будут взяты необходимые переменные с их значениями, зависимые от символьно неизвестных параметров. Вместо этих неизвестных значений будут подставлены текущие значения аргументов, которые передаются в вызов функции. Таким образом мы получим реальные значения переменных, зависящие от внешнего контекста.
Можно увеличить частоту применения данного подхода, если расширить класс функций, на которых он применяется. Расширенной чистой функцией будем называть детерминированную функцию без побочных эффектов, зависящую от входных параметров и состояния памяти виртуальной машины (на момент вызова). Иными словами, от обычных чистых функций данный класс отличается тем, что позволяет иметь обращения к внешней памяти и переменным, которые не определены внутри самой функции. Это достигается с помощью ввода неявного нового параметра — состояния памяти виртуальной машины (svms, symbolic virtual machine state), к которому сводятся все обращения во внешнюю область функции. Все обращения к переменным, которые не определены в функции, заменяются на обращения к полям параметра svms, соответствующим этим переменным. На рис. 5 и 6 показано, как путем нескольких преобразований из грязной функции получается расширенная чистая.
Расширенная чистая функция анализируется так же, как и обычная: один раз, получая таблицу суммаризации, где значения могут зависеть от неявного символьно неизвестного параметра svms. В момент вызова этой функции, при анализе других, в качестве значения параметра svms будет передано текущее состояние памяти виртуальной машины — этакий снимок ее памяти. При этом в таблице суммаризации в интересующих записях вместо обращений к полям svms будут подставлены соответствующие значения из переданного снимка памяти.
Второй подход по уменьшению покрытия кода базируется на цели проведения символьного анализа, как части SAST, а именно выявлению уязвимостей в коде. Уязвимости возникают при использовании потенциально опасных операций вкупе с применением внешних источников данных, которые могут быть заражены атакующими. Если же функция не оперирует ни одним из двух указанных пунктов, с точки зрения поиска уязвимостей она является незначимой (см. рис. 7). При этом наряду с чистыми функциями можно применить эвристику, которая базируется на незначимости функций.
Поскольку функция незначима, хотелось бы и вовсе символьно ее не анализировать и не выделять на это ресурсы. Однако один раз это сделать необходимо ввиду того, что функция может возвращать какой-либо результат, а также изменять внешнюю область памяти и переменные, определенные не в области функции (см. рис. 8). Это нельзя игнорировать при символьном анализе, так как это может привести к ложноотрицательным срабатываниям, когда после вызова этой функции извне будут обращаться к тем самым внешним переменным.
Посему, проанализировав такую функцию один раз, мы получим таблицу ее суммаризации, в которой нас будут интересовать записи с внешними переменными или с возвращаемыми значениями из функции. В зависимости от того, будут ли значения внешних переменных в таблице суммаризации зависеть от параметров функции и/или от значений из внешних зараженных источников данных (которые могут прийти как через передачу аргументов в параметры, так и через обращения внутри функции), необходимо будет в анализируемой внешней функции во все внешние переменные проставить символьные неизвестные или же значения из внешних источников данных. Это поможет избежать ложноотрицательных срабатываний.
Данные подходы к уменьшению покрытия кода являются эвристическими, то есть не всегда гарантируют уменьшение потребляемых ресурсов (построение и поиск в таблице суммаризации в некоторых случаях может требовать определенных ресурсов), а также вносят некоторую меру неточности при решении условия достижимости и эксплуатируемости уязвимости — за счет замены реальных значений на символьные неизвестные и/или значения из внешних источников данных.
Уменьшение объема данных
Как упоминалось ранее, при символьном выполнении количество вариантов растет очень быстро, с экспоненциальной скоростью. Соответственно, другой ряд эвристических подходов направлен на своевременное уменьшение объема порождаемых вариантов выражения. Варианты в вариативных множествах можно фильтровать — уменьшать их количество за счет отбрасывания лишних (ненужных). Или же аппроксимировать их — менять некое множество вариантов на другое, заведомо менее мощное, с некоторыми изменениями. На рис. 9–11 показаны возможные аппроксимации и преобразования подмножеств вариантов, их значений и условий.
Если же в качестве аппроксимирующей функции, которая преобразовывает подмножества вариантов, взять функцию, чей образ есть пустое множество, аппроксимация превратится в фильтрацию. Посему дальше мы будем рассматривать аппроксимацию, держа в уме «способ перехода к фильтрации».
Для применения аппроксимации необходимо определить ее критерий — условие, при наступлении которого аппроксимирующая функция будет применена ко множеству вариантов. Так как при символьном анализе получаются разные выражения с подвыражениями, которые могут быть представлены в виде абстрактного синтаксического дерева (см. рис. 12), логично использовать в качестве критерия аппроксимации превышение некоторого порога количества подвыражений, где количество подвыражений назовем структурной сложностью. При превышении этого порога будем запускать аппроксимацию.
Соответственно, структурная сложность для выражений вычисляется следующим образом:
примитив, не имеющий подвыражений
подвыражение g
Но не стоит спешить: при символьном анализе возникают варианты в вариативных множествах, следовательно, выражения могут иметь подвыражения, которые могут быть вариативными множествами, где значения в вариантах также являются выражениями с некоторыми своими подвыражениями. В итоге мы получаем рекуррентное определение вхождения вариативного множества в выражение (см. рис. 13). В этом случае еще одним критерием, который вызывает интерес при анализе, может стать «превышение некоторого порога количества вариантов выражения», где во всех его вариативных множествах зафиксирован итоговый вариант — будем называть его значимой сложностью. Соответственно, при превышении этого порога тоже будем запускать аппроксимацию.
Значимую же сложность для выражений будем вычислять следующим образом:
примитив, не имеющий в подвыражениях вариативных множеств
подвыражение g
Итого: имеем структурную сложность для подсчета количества подвыражений и значимую сложность для подсчета количества вариантов. Но в значимой сложности никак не учитывался тот факт, что условия вариантов в вариативных множествах — это тоже выражения, которые могут содержать свои подвыражения. Поэтому получаем третью условную сложность — «максимальное количество всевозможных условий достижимости всех вариантов выражения». Иными словами, выражение может иметь подвыражения, которые могут быть вариативными множествами, где и значения, и условия вариантов также могут являться выражениями с некоторыми подвыражениями, откуда выводится рекуррентное определение (см. рис. 14). Как следствие, при превышении этого порога тоже будем запускать аппроксимацию.
Условную сложность для выражений будем вычислять следующим образом:
примитив, не имеющий в подвыражениях вариативных множеств
подвыражение g
В результате получаем несколько метрик для подсчета объема данных, а при превышении определенных порогов запускается аппроксимация. Остается выбрать аппроксимирующую функцию. Ее критериями могут быть: уменьшение объема данных, сохранение информации об источниках внешних зараженных данных, применение санитизирующих и валидирующих операций, а также сохранение информации о типах выражений. В PT Application Inspector используется аппроксимирующая функция, которая исключает подмножество вариантов при превышении порогов, заменяет его на новое символьное неизвестное значение и выставляет ему все описанные ранее сложности равными 1. Плюс аккумулирует все указанные ранее критерии. Но не стоит забывать, что аппроксимация — тоже эвристический подход...
В нашем случае при символьном анализе некоторое поддерево абстрактного синтаксического дерева выражений с вариантами исключается из анализа и заменяется на новое символьное неизвестное значение. Это приводит к уменьшению объема данных и к их постобработке — ценой уменьшения точности решения условий достижимости и эксплуатируемости уязвимостей за счет потери реальных значений, которые были в исключенном поддереве.
Мы рассмотрели эвристические подходы к уменьшению покрытия кода и объема данных для предотвращения экспоненциального роста при символьном анализе, что является его фундаментальной проблемой. Подходы на то и эвристические, что не гарантируют улучшения во всех возможных случаях. Или же потому, что добавляют определенную меру неточности (однако в большинстве случаев показывают свою ценность).
Конечно, это не единственные способы огрубления символьного анализа. За рамками статьи остались огрубление анализа коллекций данных, циклов, рекурсий, аппроксимации кода и т. д. Но охватить сразу все, к сожалению, невозможно — для этого понадобился бы отдельный журнал :)
