Boyer-moore 문자열 탐색 알고리즘은 Robert S. Boyer와 J Strother Moore에 의해 1977년에 개발되었다. 

알고리즘의 컨셉은 패턴을 뒤에서부터 비교하여 탐지하는 것이 특징이다. 

Boyer-moore 알고리즘은 크게 다음 두 가지 방식의 탐지 방식을 사용하고 있다.

두 가지 방식 중 더 큰 값만큼 이동하면서 패턴 매칭을 시도하게 된다. 

1. bad character method 

주로, 문자열이 매칭되지 않았을 때 많이 이동 할 수 있는 알고리즘. 
character set인 256만큼의 배열을 잡아서 패턴 길이 값으로 초기화를 시켜준다. 

이후 패턴의 앞 부터 한자씩 읽어 가면서 해당 배열값에 마지막 글자까지의 값으로 설정
예를 들면, 아래 문장의 가장 처음 'A'의 경우, 'A'는 10진수 65이다. 
그러므로, 배열의 65번째 값에 'A'와 패턴의 끝인 'N' 와 7글자 떨어져 있으므로 7을 넣어준다. 
이와 같은 방식으로 A->N->P->A->N->M->A를 처리한다. 만약, 동일한 문자가 나오면 마지막 글자와 가까운 위치에 탐지를 해야할 문자가 있는 것이므로 해당 값을 덮어쓰게 된다.  (마지막 글자 N은 떨어진 거리가 0이므로 제외)
그 결과 아래 표와 같은 결과를 얻을 수 있다. 

예) ANPANMAN 

Character	Shift
A	1
M	2
N	3
P	5
all other characters	8

2. good-sufix method 
주로, 문자열이 매칭된 경우 많이 이동할 수 있는 알고리즘. 
입력받은 패턴을 가지고 최대 이동 값을 미리 계산해둔다. (문자열 길이만큼의 배열)

최대 이동값을 계산하는 방식은 아래 표와 같다.  

i는 현재 패턴을 매칭하기까지 매칭에 성공한 문자 개수이다. 
pattern에서 취소선이 그어져 있다면, 해당 문자는 매칭이 되지 않음을 의미한다. 
Left shift는 왼쪽으로 얼마만큼 이동할지를 의미한다. 
(최종적으로 배열에는 i + left shift 값으로 설정해주게 된다. )

예) ANPANMAN 

i	Pattern	Left Shift
0	N	오른쪽 끝 문자가 N이 아닌 문자만큼 왼쪽으로 이동. 오른쪽 두번째 문자가 A이므로, 한 칸 이동한다. (만약 'ANPANMNN'이라면 두 칸 이동하게 된다. )  = 1
1	AN	AN 은 ANPANMAN에 더이상 나오지 않는다. 때문에, 패턴 길이 만큼 이동하게 된다. = 8
2	MAN	MAN 은 ANPANMAN  패턴에서 세칸 이동하면 찾을 수 있다.   = 3
3	NMAN	'NMAN' 은  'ANPANMAN' 에 더이상 나오지 않는다.  하지만,  'NMAN' 은 6 칸 이동하면 또 나타난다.   ('NMANPANMAN')  = 6
4	ANMAN	'ANMAN'은 더이상 나오지 않는다. 하지만,'ANMAN' 은 6 칸 이동하면 나타난다.    ('ANMANPANMAN') = 6
5	PANMAN	'PANMAN'은 더이상 나오지 않는다. 하지만, ' PANMAN' 은 6 칸 이동하면 나타난다.     ('PANMANPANMAN')  = 6
6	NPANMAN	'NPANMAN'은 더이상 나오지 않는다. 하지만, ' NPANMAN' 은 6 칸 이동하면 나타난다.      ('NPANMANPANMAN')  = 6
7	ANPANMAN	'ANPANMAN'은 더이상 나오지 않는다. 하지만, ' ANPANMAN' 은 6 칸 이동하면 나타난다.       ('ANPANMANPANMAN')  = 6

• 탐지 예제

순번

M

A

N

P

A

N

P

A

N

M

A

N

1

A

N

P

A

N

M

A

N

2

A

N

P

A

N

M

A

N

3

A

N

P

A

N

M

A

N

- 순번 1: 패턴의 뒤에서부터 매칭을 시도 하면 문자열 ‘A’와 패턴 ‘N’이 같지 않으므로 이동을 해야 한다. bad-character method 와 good-suffix method모두 이동 값이 1 이므로 1칸만 이동.

- 순번 2: 뒤에서 ‘AN’이 매칭되었으므로, bad-character method에 의해 ‘P’의 이동 값이 5에서 ‘AN’ 두 문자만큼의 값을 뺀 3만큼 이동하게 된다. Good-suffix method에 의해서도 i가 2일 때 값이 3이므로 3만큼 이동하여 다시 매칭을 시도한다. 

- 순번 3: 원하는 문자열을 찾았다. 

정규표현식에 대해 생소한 분들은 초/중급 포스팅을 참고하세요. 
정규표현식 초급, 정규표현식 중급 


 여기서는 자주 사용되지는 않지만..
잘 알고 사용하면 여러가지로 유용한 내용들에 대해 다뤄보고자 합니다.

1. 단어 경계 - \b, \B 
 매칭하고자 하는 패턴의 단어 경계를 지정하는데 사용. 

단어의 경계를 찾는 '\b'옵션을 사용하면
문자열 중 일부에만 매칭되는 경우는 제외하게 된다. 
====================================
  표현식  \bart\b
  문자열  The art of music part of artist
==================================== 

'\B' 는  '\b'와 반대의 의미로 사용된다. 


2. 비 캡처 그룹 - (?: )
그룹화 기호를 사용해서 매칭을 시도할 경우 
매칭되는 내용은 캡처되어 추후에 재사용 할 수 있도록 한다. 

하지만, 재사용할 일이 없을 경우 
비 캡처 그룹으로 표현해주므로써 캡처 그룹에서 제외시키고,
적지만 성능 향상도 기대할 수 있다. 
====================================
  표현식  (?:one|two|three)
==================================== 


3. 명명 재참조 - (?P<name>) , (?<name>)혹은 (?'name') 
특정한 패턴을 캡처한 후 이를 사용하기 편하도록 이름을 지어준 후
그 이름으로 캡처된 패턴을 불러다 사용.

캡처된 값들에 이름을 지정해주므로써 보는 사람 관점에서도 이해하기 쉽도록 도와주고, 
특정 위치의 값을 저장해두었다가 다른 위치에서 동일한 값이 나오는지 확인 하는데 유용함.

방식은 크게 세가지가 지원되며, 버전에 따라 지원되지 않는 것도 있을 수 있다. 
값을 캡처하고 명명 할 때와 이를 호출해서 사용 하는 방법은 다음과 같다. 


 
====================================
  표현식1  (?P<hour>\d\d):(?P<min>\d\d)-(?P=hour)-(?P=min)
  표현식2  (?<hour>\d\d):(?<min>\d\d)-\k<hour>-\k<min>
  표현식3  (?'hour'\d\d):(?'min'\d\d)-\k'hour'-\k'min'

  문자열  17:53-17-53
==================================== 


4. 주석 처리 - (?# ) 혹은 (?#>     <)
정규표현식에 설명을 추가하고 싶을 때 사용.
자칫 잘못 사용하면 복잡도가 증가하여 오히려 역효과를 불러 일이킬 수 있다. 

 
====================================
  표현식  (?#year)\d{4}-(?#mon)\d{2}-(?#day)\d{2}
 
====================================

목적:
1. 웹 서버의 취약점을 사전에 검사해보고 기본적인 취약점을 보완함으로써 해커의 간단한 공격으로 부터 웹 서버를 보호
2. 웹 서버를 보호하는 보안 장비가 웹서버의 취약점을 스캔하는 행위를 정상적으로 탐지 하는지 검증

사용 절차:
1. nikto를 다운 받는다.
혹은 첨부된 파일을 받아도 됩니다.
(perl로 작성된 툴이므로 perl관련 라이브러리가 설치되어 있어야 한다.)
http://cirt.net/nikto2 

 

2. nikto 실행
타겟 호스트와 실행 옵션을 주고 실행
# ./nikto.pl  -h 66.66.66.11 -output result.html -Format html  -Cgidirs all

3. 세부 옵션 설정 
(괄호 안에 표기된 문자는 약자)
-config (c)      config 파일을 지정. 기본 설정값을 포함한 nikto.config 파일이 있으니 참고하면 된다.
-host (h)        스캔을 수행할 웹서버(호스트) 주소
-Cgidirs (C)    스캔할 CGI 디렉토리를 설정. 메뉴얼에 의하면 all을 권장함.
-output  (o)     결과를 출력할 파일 지정
-Single (S)      스캔을 한 개씩 옵션을 지정해주면서 수행. 단일 스캔을 수행 할 때 사용.  

자세한 설정은 '-H' 옵션으로 확인 가능하다.

결과 확인:
결과는 다음과 같이 화면에 출력된다.
---------------------------------------------------------------------------
+ Target IP:          66.66.66.11
+ Target Hostname:    cpe-66-66-66-11.rochester.res.rr.com
+ Target Port:        80
+ Start Time:         2011-08-18 01:00:00
---------------------------------------------------------------------------
+ Server: Microsoft-IIS/5.0
+ Retrieved x-powered-by header: ASP.NET
+ Retrieved x-aspnet-version header: 2.0.50727
+ Microsoft-IIS/5.0 appears to be outdated (4.0 for NT 4, 5.0 for Win2k, current is at least 7.5)
+ OSVDB-397: HTTP method 'PUT' allows clients to save files on the web server.
+ OSVDB-5646: HTTP method 'DELETE' allows clients to delete files on the web server.
+ Retrieved dasl header: <DAV:sql>
+ Retrieved dav header: 1, 2
+ Retrieved ms-author-via header: DAV
+ OSVDB-13431: PROPFIND HTTP verb may show the server's internal IP address: http://web-babo/_vti_bin/_vti_aut/author.dll
+ OSVDB-877: HTTP TRACE method is active, suggesting the host is vulnerable to XST
+ OSVDB-877: HTTP TRACK method is active, suggesting the host is vulnerable to XST
+ OSVDB-396: /_vti_bin/shtml.exe: Attackers may be able to crash FrontPage by requesting a DOS device, like shtml.exe/aux.htm -- a DoS was not attempted.
+ OSVDB-3092: /_vti_pvt/deptodoc.btr: FrontPage file found. This may contain useful information.
+ OSVDB-3092: /_vti_pvt/doctodep.btr: FrontPage file found. This may contain useful information.
+ OSVDB-473: /_vti_pvt/access.cnf: Contains HTTP server-specific access control information. Remove or ACL if FrontPage is not being used.
+ OSVDB-272: /msadc/msadcs.dll: See RDS advisory RFP9902, CVE-1999-1011, http://www.microsoft.com/technet/security/bulletin/MS98-004.asp, http://www.microsoft.com/technet/security/bulletin/MS99-025.asp RFP-9902 BID-29 (http://www.wiretrip.net/rfp/p/doc.asp/i2/d1.htm), CIAC J-054 http://www.ciac.org/ciac/bulletins/j-054.shtml www.securityfocus.com/bid/529
+ OSVDB-3092: /admin/: This might be interesting...
+ OSVDB-3092: /img/: This might be interesting...
+ OSVDB-3092: /test.txt: This might be interesting...
+ OSVDB-3233: /_private/: FrontPage directory found.
+ OSVDB-3233: /_vti_bin/: FrontPage directory found.
+ OSVDB-3233: /_vti_inf.html: FrontPage/SharePoint is installed and reveals its version number (check HTML source for more information).
+ OSVDB-3092: /Admin/: This might be interesting...
+ 6456 items checked: 6535 error(s) and 41 item(s) reported on remote host
+ End Time:           2011-08-18 01:02:09 (129 seconds)
---------------------------------------------------------------------------
+ 1 host(s) tested

대부분의 결과가 OSVDB-xxx 라는 패턴으로 시작하는 것을 알 수 있다.
OSVDB는 The Open Source Vulnerability Database의 약자로 해당 홈페이지에서 자세한 내용을 확인 가능하다.


OSVDB(The Open Source Vulnerability Database) 홈페이지
http://osvdb.org/

1. 홈페이지 좌측 상단의 OSVDB ID Lookup칸에 nikto 수행 결과로 나온 값을 검색

2. 다음 주소의 id값만 바꿔서 바로 해당 내용을 조회 가는 것도 가능
http://osvdb.org/show/osvdb/3233

목적:
Http의 url에서 자주 사용되는 다양한 인코딩(encoding)에 대한 정리 

※내용은 중요하지 않고 인코딩된 패킷을 생성하고 싶으시다면 다음 포스팅을 참고하세요. 
http://kthan.tistory.com/46


내용:
 1.  Hex Encoding 
URL을 인코딩 하는 가장 간단한 방법 RFC 표준에 따른다.


 
2. Double Percent Hex Encoding
Microsoft IIS에서 지원한다. 
Hex Encoding에 기반하는 encoding방식으로..
'%25' 가 '%'를 의미하기 때문에 결국은 한번 꼬았다고 보면 된다. 



3.  Double Nibble Hex Encoding
Microsoft IIS에서 지원한다. 
인코딩 할 값을 하나씩 나눠서 각각 인코딩을 한다. (nibble이란 단어의 의미를 곰곰히 생각해보면 이해하는데 조금 도움이 된다.)
'%34' 가 '4'이고 '%31'이 '1'을 의미하므로 각각을 디코딩 하면 결국 %41이 된다. 
 
 

4. First Nibble Hex Encoding  
Microsoft IIS에서 지원한다. 
바로 앞에서 다른 'Double Nibble Hex Encoding'과 유사하다. 
인코딩 이름에서 알 수 있듯 처음 nibble만 인코딩을 한다는 의미이다. 
즉, '%34'가 '4'이므로 이 값을 디코딩 하면 '%41'이 된다. 



5. Second Nibble Hex Encoding
Microsoft IIS에서 지원한다.  
이름을 봐서 알 수 있듯 .. First Nibble과 유사하다.
차이점이라면 두번째 nibble을 인코딩 한다는 점이 다르다.
문법상의 차이로 모양새는 조금 다르지만 이해하는데는 별 문제가 되지 않는다. 
'%31'이 '1'이므로 이 값을 디코딩 하면 '%41'이 된다. 


6.  Microsoft %U Encoding
Microsoft IIS에서 지원한다.  
%U뒤에 4자리 값이 오는 형식으로 인코딩 한다. 
4자리 값은 0부터 65535까지의 숫자 혹은 16진수로 0x0000 부터 0xffff까지 값이 올 수 있다. 

예) %U0041 = 'A' 

7. UTF-8 Encoding
처음 byte는 길이를 의미하므로 매우 중요하다. 

예) 110xxxxx 10xxxxxx                (two byte sequence)
     1110xxxx 10xxxxxx 10xxxxxx  (three byte sequence)

인코딩을 하기 위해 '%'를 사용한다. 
위에서 xxx 처럼 표현한 부분이 실제 의미있는 값이다. 
다음 예에서 보면.. 녹색으로 표시한 값들이 실제 데이터라고 보면 된다. 



Full UTF-8 Character Map 링크

8. UTF-8 Bare byte Encoding
Microsoft IIS 서버만이 지원한다. 
UTF-8 인코딩과 같지만 '%'를 쓰지 않는점이 다르다. 

목적:
HTTP url에는 다양한 encoding 방식에 의해 변환된 값들이 전송되기 된다. 
이 값들에 대한 재현 혹은 검증을 위해 사용

실행 파일: 
SetupHttpChameleon.exe
홈페이지:
http://www.idsresearch.org 

사용 절차:
위에서 부터 순차적으로 작성하시면 손쉽게 사용 가능합니다... 만.. 
간략하게 설명을 덧붙일께요. 

1. Http Encoding Library Templates에서 기본적인 양식을 선택 후 "Select" 클릭

2.  Http Request를 원하는 값으로 수정 후 

3. Encodings and Obfuscations에서  원하는 encoding 타입을 설정 후 "Encode" 클릭

4. Encoded Http Request 에서 원하는 request가 생성되었는지 확인

5. Http Host와 Http Port를 입력 하고 "Send Request" 클릭

6. Http Response에서 결과 확인  

※ 인코딩에 관한 자세한 내용을 알고 싶다면 다음 포스팅을 참고하세요. 
http://kthan.tistory.com/47 

 정규표현식이란?
특수한 텍스트 패턴에 일치하는지 여부를 검사하거나, 텍스트 내에서 특정 패턴과 일치하는 텍스트를 찾기 위해 사용하는 표현식
요즘은 어지간한 어플리케이션에서 모두 지원하고 있다.

정규표현식 툴
물론 돈을 주고 산다면 다양한 기능과 화려한 인터페이스를 자랑하는 툴도 많다. (RegexBuddy)
하지만.. 우리는 공짜를 좋아하기 때문에..
공짜인 "Rad RegexDesigner"를 추천한다

1. 바로 다운받아 사용하고 싶다면  (첨부파일 클릭)Rad.RegexDesigner.Setup.1.4.exe
2. 사이트에가서 설명을 보고 받고 싶다면..  (홈페이지 주소 클릭)

사용법은  "Input Text"에 문자열을 넣고 "Regular Expression"에 정규표현식을 넣은 후
상단에 있는 녹색 재생 버튼을 클릭하면 된다.
매칭 여부는 우측에 있는 "Match Results"에서 확인 가능하다"

예제의 경우 전체 문자열에서 정규표현식에 의해 매칭된 문자열이 네 개로 나온다.

그럼 중급 정규표현식에 대해 알아보자

1. Group ( ) 
특정 패턴을 묶어서 반복 기호등과 함께 사용
 

여러 문자 중 하나만 선택적으로 매칭하고자 할 때 사용.
====================================
  표현식   ba(na)*
  문자열  ba na bana banana nana bananana
====================================
====================================
  표현식   ba(na)+

  문자열  ba na bana banana nana bananana
 ====================================

2. 선택 지정 ( | ) 
괄호로 묶인 그룹 내에서 | 으로 나뉘어진 여러 개의 패턴 중 하나와 일치하는 것을 가리킨다. 
====================================
  표현식   (eg|sa|be)g
  문자열  egg eng sag sig beg bag
====================================
 

3. Group 참조  \숫자  (backreference)
 Group으로 지정된 내용을 뒤에 ‘\숫자’의 형식으로 재 사용하는데 사용.
 ====================================
  표현식   (h.t)\1
  문자열  hathat hitbit hothot hutcut

  표현식   \d\d(\d\d)-\1-\1
  문자열  2011-11-11
====================================

4. 반복 문자 탐지 – Greedy, Lazy
 반복 문자 개수를 지정하는 방법은 크게 Greedy방식과 Lazy방식으로 나뉘어진다.
 Greedy 방식은 가능한 최대의 것을 선택하고,  Lazy방식은 가능한 최소의 것을 선택한다.
 Greedy 방식뒤에 ?을 붙이면 Lazy방식이 된다.

-Greedy 방식
====================================
  표현식   <.*>
  문자열  Regex <b>Greedy</b> Style
====================================
-Lazy방식

====================================
  표현식   <.*?>
  문자열   Regex <i>Lazy</i> Style
====================================
- 사용 예

==================
 Greedy  |   Lazy 
==================
  *         |     *?
  +         |    +?
  ?         |     ??
 \d+       |   \d+?
 {n,m}    |   {n,m}?
==================

5.주요 Escape 문자 목록
 \t      탭 문자, Tab, \u0009 
 \r     줄 바꿈 문자, Carriage Return, \u000D 
 \n     줄 바꿈 문자, Line Feed, \u000A 
 \b     [ ] 안에서 사용될 때는 백스페이스 문자, Backspace, \u0008
         [ ] 밖에서 사용될 때는  단어 경계(Word Boundary), 즉 단어의 시작과 끝 빈문자에 매칭( \bhit => hit 과 매칭)
        치환 Pattern에서 사용될 때는 항상 백스페이스 문자
 \\     \ 문자 자체를 가리킬 때 사용
        비슷한 사용법 \.   \*   \+   \?   \^   \$   \(   \)   \{   \}   \[   \] 

6. 주요 특수문자 목록 

특수문자	문자 클래스	설명
\w	[0-9a-zA-Z_]	영문자, 숫자, 언더바(_)
\W	[^0-9a-zA-Z_]	영문자, 숫자, 언더바(_) 이외
\s	[\t\n\r\f]	공백( 반각 스페이스, 탭, 개행)
\S	[^\t\n\r\f]	공백 이외
\d	[0-9]	숫자
\D	[^0-9]	숫자 이외

 

참고 사이트 Joinc Wiki     <= 클릭