В чем разница между анализом потока данных и абстрактной интерпретацией
В чем разница между анализом потока данных и абстрактной интерпретацией и используются ли они для одной и той же цели? Каковы плюсы и минусы этих двух по отношению друг к другу.
2 ответа
Короче говоря, они в разных категориях. Это как сравнивать ткани и брюки.
Абстрактная интерпретация - это структура, которая формализует вычисления с фиксированной запятой с использованием абстрактной области и абстрактных передаточных функций. Абстрактная интерпретация гарантирует, что фиксированная точка должна быть найдена за конечные шаги, если соблюдены определенные условия (подробности: http://www.di.ens.fr/~cousot/COUSOTpapers/POPL77.shtml). Какое величие абстрактной интерпретации происходит от расширения и сужения. Из-за них абстрактная интерпретация может вычислить фиксированную точку над бесконечной областью.
ИМО, анализ потока данных является лишь одним из примеров абстрактной интерпретации. Поскольку большинство конкретных областей, используемых при анализе потока данных, являются конечными, вам даже не нужно расширять и сужать.
Я не уверен, что какой-либо из ответов здесь действительно затрагивает цель исходного вопроса, который, похоже, требует интуитивного, а не технического объяснения. Анализ потока данных связан с получением ценности некоторой части информации в заданном месте. Примерами "информации" являются определения того, какие определения достигают данного местоположения, какие переменные находятся в данном месте, какие выражения являются постоянными в данном месте и т. Д. Структуры потока данных обычно требуют, чтобы область значений образовывала конечную решетку, чтобы передаточные функции должны быть монотонными (передаточная функция определяет, как эта информация распространяется от входа до выхода из блока), все это с целью иметь возможность вычислять фиксированную точку значений потока данных. Используется в компиляторах.
Абстрактная интерпретация (AI) OTOH направлена на построение абстрактного интерпретатора языка. Цель состоит в том, чтобы определить, "Что вычисляет этот фрагмент кода? Давайте попробуем ответить на этот вопрос в абстрактном смысле". Например, если вычисление возвращает значение некоторой индексной переменной i, AI может вычислить диапазон для i, чтобы вы могли ответить, будет ли нарушение границ или что-то в этом роде. Таким образом, область абстрактных значений немного отличается, это может быть область диапазона, многогранная область и т. Д. По этой причине ИИ накладывает разные ограничения на поток данных: конкретные и абстрактные домены обычно должны быть связаны чем-то, называемым галуа-соединением., который связывает наборы конкретных значений с абстрактными. Поскольку используемые домены не обязательно должны быть конечными, ИИ не всегда будет сходиться без вмешательства,в виде операций расширения / сужения. ИИ используется в официальных инструментах проверки. Их обоих объединяет желание, чтобы итерации функции совпадали, но это все. Поэтому используйте анализ потока данных, если вы хотите узнать ценность чего-либо в определенном месте, используйте AI, если вы хотите знать, что программа абстрактно вычисляет.
И поток данных, и ИИ можно использовать вместе. Например, инструмент дизассемблера Jakstab сочетает в себе оба - поток данных используется для определения значений для косвенных целей перехода (т. Е. Что нового вычисляет значение ПК, которое будет загружено), а ИИ используется для абстрактной оценки фрагмента двоичного кода..
Это сводится к "Эффективность против точности".
Анализ потока данных пытается объединить данные пути гораздо больше, чем абстрактная интерпретация. Абстрактная интерпретация проходит по всем путям, сохраняя значения данных абстрактными.