memcpy - 10 pt
Are you tired of hacking?, take some rest here.
Just help me out with my small experiment regarding memcpy performance.
after that, flag is yours.
http://pwnable.kr/bin/memcpy.c
ssh memcpy@pwnable.kr -p2222 (pw:guest)
memcpy@ubuntu:~$ ls -l
total 8
-rw-r--r-- 1 root root 3172 Mar 4 2016 memcpy.c
-rw-r--r-- 1 root root 192 Mar 10 2016 readme
memcpy@ubuntu:~$ cat readme
the compiled binary of "memcpy.c" source code (with real flag) will be executed under memcpy_pwn privilege if you connect to port 9022.
execute the binary by connecting to daemon(nc 0 9022).
memcpy@ubuntu:~$ cat memcpy.c
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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | // compiled with : gcc -o memcpy memcpy.c -m32 -lm #include <stdio.h> #include <string.h> #include <stdlib.h> #include <signal.h> #include <unistd.h> #include <sys/mman.h> #include <math.h> unsigned long long rdtsc(){ asm("rdtsc"); } char* slow_memcpy(char* dest, const char* src, size_t len){ int i; for (i=0; i<len; i++) { dest[i] = src[i]; } return dest; } char* fast_memcpy(char* dest, const char* src, size_t len){ size_t i; // 64-byte block fast copy if(len >= 64){ i = len / 64; len &= (64-1); while(i-- > 0){ __asm__ __volatile__ ( "movdqa (%0), %%xmm0\n" "movdqa 16(%0), %%xmm1\n" "movdqa 32(%0), %%xmm2\n" "movdqa 48(%0), %%xmm3\n" "movntps %%xmm0, (%1)\n" "movntps %%xmm1, 16(%1)\n" "movntps %%xmm2, 32(%1)\n" "movntps %%xmm3, 48(%1)\n" ::"r"(src),"r"(dest):"memory"); dest += 64; src += 64; } } // byte-to-byte slow copy if(len) slow_memcpy(dest, src, len); return dest; } int main(void){ setvbuf(stdout, 0, _IONBF, 0); setvbuf(stdin, 0, _IOLBF, 0); printf("Hey, I have a boring assignment for CS class.. :(\n"); printf("The assignment is simple.\n"); printf("-----------------------------------------------------\n"); printf("- What is the best implementation of memcpy? -\n"); printf("- 1. implement your own slow/fast version of memcpy -\n"); printf("- 2. compare them with various size of data -\n"); printf("- 3. conclude your experiment and submit report -\n"); printf("-----------------------------------------------------\n"); printf("This time, just help me out with my experiment and get flag\n"); printf("No fancy hacking, I promise :D\n"); unsigned long long t1, t2; int e; char* src; char* dest; unsigned int low, high; unsigned int size; // allocate memory char* cache1 = mmap(0, 0x4000, 7, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); char* cache2 = mmap(0, 0x4000, 7, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); src = mmap(0, 0x2000, 7, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0); size_t sizes[10]; int i=0; // setup experiment parameters for(e=4; e<14; e++){ // 2^13 = 8K low = pow(2,e-1); high = pow(2,e); printf("specify the memcpy amount between %d ~ %d : ", low, high); scanf("%d", &size); if( size < low || size > high ){ printf("don't mess with the experiment.\n"); exit(0); } sizes[i++] = size; } sleep(1); printf("ok, lets run the experiment with your configuration\n"); sleep(1); // run experiment for(i=0; i<10; i++){ size = sizes[i]; printf("experiment %d : memcpy with buffer size %d\n", i+1, size); dest = malloc( size ); memcpy(cache1, cache2, 0x4000); // to eliminate cache effect t1 = rdtsc(); slow_memcpy(dest, src, size); // byte-to-byte memcpy t2 = rdtsc(); printf("ellapsed CPU cycles for slow_memcpy : %llu\n", t2-t1); memcpy(cache1, cache2, 0x4000); // to eliminate cache effect t1 = rdtsc(); fast_memcpy(dest, src, size); // block-to-block memcpy t2 = rdtsc(); printf("ellapsed CPU cycles for fast_memcpy : %llu\n", t2-t1); printf("\n"); } printf("thanks for helping my experiment!\n"); printf("flag : ----- erased in this source code -----\n"); return 0; } | cs |
memcpy@ubuntu:~$ nc 0 9022
Hey, I have a boring assignment for CS class.. :(
The assignment is simple.
-----------------------------------------------------
- What is the best implementation of memcpy? -
- 1. implement your own slow/fast version of memcpy -
- 2. compare them with various size of data -
- 3. conclude your experiment and submit report -
-----------------------------------------------------
This time, just help me out with my experiment and get flag
No fancy hacking, I promise :D
specify the memcpy amount between 8 ~ 16 : 8
specify the memcpy amount between 16 ~ 32 : 16
specify the memcpy amount between 32 ~ 64 : 32
specify the memcpy amount between 64 ~ 128 : 64
specify the memcpy amount between 128 ~ 256 : 128
specify the memcpy amount between 256 ~ 512 : 256
specify the memcpy amount between 512 ~ 1024 : 512
specify the memcpy amount between 1024 ~ 2048 : 1024
specify the memcpy amount between 2048 ~ 4096 : 2048
specify the memcpy amount between 4096 ~ 8192 : 4096
ok, lets run the experiment with your configuration
experiment 1 : memcpy with buffer size 8
ellapsed CPU cycles for slow_memcpy : 1371
ellapsed CPU cycles for fast_memcpy : 474
experiment 2 : memcpy with buffer size 16
ellapsed CPU cycles for slow_memcpy : 333
ellapsed CPU cycles for fast_memcpy : 414
experiment 3 : memcpy with buffer size 32
ellapsed CPU cycles for slow_memcpy : 504
ellapsed CPU cycles for fast_memcpy : 621
experiment 4 : memcpy with buffer size 64
ellapsed CPU cycles for slow_memcpy : 930
ellapsed CPU cycles for fast_memcpy : 126
experiment 5 : memcpy with buffer size 128
ellapsed CPU cycles for slow_memcpy : 1788
8~16, 16~32 ... 이런식으로 총 10번 해당 범위 사이의 정수값을 입력 받는다.
그러고 나면 slow_memcpy와 fast_memcpy를 하는 것 같다.
위의 시도에서는 experiment5에서 fast_memcpy구간에서 오류가 생겨 끊긴 것 같다.
어떻게 해서든 위 구간을 모두 통가하면 FLAG를 얻을 수 있는 것 같다.
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 | // run experiment for(i=0; i<10; i++){ size = sizes[i]; printf("experiment %d : memcpy with buffer size %d\n", i+1, size); dest = malloc( size ); memcpy(cache1, cache2, 0x4000); // to eliminate cache effect t1 = rdtsc(); slow_memcpy(dest, src, size); // byte-to-byte memcpy t2 = rdtsc(); printf("ellapsed CPU cycles for slow_memcpy : %llu\n", t2-t1); memcpy(cache1, cache2, 0x4000); // to eliminate cache effect t1 = rdtsc(); fast_memcpy(dest, src, size); // block-to-block memcpy t2 = rdtsc(); printf("ellapsed CPU cycles for fast_memcpy : %llu\n", t2-t1); printf("\n"); } printf("thanks for helping my experiment!\n"); printf("flag : ----- erased in this source code -----\n"); return 0; } | cs |
입력받은 횟수만큼 10번을 진행한다.
우리가 정해준 사이즈 만큼 malloc을 한다(=dest).
memcpy(cache1, cache2, 0x4000); 은 '캐시효과 제거를 위함'이라고 되어있다.
rdtsc()는 정확한 시간을 측정하는 함수라고 한다.
그러면 slow_memcpy()를 진행한 시간을 구하는 용로도 파악된다.
slow_memcpy()와 fast_memcpy()의 주석을 보면 slow 는 바이트 하나하나 복사를 진행하는 것이고 fast는 블록단위로 복사를진행하는 것으로 보인다.
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 | char* slow_memcpy(char* dest, const char* src, size_t len){ int i; for (i=0; i<len; i++) { dest[i] = src[i]; } return dest; } char* fast_memcpy(char* dest, const char* src, size_t len){ size_t i; // 64-byte block fast copy if(len >= 64){ i = len / 64; len &= (64-1); while(i-- > 0){ __asm__ __volatile__ ( "movdqa (%0), %%xmm0\n" "movdqa 16(%0), %%xmm1\n" "movdqa 32(%0), %%xmm2\n" "movdqa 48(%0), %%xmm3\n" "movntps %%xmm0, (%1)\n" "movntps %%xmm1, 16(%1)\n" "movntps %%xmm2, 32(%1)\n" "movntps %%xmm3, 48(%1)\n" ::"r"(src),"r"(dest):"memory"); dest += 64; src += 64; } } // byte-to-byte slow copy if(len) slow_memcpy(dest, src, len); return dest; } | cs |
소스를 보면 역시나 slow_memcpy()는 src에서 dest로 바이트 하나하나 복사한다.
그러나 fast_memcpy()를 보면 사이즈가 64바이트 미만인 경우에만 slow_memcpy를 실행하고 사이즈가 64바이트 이상인 경우 어셈블리어로 이루어진 코드를 실행한다. 또한 64바이트 단위로 해당 어셈코드를 실행한후 나머지 바이트에 대해서도 slow_memcpy를 진행한다.
위에서 시도해보았을 때 experiment 5에서 fast_memcpy()를 실행하다가 끊겼으므로 어셈으로 이루어진 코드에서 오류가 생겼을 가능성이 높다.
어셈코드를 분석해 보자.
| __asm__ __volatile__ ( "movdqa (%0), %%xmm0\n" "movdqa 16(%0), %%xmm1\n" "movdqa 32(%0), %%xmm2\n" "movdqa 48(%0), %%xmm3\n" "movntps %%xmm0, (%1)\n" "movntps %%xmm1, 16(%1)\n" "movntps %%xmm2, 32(%1)\n" "movntps %%xmm3, 48(%1)\n" ::"r"(src),"r"(dest):"memory"); | cs |
movdqa와 movntps가 사용되었다.
movdqa : (구글번역기를 돌렸다...)
소스 피연산자 (두 번째 피연산자)의 이중 쿼드 워드를 대상 피연산자 (첫 번째 피연산자)로 이동합니다. 이 명령어는 더블 쿼드 워드를 XMM 레지스터와 128 비트 메모리 위치간에 또는 두 개의 XMM 레지스터간에 이동하는 데 사용할 수 있습니다. 소스 또는 대상 피연산자가 메모리 피연산자 인 경우 피연산자는 16 바이트 경계에 정렬되어야하며 그렇지 않으면 일반 보호 예외 (#GP)가 생성됩니다.
16바이트 경계에 정렬되지 않으면 예외가 발생하는 명령어인 듯하다.
정렬이 뭐지...
구글링하다가 사진을 하나 찾았다.
저런식으로 16바이트 단위로 주소를 맞춰 주어야 하는 것 같다.
피연산자인 dest의 주소가 16바이트 단위로 만들어 준다면 해결될 것이다.
위 코드로 컴파일 해서 dest의 주소를 구하자
소스코드에 dest의 주소를 출력해주는 명령어를 추가해주었다:
printf("dest: %p\n", dest);
mandu@mandu-VirtualBox:~$ gedit memcpy.c
mandu@mandu-VirtualBox:~$ gcc -o memcpy memcpy.c -m32 -lm
In file included from /usr/include/stdio.h:27:0,
from memcpy.c:2:
/usr/include/features.h:367:25: fatal error: sys/cdefs.h: 그런 파일이나 디렉터리가 없습니다
compilation terminated.
오류가 난다.. 찾아보니
sudo apt-get install gcc-multilib && sudo apt-get install libc6-dev-i386
이 두개를 설치해주면 해결된다고 한다.
mandu@mandu-VirtualBox:~$ gedit memcpy.c
mandu@mandu-VirtualBox:~$ gcc -o memcpy memcpy.c -m32 -lm
mandu@mandu-VirtualBox:~$ gdb -q memcpy
Reading symbols from memcpy...(no debugging symbols found)...done.
(gdb) r
Starting program: /home/mandu/memcpy
Hey, I have a boring assignment for CS class.. :(
The assignment is simple.
-----------------------------------------------------
- What is the best implementation of memcpy? -
- 1. implement your own slow/fast version of memcpy -
- 2. compare them with various size of data -
- 3. conclude your experiment and submit report -
-----------------------------------------------------
This time, just help me out with my experiment and get flag
No fancy hacking, I promise :D
specify the memcpy amount between 8 ~ 16 : 8
specify the memcpy amount between 16 ~ 32 : 16
specify the memcpy amount between 32 ~ 64 : 32
specify the memcpy amount between 64 ~ 128 : 64
specify the memcpy amount between 128 ~ 256 : 128
specify the memcpy amount between 256 ~ 512 : 256
specify the memcpy amount between 512 ~ 1024 : 512
specify the memcpy amount between 1024 ~ 2048 : 1024
specify the memcpy amount between 2048 ~ 4096 : 2048
specify the memcpy amount between 4096 ~ 8192 : 4096
ok, lets run the experiment with your configuration
experiment 1 : memcpy with buffer size 8
ellapsed CPU cycles for slow_memcpy : 7395
dest: 0x804c410
ellapsed CPU cycles for fast_memcpy : 13332
experiment 2 : memcpy with buffer size 16
ellapsed CPU cycles for slow_memcpy : 458
dest: 0x804c420
ellapsed CPU cycles for fast_memcpy : 11844
experiment 3 : memcpy with buffer size 32
ellapsed CPU cycles for slow_memcpy : 450
dest: 0x804c438
ellapsed CPU cycles for fast_memcpy : 11569
experiment 4 : memcpy with buffer size 64
ellapsed CPU cycles for slow_memcpy : 756
dest: 0x804c460
ellapsed CPU cycles for fast_memcpy : 11336
experiment 5 : memcpy with buffer size 128
ellapsed CPU cycles for slow_memcpy : 1414
dest: 0x804c4a8
Program received signal SIGSEGV, Segmentation fault.
0x080487df in fast_memcpy ()
128에서 dest가 8이다. 주소를 16배수로 맞춰주기 위해서 이자리를 0으로 만들어 주어야 한다.
그러면 64에서 64 + 8 = 72를 대신 넣어준다면 8바이트가 더 들어가서 128에서의 dest의 주소에 8바이트를 채워준다.
(gdb) r
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /home/mandu/memcpy
Hey, I have a boring assignment for CS class.. :(
The assignment is simple.
-----------------------------------------------------
- What is the best implementation of memcpy? -
- 1. implement your own slow/fast version of memcpy -
- 2. compare them with various size of data -
- 3. conclude your experiment and submit report -
-----------------------------------------------------
This time, just help me out with my experiment and get flag
No fancy hacking, I promise :D
specify the memcpy amount between 8 ~ 16 : 8
specify the memcpy amount between 16 ~ 32 : 16
specify the memcpy amount between 32 ~ 64 : 32
specify the memcpy amount between 64 ~ 128 : 72
specify the memcpy amount between 128 ~ 256 : 136
specify the memcpy amount between 256 ~ 512 : 264
specify the memcpy amount between 512 ~ 1024 : 520
specify the memcpy amount between 1024 ~ 2048 : 1032
specify the memcpy amount between 2048 ~ 4096 : 2056
specify the memcpy amount between 4096 ~ 8192 : 4104
ok, lets run the experiment with your configuration
experiment 1 : memcpy with buffer size 8
ellapsed CPU cycles for slow_memcpy : 15456
dest: 0x804c410
ellapsed CPU cycles for fast_memcpy : 27273
experiment 2 : memcpy with buffer size 16
ellapsed CPU cycles for slow_memcpy : 988
dest: 0x804c420
ellapsed CPU cycles for fast_memcpy : 24212
experiment 3 : memcpy with buffer size 32
ellapsed CPU cycles for slow_memcpy : 984
dest: 0x804c438
ellapsed CPU cycles for fast_memcpy : 24454
experiment 4 : memcpy with buffer size 72
ellapsed CPU cycles for slow_memcpy : 1771
dest: 0x804c460
ellapsed CPU cycles for fast_memcpy : 24587
experiment 5 : memcpy with buffer size 136
ellapsed CPU cycles for slow_memcpy : 3138
dest: 0x804c4b0
ellapsed CPU cycles for fast_memcpy : 24393
experiment 6 : memcpy with buffer size 264
ellapsed CPU cycles for slow_memcpy : 5695
dest: 0x804c540
ellapsed CPU cycles for fast_memcpy : 24293
experiment 7 : memcpy with buffer size 520
ellapsed CPU cycles for slow_memcpy : 10584
dest: 0x804c650
ellapsed CPU cycles for fast_memcpy : 24148
experiment 8 : memcpy with buffer size 1032
ellapsed CPU cycles for slow_memcpy : 20812
dest: 0x804c860
ellapsed CPU cycles for fast_memcpy : 24511
experiment 9 : memcpy with buffer size 2056
ellapsed CPU cycles for slow_memcpy : 41402
dest: 0x804cc70
ellapsed CPU cycles for fast_memcpy : 25854
experiment 10 : memcpy with buffer size 4104
ellapsed CPU cycles for slow_memcpy : 96522
dest: 0x804d480
ellapsed CPU cycles for fast_memcpy : 28278
thanks for helping my experiment!
flag : ----- erased in this source code -----
[Inferior 1 (process 6102) exited normally]
성공이다.
문제서버에서 다시 풀었다.
thanks for helping my experiment!
flag : 1_w4nn4_br34K_th3_m3m0ry_4lignm3nt
FLAG : 1_w4nn4_br34K_th3_m3m0ry_4lignm3nt
