1. 링크드 리스트

1-1. 특징

- 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료구조

- 각 노드는 다음 노드를 가리키는 포인터를 가짐.

- 각 노드를 다음 노드를 가리키는 포인터로 연결하여 만든 리스트. Single Linked List라고도 함.

- 링크드 리스트의 첫 번째 노드를 헤드(Head), 마지막 노드를 테일(Tail)이라고 한다.

- 헤드(Head) : 첫번째 노드의 주소값을 가지고 있음(Pointer Type)

- 테일(Tail) : 마지막 노드의 주소값을 가지고 있음(Pointer Type)


1-2. 단점

- 앞에 있는 노드를 찾아갈 방법이 없다.


1-3. 배열과의 차이점

- 리스트는 주소를 통해 다른 노드로 접근하나 배열은 index 값을 통해 접근한다.


1-4. C언어로 표현하는 링크드 리스트의 노드

 typedef struct tagNode{

int Data; // 데이터 필드

struct tagNode* NextNode; // 다음 노드를 가리키는 포인터

}


1-5. 노드의 추가





1-6. 노드의 삭제

1-7. 노드의 삽입


2. 더블 링크드 리스트

2-1. 특징

- 각 노드가 앞 노드/뒷 노드 양쪽에 대한 포인터를 모두 갖고 있어 각 노드들을 이중으로 연결하는 리스트.


2-2. 노드의 추가



2-3. 노드의 삭제



2-4. 노드의 삽입




3. 환형 링크드 리스트

- 우로보로스처럼 머리(헤드)가 꼬리(테일)를 물고 있는 형태의 링크드 리스트


3-1. 노드 추가

- 최초의 노드를 추가하는 경우(즉, 노드가 한 개 뿐)


- 리스트에 노드가 이미 한 개 이상 존재하는 경우에는 테일과 헤드 사이에 새 노드를 삽입한다.

- 코드

void CDLL_AppendNode(Node** Head, Node* HeadNode)

{

/* 헤드 노드가 NULL이라면 새로운 노드가 Head */

if((*Head) == NULL)

{

*Head = HeadNode;

(*Head)->NextNode = *Head;

(*Head)->PrevNode = *Head;

}

else

{

/* 테일과 헤드 사이에 HeadNode를 삽입한다. */

Node* Tail = (*Head)->PrevNode;


Tail->NextNode->PrevNode = HeadNode;

Tail->NextNode = HeadNode;

HeadNode->NextNode = (*Head);

HeadNode->PrevNode = Tail /* 기존의 테일을 새로운 */

 /* 테일의 PrevNode가 가리킨다. */

}

}


3-2. 노드의 삭제

-코드

void CDLL_RemoveNode(Node** Head, Node* Remove){

if(*Head == Remove)

{

(*Head)->PrevNode->NextNode = Remove->NextNode;

(*Head)->NextNode->PrevNode = Remove->PrevNode;


*Head = Remove->NextNode;


Remove->PrevNode = NULL;

Remove->NextNode = NULL;

}

else

{

Node* Temp = Remove;


Remove->PrevNode->NextNode = Temp->NextNode;

Remove->NextNode->PrevNode = Temp->PrevNode;


Remove->PrevNode = NULL;

Remove->NextNode = NULL;

}

'2015-2학기 > 알고리즘' 카테고리의 다른 글

3장 큐  (0) 2015.09.14
2장 스택  (0) 2015.09.09
Posted by OnewayK
,

1. CPU 레지스터란?

- CPU 내부에 존재하는 다목적 저장 공간

- CPU와 한 몸이기 때문에 고속으로 데이터를 처리


1-1. 레지스터에 대해서 알아야 하는 이유

- 디버거가 해석(디스어셈)해주는 어셈블리 명령어를 공부해야 함

- 어셈블리 명령어의 대부분은 레지스터를 조작하고 그 내용을 검사하는 것이기 때문에 레지스터에 대해서 알아야함


2. IA-32의 레지스터

# IA-32 레지스터의 종류

+ Basic program execution registers

+ x87 FPU registers

+ MMX registers

+ XMM registers

+ Control registers

+ Memory management registers

+ Debug registers

+ Memory type range registers

+ Machine specific registers

+ Machine check register

* 초급 단계에서는 Basic program execution register에 대해 알아두고 중/고급 단계로 올라가면 추가적으로 Control registers Memory management registers, Debug registers 등에 대해서 공부하기 바람


2-1. Basic program execution registers

# 그룹

+ General Purpose Registers (32비트 - 8개)

+ Segment Registers (16비트 - 6개)

+ Program Status and Control Register (32비트 - 1개)

+ Instruction Pointer (32비트 - 1개)


1) 범용 레지스터

- 범용적으로 사용되는 레지스터

- 크기 : 32비트(4바이트)

- 상수/주소 등을 저장할 때 사용

- 특정 어셈블리 명령어에서는 특정 레지스터를 조작하기도 함


# 각 레지스터 이름 - 1

+ EAX : Accumulator for operands and results data

+ EBX : Pointer to data in the DS segment

+ ECX : Counter for string and loop operations

+ EDX : I/O pointer


- 주로 산술연산(ADD, SUB, XOR, OR 등) 명령에서 상수/변수 값을 저장하기 위해 사용

- MUL, DIV, LODS 등은 특정 레지스터를 직접 조작하기도 함

- ECX는 반복문 명령어(LOOP)에서 반복 카운트(loop count)로 사용

- EAX는 일반적으로 함수 리턴 값에 사용되며 모든 Win32 API 함수들은 리턴 값을 EAX에 저장한 후 리턴


# 각 레지스터의 이름 - 2

+ EBP : Pointer to data on the stack (in the SS segment)

+ ESI : source pointer for string operations

+ EDI : destination pointer for string operations

+ ESP : Stack pointer (in the SS segment)


- 주로 메모리 주소를 저장하는 포인터로 사용

- ESP는 스택 메모리 주소를 가리킴

- PUSH, POP, CALL, RET은 ESP를 직접 조작하기도 함

*Stack Frame 기법 : ESP는 함수가 호출되었을 때 그 순간의 ESP를 저장하고 있다가, 함수가 리턴 하기 직전에 다시 ESP에 값을 되돌려줘서 스택이 깨지지 않도록 함

- ESI와 EDI는 LODS, STOS, REP, MOVS 등과 함께 주로 메모리 복사에 사용


2) 세그먼트 레지스터

- 세그먼트 : IA-32의 메모리 관리 모델에서 나오는 용어

- IA-32 보호모드에서의 세그먼트 : 메모리를 조각내어 각 조각마다 시작 주소, 범위, 접근 권한 등을 부여해서 메모리를 보호하는 기법

- 세그먼트는 페이징(Paging) 기법과 함께 가상 메모리를 실제 물리 메모리로 변경할 때 사용

- 세그먼트 메모리는 Segment Descripor Table(SDT)이라고 하는 곳에 기술

- 세그먼트 레지스터는 SDT의 index를 가지고 있음

- 세그먼트 레지스터는 총 6개(CS, SS, DS, ES, FS, GS)이며, 각각의 크기는 16비트(2바이트)이다.


- 세그먼트 디스크립터(Segment Descriptor)와 가상 메모리가 조합되어 선형주소(Linear Address)가 되며, 페이징 기법에 의해서 선형주소가 최종적으로 물리주소(Physical Address)로 변환

* OS에서 페이징을 사용하지 않는다면 선형주소는 그대로 물리주소가 됨


# 세그먼트 레지스터의 이름

+ CS : Code Segment

+ SS : Stack Segment

+ DS : Eata Segment

+ ES : Extra(Data) Segment

+ FS : Data Segment

+ GS : Data Segment


- CS는 프로그램의 코드 세그먼트를 나타냄

- SS는 스택 세그먼트

- DS는 데이터 세그먼트

- ES, FS, GS 세그먼트는 추가적인 데이터 세그먼트

- FS 레지스터는 애플리케이션 디버깅에도 자주 등장하는데 SEH(Structured Exception Handling), TEB(Thread Environment Block), PEH(Process Environment Block)등의 주소를 계산할 때 사용


3) 프로그램 상태와 컨트롤 레지스터

- 플래그(Flag) 레지스터의 이름은 EFLAGS이며 32비트(4바이트) 크기

- 각 비트는 1 또는 0의 값을 가지는데, 이는 On/Off 혹은 True/False를 의미


#주요 flag

+ Zero Flag(ZF) : 연산 명령 후에 결과 값이 0이 되면 ZF가 1(True)로 세팅

+ Overflow Flas(OF) : 부호가 있는 수(signed integer)의 오버플로가 발생했을 때 1로 세팅, MSB(Most Significant Bit)가 변경되었을 때 1로 세팅

+ Carry Flag(CF) : 부호 없는 수(unsigned integer)의 오버플로가 발생했을 때 1로 세팅


4) Instruction Pointer

- EIP : Instruction pointer

- CPU가 처리할 명령어의 주소를 나타내는 레지스터

- 32비트(4바이트) 크기

- CPU는 EIP에 저장된 메모리 주소의 명령어(instruction)를 하나 처리하고 난 후 자동으로 그 명령어 길이만큼 EIP를 증가

- EIP는 그 값을 직접 변경할 수 없도록 되어 있어서 다른 명령어를 통하여 간접적으로 변경

- JMP, Jcc, CALL, RET을 사용하거나 인터럽트(interrupt), 예외(exception)를 발생 시켜야함

'SECURITY > 리버싱(역공학)' 카테고리의 다른 글

리버싱 3장  (0) 2015.08.20
리버싱 2장  (0) 2015.08.19
리버싱 1장  (0) 2015.08.19
Posted by OnewayK
,

1. 바이트 오더링

- 데이터를 저장하는 방식을 의미

- 빅 엔디언(Big Endian)과 리틀 엔디언(Little Endian)으로 나뉨


1-1. 리틀 엔디언 & 빅 엔디언

 BYTE b = 0x12;

 WORD w = 0x1234;

 DWORD dw = 0x12345678;

 char str[] = "abcde";


TYPE

Name 

SIZE 

빅 엔디언 

리틀 엔디언 

BYTE 

[12] 

[12] 

WORD 

[12][34] 

[34][12] 

DWORD 

dw 

[12][34][56][78] 

[78][56][34][12] 

char [] 

str 

[61][62][63][64][65][00]

[61][62][63][64][65][00] 


구분

빅 엔디언 

리틀 엔디언 

장점

 사람이 보기에 직관적

 산술 연산과 데이터의 타입이 확장/축소 될 때 더욱 효율적 

주로 사용되는 곳

 대형 UNIX 서버에 사용되는 RISC 계열의 CPU 

 네트워크 프로토콜

 Intel x86 CPU 

특징

 사람이 보는 방식과 동일하게 앞에서 부터 순차적으로 저장 

 - 데이터를 저장할 때 역순으로 저장

 - 바이트 자체는 정상적인 순서로 저장

 - 멀티바이트(multi-bytes)인 경우 각 바이트가 역순으로 저장

 - str 문자열은 Endian 형식에 상관 없이 동일 (char 배열이므로 각 바이트를 연속해서 저장)

'SECURITY > 리버싱(역공학)' 카테고리의 다른 글

리버싱 4장  (0) 2015.08.20
리버싱 2장  (0) 2015.08.19
리버싱 1장  (0) 2015.08.19
Posted by OnewayK
,