요약
큰 난수를 나머지 연산으로 잘라 고르면 결과가 치우치므로, 확률을 직접 적는 API를 기본으로 써야 합니다.
이스트 리버 소스 컨트롤 블로그에 오스틴 사이프가 쓴 API 설계 이야기입니다. 이 회사는 결정론적 퍼징(입력을 무작위로 바꿔 가며 버그를 찾는 테스트) 플랫폼 앤티시시스로 코드를 시험하면서 무작위 선택 코드를 손봤습니다.
왜 중요한가
- 개발자 주의력에 기대지 말고, 숫자 대신 결과와 확률을 다루는 도구를 기본으로 두자는 제안입니다.
- 퍼징에서는 어떤 경로를 얼마나 자주 시험할지가 분포로 정해지므로, 분포가 틀리면 테스트 범위도 틀어집니다.
핵심 내용
random_u64()로 뽑은 수를 선택지 개수로 나눈 나머지로 고르면 균등 분포가 깨집니다.- 0~9를 선택지 3개에 나누면 첫 번째는 40%, 나머지 둘은 30%씩 뽑힌다는 예를 들었습니다.
- 원인으로 지나치게 낮은 수준의 추상화와, 나머지 같은 비선형 연산이 분포 자체를 바꾼다는 점을 꼽았습니다.
- 파이썬
random.choices처럼 정수 상대 가중치를 받는random_choice()를 기본 도구로 삼자고 했습니다. - 회사는 가중치 선택 코드에서
random_u64()호출을 모두 걷어내고 새 호출도 금지했습니다.
HN 반응
- 여러 이용자가 이 현상을 암호학의 '모듈로 편향'으로 부르고, 범위 밖 값을 버리고 다시 뽑는 거부 샘플링을 해법으로 들었습니다.
- 64비트 난수라면 편향이 무시할 만큼 작다는 반론과, 좋은 라이브러리가 있어도 직접 짜다 틀리니 테스트가 필요하다는 경험담이 나왔습니다.
실제로 필요한 건 기각 샘플링(rejection sampling)입니다. https://en.wikipedia.org/wiki/Rejection_sampling .
위키 문서는 엄청 복잡한 것처럼 써 놨지만, 이 용도라면 구현은 우스울 만큼 단순해도 됩니다. 그래서 왜 동작하는지 알고 있으니 자신 있게 제대로 유지보수할 수 있다는 장점도 있고요.
충분히 큰 입력을 받습니다. 예를 들어 2부터 11까지의 정수를 뽑으려 한다면 니블(반 바이트)이면 충분합니다. 그다음 그 무작위 입력이 원하는 범위 안에 있는지 봅니다. 있으면 답을 얻은 겁니다. 없으면 그 입력을 버리고 새로 받습니다.
너무 많은 프로그래머가 난수를 귀한 자원인 양 굽니다.
난수가 귀한 건 아니지만 생성하는 데 시간이 들긴 합니다. 기각 샘플링은 분기를 하나 추가하는데, 그 분기가 얼마나 자주 실행되는지가 중요할 수 있습니다. 제 속성 기반 테스트(property-testing) 프레임워크에서는 큰 난수 배열을 더 효율적으로 생성하도록 바꿨더니 성능이 좋아졌습니다.
RNG가 u64를 내놓는다면(getrandom() 호출이나 xoshiro 같은 단순한 RNG도 그렇습니다), 기사에 나온 [0, 10) 범위의 난수 정수는 다시 뽑아야 할 확률이 아주 작습니다(2⁶⁴분의 6, 즉 3.2e-17%로 사실상 0입니다).
범위가 넓어지면 (아마도) 기각이 더 자주 일어나겠지만, 범위가 엄청나게 크지 않은 한 기각 분기는 거의 실행되지 않는 분기일 겁니다.
그런데 그러면 비트를 많이 버리게 됩니다. 숫자 하나에 4비트씩 쓰면 64비트 한 번 뽑은 것에 난수 숫자 16개를 담을 수 있어요. 하지만 그렇게 하면 기각 샘플링 분기가 훨씬 더 자주 실행됩니다.
64비트 난수를 4비트 난수 16개로 쪼개려면 그 64비트 난수를 만드는 RNG의 품질이 아주 높아야 합니다. 그 정도 품질이 나오는 건 암호학적 RNG뿐입니다.
비암호학적 PRNG는 AES 같은 것을 쓰는 암호학적 RNG보다 훨씬 빠를 때만 쓸모가 있습니다. 요즘 CPU 상당수에서 AES는 128비트 난수를 만드는 데 클럭 10사이클 정도가 들고, 더 최근 CPU에서는 그 절반 이하로도 가능합니다.
그러니 비암호학적 PRNG가 경쟁력을 가지려면 64비트 숫자를 1나노초 안에 만들어야 합니다. 오래된 PRNG 중에는 이만큼 빠르지 않은 것이 많아서 완전히 시대에 뒤떨어졌습니다.
이런 PRNG는 생성된 숫자에서 조각을 둘 이상 떼어 냈을 때 서로 상관관계가 없다는 보장을 전혀 해 주지 않습니다. 그래서 PRNG가 준 난수 하나로 난수 둘 이상을 만들어서는 안 된다는 것이 원칙입니다.
선택지 수가 2의 거듭제곱이 아닌데 균등 분포를 원한다면 기각은 피할 수 없습니다.
그래도 기각은 입력 범위를 출력 범위로 바꾸는 곱셈이나 나눗셈의 앞에서 할 수도, 뒤에서 할 수도 있습니다.
기각하는 위치를 잘 고르면 버려지는 값의 양을 최소로 줄일 수 있고, 그러면 분기가 실행될 가능성이 낮아져서 대부분 올바르게 예측됩니다.
최고 속도를 원한다면 나눗셈 대신 곱셈을 쓰는 편이 좋습니다. 입력을 1보다 작은 분수로 보고, 곱한 뒤에 정수 부분만 남기는 방식입니다. 기각 때문에 성능이 떨어질까 걱정하는 것보다 곱셈을 쓰도록 신경 쓰는 쪽이 보통 더 중요합니다.
와, 그 문서는 다차원 얘기로 완전히 샛길로 빠지네요.
그리고 맞아요, 결국 난수가 범위를 벗어나면 다시 뽑는 게 전부예요. 최대한 단순하게 하고 싶다면 항상 0부터 n까지로 생성하고, n이 들어갈 만큼만 딱 맞게 랜덤 비트를 가져오세요.
예를 들어 Doom의 "fizzle" 효과가 바로 그렇게 합니다. 2^n -1 단계 길이의 수열을 만드는 LFSR의 탭을 고를 수 있는데, 이 수열에는 0이 절대 나오지 않고 1부터 2^n -1까지의 모든 수가 정확히 한 번씩 나타납니다.
그래서 320x200 해상도를 "fizzle"하려면 17비트 LFSR을 만들고, 하위 8비트를 Y 좌표로, 상위 9비트를 X 좌표로 씁니다(반대로 해도 됩니다. 어떻게 살라고 훈수할 생각은 없습니다). 그중 일부는 화면 밖입니다! 그냥 무시하세요. 그려지지 않는 "가장자리 밖" fizzle은 워낙 무작위로 흩어져 있어서 실제로는 전혀 눈치채지 못합니다.
그러다 LFSR이 결국 시드 값으로 되돌아오면 전부 다 했다는 걸 알 수 있습니다.
블로그 글에는 그 용어가 나오지 않지만, 여기서 설명하는 것은 암호학에서 흔히 "모듈로 편향(modulo bias)"이라고 부르는 것입니다.
참고: https://romailler.ch/2020/07/28/crypto-modulo_bias_guide/
OpenBSD에는 "모듈로 편향"을 피하는 arc4random_uniform()이 있습니다.
https://man.openbsd.org/arc4random.3#arc4random_uniform
글쓴이가 선택지 3개를 고르는 데 정수 10개를 쓴다는 대목에서 길을 잃었습니다. 설명에서 빠진 게 뭔지는 이제 알 것 같습니다.
random_u64() Mod 3은 실제로 버킷 하나가 더 큽니다. 그래서 선택지 하나의 가중치가 약 5×10^-20만큼 높아집니다.
rand() 자체는 가능한 값이 32767개뿐이라서, 버킷 수에 따라 어떤 버킷이 더 큰 경우도 흔합니다.
5×10^-20 정도의 치우침이 대체 어느 시점부터 신경 써야 할 일이 되는지 궁금하네요.
통계에 대해 제가 늘 어리둥절했던 게 바로 이겁니다. 별 노력 없이도 정확하게 만들 수 있는데 오차가 작다는 이유만으로 그냥 넘겨 버린다는 점이요.
문제를 풀기 위해 필요한 만큼만 하는 건 기본적인 엔지니어링입니다. 그 이상은 하지 않습니다.
"문제를 푸는 데 필요한 것"의 정의에 예상치 못한 상황에 대한 허용 오차가 이미 들어 있지 않다면 그렇지 않습니다.
아마 틀렸을 때의 결과가 편향 자체보다 훨씬 커지는 지점쯤이겠죠.
그 정도는 노이즈 속에서 골라내려면 꽤 오래 걸릴 겁니다.
정수 10개를 쓴 건 사실 여기서 말씀하시는 내용을 설명하려고 단순화한 겁니다.
기본으로 쓸 수 있는 함수가 rand_1_to_10()이라면, 그 결과를 3으로 나눈 나머지를 취했을 때 어느 한 결과가 다른 결과보다 확률이 높아진다는 게 확실히 보입니다. random_u64()도 마찬가지입니다. 차이는 더 작지만 그래도 의미 있는 수준일 수 있습니다.
코드를 블랙박스로 가정하면, 외부 관찰자는 rand_1_to_10() mod 3 코드에 뭔가 문제가 있다고 (신뢰도 95%로) 확실히 말하기까지 관측이 천 번도 필요 없습니다.
그런데 random_u64() mod 10의 경우에는 그 편향이 무작위와 눈에 띄게 구별되려면 우주의 열적 죽음에 맞먹는 표본 수가 필요합니다.
국가 단위 암호 정도를 빼고, 그 특정한 경우가 의미를 갖는 실제 사례가 있나요?
맞습니다. 2^64는 3으로 나누어떨어지지 않으니 나머지 하나가 다른 것보다 한 번 더 나오긴 하지만, 그 차이는 대략 2^64개 중 하나일 뿐입니다.
Uniform(0, 1) PRNG는 임의의 실수값 확률변수를 위한 PRNG 라이브러리의 기반으로 삼기에 알맞은 기본 요소입니다. 어떤 실수값 확률변수든 Uniform(0, 1) 확률변수의 역분위수 변환으로 나타낼 수 있기 때문입니다. 기사에서 말하듯 이 기본 요소만 제공하면 발등을 찍을 위험이 있다는 데는 동의하지만, 더 나은 UI를 제공하는 것만으로 그런 위험이 의미 있게 줄어들지는 의문입니다. 사용자들이 대체로 "내가 더 잘 안다, 그런 건 필요 없다"는 태도라면, 쓸 수 있고 편리하다는 것이 사용을 보장하지는 않기 때문입니다. 이분 탐색은 기각 샘플링이나 역변환 샘플링보다 단순한데도, UI가 PRNG보다 훨씬 편한 라이브러리 구현이 널리 있는데 버그투성이로 직접 짠 구현이 흔히 보입니다. 그런 생각을 고치려면 퍼즈 테스트나 결정론적 시뮬레이션 테스트를 더 널리 쓰는 것이 정말 필요하고, 균등 PRNG용 어댑터를 직접 만드는 것이 통계적 성질이 검증된 구현을 쓰는 것보다 결국 손해라고 설명하는 위와 같은 기사도 더 나와야 한다고 생각합니다.
PRNG가 답이라고 하셨는데, 작은 수 집합(이를테면 100개)에서 원하는 분포를 깔끔하게 얻고 싶다면 RNG를 쓰면 안 되고, 곡선 위에서 원하는 점들을 생성한 다음 섞어야 합니다(아니면 그런 일을 하는 결정론적 코드를 쓰든가요). 진짜 RNG는 어떤 숫자든 내놓을 수 있고, 아주 큰 집합에서만 분포가 균등해집니다.
문제의 얼마나 많은 부분이 난수를 보통 가르치고 접하는 방식에서 비롯된 걸까요.
제가 본 대부분의 경우는 이런 식입니다.
대부분의 사람은 "이건 이해했으니 쓸 수 있겠다"고 생각하고, 그 위에 필요한 걸 아무렇게나 얹습니다. 저도 그런 대부분의 사람 중 하나였고요.
말씀하신 논지를 잘 모르겠어요.
그 논리를 다른 분야에 옮겨 보면 금세 무너져요. 어떤 사람들은 안전장치를 제대로 쓰지 않을 테니 권총에 안전장치가 필요 없다고요? 어떤 사람들은 안 맬 테니 자동차에 안전벨트가 필요 없다고요? 난간도 필요 없겠네요..
무슨 말인지 아실 겁니다. 이건 기본적으로 니르바나 오류(완벽한 해결책 오류)예요. 안전 조치가 막으려던 경우의 100%를 못 잡는다고 해서 그게 그 조치에 반대하는 논거가 되지는 않습니다. 그 조치가 일반적인 사용 사례에 상당한 영향을 준다면 따져 볼 만하겠지만요. 안전 조치는 어떤 것이든 이점과, 그걸 도입하는 일이 얼마나 현실적인지(유지보수 같은 다른 고려 사항은 제쳐 두고)를 함께 보고 판단해야 합니다.
이 경우 쓰기 쉬운 API를 두는 것은 비현실적이기는커녕 정반대예요. 개발자의 시간을 아껴 주면서 동시에 오류도 줄여 주죠. 그래도 직접 함수를 짜야 한다면 얼마든지 그렇게 하면 되고요. 제가 보기엔 "고민할 것도 없는 일"의 정의에 이보다 가까운 사례는 없습니다.
네, 제 주장을 좀 더 분명히 하고 고쳐야겠습니다.
제가 받은 인상으로는 이 기사가, 지금보다 쓰기 편한 API가 더 많이 있다면 확률변수 샘플링을 구현할 때 생기는 버그의 빈도가 줄어들 것이라고 말하는 듯합니다. 저는 그 전제에 의문이 듭니다. 기사에서도 지적하듯 쓰기 편한 API는 이미 많은 언어의 표준 라이브러리에도, 유명한 서드파티 라이브러리에도 널리 있기 때문입니다. 그런 주장은 완화책 하나에 지나치게 기대는 것처럼 보입니다.
말씀하신 예를 빌리자면 이렇습니다.
뻔한 이유로, 이 상황에서는 규제나 의무 교육이 비현실적이라고 생각합니다.
말씀하신 분야를 포함해 다른 공학 분야들도 안전을 더 높이려고 상호 보완적인 통제에 의존하기 때문에, 퍼즈 테스트와 결정론적 시뮬레이션 테스트가 효과적인 보완책이 될 수 있다고 추측한 겁니다. 속성 기반 테스트도 또 하나의 후보가 될 수 있습니다.
제가 이렇게 주장하는 것은, 저는 대형 소프트웨어 회사에서 소프트웨어 엔지니어들과 함께 일하는 계산 통계학자인데, 이런 버그의 변형을 매주 보기 때문입니다. 흔히 듣는 변명은 "(어떤 라이브러리) 구현이 있다는 건 아는데, 내가 짠 게 같은 것의 더 간단한 버전이라고 생각했고, 그러면 의존성도 줄어드니까요"입니다. 마치 기능이 같다는 것이 자명하다는 듯이요. 자명하지 않습니다. 처음부터 원리를 따져서 엔지니어를 라이브러리 쪽으로 설득할 수 있을 때도 있지만, 그들이 계산하는 대상의 성질을 위반하는 반례(witness)를 만들어 보여 주는 쪽이 대체로 더 설득력이 있습니다. 그리고 일반화할 수 있는 테스트 전략은 그 부가 가치가 통계 응용에만 국한되지 않기 때문에 더 호응을 얻는 편입니다.
난수성 검정 > 난수성에 대한 구체적 검정: https://en.wikipedia.org/wiki/Randomness_test
이제 보관 처리된 paranoid_crypto 난수성 검정 대신 어떤 NIST SP-800-22 구현을 써야 할까요?
paranoid_crypto/docs/randomness_tests.md : https://github.com/google/paranoid_crypto/blob/main/docs/randomness_tests.md
/? NIST SP-800-22 Rust: https://www.google.com/search?q=NIST+SP-800-22+rust&oq=NIST+SP-800-22+rust
난수를 화이트닝(whitening)해서 균등 난수나 정규 난수로 만들 수 있는 경우도 있습니다.
화이트닝 변환: https://en.wikipedia.org/wiki/Whitening_transformation
첫 번째 문제에는 Lemire의 nearly divisionless 구현이 제가 제일 좋아하는 해법입니다. https://lemire.me/blog/2019/06/06/nearly-divisionless-random-integer-generation-on-various-systems/
분포에서 샘플링하는 데는 Vose의 Alias가 최고의 방법입니다. https://www.keithschwarz.com/darts-dice-coins/ 이 제가 제일 좋아하는 설명 글입니다.
제 기억이 맞다면 대니얼 르메르(Daniel Lemire)에게는 선택지 수가 2의 거듭제곱이 아닐 때 균등 분포를 얻는 방법을 더 완전하게 다룬, 더 나은 글이 따로 있습니다.
링크하신 글은 약간 오해의 소지가 있습니다. 이 문단이 정확히 옳지 않기 때문입니다.
곱셈을 쓰고 싶다고 해서 난수 부동소수점 수를 생성할 필요는 전혀 없습니다.
난수 정수를 고정소수점 분수로 해석한 다음, 곱셈 결과를 두 배 길이로 내주는 부호 없는 정수 곱셈 명령(ISA에 따라서는 곱의 상위 절반을 내주는 명령)을 쓰면 됩니다. 거기서 결과의 정수 부분에 해당하는 비트를 뽑아내면 됩니다.
그러니 나눗셈 방식과 비교해 오버헤드가 전혀 없습니다. 입력으로는 2^N개의 값이 모두 같은 확률로 나오는 PRNG를 쓰기만 하면 되는데, 대부분의 PRNG가 그렇습니다(아주 오래된 PRNG 중에는 음수가 아닌 부호 있는 정수만 내놓는 것이 있는데, 이런 PRNG는 비트 하나를 낭비하므로 곱하기 전에 왼쪽으로 한 칸 밀어야 합니다).
게다가 "약간의 통계적 편향을 감수"할 필요도 전혀 없습니다. 곱셈 전이든 후든 기각을 적용하면 나눗셈에 기각을 쓸 때와 똑같이 편향을 완전히 없앨 수 있습니다. 다만 기각 기준이 나눗셈 방식과 다르므로 기각을 어떻게 구현하는지 주의해야 합니다. 예컨대 곱셈 뒤에 기각한다면, 결과의 소수 부분이 어떤 상수보다 클 때 기각합니다. 이 상수는 곱해지는 수(즉 출력 값의 개수)와 입력의 최댓값(2^N-1을 분수로 해석한 값)을 곱한 결과의 소수 부분으로 계산합니다. 이렇게 기각하면 길이 1짜리 출력 구간마다 같은 수의 입력 값이 들어가게 됩니다. 출력 값의 개수가 입력 값의 개수에 비해 작으면 기각은 아주 드물게 일어납니다.
분명히 말하지는 않지만, 그 서두 문단만 읽고 나면 "nearlydivisionless" 함수는 사실상 제가 위에서 말한 것과 똑같은 일을 합니다. 서두 문단은 비교용 허수아비를 세워 놓은 것이고, 그 함수는 제대로 구현한 곱셈 방식보다 더 복잡하고 느립니다. 제대로 구현한 곱셈 방식은 나눗셈이 아예 필요 없습니다. "nearlydivisionless" 함수도 결과의 소수 부분을 보고 기각해서 통계적 편향을 없애지만, 미리 계산한 상수와 비교하는 대신 함수를 호출할 때마다 기각 임계값을 계산하는 비효율적인 방법을 쓰고, 그것도 나눗셈을 씁니다. 임계값 역시 곱셈으로 계산할 수 있는데도 말입니다.
게다가 제대로 된 구현이라면 곱셈 명령에 인라인 어셈블리를 써야 성능이 보장된다고 생각합니다. "nearlydivisionless" 함수는 인라인 어셈블리를 피하려고 지나치게 복잡한 식을 쓰는데, 영리한 컴파일러가 이를 단순화해서 올바른 어셈블리 명령과 같은 코드로 최적화해 주길 바라는 겁니다. 프로그램의 이식성을 확보하는 방법으로 아주 영리한 컴파일러에 기대는 건 옳은 선택이 아니라고 봅니다. 오히려 같은 ISA용으로 다시 컴파일하더라도 같은 컴파일러의 새 버전이 원하는 최적화를 하지 못해서 예측할 수 없는 성능 문제가 생길 수 있습니다. "nearlydivisionless" 함수에 쓰인 128비트 곱셈을 컴파일러가 최적화하지 못해서, 두 128비트 피연산자가 방금 64비트 값에서 승격된 것임을 알아채지 못하면 곱셈 1번 대신 4번을 하게 됩니다.
말씀드렸듯이 대니얼 르메르에게는 더 나은 곱셈 방법까지 담은 더 최근 글이 있다고 생각하는데, 지금은 찾아보기가 너무 귀찮네요.
에릭 리퍼트(Eric Lippert)가 쓴 "Fixing Random"[1]이라는 블로그 연재[0]가 있습니다. 난수에서 출발해 분포, 가중치, 노이즈 등 훨씬 많은 내용을 다룹니다. 이 주제를 깊이 파고드는 훌륭한 글입니다.
[0] https://ericlippert.com/2019/01/31/fixing-random-part-1/
[1] https://ericlippert.com/tag/fixing_random/
저는 "난수 uint" API가 너무 저수준이거나 성공의 구덩이(pit of success)가 없다고 생각하지 않습니다. 그냥 엉뚱한 API를 집어 들고 계신 겁니다. "n개의 비트를 의사 난수적으로 1 또는 0으로 정하기"라는 문제는 "확률 분포에 따라 원소 하나 고르기"라는 문제와 가깝긴 해도, 그 자체로 별개의 문제입니다.
그래서 실제로는 언어 설계자들이 표준 라이브러리에 "std.choice" 같은 것을 넣어야 한다는 주장이 된다고 봅니다. 난수 바이트를 받아서 "이 컬렉션에서 원소 하나를 무작위로 가져오기" 같은 흔한 작업을 편리하게, 그리고 올바르게 해 주는 함수 말입니다.
(표준 라이브러리가 "일반 난수 생성기"와 "암호학적으로 안전한 난수 생성기"를 구분한다면, "무작위 비트 생성"과 "확률적 선택"의 구분도 그만큼 중요하다고 생각합니다.)