해나의 컴공생존기

1. Merge Algorithm sorting된 두개의 배열을 앞에서부터 각각 하나씩 비교하며 한 배열에 순서대로 합치는 알고리즘. 이 알고리즘의 단점은 하나의 배열을 새로 만들어야한다는 것이다 2. Recursive Merge Sort 위 코드를 간단히 설명해보자면 먼저 a[]와 똑같은 b[]를 만든다. h는 배열 전체 길이의 절반이다. b[0]부터 b[h-1] 까지 sort하는 함수를 한번 호출하고 b[h]부터 b[n-h-1]까지 sort하는 함수 하나를 호출한다. 끝까지 한 다음에는 마지막에 a로 sorting되며 합쳐진다. 증명 (proof by Invariant) invariant : 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야..

1. sorting의 조건 정확하게 sorting이 되기 위해서는 아래의 두가지 조건이 성립되어야한다. 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다. 조건2. 배열 b는 b[0]n−1 일 때 sort 함수가 성공한다고 가정하자. 항상 재귀 실행 전에 a[0]에 최소값이 들어간 후 실행된다. 따라서 재귀로 들어가기 전부터 ∀x((x>0)→(a[0]a[0]

1. Binary Search 이진탐색트리 코드이다. l은 왼쪽 끝 ,r은 오른쪽 끝 ,m은 중간이다. 기본 적인 아이디어는 sorting된 배열의 중간을 찾아 크기를 비교해가며 원하는 값을 찾는 것이다. 처음에는 0번째 배열을 l , 마지막 배열을 r로 두고 탐색을 시작한다. 탐색은 l과 r이 만나면 종료된다. m은 l과 r의 중간이고 (l+r)/2 로 두었다. 이게 성립하나를 위해 몇가지 예시를 보겠다. 1) n=2 l=0, r=1, m=0 으로 모두 탐색 가능하고 2) n-3 l=0, r=2, m=1 으로 모두 탐색 가능하다 a[m]과 x를을 비교해서 x가 작다면 왼쪽을 탐색하고 x가 크다면 오른쪽을 탐색하고 x와 같다면 종료된다. 왼쪽 탐색을 위해서는 r을 m의 바로 전 인덱스로 설정되고 오른쪽 ..

스택의 반환 주소를 덮는 공격은 스택 카나리, NX, ASLR이 도입되며 점점 어려워졌다. 공격 기법은 셸 코드의 실행에서 라이브러리 함수의 실행으로, 그리고 다수의 리턴 가젯을 연결해서 사용하는 Return Oriented Programming(ROP)로 발전하였다. NX의 도입으로 셸 코드를 사용할 수 없게 된 것은 공격자에게 큰 제약이 되었다. 그래서 지난 코스 Return to Library에서 살펴본 것과 같이 pop rdi; ret같은 코드 가젯과 라이브러리의 system 함수를 사용하는 공격 기법이 새롭게 등장하였다. 현실적으로, ASLR이 걸린 환경에서 system 함수를 사용하려면 프로세스에서 libc가 매핑된 주소를 찾고, 그 주소로부터 system 함수의 오프셋을 이용하여 함수의 주소..

1. 라이브러리 라이브러리는 컴퓨터 시스템에서, 프로그램들이 함수나, 변수를 공유해서 사용할 수 있게 한다. 대개의 프로그램은 서로 공통으로 사용하는 함수들이 많다. 예를 들어, printf, scanf, strlen, memcpy, malloc 등은 많은 C 프로그래머들이 코드를 작성하면서 사용하는 함수이다. C언어를 비롯하여 많은 컴파일 언어들은 자주 사용되는 함수들의 정의를 묶어서 하나의 라이브러리 파일로 만들고, 이를 여러 프로그램이 공유해서 사용할 수 있도록 지원하고 있다. 라이브러리를 사용하면 같은 함수를 반복적으로 정의해야 하는 수고를 덜 수 있어서 코드 개발의 효율이 높아진다는 장점이 있다. 또한, 각 언어에서 범용적으로 많이 사용되는 함수들은 표준 라이브러리가 제작되어 있어서 개발자들은 ..

어떤 공격이 새롭게 등장할지는 누구도 예상할 수 없기 때문에 시스템 개발자들은 여러 겹의 보호 기법을 적용하여 시스템이 공격당할 수 있는 표면(Attack Surface)자체를 줄여나가려고 했다. 공격자의 침입을 더 어렵게 하려면, 공격자가 메모리에서 임의 버퍼의 주소를 알기 어렵게 하고, 메모리 영역에서 불필요한 실행 권한을 제거하는 보호 기법을 추가로 도입해야 한다. 이와 관련하여 시스템 개발자들은 Address Space Layout Randomization(ASLR)과 No-eXecute(NX)을 개발하고, 시스템에 적용했다. 1. ASLR Address Space Layout Randomization(ASLR)은 바이너리가 실행될 때마다 스택, 힙, 공유 라이브러리 등을 임의의 주소에 할당하는 ..

웹 개발을 하는데에는 세가지 방식 정적컨텐츠, MVC와 템플릿엔진, API로 세가지 방식이 있다. 1. 정적 컨텐츠 정적 컨텐츠 - 서버에서 하는거 없이 파일을 웹브라우저에 내려주는 것 이를 위해서는 위에 그림처럼 static 파일에 html파일을 생성해주면 된다. 정적 컨텐츠 입니다. 실제로 아래와 같은 코드로 hello-static.html 파일을 생성하고 localhost:8080/hello-static.html 로 들어가보면 아래 사진과 같이 html 코드에 대한 결과가 그대로 나오게 된다. 원리를 살펴보자. 웹 브라우저에서 주소를 입력하면 내장 톰켓 서버가 스트링 컨테이너로 넘긴다. 스트링 컨테이너에서는 관련 컨트롤러가 있나 확인을 해보고 없으면 파일을 찾아서 웹 브라우저로 넘긴다. 2. MVC..

컨트롤러에서 리턴 값으로 문자를 반환하면 뷰 리졸버( viewResolver )가 리턴값과 같은 파일를 찾아서 처리한다. resources:templates/ +{ViewName}+ .html 현재 컨트롤러에서 hello를 리턴하고 있어, 이를 실행하면 hello.html이 실행이된다. @Controller public class HelloController { @GetMapping("hello") public String hello(Model model) { model.addAttribute("data", "hello!!"); return "hello"; } } 안녕하세요. 손님 위와 같이 두개의 코드를 작성한 뒤 locallhost:8080/hello로 들어가면 " 안녕하세요. Hello! " 라고 ..

1. 문제 문제를 보면 32비트라는 것과 Partial RELRO라는 것을 알 수 있고 카나리, NX는 존재하지만 PIE는 존재하지 않음을 알 수 있다. 2. 코드 #include #include #include #include #include char name[16]; char *command[10] = { "cat", "ls", "id", "ps", "file ./oob" }; void alarm_handler() { puts("TIME OUT"); exit(-1); } void initialize() { setvbuf(stdin, NULL, _IONBF, 0); setvbuf(stdout, NULL, _IONBF, 0); signal(SIGALRM, alarm_handler); alarm(30); ..

같은 자료형의 변수나 객체를 여러 개 관리해야 하면, 이들을 요소로 하는 배열을 선언하여 사용한다. 배열은 같은 자료형의 요소(Element)들로 이루어져 있는데, 각 요소의 위치를 인덱스(Index)라고 한다. Out of Bounds (OOB)는 배열의 임의 인덱스에 접근할 수 있는 취약점이다. 배열은 연속된 메모리 공간을 점유하며, 크기는 요소의 개수와 요소 자료형의 크기를 곱한 값이 된다. 배열 각 요소의 주소는 배열의 주소, 요소의 인덱스, 요소 자료형의 크기를 이용하여 계산된다. 1. Out of Bounds OOB는 요소를 참조할 때, 인덱스 값이 음수이거나 배열의 길이를 벗어날 때 발생한다. 개발자가 인덱스의 범위에 대한 검사를 명시적으로 프로그래밍하지 않으면, 프로세스는 앞서 배운 식을 ..