Как работает абстрактный переводчик?

Question

Я пытаюсь построить абстрактный интерпретатор для C. Вероятно, не для всей грамматики, а только для ее подмножества. Я ранее спрашивал, на каком языке использовать. Прежде чем я продолжу, я хотел бы знать, как работает эта абстрактная интерпретация?

Я просмотрел ссылки на вики и ссылки на лекционные заметки. Я понял обоснование и теорию, стоящую за этим. У меня есть мой анализ разработан. Часть, которую я совершенно не в состоянии понять, это как интерпретировать код. То есть у меня был исходный код. У меня сейчас это предварительно обработано. Я также выполнил некоторую нормализацию кода, которая требуется для моего анализа. Теперь, как мне выполнить код построчно и извлечь данные из него, пока я продолжаю его выполнять? (Пожалуйста, скажите мне, если это невозможно. Или есть способ правильно выполнить программу, которая достигнет моей цели). Я смотрю на сбор информации, такой как адрес памяти динамически выделяемого пространства, адреса возврата вызова функции.

Мне предлагали CIL ранее, CIL - это в основном инструмент преобразования, преобразующий код в некоторую нормализованную форму, учитывающий многие аномалии, но я не смог получить никакой информации, относящейся к моей проблеме.

У меня вопрос, как извлечь информацию построчно и какой язык предпочтительнее? Императивные языки или функциональные языки? Я довольно много дней гуглял за информацией об этом, но бесполезно. Любые ссылки также высоко ценятся. Спасибо.

РЕДАКТИРОВАТЬ: У меня все еще есть некоторые сомнения. Я получил часть, где мы пытаемся создать виртуальную среду. Позвольте мне объяснить, что я пытаюсь сделать, чтобы это помогло обсуждению. Я в основном пытаюсь сделать анализ указателя, который в основном концентрируется на арифметике указателя. Теперь предположим, что у меня есть целочисленный указатель, и я делаю арифметику указателя, тогда я не могу быть уверен, что указатель все еще указывает на действительные данные.

Из того, что вы говорите, я понимаю, что нам нужно выделить места для переменных, но как насчет значений. если у меня есть что-то вроде ниже

int a=10;<br> int *p = &a;<br> p = p+4;

Здесь известны значения a и константы '4'. Что, если я получу значение от пользователя или файла. В таком случае мне нужно выполнить саму программу. В то же время мне нужно захватить данные, как адрес. ниже,

int *p =(int *) malloc (sizeof(int));<br> *p= 15;<br> cout<<*p;<br> p = p+ino//some user input value;<br> cout<<*p;<br>

Таким образом, в основном код должен быть выполнен, но более поздняя часть решения звучала больше как синтаксический анализ файла C. Пожалуйста, поправьте меня, если я ошибаюсь.

Answer 1

Предполагая, что вы действительно говорите об абстрактной интерпретации, а не просто о интерпретации C ...

Абстрактная интерпретация опирается на две вещи - абстрактную область, решетку конечной высоты и абстрактную семантику, в результате чего применение семантики строки к значению в домене из строки перед этим должно создать новое значение в области, такой же высоты или выше.

т.е. Если для вашего домена установлено значение {1,2,3,4}, а для ввода - {1,2,3}, то единственными допустимыми выходами являются {1,2,3} или {1,2,3,4} (при условии обычного упорядочения набора)

Затем вы продолжаете, выполняя рекурсию с фиксированной точкой в ​​каждой строке и сохраняя выходные данные семантики со строкой и семантику в конце каждой функции с определением функции. То, как вы выбираете домен и интерпретируете набор, который в итоге получается, в огромной степени зависит от того, какой анализ вы пытаетесь сделать, но, как я понимаю, это план ...

Я должен сказать, что я не эксперт в этом, но некоторые из моих коллег-исследователей говорили со мной об этом в прошлом, и это понимание, с которым я пришел ...

Кроме того, вы также можете легко запустить анализ в обратном направлении - начиная с конца функции и двигаясь вперед, и это будет более подходящим для некоторых видов анализа ...

Answer 2

CIL способен выполнять SSA-преобразование .Программа в форме SSA удивительно проста для рассуждений о и частичной оценки - вам просто нужно подставить именованные значения, игнорируя или объединяя значения, полученные из phi узлы.Итак, чтобы превратить CIL в правильный абстрактный интерпретатор, вам нужно только добавить пару преобразований после SSA (который уже существует).В качестве альтернативы, вы можете делать такого рода преобразования поверх LLVM IR, произведенного Clang.

Answer 3

Из того, как вы излагаете свою проблему, кажется, что вы говорите о интерпретации , а не абстрактной интерпретации . Интерпретация просто означает, что вы берете код C и запускаете его самостоятельно, в вашем случае, чтобы извлечь некоторую информацию из того, что происходит во время выполнения. Абстрактная интерпретация относится к процедуре статического анализа, в которой вы пытаетесь понять, на что способна программа, возможно, в целях оптимизации или, возможно, чтобы попытаться доказать правильность или отсутствие ошибок. Конечно, я могу быть совершенно неправ в этом, и в этом случае вы можете игнорировать этот ответ.

Если вы пытаетесь написать интерпретатор, вам, вероятно, потребуется настроить виртуальную среду выполнения, в которой будет работать программа. То есть вы, вероятно, захотите установить гигантский массив байтов, который будет служить памятью программы, и вам потребуется поддерживать свой собственный указатель стека и распределитель кучи. Затем вы можете выполнить программу, переходя построчно и изменяя состояние этой среды в зависимости от конкретной строки кода, которую вы выполняете. Например, выполнение оператора типа

int a;

будет работать путем увеличения указателя стека на четыре байта при выполнении чего-то вроде

a = 137;

будет искать, на какую часть массива глобальной памяти ссылается a, а затем перезаписывает байты четырехбайтовым значением для 137. С этой точки зрения отслеживание того, что происходит во время выполнения, должно быть относительно простым - до того, как ваш интерпретатор выполнит какое-либо конкретное утверждение или оценит выражение, вы можете записать в него любые соответствующие подробности.

Обратите внимание, что это не будет легко. Вам нужно будет вручную распределять и очищать кадры стека, вести счетчик программ и т. Д. Однако это звучит очень весело, и я желаю вам удачи с ним!