[pwnable.kr] memcpy(10 pts) :: Write-Up

 

 

 

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.

 

https://pwnable.kr/bin/memcpy.c

 

ssh memcpy@pwnable.kr -p2222 (pw:guest)

 

 

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

 

일단 코드를 분석해봅시다.

 

 

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

우선 memcpy를 할 size를 입력받습니다.

 

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

그 후에 size에 대한 memcpy를 진행하는데, 이때 rdtsc를 진행합니다.

rdtsc가 뭐냐, 

참고: https://choayo.tistory.com/88

RDTSC

 

MOVDQA (Move Aligned Double Quadword)

데이터 전송 명령어로, 128bits의 데이터를 한 번에 xmm 레지스터로 이동하거나, 반대로 xmm레지스터의 데이터를 메모리로 전송하는 처리를 한다.

 

MOVNTPS (Store Packed Single-Precision Floating-Point Values Using Non-Temporal Hint)

두 번째 오퍼랜드로 입력받은 XMM 레지스터에 있는 float형 데이터 4개를 캐시를 통하지 않고 첫 번째 오퍼랜드로 입력받은 메모리 주소로 복사한다.

 

라고 하네요. 아래 링크 참고했습니다.

MOVDQA: http://www.jaist.ac.jp/iscenter-new/mpc/altix/altixdata/opt/intel/vtune/doc/users_guide/mergedProjects/analyzer_ec/mergedProjects/reference_olh/mergedProjects/instructions/instruct32_hh/vc183.htm

MOVNTPS: http://x86.renejeschke.de/html/file_module_x86_id_197.html

 

근데 xmm레지스터도 뭔지 모르겠어서 찾아봤습니다.

 

CPU에서 정보를 처리하기 위해서는 반드시 레지스터라고 하는 CPU내부의 임시 기억장소에 데이터를 적재해야 한다. 일반 범용 레지스터로 EAX, EBX, ECX, EDX 같은 게 있고 특수 용도 레지스터로 ESP, EBP 같은게 있는데 이런 것들이 모두 SISD용 레지스터다. SIMD용으로도 레지스터가 존재하며 여러 데이터를 한번에 처리하기 위해 일반 범용 레지스터보다 용량이 크다. XMM0, XMM1 같은 이름이 붙어있고 CPU가 지원하는 기술이 뭐냐에 따라 이 레지스터도 달라진다. (xmm0~xmm7)

ㅖ... 뭐 그렇다네요

 

아무튼 SIMD용 레지스터이고, 32비트 정수 네 개의 배열로 간주하고 연산한다고 한다.

따라서 32*4 = 128, 128bit memory의 배수이면 될 것 같다.

 

맨 처음에는 말그대로 128의 배수..? 이러면서 삽질했는데, 생각해보니까 bit였다. 즉 16byte, 0x10..... 바보같으니라고...

해당하는 범위 안에서 0x10의 값들을 집어넣었다. 컴파일링 안하고 하려고 애를 썼지만 결국.... 노가다랑 삽질 열심히 하면서 풀었다.
풀이과정은......귀찮아서...미앙.....

 

 

직접 중간에 gdb로 까봐서 FM의 dest addr을 확인하면서 삽질했다.

아무튼 8, 16, 32, 72, 136, 264, 520, 1032, 2056, 4096을 차례로 입력해주면 문제가 풀린다.

 

 

굳굳