qsortを撃墜し(最悪ケースを与え)てみた。
glibcのqsortをターゲットに、クイックソートの最悪ケースO(n^2)を与えてみた。
先日の記事の通り、glibcのqsortはマージソートだが、非常に大きいデータのときはクイックソートを利用するので、そのように仕向けてみた。
実行した結果、約5億バイトの配列が確保され、ソートにかかった時間は以下のようになった。
- マージソート(非アタック用データ):37126ミリ秒
- マージソート(アタック用データ):46724ミリ秒
- クイックソート(非アタック用データ):39189ミリ秒
- クイックソート(アタック用データ):中断(507514ミリ秒以上)
明らかに最悪ケースである。
環境は
- OS: Debian GNU/Linux (sid/unstable)
- Compiler: gcc version 4.3.3 (Debian 4.3.3-8)
- C Library: glibc version 2.9-8
もちろん、別のCライブラリ相手では撃墜できない可能性が高い。
#include <stdio.h> #include <stdlib.h> #include <signal.h> #include <sys/time.h> #include <unistd.h> #include <err.h> #include <errno.h> static struct timeval starttime, endtime; static int started = 0; static void start_timer(void) { if(!started) { started = 1; gettimeofday(&starttime, NULL); } } static void end_timer(const char *msg) { if(started) { started = 0; gettimeofday(&endtime, NULL); printf("%s %ldmsecs.\n", msg, (endtime.tv_sec-starttime.tv_sec)*1000+(endtime.tv_usec-starttime.tv_usec)/1000); } } static int intcmp(const int *a, const int *b) { return (*a == *b) ? 0 : (*a > *b) ? 1 : -1; } static void attack_main(size_t memsize, int does_attack) { size_t arysize; int *ptr; ptr = (int*)malloc(memsize); if(ptr) { int i; printf("safely allocated %d bytes.\n", memsize); arysize = (memsize / sizeof(int)) & ~1; printf("generating sequences...\n"); for(i = 0; i < arysize/2; ++i) { int nextsize = (i+1)*2; int nextmid = (nextsize-1)/2; int tmp; ptr[i*2] = i; ptr[i*2+1] = i; if(does_attack) { tmp = ptr[nextmid]; ptr[nextmid] = ptr[i*2]; ptr[i*2] = tmp; } } printf("sorting...\n"); start_timer(); qsort(ptr, arysize, sizeof(int), (int(*)(const void*, const void*))intcmp); end_timer("sorted."); printf("the first element is:%d\n", ptr[0]); free(ptr); printf("finished.\n\n"); } else { err(errno,NULL); } } static void sigint_action(int signum, siginfo_t *info, void *ctx) { end_timer("aborted."); exit(1); } int main(int argc, char *argv[], char *envp[]) { long int phys_pages; int pagesize; long long int all_memory; struct sigaction sa_sigint; sa_sigint.sa_sigaction = sigint_action; sa_sigint.sa_flags = SA_RESTART | SA_SIGINFO; if (sigaction(SIGINT, &sa_sigint, NULL) < 0) { err(errno, NULL); exit(1); } srand(2009u); phys_pages = sysconf(_SC_PHYS_PAGES); pagesize = sysconf(_SC_PAGESIZE); all_memory = (long long int)phys_pages*pagesize; printf("%ld * %d = %lld;\n", phys_pages, pagesize, all_memory); printf("testing phys_pages*pagesize/4 bytes (maybe merge sort in glibc)...\n"); attack_main((size_t)(all_memory / 4), 0); printf("testing phys_pages*pagesize/4 bytes (maybe merge sort in glibc) with ATTACK...\n"); attack_main((size_t)(all_memory / 4), 1); printf("testing phys_pages*pagesize/4 + 10000 bytes (maybe quick sort in glibc)...\n"); attack_main((size_t)(all_memory / 4 + 10000), 0); printf("testing phys_pages*pagesize/4 + 10000 bytes (maybe quick sort in glibc) with ATTACK...\n"); attack_main((size_t)(all_memory / 4 + 10000), 1); return 0; }
% ./qsattack 516777 * 4096 = 2116718592; testing phys_pages*pagesize/4 bytes (maybe merge sort in glibc)... safely allocated 529179648 bytes. generating sequences... sorting... sorted. 37126msecs. the first element is:0 finished. testing phys_pages*pagesize/4 bytes (maybe merge sort in glibc) with ATTACK... safely allocated 529179648 bytes. generating sequences... sorting... sorted. 46724msecs. the first element is:0 finished. testing phys_pages*pagesize/4 + 10000 bytes (maybe quick sort in glibc)... safely allocated 529189648 bytes. generating sequences... sorting... sorted. 39189msecs. the first element is:0 finished. testing phys_pages*pagesize/4 + 10000 bytes (maybe quick sort in glibc) with ATTACK... safely allocated 529189648 bytes. generating sequences... sorting... ^Caborted. 507514msecs.