Ctrl + Shift + ESC

서론 해커들은 double free bug를 이용하면 free list에 어떤 청크를 중복으로 연결시킬 수 있음을 알아냈다. free list는 ptmalloc2의 동작에서 매우 중요한 기능을 하므로, 이 버그는 시스템에 심각한 오동작을 일으킬 수 있다. Tcache poisoning은 중복으로 연결된 청크를 재할당하면, 그 청크가 해제된 청크인 동시에, 할당된 청크라는 특징을 이용한다. 이러한 중첩 상태를 이용하면 공격자는 임의 주소에 청크를 할당할 수 있으며, 그 청크를 이용하여 임의 주소의 데이터를 읽거나 조작할 수 있게 된다. Tcache Poisoning Tcache Poisoning : tcache를 조작하여 임의 주소에 청크를 할당시키는 공격 기법 원리 중복으로 연결된 청크를 재할당하면, 그..

서론 free 함수로 청크를 해제하면, ptmalloc2는 이를 tcache나 bins에 추가하여 관리한다. 그리고 이후에 malloc으로 비슷한 크기의 동적 할당이 발생하면, 이 연결리스트들을 탐색하여 청크를 재할당한다. 이 메커니즘에서, 해커들은 free로 해제한 청크를 free로 다시 해제했을 때 발생하는 현상에 주목했다. tcache와 bins를 free list라고 통칭한다면, free list의 관점에서 free는 청크를 추가하는 함수, malloc은 청크를 꺼내는 함수이다. 그러므로, 임의의 청크에 대해 free를 두 번이상 적용할 수 있다는 것은 청크를 free list에 여러 번 추가할 수 있음을 의미한다. 청크가 free list에 중복해서 존재하면 청크가 duplicated됐다고 표현..

서론 운영체제의 Memory Allocator의 핵심 역할 중 하나는 한정된 메모리 자원을 각 프로세스에 효율적으로 배분하는 일이다. 모든 프로세스는 실행 중에 메모리를 동적으로 할당하고, 할당한 메모리의 쓰임이 다하면 이를 해제한다. 이 과정은 매우 빈번하게 일어나기 때문에 운영체제의 Memory Allocator는 이 동작이 빠르고, 메모리의 낭비 없이 이뤄지도록 특수한 알고리즘으로 구현된다. 몇몇 소프트웨어는 직접 구현한 Memory Allocator를 사용하기도 한다. Memory Allocator는 구현에 사용된 알고리즘에 따라 여러 종류가 있다. 리눅스는 ptmalloc2, 구글은 tcmalloc, 페이스북이나 파이어폭스는 jemalloc을 사용한다. ptmalloc2는 메모리가 해제되면, 해..

문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8..

문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문자열..

문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 입력 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어..

서론 메모리 레이아웃(Memory Layout) : 프로세스 가상 메모리(Virtual Memory)의 구성 프로그램을 실행하면 운영체제는 프로세스에게 사용 가능한 메모리 공간을 할당해준다. 컴퓨터 과학에서는 이 공간을 가상 메모리라고 부른다. 운영체제는 프로그램의 정보를 참조하여 프로그램에 저장된 데이터를 적절한 영역에 저장한다. 프로세스가 사용할 가상 메모리를 용도별로 구획하고, 프로세스가 사용하는 데이터를 적절한 구획에 저장한다. 유사한 데이터를 모아놓기 때문에 운영체제는 각 구획에 적절한 권한을 부여할 수 있으며, 개발자는 프로세스의 메모리를 더 직관적으로 이해할 수 있다. 섹션 섹션 : 유사한 용도로 사용되는 데이터가 모여있는 영역 윈도우의 PE 파일은 PE 헤더와 1개 이상의 섹션으로 구성되어..

컴퓨터 구조(Computer Architecture) 컴퓨터가 효율적으로 작동할 수 있도록 하드웨어 및 소프트웨어의 기능을 고안하고, 이들을 구성하는 방법 컴퓨터의 기능 구조에 대한 설계, 명령어 집합구조, 마이크로 아키텍처, 그리고 기타 하드웨어 및 컴퓨팅 방법에 대한 설계 등이 포함된다. ​ ‘컴퓨터의 기능 구조에 대한 설계’ : 컴퓨터가 연산을 효율적으로 하기 위해 어떤 기능들이 컴퓨터에 필요한지 고민하고, 설계하는 분야 대표적으로 폰 노이만 구조, 하버드 구조, 수정된 하버드 구조가 있다. 명령어 집합구조(Instruction Set Architecture) : CPU의 명령어에 대한 설계 CPU가 처리해야하는 명령어를 설계하는 분야이다. 대표적으로 ARM, MIPS, AVR, 인텔의 x86 및 ..