PEP 651 – 견고한 스택 오버플로 처리

Author:

Mark Shannon <mark at hotpy.org>

Status:

Rejected

Type:

Standards Track

Created:

18-Jan-2021

Post-History:

19-Jan-2021

---

Table of Contents

• 거부 공지
• 초록
• 동기
• 근거
• 명세
  • StackOverflow 예외
  • RecursionOverflow 예외
  • C 스택에서 Python 스택 분리하기
  • 다른 구현
  • C-API
    • Py_CheckStackDepth()
    • Py_EnterRecursiveCall()
    • PyLeaveRecursiveCall()
• 하위 호환성
• 보안 영향
• 성능 영향
• 구현
  • C 스택 사용량 모니터링
  • C 스택을 소비하지 않는 Python 간 호출
• 기각된 아이디어
• 미해결 문제
• Copyright

번역·라이선스 안내

이 비공식 한국어 번역은 원문 Copyright 절의 Public Domain or CC0-1.0, whichever is more permissive 조건에 따라 제공합니다. 원저자와 공식 원문은 그대로 표시합니다. 수정되지 않은 기준 원문 · 공식 최신판

거부 공지

이 PEP는 파이썬 운영 위원회에서 거부되었습니다.

초록

이 PEP는 Python이 머신 스택 오버플로를 폭주하는 재귀와 다르게 다루어야 한다고 제안합니다.

이렇게 하면 프로그램이 필요에 맞게 최대 재귀 깊이를 설정할 수 있고, 추가적인 안전성도 보장됩니다.

이 PEP가 수락되면 다음 프로그램은 끝까지 안전하게 실행됩니다:

sys.setrecursionlimit(1_000_000)

def f(n):
    if n:
        f(n-1)

f(500_000)

그리고 다음 프로그램은 VM 충돌을 일으키지 않고 StackOverflow를 발생시킵니다:

sys.setrecursionlimit(1_000_000)

class X:
    def __add__(self, other):
        return self + other

X() + 1

동기

CPython은 폭주하는 재귀와 C 스택 오버플로를 모두 막기 위해 하나의 재귀 깊이 카운터를 사용합니다. 하지만 폭주하는 재귀와 머신 스택 오버플로는 서로 다른 문제입니다. 머신 스택 오버플로를 허용하면 보안 취약점이 될 수 있지만, 재귀 깊이를 제한하면 Python에서 일부 알고리즘을 사용하지 못하게 될 수 있습니다.

현재는 프로그램이 깊은 재귀를 필요로 하면 허용되는 최대 재귀 깊이를 직접 관리해야 하며, 올바르게 실행되는 데 필요한 최솟값과 메모리 보호 오류를 피할 수 있는 안전한 최댓값 사이 구간에 그 값을 맞출 수 있기를 바랄 수밖에 없습니다.

C 스택 오버플로 검사를 재귀 깊이 검사와 분리하면, 순수 Python 프로그램은 필요한 만큼의 재귀를 사용하면서도 안전하게 실행될 수 있습니다.

근거

CPython은 현재 가상 머신에서 일어날 수 있는 위험한 스택 오버플로를 막는 데에도, 파이썬 프로그램의 폭주하는 재귀를 막는 데에도 하나의 한도에 의존합니다.

이는 C 호출 스택과 Python 호출 스택을 결합한 구현에서 비롯된 결과입니다. 이 결합을 끊으면 CPython의 사용성과 안전성을 모두 개선할 수 있습니다.

재귀 한도는 폭주하는 재귀를 막기 위해 존재하는 것이며, 가상 머신의 무결성이 이에 의존해서는 안 됩니다. 마찬가지로, 재귀가 구현 세부 사항 때문에 제한되어서는 안 됩니다.

명세

두 개의 새 예외 클래스 StackOverflow와 RecursionOverflow가 추가되며, 둘 다 RecursionError의 서브클래스입니다

StackOverflow 예외

인터프리터나 내장 모듈 코드가 C 스택이 안전 한도에 도달했거나 가까워졌다고 판단할 때마다 StackOverflow 예외가 발생합니다. StackOverflow는 RecursionError의 서브클래스이므로, RecursionError를 처리하는 모든 코드는 StackOverflow도 처리합니다

RecursionOverflow 예외

Python 함수 호출로 인해 재귀 한도를 초과하면 RecursionOverflow 예외가 발생합니다. 이는 RecursionError를 발생시키는 현재 동작에서 약간 바뀐 것입니다. RecursionOverflow는 RecursionError의 서브클래스이므로, RecursionError를 처리하는 모든 코드는 이전과 같이 계속 동작합니다.

C 스택에서 Python 스택 분리하기

위의 보장을 제공하고 이전에 동작하던 모든 프로그램이 계속 동작하도록 하려면, Python 스택과 C 스택을 분리해야 합니다. 즉, Python 함수에서 Python 함수를 호출할 때는 C 스택 공간을 소비하지 않아야 합니다. 내장 함수를 호출하거나 내장 함수에서 호출할 때는 계속해서 C 스택의 공간을 소비합니다.

C 스택의 크기는 구현에 따라 정의되며, 기계마다 다를 수 있습니다. 스레드마다 다를 수도 있습니다. 그러나 재귀 한도를 이전 기본값으로 설정한 상태에서 실행될 수 있었던 코드는 모두 계속 실행될 것으로 기대됩니다.

Python의 많은 연산은 C 수준에서 어떤 형태로든 호출을 수행합니다. 이러한 연산 대부분은 계속해서 C 스택을 소비하며, 통제되지 않는 재귀가 발생하면 StackOverflow 예외를 일으킵니다.

다른 구현

다른 구현은 재귀 한도가 어떤 값으로 설정되어 있든 안전하게 실패해야 합니다.

구현이 Python 스택을 하부 VM 스택이나 하드웨어 스택에 결합하는 경우, 재귀 한도를 초과했지만 하부 스택이 오버플로되지 않았을 때는 RecursionOverflow 예외를 발생시켜야 합니다. 하부 스택이 오버플로하거나 오버플로에 가까워지면 StackOverflow 예외를 발생시켜야 합니다.

C-API

새 함수 Py_CheckStackDepth()가 추가되고, Py_EnterRecursiveCall()의 동작이 약간 수정됩니다.

Py_CheckStackDepth()

int Py_CheckStackDepth(const char *where)는 C 스택 오버플로의 즉각적인 위험이 없으면 0을 반환합니다. C 스택이 오버플로에 가까우면 -1을 반환하고 예외를 설정합니다. where 매개변수는 Py_EnterRecursiveCall()의 where 매개변수와 같은 방식으로 예외 메시지에 사용됩니다.

Py_EnterRecursiveCall()

Py_EnterRecursiveCall()은 이 함수가 현재 수행하는 작업을 하기 전에 Py_CheckStackDepth()를 호출하도록 수정됩니다.

PyLeaveRecursiveCall()

Py_LeaveRecursiveCall()은 변경되지 않습니다.

하위 호환성

이 기능은 Python 수준에서 완전한 하위 호환성을 갖습니다. 기계어 디버거와 같은 일부 저수준 도구는 수정해야 합니다. 예를 들어, Python용 gdb 스크립트는 C 프레임 하나당 Python 프레임이 둘 이상 있을 수 있다는 점을 고려해야 합니다.

Py_EnterRecursiveCall(), PyLeaveRecursiveCall() 함수 쌍을 사용하는 C 코드는 계속해서 올바르게 동작합니다. 또한 Py_EnterRecursiveCall()은 StackOverflow 예외를 발생시킬 수 있습니다.

새 코드는 재귀 한도와 관련하여 Python 함수 호출로 간주되기를 원하는 경우가 아니라면 Py_CheckStackDepth() 함수를 사용해야 합니다.

Cython이 생성한 함수와 같은 “Python과 유사한” 코드는 Py_EnterRecursiveCall()을 사용하고, 그 밖의 코드는 Py_CheckStackDepth()를 사용할 것을 권장합니다.

보안 영향

더 이상 재귀를 통해 CPython 가상 머신을 충돌시킬 수 없게 됩니다.

성능 영향

성능에 미치는 영향이 클 가능성은 낮습니다.

추가로 필요한 로직은 아마도 성능에 아주 작은 부정적 영향을 줄 것입니다. C 스택 사용량이 줄어들어 참조 지역성이 개선되므로 약간의 긍정적 영향이 있을 것입니다.

전체적인 효과가 긍정적일지 부정적일지 예측하기는 어렵지만, 순효과는 측정할 수 없을 만큼 작을 가능성이 매우 높습니다.

구현

C 스택 사용량 모니터링

C 스택 오버플로가 임박했는지 가늠하기는 어렵습니다. 따라서 보수적으로 접근해야 합니다. 스택의 안전한 경계를 정해야 하는데, 이는 이식 가능한 C 코드로는 할 수 없는 일입니다.

주요 플랫폼에서는 플랫폼별 API를 사용하여 정확한 스택 경계를 구할 것입니다. 그러나 그 밖의 소수 플랫폼에서는 어느 정도 추측이 필요할 수 있습니다. 좋지 않게 들릴 수도 있지만, C 스택의 크기가 _PyEval_EvalFrameDefault에서 _PyEval_EvalFrameDefault까지 이어지는 호출 체인에 필요한 스택 공간의 최소 1000배라고 추측하는 현재 상황보다 나쁘지 않습니다.

이는 경우에 따라 가능한 재귀 깊이가 줄어들 수 있음을 의미합니다. 하지만 많은 호출이 C 스택을 전혀 사용하지 않게 되므로, 일반적으로는 가능한 재귀 깊이가 늘어날 것입니다.

C 스택의 한계를 정하는 일반적인 접근 방식은 호출 체인에서 가능한 한 이른 시점에 현재 C 프레임 안의 주소를 얻는 것입니다. 그런 다음 그 주소에 어떤 상수를 더하여 한계를 추측할 수 있습니다.

C 스택을 소비하지 않는 Python 간 호출

인터프리터에서 호출은 CALL_FUNCTION, CALL_FUNCTION_KW, CALL_FUNCTION_EX, CALL_METHOD 명령어가 처리합니다. 이 명령어들의 코드는 Python 함수나 메서드가 호출될 때 C 수준에서 호출하는 대신, 인터프리터가 피호출자의 프레임을 설정하고 평소처럼 해석을 계속하도록 수정될 것입니다.

RETURN_VALUE 명령어는 그 반대 작업을 수행합니다. 다만 현재 프레임이 인터프리터의 진입 프레임인 경우에는 평소처럼 반환합니다.

기각된 아이디어

아직 없습니다.

미해결 문제

아직 없습니다.

Copyright

This document is placed in the public domain or under the CC0-1.0-Universal license, whichever is more permissive.