ITPE Momentum

I. B-Tree의 개념

가. B-Tree의 정의

   - 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 이진트리의 확장형 트리구조

나. B-Tree의 개념도 및 설명

구 분	항 목	설 명
개념도
구조	Root node	최소 2개의 자식노드 보유, 최소 한 개의 값 보유
	Internal node	최대 m개의 자식노드 보유(차수가 m일 경우)
	Leaf node	최하위 노드는 동일레벨로 구현
특징	자식노드 수	리프, 루트를 제외한 노드는 최소 m/2개의 자료 보유
	균등 탐색 속도	최악의 경우가 존재하지 않아 시간복잡도는 O(logN)으로 일정
	효율성	자식노드를 많이 보유하여 트리의 높이가 줄어들어 효율성 확보
	정렬상태	각 노드에 입력된 자료는 정렬된 상태로 존재
유형	B+ Tree	인덱스 세트(index set)와 순차세트(sequence set)로 구성된 트리
	B* Tree	리프, 루트를 제외한 노드가 최소한 2/3가 채워지도록 제한한 트리

- 중복된 자료는 입력 불가하며, 데이터 추가 및 삭제시 항상 Leaf노드에서 수행

II. B-Tree의 삽입 연산 설명 및 삽입과정 설명

 가. B-tree의 삽입 연산 설명

- 분할해야할 경우를 Overflow라고 하며, 분할결과 부모노드도 Overflow발생시 분할 반복수행

 나. 1, 2, 3, 4, 5, 6 순서대로 삽입되는 과정 설명

- Overflow 발생시 분할하여 부모노드에 배치

III. B-Tree의 삭제 연산 설명 및 삭제과정 설명

가. B-tree의 삭제 연산 설명

- M/2보다 자료가 적을 경우를 underflow라고 하며, 이럴경우 balance 유지를 위한 연산 수행 필요

나. 3, 4, 5 순서대로 삭제되는 과정 설명

- 해당 과정에서는 Swap시 Right Subtree의 최소값을 이용

[정의] 힙 데이터 영역에서 발생하는 버퍼 오버플로의 한 종류로, 동적 메모리 할당 연결(malloc 메타 데이터 같은)을 겹쳐쓰고 프로그램 함수 포인터를 겹쳐쓰기 위해 결과로 나온 포인터를 교환하는 기법.

[개념] 프로그램이 실행되면, 실행에 필요한 정보들이 메모리 영역에 올라가는데 크게는 코드 영역, 데이터 영역, 스택 영역, 힙 영역 으로 구분.
- 코드영역 : 프로그램의 코드가 올라가는 영역, 여기서코드란, 컴파일된 기계어코드
- 데이터영역: 전역변수와 정적변수등이 할당되는영역. 초기화된 데이터는 data 영역에 저장. 초기화 되지 않은 데이터는 bss 영역에 저장
- 스택영역 : 지역변수와 매개변수가 저장되는 영역
- 힙영역 : 빈공간, 필요에 의해 메모리를 할당 및 해제(컴파일러가 예측 할 수 없는, 프로그래머가 관리하는 영역)

[스택 대신 힙영역 사용이유]
- 동적할당, 컴파일시기에 크기를 알수없는 데이터, 컴파일할때는크기를 알지 못하다가, 프로그램이 실행되었을때 크기가 결정되는 경우에 사용

[원리] Heap 영역의 낮은 주소에 있는 버퍼가 넘쳐서 다른 버퍼를 침범하여 발생

[예시] 

1) 두 개의 heap 메모리인 input과 secret을 할당한 뒤, secret 파일을 읽어서 두 번째로 할당했던 secret 영역에 저장
2) 그 후 input 영역에 입력 값을 받고 출력시켜주는 간단한 코드
3) 취약점은 read 함수, input으로 할당한 메모리 크기는 40 바이트이지만
read 함수를 통해 최대 100 바이트까지 입력할 수 있어 Heap Overflow 가 발생
4) Heap Overflow를 이용해서 secret 에 할당된 메모리 영역의 직전까지 데이터를 채워주면,
문자열이 연결되어 printf 함수가 secret 메모리의 값까지 출력 됨.
5) 40 바이트 만큼 할당 한다면 input 에 할당된 메모리와 secret 에 할당된 메모리의 거리차이는 40 바이트
6) 40 바이트를 할당한다고 해서 딱 40 바이트만 할당되는 것은 아니고
메모리의 할당과 해제를 관리하기 위한 정보들이 함께 들어가기 때문에 실제 할당되는 사이즈는 조금 늘어나게 됨.
그래서 문자열의 길이를 조금 늘려주면 Heap Overflow 를 이용한 Leak 이 가능
7) 만약 뒤쪽에 함수 포인터가 존재한다면 그 부분을 조작하여 프로그램의 실행 흐름을 변조도 가능