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

Причем, если для подсчета ссылок в рантайме, решения существуют, то контроль переполнения стека невозможно сделать не только во время анализа исходного текста программы, но это практически невозможно и во время выполнения приложения! Ведь ошибка переполнение стека (stack overflow) - это всегда фатально, так как не существует способа поймать и обработать эту ошибку изнутри выполняемой программы, чтобы потом продолжить её выполнение как ни в чем не бывало.

Существует ли хотя бы теоретическая возможность защититься от ошибок переполнения стека и сделать из нее обычную ошибку (исключение), которую можно поймать (обработать) в самом приложении, чтобы была возможность продолжить выполнение программы без боязни последующей ошибки сегментации (segmentation fault) или повреждения стека (stack smashing)?

Пропустить лирику и перейти сразу к описанию решения

Немного технической информации о стеке

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

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

Именно поэтому переполнение стека практически всегда заканчивается аварийной остановкой потока или всего процесса. Допускается лишь корректное завершение приложения с отчётом/дампом памяти, без продолжения работы программы.

Проблема усугубляется еще и тем, что вычислить размер стека для функции во время анализа AST невозможно в принципе, так как это информация исключительно времени компиляции:

• Размер стека у функции может зависеть от входных данных функции (например alloca и VLA в языке С)

• Компилятор может добавлять неиспользуемое пространство между переменными для их выравнивания (Padding).

• На стеке сохраняются регистры, которые функция должна восстановить перед выходом (callee-saved registers), адрес возврат из функции и возвращаемые данные. Причем это все зависит не только от особенностей конкретной аппаратной платформы, но и от соглашения о вызовах функции.

• Компилятор может создавать безымянные временные переменные на стеке для хранения промежуточных результатов вычислений.

• Оптимизатор может полностью удалить некоторые переменные или хранить их только в регистрах, не используя для этого память в стеке.

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

Причем информация о размере стека функции обычно не доступна и во время выполнения приложения, ведь программа - это машинные инструкции и чтобы узнать размер используемого стека у конкретной функции, для этого нужно декодировать (дизассемблировать) её код для анализа.

Причины переполнения стека и механизмы защиты

В основе теории алгоритмов лежит абстрактная машина Тьюринга, которая имеет бесконечные вычислительные ресурсы (бесконечная память и не ограниченное время выполнения), благодаря чему допускаются любые алгоритмы, в том числе и с бесконечной глубиной рекурсии.

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

Поэтому размер стека всегда задается заранее:

• При компоновке/загрузке процесса в оперативную память или при создании потока приложения.

• Максимальный размер стека резервируется на уровне ОС и не может быть увеличен в ходе жизни потока (хотя иногда и предпринимаются попытки динамически увеличивать размер стека во время работы приложения, Segmented Stacks in LLVM и Split Stacks in GCC)

• В некоторых языка программирования рантаймы могут устанавливать пользовательские размеры стеков, но это не изменяет ограничений для системного потока и всё равно упирается в общий предел памяти.

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

Реализация защиты стека от переполнения для С++

Исходный код проекта для предотвращения аварийного завершения работы приложения из-за переполнения стека можно посмотреть на GitHub/stack-check.

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

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

Для ручной маркировки функций и методов классов, перед вызовом которых требуется проверка свободного места на стеке, используются пользовательские атрибуты C++ которые раскрываются с помощью макросов STACK_CHECK_SIZE(size) и STACK_CHECK_LIMIT :

• Атрибут STACK_CHECK_SIZE(size) принимает один аргумент в виде целого числа - размер свободного пространства на стеке, который будет автоматически проверяться перед вызовом защищаемой функции.

• Атрибут STACK_CHECK_LIMIT тоже проверяет размер свободного пространства на стеке, который задаётся при компиляции приложения. Размер использования стека для каждой функции можно выяснить, указав при компиляции опцию -fstack-usage, которая сохраняет в файле *.su список всех функций и требуемый для них размер стека.

Автоматическую вставку кода перед защищаемой функцией можно отменить. Для этого требуется вставить в C++ коде вызов вспомогательного статического метода ignore_next_check(const size_t), которому передаётся количество следующих вставок кода, которые будут пропущены (удалены) из генерируемого (исполняемого) файла.

Пример кода для использования библиотеки:

#include "stack_check.h"

using namespace trust;
const thread_local stack_check stack_check::info;

// Функция без автоматической проверки стека от переполнения
int func() {
    ...
}
 

// Перед каждым вызовом функции будет вставлен код проверки указанного свободного места на стеке
[[stack_check_size(100)]]
int guard_size_func() {
char data[92];
    ...
}

// Перед каждым вызовом функции будет проверяться минимальный размер свободного места на стеке
STACK_CHECK_LIMIT
int guard_limit_func() {
    ...
}

int main() {

    // Тут будет автоматически добавлен код для контроля стека от переполнения
    guard_size_func();
     
    
    stack_check::ignore_next_check(1); // Следующая автоматическая вставка проверки стека будет проигнорирована
    guard_size_func();
     
    
    // Тут будет автоматически добавлен код для проверки минимального размера свободного места на стеке
    guard_limit_func();
     
    stack_check::check_overflow(10000); // Ручная проверка свободного места на стеке
    func();
    
    return 0;
}

После чего файл компилируется с подключением clang плагина:

$ clang++ -std=c++20 -Xclang -load -Xclang stack_check_clang.so -Xclang -add-plugin -Xclang stack_check -lpthread filename.cpp

Детали реализации

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

Причём для целей автоматического контроля (для функций, отмеченных атрибутом stack_check_size или stack_check_limit) минимальный размер свободного пространства на стеке не может быть меньше определённого фиксированного порога, который требуется для создания программного исключения с информацией об ошибке. Размер такого порога зависит от реализации, и на него влияет целевая платформа, операционная система, степень оптимизации программы и прочие факторы.

Основная функциональность контроля переполнения стека находится в классе trust::stack_check. Информация о размере стека хранится в статических полях класса, индивидуально для каждого потока (Thread Local - локальное хранилище потоков, TLS), что позволяет однократно запрашивать параметры стека для каждого потока при инициализации структуры, а при проверке размера свободного места на стеке с помощью метода stack_check::check_overflow(N) сравнивать текущий указатель стека с нижней границей выделенной под стек области памяти.

Для использования библиотеки в приложении необходимо определить статическую переменную const thread_local trust::stack_check trust::stack_check::info, а для указания минимального лимита свободного пространства на стеке присвоить соответствующее значение макросу STACK_SIZE_LIMIT.

Накладные расходы и влияние на скорость работы программы

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

В качестве "измерителя скорости" использовал программу нахождения простых чисел рекурсивным методом из файла prime_check.cpp (в качестве тестов также пробовал ханойские башни и рекурсивный алгоритм подсчёта суммы цифр у длинного числа, но глубина стека для проверки переполнения в первом случае требует очень большой продолжительности работы алгоритма, а запись длинного числа, при котором возникает переполнение стека, занимает несколько экранов, что тоже неудобно для целей тестирования).

$ ./prime-check-O3
Usage: ./prime-check-O3 <start_number> [count]

$ ./prime-check-O3 9999999999999999
Stack overflow exception at: 104588 call depth.
Stack top: 0x7fffdc634000 bottom: 0x7fffdbe36000 (stack size: 8380416)
Query size: 10000 end frame: 0x7fffdbe386a0 (free space: 9888)

$ ./prime-check-O3 10000000000 1000
10000000019
10000000033
10000000061
...
10000022899
10000022909
Max recursion depth SAFE: 100000
Number of recursive calls SAFE: 117539009
Execution time SAFE: 18227634 microseconds

Max recursion depth: 100000
Number of recursive calls: 117539009
Execution time: 17925080 microseconds
Difference in execution time: 1.68788 %

Оценка влияния контроля переполнения стека на скорость работы приложения: без оптимизации (-O0) - время выполнения увеличивается примерно на 1%-5%, а при максимальной оптимизации (-O3) - примерно на 0,5-2% (общее время выполнения приложения около 20 секунд).

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

Причем тут ИИ ?

Честно признаюсь, что даже имея за плечами некоторый опыт разработки плагинов для clang, без использования LLM я бы такой проект не осилил за столь короткий срок (около месяца работы в фоне).

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

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

Все попытки организовать работу по другому на полной кодовой базе закончились фиаско. Любые LLM начинали терять контекст, переключались на второстепенные, а часто и не существующие проблемы. После чего проекта и вовсе ломался, так как LLM решала проверить систему сборки, для чего делала "заглушку", т.е. удаляла существующий рабочий код, убеждалась, что сборка проходит нормально и все начиналось по кругу.

При долгом использовании LLM стала особенно раздражать эмоциональное поощрение пользователей и попытки задавать уточняющие вопросы: "Вы задали хороший вопрос", "Вы правильно сформулировали проблему", "Спасибо за замечания. Пожалуйста уточните ...", а так же встраиваемая реклама собственных решений:

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

Я сейчас вообще перестал вручную писать скрипты, править конфигурационные файлы для VSCode или разбираться с ошибками в CMakeLists.txt. Конечно я не думаю, что LLM в скором времени и в самом деле смогут заменить программиста, но реально облегчить работу разработчиков они могут уже сейчас.