hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
부분 순서 집합 예
모든 전순서는 부분 순서이다. 예를 들어, 자연수 집합 이나 정수 집합 , 유리수 집합 , 실수 집합  위의 표준적인 순서는 전순서이므로 부분 순서이다.
집합 의 멱집합  위의 포함 관계 는 부분 순서이며, 만약 가 두 개 이상의 원소를 갖는다면 이는 전순서가 아니다. 또한, 이를 의 부분 집합에 국한시켜도 역시 부분 순서를 이룬다. 예를 들어,
등등은 특정한 부분 집합들의 집합이므로 포함 관계를 통해 부분 순서를 갖는다.
부분수열에 의한 관계는 특정한 집합 (예를 들어 어떤 수열의 부분수열들의 집합, 집합 의 원소를 항으로 하는 수열들의 집합) 위의 부분 순서이다. 이는 일반적으로 전순서가 아니다. 이와 비슷하게 문자열들의 집합에서 부속문자열에 의한 관계는 부분 순서이다.
양의 정수의 집합  위의 약수 관계 (는 가 의 약수라는 의미)는 부분 순서이며, 이는 전순서가 아니다.
비순환 유향그래프의 꼭짓점들의 집합은 도달가능성에 의한 부분 순서를 가진다.
부분 순서 집합 의 수열 공간 에 정의된 성분별 순서는 부분 순서이다.
부분 순서 집합 응용
부분 순서 에 대하여, 전순서 를 의 선형 확장이라고 한다. 예를 들어, 부분 순서 집합의 직접곱의 한 가지 선형 확장은 사전식 순서이다. 선택 공리 아래, 임의의 부분 순서는 선형 확장을 갖는다. 컴퓨터 과학에서, 위상 정렬은 부분 순서의 선형 확장을 구하는 알고리즘이다.
반군 (수학)
추상대수학에서 반군(半群, 영어: semigroup)은 결합법칙을 따르는 하나의 이항 연산이 부여된 대수 구조이다.
반군 (수학) 정의
반군 은 다음과 같은 데이터로 구성되는 대수 구조이다.
은 항등원을 가질 필요가 없다. 항등원을 갖는 반군을 모노이드라고 한다. 즉, 반군과 모노이드의 관계는 유사환과 환의 관계와 같다. 보통, 편의상 이항 연산을 (곱셈과 같이) 생략하는 경우가 많다.
즉, 다음과 같은 포함 관계가 성립한다.
마그마 ⊋ 반군 ⊋ 모노이드 ⊋ 군
두 반군 ,  사이의 반군 준동형(半群準同型, 영어: semigroup homomorphism)은 다음 조건을 만족시키는 함수 이다.
모든 모노이드는 반군이므로, 두 모노이드 사이의 반군 준동형을 생각할 수 있다. 두 모노이드 사이의 모든 모노이드 준동형은 반군 준동형이지만, 두 모노이드 사이의 반군 준동형은 모노이드 준동형이 아닐 수 있다 (즉, 항등원을 항등원으로 대응시키지 않을 수 있다).
반군 의 부분 집합 가 다음 조건을 만족시킨다면, 를 의 부분 반군(部分半群, 영어: subsemigroup)라고 한다.
모노이드의 모든 부분 모노이드는 부분 반군이지만, 모노이드의 부분 반군은 부분 모노이드가 아닐 수 있다 (즉, 항등원을 포함하지 않을 수 있다).
반군 (수학) 정의
반군  속에서, 다음 조건을 만족시키는 부분 반군 을 의 왼쪽 아이디얼(영어: left ideal)이라고 한다.
반군  속에서, 다음 조건을 만족시키는 부분 반군 을 의 오른쪽 아이디얼(영어: right ideal)이라고 한다.
왼쪽 아이디얼이자 오른쪽 아이디얼인 부분 반군을 아이디얼(영어: ideal)이라고 한다. 모노이드의 아이디얼은 부분 모노이드를 이룰 필요가 없다 (즉, 1을 포함하지 않을 수 있다). 이는 환의 환론적 아이디얼이 부분환을 이룰 필요가 없는 것과 마찬가지다.
반군 의 부분 반군의 몫반군을 의 인자(영어: divisor)라고 한다.
반군  속에서, 다음과 같은 원소 가 존재한다면, 이를 의 왼쪽 영원(영어: left zero element)이라고 한다.
반군  속에서, 다음과 같은 원소 가 존재한다면, 이를 의 오른쪽 영원(영어: right zero element)이라고 한다.
왼쪽 영원이자 오른쪽 영원인 원소를 영원(영어: zero element)이라고 한다. 왼쪽 영원과 오른쪽 영원은 일반적으로 유일하지 않지만, (양쪽) 영원은 만약 존재한다면 유일하다.
반군 (수학) 정의
반군  속에서, 다음과 같은 원소 가 존재한다면, 이를 의 왼쪽 항등원(영어: left identity element)이라고 한다.
반군  속에서, 다음과 같은 원소 가 존재한다면, 이를 의 오른쪽 항등원(영어: right identity element)이라고 한다.
왼쪽 항등원이자 오른쪽 항등원인 원소를 항등원(영어: identity element)이라고 한다. 왼쪽 항등원과 오른쪽 항등원은 일반적으로 유일하지 않지만, (양쪽) 항등원은 만약 존재한다면 유일하다. 이렇게 양쪽 항등원을 갖는 반군을 모노이드라고 한다.
반군  속에서 를 만족시키는 원소 를 멱등원(영어: idempotent element)이라고 한다. 왼쪽 영원 · 오른쪽 역원 · 왼쪽 항등원 · 오른쪽 항등원은 모두 항상 멱등원이다.
유한 반군은 항상 적어도 하나 이상의 멱등원을 갖는다. 보다 일반적으로, 모든 원소의 차수가 유한한 반군은 적어도 하나 이상의 멱등원을 갖는다. 이는 하나의 원소로 생성되는 모든 유한 반군은 멱등원을 갖기 때문이다.
반군  속의 원소 에 대하여, 만약 가 되는 원소 가 존재한다면, 를 정칙원(영어: regular element)이라고 하고, 를 의 유사역원(영어: pseudoinverse)이라고 한다. 유사역원은 일반적으로 유일하지 않다.
반군 (수학) 연산
반군 가 주어졌을 때, 집합  위에 다음과 같은 다른 이항 연산 을 줄 수 있다.
그렇다면 는 반군을 이룬다. 이를 의 반대 반군(反對半群, 영어: opposite semigroup)이라고 하고, 으로 쓴다.
반대 모노이드나, 군론의 반대군이나, 환론의 반대환은 반대 반군의 특수한 경우이다.
군의 경우 모든 군은 스스로의 반대군과 역원 함수를 통해 표준적으로 동형이지만, 반군의 경우 일반적으로 스스로의 반대 반군과 동형이 아니다. (가환 반군은 물론 스스로의 반대 반군과 같다.)
반군  위의 합동 관계 는
를 만족시키는  위의 동치 관계이다. 반군 위의 합동 관계가 주어졌을 때 몫반군(-半群, 영어: quotient semigroup) 을 정의할 수 있다. 군이나 유사환의 경우와 달리, 반군의 경우 합동 관계는 일반적으로 정규 부분군이나 유사환 아이디얼과 같은 부분 집합으로 나타내어지지 않는다.
몫반군의 특별한 경우로, 반군 의 아이디얼 가 주어졌을 때, 동치 관계
반군 (수학) 연산
는 합동 관계를 이루며, 따라서 몫반군 를 정의할 수 있다. 이러한 꼴의 몫반군을 리스 몫반군(영어: Rees quotient)이라고 한다. 만약 가 공집합이 아니라면, 는 항상 영원 를 가진다. 만약 이라면 이며, 반대로 라면 은 자명군이다.
반군의 모임은 대수 구조 다양체이므로, 여러 개의 반군들의 직접곱을 정의할 수 있다. 이는 반군과 반군 준동형의 범주에서의 범주론적 곱이다. 구체적으로, 반군들의 집합 의 직접곱 은 집합으로서 곱집합과 같으며, 그 위의 이항 연산은 다음과 같다.
각 의 성질은 에게 다음과 같이 유전된다.
두 반군 ,  및 의  위의 작용 이 주어졌을 때, 반직접곱 를 정의할 수 있다.
반군의 모임은 대수 구조 다양체이므로, 여러 개의 반군들의 자유곱을 정의할 수 있으며, 이는 반군의 범주의 쌍대곱이다. 반군의 자유곱은 모노이드의 자유곱과 다르다. 즉, 각 성분들의 항등원이 모노이드 자유곱에서는 한 원소로 합쳐지지만, 반군 자유곱에서는 그렇지 않다.
반군 (수학) 연산
반군 가 주어졌을 때, 에 다음과 같은 이항 연산을 주자.
그렇다면 는 반군을 이루며, 새로 추가한 원소 은 그 속의 영원을 이룬다. 만약 가 모노이드라면  역시 모노이드이다.
반군 가 주어졌을 때, 그 멱집합  위에 다음과 같은 이항 연산을 주자.
그렇다면 는 반군을 이룬다. 는 항상 영원을 가지며, 이는 공집합이다. 또한,  역시 반군을 이룬다.
만약 가 모노이드라면  역시 모노이드이다.
군론의 화환곱(영어: wreath product)을 반군에 대하여 일반화할 수 있다. 즉, 두 반군 , 와 가 왼쪽에서 작용하는 집합 가 주어졌을 때, 화환곱 는 집합  위에 주어진 반군이다. 구체적으로, 이는 다음과 같다.
작용을 갖춘 반군들에 대하여, 화환곱은 결합 법칙을 따른다.
반군 (수학) 성질
군론의 케일리 정리와 마찬가지로, 반군에 대하여 케일리 정리가 성립한다. 즉, 임의의 반군 에 대하여, 어떤 집합  위의 완전 변환 모노이드 로 가는 단사 반군 준동형
이 존재한다. 또한, 만약 가 유한 반군이라면  역시 유한 집합으로 잡을 수 있다.
반군 의 부분 반군 가운데 부분군인 것들은 포함 관계에 따라 부분 순서 집합을 이룬다. 그렇다면, 다음 두 집합 사이에 표준적인 전단사 함수가 존재한다.
구체적으로, 의 극대 부분군 에 대하여, 는 의 멱등원을 이룬다. 반대로, 임의의 멱등원 에 대하여, 에 대한 역원을 갖는 모든 원소들의 집합
은 를 항등원으로 하는 극대 부분군이다.
공집합이 아닌 모든 유한 반군은 항상 하나 이상의 멱등원을 가진다. (모노이드의 경우 항등원이 멱등원이므로 이는 자명하게 성립한다.) 그러나 이는 무한 반군에 대하여 성립하지 않는다.
반군 (수학) 종류
다음과 같은 특별한 종류의 반군들의 모임이 존재한다.
왼쪽 소거 반군(영어: left-cancellative semigroup)은 만약 라면 가 성립하는 반군이다.  오른쪽 소거 반군(영어: right-cancellative semigroup)은 만약 라면 가 성립하는 반군이다. 소거 반군(영어: cancellative semigroup)은 왼쪽 소거 반군이자 오른쪽 소거 반군인 반군이다.
반군 (수학) 분류
유한 반군에 대하여, 크론-로즈 정리(영어: Krohn–Rhodes theorem)라는 구조 정리가 존재한다. 이에 따르면, 모든 유한 반군 는 유한 단순군과 비자명군을 포함하지 않는 유한 반군들의 화환곱의 부분 반군의 몫반군이다. 즉, 다음과 같은 꼴로 나타낼 수 있다.
여기서
가환 반군의 경우, 다음과 같은 구조 정리가 존재한다.
임의의 가환 반군 에서 가환 멱등 반군 으로 가는 반군 준동형 이 주어졌다고 하자. 그렇다면, 다음이 성립한다.
임의의 가환 반군 에 대하여, 이 가환 멱등 반군이 되는 가장 섬세한 합동 관계 가 존재하며, 는 에 대한 등급 반군을 이룬다. 또한, 각 에 대하여, 동차 성분 는 모두 아르키메데스 반군을 이룬다.
따라서, 가환 반군의 분류는 가환 멱등 반군의 분류와 아르키메데스 반군의 분류로 귀결된다. 가환 멱등 반군은 공집합이 아닌 유한 부분 집합이 항상 최소 원소를 갖는 부분 순서 집합과 동치이다. 이 경우 부분 순서는 와 같다.
반군 (수학) 예
모든 모노이드는 반군이다. 따라서 모든 군은 반군이다. 모든 유사환 에 대하여, 은 반군을 이룬다. (는 아벨 군이므로 역시 반군이다.) 모든 격자 에 대하여, 와  역시 각각 가환 멱등 반군을 이룬다. (만약 이 최대 원소 또는 최소 원소를 갖지 않는다면, 둘 가운데 하나는 모노이드를 이루지 않는다.)
임의의 음이 아닌 정수 에 대하여, 는 덧셈에 대하여 가환 반군을 이룬다. 이라면 이는 모노이드가 아니다.
공집합  위에 유일한 이항 관계를 준다면, 이는 자명하게 반군을 이룬다. 이를 공반군(空半群, 영어: empty semigroup)이라고 하며, 이는 모노이드가 아니다.
집합 에 원소 을 추가한 분리합집합  위에 다음과 같은 이항 연산을 상수 함수로 정의하자.
그렇다면 은 반군을 이룬다. 이를 영반군(零半群, 영어: zero monoid)이라고 한다. 만약 가 공집합이 아니라면 이는 모노이드를 이루지 않는다. (만약 가 공집합이라면 이는 자명군을 이룬다.)
아벨 군 위에 곱셈을 모두 0으로 정의하여 영 유사환을 정의할 수 있는데, 그 곱셈 반군은 영반군이다.
반군 (수학) 예
반군의 모임은 대수 구조 다양체이므로, 이에 대한 자유 대수를 정의할 수 있다. 집합  위의 자유 반군(自由半群, 영어: free semigroup)은  위의 클레이니 스타 (자유 모노이드) 에서, 길이가 0인 문자열  (항등원)을 제거한 반군 이다.
한원소 집합으로 생성되는 자유 반군은 양의 정수의 덧셈 반군 과 동형이다.
마찬가지로 자유 가환 반군(自由可換半群, 영어: free commutative semigroup)을 정의할 수 있다. 집합  위의 자유 가환 모노이드는 의 원소들로 구성된 유한 중복집합들의 모노이드이며,  위의 자유 가환 반군은 이 가운데 공집합을 제거한 것이다.
집합  위에 다음과 같은 두 이항 연산을 정의하자.
그렇다면 과 는 각각 반군을 이룬다. 를 왼쪽 영원 반군(영어: left zero semigroup), 를 오른쪽 영원 반군(영어: right zero semigroup)이라고 한다.
왼쪽 영원 반군에서, 모든 원소는 왼쪽 영원이자 오른쪽 항등원이다. 오른쪽 영원 반군에서, 모든 원소는 오른쪽 영원이자 왼쪽 항등원이다.
반군 (수학) 예
왼쪽 · 오른쪽 영원 반군은 가 한원소 집합이 아니라면 모노이드를 이루지 않는다.
하나의 원소로 생성되는 반군은 항상 가환 반군이며, 다음 두 경우 가운데 하나와 동형이다.
마찬가지로, 하나의 원소로 생성되는 모노이드는 항상 가환 모노이드이며, 다음 두 경우 가운데 하나와 동형이다.
크기가 인 반군의 동형류의 수는 다음과 같다. (. 모노이드와 그 반대 모노이드는 일반적으로 서로 동형이 아니라고 간주한다.)
1, 1, 5, 24, 188, 1915, 28634, 1627672, 3684030417, 105978177936292, … (OEIS의 수열 A027851)
만약 반군과 그 반대 반군을 동치로 놓았을 때, 동치류의 수는 다음과 같다. ()
1, 1, 4, 18, 126, 1160, 15973, 836021, 1843120128, 52989400714478, … (OEIS의 수열 A001423)
만약 반군과 그 반대 반군을 동치로 놓았을 때, 정확히 1개의 멱등원을 갖는 반군의 동치류의 수는 다음과 같다.
반군 (수학) 예
0, 1, 2, 5, 19, 132, 3107, 623615, 1834861133, 52976551026562, … (OEIS의 수열 A002786)
정확히 2개의 멱등원을 갖는 반군의 동형류의 수는 다음과 같다.
0, 0, 2, 7, 37, 216, 1780, 32652, 4665709, 12710266442, … (OEIS의 수열 A002787)
크기가 인 가환 반군의 동형류의 수는 다음과 같다.
1, 1, 3, 12, 58, 325, 2143, 17291, 221805, 11545843, 3518930337, … (OEIS의 수열 A027851)
크기가 0인 반군은 공반군 밖에 없고, 크기가 1인 반군은 자명군 밖에 없다. 크기가 2인 반군은 총 5개가 있다.
크기가 3인 반군은 총 24개가 있다. 이 가운데 모노이드가 아닌 것은 17개이며, 다음과 같다. 아래 목록에서 표시는 반군의 표시이며, 영원의 경우 항상 0으로 표기하며 이에 대한 관계 ( 등)는 생략하였다.
반군 (수학) 역사
1904년에 장아르망 드 세기에(프랑스어: Jean-Armand de Séguier, 1862~1935)가 최초로 반군(프랑스어: semi-groupe)이라는 용어를 사용하였으나,:8 드 세기에는 이를 오늘날과 달리 "소거 반군"의 뜻으로 사용하였다. 1908년에 해럴트 힐턴(영어: Harold Hilton, 훗날 해럴드 심프슨(영어: Harold Simpson)으로 개명, 1876~1974)은 최초로 영어 문헌에서 "반군"(영어: semi-group)이라는 용어를 사용하였으며, 힐턴은 반군을 오늘날과 같이 정의하였다.
반군에 대한 최초의 (자명하지 않은) 정리들은 하인리히 브란트(독일어: Heinrich Brandt, 1886~1954)의 1926년 논문과 안톤 카시미로비치 수시케비치(러시아어: Анто́н Казими́рович Сушке́вич, 1889~1961)의 1928년 논문이다. 앨프리드 호블리첼 클리퍼드(영어: Alfred Hoblitzelle Clifford, 1908~1992)는 수시케비치의 구조 정리들을 일반화하였다.
반군 (수학) 역사
데이비드 리스(영어: David Rees, 1918~2013)는 1947년에 역원 반군(영어: inverse semigroup)의 개념을 도입하였고, 예브게니 세르게예비치 랴핀(러시아어: Евге́ний Сергее́вич Ля́пин, 1914~2005)와 고든 프레스턴(영어: Gordon Preston, 1925~2015)은 그 이론을 발전시켰다. 이 밖에도, 제임스 알렉산더 그린(영어: James Alexander Green, 1926~2014), 존 매킨토시 하위(영어: John Mackintosh Howie, 1936~2011) 등이 반군 이론에 공헌하였다. 특히, 그린은 1951년에 그린 관계를 도입하였다.
사무엘 에일렌베르크(1913~1998)와 마르셀폴 쉬첸베르제(프랑스어: Marcel-Paul Schützenberger, 1920~1996)는 반군 이론을 자동기계 이론에 응용하여 발전시켰다. 특히, 쉬첸베르제는 1957년에 쉬첸베르제 군을 도입하였다.
크론-로즈 정리는 미국의 케네스 크론(영어: Kenneth Krohn)과 존 루이스 로즈(영어: John Lewis Rhodes, 1937~)가 1965년 박사 학위 논문에서 발표하였다.
1961년~1967년에 클리퍼드와 프레스턴은 당시 알려진 반군 이론을 체계화하여, 반군 이론에 대한 최초의 책을 출판하였다.
야고보 (제베대오의 아들)
제베대오 또는 세베대의 아들 야고보(히브리어: יעקב, 그리스어: Ιάκωβος 이아코보스[*], 라틴어: Iacobus, 영어: James the Great, ? - 44년)는 예수 그리스도의 열두 사도들 가운데 한 사람이며, 사도 요한의 형제이다. 야고보라는 이름의 유래는 ‘발꿈치를 잡다’라는 뜻이다. 또 다른 사도인 알패오의 아들 야고보와 동명이인이라 혼동을 피하기 위해 흔히 ‘대(大)야고보’라고 부른다. 사도 가운데 가장 먼저 순교하였고, 기독교의 성인으로 기린다. 로마 가톨릭에서 축일은 7월 25일이며, 동방 정교회에서 축일은 4월 30일이다. 회화에서는 종종 말을 타고, 한 손에는 순례자의 종, 다른 손에는 칼을 들고 무어인을 무찌르는 모습으로 그린다. 상징물은 책·칼·외투·조가비·모자·지팡이·자루·호리병이며, 수의사·약사·기수·식료품 상인·순례자·에스파냐·과테말라·니카라과의 수호 성인이다.
야고보 (제베대오의 아들) 행적
야고보는 제베대오(세배대)와 살로메 사이 태어난 첫째 아들로, 동생 요한과 함께 아버지를 도와 갈릴래아 호숫가에서 어부로 일하다가 예수를 만나서 같은 직업의 다른 형제인 베드로와 안드레아와 함께 부름을 받았다. 예수의 부름을 듣자 그들은 곧 배를 버리고 아버지를 떠나 예수를 따라갔다(마태 4,21-22). 마가 복음사가는 제베대오가 일용직 노동자들을 고용했다고 말하는 것을 보면(마가 1:19-20), 야고보, 요한 형제 집안은 임금노동자는 아니고, 사업장을 갖춘 중간계급으로 보인다. 김성 협성대학교 교수에 따르면, 고대 이스라엘에서 물고기는 훈제한 물고기 한 수레를 황소와 바꿀 정도로 비싼 식량이었다고 한다. 그럼에도, 이들은 예수의 부름을 듣고서 즉시 안정된 삶을 버렸다.
야고보 (제베대오의 아들) 행적
복음서에 있는 두 가지 사건이 야고보와 요한 형제의 성격을 보여주고 있다. 하루는 야고보와 요한 형제(또는 그들의 어머니라고도 함)가 예수에게 하늘 나라에서 자신들이 각각 예수의 오른편과 왼편에 앉도록 해달라고 간청했다. 이때 예수는 “너희는 너희가 청하고 있는 것이 무엇인지조차도 모르는구나! 너희는 내가 마시고자 하는 잔을 마실 수 있으며, 내가 받을 고난의 세례를 받을 수 있겠느냐?” 며 물었다. 그러자 그들은 자신있게 할 수 있다고 대답했다. 이에 예수는 “죽음의 잔을 마시고 고통의 세례를 받을 수는 있다. 그러나 나의 오른편이나 왼편에 앉는 특권은 내가 줄 수 있는 것이 아니고 오직 하느님께서 미리 정하신 이들을 위한 것이다.” 라고 대답하였다. 다른 사도들이 이 형제의 야심에 분개하자, 예수는 그들에게 “너희 사이에서 높은 사람이 되고자 하는 사람은 남을 섬기는 사람이 되어야 하고 으뜸이 되고자 하는 사람은 종이 되어야 한다. 사람의 아들도 섬김을 받으러 온 것이 아니라 섬기러 왔고 또 많은 사람을 위하여 목숨을 바쳐 몸값을 치르러 온 것이다”라고 훈계하여 권력의 목적은 봉사하는 것으로서 다른 사람들에게 무언가를 강요하거나 그들 위에 군림하는 것이 아니라는 것을 일깨워 주었다(마태 20,27-28).
야고보 (제베대오의 아들) 행적
또한 두 형제는 예수가 예루살렘으로 가던 길에 자신들을 영접하지 않은 불친절한 사마리아 사람들을 보고 불같이 화를 내며 “주님, 저희가 하늘에서 불을 내리게 하여 그들을 불살라 버릴까요?” 하고 말했다. 예수는 그 말을 듣고 그들을 호되게 질책하였다(누가 9,54).
이러한 타고난 과격한 성격 때문에 예수는 요한과 야고보 형제를 아울러 ‘천둥의 아들’이라는 뜻의 보아네르게스(Boanerges)라는 별명을 붙여주었지만(마르 3,17), 야고보는 베드로 및 요한과 더불어 타볼 산에서의 변모와 야이로의 딸 소생과 겟세마네에서의 피땀을 흘린 기도를 보고 사람들에게 증언할 특권을 누리며 총애를 받던 세 제자 중의 한 사람이었다(마태 7,1; 마르 1,29-31; 마르 5,37; 마르 13,3-14; 14,32-35). 그런 야고보도 예수가 이스카리옷 유다에게 배신당하여 군인들에게 붙잡혀 끌려갔을 때는 지레 겁을 먹고 다른 사도들과 함께 어디론가 도망가 숨어버리고 말았다.
야고보 (제베대오의 아들) 행적
성령 강림 이후 다른 사도들처럼 야고보 역시 사마리아와 유대 지역에서 복음을 전파하였으며 심지어 이베리아반도까지도 다녀갔다는 기록이 있다. 44년 예루살렘에서 그리스도인을 탄압하던 헤로데 아그리파 1세에 의하여 체포되어 파스카 축일 전날 참수형으로써 순교를 하였다.
야고보의 유해는 처음에는 예루살렘에 안장되었으나, 정확히 어디에 묻혔는지에 대해서는 행방이 묘연하여 찾을 길이 없었다. 그러던 중 9세기 즈음에 하늘에서 한 별빛이 내려와 숲 속의 한 동굴을 비추어 사람들이 그 안으로 가보니 야고보의 무덤이 있었다고 한다. 그 후 야고보의 유해는 에스파냐의 서북부 지역 갈리시아의 산티아고데콤포스텔라로 이장되어 모셔졌고, 당시 국왕 알폰소는 그 묘지 위에 150년에 걸쳐 웅대한 대성당을 건축하였다. 산티아고데콤포스텔라 대성당 안으로 들어가보면 그의 유골함이 전시되어 있다.
그 후 844년 이베리아반도에 세력을 뻗친 이슬람교 세력에 로마 가톨릭 세력이 대항하기 위하여 일어난 클라비호 전투에서 야고보가 에스파냐군 앞에 나타나는 기적을 일으켜 이슬람군을 무찔렀다는 말이 전해지면서 그에 대한 신심이 에스파냐를 중심으로 대폭 커져 산티아고데콤포스텔라는 금새 세계적인 순례지가 되었다. 참고로 산티아고는 야고보의 에스파냐어식 표기이다.
블라디미르 비소츠키
블라디미르 세묘노비치 비소츠키(Vladimir Semyonovich Vysotsky, 러시아어: Владимир Семёнович Высоцкий, 1938년 1월 25일 ~ 1980년 7월 25일)는 소련의 배우 겸 시인이며 가수 겸 작사가이다.
비소츠키는 1938년 1월 25일 모스크바에서 태어났다. 아버지는 군장교였으며 어머니는 독일어 번역사였는데 그의 출생직후 이혼하여 계모의 손에서 컸다. 1954년 부모의 희망에 따라 모스크바 기술대학(Moscow Institute of Civil Engineering)에 진학해서 공부했지만 적성에 맞지 않아 곧바로 중단하고 자신의 꿈을 이루기 위해 1956년 모스크바 예술극단의 배우학교에 입학하여 4년 동안 배우 수업을 받는다.
비소츠키는 1960년 대학을 졸업하고 알렉산드르 푸시킨 극단(Aleksandr Pushkin Theatre)에 입단한 후 단역배우로 전전하던 시절 가끔씩 친구들 앞에서 자신이 작곡하고 가사를 붙인 노래를 불렀다. 독재체제에 대한 비판과 억눌린 인민들의 삶에 대해 분노에 찬 목소리로 절규하듯 700여 곡의 저항가요를 불렀다.
블라디미르 비소츠키
그는 세상을 떠날 때까지 단 한 권의 시집도, 단 한장의 음반도 내지 못하고 정보기관으로부터 늘 감시를 받았다. 본인은 스스로를 가수라고 인정하지 않았지만 카세트테이프에 녹음된 그의 노래는 사람들에게 전해져 소련은 물론 주변 국가들에까지 널리 퍼지게 되었다. 배우로도 성공하여 수많은 연극과 드라마에서 연기했으며 28편의 영화에 출연하였다.
그는 1980년 7월 27일 모스크바에서 42세의 젊은 나이에 심장마비로 죽었는데, 사인은 평소 과도했던 음주벽 때문이라고 하지만 러시아인들 사이에서는 비소츠키의 사인은 마약복용으로 인한 쇼크사라는 이야기도 있다. 사후에도 그의 노래는 꾸준히 사랑받아 1980년대 후반에 이르러 소련 정부는 그의 시와 노래의 출판을 허용하기 시작했으며 그는 아직도 러시아에서 가장 사랑받는 배우/음유시인들 중 한명이다.
답답함을 토해내듯 노래불렀던 비소츠키는 부드러운 목소리로 서정적인 음유시가를 부른 불라트 오쿠자바(Bulat Shalvovich Okudzhava)와 함께 러시아의 대표적인 음유시인이 되었다. 그는 인기있는 배우였지만 오히려 음유시가의 발전에 지대한 공을 세워 음유시가를 좋아하는 사람들에게 우상이 되었다.
입법부
입법부(立法府, 문화어: 립법부, 영어: legislature, 프랑스어: pouvoir législatif)는 법률이나 조례 등을 제정하거나 수정 또는 폐기하는 중앙정부 혹은 지방정부 제도 기관(制度 機關)이다. 행정부, 사법부와 함께 국가의 주요 기능을 담당한다. 근데 민주주의 정치는 권력을 독점하는 것을 막기 위해 입법권, 행정권, 사법권을 서로 견제하는 세 개의 국가 기관에 분리하여 부여하는 것을 원칙으로 하고 있다. 이러한 권력의 분리와 견제를 삼권분립의 원칙이라 한다.
입법부 의미
입법기관은 광의로는 법률제정에 참여하는 권한을 가진 국가기관을 통틀어 이르는 말이다.
입법부 나라별 입법부 명칭
입법부는 나라마다 부르는 명칭이 다르다. 나라에 따른 명칭은 아래와 같다.
캐나다 - 캐나다 의회(영어: Parliament of Canada, 프랑스어: Parlement du Canada)
상원(영어: Senate of Canada 프랑스어: Sénat du Canada)
하원(영어: House of Commons of Canada 프랑스어: Chambre des communes du Canada)
버퍼 오버플로
버퍼 오버플로(영어: buffer overflow) 또는 버퍼 오버런(buffer overrun)은 메모리를 다루는 데에 오류가 발생하여 잘못된 동작을 하는 프로그램 취약점이다. 컴퓨터 보안과 프로그래밍에서는 프로세스가 데이터를 버퍼에 저장할 때 프로그래머가 지정한 곳 바깥에 저장하는 것을 의미한다. 벗어난 데이터는 인접 메모리를 덮어 쓰게 되며 이때 다른 데이터가 포함되어 있을 수도 있는데, 손상을 받을 수 있는 데이터는 프로그램 변수와 프로그램 흐름 제어 데이터도 포함된다. 이로 인해 잘못된 프로그램 작동이 나타날 수 있으며, 메모리 접근 오류, 잘못된 결과, 프로그램 종료, 또는 시스템 보안 누설이 발생할 수 있다.
버퍼 오버플로가 코드를 실행시키도록 설계되거나 프로그램 작동을 변경시키도록 설계된 입력에 의해 촉발될 수 있다. 따라서 이는 많은 소프트웨어 취약점의 근간이 되며 악의적으로 이용될 수 있다. 경계 검사로 버퍼 오버플로를 방지할 수 있다.
버퍼 오버플로
버퍼 오버플로는 보통 데이터를 저장하는 과정에서 그 데이터를 저장할 메모리 위치가 유효한지를 검사하지 않아 발생한다. 이러한 경우 데이터가 담긴 위치 근처에 있는 값이 손상되고 그 손상이 프로그램 실행에 영향을 미칠 수도 있다. 특히, 악의적인 공격으로 인해 프로그램에 취약점이 발생할 수도 있다.
흔히 버퍼 오버플로와 관련되는 프로그래밍 언어는 C와 C++로, 어떤 영역의 메모리에서도 내장된 데이터 접근 또는 덮어쓰기 보호 기능을 제공하지 않으며 어떤 배열에 기록되는 데이터가 그 배열의 범위 안에 포함되는지 자동으로 검사하지 않는다.
버퍼 오버플로 기술적인 설명
버퍼 오버플로는 불충분한 경계 검사에 의해 버퍼에 쓰인 데이터가 버퍼에 이미 할당된 근접한 메모리 주소에 있는 데이터 값을 오염시킬 때 발생한다. 대부분 이는 문자열을 하나의 버퍼에서 다른 버퍼로 복사할 때 발생한다.
아래의 예제에서, 프로그램은 메모리에서 인접해 있는 두 아이템을 정의하였다: 8 바이트 길이 스트링 버퍼, A. 그리고 2 바이트 정수형, B. 우선, A는 8바이트 모두 숫자 0값만 포함하고 B는 숫자 3을 포함한다. 문자들은 1바이트 크기이다.
이제, 프로그램은 문자열 "excessive"를 A 버퍼에 저장한다. 한 바이트짜리 0값이 스트링의 끝임을 알리기 위해 따라온다. 스트링의 길이를 확인하지 않음으로 B의 값을 덮어쓴다.
비록 프로그래머가 B가 바뀌는 것을 전혀 의도하지 않았다 하더라도, B의 값은 문자열의 한 부분을 구성하는 숫자로 바뀌었다. 이 예제에서 ASCII를 사용하는 빅 엔디언 시스템에서 "e" "0"는 숫자 25856가 될 수 있다. B가 프로그램이 정의한 유일한 다른 변수였다면, B의 끝을 지나가는 긴 스트링을 쓰는 것은 세그멘테이션 오류, 프로세스 종료와 같은 오류를 발생시켰을 것이다.
버퍼 오버플로 이용
버퍼 오버플로 취약점을 이용하는 기술은 구조, 운영 체제, 메모리 영역에 따라 다르다. 예를 들어 힙(heap, 동적 메모리 할당에 사용됨) 을 이용하는 방법은 함수 호출 스택을 이용하는 방법과 매우 다르다.
기술적 성향을 가진 악의적 사용자가 스택 기반 버퍼 오버플로를 이용하여 프로그램을 아래와 같이 조작할 수 있다:
버퍼 오버플로 이용
트램폴라이닝(trampolining)이라 불리는 방법을 사용하면, 사용자가 지정한 데이터의 주소를 모르더라도, 레지스터에 그 주소가 저장되어 있다면, 실행 흐름을 사용자 제공 데이터로 도약하도록하는 어떤 실행코드의 주소로 귀환 주소를 덮어쓸 수 있다. 위치가 레지스터 R에 저장되어 있다면 jump R이나 call R과 같이 R에 저장되어 있는 주소로 건너뛰는 작동코드 opcode 로 사용자 제공 데이터가 실행되도록 할 수 있다. 적당한 작동코드 또는 바이트의 위치는 DLL이나 실행 파일 자체 안에서 찾을 수 있다. 그러나 작동 코드의 주소는 전형적으로는 어떠한 무효 문자도 포함할 수 없고, 이러한 작동 코드의 위치는 응용 프로그램마다, 운영 체제 버전에 따라 달라질 수 있다. 메타스플로잇 프로젝트는 그러한 적당한 작동코드의 데이터베이스로 윈도우 운영 체제에 관한 것이 나열되어 있다.
아래의 예에서 "X"는 프로그램이 실행될 때 스택에 있게 되는 데이터이다. 프로그램은 그 다음 작은 양의 저장공간만 필요한 함수 "Y"를 호출한다. 그리고 "Y"는 그 다음 많은 버퍼를 필요로 하는 "Z"를 호출한다.
버퍼 오버플로 이용
만약 함수 Z가 오버플로를 발생시키면, 그것은 함수 Y나 주 프로그램에 포함된 데이터를 덮어 쓸 수도 있다:
이것은 대부분의 시스템에서 현재의 프로세스가 호출되기 전 실행되고 있던 프로그램 부분의 위치인 반환값을 스택이 갖고 있기 때문에 특히나 심각하다. 함수가 끝날 때 임시 저장소는 스택에서 제거되고 실행은 반환 주소로 되돌아간다. 그런데 반환 주소를 버퍼 오버플로가 덮어쓰면 어떤 다른 위치를 가리킬 것이다. 처음 예제에서와 같은 버퍼 오퍼플로가 우연히 발생하는 경우 거의 틀림없이 쓸모없는 위치일 것이다. 어떠한 프로그램 명령어 위치가 아닌 이상, 프로세스는 망가질 것이다. 그리고 악의적인 공격자가 시스템 보안과 충돌할 수 있는 임의 위치로 반환 주소를 바꿀 수 있다.
버퍼 오버플로 이용
힙 데이터 영역에서 일어나는 버퍼 오버플로를 힙 오버플로라 부르며 스택 기반 오버플로와는 다른 방법으로 이용할 수 있다. 힙 상의 메모리는 동적으로 응용 프로그램에 의해 실행시간 중에 할당되고 보통 프로그램 데이터를 보관하고 있다. 이용하는 방법은 이 데이터를 특정한 방법으로 오염시켜 응용 프로그램이 연결 리스트 포인터(linked list pointer)등과 같은 내부 자료 구조를 덮어쓰게 한다. 기본적인 힙 오버플로 기술은 동적 메모리 할당 연결(malloc 상위 수준 데이터)을 덮어씀으로써 프로그램 함수 포인터를 조작한다. 마이크로소프트 JPEG GDI+ 취약점은 힙 오버플로도 컴퓨터 사용자에 위험이 될 수 있다는 예이다.
버퍼 오버플로 이용
읽히거나 실행되기 전에 버퍼를 조작하면 이용하려는 시도를 막을 수도 있다. 이러한 조작은 이용당할 위협을 완화시켜줄 수는 있지만 불가능하게 만들지는 못한다. 조작에는 대문자로 또는 소문자로 변환, 제어 부호 제거, 숫자 영문자 제거 등이 포함된다. 이러한 방지 수단을 회피하는 기술도 존재한다: 숫자 영문자 코드, 다형성 코드, 자체 수정 코드, libc 귀환 공격 등. 같은 방법을 침입 감지 시스템에 의한 피탐지를 회피하는 데도 사용할 수 있다. 어떤 경우에는, 유니코드 변환의 경우도 포함되지만, 서비스 거부만 가능한 것으로 취약점의 위협이 잘못 표현되었지만 사실은 임의 코드의 원격 실행이 가능할 수도 있다.
실세계 이용에서는 다양한 이슈를 극복해야 공격을 신뢰성 있게 수행할 수 있다. 이러한 요소에는 주소에서의 무효값 바이트, 셸 코드 위치 가변성, 환경간 상이성, 그리고 다양한 대응수단이다.
버퍼 오버플로 이용
NOP 슬라이드 기법은 가장 오래되고 가장 널리 알려진 스택 버퍼 오버플로 공격 기법이다. 버퍼의 정확한 주소를 찾는 문제를 해결하는 것으로, 표적 영역의 크기를 효과적으로 증대시킨다. 이를 위하여 훨씬 큰 영역의 스택을 NOP 기계어 코드 (컴퓨터가 이 명령을 읽으면 그 클럭 싸이클에는 아무 일도 하지 않는다)로 오염시킨다. 공격자 제공 데이터 끝, 즉 NOP 명령어 이후에 버퍼의 최상위 위치, 셸 코드가 있는 곳으로 상대적 jump 명령어를 둔다. NOP 명령어의 모음이 "NOP 슬라이드"라고 불린다. 왜냐하면 귀환 주소를 덮어 쓸 때 NOP 영역 내의 주소값 어디를 써도 결국 NOP 명령어들을 따라 "미끄러져" 최후의 상대 jump로 실제 악성 코드에 도달하기 때문이다. 이 기법은 공격자가 상대적으로 작은 크기의 셸 코드의 위치 대신 스택에서 NOP 슬라이드의 위치를 추정하면 된다.
버퍼 오버플로 이용
이 기법이 인기 있기 때문에 많은 침입 방지 시스템 업체에서 이러한 NOP 기계어 명령어 패턴을 탐색하여 사용중인 셸 코드를 검출할 것이다. 중요한 것은 NOP 슬라이드는 반드시 전통적인 NOP 기계어 코드만 담는 것은 아니며 어떤 명령이라도 셸 코드가 실행될 수 없을 만큼 기계 상태를 해치지 않으면 하드웨어로 지원되는 NOP자리에 사용할 수 있다. 결과적으로, 공격자가 NOP 슬라이드를 셸코드 실행에 사실상 지장이 없는 임의로 선택한 명령어로 채우는 관행이 널리 퍼지게 되었다.
한편, 이 방법이 어떤 공격이 성공적일 확률을 크게 높이는 반면, 문제가 없는 것은 아니다.
또 한가지 문제가 될 수 있는 경우는 효과적인 NOP-슬라이드가 할당받을 수 있는 메모리에 비해 너무 큰 경우이다. 이것이 문제가 될 수 있는 경우는 할당된 버퍼 크기가 너무 작고 현재 스택의 깊이가 너무 얕을 때(즉, 현재 스택 프레임의 끝으로부터 시작점까지의 공간이 얼마 되지 않았을 때)이다. 그 문제점에도 불구하고 NOP-슬라이드는 주어진 플랫폼, 환경, 상황에 따라 유일하게 작동하는 방법으로 아직도 중요한 기법이다.
레지스터로 건너뛰기 jump to register 기법은 NOP-슬라이드와 같은 추가 공간이나 스택 위치 오프셋을 추정하지 않아도 잘 작동한다. 전략은 복귀 포인터를 덮어써서 통제된 버퍼, 즉 셸코드를 담고 있는 레지스터의 위치로 프로그램이 건너뛰게 만드는 것이다. 예를 들어 레지스터 A가 어떤 버퍼의 시작점을 담고 있다면, 이 레지스터를 오퍼랜드(operand)로 삼은 어떠한 건너뛰기 또는 호출로 실행 흐름의 제어권을 얻을 수 있다. 실전에서는 어떤 프로그램이 의도적으로는 어떤 특정 레지스터에 저장된 주소로 건너뛰는 명령을 포함하지 않을 수도 있다. 전통적인 해법은 어떤 의도되지 않은 적당한 작동코드 opcode 사례를 프로그램 메모리 어딘가 고정된 위치에서 찾는 것이다. 예를 들면, 뜻하지 않게 i386 JMP esp 명령이 포함된 경우가 ntdll.dll 안의 DbgPrint()함수에 있었다. 이 명령의 작동 코드는 FF E4이다. 이 연속 두 바이트 패턴이 call DbgPrint 명령에서 1Byte 떨어진 곳 주소 0x7C941EED에 나타났다. 공격자가 프로그램의 귀환 주소를 이 주소로 덮어 쓰면, 프로그램이 처음에는 0x7C941EED로 건너뛰어 실행 코드 FF E4를 JMP esp 명령으로 인식하여 스택의 정상 위치로 jump, 공격자의 코드를 실행할 것이다. 이 기법이 가능하다면 취약성의 심각성이 상당히 증가한다. 이는 왜냐하면 이용이 충분히 신뢰성 있게 작동하여 공격을 자동화, 실행하면 가상적으로 성공을 보증할 수 있게 되기 때문이다. 이러한 이유로, 이 기법이 인터넷 웜에서 가장 흔히 버퍼 오버플로 취약점을 이용하기 위해 사용된다. 이 방법은 또한 셸코드의 위치를 윈도 플랫폼 상에서 덮어씌어진 귀환 주소 뒤에 위치하더라고 가능하다. 실행 코드는 주소 0x00400000에 기반하고, x86은 리틀 엔디안 구조이므로 귀환 주소의 최후 바이트는 반드시 무효값이 되고, 이것이 버퍼 복사를 마감하며 그 이후에는 아무것도 씌지 않는다. 이로 하여 셸코드의 크기는 버퍼의 크기로 제한되며, 지나친 규제가 될 수 있다. 동적 연결 라이브러리 DLL은 고위 메모리 (0x01000000 이상)에 저장되며 따라서 무효 바이트가 없는 주소를 가지므로, 이 방법은 무효 바이트 (또는 다른 허용 안되는 문자)를 덮어씌어진 복귀 주소에서 제거할 수 있다. 이런 식으로 사용되면, 이 방법은 때때로 DLL 프램폴라이닝이라고 불린다.
버퍼 오버플로 보호 대응 수단
다양한 기법이 버퍼 오버플로를 감지 또는 방지하기 위하여, 다양한 대가를 지불하며 사용되어 왔다. 가장 신뢰성 있는 버퍼 오버플로를 회피 또는 방지하기 위한 방법은 언어 수준에서 자동 보호를 사용하는 것이다. 그러나 이러한 종류의 보호는 기존 코드에 적용할 수 없고, 때때로 기술적, 상업적, 또는 문화적 제한으로 취약한 언어를 요구한다.
프로그래밍 언어 선택은 버퍼 오버플로 발생에 깊이 있는 영향을 미칠 수 있다. 2008년 기준으로, C와 그로부터 발전된 C++는 가장 인기 있는 언어들에 포함되며, 거대한 양의 소프트웨어가 이러한 언어로 작성되었다. C와 C++는 메모리상 어떤 부분에서도 데이터 접근과 덮어쓰기에 대한 내장 보호 기능이 없다. 더 구체적으로, 데이터가 어떤 배열 (버퍼의 구현)에 씌어지는 데이터가 그 배열의 범위 안에 씌어지는지 검사하지 않는다. 그러나 표준 C++ 라이브러리는 데이터를 안전히 저장하는 많은 방법을 제공하고, C언어에서 버퍼 오버플로를 회피하기 위한 기술도 존재한다. 장기간 작동시키며 안정성을 유지해야 하는 프로그램을 작성해야 한다면 보다 데이터 타입과 오버플로 검사가 엄격한 C#과 자바를 사용할 수 있다.
버퍼 오버플로 보호 대응 수단
많은 다른 프로그래밍 언어는 실행시간 검사를 제공하고, 어떤 경우에는 심지어 컴파일 시 검사하여 C 또는 C++가 데이터를 덮어쓰고 계속하여 더 많은 명령을 실행하여 잘못된 결과가 프로그램을 깨뜨릴 수도 있는 경우 경고 또는 예외를 제기할 수도 있다. 그러한 언어의 예는 에이다, 리스프, 모듈라-2, 스몰토크, OCaml 그리고 C에서 발전된 사이클론과 D이다. 자바와 닷넷 바이트코드 환경도 경계 검사를 모든 배열에 대하여 요구한다. 거의 모든 인터프리터 언어는 잘 정의된 에러 조건에 신호를 보냄으로써 버퍼 오버플로에 대항 보호할 것이다. 어떤 언어가 충분한 형 정보(type information)를 제공하면 때때로 가능케 할것인지 불가능하게 할 것인지 정할 수 있게 해 준다. 정적 코드 분석은 다수의 동적 경계 검사를 제거할 수 있지만, 잘못 구현되거나 부적절한 케이스(case)는 심각하게 성능을 저하시킬 수 있다. 소프트웨어 공학자는 반드시 조심스럽게 안전성과 성능 비용 사이의 조율을 고려하여 언어와 컴파일러 설정을 결정하여야 한다.
버퍼 오버플로 보호 대응 수단
버퍼 오버플로의 문제는 C와 C++언어에서는 일반적이다. 왜냐하면 이들 언어가 데이터 형을 보관 장소로서 버퍼의 저수준 표현상 상세를 노출시키기 때문이다. 버퍼 오버플로는 반드시 따라서 버퍼 관리 코드안에서의 높은 수준의 정확성을 유지함으로써 회피되어야 한다. 오래전부터 표준 라이브러리 함수 중 경계를 검사하지 않는 함수의 사용을 피할 것이 권고되어 왔다: gets, scanf, strcpy 등. 모리스 웜은 핑거 데몬 안에서 호출되는 gets 함수를 이용하였다.
버퍼 오버플로 보호 대응 수단
잘 씌어지고 검사된 추상 데이터형 라이브러리는 경계 검사를 포함한 버퍼 관리를 중앙집중화하고 자동적으로 실시하여 버퍼 오버플로 발생과 충격을 줄일 수 있다. 버퍼 오버플로가 일상적으로 일어나는 언어의 두가지 주요한 기본 데이터 형은 문자열과 배열이다; 따라서 버퍼 오버플로를 이러한 데이터 형에서 방지하는 라이브러리는 필요 영역 가운데 방대한 대다수를 담당해 줄 수 있다. 여전히 이러한 안전한 라이브러리를 사용하지 못한다면 버퍼 오버플로와 다른 취약점을 낳을 것이다; 자연스럽게 라이브러러 자체의 어떤 버그도 잠재적인 취약점이 된다. "안전한" 라이브러리 구현은 "개선된 문자열 라이브러리", Vstr, 어원을 포함한다. 오픈 BSD 운영체제의 C 라이브러리는 strlcpy와 strlcat 함수를 제공하지만 이들은 전 안전 라이브러리 구현보다 더 제한되어 있다.
버퍼 오버플로 보호 대응 수단
2006년 9월 C 언어 표준 위원회 기술 보고서 24731이 공개되었다; 이는 표준 C 라이브러리의 문자열과 입출력 함수들에 기반하였으나 버퍼 크기 매개 변수를 추가로 가진 함수들을 명세하였다. 그러나 이런 함수들의 버퍼 오버플로 방지 효력은 논란의 여지가 있다. 프로그래머가 일부러 함수 호출 마다 개입하여야 하는데 이는 더 오래된 표준 라이브러리 함수의 버퍼 오버플로를 방지하게 만드는 것과 등가의 일이다.
가능한 더 안전한 기능을 제공하는 함수를 사용하는 것도 방법이다. 예를 들어 문자열의 길이를 구하는 C 함수 strlen, wcslen 함수는 NULL 문자를 만날 때까지 계속 다음 메모리를 참조해 나가는 메커니즘으로 되어 있어서 원래의 문자열 끝에 NULL이 없으면 최악의 경우 메모리 영역 끝을 넘어서까지 메모리를 참조하려 시도할 것이다. 이 때에는 좀 더 개선된 함수 strlen s나 wcslen s를 사용하여 참조할 최대 메모리를 제한할 수 있다. 이 외에 기존의 문자열 함수 뒤에 _s가 붙은 이름의 함수를 사용하면 버퍼 오버플로 문제를 개선할 수 있다.
버퍼 오버플로 보호 대응 수단
버퍼 오버플로 보호는 가장 일반적인 버퍼 오버플로를 검출하기 위해 사용되며 함수가 귀환할 때 스택이 변경되었는지 검사한다. 변경되었다면 프로그램이 세그멘테이션 오류를 발생 시키며 중단된다. 그러한 시스템의 세가지 예가 gcc 패치인 립세이프 LibSafe, 스택 가드, 프로폴리스이다. 마이크로소프트의 데이터 실행 방지 모드는 명백히 SEH 예외 처리기를 가리키는 포인터를 덮어쓰기로부터 보호한다. 더 강력한 스택 보호는 스택을 두가지로 나눔으로써 가능하다: 하나는 데이터용이고 다른 하나를 함수 귀환에 사용하는 것이다. 이러한 구분은 포스 프로그래밍 언어에 비록 안전을 위한 기능은 아니지만 채택되어 있다. 어쨌든, 이는 버퍼 오버플로에 관한 완벽한 해결책은 아닌 것이, 귀환 주소가 아닌 민감한 데이터는 여전히 덮어씌어질 가능성이 있다.
버퍼 오버플로 보호 대응 수단
버퍼 오버플로는 포인터를 조작함으로써 (저장되어 있는 주소를 포함하여) 작동한다. 포인트 가드는 컴파일러 확장으로 제안되었는데, 공격자가 신뢰성 있게 포인터와 주소를 조작하는 것을 방지한다. 접근 방법은 컴파일러가 추가 코드를 삽입하여 자동적으로 포인터를 사용 전후에 XOR-인코딩하도록 하는 것이다. 공격자가 (이론적으로는) 어떤 값이 포인터를 인코드/디코드할 때 사용할지 알지 못하기 때문에 어떤 값으로 덮어 써야 원하는 효과를 거둘 수 있을지 알기 힘들게 된다. 포인트가드가 배포된 적은 없지만 마이크로소프트에서 비슷한 접근 방법을 구현하여 윈도우 XP SP2와 윈도 서버 2003 SP1 이후에 적용하였다. 포인터 보호를 자동 기능으로 구현하지는 않았고, API를 추가하여 프로그래머의 재량에 따라 호출하여 사용하도록 하였다. XOR이 선형이므로, 공격자가 암호화된 포인터를 조작하여 어떤 주소의 하위 바이트만 덮어쓸 수 있다. 이렇게 하면 공격자가 여러번 시도하거나 복수의 위치 (예를 들어 NOP 슬라이드 안의 어떤 위치)에 대해 시도함으로써 공격이 성공할 수 있다. 마이크로소프트는 임의로 암호화 방안을 변경함으로써 이 약점을 보완, 부분적으로만 덮어쓰기가 가능하게 하였다.
버퍼 오버플로 보호 대응 수단
실행 공간 보호는 버퍼 오버플로를 방지하기 위한 접근 방법으로 스택이나 힙 상의 코드가 실행되는 것을 막는다. 공격자는 버퍼 오버플로를 이용하여 임의의 코드를 프로그램의 메모리에 삽입할 수 있지만, 실행 영역 보호가 있다면, 그 코드를 실행하고자 하는 어떠한 시도도 예외를 발생시킬 것이다. 어떤 CPU는 NX (No eXecute) 또는 XD (eXecute Disabled)비트 라는 기능을 지원하는데 소프트웨어와 연계하여 데이터의 페이지 (즉 스택이나 힙을 담고 있는)를 읽고 쓰기는 가능하나 실행 불가로 표시할 수 있다. 어떤 유닉스 운영 체제는 (예를 들어 오픈 BSD, OS X) 은 실행가능한 공간 보호와 함께 출시되었다. (예: W^X) 옵션 패키지에는 다음이 포함될 수 있다:
새로운 마이크로소프트 변종도 실행 공간 보호를 지원하며 데이터 실행 방지라고 부른다. 상용 추가 기능은 다음과 같다:
실행 공간 보호로 libc로 귀환 공격 또는 공격자 코드 실행에 의지하지 않는 공격을 방지한다고 보증할 수는 없다.
주소 공간 배치 난수화 (Address space layout randomization, ASLR)는 컴퓨터 보안 기능으로 중요 데이터 영역, 예를 들어 실행 코드의 기반 주소, 라이브러리, 힙, 스택 주소 등을 임의로 프로세서의 주소 공간에 배치하는 것이다. 함수와 변수를 찾을 수 있는 가상 메모리 주소의 난수화로 버퍼 오버플로 이용이 더 어려워지지만 불가능한 것은 아니다. 공격자가 이용 시도를 각각의 시스템에 따라 다르게 하도록 강요하므로 인터넷 웜 방어에 더 유용하다. 비슷하지만 덜 효과적인 방법은 프로세스와 라이브러리를 가상 주소 공간에 리베이스하는 것이다.
심층 패킷 조사로 네트워크 경계에서 아주 간단한 버퍼 오버플로 원격 시도를 공격 고유 신호과 경험적 방법으로 검출할 수 있다. 알려진 공격 고유 신호 또는 긴 NOP 명령이 검출되면 패킷을 막을 수 있으며, 공격 패킷 내용으 조금 달라도 사용할 수 있다. 패킷 스캐닝은 효과적이지 못한데, 그 까닭은 알려진 공격만 막을 수 있고 NOP 슬라이드는 다양한 방법으로 암호화 할 수 있기 때문이다. 공격자들은 경험론적 패킷 스캐너와 침입 감지 시스템의 탐지를 회피하기 위하여 영숫자, 탈바꿈, 자기 수정 셸코드를 사용하기 시작하였다.
버퍼 오버플로 이용의 역사
버퍼 오버플로는 1972년 컴퓨터 보안 기술 기획 연구에서 기법을 소개하였을 때부터 이해되었던 개념이다. "이 기능을 수행하는 코드는 출처와 목적지 주소를 적절히 검사하지 않으므로, 사용자가 모니터의 일부를 덮어쓰도록 허용한다. 이는 코드를 모니터에 삽입하여 제어권을 획득하는 데 사용될 수 있다." 오늘날 모니터는 커널이라고 불릴 것이다.
버퍼 오버플로 이용의 역사
1980년대 개인용 컴퓨터의 확산으로 이 기법에 대해 아는 사람의 수가 증가하였다. 코모도어 PET 상에서 예를 들어 흔히 두 번째 테이프 버퍼를 사용하여 어셈블리 언어 루틴을 저장하였다. 어떤 프로그래머들은 최대 32KB인 컴퓨터의 주기억장소 공간에서 몇바이트를 절약하기 위해 베이직 언어의 번거로운 POKE 명령 사용 대신 프린트 버퍼의 시작점을 테이프 버퍼로 변경하여 6502 어셈블리 언어 코드(이상해 보이는 글자로 이루어진)를 직접 원하는 곳으로 출력하였다. 실제로는 프린터 버퍼가 테이프 버퍼 보다 길었기 때문에, 베이직 문자열이 쉽게 1024 바이트를 넘어갔고, PET상의 마이크로소프트 베이직 인터프리터와 간섭하였다. 초기 맥, 코모도어, 아타리등 초기 개인용 컴퓨터 부트 이미지 로더와 95, 98까지의 마이크로소프트 윈도우 운영 체제는 버퍼 보호에 부적절하였고 많은 프로그래머들이 버퍼 오버플로에 대해 알게 되었다.