Избавляемся от ошибок Segmentation fault из-за переполнения стека в С++

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

Причем, если для подсчета ссылок в рантайме, решения существуют, то контроль переполнения стека невозможно сделать не только во время анализа исходного текста программы, но это практически невозможно и во время выполнения приложения! Ведь ошибка переполнение стека (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 в скором времени и в самом деле смогут заменить программиста, но реально облегчить работу разработчиков они могут уже сейчас.