생초보 pwnable.kr - memcpy write-up

필요 지식

---

 1. memory 관련 함수, 명령어

• void* memcpy(void* dst, void* src, size_t num)
  이름 그대로 메모리 영역에서 다른 메모리 영역으로 데이터를 복사하는 함수입니다. 첫 번째 인자에서 복사받을 메모리 포인터, 두 번째 인자에서 복사할 메모리를 가리키는 포인터, 세 번째 인자로 복사할 데이터의 길이를 받습니다. 주의할 점으로 memcpy함수는 src와 dst가 겹치는 영역에 사용할 수 없습니다. 겹쳐져 있는 부분을 덮어씌워야 한다면 memmove함수를 사용해야 합니다.
• void* memset(void*ptr, int value, size_t num)
  memset은 메모리의 내용을 원하는 크기만큼 특정값으로 세팅할 수 있는 함수입니다. 첫 번째 인자로 세팅하고자하는 메모리의 포인터, 두번째 인자로 메모리에 세팅해 주고자하는 값, 세번째 인자는 세팅하고자하는 데이터의 길이를 의미합니다. value의 경우 정수를 받지만 내부적으로 unsigned char로 변환되어 저장됩니다. 리턴값은 성공시 첫번째 인자로 들어가 포인터를 반환하고 실패시 NULL을 반환합니다.

• void* mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset)
  mmap은 메모리 맵핑 함수 중 하나로 파일을 메모리에 맵핑하여 파일을 메모리처럼 사용할 수 있게 해주는 시스템콜입니다. 
  첫번째 인자인 start는 맵핑될 메모리 영역의 시작 주소로 NULL일 경우 시스템이 알아서 할당해 줍니다.
  두 번째 인자인 length는 맵핑할 파일의 크기로 0 이상의 정수값이 들어갑니다.
  세 번째 인자인 prot은 맵핑된 메모리 영역의 보호속성을 지정합니다. (PROT_READ, PROT_WIRTE 등)
  네 번째 인자인 flags는 맵핑 옵션을 지정합니다.(MAP_SHARED, MAP_PRIVATE 등)
  다섯 번째 인자인 fd는 맵핑할 파일을 지정합니다. -1일 경우 파일 대신 익명의 메모리 맵핑을 생성합니다.
  여섯 번째 인자인 offset은 start부터 얼마큼 떨어져서 맵핑할 건지를 설정해 줄 수 있습니다.
  mmap을 사용 시 파일 입출력 함수보다 더 높은 성능을 기대할 수 있습니다. 그러나 맵핑된 메모리 영역은 파일의 크기만큼 가상 메모리 공간을 사용하므로 메모리 사용량에 주의해야 합니다.
• movdqa memptr, xmm
  XMM 전용 레지스터에서 사용하는 레지스터와 메모리 사이에서 128비트 데이터를 빠르게 전송하는 데 사용되는 명령어입니다. 128비트의 정렬된 데이터를 레지스터와 메모리 사이에서 복사하는 데 사용됩니다.이때 주의할 점은 레지스터의 주소가 16바이트(128비트)로 정렬되어 있어야 합니다. 정렬돼있지 않다면 인터럽트가 발생하여 프로그램이 비정상적으로 종료될 수 있습니다. 정렬되지 않은 데이터를 처리하기 위해서는 movdqu를 사용해야 합니다. 데이터가 정렬되어 있다는 것은 16바이트 데이터를 다룰 경우 데이터의 시작주소가 16의 배수로 통일되어 있다는 것을 말합니다.
• movntps xmm, memptr 
  movntps는 인텔 x86 아키텍처에서 SSE 명령어 세트에서 제공하는 빠른 비-캐시 쓰기를 수행하는 명령어입니다. 캐시가 아닌 메모리 영역에 단일 정밀도 부동 소수점 값을 저장하는 데 사용됩니다. 이때 캐시에 값을 저장하지 않으므로 쓰기 속도가 빨라집니다.

Write-Up

---

 

안녕하세요. 이번엔 10점짜리 memcpy문제입니다.

 

문제 내용을 보니 해킹문제는 아닌 거 같네요. 접속해 보겠습니다.

readme를 보니 이번에도 nc로 따로 접속해서 푸는 문제입니다.

실행해 보니 memcpy 성능을 테스트해보는 문제라 하고 단계별로 카피할 메모리를 입력받습니다. 그런데 결과를 보니 실험 5까지만 나오고 프로그램이 갑자기 종료됩니다.  c 코드를 보도록 하겠습니다.

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

내용이 긴 관계로 함수별로 나누어서 보겠습니다. 우선 버퍼설정을 해주고  cache1,2, src에 메모리 맵핑을 해주네요. 그런 다음 각 단계별로 메모리 복사할 데이터의 사이즈를 사용자 입력으로 받습니다. 그런 다음 본격적으로 메모리 카피를 시작합니다. 각 단계별로 시작하는데  dest에 복사할 사이즈만큼 공간을 할당하고 캐시를 비워주고  t1, t2에 rdtsc를 통해 시간을 계산해 주네요. 처음에는 slow_memcpy()를 통해 느린 복사를 다음은 fast_memcpy()를 통해 빠른 복사를 하는 것 같습니다. 

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

slow_memcpy는 단순히 배열대 배열로 복사를 해주는 함수입니다. 

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

fast_memcpy 함수는 movdqa와 movntps 명령어를 이용해서 어셈블리어로 메모리 단계에서 빠르게 복사하는 함수입니다. 그리고 64바이트보다 작을 경우는 slow_memcpy를 실행하네요. 

멈춘 부분을 보면 slow_memcpy는 실행되고 fast_memcpy가 실행되지 않은 것을 알 수 있습니다. fast_memcpy에서 문제가 발생한 거겠죠. 정확히 무슨 문제인지는 아직 모르지만 위에서 공부했듯이 movdqa는 정렬된 데이터만을 처리한다는 것을 알고 있습니다. 이 부분을 공략해 보도록 하겠습니다. 

그러기 위해서 우선  movdqa가 실행되는 주소를 알아야 하기에 tmp 파일로 가서 memcpy.c를 조금 수정하도록 하겠습니다.

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);

		printf("src: %p \n",src);
                printf("dest: %p \n",dest);
                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");
        }

복사하는 부분에서 slow_memcpy가 수행된 뒤에 src와 dest의 주소를 볼 수 있는 코드를 추가했습니다.

다시 보니 dest가 복사할 때마다 위치가 증가하는데 중간중간 16바이트(128비트)로 정렬되지 않은 부분이 보입니다. 64바이트 보다 작은 경우는 어차피 들어가도 slow_memcpy가 수행되므로 상관없지만 movdqa가 사용되는 부분은 문제가 되는 거 같습니다. 사이즈를 조정해서 하나씩 맞춰 보도록 하겠습니다.

8씩 더해주니 깔끔하게 모두 맞아떨어지네요. 이제 원래 프로그램으로 돌아가 작동시켜 flag를 확인해 보겠습니다.

After Review

---

음 사실 완전한 이해를 통해 풀었다기보다 몇 번 시도하다 보니 몇 개 더 나와서 아 dest를 맞추면 되는구나 해서 풀었습니다.  movdqa가  source 레지스터가 정렬되어 있어야 되는 거라 생각해서 src 주소 증가량을 봐야 되나 싶었는데 그냥 dest만 맞추니 되더군요. 내부적으로 뭔가 더 있는 건지 궁금하네요. 질문해 보고 더 알아오도록 하겠습니다.

감사합니다.