[자료구조] 스택 오버플로우, 스택 언더플로우 란?

스택 오버플로우와 스택 언더플로우가 뭔지 알아보자.

 

---

1. 스택 오버플로우 (Stack Overflow)

 

스택 오버플로우는 데이터 구조가 가득 차서 더 이상 데이터를 저장할 수 없는 상태에서 추가 데이터를 넣으려고 할 때 발생하는 오류이다.

 

발생 원인

 

• 재귀 함수의 과도한 호출: 가장 흔한 원인으로, 종료 조건이 없거나 잘못된 재귀 함수가 메모리 한계까지 호출 스택을 쌓음
• 큰 지역 변수: 함수 내에서 너무 큰 배열과 같은 지역 변수를 선언할 때 발생
• 깊은 함수 호출 체인: 함수가 다른 함수를 호출하고, 그 함수가 또 다른 함수를 호출하는 구조가 깊게 이어질 때

public class Main {

    public static void infiniteRecursion() {
        infiniteRecursion(); // 종료 조건 없음 - 스택 오버플로우 발생
    }

    public static void main(String[] args) throws Exception {
        infiniteRecursion();
    }
}

스택 오버플로우를 발생시키는 예제코드를 한번 보자.

• infiniteRecursion() 을 무한 재귀 시키는 코드이다.

해당 코드를 실행하면 StackOverflowError가 발생한다.

java.lang.StackOverflowError

 

 

결과

• 스택 오버플로우가 발생하면 프로그램이 즉시 종료된다.

보안 측면

• 버퍼 오버플로우 공격: 악의적인 사용자가 의도적으로 스택 오버플로우를 일으켜 임의 코드를 실행하게 할 수 있음
• Return-Oriented Programming (ROP): 스택 오버플로우를 이용한 고급 공격 기법

방지 방법

• 종료 조건 확인: 재귀 함수에 명확한 종료 조건 설정
• 스택 크기 제한 설정: 일부 컴파일러나 인터프리터에서는 스택 크기를 명시적으로 설정 가능
• 반복문 사용: 너무 깊은 재귀 호출이 예상되는 경우, 반복문으로 대체
• 메모리 동적 할당: 큰 배열과 같은 데이터 구조는 스택이 아닌 힙에 동적 할당

 

 

 

---

2. 스택 언더플로우 (Stack Underflow)

 

스택 언더플로우는 스택이 비어있는 상태에서 데이터를 꺼내려고 할 때 발생하는 오류이다.

 

발생 원인

 

• 잘못된 로직: 스택의 상태를 확인하지 않고 데이터를 꺼내려고 시도
• 동기화 문제: 멀티스레드 환경에서 스택 접근 제어가 적절히 이루어지지 않을 때
• 알고리즘 오류: 스택을 사용하는 알고리즘에서 push와 pop 연산의 불균형
• 경계 조건 처리 실수: 반복문이나 조건문에서 스택의 경계 조건을 잘못 처리

    public static void main(String[] args) throws Exception {
        Stack<Integer> stack = new Stack<>();
        // 빈 스택에서 pop 시도
        int value = stack.pop(); // EmptyStackException 발생
    }

 

스택 언더플로우를 발생시키는 코드이다.

해당 코드를 실행하면 java.util.EmptyStackException가 발생한다.

java.util.EmptyStackException

 

방지 방법

• 상태 확인: 모든 pop 연산 전에 isEmpty() 검사 수행
• 예외 처리: 언더플로우 발생 가능성이 있는 코드에 try-catch 블록 사용
• 안전한 API 사용: Java의 java.util.Stack 클래스처럼 내장된 예외 처리 기능이 있는 API 사용
• 디버깅: 스택 동작을 시각화하여 추적하는 디버깅 도구 활용
• 유닛 테스트: 경계 조건(빈 스택, 하나의 요소만 있는 스택 등)에 대한 테스트 작성

 

---

정리

특성	스택 언더플로우	스택 오버플로우
발생 조건	빈 스택에서 pop 시도	가득 찬 스택에 push 시도
일반적 빈도	상대적으로 적음	더 흔함
주요 원인	로직 오류, 경계 조건 처리 실수	무한 재귀, 큰 지역 변수
보안 영향	보통 낮음	높음 (버퍼 오버플로우 관련)
발견 난이도	테스트로 비교적 쉽게 발견	경우에 따라 발견 어려울 수 있음