Apache Web Server 1.2 beck exploit 버그의 교훈

-

Apache web server 1.2 beck exploit 는 Apache Web Server 1.2에 있던 버그라고 합니다.
(http://www.iss.net/security_center/reference/vuln/HTTP_Apache_DOS.htm 참조.)
Apache web server에는 / (slash) 가 동시에 여러 개 입력되는 URL이 있는 경우에 이를  이를 1개로 만드는 기능이 있습니다. 예를 들어, /d1///d2////d3/test.html 의 값으로 입력되면, 이를 /d1/d2/d3/test.html로 변환하는 기능입니다. 그런데 프로그램 모듈(no2slash)의 버그 때문에 시스템의 성능을 저하시키는 영향을 미치게 되어, DOS (denial of service) 공격이 용이하게 하는 문제를 안고 있었습니다. 이 프로그램의 원문은 다음과 같습니다.

void no2slash(char *name) {
  int x, y;
  for (x = 0; name[x]; ) {
    if (x && (name[x-1] == '/') && (name[x] == '/')) {
      for (y = x + 1; name[y-1]; y++)
        name[y-1] = name[y];
    }
    else {
      x++;
    }
  }
}

이 프로그램의 시간 복잡도는 2차(quadratic) 식입니다. 즉, ‘/’ 의 개수의 제곱에 비례하는 수행 시간이 증가하는 특성이 나타납니다. 이 특성 때문에, 많은 개수의 ‘/’가 포함된 URL이 주어지면, 이를 처리하느라 CPU의 시간을 다 소모하게 됩니다. 이를 개선한 프로그램은 다음과 같습니다.

public void no2slash2(char[] name) {
  int n = name.length;
  int offset = 0;
  for (int i = 1; i < n; i++) {
    if ((name[i-1] == '/') && (name[i] == '/')) {
      offset++;
    }
    else {
      name[i-offset] = name[i];
    }
  }
}

이 알고리즘의 시간 복잡도는 선형적(linear)입니다. 즉, ‘/’ 의 개수에 비례하여 수행시간이 증가하게 됩니다.

이 사례는 몇 가지 교훈을 남기고 있습니다.

1. 프로그램의 알고리즘은 매우 중요하다.

이 두 개의 프로그램의 정확성에는 문제가 없습니다. 둘 다 정확하게 원하는 결과를 얻을 수 있습니다. 하지만, quadratic 알고리즘과 linear 알고리즘은 그 수행 속도에서 매우 큰 차이를 보입니다. ‘/’ 가 500개가 연속되어 나타나는 URL로 테스트를 해 보면, 처음의 프로그램은 for 루프 안에서 130,000번을 헤매게 됩니다. 반면에, 개선된 프로그램은 510번만을 수행합니다. 단순하게 비교하면, 처음의 프로그램이 250배이나 많은 연산을 수행하고 있습니다. 뒤집어서 말하면, 개선된 프로그램이 250건의 request를 처리하는 동안, 최초의 프로그램은 단 1건만 처리할 수 있다는 것입니다. 따라서, 좋은 알고리즘을 찾기 위한 노력은 매우 중요합니다.

2. 알고리즘은 매우 고차원적인 프로그램에서만 사용되는 것은 아니다.

알고리즘의 개선은 프로그램에 작성할 때 고민하는 것은 매우 복잡하고, 어렵고, 고차원적인 수준의 프로그램에만 국한되는 것은 아닙니다. 이 경우처럼 중복되는 ‘/’ 를 제거하는, 어찌 보면 매우 단순한 로직에서도 사용됩니다.

3. 프로그램이 논리적으로 동작한다고 해서 완성된 것은 아니다.

정확하게 동작하는 것은 프로그램의 기본이지만 그것만으로 개발자의 역할이 끝난 것은 아닙니다.


문제 1:  '/' 가 500개 일 때, 프로그램 2는 0.0001 초의 시간이 걸리고, 프로그램 1은 0.0250 초가 걸린다고 할 때,
'/'가 10배인 5000개일 때는 각각의 프로그램은 얼마의 시간에 수행될까요?


문제 2:  '/' 가 500개 일 때, 수행 연산의 수에서 250배의 차이를 보였다면, 10배인 5000개일 때는 얼마의 차이를 보일까요?
(1) 250배    (2) 2,500배

문제1의 답: 프로그램 2는 0.001 초, 프로그램 1은 2.5 초가 소요된다.

문제2의 답: (2)
이유는, N^2 : N = 250 : 1 이므로,
(10N)^2 : 10N = 100N^2 : 10N = 10N^2 : N = 2500 : 1

댓글

댓글 쓰기

이 블로그의 인기 게시물

Java의 String 객체의 메모리 사용량

-
인터넷에서 자료를 찾다가, 우연히 다른 사람의 블로그를 방문하였습니다. 그 블로그에서는 다음의 두 프로그램이 JVM 메모리 사용량 관점에서 볼 때 너무 상이한 결과가 나온다면서 의아해하더군요. Program 1 String str = "0123456789"; List list = new ArrayList(100); long realSize = 0; for (int i = 1; i < 100000000; i++) {   String data = “0123456789” + str;   list.add(data);   realSize += data.getBytes().length   if (i % 10000 == 0)     System.out.println("dataCount=" + i + ",dataSize=" + realSize); } 간단한 이 Java 프로그램을 -Xms256M -Xmx256M의 옵션으로 실행하면, 약 300만개(3,000,000)의 String을 ArrayList에 저장하고 out of memory 에러가 발생합니다. 즉, 256MB 정도의 메모리를 사용하는 Java 프로그램은 문자가 20개인 String 객체를 300만개 정도 만들어서 다룰 수 있습니다. 반면에 다음의 프로그램을 보시죠. Program 2 String str = "0123456789"; List list = new ArrayList(100); long realSize = 0; for (int i = 1; i < 100000000; i++) {   String data = new String("01234567890123456789"); // 요기 한줄만 다릅니다.   list.add(data);   realSize += data.getBytes().length   if (i % 10000 == 0)    System.out.println("d
자세한 내용 보기

리틀의 법칙 – Little’s law

-
IT관련 프로젝트를 진행하다 보면 심심치 않게 성능과 용량에 대한 문제를 다루게 됩니다. 성능과 용량 문제는 매우 복잡하고 알아야 할 것이 많은 부분입니다. 그리고 이런 분야는 수요가 그리 많지 않기 때문에 많은 사람들이 크게 관심을 기울이지 않습니다. 이 부분에 대한 가장 기본적인 수식으로 리틀의 법칙 (Little's law)이라는 것이 있습니다. 계산식은 간단하며 다음과 같습니다. n = x * (z + r) 여기서 각 변수의 의미는 다음과 같습니다. n - 동시 상용자 수, x - 시스템이 처리 가능한 용량, 다른 용어로는 throughput이라고 합니다. r - 단위 처리의 응답 시간, z - 각 단위 처리 사이의 간격 (이른바 씽크타임, think time). 이 법칙에 대한 예를 들어보겠습니다. 간단한 성능 테스트를 진행했을 때의 결과가 다음과 같이 나왔다고 가정해보겠습니다. 동시에 1명이 접속하고 think time은 0이고, 꽤 많은 횟수를 테스트할 때 평균 응답 시간이 2초로 측정되었다면 이를 리틀의 법칙 수식에 넣으면 다음과 같이 될 것입니다. 1 user = x * (0 sec + 2 sec) 이 수식을 풀면 x 값은 0.5 (user/sec)가 됩니다. 즉, 1초에 0.5 사용자의 동시 요청을 처리할 수 있는 용량입니다. 잠깐만요… throughput 즉 x 값이 0.5라면 너무 적은 값이 아닌가요? 그렇습니다. 이 테스트의 결과로는 throughput은 0.5가 맞습니다. 단, 최대 throughput은 아닙니다. 동일한 시스템에 대하여 더 테스트를 진행합니다. 그래서 다음과 같은 측정값들을 얻었습니다. 동시에 5명이 접속하고, think time은 0 (그리고 당연히 꽤 많은 횟수를 테스트하고) 일 때, 평균 응답 시간이 2.3초가 나왔다면, 다음과 같이 수식이 나올 것입니다. 5 user = x * (0 sec + 2.3 sec) 이 식을 계산하면 x는 대략 2.17 users/sec 의 값을 갖습니다.
자세한 내용 보기

true, false, positive, negative – TP/TN/FN/FP

-
그다지 복잡한 내용도 아니고 몇 번을 보고 외우고 했던 내용이지만 자꾸 헷갈려서 정리를 합니다. 스팸 메일 필터를 예로 들어 보겠습니다. 실제 한통의 메일은 스팸일 수도 있고 아닐 수도 있습니다. 이 한통의 메일을 스팸 필터가 판단을 해서 스팸인지 아닌지를 구분합니다. 그러면 다음과 같이 4가지의 결과가 나올 수 있습니다. 실제로는 스팸 - 스팸이라고 판정: 이 경우를 true positive(TP)라고 합니다. 실제로는 스팸 – 스팸이 아니라고 판정 – 이 경우를 false negative(FN)라고 합니다. 실제로는 스팸 아님 – 스팸이라고 판정 – 이 경우를 false positive(FP)라고 합니다. 실제로는 스팸 아님 – 스팸이 아니라고 판정 – 이 경우를 true negative(TN)라고 합니다. 이를 도표로 정리하면 아래와 같습니다.   스팸이라고 판정 스팸이 아니라고 판정 실제로 스팸 true postivie false negative 실제로 스팸이 아님 false positive true negative
자세한 내용 보기