В любой непонятной ситуации, когда станет совсем скучно — заводи спор о терминологии...
Пост родился по мотивам вчерашних обсуждений с
При символьном выполнении код интерпретируется, или выполняется, в соответствии с подмножеством семантики целевого языка, заменой всех неизвестных значений (входных данных) символьными переменными и вычислением формул в модели памяти, вместо конкретных значений. Подмножеством — потому что, невычислимые и сложно-вычислимые конструкции (вроде циклов и рекурсии, инварианты которых включают символьные переменные) упрощаются различными способами, про которые в академическом мире пишут целые диссертации. В реальном же мире SAST, как правило, просто ограничиваются «прокруткой» таких конструкций фиксированное количество раз или охапкой эвристик.
Основной челлендж разработчиков SAST, работающих в парадигме символьного выполнения: приемлемая аппроксимация семантики языка и эффективное решение проблемы экспоненциального роста путей выполнения или множества значений. Короче, долго, «дорого» (в плане сложности реализации), но относительно точно.
Абстрактная интерпретация же — это размен точности на скорость, при примерно той же «стоимости». Вместо неизвестных значений берутся их приближения: «переменная
x в [0..10]», или «переменная y чётная», или (в продвинутых техниках) «переменная s определяется конечным автоматом [a-zA-Z]+». Это формирует т.н. домен интерпретации. И далее осуществляется интерпретация кода в соответствии с определенным доменом. Анализ завершается в куда более приемлемое время, и охватывает все пути, но ценой роста процента ложных срабатываний.Проще пояснить на примере вычисления цикла:
def g(x):
while x < 100:
x = x + 2
return x
Символьное выполнение (один из подходов):
– принимает число итераций за неизвестную переменную
k;– выводит через интерпретацию уравнение
x0 + 2k = 100 и ищет его решения;– находит, например,
x0 = 0, k = 50;– крутит цикл k раз.
Относительно точно, но для сложных циклов всё же нужны инварианты (см. диссертацию выше), иначе анализ взорвётся по путям выполнения. На практике, в реальных приложениях, для подобного цикла — это произойдет задолго до приближения к 50-ой итерации.
Абстрактная интерпретация (интервальный домен):
– начнём с
x ∈ [0..50];– каждую итерацию добавляем 2:
[0..52] → [0..54] → …;– рост бесконечный, поэтому применяем widening («перепрыгиваем» через растущие приближения, чтобы гарантировать быстрое достижение фиксированной точки, пусть и грубым образом) и прыгаем к границе
[0..+∞);– потом применяем narrowing (уточняем полученное приближение, чтобы вернуть часть точности, которую потеряли на шаге widening) и условие выхода из цикла уточняют результат до
[100..+∞).Интервалы говорят: «на выходе точно
x ≥ 100», но теряют информацию о чётности.Если взять домен «чёт/нечет», анализ сохранит инвариант:
x ≡ x0 (mod 2). Это уже лучше, чем только интервалы, но и дороже.Таким образом, эти два подхода действительно принадлежат одному семейству в том смысле, что осуществляют интерпретацию кода. Но символьное выполнение полагается в большей степени на упрощение семантики языка, в то время, как абстрактная интерпретация — на упрощение семантики данных, заданное на старте интерпретации.
Но вообще, отвечая на вопрос, является ли одно подмножеством другого... если у абстрактной интерпретации отрезать все ограничения на входные данные, и основанные на них техники вычисления циклов и рекурсии, но пришить при этом упрощение семантики языка, то из дедушки возможно и получится бабушка🤷♂️
#SAST