[C] Stack Buffer Overflow와 Canary

Q2: Stack Buffer Overflow와 카나리

파스칼 삼각형에서의 Stack Buffer Overflow 문제

https://github.com/Jihyun0511/SW-AI-W05/blob/master/challenges/02_stack_buffer_overflow/bug.c

SW-AI-W05/challenges/02_stack_buffer_overflow/bug.c at master · Jihyun0511/SW-AI-W05

 

파스칼 삼각형

숫자를 삼각형 모양으로 배치한 것으로, 다음과 같은 규칙을 가진다.

- 맨 위는 항상 1
- 양쪽 가장자리는 항상 1
- 가운데 숫자는 바로 위의 두 숫자의 합
              1
            1   1
          1   2   1
        1   3   3   1
      1   4   6   4   1
    1   5  10  10   5   1
파스칼의 삼각형을 2차원 배열로 정리하면 하기와 같다.
   1
   1 1
   1 2 1
   1 3 3 1

 

파스칼의 삼각형과 같은 삼각형 모양의 데이터를 2차원 배열에 넣게 된다면, 삼각형의 절반은 빈 공간으로 남아 메모리가 낭비된다.

 

삼각 인덱싱

따라서 해당 데이터를 1차원 배열로 압축하여 메모리 효율을 높일 수 있다.

2차원 배열의 arr[i][j]는 1차원 배열의 arr[i*(i+1)/2 + j] 에 저장할 수 있다.

 

파스칼의 삼각형은 0행에 1개, 1행에 2개, 2행에 3개…

i번째 번째 행이 시작하기 전까지 1 + 2 + 3 + … + i 개의 원소가 있다.

따라서 i 행의 1차원 배열에서의 첫 위치는 i * (i + 1) / 2 이다.

행 내부에서는 j 번째 칸에 위치하고 있으므로,

2차원 배열의 arr[i][j]는 1차원 배열의 arr[i*(i+1)/2 + j] 에 저장할 수 있다.

 

SIGABRT, Aborted

메모리가 오염되었으니 더 이상 실행하는 것은 위험하다고 판단하여, 프로그램이 스스로 강제 종료(Abort) 신호를 보내 멈춘 것!

 

왜 이런 일이?: Stack Buffer Overflow

파스칼 삼각형의 0행부터 13행까지, 총 14개의 행을 담을 수 있는 105칸짜리 배열이 마련되어 있다.

하지만 코드의 반복문 for (int i = 0; i <= 14; i++) 에서 행 루프가 i <= ROWS 로 돌아서 행이 총 15개가 생성된다.

초과 생성된 14행(i = 14)의 인덱스는 SIZE + j가 되어 스택 배열의 끝을 넘어가게 된다. [Stack Buffer Overflow]

사용할 수 있는 인덱스는 0부터 104까지였는데, 14행을 계산하면서 존재하지 않는 105번 인덱스 영역부터 강제로 값을 써넣고 허용된 메모리 공간을 벗어나게 된다.

 

Stack Canary의 훼손

컴파일러는 이러한 메모리 초과 덮어쓰기를 감시하기 위해, 배열이 끝나는 메모리 지점 바로 뒤에 Canary라는 임의의 값을 숨겨둔다.

14행의 값을 배정된 공간을 초과해서 넣다 보니 카나리 또한 14행의 값으로 덮어씌워지게 되고, 함수가 끝날 때 시스템이 해당 현상을 감지하고 메모리 침범(Stack Smashing)에 대한 경고 메세지를 띄우게 되는 것이다.

해당 경고 메세지를 받고, 프로그램은 메모리가 오염되었기 때문에 더 이상 실행하는 것은 위험하다고 판단하여 강제 종료(Abort)하게 된다.

1. main 함수가 종료되기 직전, 스택에 숨겨둔 카나리아가 그대로 유지되어 있는지 검사
2. 105번 인덱스를 넘어가는 덮어쓰기로 인해 카나리아 값이 변경된 것을 감지하면, __stack_chk_fail() 함수가 실행
3. 이 함수가 먼저 터미널에 경고 메세지 ** stack smashing detected ***: terminated 출력
4. 메시지를 남긴 직후, 더 이상의 비정상적인 실행을 막기 위해 스스로 abort() 함수를 호출하여 SIGABRT 신호와 함께 프로그램을 강제 종료(Abort) 시킴

 

같이 보면 너무너무 좋은 글!

https://tlssk77.tistory.com/entry/CS-stack-buffer-overflow%EC%8A%A4%ED%83%9D-%EB%B2%84%ED%8D%BC-%EC%98%A4%EB%B2%84%ED%94%8C%EB%A1%9C%EC%9A%B0

[CS] stack buffer overflow(스택 버퍼 오버플로우)