Таблица символов

Таблица символов может существовать только в оперативной памяти во время процесса трансляции, либо быть встроенной в выходные данные трансляции, например, в объектный файл ABI — для последующего использования. Например, таблица символов может использоваться во время отладки или как источник сведений при формировании диагностического отчёта во время или после выполнения программы^[2].

Минимальная информация, содержащаяся в таблице символов, используемой транслятором и промежуточным представлением, включает в себя имя символа и его местоположение или адрес. Для компиляторов, целевыми платформами которых являются системы с поддержкой перемещаемости кода, таблица также содержит соответствующие атрибуты (абсолютный, релокейтабельный(перемещаемый) и т. д.) и необходимые сведения для обработки таких символов. В таблицах символов для языков высокого уровня могут храниться сведения о типе (строка, целое число, число с плавающей запятой и др.), размере, измерениях и границах символа. Не вся эта информация включается в выходной файл, но может предоставляться для целей отладки. Во многих случаях к каждому символу хранится перекрёстная ссылка. Большинство компиляторов формируют итоговые отчёты, где перечисляют информацию из таблицы символов и перекрестных ссылок^[1]. В современных системах для поддержки позиционно-независимого кода (PIC) и рандомизации размещения адресного пространства (ASLR) применяются атрибуты относительной адресации (например, PC-relative). Вместо жёсткой привязки к абсолютным адресам используется слой косвенности через глобальную таблицу смещений (GOT) и таблицу связывания процедур (PLT). GOT хранит фактические адреса внешних символов, которые обновляются динамическим загрузчиком во время выполнения, а PLT обеспечивает механизм «ленивого связывания» для вызова внешних функций^[3]..

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

Компилятор может использовать единую большую таблицу символов для всех символов или раздельные (иерархические) таблицы для каждого блока видимости. Например, в языках с блочной структурой, таких как ALGOL или PL/I, символ «p» может быть объявлен неоднократно — в разных процедурах и с разными атрибутами. Область видимости каждого объявления — это участок программы, где использование «p» разрешается к этой конкретной декларации. Таблица символов должна обеспечивать различие между такими случаями.

Часто таблицы символов реализуются в виде хеш-таблиц. Время поиска в хеш-таблице не зависит от количества хранимых элементов, что делает этот подход эффективным при большом их числе. Кроме того, это упрощает классификацию литералов — необходимая информация включается в вычисление хеш-ключа^[4].

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

Помимо классических хеш-таблиц, для задач автодополнения кода применяются префиксные деревья (Trie), так как они эффективно поддерживают поиск по префиксу^[5][6].

Объектный файл содержит таблицу символов используемых идентификаторов, видимых извне. При компоновке нескольких объектных файлов компоновщик идентифицирует и разрешает такие символы. Обычно все неопределённые внешние символы ищутся в одной или нескольких библиотеках объектных файлов. Если найден модуль, определяющий требуемый символ, он связывается с первым объектным файлом, а все новые неопределённые идентификаторы добавляются к списку для поиска. Этот процесс продолжается до тех пор, пока все внешние ссылки не будут разрешены. Если после завершения процесса остались неразрешённые ссылки, это считается ошибкой.

В отличие от классических объектных файлов, при оптимизации во время компоновки (Link Time Optimization, LTO) промежуточное представление сохраняет расширенные метаданные (например, граф вызовов и межпроцедурные ссылки) в специализированных секциях^[14].

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

Рассмотрим следующий фрагмент программы на языке C:

// Объявление внешней функции
extern double bar(double x);

// Определение публичной функции
double foo(int count)
{
    double sum = 0.0;

    // Суммирование значений bar(1) до bar(count)
    for (int i = 1; i <= count; i++)
        sum += bar((double) i);
    return sum;
}

Компилятор C, который анализирует этот код, как правило, сформирует как минимум следующие записи таблицы символов:

Кроме перечисленных, компилятор может добавить в таблицу служебные записи, генерируемые для промежуточных выражений (например, преобразование i в double), возвратных значений функций, меток перехода и т. п.

Пример таблицы символов можно найти в спецификации SysV ABI (англ. System V Application Binary Interface), где стандартизируется способ размещения символов в бинарных файлах. Это обеспечивает совместную работу различных компиляторов, компоновщиков и загрузчиков с символами в скомпилированных объектах.

SysV ABI реализован, например, в утилите англ. nm пакета GNU binutils. Формат таблицы включает отсортированное поле с адресом памяти, поле «тип символа» и идентификатор символа («имя»)^[15].

В спецификации формата ELF секции .symtab и .dynsym служат для хранения таблиц символов, но имеют разные технические характеристики. Секция .dynsym используется для динамического связывания, содержит только необходимые для динамического компоновщика символы, загружается в память при выполнении программы и сохраняется после выполнения команды strip. В отличие от неё, .symtab представляет собой полную таблицу символов (включая локальные), используется для статической компоновки и отладки, не требует загрузки в память и может быть удалена..

В утилите GNU англ. nm тип символа обозначается одной буквой. По общему правилу заглавные буквы обозначают глобальные (внешние) символы, а строчные — локальные (исключениями являются строчные «u», «v» и «w», которые используются для специальных глобальных символов)^[16]. Полный список кодов типов символов:

• A — абсолютное значение символа (не изменяется при дальнейшей линковке);
• B / b — неинициализированные данные (секция BSS);
• C / c — общий символ (common), представляющий неинициализированные данные;
• D / d — инициализированные данные;
• G / g — инициализированные данные для малых объектов;
• i — косвенная функция (для ELF) или символ реализации DLL (для PE);
• I — косвенная ссылка на другой символ;
• N — отладочный символ;
• n — данные только для чтения;
• p — информация для раскрутки стека;
• R / r — данные только для чтения;
• S / s — неинициализированные или нуль-инициализированные данные для малых объектов;
• T / t — исполняемый код (текстовая секция);
• U — неопределённый символ;
• u — уникальный глобальный символ (GNU-расширение);
• V / v — слабый объект (weak object);
• W / w — слабый символ (weak symbol), не помеченный как слабый объект;
• - — символ stabs (отладочная информация).

Язык программирования Python содержит широкие возможности для создания и анализа таблиц символов^[17]. Можно, например, проверять, является ли символ свободной или связанной переменной, к какому пространству имён относится, импортирован ли он и принадлежит ли к блочной или глобальной области видимости.

Построение таблицы символов в CPython выполняется в два прохода: первый проход по абстрактному синтаксическому дереву (AST) создаёт базовую структуру записей, а второй вычисляет области видимости и обрабатывает нелокальные переменные^[18].

В некоторых языках таблица символов может изменяться во время выполнения программы — позволяется создавать новые символы на лету. Примером такого языка является англ. Racket^[19].

Языки LISP и Scheme позволяют ассоциировать с каждым символом произвольные свойства^[20].

Язык Prolog во многом представляет собой язык обработки таблицы символов: символы называются атомами, а взаимосвязи между ними могут анализироваться логически. Похожая система реализована в OpenCog, где динамическая таблица символов («atomspace») служит для представления знаний.

В современных компиляторах и утилитах (например, GNU Binutils) для защиты от атак через манипуляцию таблицей символов применяются специализированные механизмы. Для предотвращения DoS-атак, связанных с переполнением стека из-за бесконечной рекурсивной вставки символов (например, уязвимость CVE-2018-10373), вводится жёсткое ограничение глубины рекурсии. Также используется арен-аллокация (arena-based allocation) для управления областями видимости, позволяющая выполнять массовую очистку памяти за константное время, и принципы Panic Mode для ограничения глубины восстановления при ошибках^[21].

Для защиты исполняемых файлов от реверс-инжиниринга применяется удаление отладочных символов (stripping) и обфускация. При удалении символов имена внутренних функций заменяются адресами памяти, что существенно усложняет статический анализ кода. При этом символы, необходимые для динамического связывания, сохраняются для обеспечения работоспособности программы. Дополнительно могут применяться автоматизированная обфускация на уровне промежуточного представления, ручное запутывание критичных участков кода и шифрование строковых констант^[22].

Механизмы защиты таблиц символов при динамическом связывании включают технологии RELRO (Relocation Read-Only). Partial RELRO делает часть таблицы глобальных смещений (GOT) доступной только для чтения после применения релокаций, оставляя секцию .got.plt доступной для записи для поддержки ленивого связывания. Механизм Full RELRO в сочетании с флагом BIND_NOW выполняет немедленное разрешение всех символов при запуске программы, делая всю таблицу GOT доступной только для чтения и полностью предотвращая атаки типа перезаписи GOT (GOT overwrite)^[23][24].

Угрозу безопасности также представляет манипуляция поиском символов через переменные окружения (например, LD_PRELOAD в Linux или DYLD_INSERT_LIBRARIES в macOS), что позволяет загружать сторонние библиотеки с более высоким приоритетом и перехватывать вызовы функций. Для предотвращения подобных атак используются флаги безопасности: в Linux при запуске привилегированных программ ядро передаёт флаг AT_SECURE, который очищает опасные переменные окружения, а в macOS аналогичную защиту обеспечивают механизмы System Integrity Protection (SIP) и Hardened Runtime. Кроме того, применяются механизмы верификации цифровых подписей и хешей библиотек перед их загрузкой (например, подсистемы IMA и EVM в Linux)^[25][26].