24.01.26 CSAPP 3.10.3 - 3.10.5, LCS, Knapsack

CSAPP

3.10.3 범위를 벗어난 메모리 참조와 버퍼오버플로우

• C에서 배열참조시 범위를 체크하지 않으며, 지역변수들이 스택에 보존용 레지스터들과 리턴주소 같은 상태 정보와 함께 스택에 저장된다. 이러한 조합 때문에 심각한 프로그램 에러가 발생할 수 있는데, 스택에 저장된 상태정보가 범위를 벗어난 배열의 원소에 대한 쓰기 작업에 의해 변경되는 것이다. 그러고 나서 프로그램이 레지스터값을 재 적재하거나 이렇게 변경된 상태정보를 사용해서 ret인스트럭션을 실행할 때, 심각한 결과를 초래한다. 일반적인 상태손실을 버퍼오버플로우라고 알려져있다.
• 일반적으로 gets나 저장공간을 오버플로우하게 되는 함수를 사용하는 것은 나쁜 프로그래밍 습관으로 평가한다.
• 자주 사용하는 strcpy,strcat,sprintf 같이 자주 사용되는 많은 라이브러리 함수들은 대상 버퍼 크기를 나타내는 아무런 수단도 없이 일련의 바이트를 생성할 수 있는 특성을 가진다. 이런 조건들은 버퍼오버플로우 시 취약성이 될 수 있다.
• 버퍼 오버플로우의 보다 치명적인 사용은 일반적으로 프로그램이 하지 않을 기능들을 실행하도록 하는 것이다. 이것은 컴퓨터 네트워크 상의 시스템 보안성을 공격하는 가장 일반적인 방법 중 하나다. 일반적으로 탐색코드(ExploitCode)라고 하는 실행코드를 바이트 인코딩한 탐색코드를 가리키는 포인터로 리턴주소를 덮어쓰는 약간의 추가적인 바이트들을 포함하는 스트링을 입력한다. ret인스트럭션을 실행하면 탐색코드로 점프하게 된다.
• 공격의 한 가지 유형으로 탐색코드는 시스템 콜을 이용해서 쉘 프로그램을 시작하고, 공격자에게 여러가지 운영체제 기능을 제공한다. 다른 형태로 탐색코드는 허용되지 않은 기능을 실행하고, 손상된 스택을 복구하며, ret을 한번 더 실행해서 호출자에게 정상적인 리턴이 발생한 것처럼 하기도 한다.

3.10.4 버퍼오버플로우 공격 대응기법

스택랜덤화

• 공격자는 탐색코드를 시스템에 삽입하기 위해 공격 스트링 내에 코드뿐만 아니라 코드로의 포인터까지 집어넣어야 한다. 이 포인터를 만들기 위해서는 스트링이 위치하게 될 스택의 주소를 알아야한다. 역사적으로 프로그램의 스택주소는 쉽게 예측할 수 있었다.
• 스택랜덤화의 아이디어는 스택의 위치를 프로그램의 매 실행마다 다르게 해주는 것이다. 그래서 많은 컴퓨터가 동일한 코드를 실행하고 있을지라도 이들은 모두 완전히 다른 스택 주소를 사용하게 된다.
• 이 방법은 예를 들어 프로그램 시작시 스택에 alloca함수를 사용하여 0부터 n바이트 사이의 랜덤 크기 공간을 할당해서 스택에 정해진 크기의 공간을 할당한다. 이렇게 할당된 공간은 프로그램에서 사용하지 않지만 이렇게 함으로써 프로그램의 매 실행마다 모든 이후의 스택위치가 변경되도록 해준다. 할당의 범위 n은 너무 커서 공간을 낭비하지 말아야하며, 스택 주소에 충분한 변화를 줄 정도로 큰 값을 유지해야 한다.
• 스택랜덤화는 리눅스 시스템에서 표준 기법이 되었다. 이것은 주소공간 배치 랜덤화 ASLR라고 하는 보다 넓은 종류의 기술에 속한다. ASLR을 사용하면 프로그램 코드, 라이브러리 코드, 스택, 전역변수, 힙 데이터를 포함하는 여러 프로그램의 부분들이 프로그램이 매번 실행할 때 마다 메모리의 다른 지역에 로딩된다.
• 이것은 하나의 컴퓨터에서 실행하는 프로그램은 다른 컴퓨터의 동일한 프로그램과 서로 다른 주소 매핑을 갖는것을 의미한다.

스택 손상 검출

• 두 번째 방어 방법은 스택이 손상되는 것을 감지하는 것이다. C에서 배열의 경계를 넘는 쓰기 작업을 방지하는 안정적인 방법은 존재하지 않는다. 그 대신, 프로그램은 해로운 효과가 발생하기 전에 이러한 쓰기 작업이 발생하는 것을 감지하는 시도를 할 수 있다.
• 최신 GCC에서는 스택 보호코드를 버퍼 오버플로우를 감지하기 위해 생성된 코드에 추가하는 기법을 구현한다. 이 아이디어는 지역버퍼와 나머지 스택 상태값 사이에 특별한 카나리(Canary)값을 저장하는 것이다. 이 카나리값은 보호값(guard value)이라고도 불리며 프로그램의 매 실행마다 랜덤으로 생성되므로 공격자가 값을 쉽게 추정하기 어렵다. 레지스터 상태를 복원하고 함수로부터 리턴 하기 전에 프로그램은 카나리 값이 이 함수나 호출한 동작에 의해 변경 되었는지를 체크한다. 만일 변경되었다면, 프로그램은 에러를 발생시키며 종료한다.
• 최신 GCC버전에서는 함수가 스택 오버플로우에 취약한지 판단하려하며, 이러한 종류의 오버플로우 감지기능을 자동으로 삽입한다. 카나리 값을 특별한 세그먼트에 저장해서 ‘read only’로 표시할 수 있으며, 공격자가 저장된 카나리 값을 변경할 수 없게된다.
• 스택보호는 버퍼 오버플로우 공격에 의해 프로그램 스택에 저장된 상태의 손상을 방지하는데 유용하다. 이 방식은 매우 작은 성능 저하를 가져올 뿐이며, 그것은 특히 GCC가 함수 내에 Char 타입의 지역 버퍼가 있는 경우에만 이 코드를 삽입하기 때문이다.

실행코드 영역 제한하기

• 마지막 방법은 공격자가 실행코드를 시스템에 추가 할 가능성을 제거하는 것이다. 한 가지 방법은 어느 메모리 영역이 실행코드를 저장하는지를 제한하는 것이다. 일반적인 프로그램에서 컴파일러가 만든 코드를 저장하는 메모리 부분만이 실행 가능하면 된다. 다른 부분들은 읽기와 쓰기만 허용하도록 제한할 수 있다.
• 하드웨어는 사용자 프로그램과 운영체제 커널에게 허용된 접근 형태를 나타내는 서로 다른 메모리 보호 형태를 지원한다. 많은 컴퓨터는 세 개의 접근 형태에 걸친 제어를 허용한다.
  1. 읽기 : 메모리에서 데이터 읽기
  2. 쓰기 : 메모리에 데이터 저장하기
  3. 실행하기 : 메모리 내용을 기계어 수준 코드로 취급하기
• 역사적으로 x86 아키텍처는 읽기와 실행 접근 제어를 1비트 플래그에 통합 하였으며, 따라서 읽기 허용으로 표시된 페이지는 모두 실행 가능했다. 일부 페이지를 읽기 가능하면서 실행 불가능하게 하기 위한 여러 방법이 구현되었지만, 대개 상당한 비효율성을 발생시켰다.
• 보다 최근 AMD는 ‘NX’ no-execute 비트를 그들 64비트 프로세서를 위한 메모리 보호 내에 추가하였고, 이 방법으로 읽기와 쓰기 접근이 분리 되었으며, 인텔도 이 방법을 채택했다.
• 이 기능으로 스택은 읽기와 쓰기가 가능하지만 실행할 수 없도록 표시될 수 있으며, 페이지가 실행 가능한지 체크하는 것도 하드웨어에서 효율성 저하 없이 실행된다.

3.10.5 가변크기 스택프레임 지원하기

• 일부 함수들은 가변적인 지역공간 크기를 필요로 한다. 이런 경우는 함수가 스택에 임의의 크기의 바이트를 할당하는 표준함수인 alloca를 호출할 때 일어난다. 또 이 코드가 가변 크기의 지역 배열을 선언할 때 일어날 수 있다.
• 가변 크기 스택 프레임을 처리하기 위해 x86-64 코드는 레지스터 %rbp를 이용해서 프레임 포인터frame pointer(어떤 경우에는 base pointer 라고 부르며, 따라서 %rbp에서 문자 bp를 사용한 것을 볼 수있다.) %rbp 레지스터는 피호출자 - 저장 레지스터기 때문에 이 코드는 스택에 이전 버전의 %rbp를 보관한다. 그 후 이 함수가 실행되는 동안 계속 %rbp를 현 위치를 가리키도록 유지하며, 이것은 고정길이 지역변수들을 %rbp에 대한 상대적인 오프셋 값으로 참조한다.

Algorithm

최장 공통 부분수열(Longest Common Subsequence)

최장 공통 문자열Longest common substring

• 점화식

if i == 0 or j == 0:
	LCS[i][j] = 0
elif string_A[i] == string_B[j]
	LCS[i][j] = LCS[i-1][j-1] + 1
else:
	LCS[i][j] = 0

동작

1. 문자열 A, 문자열 B의 한 글자씩 비교한다.
2. 두 문자가 다르다면 LCS[i][j]에 0을 표시
3. 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 + 1
4. 위 과정을 반복한다.

• 이 과정이 성립하는 이유는 공통 문자열은 연속 되어야 하기 때문에 현재 두 문자가 같을 때 두 문자의 앞 글자 까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 본인부터 다시 공통 문자열을 만들어가게 될 것이다.

최장 공통 부분수열

• 점화식

if i == 0 or j == 0:
	LCS[i][j] = 0
elif string_A[i] == string_B[j]
	LCS[i][j] = LCS[i-1][j-1] + 1
else:
	LCS[i][j] max(LCS[i-1][j],LCS[i][j-1])

동작

1. 문자열 A, 문자열 B의 한 글자씩 비교한다
2. 두 문자가 다르다면 LCS[i-1][j] 와 LCS[i][j-1] 중 큰 값을 표시한다.
3. 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 +1 한다
4. 위 과정을 반복한다.

• 부분 수열은 연속된 값이 아니다. 현재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속해서 유지된다.

배낭 알고리즘(Knapsack)

• n개의 물건과 배낭이 있을 때 각 물건에는 가치와 무게가 존재한다.
• 또한 각 물건은 1개씩만 있다.
• 배낭에는 담을 수 있는 최대 용량이 존재한다.
• 이러한 조건일 때, 배낭의 최대 용량을 초과하지 않으면서 배낭에 담을 수 있는 최대 가치의 합을 찾는 문제이다.

Knapsack problem

• 배낭문제는 물건을 쪼갤 수 있는 Fractional Knapsack problem과 물건을 쪼갤 수 없는 0-1 Knapsack problem으로 나뉜다.