분류 전체보기
-
카쿠로알고리즘/algospot 2016. 12. 11. 16:49
스도쿠나 N-Queens 문제들을 마주할 때면 가슴이 답답하다. 냅색이나 LIS 처럼 차곡차곡 상황들을 쌓아 갈 수 없을 뿐더러 두더지 게임 처럼 하나의 조건을 해결하면 또 다른 문제가 튀어나오니 도대체 어떻게 풀어야 할 지 감을 잡을 수 없었다. 이러한 유형의 문제를 보면 정말 머리 좋은 친구들이 푸는건가보다 하고 그냥 넘어 갔던 것 같다. 알고리즘 해결 전략에서는 스도쿠, N-Queen 그리고 가쿠로 문제처럼 특정한 제약에 해당하는 답을 찾는 문제를 제약 충족 문제라고 한다. 조합 탐색 문제들 중에 하나인데 먼저 조합 탐색은 기존에 사용했던 알고리즘(DP, 탐욕법 등등)을 사용 할 수 없고 가지치기를 통해 검사 할 필요가 없는 경우들을 미리 쳐내는 방법이다. 제약 충족 문제는 조합 문제에서 한 발 더..
-
가상화기술의 대표적인 보안 문제개발/가상화 2016. 12. 10. 12:54
가상화 기술은 각 OS들 간의 isolation을 지원해 다른 VM들에 비해 보안이 우수하다고 하지만 가상화 기술 또한 보안 문제에서 자유롭지 못하다. 기존 OS가 갖고 있는 보안 문제를 회피 할 수 있으면서도 또 다른 양상의 보안 문제가 발생 할 수 있는데 이번 포스트에서는 가상화 기술의 대표적인 보안 문제점들을 정리 해보고자 한다. 1. Virtual Machine들 간의 공격. 가상화 기술의 가장 큰 장점은 VM들끼리 독립된 관계를 유지(isolation)되어 서로 영향을 주지 않는다는 것인데 만약 이 처리를 잘 해두지 않는다면 VM들간에 혹은 VM이랑 VMM 간에 공격이 발생 할 수 있다. 공격 양상은 VMM이 갖고 있는 데이터를 바꿔버리거나 혹은 읽어오는것 등등이 있다. 2. VM escape ..
-
모듈러 나눗셈 연산 처리하기알고리즘/자료구조 2016. 12. 10. 12:14
프로그래밍 문제에서 가끔 이런 연산을 요구하는 문제들이 있다. (N/K) % MOD N과 K의 값이 작으면 N과 K의 값을 먼저 계산 하고 나서 모듈러 연산을 취해주면 문제가 없다. 하지만 N과 K값이 64bit 이상으로 변수에 넣을 크기를 초과하는 경우 앞의 나눗셈 계산은 정상적인 값을 내놓지 않을 것이고 모듈러 연산은 정상이 아닌 값을 받아 처리해 결론적으로 잘못된 값을 낸다. 주로 N과 K를 팩토리얼로 받는 조합의 경우의 수를 구할 때 난감하다 -> nCr % MOD 인 경우 이런 경우를 해결 하기 위해 모듈러 연산의 나눗셈을 계산하는 특별한 방법이 존재한다. 모듈러 연산에서 나눗셈 N/K는 K로 나누는 대신에 K의 곱셈 역원(multiple inverse)를 곱하는 방식으로 이뤄진다. 곱셈 역원은..
-
완전순열(교란순열)알고리즘/자료구조 2016. 12. 4. 20:52
어떤 배열의 원소 Xi의 위치가 i라고 할 때 모든 원소들이 자기의 위치에 존재하지 않을 때 이를 완전 순열이라고 한다. X2 X1 X4 X3 점화식을 통해 원소의 개수에 따라 완전순열의 개수를 구할 수 있다. 공식은 다음과 같다 a(n) = (n-1) * (a(n-1) + a(n-2)) 증명을 하면, 1 부터 N까지 오름 차순으로 이뤄진 배열이 있다고 하자 여기서 배열내의 원소중 1의 위치를 X로 옮기려고 한다. 이럴 경우 두가지 경우가 발생한다. - X를 1의 위치로 옮기는 경우 -> N-2의 개수로 완전순열을 구하는 경우와 같다.- X를 1의 위치로 옮기지 않는 경우 -> N-1의 개수로 완전순열을 구하는 경우와 같다. 1이 선택 할 수 있는 X 의 개수는 N-1개 이므로 이를 점화식으로 나타내면 ..
-
4. Domain 장치 드라이버 개발개발/가상화 2016. 11. 27. 21:36
Domain의 장치 드라이버 개발 설명에 앞서 왜 장치 드라이버 개발이 필요한지 먼저 알아보자. 일반적으로 OS는 각각의 드라이버(네트워크, 블록 등등)를 통해 실제 하드웨어 장치를 제어하는 시스템을 가지고 있다. 하지만 가상화 환경에서는 하드웨어는 하나인 상태에서 여러개의 OS가 떠있다. Xen 플랫폼 내에 구동중인 여러 Domain들이 각자 하드웨어 Device들을 각자의 방식으로 제어하려 한다면 어떻게 될까? 물건은 하나인데 주인이 여러명이 생기는 엉뚱한 상황이 벌어질 것이다. 각 Domain들의 하드웨어 통제권을 정리하기 위해 Xen은 Domain0에게 하드웨어를 제어하는 독점적인 권한을 주고 나머지 DomainU 들은 Domain0의 통해서 하드웨어에 접근 할 수 있도록 규칙을 세웠다. 간단히 ..
-
3. Domain간 통신 방법개발/가상화 2016. 11. 6. 12:49
Guest OS들은 동작하면서 Block, Network Device처럼 다양한 장치에 접근할 일이 생긴다. Domain0는 Real Hardware driver를 갖고 있기 때문에 직접 접근 할 수 있지만, DomainU는 Control Domain의 역할을 하는 Domain0를 거쳐서 접근해야 한다. DomainU는 Domain 0에게 전송을 요청할 뿐만 아니라 Domain0에게 전송할 데이터들을 전달해야하는데 이때 Domain간에 통신 메커니즘이 필요하다. 가상머신에서 잠깐 물러나 일반 OS를 생각해보자. 두 개의 프로세스가 메시지를 전달 하는 방법은 여러 가지가 존재한다. 간단히 file에다가 값을 입력하는 방식도 있고 socket, pipe 공유메모리까지 사용 환경과 목적에 맞춰서 적용이 가능하..
-
2. Xen 기본 구조/Hypercall개발/가상화 2016. 11. 5. 20:52
Xen 기본 구조를 설명하기에 앞서 Hypervisor의 기본 형태중 Type 1에 대해서 간단히 설명을 한다. Type1은 가상머신을 관리하는 Hypervisor가 OS처럼 직접 하드웨어를 통제하고 VM(Guest OS)들은 Hypervisor 위에서 동작하는 형태이다. 스케줄러, MMU, Page table처럼 OS의 기본적인 기능들을 Hypervisor가 갖고 있고 위 기능들을 잘 이용해서 여러 개의 Guest OS들을 관리한다(작은 OS인 느낌이다). 기본적인 개념은 Type1 Hypervisor들이 모두 같으나 Guest OS를 관리하는 메커니즘은 Hypervisor마다 차이가 있다. Xen은 Guest OS들을 도메인이라 부르고 Domain이 생성된 순서에 따라 Domain + 생성순서로 이름..
-
1. Xen Project 소개개발/가상화 2016. 11. 5. 19:38
반가상화(Para-virtualization) 소프트웨어로 가장 대표적인 Xen에 대한 포스트를 앞으로 써보려고 한다. 이번 포스트에서는 Xen에 대한 소개와 역사 및 앞으로의 포스트 순서에 대해서 소개해보려 한다. 1. 소개 Xen은 Para-virtualization 형태로 여러 개의 Guest OS를 실행 할 수 있는 Hypervisor이다. 현재 Xen community에서 오픈소스의 형태로 개발중(www.xenproject.org)이며 작업에 따라서 여러가지 브랜치로 나눠져 있다. 크게 다음과 같이 세가지 Feature를 지원하는 것을 목표로 작업이 나눠져 있다. Feature Value Hypervisor 개발 여러개의 반가상화 Guest OS를 동시에 실행 할 수 있는 플랫폼을 개발한다. 확..