컴퓨터시스템 01: 비트와 바이트, 그리고 정수

글에 들어가기 앞서…

이 포스팅은 서울시립대학교 인공지능학과 백형부 교수님의 ‘컴퓨터시스템’ 강좌의 중간고사 이전 범위 수업 내용에 대한 정리를 담고 있습니다.

수업 자료 출처: Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, 3rd Edition

Bits, Bytes, and Integers

비트로 표현되는 정보

컴퓨터 내부에서 모든 정보는 기본적으로 비트(bit), 즉 0 또는 1로 표현됩니다. 그러나 컴퓨터가 정보를 실제로 처리하는 최소 단위는 비트가 아니라 바이트(byte)입니다. 이는 컴퓨터의 인스트럭션, 즉 명령어가 바이트 단위로 구성되어 있기 때문입니다.

컴퓨터의 운영체제는 보통 비트 단위로 구분합니다. 이는 운영체제가 처리할 수 있는 최대 인스트럭션 길이와 직접적으로 관련이 있습니다. 예를 들어, 32비트 운영체제는 최대 32비트, 즉 4바이트 길이의 인스트럭션을 처리할 수 있습니다.

C Data Type	Typical 32-bit	Typical 64-bit
char	1	1
short	2	2
int	4	4
long	4	8
float	4	4
double	8	8
pointer	4	8

C언어 경험이 있는 분이라면 잘 아실 것입니다만, 같은 변수명을 사용하더라도 포인터형 변수가 차지하는 메모리의 크기는 다를 수 있습니다. 이러한 차이는 포인터 변수가 운영체제와 동일한 비트 크기를 사용한다는 점에서 비롯됩니다. 즉, 컴퓨터가 변수의 주소를 표현할 때 해당 운영체제의 비트 수만큼의 크기를 사용합니다.

Operation

Bit-Level Operations

위의 네 연산자(&, |, ^, ~)는 비트 단위에서 연산을 수행합니다. 파이썬과는 달리, 이들 연산자는 변수의 전체적인 참 또는 거짓 여부를 판단하는 것이 아니라, 변수가 이진수로 표현될 때 각 비트별로 연산을 수행합니다. 실제로 컴퓨터 내부에서는 모든 데이터가 이진수로 표현되기 때문에, C언어에서 이러한 비트 단위 연산자들은 각 비트에 대해 개별적으로 참 또는 거짓 연산을 진행합니다.

Logical Operations

파이썬에서 사용되는 것과 유사하게, 변수의 전체적인 참 또는 거짓을 평가하는 연산자들도 존재합니다. C언어에서는 && 연산자가 변수 전체에 대한 AND 연산을, || 연산자가 OR 연산을, 그리고 ! 연산자가 negation(부정) 연산을 수행합니다. 중요한 점은, 이러한 연산들에서는 조기 종료(Early termination)가 가능하다는 것입니다. 즉, 연산의 결과가 이미 결정된 경우, 남은 연산을 수행하지 않고 빠져나올 수 있습니다. 예를 들어, && 연산에서 첫 번째 조건이 거짓인 경우, 두 번째 조건은 평가되지 않습니다. 마찬가지로 || 연산에서 첫 번째 조건이 참인 경우, 두 번째 조건은 평가되지 않습니다. 이는 연산의 효율성을 높여주는 중요한 특징입니다.

변수 전체에 대한 참 또는 거짓을 판단할 때, 0은 거짓(False)으로, 0이 아닌 모든 값은 참(True)으로 간주됩니다. 이는 파이썬에서 사용되는 참과 거짓의 개념과 일치합니다.

Shift Operations

시프트(Shift) 연산은 비트를 순차적으로 이동시키는 매우 기본적인 연산입니다. 만약 왼쪽으로 시프트(Left Shift)를 수행한다면, 모든 비트가 왼쪽 방향으로 이동하며, 오른쪽으로 시프트(Right Shift)를 한다면 비트들이 오른쪽으로 이동합니다.

이러한 비트의 이동 과정은 어떤 의미를 가질까요? 실질적으로 시프트 연산은 숫자의 크기를 조절하는 데 사용됩니다. 왼쪽으로 한 번 시프트하는 것은 숫자를 2배로 증가시키는 것과 동일하며, 오른쪽으로 한 번 시프트하는 것은 숫자를 2로 나누는 것과 같습니다. 이러한 연산은 컴퓨터 내부에서 매우 효율적으로 진행됩니다. 결과적으로, 많은 곱셈 연산들이 시프트 연산으로 대체되어 수행됩니다.

시프트 연산을 수행할 때, 비트를 이동시키고 남은 빈 공간은 0으로 채워집니다. 반면, 변수의 표현 범위를 벗어나는 비트들은 버려집니다. 왼쪽 시프트에서는 이 과정이 별다른 문제를 일으키지 않지만, 오른쪽 시프트의 경우 음수에 대해 문제가 발생할 수 있습니다. 음수는 가장 앞 비트(최상위 비트)가 1로 표현됩니다. 음수를 오른쪽으로 시프트하는 것은 본질적으로 숫자를 2로 나누는 것이지만, 새롭게 채워진 0 비트로 인해 결과가 달라질 수 있습니다. 이 문제를 해결하기 위해 산술 시프트(Arithmetic Shift)가 사용됩니다. 산술 시프트는 비트를 이동시킨 후 빈 공간을 가장 앞 비트와 동일한 값으로 채웁니다. 이 방식을 통해 음수의 오른쪽 시프트 연산 결과가 나누기 2와 같은 의미를 유지하도록 합니다. 주의할 점은, 산술 시프트는 오른쪽 시프트에만 존재하는 개념이라는 사실입니다.

정수 표현

\[X = [x_0, x_1, x_2, ..., x_{w-1}]\] \[B2U(X) = \sum_{i=0}^{w-1}x_i\times 2^i\] \[B2T(X) = -x_{w-1} \times 2^{w-1} + \sum_{i=0}^{w-2}x_i\times 2^i\]

정수를 비트 단위에서 표현하는 방법에는 크게 두 가지 유형이 있습니다. 첫 번째는 부호가 없는 ‘Unsigned’ 변수형입니다. 이 유형에서는 정수 값이 이진수로 직접 표현되며, 각 비트는 2의 거듭제곱 값을 가지게 됩니다. 가장 낮은 자리(오른쪽 끝)부터 시작해 자리수가 올라갈수록 해당 비트의 값은 2의 거듭제곱만큼 커지게 됩니다. 이 방식은 순수하게 양의 정수만을 표현하는데 사용됩니다.

두 번째 유형은 부호가 있는 ‘Signed’ 변수형입니다. 이 유형에서 음수의 표현은 조금 더 복잡한데, 이는 ‘2의 보수’ 방식을 사용하여 이루어집니다. 2의 보수는 가장 앞자리 비트를 음수로 계산하고, 나머지 비트에는 양수의 2의 거듭제곱 값을 곱하는 방식으로 작동합니다. 이 디자인에서 가장 앞자리가 음수를 나타내기 때문에 음수 범위는 양수 범위보다 하나 더 많은 값을 포함합니다. 예를 들어, 8비트 정수에서는 +127까지의 양수와 -128까지의 음수를 표현할 수 있습니다. 이렇게 2의 보수 방식은 음수 값을 효율적으로 표현하고 계산을 용이하게 하는데 중요한 역할을 합니다.

Signed, Unsigned 변환

앞서 언급했듯이, 컴퓨터 시스템에서 정수를 표현하는 방식에는 주로 부호 있는 정수(Signed)와 부호 없는 정수(Unsigned) 두 가지가 있습니다. 이 두 표현 방식 사이에서는 같은 비트 패턴이라도 해석하는 값이 다르게 됩니다. 이러한 차이점을 이해하는 것은 프로그래밍에서 중요한데, 특히 T2U(Type to Unsigned)와 U2T(Unsigned to Type) 연산을 다룰 때 혼동을 피하기 위해 필수적입니다.

“T2U” 연산은 부호 있는 정수 타입의 변수가 가지고 있는 비트 패턴을 부호 없는 정수 도메인에서 어떤 숫자로 해석되는지를 묻는 연산입니다. 중요한 점은, 이 연산이 비트 패턴 자체를 변환하는 것이 아니라, 동일한 비트 패턴을 다른 도메인(부호 없는 정수)에서 해석하는 방식에 대한 질문이라는 것입니다.

예를 들어, 4비트로 표현된 정수에서 “-7”은 부호 있는 정수로서 “1001”로 표현됩니다. 이 비트 패턴을 부호 없는 정수 도메인에서 해석하면, “9”로 해석됩니다. 즉, T2U 연산은 이러한 변환에서 “1001”이라는 비트 패턴이 부호 없는 정수 도메인에서 “9”로 해석된다는 사실을 묻는 것입니다. 이 과정에서 ‘동일한 비트 패턴이 유지된다‘는 표현은, 변환 과정에서 비트 패턴 자체에 변화가 없음을 강조하는 것입니다.

부호 없는 정수(Unsigned Integer) 도메인에서 숫자의 부호를 바꾸기 위한 방법 중 하나는 비트 단위 부정(Bit-wise Negation) 연산을 수행한 후 1을 더하는 것입니다. 이 방식은 컴퓨터 과학에서 ‘2의 보수(Two’s Complement)’라고 알려져 있으며, 정수의 부호를 변경하는 표준적인 방법입니다. 이러한 설계의 근본적인 이유는, 절대값이 동일하지만 부호가 반대인 두 수를 더했을 때 결과값으로 0을 얻기를 원하기 때문입니다.

비트 단위 부정 연산을 통해 모든 비트가 반전되면, 원래의 수에 대해 비트별로 보았을 때 1은 0이 되고, 0은 1이 됩니다. 이 상태에서 1을 더하게 되면, 가장 낮은 자리에서부터 올림이 발생하게 되어 모든 자리가 0이 되고, 맨 앞에 새로운 1이 추가되는 형태의 결과가 나타나게 됩니다. 그러나 이 새로운 1은 부호 없는 정수 도메인에서는 고려되지 않으므로, 실질적으로는 모든 비트가 0인 상태, 즉 숫자 0을 얻게 됩니다.

예를 들어, 4비트 부호 없는 정수에서 숫자 1을 비트 단위 부정 연산을 통해 변환하면 1110이 되고, 여기에 1을 더하면 1111에서 0000이 됩니다. 이처럼, 2의 보수를 사용하면 절대값이 같으나 부호가 반대인 두 수를 더했을 때 자연스럽게 0이 되는 특성 덕분에, 컴퓨터는 덧셈과 뺄셈을 보다 효율적으로 처리할 수 있습니다. 이는 컴퓨터 시스템에서 정수의 표현 및 연산을 설계하는 데 있어 중요한 원리 중 하나입니다.

C언어 예시

4258405349U;
4258405349;
0U;
0;

위 예시는 C언어에서 부호 없는 정수 상수를 사용하는 방법입니다. 기본적으로 정수 상수는 부호가 존재하는 정수로 인식됩니다. 만약에 입력한 상수가 부호 없는 정수 도메인으로 인식되길 원한다면, 상수 뒤에 U를 붙여야 합니다.

프로그래밍을 할 때, 특히 상수들이 하나의 표현식 내에서 비교될 때 주의해야 할 사항이 있습니다. 만약 두 상수 중 하나라도 ‘U’를 명시적으로 포함하고 있다면, 이들 상수의 비교는 부호 없는(unsigned) 도메인에서 이루어집니다. 이는 비교 연산이 부호 없는 정수에 대해 수행됨을 의미하며, 이 경우 비교의 결과가 예상과 다를 수 있습니다.

반면에, 한 상수 앞에 ‘(int)’와 같이 명시적으로 타입을 지정하여 부호 있는(signed) 정수로 변환하고, 그 상수가 ‘U’를 포함하고 있더라도, 이렇게 변환된 상수는 부호 있는 도메인에서 비교됩니다. 즉, ‘(int)’를 사용하여 명시적으로 부호 있는 타입으로 변환하면, 상수 뒤에 붙은 ‘U’의 영향이 상쇄되어, 비교는 부호 있는 도메인에서 수행됩니다.

int tx, ty;
unsigned ux, uy;
tx = (int) ux;
uy = (unsigned) ty;

위 예시는 C 언어에서 부호 없는 정수 도메인과, 부호가 존재하는 정수 도메인 사이의 변환을 수행하는 코드입니다.

Sign Extension

변수의 바이트 수를 확장해야 하는 상황은 프로그래밍을 하면서 자주 마주치게 됩니다. 예를 들어, 2바이트로 표현되는 정수형 변수를 4바이트 길이로 확장해야 할 때가 있습니다. 이 과정에서 가장 직관적이고 단순한 방법은 확장하고자 하는 바이트 자리에 0을 추가하는 것입니다. 이 방식은 부호 없는(unsigned) 정수에 대해서는 잘 작동합니다.

하지만, 부호 있는(signed) 정수, 특히 음수를 다룰 때에는 단순히 0을 추가하는 방식으로는 원래의 값과 동일한 값을 유지할 수 없습니다. 이 문제의 해결책은 변수 확장 시 앞에 추가되는 비트를 원래 변수의 최상위 비트(sign bit)와 동일하게 만드는 것입니다. 이 방법은 ‘사인 익스텐션(Sign Extension)’이라고 불리며, 부호 있는 정수의 값을 확장할 때 그 의미를 유지하도록 해줍니다.

이러한 사인 익스텐션의 원리는 2의 보수법과 밀접하게 연관되어 있습니다. 2의 보수법은 음수를 표현하는 표준적인 방법으로, 음수의 절대값을 이진수로 표현한 뒤, 모든 비트를 반전시키고 1을 더하여 얻습니다. 이 방식에서는 최상위 비트가 부호 비트로 사용되며, 음수는 최상위 비트가 1로 설정됩니다. 따라서, 사인 익스텐션을 통해 변수를 확장하면, 부호 비트를 유지하면서도 원래의 수치 값을 정확히 표현할 수 있습니다.

이처럼, 변수의 바이트 수를 확장할 때 사인 익스텐션을 사용하는 것은 단순한 방법이 아니라, 컴퓨터가 부호 있는 정수를 표현하고 연산을 수행하는 근본적인 설계 원리에 기반한 것입니다.

Addition

비트로 표현되는 정수 간의 덧셈에서 주목할 만한 특징 중 하나는, 캐리(carry)를 고려하지 않는다는 점입니다. 이는 덧셈 연산에서 변수의 표현 범위를 넘어설 때 발생하는 현상, 즉 오버플로우(overflow) 때문입니다. 산술적으로 설명하자면, 예를 들어 4비트로 표현되는 부호 없는(unsigned) 정수형 변수가 있다고 가정할 때, 두 변수의 합이 2의 4승, 즉 16을 초과하게 되면, 결과값은 16으로 나눈 나머지 값을 가지게 됩니다. 이는 합산 결과가 해당 변수가 표현할 수 있는 최대 범위를 넘어섰을 때, 초과분(carry)을 고려하지 않고 버려지는 것을 의미합니다.

이러한 오버플로우 현상은 부호 없는 정수형(unsigned integer)에서만 발생하는 것이 아니라, 부호 있는(signed) 정수형에서도 마찬가지로 발생합니다. 물론 부호 있는 정수에서의 오버플로우는 범위가 다르게 나타나지만, 근본적인 원리는 동일합니다. 즉, 덧셈 결과가 해당 정수형 변수가 표현할 수 있는 범위를 넘어서는 경우, 이를 고려하지 않고 초과분을 버리게 되는 것입니다. 이러한 오버플로우는 컴퓨터가 한정된 비트 수로 숫자를 표현하고 연산을 수행하는 과정에서 불가피하게 발생하는 현상입니다.

예시 01(Unsigned 변수를 쓸 때의 주의사항)

unsigned i;
for (i = cnt-2; i >= 0; i--)
  a[i] += a[i+1];

이 코드는 예상과 다르게 무한 루프에 빠지게 됩니다. 그 이유는 for 루프의 종료 조건이 i가 음수가 되어야 종료되는 것으로 설정되어 있지만, i는 ‘unsigned’ 즉, 부호 없는 정수형 변수로 선언되어 있어 음수 값을 가질 수 없기 때문입니다. 따라서 i가 0이 될 때까지 감소한 후, 0에서 1을 빼면 부호 없는 정수의 최대 값으로 오버플로우되어, 루프의 종료 조건을 만족시킬 수 없게 됩니다.

이 문제를 해결하기 위해서는 루프가 i가 0이 될 때 종료되도록 조건을 변경하는 것이 한 가지 방법입니다. 또는 더 직관적으로, i가 0보다 클 동안 루프를 실행하도록 조건을 명시적으로 변경할 수도 있겠습니다.

메모리에서의 표현 방법, 포인터, 문자열

앞서 언급했듯이, 메모리 주소 체계는 바이트 단위로 구성되어 있으며, 메모리는 하나의 거대한 바이트 배열로 생각할 수 있습니다. 이때 각 바이트는 고유한 인덱스, 즉 주소를 가지고 있습니다. 주소의 길이는 운영체제의 아키텍처에 의해 결정됩니다. 32비트 운영체제에서는 주소 길이가 32비트이며, 64비트 운영체제에서는 주소 길이가 64비트가 됩니다. 이러한 차이로 인해, 64비트 운영체제는 훨씬 더 많은 메모리에 주소를 할당할 수 있으며, 그 결과로 더 큰 메모리 영역을 활용할 수 있습니다. 컴퓨터가 메모리의 특정 바이트를 사용하기 위해서는 그 바이트에 주소가 할당되어 있어야 합니다.

https://en.wikipedia.org/wiki/Physical_address#/media/File:Virtual_address_space_and_physical_address_space_relationship.svg

여기서 우리가 주로 다룰 ‘주소’ 개념은 private address, 즉 개인 주소(논리 주소 또는 가상 주소)입니다. private address는 실제 물리적인 메모리 주소와는 독립적으로 정의된 추상적인 공간을 의미합니다. 이러한 추상화를 통해, 우리는 프로세스의 명령어들이 메모리에 어떻게 할당되는지를 보다 쉽게 이해할 수 있습니다. 실제 물리적인 메모리 주소에 대한 할당 작업은 운영체제의 책임하에 이루어집니다.

Byte-Ordering

앞서 우리는 다양한 데이터 타입에 따라 필요한 바이트의 수가 다르다는 것을 살펴보았습니다. 대부분의 데이터 타입은 두 개 이상의 바이트를 사용합니다. 이게 큰 문제가 되지 않을 것 같아 보입니다. 데이터를 여러 바이트에 걸쳐 저장한다 하더라도, 이들을 순차적으로 배열하기만 하면 되니까요. 이런 방식을 ‘Big Endian’ 방식이라고 부릅니다. 그러나 주목해야 할 부분은 바로 바이트를 저장하는 또 다른 방식인 ‘Little Endian’입니다.

Big Endian 방식에서는 가장 중요한 바이트(가장 큰 자릿수를 나타내는 바이트)를 메모리의 가장 낮은 주소에 배치합니다. 반면, Little Endian 방식에서는 가장 중요하지 않은 바이트(가장 작은 자릿수를 나타내는 바이트)를 메모리의 가장 낮은 주소에 배치합니다. 이 두 방식은 데이터를 메모리에 저장하고 읽는 방법에 있어 근본적인 차이를 가지며, 이는 컴퓨터 아키텍처에 따라 달라질 수 있습니다.

Little Endian 방식을 사용하는 주된 이유는 연산의 효율성에 있습니다. 이 방식에서는 최하위 바이트(LSB)부터 연산을 시작하기 때문에, 계산 과정이 더 효율적이 됩니다. 실제로 대부분의 컴퓨터 아키텍처는 이 Little Endian 방식을 채택하고 있습니다. 반면에, Big Endian 방식도 여전히 사용되는데, 이는 데이터를 인간이 이해하기에 더 직관적인 형식으로 표현하기 때문입니다. 또한 인터넷 상의 여러 프로토콜은 Big Endian을 기반으로 하고 있어, 이 방식이 특정 상황에서는 더 편리할 수 있습니다.

그러나 Little Endian과 Big Endian을 사용하는 아키텍처 간에 데이터를 교환할 때는 이 두 방식 사이의 차이를 고려하여 데이터를 적절히 변환할 필요가 있습니다. 이는 서로 다른 아키텍처 간의 호환성을 보장하고, 데이터가 올바르게 해석되도록 하는 데 중요합니다. 따라서, 두 바이트 순서 간의 변환 방법을 이해하고 적용할 수 있는 능력은 다양한 컴퓨팅 환경에서 효과적으로 작업을 수행하기 위해 필수적입니다.

포인터형 변수에 저장되는 주소값 역시 예외가 아닙니다.

실제로 Little Endian과 Big Endian 사이의 변환 방법은 복잡하지 않습니다. 핵심은 데이터를 저장하는 바이트 순서를 반대로 뒤집는 것에 있습니다. 즉, 데이터를 저장할 때 적용했던 순서를 역순으로 조정함으로써, 한 방식에서 다른 방식으로의 전환을 달성할 수 있습니다. 이 간단한 원리를 통해 서로 다른 아키텍처를 사용하는 시스템 간의 호환성을 보장할 수 있습니다.

이 과정을 통해, 어떠한 아키텍처에서 생성된 데이터도 다른 아키텍처에서 올바르게 해석하고 사용할 수 있게 됩니다. 따라서, Little Endian과 Big Endian 방식 사이의 차이는 데이터를 교환하고 처리하는 과정에 있어 중요한 고려사항이지만, 이를 쉽게 극복할 수 있는 방법이 있음을 알 수 있습니다.

C언어 예시

typedef unsigned char *pointer;

void show_bytes(pointer start, size_t len){
  size_t i;
  for (i = 0; i < len; i++)
    printf(”%p\t0x%.2x\n",start+i, start[i]);
  printf("\n");
}

이 C 코드는 실제로 변수가 Little Endian 방식으로 저장되어 있는지 확인하는 데 사용됩니다. 현재 대부분의 CPU가 X86 아키텍처를 기반으로 하고 있기 때문에, 실행 결과를 통해 변수가 저장될 때 바이트 순서가 역순으로 되어 있는 것을 확인할 수 있을 것입니다.

Representing Strings

문자열은 여러 개의 바이트를 사용하지만, 바이트 순서(Byte-ordering)에 대해 걱정할 필요가 없습니다. 이는 문자열을 구성하는 각 바이트가 독립적으로 하나의 문자를 나타내기 때문입니다. 정수와 같은 경우, 여러 바이트가 모여 하나의 큰 값을 형성하기 때문에 바이트의 순서가 중요합니다. 하지만 문자열에서는 각 바이트가 개별 문자를 의미하므로, 문자열을 그대로 순서대로 저장하면 됩니다.

Code Security Example

/* Kernel memory region holding user-accessible data */
#define KSIZE 1024
char kbuf[KSIZE];

/* Copy at most maxlen bytes from kernel region to user buffer */
int copy_from_kernel(void *user_dest, int maxlen) {
    /* Byte count len is minimum of buffer size and maxlen */
    int len = KSIZE < maxlen ? KSIZE : maxlen;
    memcpy(user_dest, kbuf, len);
    return len;
}

#define MSIZE 528

void getstuff() {
    char mybuf[MSIZE];
    copy_from_kernel(mybuf, -MSIZE);
    . . .
}

위 코드는 C 언어를 사용하여, 일반적으로 접근 가능하지 않은 커널 메모리 영역에서 데이터를 가져오는 방법을 보여주는 유명한 예시입니다. 이 예시는 변수형을 통해 보안 취약점을 이용하는 방법을 보여줍니다.

첫 번째 코드 블록에서 copy_from_kernel 함수는 커널 메모리 영역인 kbuf에서 사용자가 지정한 버퍼인 user_dest로 데이터를 복사합니다. 복사되는 최대 바이트 수는 maxlen에 의해 결정되며, KSIZE(커널 버퍼의 크기)와 maxlen 중 더 작은 값으로 설정됩니다.

두 번째 코드 블록에서 getstuff 함수는 MSIZE 크기의 로컬 버퍼 mybuf를 선언하고, copy_from_kernel 함수를 호출하여 -MSIZE를 maxlen 파라미터로 전달합니다. 여기서 -MSIZE는 음수 값이고, 이는 함수 내에서 maxlen을 처리할 때 발생하는 문제의 핵심입니다.

memcpy 함수는 입력 값이 음수일지라도 이를 부호 없는 정수(unsigned)로 해석합니다. 따라서, copy_from_kernel 함수 내 조건문에서 음수인 maxlen을 검사하여 허용된 범위보다 작다고 판단하고, 이를 memcpy에 전달하면, memcpy는 이를 부호 없는 정수로 해석하여 실제로 허용되어야 할 크기를 초과하는 막대한 양의 데이터를 복사하여 사용자에게 전달하게 됩니다.

이러한 방식은 커널 메모리에서 사용자 버퍼로의 데이터 복사 과정에서 발생할 수 있는 보안 취약점을 명확히 보여줍니다.

Mathmatical Properties

Modular Addition Forms an Abelian Group

모듈러 덧셈은 특정 수를 기준으로 덧셈을 수행하되 결과가 n이상이 되면 n으로 나눈 나머지를 결과로 취하는 연산 방식입니다. 이는 컴퓨터에서 변수를 처리하는 방식과 정확히 일치합니다.

이 점을 미루어볼 때, 모듈러 덧셈이 아벨 그룹을 형성한다는 사실은 자명합니다.이 집합은 처음부터 정해진 범위를 가지므로, 덧셈 연산에 대해 닫혀 있습니다. 또한, 교환 법칙이 성립하는 것은 명확하며, 결합 법칙도 마찬가지로 성립합니다. 여기서 0은 이 도메인에서 덧셈에 대한 항등원에 해당하며, 모든 요소에 대해 덧셈의 역원이 존재합니다.

이 특징은 UAdd와 TAdd 둘 다에게 해당됩니다.

Isomorphic Group to unsigneds with UAdd

\[TAdd_w(u, v) = U2T(UAdd_w(T2U(u), T2U(v)))\]

위 식이 성립하는 이유는 명백합니다. 사실, T2U와 U2T는 단지 이 도메인의 비트가 어떻게 해석되는지를 나타내는 것일 뿐입니다. 실제 연산은 비트 수준에서 이루어지며, 비트를 어떻게 해석하든 그 연산 결과에 영향을 주지 않습니다.

컴파일 예시

예시 01(곱셈)

long mul12(long x)
{
  return x*12;
}

위 C 코드는 변수 x에 12를 곱하는 함수입니다. 이 함수가 실제로 어떻게 컴파일되는지 살펴봅시다.

leaq (%rax, %rax, 2), %rax
salq $2, %rax

첫 번째 줄에서는 rax 레지스터에 저장된 값(x)에 2를 곱한 후, 그 결과에 원래의 rax 값을 더해 다시 rax에 저장합니다. 이 연산으로 rax에는 원래 값의 3배가 저장됩니다. 다음 줄에서는 rax에 저장된 값을 2비트만큼 왼쪽으로 산술 시프트(salq)합니다. 이는 값을 4배로 만드는 연산과 동일합니다.

결과적으로, 이 어셈블리 코드는 원래 값에 3을 곱한 후, 그 결과를 다시 4배로 만들어 최종적으로 12배를 하는 연산을 수행합니다. 따라서, 이 어셈블리 코드는 C 코드의 x*12 연산과 같은 결과를 성공적으로 수행합니다.

예시 02(나눗셈)

unsigned long udiv8
      (unsigned long x)
{
  return x/8;
}

위 C 코드는 주어진 x 값을 8로 나누는 함수입니다. 해당 함수가 어셈블리로 어떻게 번역되었는지 살펴보겠습니다

shrq $3 %rax

이 어셈블리 코드는 rax 레지스터에 저장된 값을 오른쪽으로 3비트 논리 시프트(shrq)합니다. 오른쪽으로 1비트 논리 시프트는 값을 2로 나누는 것과 같으므로, 3비트를 오른쪽으로 시프트하는 것은 값을 (2^3 = 8)로 나누는 것과 동일한 결과를 가져옵니다. 논리 시프트를 사용하는 이유는 함수에 들어오는 값이 unsigned long으로, 음수인 경우를 고려할 필요가 없기 때문입니다.

따라서, 이 어셈블리 코드는 C 코드의 x/8 연산과 같은 결과를 성공적으로 수행합니다.

Signed Power of 2 Divede with Shift

2로 나누는 과정에서 오른쪽 시프트 연산을 사용하는 것은 컴퓨터 내부에서의 효율적인 계산 방식을 의미합니다. 이때 산술 시프트를 사용하면, 음수를 나누는 경우에도 오류 없이 처리할 수 있습니다. 그러나 이 방법으로 나눗셈을 수행하면 때로는 원치 않는 결과를 얻게 됩니다.

예를 들어, -15213을 2로 나누면 이론적으로는 -7606.5가 되어야 하지만, 컴퓨터는 몫만을 저장하기 때문에 -7607을 저장합니다. 그러나 실제 프로그래밍 언어에서는 대체로 -7606을 결과로 제공합니다. 이는 음수를 나눌 때 소수점 아래를 단순히 제거하기를 원하기 때문입니다.

이 문제를 해결하기 위한 방법에는 마지막에 단순히 1을 더하는 전략이 아닌, 나누기 전에 1과 최대한 가까운 값을 더하는 방법이 있습니다. 만약 2의 k승으로 나눈다면, k개의 오른쪽 비트가 사라집니다. 따라서, 이 비트들이 모두 1인 값을 더한 후에 k만큼 오른쪽 시프트를 수행하면, 1에 매우 가까운 값을 더한 것과 같은 효과를 얻을 수 있습니다.

구체적으로, 만약 사라지는 k개의 비트 중 하나라도 1이 있었다면, 이는 나눈 결과에 소수점 아래 수가 존재한다는 것을 의미합니다. 이 경우, 컴퓨터는 일반적으로 1을 내립니다만, 우리는 결과적으로 1을 올려주고자 합니다. 이를 위해, 하위 k비트가 모두 1인 값을 더해주면, 하위 k비트 중 하나라도 1이 있었다면 carry가 k번째 비트까지 전달되어, 결과적으로 1을 올려주는 효과를 낼 수 있습니다

C언어 예시

C언어에서 음수를 8로 나누는 코드를 어셈블리 언어로 변환하는 과정을 살펴보겠습니다. 아래는 C언어로 작성된 함수입니다.

long idiv8(long x)
{
  return x / 8;
}

이 함수는 입력된 x 값을 8로 나누어 반환합니다. 이 연산을 어셈블리 언어로 변환한 결과는 아래와 같습니다.

	testq %rax, %rax
	js	L4
L3:
	sarq	$3, %rax
	ret
L4:
	addq	$7, %rax
	jmp	L3

위 어셈블리 코드를 분석해 보면, testq %rax, %rax 명령어를 사용하여 입력 값(%rax 레지스터에 저장된 값)이 음수인지 양수인지를 확인합니다. testq 명령은 두 연산자를 AND 연산하고, 그 결과에 따라 플래그를 설정합니다. 여기서는 같은 값을 AND 연산하므로, 입력 값이 음수라면 음수 플래그(Negative flag)가 설정됩니다.

js L4 명령어는 음수 플래그가 설정된 경우(L4 레이블로 이동)를 확인합니다. 이 경우, 입력 값이 음수임을 의미하며, L4 블록으로 이동합니다.

L4 블록에서는 addq $7, %rax 명령어를 사용하여 입력 값에 7을 더합니다. 이는 앞서 설명한 음수를 나눌 때 소수점 아래 값을 올리기 위한 방법과 일치합니다. 8로 나눌 때 사라지는 하위 3비트 중 하나라도 1이 있다면, 나눈 결과에 소수점이 존재하는 것이므로, 7을 더함으로써 나눗셈 결과를 올림합니다.

이후 jmp L3 명령어로 L3 레이블로 점프하여 실제 나눗셈 연산(sarq $3, %rax)을 수행합니다. 여기서 sarq $3, %rax는 %rax 레지스터의 값을 오른쪽으로 3비트 산술 시프트하여, 즉 8로 나누는 연산을 수행합니다. ret 명령어는 함수의 마지막에서 호출자로 제어를 반환합니다.

이 어셈블리 코드를 통해 C언어에서 음수를 나누는 연산이 어떻게 처리되는지, 특히 음수를 나누기 전에 7을 더하는 과정이 어떻게 구현되는지를 이해할 수 있습니다.