oiehso0

https://www.acmicpc.net/problem/1932

풀이

arr[1][1]

arr[2][1]    arr[2][2]

arr[3][1]    arr[3][2]    arr[3][3]

arr[4][1]    arr[4][2]    arr[4][3]    arr[4][4]  <<------와 같은 구조로 이루어져있고 무조건 같은 단(행)에 있는 숫자중에 최대값만 따라 간다고 해서 결과값이 최대가 나오지 않는다는 것을 알 수 있다. 결국 모든 각각 배열공간에 위 값을 누적해서 넣어준다.

먼저 모든 연산을 식으로 정리해 본다면  3가지 경우로 나눌 수있다.

1. arr[1][1] -> arr[2][1] -> arr[3][1] -> arr[4][1] 과 같이 맨 왼쪽 배열만 따라서 누적해주는 경우

if(j == 1) arr[i][j] += arr[i-1][j];

2. arr[1][1] -> arr[2][2] -> arr[3][3] -> arr[4][4] 과 같이 맨 오른쪽 배열만 따라서 누적해주는 경우

if else(i == j) arr[i][j] += arr[i-1][j-1];

3. 위의 두가지 경우가 아닌 중간에 위치한 배열에 상위 값을 누적해줄 경우 

왼쪽 대각선과 오른쪽 대각선 값 2가지가 존재하므로 max함수를 만들어서 비교후 누적해준다.

else arr[i][j] += max(arr[i-1][j-1], arr[i-1][j]);

위의 코드가 핵심이다. 이를 종합하면 아래와 같은 답안 코드를 작성할 수 있다. 

실행시간을 줄이기 위해서 어떻게 해야하는지 생각해봤는데 결국 마지막 단에서 모든 배열에 대해서 연산을 해주고 마지막 단에서 max값을 찾는 방법 밖에 없었다.

Dynamic Programming

동적 계획법(Dynamic Programming), 줄여서 DP는 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계기법이다.

구현

동적 계획법의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷하다. 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한번만 계산하고 저장해둔 뒤 다시한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다.

대표적인 예시

동적 계획법의 핵심이 되는 메모이제이션 코드이다. 

1. 재귀함수 형태의 피보나치 수열

house of spirit

house of spirit은 공격자가 기존 포인터를 'free'하기 전에 덮어 쓰는 것과 관련하여 다른 공격과 약간 다르다. 공격자는 메모리(힙, 스택 등)의 어느 곳에서나 상주 할 수 있는 포인터를 덮어씁니다. 청크는 모든 보안 테스트를 통과 할 수 있는 방식으로 설계한다. 어렵지 않으며 크기와 다음 chunks 크기만 설정하면 된다. fake chunk가 free되면, 그것은 적절한 binlist에 삽입됩니다. 이 크기에 대한 malloc호출은  공격자의 fake chunk를 호출한다. 최종결과는 'forging chunks attack'과 유사하다. 

샘플 코드 : 

예상대로 반환된 포인터는 fake_chunks[0] 보다 16바이트 앞을 가리킨다. fd포인터가 저장된 주소다. 힙공간 대신에 스택의 메모리를 가리킨다.

공격자는 스택의 return 어드레스를 수정에서 exploit한다.

일반적으로 우리는 우리가 할당한 메모리에 데이터를 쓴다. 그렇기 때문에 만약 malloc이 반환하는 주소를 제어할 수 있다면, write-anything-anywhere를 실현할 수 있다.House of Spirit의 최종적인 효과는 공격자가 만든 가짜 청크를 fastbin을 통해 반환하게 하는 것이다.

Shrinking Free Chunks

이 공격은 'Glibc adventures : The forgotten chunk'에 설명되어 있다. 그것은 단일 바이트의 힙 오버플로우를 사용한다.

공격의 목표는 'malloc'이 현재 사용중인 이미 할당 된 청크와 겹치는 청크를 반환하도록하는 것이다. 

먼저 3개의 연속 청크(a, b, c)가 할당되고 가운데 청크(b)가 free된 상태에서 1번째(a) chunk에서 overflow하여 2번째 청크(b)에 size 부분을 덮어쓰게 된다. 

공격차는 최하위 바이트를 0으로 설정한다. 이 'shrinks'는 청크 사이즈를 줄인다. (b의 사이즈를 0x208 -> 0x200으로) 그 다음 2개의 작은 청크(b1, b2)가 free된 중간의 청크로부터 할당된다. 

The third chunk's prev_size does not get updated as b + b->size no longer points to c. It, in fact, points to a memory region 'before' c.  

그런 다음 c와 함께 b1이 free됩니다. c는 여전히 b가 free라고 가정합니다. (prev_size가 없데이트되지 않았기 때문에 c -> c -> prev_size가 여전히 b를 가리킴) 그리고 자신(c)을 b로 통합한다.

 그 결과 b에서 시작하여 b2와 겹치는 큰 free chunk가 설정된다. 새로운 malloc은 이 큰 chunk를 반환하여 공격을 완료한다.

* unsortedbin은 FIFO! 인접한것이 오면 병합

big은 초기 b청크를 가리키고 b2와 겹친다. 이 두 청크가 결코 free되지 않아도 big의 내용을 갱신하면 b2의 내용도 갱신된다.

b를 축소하는 대신 공격자는 b의 크기를 늘릴 수도 있다.

이경우 중복의 비슷한 케이스가 나타난다.

'malloc'이 증가된 크기의 다른 청크를 요청하면 b가 이 요청을 처리하는데 사용된다.

이제 c의 메모리도 이 새로운 청크의 일부가 될 것이다.

Unlink Exlpoit

Unlink 공격은 한때 꽤 흔했다. 그러나 두 가지 보안 검사가 unlink MACRO ("corrupted size vs. prev_size" 와 "corrupted double linked list" FD->bk != P || BK->fd != P )에 추가되어 공격의 영향을 어느 정도 줄였다.

그럼에도 불구하고, bin에서 chunk를 제거할때, unlink MACRO에서 수정된 포인터를 exploit한다.

struct chunk_structure {
  size_t prev_size;
  size_t size;
  struct chunk_structure *fd;
  struct chunk_structure *bk;
  char buf[10];               // padding
};

unsigned long long *chunk1, *chunk2; 
struct chunk_structure *fake_chunk, *chunk2_hdr; 
char data[20];

// First grab two chunks (non fast)
chunk1 = malloc(0x80);        // Points to 0xa0e010
chunk2 = malloc(0x80);        // Points to 0xa0e0a0

// 공격자가 chunk1의 내용을 제어한다고 가정
// heap 오버플로우로 chunk2의 헤더가 덮힘

// 첫번째 수정한 fake chunk는 chunk1에서 시작함
// unlink security check을 우회하기 위해 fd와 bk 포인터를 설정해줘야함
fake_chunk = (struct chunk_structure *)chunk1;
fake_chunk->fd = (struct chunk_structure *)(&chunk1 - 3); // Ensures P->fd->bk == P 3 : 0x18
fake_chunk->bk = (struct chunk_structure *)(&chunk1 - 2); // Ensures P->bk->fd == P 2 : 0x10

// 모든 security check를 우회할 수 있도록 chunk2의 헤더를 수정한다.
chunk2_hdr = (struct chunk_structure *)(chunk2 - 2);
chunk2_hdr->prev_size = 0x80;  // chunk1의 데이터 영역의 size
chunk2_hdr->size &= ~1;        // prev_inuse bit를 unsetting한다.

//chunk2가 free될때, 공격자의 fake chunk는 'unlink' 된다.
// chunk1의 포인터에 chunk1 - 3을 가리키는 포인터가 생성된다.
// i.e. chunk1[3]이 chunk1 자체가 포함됨
// 우리는 chunk1이 victim's data를 가리키도록 만든다.
free(chunk2);

chunk1[3] = (unsigned long long)data;

strcpy(data, "Victim's data");

// Overwrite victim's data using chunk1
chunk1[0] = 0x002164656b636168LL;   // hex for "hacked!"

printf("%s\n", data);         // Prints "hacked!"

먼저, smallbin 범위에 속하는 0x80사이즈의 chunk1 과 chunk2을 malloc한다. 그 다음 공격자가 chunk1의 내용을 제어할 수 있다고 가정한다.(strcpy와 같은 안전하지 않은 user input 사용) 두 청크는 메모리상에 나란히 위치하게 되고 chunk1에 데이터부분에 fake_chunk를 생성한다. 그리고 "corrupted double-linked list" security check을 우회하기 위해 fd와 bk포인터를 조정한다. 그리고 chunk2의 헤더를 덮어 prev_size와 prev_inuse 비트를 수정한다. 이렇게 하면 chunk2가 해제 될 때 fake_chunk가 unlink된다. 

P ->fd -> bk == P 와 P -> bk -> fd == P check가 어떻게 pass되는가?

chunk2가 free되면, smallbin으로 간다. prev와 next chunk가  free되어있는지 아닌지 체크한다.

임의의 청크가 'free'로 탐지되면 연속적인 free 청크를 병합하기 위해 unlink된다.

unlink MACRO는 포인터를 수정하는 두가지 명령을 실행한다.

1. Set P -> fd -> bk = P -> bk

2. Set P -> bk -> fd = P -> bk

이 경우, P-> fd-> bk와 P-> bk-> fd는 같은 위치를 가리키고 있으므로 두 번째 업데이트 만 나타납니다. 다음 다이어그램은 chunk2가 해제 된 직후 두 번째 업데이트의 효과를 보여줍니다.

이제 chunk1은 (& chunk1-3)의 주소 (16 비트)를 가리킨다.

그러므로 chunk1 [3]은 실제로 chunk1이다. chunk1 [3] 변경은 chunk1을 변경하는 것과 같다.

침입자는 chunk1 자체 대신에 chunk1 (chunk1 [3]) 위치의 데이터를 업데이트 할 수있는 기회를 얻는다.

이 예제에서 chunk1은 'data'변수를 가리키게되고 chunk1을 통한 변경 사항은 해당 변수에 반영됩니다.

 .got 섹션을 덮어 쓰면 임의 코드가 실행됩니다.

forging chunks

청크가 해제되면 binlist에 삽입되고 이후에도 포인터는 프로그램에서 계속 사용할 수 있다. 공격자가 이 포인터를 제어할 경우 bin에서 linked list 구조를 수정할 수 있고 임의의 위조된 청크를 삽입 할 수 있다. 

struct forged_chunk {
  size_t prev_size;
  size_t size;
  struct forged_chunk *fd;
  struct forged_chunk *bck;
  char buf[10];               // padding
};

// First grab a fast chunk
a = malloc(10);               // 'a' points to 0x219c010

// Create a forged chunk
struct forged_chunk chunk;    // At address 0x7ffc6de96690
chunk.size = 0x20;            // This size should fall in the same fastbin
data = (char *)&chunk.fd;     // Data starts here for an allocated chunk
strcpy(data, "attacker's data");

// Put the fast chunk back into fastbin
free(a);
// 위조된 청크를 가리키기 위해 'a'의 'fd'포인터를 수정한다.
*((unsigned long long *)a) = (unsigned long long)&chunk;
// Remove 'a' from HEAD of fastbin
// Our forged chunk will now be at the HEAD of fastbin
malloc(10);                   // Will return 0x219c010

victim = malloc(10);          // Points to 0x7ffc6de966a0
printf("%s\n", victim);       // Prints "attacker's data" !!

위조된 청크의 크기 변수는 "malloc() : memory corruption(fast)"를 우회하기 위해 0x20으로 설정되었다.

이 검사는 청크의 크기가 특정 fastbin의 범위에 해당되는지를 판별한다. 또한, 할당된 청크에 대한 데이터는 'fd' 포인터에서 시작된다.

1. 'a' free됨

head -> a -> tail

2. 'a'의 'fd'포인터가 'forged chunk'를 가리키게 수정됨

head -> a -> forged chunk -> undefined(forged chunk의 fd는 실제 공격자의 데이터를 보유)

3. 'malloc' 요청됨.

head -> forged chunk -> undefined

4. victim에 의한 'malloc' 요청

head -> undefined (forged chunk가 victim에 의해 리턴됨)

유의 : 

같은 bin list에 있는 fast chunk에 대한 'malloc'요청은  segmentation fault 오류를 일으킨다.

우리가 10bytes를 요청하고 위조된 덩어리의 크기를 32(0x20)바이트로 설정하더라도, 둘 다 32 바이트 덩어리의 동일한 fastbin의 범위에 속한다.

small과 large 청크에 대한 이 공격은 나중에 'House of Lore'로 보여줄 것이다.

위 예시 코드는 64bit용으로 설계되었다. 32bit에서 실행하려면 포인터가 8바이트대신 4바이트가 되므로 unsigned long long을 unsigned int로 바꾼다.

또한, forged chunk의 크기로 32bytes를 사용하는 대신 약 17bytes의 작은 크기가 작동한다.

Double Free

리소스를 두번 이상 free하면 메모리 누수가 발생한다. allocator의 데이터 구조가 공격자에 의해서 손상되어 exploit 될 수 있다.

아래의 샘플 프로그램에서 fastbin chunk가 두 번 해제됩니다. glibc에 의한 'double free or corruption(fasttop)' security check을 피하기위해 두 free 사이에 다른 청크가 free된다. 

이것은 동일한 두개의 청크가 서로 다른 malloc에 의해 반환된다는 것을 의미한다.

아래에서 d 와 f 포인터는 동일한 메모리 주소를 가리킨다. d 나 f 둘 중 하나의 메모리 수정이 이루어지면 다양한 공격으로 이루어질 수 있다.

a = malloc(10);     // 0xa04010
b = malloc(10);     // 0xa04030
c = malloc(10);     // 0xa04050

free(a);
free(b);  // To bypass "double free or corruption (fasttop)" check
free(a);  // Double Free !!

d = malloc(10);     // 0xa04010
e = malloc(10);     // 0xa04030
f = malloc(10);     // 0xa04010   - Same as 'd' !

fastbin의 상태 : 

1. 'a' free됨

head -> a -> tail

2. 'b' free됨

head -> b -> a -> tail

3. 'a' 다시 free됨

head -> a -> b -> a -> tail

4. 'd' malloc요청

head -> b -> a -> tail  (a 공간 리턴)

5. 'e' malloc 요청

head -> a -> tail (b 공간 리턴)

6. 'f' malloc 요청

head -> tail (a 공간 리턴)

이제, 'd' 와 'f' 포인터는 같은 메모리 주소를 가리킨다. smallbin 범위에서 크기가 변경될 시 예제 작동 x

첫번째 free에서 next chunk의 prev_inuse 비트가 0으로 설정도니다. 두번째 free 과정에서 이 비트가 0이면 "double free or corruption(!prev)" 오류가 발생한다. 

이 기술은 glibc의 allocator의 first-fit 동작을 설명한다.

모든 청크(fastbin 제외)가 free될 때마다 unsorted bin에서 끝난다.

삽입은 리스트의 HEAD에서 일어난다. fastbin을 제외하고 새로운 청크를 요청할때, small bin이 비어있을 때 처음에 unsorted bin에서 찾는다.

이 조회는 TAIL에서 일어난다. 

만약 unsorted bin에 필요한 크기의 청크가 있다면 사용하겠지만, 요청된 크기보다 큰 청크가 존재할때 두개로 분할되어 반환된다. 이렇게 하면 FIFO 구조가 된다.

char *a = malloc(300);    // 0x***010
char *b = malloc(250);    // 0x***150

free(a);

a = malloc(250);          // 0x***010

unsorted bin에서 free와 malloc은 아래와 같이 진행된다.

1. 'a'가 free된다.

head -> a -> tail

2. 'malloc'이 요청된다.

head -> a2 -> tail ['a1' is returned]

'a' chunk는 'a1' , 'a2'로 나눠진다.  요청된 크기(250바이트)는 'a'(300바이트)보다 작아서.

이과정은 _int_malloc에서도 해당된다. 그리고 fastbin의 경우에도 마찬가지이다. 

unsorted bin에서 free되는 대신에, fasbin에서 fast chunk는 끝난다. 앞에서 언급 했듯이, fastbin은 single linked list를 가지고 있어 

HEAD에서 추가와 삭제가 이루어진다. 그래서 fastbin은 FILO구조를 같는다.(?)

char *a = malloc(20);     // 0xe4b010
char *b = malloc(20);     // 0xe4b030
char *c = malloc(20);     // 0xe4b050
char *d = malloc(20);     // 0xe4b070

free(a);
free(b);
free(c);
free(d);

a = malloc(20);           // 0xe4b070
b = malloc(20);           // 0xe4b050
c = malloc(20);           // 0xe4b030
d = malloc(20);           // 0xe4b010

deferred coalescing

fastbin에서의 free, malloc 진행

1. 'a'가 free됨

head -> a -> tail

2. 'b' free됨

head -> b -> a -> tail

3. 'c' free됨

head -> c -> b -> a -> tail

4. 'd' free됨

head -> d -> c -> b -> a ->tail

5. malloc 요청 

 d, c, b, a순으로 return됨

20byte의 작은 청크는 unsortedbin 대신에 fastbin으로 들어간다.

Use after Free Vulnerability

위의 예제에서 malloc은 이전에 사용되었고 free된 청크를 return하는 것을 알 수 있었다. 결국 free된 메모리 청크의 재사용은 취약할 수 있다. 청크가 free되면 공격자는 청크 내부의 데이터를 제어 할 수 있다는 뜻이 된다. 

av는 arena ptr(Main or Thread), bytes는 사용자가 요청한 크기

unlink

1. 청크 크기가 다음 청크에 설정된 prev_size와 같은지 // corrupted size vs prev_size

2. FD->bk != P || BK->fd != P // corrupted double-linked list

여기서 p는 unlink 되어지는 청크

fake chunk

참고 : https://www.lazenca.net/display/TEC/unsafe+unlink

_int_malloc

1. fastbin에서 첫 번째 청크를 제거하는 동안, 청크의 크기가 fastbin 의 청크 사이즈 범위에 속하는지 확인 // malloc() : memory corruption(fast)

2. small bin으로부터 마지막 청크(victim)를 제거하는 동안 victim -> bk -> fd 와 victim이 같은지 확인 // malloc() : smallbin double linked list corrupted

3. unsorted bin에서 반복하는 동안, 현재 청크의 사이즈가 최소(2*SIZE_SZ)와 최대(av -> system_mem) 범위 내에 있는지 확인 // malloc() : memory corruption

4. 마지막 remainder chunk를 unsorted bin에 넣는 동안(large chunk를 분할 한 후)에 unsorted_chunks(av) -> fd -> bk == unsorted_chunks(av)인지 확인 // malloc() : corrupted unsorted chunks

 _int_free

1. P가 P+chunksize(P)보다 앞에 있는지 확인(to avoid wrapping) ?? // free() : invalid pointer

여기서 P는 free된 청크 

2. chunk가 최소 MINISZE 크기인지 또는 MALLOC_ALIGNMENT의 배수인지 확인 // free() : invalid size

3. fastbin 범위의 크기를 가진 chunk의 경우, 다음 청크의 크기가 최소와 최대(av -> system_mem)사이의 크기에 있는지 확인 // free() : invalid next size(fast)

4. fast chunk를 fastbin(HEAD)에 넣을때 HEAD에 이미 있는 청크와 동일하지 않은지 확인 // double free or corruption(fasttop)

5. fastbin에 fast chunk를 넣을때(HEAD에), HEAD에 있는 청크의 크기와 삽입 될 청크의 크기가 같은지 확인 // invalid fastbin entry(free)

6. chunk가 fastbin의 크기 범위에 있지 않고 mmapped chunks도 아닌 경우, top chunk와 같은지 확인 // double free or corruption(top)

7. next chunk가 아레나의 범위 안에 있는지 확인한다. // double free or corruption (out)

8. 다음 청크의 prev_inuse 비트가 표시되어 있는지 확인 // double free or corruption(!prev)

9. next chunk의 크기가 최소와 최대(av -> system_mem) 사이즈 사이에 있는지 확인 // free() : invalid next size(normal)

10. unsorted bin에 병합된 청크를 삽입하는 동안 unsorted_chunks(av) -> fd -> bk == unsorted_chunks(av)인지 확인 // free() : corrupted unsorted chunks