[완료] 퀵소트의 보안 문제
글쓴이: newpolaris / 작성시간: 금, 2008/10/31 - 5:07오후
http://en.wikipedia.org/wiki/Heapsort
에
Quicksort is typically somewhat faster, due to better cache behavior and other factors, but the worst-case running time for quicksort is O(n2), which is unacceptable for large data sets and can be deliberately triggered given enough knowledge of the implementation, creating a security risk. See quicksort for a detailed discussion of this problem, and possible solutions.
이렇게 나와 있는데요.
deliberately triggered given enough knowledge of the implementation, creating a security risk.
이 부분이 잘 이해가 안됩니다.
저 구현의 충분한 지식을 준다는게 n^2을 일으키는 입력을 넣고 구조를 알아본다는 건가요?
Forums:
정렬된 데이타를
정렬된 데이타를 입력으로 받을 경우 quicksort 는 bubble sort 와 동일한 n^2 의 계산 복잡도를 가집니다. n^2 은 그얘기를 하고 있는 것이구요.
보안 문제라면 굉장히 많은 데이타를 정렬하는 경우 스택 오버플로우의 위험이 있다는 얘기일겁니다. log n 만큼의 스택을 채워야 할테니...
--
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...
http://mytears.org ~(~_~)~
나 한줄기 바람처럼..
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...
http://mytears.org ~(~_~)~
나 한줄기 바람처럼..
스택
스택 오버플로우보다는 정렬을 하는 것만으로 DoS 공격이 가능하다는 얘기일 것 같습니다. (재귀 문제라면 비재귀 형태로 고쳐서 짜면 되니까요.) 퀵 정렬을 할 때 pivot이 결정적인 방법으로 정해진다면 (흔히 쓰는 median-of-3 같은 것들이 여기에 포함됩니다) 이 결정적인 방법을 역으로 이용해서 O(n^2) 시간이 걸리게 하는 데이터를 항상 만들 수 있거든요. 비결정적인 방법(randomized quick sort 등)을 쓸 경우 이런 위험은 줄어 듭니다만 난수 생성기의 부하가 꽤 크기 때문에 실용적으로 쓸만할 지는 모르겠습니다.
힙 정렬은 어떤 경우에도 항상 O(n log n)의 성능을 내기 때문에 퀵 정렬에 비해서 평균은 좀 느릴지 몰라도 이런 공격이 힘들게 됩니다. 어느 쪽을 쓸 거냐는 실제 용례와 요구되는 보안 수준 등에 따라서 결정되어야 겠죠.
그건 아닌 것
그건 아닌 것 같습니다.
그런 식으로 따지면 for 나 while 이나 goto 등을 죽여버려야죠.
OTL
일부만 번역하자면
...which is unacceptable for large data sets and can be deliberately triggered given enough knowledge of the implementation, creating a security risk.
...이는 (= O(n^2) time) 데이터가 클 경우 일어나서는 안될 일이며, (해당 프로그램의 자세한 quicksort 구현 방식에 대해) 충분한 지식이 있다면 (예를 들면 소스 코드를 볼 수 있다든지..) 의도적으로 이런 상황을 만들 수 있는데, 이는 보안상 위험 요소가 된다.
위의 lifthrasiir 님 말이 정확한 해석입니다. 해당 implementation에 대해 잘 알고 있다면 의도적으로 O(n^2)을 발생시켜 DOS 공격에 써먹을 수 있다는 얘기죠.
자답
detailed discussion of this problem
은 qsort의 문제점을 지적한 모 논문을 가르킨거다.
MIT 알고리즘책에 언급되어있으며
나름 히트친 논문이다. 제목은 까먹음 대충 검색하면 나올듯
보통 알고리즘 공격자는 알고리즘의 모든 소스, call stack, register등 모든 변수에 접근이 가능하다고 가정되는데
해당 논문에서는 이를 이용하여 n^2이 되도록 작동되는 순열을 만들수 있음을 보여주었다.
방식은 머였는지 기억은 안나지만 프로그램을 따라가는 형식이라고 기억한다.
nEW
nEW
댓글 달기