하루는 본인은 회사 업무를 위해 인터넷에 굴러다니는 어느 암호화 알고리즘 소스를 프로젝트에다 붙여 쓴 적이 있었다.
그런데 곧장 문제가 발생했다. 본인이 맡은 부분은 Windows용 클라이언트인데, 같은 소스를 사용하는 다른 플랫폼 클라이언트 내지 서버와 교신이 제대로 되지 않고 있었다.
결국은 문제의 코드를 별도의 콘솔 프로그램 프로젝트로 떼어서 따로 돌려 보니, 문제의 원인은 그 암호화 알고리즘에 있음이 밝혀졌다. 같은 소스를 빌드해서 돌렸는데 결과가 서로 차이가 나는 것이었다.
게다가 Visual C++로 빌드하는 같은 Windows용 프로그램도, 알고 보니 debug 빌드는 결과가 옳게 나오는데 release 빌드만이 문제가 있었다!
debug와 release가 서로 다르게 동작하는 프로그램은 십중팔구가 멀티스레드 race condition 아니면 단순 초기화되지 않은 변수 때문이다. 물론 이 코드는 스레드를 따로 만들지는 않으니 의심 부분은 응당 후자. 이거 또 남이 짜 놓은 복잡한 코드에서 꼭꼭 짱박혀 있는 버그 찾느라 무진장 고생하겠다는 생각과 함께 몇 시간 동안 디버깅을 진행했다.
release 모드로 빌드된 프로그램은 함수 인라이닝과 각종 최적화 때문에 debug 빌드처럼 한 라인씩 엄밀하게 step in이 되지 않으며 변수값 조회도 안 되는 경우가 종종 있다. 그러니 도대체 언제부터 두 빌드의 변수값이 달라지는지 printf 신공을 펼치면서 꽤 어렵게 문제 원인을 추적해야 했다.
문제의 범위는 많이 좁혀졌다. stack이나 heap 메모리를 초기화하지 않고 쓴 경우는 눈을 씻고 찾아도 없었다. 마치 난수 씨앗처럼 초기의 동일한 input으로부터 일련의 output들이 계산을 통해 파생되는데, 언제부턴가 두 빌드가 생성해 내는 변수값이 미묘하게 서로 달라지는 게 보였다. 저 동일한 input 말고 계산에 영향을 끼치는 요소는 정말 없는데? 왜 값이 달라지지..?
그리고 결국은 설마 하던 녀석이 사람을 잡았다는 걸 알게 됐다. 문제의 함수는 바로.. 이것이었다!
unsigned long Rol(unsigned long x, long y)
{
if (y % 32 == 0) {return x;}
else {return ((x << y)^(x >> -y));}
}
저 간단한 함수의 실행 결과가 release 빌드와 debug 빌드가 서로 달랐다. 비주얼 C++ 2012, 2010, 2003 전부 공통으로.
암호화 알고리즘에서 절대 빠지지 않는 그 이름도 유명한 비트 회전(bit rotation)을 구현한 함수인데..
비트를 음수 shift하는 연산은 좀 생소해 보였다.
본인은 15년 가까이 C/C++ 프로그래밍을 해 오면서 지금까지 막연히 A<<-B = A>>B, A>>-B = A<<B이지 않으려나 생각해 왔다.
그런데 실상은 전혀 그렇지 않았다.
컴퓨터의 구조적인 특성상 나눗셈에서 피연산자의 부호에 음수가 섞이면 몫과 나머지의 부호가 수학에서 생각하는 직관적인 형태로 구해지지 않는다는 건 어렴풋이 알고 있었다만, 비트 shift에도 그런 특성이 있구나.
음수 shift의 결과는 언어 스펙 차원에서 undefined인 모양이다. 진짜 말 그대로 A=A++처럼 '그때 그때 달라요'인 듯.
중의적인 코드를 컴파일러마다 제멋대로 번역하는 것 자체를 모조리 막을 수는 없겠지만, 그건 최소한 '이식성'에 문제가 생길 수 있다고 경고라도 띄워야 하지 않나 싶다.
실제로 위의 함수를 실행하면
Rol(0xBE9F8300, 1);
Rol(0xEC6BFC33, 1);
Rol(0xFC58371A, 1);
의 함수값은 release 빌드에서는 각각 0x7D3F0600, 0xD8D7F866, 0xF8B06E34이 나온다.
그러나 debug 빌드에서는 0x7D3F0601, 0xD8D7F867, 0xF8B06E35가 나오며, 이게 맞는 값이다. release는 무슨 이유에서인지 최하 자리 1비트를 누락하고 있었던 것이다. 그러니 이후의 암호화 결과가 몽땅 틀어지는 건 당연지사.
설상가상으로 xcode에서는 더 이상한 결과가 나왔던 걸로 기억한다.
유명 암호화 라이브러리가 왜 저렇게 이식성 없는 연산을 썼는지 난 잘 모르겠다. 음수 shift의 결과가 어떻게 나올 것을 기대한 건지?
저 문제를 우회하느라 지금까지 머리로만 알고만 있었지 실무에서 쓸 일이 전혀 없으리라 생각했던 테크닉을 쓰게 됐다.
소스 코드의 특정 구간에 한하여 최적화를 잠시 끄는 #pragma optimize("", off) 되시겠다.
bit rotation은 bit shift에다가 한쪽 끝에 있는 비트들을 따로 반대편 끝에다 shift시켜서 얹어 준다는 차이만이 있을 뿐이다. 32비트 부호 없는 정수 기준으로, 작은 자리수가 큰 자리로 이동하는 왼쪽(<<) rotation을 나보고 구현하라면 이렇게 짜겠다.
UINT Rol2(UINT x, int y)
{
return (x<<y)|(x>>(32-y));
}
32라는 숫자가 보기 싫으면 sizeof 등을 써서 다른 방식으로 바꾸면 되고.
그리고 이렇게만 짜도 컴파일러는 이 연산 전체의 의미를 알아보고 당연히 rol이라는 '비트 왼쪽 회전'이라는 '한 인스트럭션'으로 최적화해서 번역해 준다. bit shift인 shl, shr만큼이나 rotation도 굉장히 기계 친화적인 동작이며, 전용 명령이 있는 것이다. 하지만 정작 저 공개 라이브러리 함수는 Visual C++ 컴파일러가 rol이라고 최적화하지 않는다.
아마 -n shift는.. 전체 비트수에 대한 보수(32-n)만치 shift하는 것과 같다고 전제를 한 듯하다.
그리고 or 대신 xor을 쓴 것은 그게 컴퓨터 구조 차원에서 기계어 코드 길이가 더 짧거나 속도가 조금이라도 더 빨라서 그런 듯하다. 필요하다면 x=0조차도 x^=x로 표현하는 게 컴퓨터 세계이니 말이다.
결국은 음수 처리까지 정확하게 해서 shift든 rotation이든 -n만치 하는 건 반대편으로 n만치 하는 것과 같은 게 보장되는 함수를 만들려면..
if문을 써서 처리를 완전히 따로 하고 <<, >> 자체에는 어떤 경우든 음수 shift가 존재하지 않게 하는 게 이식성 면에서 가장 좋은 해결책으로 보인다. 흥미진진한 경험을 한 날이었다.
Posted by 사무엘
