'2021/03'에 해당되는 글 20건

DNS(Domain Name System)

우리들이 www.naver.com 이나 www.google.com 를 웹브라우저를 통해 접속할때 문자열로 된 주소를 타이핑하여서 웹 사이트에 접속을 하게 되죠? 근데 컴퓨터는 글자로 된 주소는 사실 모르고, 서버 컴퓨터의 IP를 이용해서 웹사이트에 접속하게 됩니다. naver에 접속을 하면 위의 www로 시작하는 주소를 입력하여 접속해도 되지만 이번에는 IP주소를 직접 쳐서 들어가보세요. IP를 알아볼 수 있는 명령어는 nslookup입니다. 저는 naver와 nate의 주소를 알아보았습니다.

223.130.195.200이라는 IP주소를 웹브라우저에 쳐서 들어가도 똑같이 네이버에 접속이 가능합니다. 네이트의 주소는 120.50.131.112네요.

whois 명령을 사용하면 도메인의 등록 정보를 알아볼 수 있습니다. 단, 업체에서 whois서버가 따로 존재해야합니다. 사용 방법은 whois 도메인명 혹인 whois IP주소 를 쳐서 도메인 등록 정보를 알 수 있습니다. google도메인에 대한 정보를 알아봤습니다. whois google을 타이핑해보세요.

아무튼 그렇다면 컴퓨터가 어떻게 이 주소를 알수 있을까요? 컴퓨터는 다음의 순서로 알아냅니다. 

1. 로컬 DNS Cache에서 IP 검색

2. hosts파일에서 IP 검색

3. DNS 서버에 질의

로컬에 저장된 캐시에 해당 IP주소가 있는지 확인하고 그래도 없으면 hosts파일에서 IP를 찾아옵니다. (참고로 DNS Cache를 삭제하려면 /etc/init.d/dns-clean restart 명령을 사용하여 삭제하면 됩니다.)
이 DNS 캐시에도 없으면 DNS서버에 물어보게 되죠. hosts파일은 무엇일까요? 리눅스에서 /etc/hosts파일을 아래와 같이 수정해봅시다. 네이버의 주소를 네이트의 IP주소를, 네이트의 주소를 네이트의 IP주소로 저장해 놓으면 www.naver.com  접속시 네이트가 접속이 됩니다. 물론 악의적인 사람은 이 파일을 악용하는 사람들도 있겠죠?

hosts파일에도 맞는 IP주소가 없으면 이제 서버에 여쭈어보게 됩니다. 이 서버 불쌍한 놈입니다.. 우리가 알려달라고 하면 여기 저기 물어보고 그제서야 알려줍니다.

사용자의 컴퓨터는 google의 주소를 서버에 물어봅니다. 우리가 www.google.com이라고 치면 사실 www.google.com. 으로 되어 접속이 됩니다. 여기 맨 끝에 끝나는 . 을 루트 도메인이라고 부릅니다. 자, 우리가 직접 물어본 서버는 이제 최상위의 Root DNS서버(.)에게 google IP에 대해 질의합니다. Root DNS 서버는 다음 도메인(.com)의 서버를 알려줍니다. 이제 우리 서버는 COM 서버에 질의합니다. 이 불친절한 com 서버도 역시 google.com의 서버에게 질의하라고 넘깁니다. 이제 google.com 서버에 질의합니다. google.com은 www.google.com의 IP주소를 를 알려줍니다. 이제 우리의 서버는 IP주소를 사용자에게 알려주지요. 이렇게 주소를 받은 사용자 컴퓨터는 다음에 또 물어보기 미안하기 때문에 DNS Cache에 일정시간 동안 저장합니다.

이때 사용자가 질의하는 방식을 재귀적 질의(Recursive Query)라고 하며, DNS서버가 다른 DNS서버에게 질의하는 방식을 반복적 질의(Iterative Query)라고 합니다. 우리가 Recursieve Query를 날리는 서버는 보통 인터넷 서비스 제공 업체의 서버 주소입니다. Root DNS 서버나 Com DNS 서버를 Authoritative DNS 서버라고 합니다.

DNS서버의 IP주소는 어디에 기록되어 있을까요? 리눅스에서 /etc/resolv.conf 가 DNS 서버의 주소를 갖고 있습니다. 

DNS는 보통 UDP 53번 포트를 사용합니다. TCP 53번도 쓰는 경우가 있는데, 이것은 DNS 헤더의 특수한 flag를 설정하면 TCP로 DNS 연결을 할 수 있고, 응답하는 데이터가 512 바이트를 넘어갈 경우 TCP를 통해 응답합니다.

실제 DNS 헤더는 어떤 정보를 담고 있을까요? 다음은 저의 DNS 패킷 중 하나입니다. 제가 사용하는 DNS서버의 주소는 210.220.163.82 인것을 알 수 있습니다. 여기에 Transaction ID와 Flag, 그리고 가장 밑에 질의(Query)를 볼 수 있습니다. 질의 형태(type)은 주로 A인데요. DNS의 본질인 IP주소를 받아오는 질의 타입이 A입니다.

그리고 그에 대한 응답입니다. 응답에서 Transaction ID를 보면 이전에 요청했던 Transaction ID와 같은 것을 볼 수 있습니다. 그리고 우리가 알고 싶은 IP주소는 Answer필드에 있는 것을 볼 수 있네요.

DNS의 패킷 그대로를 살펴보면 가장 마지막 4바이트가 우리가 원하는 주소라는 것을 알 수 있습니다. AC D9 A1 EE(172 217 161 238)이 주소이지요.

DNS의 질의는 아래 표에 정리되고 있습니다.

이상으로 DNS에 대한 개념과 실 데이터를 구경해보았습니다. 

위상 정렬(Topological Sort)

위상 정렬은 무엇일까요? 여러 작업들이 있을때 특정 작업을 수행하기 전 진행되어야 할 작업들이 있을텐데요. 이 작업들을 순서에 맞게 정렬해주는 것이 바로 위상정렬이라고 합니다. 이때 각 작업들은 직전 작업에 의존하게 되죠. 예를 들어 C라는 작업을 끝내기 위해서는 A작업과 B작업이 끝나야지만 C작업을 시작할 수 있는데, C는 A와 B가 끝날때까지 일을 실행하지 못하므로 A와 B에게 의존하고 있다고 봐야겠죠.

위상정렬은 우리 삶에도 영향이 있습니다. 예를 들어 요리할때나 청소할때, 여러분이 좋아하는 게임을 할때도 일의 순서등 말이죠.

위상정렬은 깊이 우선 탐색(Depth First Search, DFS)로 풀 수 있는 대표적인 정렬 방법입니다. 여기서 그래프는 의존성 그래프(Dependency Graph)의 모양을 띄고 있어야하는데, 그 말은 각 정점(작업)의 의존 관계를 간선으로 나타낸 방향 그래프라는 의미입니다. 만일 작업 v는 u가 끝나야만 수행할 수 있다면(v가 u에 의존한다면), 그래프는 u->v로 향하는 간선을 포함하게 됩니다. 의존성 그래프에서는 사이클이 존재할 수 없습니다.

자, 여기 작업을 나타내는 의존성 그래프가 있습니다. 

위상정렬 순서 단계별 알아보기

작업 순서)

B와 C는 A가 작업을 끝나야만 실행 가능

D는 B와 C가 작업을 끝나야만 실행 가능

E는 C가 끝나야만 실행 가능

F는 D와 E가 작업을 끝나야만 실행 가능

만약 여기서 F가 A로 향하는 간선이 있다면 어떻게 될까요? 그렇다는 의미는 A는 F 다음으로 수행가능 하다는 것인데, A는 이미 수행했기 때문에 모순입니다. 그렇기 때문에 의존성 그래프에는 사이클이 발생하지 않습니다. 이 그래프를 보기좋게 옆으로 돌려보도록 하겠습니다. 그러면 아래의 모양이 나오겠네요.

DFS를 이용해서 이 그래프의 위상정렬을 하면 결과는 이렇습니다. A C E B D F

여기서 힌트는 DFS를 종료한 역순이라는 것이 위상정렬된 결과라는 점입니다. 글로는 이해가 어려울 수 있으니, 이제 DFS를 통해서 어떻게 이 그래프가 위상 정렬이 되는지 그 과정을 보도록 합시다. 그전에 DFS를 방문할 노드의 규칙을 다음과 같이 정합시다. 연결된 정점 중 알파벳 순서가 가장 낮은 정점부터 탐색하는 것으로요.

 1. 들어오는 간선이 없는 A부터 DFS 탐색을 실시하면 아래의 그림과 같이 F에서 끝이 납니다. F는 이때 더 이상 나가는 간선이 없으니까 F는 종료가 됩니다. - 종료 순서 F

 2. F가 반환되면 D가 다음 종료됩니다. 여기서 D에서 더 이상 방문할 정점이 없으니까요. - 종료 순서 F D

3. B역시 마찬가지로 종료됩니다. - 종료 순서 F D B

4. 이후 A는 종료되지 않습니다. 왜냐면 C와 연결된 정점이 있으니까요. 그래서 결국 E까지 DFS가 탐색을 하여 도달하게 됩니다. E는 더이상 방문할 노드가 없습니다. 그러니 종료하게 됩니다. - 종료 순서 F D B E

5. C는 D와 연결된 간선이 있는데 이전에 D는 방문 됐었죠? 그러니 C도 더 이상 방문할 정점이 없으니 종료됩니다. - 종료 순서 F D B E C

6. 이제 A는 더 이상 방문할 노드가 없으니 종료됩니다. 종료 순서 F D B E C A

DFS가 종료된 순서는 F D B E C A 인데, 이 순서를 역으로 취하면 A C E B D F 입니다. 어때요? 우리가 원하는 결과를 얻을 수 있죠? 

그리고 아래의 코드는 위상정렬을 구현한 코드입니다. 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M;
vector<vector<int> > adj;


vector<bool> visited;
vector<int> order;
void dfs(int here) {
	visited[here] = true;
	
	for (int there = 0; there < adj.size(); there++) {
		if (adj[here][there] && !visited[there])
			dfs(there);
	}
	//위의 정점이 다 종료된 후에 이 곳의 정점(here)이 추가가 되어야함
	order.push_back(here);
}


void topologicalSort() {
	int n = adj.size();
	visited = vector<bool>(N, false);

	order.clear();

	//들어오는 간선이 없을 경우가 있을 수 있으므로 모두 DFS 탐색
	for (int i = 0;i<N;i++)
		if (!visited[i]) dfs(i);

	//종료된 순서를 거꾸로 만든다.
	reverse(order.begin(), order.end());
}

void printOrder() {
	for (int i = 0; i < order.size(); i++)
		printf("%c ", order[i] + 'A');
	printf("\n");
}
int main() {
	printf("정점의 갯수 : ");
	scanf("%d", &N);
	
	printf("간선의 갯수 : ");
	scanf("%d", &M);

	visited = vector<bool>(N, false);
	adj = vector<vector<int>>(N, vector<int>(N, 0));

	for (int i = 0; i < M; i++) {
		char from, to;
		printf("정점1 -> 정점2 : ");
		scanf(" %c %c", &from, &to);
		adj[from-'A'][to-'A'] = 1;
	}
	
	topologicalSort();
	printOrder();
}

topologicalSort안에 dfs를 전부 호출하는 이유는 아래의 그림과 같은 정점이 있을 수 있기 때문입니다. 여기서 G는 A와 같이 들어오는 간선(inboud-edge)이 없으므로 A부터 수행한 DFS에서는 G정점이 방문되지 않습니다. 그렇기 때문에 모든 정점을 방문하는 것입니다.

위의 코드를 실행한 결과를 보면 위상정렬이 잘 된 것임을 확인할 수 있습니다.

그리고 제가 제시했던 바로 위의 그래프의 위상정렬 결과는 아래와 같습니다. 

이상으로 위상정렬에 대해서 알아보았습니다. DFS의 응용이면서 결코 어렵지 않은 주제니까 원리와 코드는 알아두시면 좋겠습니다. 위의 코드는 구종만 저자님의 알고리즘 문제 해결 전략을 변형해서 만든 코드입니다.

ARP(Address Resolution Protocol)

ARP는 논리적인 주소(Logical Address)를 물리적 주소(Physical Address)로 변환하는 프로토콜을 의미합니다. 논리적인 주소라함은 IP주소, 물리적 주소는 MAC 주소(하드웨어 주소)라고 생각하면 훨씬 편합니다. IP주소는 어떻게 생겼죠?

예를 들어 저의 IP는 192.168.35.10이라고 해봅시다. 그리고 저희 MAC주소는 AA:BB:CC:DD:EE:FF라고 해볼게요. 저의 IP주소는 저 말고도 다른 사람도 쓸 수 있습니다. 왜냐면 네트워크는 특정 구역마다 나누어져 있으니까요. 쉽게 라우터를 기준으로 나누어져 있다고 생각하시면 됩니다. 그래서 논리적인 주소라 칭합니다. 저의 MAC주소는 이 세상에 단 하나밖에 없습니다. 하드웨어 고유한 주소이기 때문에 물리적 주소라고 합니다.

같은 네트워크에서는 IP주소로 통신하지 않고 물리적 주소를 가지고 통신합니다. 즉, MAC주소를 사용하여 통신한다는 것이죠. 스위치가 왜 2계층에 동작하는 것이 그 이유입니다. 2계층에서 MAC주소만 보아 정보 전송을 하면 되니까요.

어쨌든, IP주소를 MAC주소로 변환하는 프로토콜이 ARP라고 하는 거죠. ARP의 동작 방식을 보도록 합시다. 

1. 초기 Host A는 192.168.30.6에 MAC주소를 모르니까 네트워크 전체에 192.168.30.6에 대한 MAC주소를 물어보는 요청을 보냅니다.

2. 이 IP주소에 맞는 다른 호스트는 자신의 MAC주소를 담아 응답을 보냅니다. 요청 메시지에 자신의 MAC주소를 요청한 호스트 A의 IP주소가 있기 때문에 A에게 응답을 곧장 보낼 수 있습니다. 

3. MAC주소를 알아낸 호스트 A는 ARP의 정보를 담고 있는 저장소에 192.168.30.6의 MAC주소를 업데이트 합니다. 이 저장소를 ARP Cache라고 하며 일정 시간 후에 이 정보를 삭제합니다.

RARP(Reverse ARP)

반대로 MAC주소를 IP주소로 변환하는 프로토콜은 무엇일까요? ARP의 반대 과정을 거친다고 하여 RARP(Reverse ARP)라고 합니다. RARP 동작이 되려면 따로 RARP 서버가 존재하여야합니다. 자신의 IP를 모를때 이 프로토콜을 사용합니다. 동작방식은 아래의 순서와 같습니다.

1. 최초 호스트 A는 자신의 IP를 모르는 상태이기 때문에 IP를 요청하는 RARP Request를 Broadcasting으로 보냅니다. 이때 요청에는 자신의 MAC주소가 기재되어있습니다.

2. RARP 서버는 요청한 호스트 A의 IP 주소를 담은 RARP 응답 메시지를 만들어 Host A에게 전송합니다. 

ARP Cache

실제 ARP cache는 어떻게 생겼을까요?  cmd 창을 열고 arp -a 명령을 처보면 아래와 같이 ARP Cache 내용을 볼 수 있습니다. 저는 가장 호스트까지 있기 때문에 인터페이스가 2개가 잡히는데, 아니면 하나만 보일 수 있습니다. 여기에 IP주소와 MAC주소가 보이시죠? 그리고 맨 오른쪽에 정적, 동적이 보이는데, 정적은 등록된 ARP정보가 수동으로 시스템 종료가 되기 전까지 영구적으로 설정이 된것이고 동적은 컴퓨터가 알아서 설정한 것이고 시간이 지나면 없어지게 됩니다.

ARP Cache내용을 지우려면 arp -d를 사용하시면 됩니다. arp -d를 쳤을때 관리자 권한이 필요하다고 나온다면 cmd를 오른쪽 마우스를 클릭하면 관리자 권한으로 실행이라는 항목이 보이실 겁니다. 이것을 통해 cmd를 실행해보세요.

지워도 되냐구요? 단순히 컴퓨터를 쓰는 일반 사용자라면 지우셔도 됩니다. 다시 업데이트 될거니까요. 그 후 arp -a를 보면 반드시 필요한 몇개의 MAC주소를 제외하면 지워진것을 볼 수 있습니다. 

그리고 정적으로 MAC주소를 등록하려면 arp -s를 이용하면 됩니다. 아래와 같이 "arp -s IP주소 MAC주소" 를 입력하면 됩니다.

ARP 스푸핑(ARP Spoofing)

혹은 ARP Cache Poisoning이라고 합니다. 공격자는 두 호스트의 통신을 감시하기 위해서 두 호스트의 ARP Cache를 변경하는 것을 공격방법입니다. 공격자는 아래의 그림처럼 지속적으로 ARP 응답을 보냅니다. 물론 잘못된 정보로 말이죠. 

만약 동적으로 ARP 정보가 등록되어있다면 시간이 지나면 삭제되는 것을 이용합니다. 그때 응답을 받으면 피해 컴퓨터는 잘못된 정보로 ARP Cache를 업데이트하게 됩니다. 여기서 AA:AA:AA:AA:AA:AA의 MAC주소를 갖는 호스트를 Alice, BB:BB:BB:BB:BB:BB의 MAC주소를 갖는 호스트를 Bob라고 부르도록 하겠습니다. 공격자 자신은 정상적인 ARP Cache를 가지고 있습니다.

이때 Alice가 Bob에게 데이터를 전송할때 C에게 그 정보를 전송합니다. 맨 처음에 같은 네트워크는 MAC주소만 보고 그 데이터를 전달한다고 했죠? 그러니 공격자의 MAC주소인 CC:CC:CC:CC:CC:CC으로 전달하게 되죠. 공격자는 이제 Alice의 데이터를 볼 수 있죠. 이것을 다시 정상적인 Bob에게 전달합니다. 이렇게 Alice와 Bob를 속이고 그 당사자인척 하는 공격방법이 스푸핑이라고 합니다.

반대로 Bob이 Alice에게 데이터를 보낼때도 공격자를 거쳐가게 되죠. Bob의 ARP Cache도 오염되어 공격자의 MAC주소로 업데이트되었기 떄문이죠.

공격자는 2계층의 MAC주소를 그 사람인척 위장해야하므로 같은 네트워크에 위치해야합니다. 

대응

- 위에서 본 정적 arp cache를 구성하면 시스템 종료시까지 막을 수 있습니다. 또한 시스템 가동시마다 arp를 정적으로 구성해주어야합니다. 물론 매번 arp를 정적으로 구성하는 것은 까다로울 수 있으니 자동화된 프로그램을 사용하는 것이 좋겠죠.

- arp cache의 변경을 감지하는 프로그램을 사용할 수도 있습니다.

여기까지 ARP에 대한 개념과 설명, 그리고 ARP Cache와 Reply를 통해서 스푸핑할 수 있는 원리에 대해서 알아보았습니다.

디피-헬만 (Diffie-Hellman) 

디피-헬만(이하 DH)은 대칭키를 키 분배 센터(KDC, Key Distribution Center)없이 대칭키를 생성할 수 있는 암호 프로토콜을 의미합니다. KDC가 뭐냐하면 키를 분배하고 관리해주는 센터를 의미하는데요. 수 많은 호스트가 있는데 암호화 통신을 하려면 그 호스트들의 대칭키를 모두 가지고 있어야하니, KDC에게 키를 얻습니다. KDC는 물론 신뢰성이 큰 센터여야겠지요.  DH는 KDC없이도 대칭키를 서로 합의할 수 있도록 만들어줍니다. 아래의 그 과정을 봅시다.

우선 Alice와 Bob(암호학에서는 Alice와 Bob 이름에 친숙해지셔야합니다.)이 먼저 거쳐야 할 과정이 있습니다.

1) Alice와 Bob은 p와 g를 정하는데요. 매우 큰 300자리가 넘는 매우 큰 소수 p를 정합니다. 그리고 \(1 <= g <= p-1\)인 g를 정합니다. p와 g는 공개되어도 상관없습니다. 누구나 알아도 됩니다.

2) 그 후 Alice는 \(0 <= x < p-1\)인 x를 선택합니다. 이 사이의 수면 아무거나 상관없습니다. 그 후 R1=\(g^{x}\) mod p를 계산합니다. 여기서 mod는 모듈러 연산으로 \(g^{x}\)를 p로 나눈 나머지를 의미합니다. Alice가 정한 x는 Alice 본인만 알아야하는 값입니다. 절대 공개해서는 안되는 값입니다.

3) Bob도 역시 Alice와 마찬가지로 \(0 <= y < p-1\)인 y를 선택합니다. 그 후 R2=\(g^{y}\) mod p를 전달합니다.  y는 Bob만 알고 있어야합니다.

4) 이제 서로 R1과 R2를 당사자들에게 보냅니다. 

5) Alice는 R2\(^{x}\) mod p를 계산합니다. \((g^{y}\) mod p)\(^{x}\) mod p = \((g^{y})^{x}\) mod p = \(g^{yx}\) mod p로 이 값이 결국 대칭키 K가 됩니다.  

6) Bob도 역시 R1\(^{y}\) mod p 를 계산합니다. \((g^{x}\) mod p)\(^{y}\) mod p = \((g^{x})^{y}\) mod p = \(g^{xy}\) mod p로 이 값이 결국 대칭키 K가 됩니다.

결국 둘은 K=(g^{xy}\) mod p 인 대칭키를 갖고 있게 됩니다. 아래의 그림은 그 과정을 나타냅니다.(오타가 있네요. 아래 그림에 Bob이 생성한것은 R1이 아니라 R2입니다.) 

예제

이게껏 설명만 했는데 실제로 계산하는 과정을 보도록 하겠습니다.

Alice와 Bob은 p와 g는 11과 7로 설정했습니다. Alice는 x를 5로 선택하고 Bob은 y를 3으로 선택했다고 치겠습니다. R1=\(g^{5}\) mod p를 보내고, Bob은 R2=\(g^{3}\) mod p으로 하여 서로에게 보냅니다. 이제 Alice는 \((7^{3}\) mod 11)\(^{5}\) mod 11 = \((7^{3})^{5}\) mod 11 = \(7^{15}\) mod 11 의 값 K=10입니다. 이제 Bob도 역시 그렇게 계산을 하는데요. \((7^{5}\) mod 11)\(^{3}\) mod p = \((7^{5})^{3}\) mod 11 = \(7^{15}\) mod 11의 값은 역시 동일한 값으로 10임을 확인할 수 있습니다.

중간자 공격(Man-In-The-Middle-Attack)

만약 Alice와 Bob 사이에 공격자가 있다면 어떻게 될까요? 어찌 저찌 되어서 Alice가 Bob과 통신해야하는 것을 Eve로 착각했다고 합니다. Bob 역시 Alice와 통신을 해야하는데 Eve가 Alice로 알고 있다고 해봅시다. 그러면 Alice는 R1을 계산해서 Eve에게 주고, Bob도 R2를 계산해서 Eve에게 줍니다. Eve는 자신도 z를 정해서 R3를 양쪽 모두에게 전달해줍니다. 

이렇게 되면 Alice는 R3를 가지고 키 K1을 구할 수 있고 Eve 역시 위의 방법대로 K1을 구할 수 있습니다. Bob도 역시 R3를 가지고 K2를 구할 수 있게 되고 Eve 역시 K2를 구할 수 있습니다. 이제 공격자는 Alice와도 통신할 수 있고 Bob과도 통신할 수 있는 상황이 되었습니다. 공격자가 중간에 위치해서 민감한 정보를 모두 볼 수 있군요. 이런 공격 방식이 중간자 공격이라고 합니다.

이산대수 공격

만약 Eve가 R1, R2를 가로챌 수 있다고 해봅시다. R1에서 x를 구하고, R2에서 y를 구할 수 있으면 K를 구하는 것을 쉽습니다. 그런 이산대수 공격에 대해서 안전하려면 p를 아주 매우 큰 소수로 정해놓아야합니다. 그래야 x,y를 구하기가 어렵거든요. p-1이 적어도 하나의 큰 소인수(60자리의 10진수 이상)을 가져야합니다. Alice와 Bob은 x,y를 사용 즉시 폐기하는 것이 좋습니다.

이상으로 디피-헬만 암호 프로토콜에 대해서 알아보았는데요. 모듈러 연산을 모르신다면 조금 어려울 수가 있는데요. 모듈러 연산에 대해서는 따로 시간을 내어 공부하시는 것이 좋을 듯 합니다. 쉽게 계산하는 규칙들도 존재하거든요. 디피-헬만은 ECC 암호화 알고리즘과 결합하여 사용하기도 합니다. ECDH라고도 하지요. 

DH에서 키를 구하는 문제가 이전 2016년 정보보안 기사 시험에 나온적이 있습니다.

더 많은 정보를 담은 리눅스 교재를 배포했습니다. 아래의 페이지에서 리눅스 교재를 받아가세요.

https://reakwon.tistory.com/233

/etc/passwd(사용자 정보)

보안이나 리눅스를 배우신다면 /etc/passwd에 대한 이해는 필수입니다. 정보보안기사 시험에도 당골손님이기도 하죠.

/etc/passwd에는 시스템에 등록된 사용자의 정보들이 담겨있는 파일입니다. 이 파일을 이용해서 사용자의 계정과 인증을 관리하게 됩니다. 이 파일의 이름이 passwd인데, 여기에 패스워드 정보가 있는건 아니구요. 과거에 사용자의 패스워드를 이곳에 저장을 하였는데, /etc/shadow에 따로 암호화된 패스워드를 저장합니다. 과거에 패스워드를 저장했었던 것이 아직 파일 이름으로 남아 파일명이 passwd입니다.

/etc/passwd를 열어보면 아래와 같이 사용자의 정보들이 있습니다. 

각 필드들이 의미하는 바가 있는데, 필드 하나하나 무엇을 의미하는지 확인해봅시다. 각 필드는 콜론(:)으로 구분되어 집니다. 

/etc/shadow

/etc/shadow에는 암호화된 패스워드와 패스워드 설정 정책이 기재되어 있습니다. 여기서 관리자 계정과 관리자 그룹만이 이 파일을 읽을 수 있습니다. 이 파일이 만약 평문의 비밀번호의 정보를 가지고 있다면 모든 사용자의 비밀번호가 유출될 수 있습니다.

/etc/shadow 파일의 root의 정보를 보게되면 아래와 같이 나오게 되는데요. 각 필드에 대해 설명해보도록 하겠습니다.

필드	설명
사용자 계정명	맨 첫 필드는 사용자의 계정명을 뜻합니다.
암호화된 패스워드	두번째 필드는 암호화된 패스워드를 뜻합니다. 이 패스워드는 또 $로 필드가 구분되어 있는데요. 아래처럼 구분이 됩니다. $algorithm_id$salt$encrypted_password algorithm_id : 암호학적 해시의 id를 의미하는데요. id는 아래와 같습니다. 1 : MD5(가장 취약한 일방향 해쉬로 요즘에는 쓰지 않습니다. 2 : BlowFish 5 : SHA-256 6 : SHA-512 제 시스템은 SHA-512를 사용하는 것을 알 수 있습니다. salt : 각 해쉬에 첨가할 랜덤값입니다. 이 랜덤값에 따라서 해시의 값이 바뀌게 됩니다. encrypted_password : 마지막은 알고리즘과 salt로 패스워드를 암호화한 값입니다. 이 뿐만 아니라 패스워드 필드에 *, !!, 또는 빈값이 설정될 수 있습니다. 이것이 의미하는 바를 알아보겠습니다. * : 패스워드가 잠긴 상태입니다. 로그인은 불가합니다. 별도의 인증방식을 사용하여 로그인을 할 수는 있습니다. ! : 패스워드가 잠긴 상태이고 로그인을 할 수 없습니다. 또는 사용자를 생성하고 패스워드를 설정하지 않은 상태이기도 합니다. empty : 패스워드가 설정되지 않았지만 로그인이 가능합니다.
마지막 변경	마지막으로 패스워드를 변경한 날을 1970년 1월 1일 기준으로 일수도 표시합니다. 여기서 마지막으로 패스워드를 변경한 날은 1970년 1월 1일 이후 18693일이 지났음을 알 수 있습니다.
패스워드 최소 사용기간	패스워드의 최소 사용기간 설정으로 패스워드를 변경한 이후 최소 이 정도의 기간은 써야한다는 것을 의미합니다. 그래서 마지막 변경이 일어난 후 이 일수가 지나기 전에 암호를 변경할 수 없습니다.
패스워드 최대 사용기간	패스워드의 최대 사용기간 설정으로 마지막 패스워드 변경 이후 만료일수를 의미합니다. 패스워드를 변경하지 않으면 공격자가 패스워드를 깰 수도 있으므로 90일을 권장합니다.
경고	패스워드 만료 이전에 경고할 경고 일수를 의미합니다.
비활성화	패스워드가 만료된 이후에 계정이 잠기기 전까지 비활성 일수(date)입니다. 해당 비활성 기간동안에 패스워드를 변경해야 계정이 잠기지 않습니다.
만료일	계정 만료일 필드입니다. 1970년 1월 1일 기준으로 일수로 표시합니다.

이상으로 /etc/shadow와 /etc/passwd에 대해서 알아보았는데, 이 파일은 매우 중요하므로 보안을 배우는 사람은 잘 알아두어야합니다. 

더 많은 정보를 담은 리눅스 교재를 배포했습니다. 아래의 페이지에서 리눅스 교재를 받아가세요.

https://reakwon.tistory.com/233

쉘스크립트 기본

쉘 스크립트는 쉘에게 무슨 명령들을 실행할지 알려주는 스크립트 파일입니다. 여기서는 가장 널리쓰이는 bash 쉘을 사용하는 스크립트를 설명하도록 하겠습니다.

#!/bin/bash

스크립트 최상단에는 항상 이 구문이 적혀있어야합니다. 간단하게 hello,world라는 문자열을 출력하는 스크립트를 만들어봅시다. 파일명은 exam.sh로 정해놓고요.

#!/bin/bash

echo "hello, world"
printf "hello, world"

./exam.sh로 스크립트를 실행하면 되는데 혹시 실행이 되지 않는다면 실행 권한이 없어서 그런것이니까 chmod 777 exam.sh로 권한을 바꾸어주면 됩니다. 그 후 결과를 보면 echo는 개행이 되지만 printf는 개행이 되지 않는 다는 것을 알 수 있습니다. 또 C언어 처럼 문자열을 전달할 수도 있는데 포맷 문자 %s를 이용하면 됩니다.

printf "%s, %s" hello, world

1) 변수(Variable)

쉘스크립트에서도 변수를 사용할 수 있는데요. 변수명=값 으로 변수를 선언하고, 사용할때는 앞에 $를 붙여줍니다. 중괄호를 이용하는 방법도 있습니다. ${변수}식으로 중괄호로 묶어서 사용합니다.

#!/bin/bash

h="hello"
w="world"
echo "${h}, ${w}"

여기서 export를 사용하여 다른 쉘 스크립트에서 사용할 수 있게 합니다. exam.sh는 변수 선언하고 export를, exam2.sh는 그 변수를 출력하는 쉘 스크립트입니다.

#!/bin/bash
#exam.sh
export MY_VAR="reakwon"

./exam2.sh

#!/bin/bash
#exam2.sh
echo ${MY_VAR}

매개변수

프로그램에서도 실행할때 인자를 주듯 쉘 스크립트도 역시 그렇게 할 수 있습니다. 실행한 스크립트 이름은 ${0}, 그 이후는 전달받은 인자 값들입니다(${1}, ${2}, ...). 아래의 예제코드를 보면서 이해하실 수 있습니다.

#!/bin/bash


echo "script name:${0}"
echo "매개변수 갯수 :${#}"
echo "전체 매개변수  값 : ${*}"
echo "전체 매개변수 값2 : ${@}"
echo "매개변수 1 : ${1}"
echo "매개변수 2 : ${2}"

예약변수

쉘 스크립트에서 사용자가 정해서 만들 수 없는 이미 정의된 변수가 존재합니다. 그것을 예약 변수라고 하는데요. 몇가지 예약 변수를 보도록 합시다.

2) 배열(Array)

쉘 스크립트에서 배열은 1차원 배열만 지원하며 중괄호를 사용해야합니다. 배열 원소는 소괄호안에 공백으로 구분하여 줍니다. 배열 안 원소는 문자열이든 정수든 상관 없이 쓸 수 있는 특징이 있습니다.

#!/bin/bash

arr=("hello" "world" 1 2 3 4 5)

echo "배열 전체 : ${arr[@]}"
echo "배열 원소의 갯수 : ${#arr[@]}"
echo "배열 첫번째 : ${arr}, 혹은 ${arr[0]}"
echo "5번 index를 갖는 배열의 원소 : ${arr[5]}"

arr[5]="five"

echo "5번 index를 갖는 배열의 원소 : ${arr[5]}"

# 5번 원소 해제
unset arr[5]
echo "5번 원소 삭제 후"
echo "5번 index를 갖는 배열의 원소 : ${arr[5]}"
echo "6번 index를 갖는 배열의 원소 : ${arr[6]}"

3) 함수(Function)

다른 프로그래밍 언어와 같이 쉘 스크립트에서도 함수를 사용할 수 있습니다. 함수의 정의 형식은 아래와 같습니다. 함수명 앞 function은 써주지 않아도 무관합니다. 주의 할 점은 함수가 호출되기 전에 함수가 정의되어 있어야하며 호출할때는 괄호를 써주지 않고 호출해야한다는 점입니다.

function 함수명(){
 ... 내용 ...
}

#!/bin/bash

function func(){
        echo "func()"
}

#함수 호출
func

4) 비교문

쉘스크립트에서 비교문은 약간 특이합니다. 아래와 같은 형식으로 비교문을 사용할 수 있습니다. 

if [ 값1 조건 값2 ]; then
	... 작업 내용 ...
fi

조건은 -eq, -gt, -lt 등이 있는데, 자세한 것은 아래의 코드에서 보도록 합시다.

#!/bin/bash

function func(){
        a=10
        b=5

        if [ ${a} -eq ${b} ]; then
                echo "a와 b는 같다."
        fi

        if [ ${a} -ne ${b} ]; then
                echo "a와 b는 같지 않다."
        fi

        if [ ${a} -gt ${b} ]; then
                echo "a가 b보다 크다."
        fi

        if [ ${a} -ge ${b} ]; then
                echo "a가 b보다 크거나 같다."
        fi

        if [ ${a} -lt ${b} ]; then
                echo "a가 b보다 작다."
        fi

        if [ ${a} -le ${b} ]; then
                echo "a가 b보다 작거나 같다."
        fi

}

#함수 호출
func

쉘스크립트는 명령어를 다루는 스크립트이기 때문에 파일이 존재하는지, 디렉토리가 존재하는지 등 파일과 관련된 조건 여부도 조건문을 통해 알 수 있습니다. 아래는 그것을 정리한 표입니다. 그리고 앞에 느낌표(!)를 써주고 조건을 기재하면 그 조건이 false일때 참이 성립합니다.

파일 관련 조건

만약 AND조건과 OR조건을 섞어서 쓴다면 어떻게 할까요? AND는 -a, OR은 -o를 이용해서 조건을 추가할 수 있습니다.

function func(){
        a=aa
        b=bb
        if [ -f ${a} -a -d ${b} ]; then
                echo "a는 파일이고 b는 디렉토리 "
        fi
}

#함수 호출
func

또한 여러 조건을 걸려면, 즉, C언어에서 else if역할을 하는 것은 elif라는 것을 사용하여 else if와 똑같은 역할을 할 수 있게 해줍니다. elif[ 조건 ]; then 이런식으로 쓰시면 됩니다.

만약 반복문에서 사용하여 조건이 참일때 반복문을 멈추고 싶을때 break라는 키워드를 사용하여 반복문을 멈출 수 있습니다.

C에서 switch case와 동일한 구문을 하는 문법도 존재합니다. 아래와 같이 case문을 사용하면 됩니다. 각 case의 끝을 보면 세미콜론 2개로 종료하는 것을 볼 수 있습니다.

#!/bin/bash

case ${1} in
        "linux") echo "리눅스" ;;
        "unix") echo "유닉스" ;;
        "windows") echo "윈도우즈" ;;
        "MacOS") echo "맥OS" ;;
        *) echo "머야" ;;
esac

5) 반복문

반복문 중 for문에 대한 설명은 예제와 같이 보는 것으로 하겠습니다. 

#!/bin/bash

function func(){
        echo "사용예1"
        for i in 1 2 3 4 5
        do
                echo "${i}"
        done

        echo "사용예2"
        list="1 2 3 4 5"
        for i in ${list}
        do
                echo "${i}"
        done

        echo "사용예3"
        for i in {1..5}
        do
                echo "${i}"
        done

        echo "사용예4: 크기를 2만큼 증가시키면서 출력"
        for i in {1..5..2}
        do
                echo "${i}"
        done

        echo "사용예5: 배열을 이용"
        arr=(1 2 3 4 5)
        for i in "${arr[@]}"
        do
                echo "${i}"
        done


        echo "사용예6: C와 유사한 형식의 for문"
        for ((i=0; i<5; i++)); do
                echo "${i}"
        done
}

#함수 호출
func

6) 명령어의 종료 코드(exit)

만약 명령어가 실패할 경우 동작을 다르게 할것이라면 어떻게 할까요? 명령어의 종료 코드를 얻어오면 됩니다. 명령어의 종료 코드는 $?에 가장 최근 실행한 명령어의 종료 코드가 있습니다. 정상적인 종료는 0이 반환되는데, 만약 0이 아닌 값으로 반환되면 오류라고 판단하시면 됩니다. 여기에 간단한 오류를 내는 c파일(main.c)을 작성하고 gcc로 컴파일(gcc main.c)합니다. 이 c파일은 실행시 전달인자가 2개 보다 작으면 exit으로 코드 16을 반환합니다.

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char* argv[]){
        if(argc<2){
                fprintf(stderr,"인자는 2개 이상이어야 합니다.\n");
                exit(16);
        }
}

그리고 쉘스크립트를 아래와 같이 수정해서 오류의 코드가 얼마인지 확인해보면 우리가 exit에 넘겨준 16이 찍히는 것을 확인할 수 있습니다.

#!/bin/bash

function func(){
        ./a.out
        echo "오류 코드 ($?)"
}

#함수 호출
func

./a.out에 인자를 하나 넣어서 다시 실행시켜보세요. 0이 종료코드로 반환 될 것입니다. 이렇게 이전에 명령어의 결과를 봐야하는 경우 $?으로 판단하여 분기시킬 수 있습니다.

이렇게 종료 반환 코드는 명령어 뿐만 아니라 쉘 스크립트 자체도 반환할 수 있습니다. 즉, 쉘 스크립트의 수행이 실패했는지 알려주기 위해서는 exit 명령어를 사용하면 됩니다. 아래의 예가 그 사용법을 보여줍니다. 우선 exam2.sh라는 파일을 만들어봅시다. 이 쉘 스크립트 파일은 exam.sh에서 실행할 예정입니다. 별거없이 16의 종료코드를 반환하며 끝이 납니다. 

#!/bin/bash

exit 16

이 쉘 파일을 exam.sh에서 실행시켜볼까요?

#!/bin/bash

function func(){
        ./exam2.sh
        echo "오류 코드 ($?)"
}

#함수 호출
func

확인해보면 우리가 기재했던 16이 출력되는 것을 확인할 수 있습니다.

리눅스에 대한 더 많은 정보와 예제를 담은 리눅스 교재를 배포했습니다. 아래의 페이지에서 리눅스 교재를 받아가세요.

https://reakwon.tistory.com/233

리눅스 커널(Kernel)

리눅스 커널은 하드웨어와 가장 가까이 있는 일종의 프로그램입니다. 가장 핵심적인 프로그램으로 사용자는 커널을 통해서 하드웨어를 제어합니다. 함부로 하드웨어를 직접 만졌다가는 돌아올 수 없는 강을 건너게 될 수도 있습니다. H/W에는 CPU, 메모리(RAM), 하드디스크(HDD), 기타 입출력 장치 등 많은 것들이 있는데 실제 직접 조작할 수도 없고 해서도 안됩니다. 그래서 커널이 존재하게 되는것이지요. 이 처럼 커널은 시스템의 자원을 관리하는 운영체제 그 자체로 보시면 됩니다. 

윈도우즈도 역시 커널을 가지고 있는데, 사용자가 커널의 코드를 직접 들여다 볼 수 없고 거기에 맞는 모듈(Module)을 만들어거 끼워넣을 수 없죠. 윈도우즈는 커널 내부를 공개하고 있지 않기 때문인데요. 그래서 윈도우즈 커널을 수정하려면 오직 MS사 밖에 할 수 없습니다. 리눅스는 윈도우즈와는 다르게 커널 내부 소스를 전부 공개합니다. 그래서 커널을 잘 아는 사람은 거기에 맞게 모듈이라는 커널의 부분을 끼워넣어서 변경할 수 있습니다. 

이전에 리눅스는 커널에 조금이라도 변경이 생기면 수정 후 전체 커널 컴파일을 해야했는데, 이 모듈이라는 개념이 도입된 후 필요한 커널의 부분만 수정하고 다시 끼울 수 있으면서 커널 컴파일하는 모든 과정을 수행하지 않아 시간이 획기적으로 줄어 들 수 있습니다. 현재 적재된 커널 모듈을 보려면 lsmod를 이용해서 볼 수 있고 모듈을 설치할때는 insmod를 이용하면 되는데, 물론 아무나는 안됩니다. 커널 프로그래밍을 이용하기 때문에 아무나 건드리면 시스템이 멈출 수 있습니다.

쉘(shell)

쉘은 사용자의 응용프로그램과 커널 사이에 위치해있으며 응용프로그램의 명령어와 커널이 대화를 하도록 만들어줍니다. 그래서 명령어 해석기라는 부릅니다.

자, 우리가 명령어를 입력하게 되면 컴퓨터에서는 쉘(shell)이 이 명령어를 받아 해석하여 커널(kernel)에게 보내면 커널은 우리가 내려주었던 동작을 하게 됩니다. 그래서 그에 대한 결과를 사용자에게 전달하려고 다시 쉘에 응답을 보내고 쉘을 거쳐 사용자에게 도달합니다. 여기서 쉘도 프로그램입니다.

쉘 종류는 여러가지고 존재합니다. 

Bourne Shell (/bin/sh)

본쉘이라고 합니다. 유닉스 최초의 쉘이기도 하지요. 최조의 쉘이라서 미흡한 기능이 많은데요. 여기서 일반 유저의 쉘 프롬프트는 $, root사용자의 프롬프트는 #으로 나타냅니다.

Bash, Bourne Again Shell (/bin/bash)

현재 리눅스에서 표준으로 채택된 쉘입니다. 여러분에게 가장 친숙한 쉘이라고 생각하시면 됩니다. 여러분이 명령을 칠때 명령어 다 쓰기 싫어서 tab쓰시죠? 그게 원래는 리눅스 자체의 기능이 아니고 bash의 기능입니다. 그 밖에도 아래와 같은 특징이 있습니다. Mac 운영체제에서도 bash가 쓰입니다.

C shell (/bin/csh)

C언어를 기반으로 만들어진 쉘입니다. 쉘 스크립트가 C언어로 작성하는 것처럼 작성할 수 있습니다.

쉘을 이해해보자

이 외에도 쉘의 종류는 여러가지가 있는데요. 실제 시스템에서 지원하는 쉘을 보기 위해서 /etc/shells를 열어보시면 됩니다. 아래는 저의 시스템에 있는 shell들입니다.

그리고 사용자가 어떤 쉘을 쓰고 있는지 보고 싶으시다면 SHELL 환경변수를 확인하면 됩니다. echo $SHELL 으로 확인하세요. 저는 bash쉘을 사용하고 있군요.

여기서 bash쉘에서 지원하는 기능이 sh(본쉘)에서도 먹힐까요? 사용하는 bash쉘을 본쉘로 바꿔보도록 하겠습니다. 단순히 sh명령으로 쉘을 실행해봅시다. 그리고 명령어를 아무거나 처보세요. 그리고 우리가 이전의 명령어를 치려고 위 화살표(↑)를 누르면 이상한 문자(^[[A)가 쓰여지게 되어 이전의 명령어를 수행할 수는 없습니다. 결국 sh는 히스토리 기능을 지원하지 못하며, 정확히 얘기해서 저의 명령을 해석하지 못한다는 것입니다. bash에서는 ~/.bash_history에 그 동안의 명령어들 내역을 보관하고 있는데, 본쉘은 ~/.bash_history가 무엇인지도 모르죠.

보통 bash에서 ll은 alias로 ls -alF의 명령어 별명으로 지정합니다. 지금 bash에서 ll을 치면 파일들의 목록이 자세히 나오게 되는데요. ll을 sh상에서 실행하면 실행이 되지 않습니다. bash에서 ll이 수행되지 않는다면 alias지정이 되지 않은 것인데요. vi로 ~/.bashrc를 열고 하단에 alias ll='ls -alF'를 써주시고 source ~/.bashrc를 수행하면 이제 ll이 수행될 것입니다. bashrc는 bash쉘의 설정파일입니다. 

그렇다면 사용자가 접속할때 bash말고 다른 쉘을 사용하고 싶다면 어떻게 할까요? 시스템에서 root로 접속시 기본적으로 사용할 쉘이 어디에 기록되어있냐면 /etc/passwd에 기록되어있습니다. cat /etc/passwd | grep root의 결과가 아래와 같습니다. 리눅스를 조금 공부하셨다면 /etc/passwd에서 각 필드가 무엇을 뜻하는지는 아실겁니다. 

root:x:0:0:root:/root:/bin/bash

맨 오른쪽에 보이는 것이 접속 시 적용할 쉘인데요. 바꾸고 싶다면 chsh -s [shell path]를 입력하면 됩니다. 예를 들면 chsh -s /bin/sh 이렇게 쓰고 재접속을 하면 적용된 쉘로 바뀝니다. 

쉘에서 쓰는 명령어들을 하나의 대본으로 만들어 놓을 수 있는데요. 예를 들어 어느 경로에 들어가서 디렉토리를 만들고 거기에 파일을 만들고 파일의 내용을 어떤 내용으로 기록하고, 그런 작업들 말이에요. 그러려면 사용자가 수동으로 cd를 입력하고 mkdir하고 touch해서 파일을 만들고 그 내용을 echo '블라블라' > file 해서 입력하고 해야겠지요. 하지만 이런 대본(script)를 만들어서 쉘에게 알려주면 일련의 명령을 쉘이 알아서 수행해줍니다. 이것을 우리는 쉘 스크립트라고 하며 확장자가 .sh로 끝나는 파일입니다.

헨리 하워드 홈즈(Heny Howord Holmes, H.H.Holmes)

헨리 하워드 홈즈는 본명이 아니라 가명입니다. 이 가명으로 유명한 이유는 가명을 쓰면서 대량학살이 이뤄지기 때문이죠. 본명은 허만 웹스터 마젯(Herman Webster Mudgett)인데요. 미국에서 기록된 최초 연쇄 살인마입니다. 오늘날의 연쇄살인마와는 클라스가 조금 다릅니다. 아예 호텔까지 지어버리거든요.

출생

홈즈는 1861년 5월 16일, 미국 뉴햄프셔(New hampshire) 길맨턴에서 태어났습니다. 어렸을 적 홈즈는 매우 똘똘하고 예의바르며 어른 들에게 무척이나 예쁨받는 아이였습니다. 게다가 똘똘한 머리까지 가졌습니다. 하지만 어렸을 적 홈즈는 행복하다고 할 수 없었습니다. 아니, 매우 불행한 삶을 살았습니다. 아버지는 독실한 신자였었는데, 특히 잠언 13장 24절의 구문을 그렇게 가슴속에 새겼다고 합니다. 홈즈를 이유없이 폭행하게 됩니다. 왜냐면 아버지는 홈즈를 무척이나 사랑했거든요.

잠언 13장 24절 매를 아끼는 자는 그의 자식을 미워함이라 자식을 사랑하는 자는 근실히 징계하느니라

살인 호텔

1886년, 그는 시카고로 이사를 가는데요. 거기에서 헨리 하워드 홈즈라는 이름을 사용하기 시작합니다. 시카고 어떤 약국에서 조수 역할을 하면서 약국일을 했고, 약국을 인수하게 됩니다. 약국이 잘되자 홈즈는 그 앞에 호텔을 하나 짓는데요. 홈즈는 그 호텔을 성이라고 부릅니다. 이 호텔이 보통 호텔이 아닙니다. 살인을 목적으로 만들어진 호텔이었는데요. 

100개가 넘는 방과 비밀 통로, 그리고 시체를 단숨에 지하실로 옮길 수 있게 만든 낙하장, 각 방들은 파이프가 연결되어있어 이곳에서 독가스를 살포할 수 있었습니다. 벽은 석면으로 이루어져있어 내부의 소리가 밖으로 세어나가지 않았습니다. 지하실은 홈즈가 시체를 해체하고 소각할 수 있는 홈즈의 작업장이었습니다.

이러한 호텔을 짓는데 일조했던 사람은 그의 동료 밴자민 피첼. 그의 기술이 이 성에 접목이 되었습니다.

1893년 시카고 만국 박람회에서 엄청난 관광객들이 몰려오게 되며 숙박 시설이 부족해지게 됩니다. 홈즈는 이런 상황이 떼돈을 벌 수 있는 엄청난 기회였던 셈이죠. 홈즈는 객실에 있는 손님을 티나지 않게 몇몇 죽이게 됩니다. 이렇게 죽인 시체는 의과 대학에 가져다가 팔게 되죠.

체포

살인을 3년간 지속하면서 이제 꼬리를 밟히게 되는데요. 실종자의 대다수가 이 호텔에 머물렀다는 사실을 알게된 경찰은 홈즈를 유력 용의자로 지목하게 감시하게 됩니다.

물론 공범인 벤자민 피첼도 같이 감시하게 되는데, 홈즈는 돈독이 제대로 올라서 자신의 동료 피첼마저 죽입니다. 당시 피첼을 감시하고 있었던 경찰에 의해 드디어 홈즈는 붙잡히게 되면서 살인 호텔에서의 살인은 끝나게 됩니다.

H.H.Holmes는 미국에 기록된 최초의 연쇄살인범으로 매우 유명한 인물입니다. 어떻게 호감형인 외모와 명석한 지성으로 그런 짓을 저질렀을까요? 그 능력을 조금 더 좋은 곳에 썼더라면 어땠을까요? 홈즈는 차트를 달리는 남자에서 소개된바가 있습니다.

이분 매칭(bipartite matching)

그래프에서 정점의 짝을 이루게 해볼까요? 정점은 다른 정점과 짝이 될 수 있는데, 단 여기서 한 정점은 최대 한 정점과 짝을 이룰 수 있는 조건으로 말이죠. 정점이 모두 선택될 필요는 없습니다. 아래의 그래프가 그 예를 보여줍니다. 왼쪽은 1:1 매칭이 된 간선을 선택한 것이고 오른쪽은 1:1 매칭이 되지 않은 그래프입니다. 왼쪽의 그래프는 간선을 3개 갖는데 각 정점은 1:1로 짝을 이루고 있네요. 하지만 오른쪽 그래프에서 주황색 정점은 위, 아래 정점 2개와 짝을 이루고 있으니 1:1 매칭이 되었다고 볼 수 없습니다.

정점을 보기좋게 두 그룹으로 나누면 어떨까요? 왼쪽에 정점이 오른쪽에 정점과 연결될 수 있도록 보면 더 보기 편할 거 같습니다.

이처럼 그래프의 정점을 두 그룹으로 나눈 후 모든 간선이 서로 다른 그룹의 정점들을 연결할 수 있는 그래프를 이분 그래프라고 합니다. 여기서 가장 큰 매칭을 찾아내는 문제를 최대 매칭 문제(Maximum Matching)라고합니다. 간단하게 이분 매칭이라고 부릅니다.

이분 매칭을 네트워크 유량을 이용하여 풀게 됩니다. 그보다는 아주 간단하게 dfs를 이용해서 풀 수 있습니다. 이분 매칭을 구현한 코드가 아래에 있습니다. (이 코드는 구종만 님의 알고리즘 문제해결 전략의 코드입니다.)

#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;

const int MAX_N = 201;
int adj[MAX_N][MAX_N];
vector<bool> visited;
vector<int> partner;
int N, M;
bool dfs(int here) {
	if (visited[here]) return false;
	visited[here] = true;
	for (int there = 1; there <= M; there++) {
		if (adj[here][there]) {
			//there의 짝이 정해지지 않았거나
			//there의 짝이 다른짝과 매칭된다면 true반환
			if (partner[there] == -1 || dfs(partner[there])) {
				partner[there] = here;
				return true;
			}
		}
	}
	return false;
}

int bipartiteMatch() {
	int ret = 0;
	for (int i = 1; i <= N; i++) {
		visited = vector<bool>(N + 1, false);
		if (dfs(i)) ret++;
	}
	return ret;
}

왼쪽의 정점은 A, 오른쪽의 정점은 B라고 칭한다면 partner라는 배열은 B와 짝이된 A정점을 뜻합니다. 초기화는 아래와 같이 -1로 초기화시킵니다. partner[b]가 -1이면 아직 짝이 정해지지 않은 정점을 의미합니다.

partner = vector<int>(M + 1, -1);

전체적으로 보면 왼쪽(here)에서 하나 씩 dfs를 탐색하는데요. dfs를 통해 짝을 찾을 수 있다면 매칭된 수를 하나 증가시킵니다. 코드와 글로는 이해가 어렵습니다. 그림이 있어야겠네요. 처음에 파란색 정점이 dfs를 수행합니다. 이때 조건문을 잘보세요. 설명을 편하게 하기 위해서 왼쪽 정점은 숫자, 오른쪽 정점은 알파벳으로 가정하도록 하겠습니다.

if (adj[here][there]) {
	//there의 짝이 정해지지 않았거나
	//there의 짝이 다른짝과 매칭된다면 true반환
	if (partner[there] == -1 || dfs(partner[there])) {
		partner[there] = here;
		return true;
	}
}

정점 1은 정점 a와 연결이 되고 있고(adj[1][a]), partner[a]의 짝은 아직 정해지지 않았으니, partner[a]=1이 되고 dfs는 true를 반환합니다. 그러니 짝을 하나 찾았네요.

이제 2번에서 dfs를 수행합니다. 연결된 간선의 정점이 a인데, a는 이미 짝이 있으나, a의 파트너인 1이 다른 짝과 매칭될 수 있는지(dfs(1))을 보는데요. 1은 다시 a로 가려고 하지만 이미 방문된 정점(visited[a]=true)이기 때문에 다른 연결된 c쪽으로 탐색합니다. c는 아직 짝이 정해지지 않았기 때문에 c의 파트너를 1로 정합니다. 그 결과 a의 파트너는 3이 될 수 있네요.

이제 다음 정점인 3에서 dfs를 시작합니다. 연결된 정점은 a와 c인데요. a는 이미 짝이 정해져있으나, partner[a]에서 dfs를 수행하면 다른 짝을 구할 수도 있으니 dfs(partner[a]) = dfs(1)를 수행합니다. dfs(1)은 dfs를 수행하지 않은 c로 탐색을 수행할텐데, 이때 c와 유일하게 연결된 정점 3은 이미 방문된 상태이므로 결국 다른 짝을 찾지 못했습니다.

이제 3의 다른 정점 c도 역시 같은 방법으로 경로를 찾는데 c는 이전에 방문되었던 상태라서 종료합니다. 결국 3에서 dfs를 수행한 결과 다른 짝을 찾지 못했네요.

결국 이렇게 이분 그래프에서 최대 2쌍을 찾을 수 있습니다.

예제(BOJ 2188 축사배정)

www.acmicpc.net/problem/2188

이 문제는 위의 코드를 그대로 구현하여 풀 수 있습니다. N마리의 소와 M개의 축사가 있는데, 각 소들은 들어가길 희망하는 축사가 있어 그 외의 축사는 들여보낼 수 없습니다. 소가 희망하는 축사는 여러개가 될 수 있는데요. 이때 소를 최대한으로 들여보낼 수 있는 수를 구하는 것입니다. (1<= N,M <= 200)

첫줄에는 N,M을 입력으로 받고 그 다음부터 차례대로 N 줄까지 1번 소가 원하는 축사의 수, 축사의 번호를 차례대로 입력받습니다. 그때 입출력의 예는 아래와 같습니다.

이 문제를 해결할 수 있는 전체 코드는 아래와 같습니다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;

/*이분매칭
소와 방을 1:1로 짝을 지을 수 있는 최대수를 반환
*/

const int MAX_N = 201;
int adj[MAX_N][MAX_N];
vector<bool> visited;
vector<int> partner;
int N, M;
bool dfs(int here) {
	if (visited[here]) return false;
	visited[here] = true;
	for (int there = 1; there <= M; there++) {
		if (adj[here][there]) {
			//there의 짝이 정해지지 않았거나
			//there의 짝이 다른짝과 매칭된다면 true반환
			if (partner[there] == -1 || dfs(partner[there])) {
				partner[there] = here;
				return true;
			}
		}
	}
	return false;
}

int bipartiteMatch() {
	int ret = 0;
	for (int i = 1; i <= N; i++) {
		visited = vector<bool>(N + 1, false);
		if (dfs(i)) ret++;
	}
	return ret;
}
int main() {

	cin >> N >> M;
	partner = vector<int>(M + 1, -1);
	for (int from = 1; from <= N; from++) {
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			int to;
			cin >> to;
			adj[from][to] = 1;
		}
	}
	cout << bipartiteMatch() << endl;
	return 0;
}

이상으로 그래프 이분 매칭에 대한 개념과 예제 코드였습니다.

스케줄링의 개념

단일 처리 시스템에서는 실행 중인 프로세스(A)가 존재하는데 다른 프로세스(B)가 입출력을 요청하면 그 프로세스(B)는 이전의 프로세스(A)의 자원을 놓을때까지 대기하고 있어야합니다. 하지만 다중 프로그래밍에서는 여러 프로세스들이 동시에 돌아갈 수 있으며, 프로세스가 자원(프로세서 등)을 요청하면 운영체제는 그 자원을 적절히 분배하여 프로세스에게 할당합니다. 그래서 다음과 같은 장점을 얻을 수 있습니다.

1. CPU의 활용 극대화

2.프로세스 처리율(시간 당 작업량)을 늘릴 수 있습니다.

프로세스는 필요한 자원을 할당받기 위해 큐에 대기합니다. 그래서 그 큐에 있는 프로세스를 어떻게 스케쥴링하는지가 프로세스 스케줄링 알고리즘이라고 합니다. 그레서 어떤 스케줄링 알고리즘이 있는지 봅시다. 

잠깐 프로세스 스케줄링에 관한 용어 몇가지만 알아보고 가도록 합시다. 대기 시간, 실행 시간, 반환 시간입니다. 

1 선입선처리 스케줄링(First Come First Served, First In First Out)

선입선처리(FCFS, FIFO) 알고리즘은 말 그대로 먼저 요청한 프로세스가 먼저 자원을 제공받으며 이미 사용중이라면 사용이 끝날때까지 기다려야하는 스케줄링 방식입니다.

프로세스 5개가 있고, 각가 P1의 실행시간 10, P2의 실행시간 5, P3의 실행시간 6, P4의 실행시간 9, P5의 실행시간 10이라고 할때 반환 시간을 알아보도록 하죠.

먼저 요청한 프로세스가 먼저 제공받으니 P1부터 차례대로 자원을 할당받습니다. 그래서 프로세스의 반환시간과 대기시간을 구하면 아래와 같습니다.

2. 최소 작업 우선 스케줄링(Shortest Job First)

프로세스의 실행 시간을 이용하여 가장 짧은 시간을 갖는 프로세스가 먼저 자원을 할당받는 방식입니다. 이 방식은 선점할 수도 있는 스케줄링 방식입니다. 이전에 FIFO방식은 중간에 다른 프로세스가 들어오면 그 프로세스는 대기해야했죠? 이 스케줄링 방식은 선점 또는 비선점이 가능합니다. 위와 같은 프로세스라고 할때 비선점형 SJF 스케줄링의 결과는 아래와 같습니다.

자 P1이 먼저 요청해서 자원을 할당받아 놓은 상태인데, P2가 도착합니다. 비선점형이기 때문에 P2는 우선 기다리고 있는데 P1의 작업이 끝나기 전에 P3, P4 ,P5의 요청이 도착하네요. 그러면 실행 시간이 가장 작은 P4가 자원을 할당받아 쓰고 그 다음인 P3이 자원을 할당받아 사용합니다. 이렇게 되면 위와 같은 결과가 도출되지요.

그렇다면 비선점형 SJF는 어떨까요? 아래의 표가 선점형 SJF의 결과입니다.

이해를 돕기 위해서 아래의 간트 차트를 보세요.  P1이 먼저 도착해서 수행하고 있는 와중에 P2가 도착하는데요. P2는 수행되어야할 시간이 P1보다 크니 P1은 계속 작업을 수행합니다. 그러다가 P3가 도착하는데 P1이 수행해야할 시간보다 P3의 수행시간이 더 짧으니 P3가 작업을 수행합니다. 그런데 P4가 다음에 도착하네요. P4가 더 적은 시간을 갖으니 P4를 수행합니다. 이때 P4가 끝나면 남아있는 프로세스 중에서 가장 적은 수행시간을 갖는 P3의 작업을 이어서 하게 됩니다.

3. 우선순위 스케줄링

우선순위 스케줄링은 프로세스마다 우선순위라는 속성이 붙게 됩니다. 우선순위 스케줄링도 역시 선점, 비선점형으로 스케줄링이 가능합니다. 숫자가 높을 수록 우선순위가 높고 만약 우선순위가 같다면 FIFO방식으로 동작합니다.

그래서 아래는 선점형에서의 결과를 나타낸 표입니다. 약간 헷갈릴 수 있을텐데요. P1 먼저 수행하다가 P3가 오면 우선 순위가 P3가 더 높으니까 P1은 대기하고 P3가 작업을 수행합니다.

다음은 비선점형일때의 결과 표입니다.

만약 우선순위가 낮은 프로세스가 높은 프로세스에 의해 실행이 되고 있지 않은 상황이라면 어떻게 될까요? 이때는 그 프로세스의 우선순위를 점차 높여 처리받게끔 하는 에이징이라는 기법을 사용합니다.

4. 라운드 로빈 스케줄링(Round-Robin)

라운드 로빈 스케줄링은 시분할 시스템을 위해 설계된 스케줄링 기법입니다. 이 스케줄링은 작은 단위의 시간인 시간 할당량(Time-Slice)을 정의하여 그 시간 만큼 자원을 할당하는 방식입니다. 그래서 그 시간안에 작업을 끝내지 못하면 다음 프로세스가 다시 그 시간만큼 자원을 할당받아씁니다. 여기서 시간 할당량을 5로 정하고 간트 차트와 결과를 보면 아래와 같습니다. 

각 프로세스들은 공정하게 5만큼의 시간 동안 작업을 진행하는 것을 볼 수 있네요.