Возможно ли для языка программирования уверенно предотвратить неопределенное поведение при переполнении стека?

Question

Учитывая следующие допущения:

• Мы не можем проверять указатель стека (%rsp) перед каждой отдельной push или sub операцией
• Мы не можем вычислить максимум размер стека во время компиляции (например, наш язык программирования поддерживает рекурсию)

Возможно ли иметь язык программирования, который предотвращает неопределенное поведение в 100% случаев переполнения стека?

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

Мои рассуждения ошибочны? Есть ли надежный способ для языков программирования предотвратить неопределенное поведение при переполнении стека?

Answer 1

Если у вас MMU, вы можете получить четко определенное безопасное поведение: переполнение стека вызывает ошибку неверной страницы (Ошибка сегментации в POSIX). Для этого требуется некоторая помощь от ОС или ручное отображение Страница только для чтения ниже предела роста стека. Просто убедитесь, что вы касаетесь каждой страницы пространства стека по мере его увеличения. (Или один зонд на 64 кБ, если вы резервируете больше места для защиты). Вы можете поймать SIGSEGV, если хотите в POSIX OS. Другие ОС могут иметь другие механизмы.

---

G CC -fstack-check делает это довольно дешево, в сочетании с ОС, имеющей «защитную область» непопечатанных страниц под отображением стека. (Точнее говоря, ниже максимального предела роста для стека, поэтому стек может продолжать расти, но не за пределами этой защитной области.)

Защитная область 1 МБ (текущее значение Linux по умолчанию) обычно достаточно, чтобы вам даже не нужны стековые зонды для предотвращения ошибок stack cla sh, когда стек перекрывается с динамическим выделением c под стеком. Но глючная / уязвимая программа, которая использует неконтролируемый пользовательский ввод в качестве размера для alloca или C99 VLA, может пропустить весь путь через защитную область.

И Windows всегда требуют «стековые зонды» ( касание памяти на каждой странице размером 4 КБ для увеличения стека большого или переменного размера, как gcc -fstack-protector ). Windows требует, чтобы это вообще вызывало рост стека; он не увеличит ваш стек, если вы коснетесь нескольких страниц ниже последней использованной страницы стека.

Linux переполнение стека процесса локальными переменными (защита стека) содержит больше подробностей.

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

Общая стоимость времени выполнения равна всего лишь oop при входе в функцию (и при каждом выделении или области, включающей VLA), которая затрагивает память шагом 4 кБ, пока не пройдет расстояние в стеке. рост. Если этот размер известен во время компиляции, он может быть полностью развернут / очищен только для одной или нескольких инструкций.

Или в большинстве функций, которые имеют только несколько локальных объектов, не включая массив огромного или переменного размера, нет наверху вообще. Выполнение другого вызова функции включает запись в стековую память для сохранения адреса возврата, либо как часть x86 call, либо при входе в функцию для ISA RIS C, которые передают адрес возврата в регистр ссылок. Таким образом, даже целая цепочка функций, которые выделяют небольшие и средние массивы и не касаются их, не могут пропустить указатель стека за защитной страницей. Сохранение / восстановление адреса возврата в / из стека фактически является пробной задачей.

Answer 2

Язык программирования может быть довольно легко создан для поддержки рекурсии, в то же время обеспечивая stati c гарантии о переполнении стека при условии, что любой цикл в графе вызовов защищен проверкой "if (__STACK_SAFE)" и делает только рекурсивный вызовы функций в "истинной" ветке. За исключением случаев вызова внешних функций вне контроля реализации, программисту не нужно было бы указывать использование стека.

Реализация C могла бы выполнить sh с относительно минимальными изменениями:

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

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

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

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

5. Создайте этот выходной файл и свяжите его с основная программа.

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

Например, парсер рекурсивного спуска может начинать каждую функцию с проверки безопасности стека и, в случае недостаточности стека, устанавливать и возвращать флаг ошибки и возвращать. Некоторые другие формы рекурсивного алгоритма могут быть в состоянии установить флаг «неполное действие» и переключиться на резервную стратегию, которая будет медленнее рекурсивной, но, тем не менее, будет работать. Например, реализация QuickSort, которая рекурсивно выполняет быструю сортировку половин раздела (да, я знаю, что Quicksort обычно лучше всего реализован не рекурсивно), могла бы просто использовать сортировку вставками для обработки каждой половины.

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