pwnable.kr - memcpy

해설

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.

 

일단 ssh로 접속해보자. readme를 읽어보면 nc로 연결하란다. nc로 연결하면 memcpy의 사이즈를 지정하라는 문자열과 함께 총 10번의 입력을 해야 한다. 일단 대충 다음과 같이 입력해 보았다.

 

무슨일인지 끝까지 실행되지 않고 5번째 체크의 fast_memcpy 부분에서 멈추는거 같다. 코드를 보자.

 

// 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;
}

코드를 보면, dest에 입력한 size 만큼을 할당하고 memcpy 실험을 하는것 같다. slow_memcpy는 그냥 바이트 단위로 옮기는 것이고, fast_memcpy는 64 바이트 블럭 단위로 옮기는 것 같다. fast_memcpy 코드를 보면 중간에 어셈이 있고 movdqa와 movntps라는 명령어를 사용해서 뭔가 메모리 카피를 하는것 같다. 즉 movdqa를 통해 src 부분의 주소를 xmm 레지스터에 저장하고, movntps를 통해 dest 부분에 xmm 레지스터에 저장되었던 src의 주소가 가리키는 메모리 영역을 복사하는 것 같다.

 

movntps의 설명을 좀 더 찾아보면, 주소가 16바이트 단위로 align 되어 있어야 함을 알 수 있다. 그런데 앞선 입력에서는 처음에 8바이트를 입력했기 떄문에, 여기서 뭔가 꼬인것 같다. 그럼 16바이트 배수로 맞춰서 입력해보자.

 

?? 분명 16바이트 배수로 맞춰서 사이즈를 입력했음에도 중간에 멈춰 버렸다. 왜그런걸까?

 

사실 dest 메모리를 할당하는 malloc 함수는 입력 받은 size만큼만 메모리를 할당하는 것이 아니라, bookkeeping이라는 기능을 위해 추가적인 메모리를 더 할당한다. 우선 기본적으로 malloc은 memory alignment에 의해 32비트 기준으로 8바이트로 정렬된 메모리 사이즈를 할당한다. 따라서 실제 입력된 사이즈를 8바이트 배수에 맞게 패딩하여 할당하는 것이다. 여기에 추가로 bookkepping을 위한 8바이트를 더 할당하게 된다. bookkeeping은 동적 할당된 메모리의 free를 위해 저장되는 추가 정보이다.

 

따라서 입력할 size+8 이 16의 배수가 되도록 입력하면 된다.