LLVM이 해시 시드, 반복 순서, 반복자 무효화, 불안정 정렬, 링커 섹션 배치, ABI 검사로 관찰 가능한 우발적 동작에 대한 의존성을 드러내고 억제하는 방법을 살펴본다.
HomeArchivesFeedsTILPresentations
API 사용자가 충분히 많아지면, 계약에서 무엇을 약속했는지는 중요하지 않다. 당신의 시스템에서 관찰 가능한 모든 동작은 누군가에게 의존 대상이 된다. — Hyrum's Law
컴파일러에서 Hyrum의 법칙이 나타나는 가장 흔한 형태는 명시되지 않은 동작 에 대한 의존이다. 예를 들면 해시 버킷 순서, std::sort 이후 같은 원소들의 순서, 패딩 오프셋 등이 있다. 같은 틀로 보면 기술적으로는 정의되지 않은 동작인 경우도 포함된다. 예를 들어 무효화된 반복자의 사용이 그렇고, 단순한 우발적 속성인 ABI 구조체 레이아웃이나 ELF 섹션 오프셋도 여기에 들어간다.
컴파일러 자체가 이런 의존성을 품고 있을 때 증상은 보통 빌드마다 출력이 달라지는 형태로 나타난다. 표준 라이브러리가 바뀐 뒤 결과가 달라지는 불안정 정렬, 해시 함수가 바뀌었을 때 반복 순서가 달라지는 해시 맵 같은 경우다. 때로는 하나의 빌드 안에서도 실행마다 달라진다. DenseMap<void *, X> 키는 ASLR에서 유도된 시드 때문에 호출마다 버킷 순서가 달라진다. 어느 쪽이든 재현 가능한 빌드, 이분 탐색, 버그 리포트는 모두 같은 입력 → 같은 출력이라는 가정에 기대고 있으며, 숨어 있는 Hyrum 의존성은 그 가정을 깨뜨린다.
이 글에서는 계약의 사각지대를 흔들어서 그러한 의존성이 조용히 형성되지 못하게 하는 몇 가지 메커니즘을 훑어본다.
첫 번째 방어선은 해시 함수 자체다. llvm/include/llvm/ADT/Hashing.h:
1
2
3
4
5
6
7
8 inline uint64_t get_execution_seed() {
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
return static_cast<uint64_t>(
reinterpret_cast<uintptr_t>(&install_fatal_error_handler));
#else
return 0xff51afd7ed558ccd ULL;
#endif
}
모든 llvm::hash_value에 XOR되는 시드는 install_fatal_error_handler의 런타임 주소이며, ASLR 아래에서는 프로세스마다 달라진다. 헤더 주석은 이를 분명히 말한다.
시드는 프로세스마다 비결정적이다(LLVMSupport 안 함수의 주소). 이는 사용자가 특정 해시 값에 의존하지 못하게 하기 위함이다.
모든 hash_combine / hash_integer_value 호출은 이 시드를 받아들이고, hash_value를 사용하는 타입을 키로 삼는 모든 DenseMap<K, V>는 실행마다 버킷 순서를 바꾼다. MD5, BLAKE3, SHA1, SHA256은 바이트 단위로 안정적이다. 실제로 다이제스트를 원한다면 그런 것들이 맞는 도구다.
내 커밋 ce80c80dca45가 2024년에 이 시드를 도입했다.
코드는 반복 순서에 대한 의존성을 키워 나갈 수 있다. LLVM_ENABLE_REVERSE_ITERATION은 해시 컨테이너를 거꾸로 순회하게 해서 그런 위반을 드러낸다. llvm/include/llvm/Support/ReverseIteration.h:
1
2
3
4
5
6
7 template <class T = void *> constexpr bool shouldReverseIterate() {
#if LLVM_ENABLE_REVERSE_ITERATION
return detail::IsPointerLike<T>::value;
#else
return false;
#endif
}
DenseMap은 BucketItTy를 std::reverse_iterator<pointer>로 뒤집고, SmallPtrSet은 begin()과 end()를 바꾸며, StringMap은 버킷 선택 전에 해시에 비트 단위 NOT을 적용한다. StringMap의 해시는 get_execution_seed를 우회하므로, 이것이 StringMap에 변화를 주는 유일한 장치다.
해시 시드와 달리, 역방향 반복은 assertion과 함께 자동으로 켜지지 않는다. -DLLVM_REVERSE_ITERATION=ON으로 명시적으로 선택해야 한다. 2026년에는 이미 이 옵션이 촉발한 수정들이 병합되었다. 7f703cabf728 (MLIR SSA 값 완성 순서), 0b3afd35c41d (MLIR SROA alloca 순서), f5e2c5ddcec7 (clang 테스트 하나)다.
반복 순서와는 별개의 축은, 변경 후 기존 반복자에 무슨 일이 일어나는가이다. llvm/include/llvm/ADT/EpochTracker.h:
1
2
3
4
5
6
7
8
9
10
11
12 class DebugEpochBase {
uint64_t Epoch = 0;
public:
void incrementEpoch() { ++Epoch; }
~DebugEpochBase() { incrementEpoch(); } // use-after-free를 잡는다
class HandleBase {
bool isHandleInSync() const {
return *EpochAddress == EpochAtCreation;
}
};
};
DenseMap과 관련 컨테이너는 DebugEpochBase를 상속한다. 변경이 일어나면 epoch가 증가하고, 반복자는 생성 시 그 값을 캡처한 뒤 불일치 시 assertion을 발생시킨다. 소멸자도 값을 증가시키므로, 파괴된 컨테이너를 가리키는 오래된 반복자는 해제된 메모리를 읽는 대신 assertion을 낸다.
이 장치가 없으면 반복 중 변경이 버킷 레이아웃에 따라 우연히 동작하는 것처럼 보일 수 있다. 그리고 바로 그 버킷 레이아웃이 앞서 본 해시 시드와 역방향 반복에 의해 흔들린다. epoch 검사는 실행이 어떤 “운 좋은” 레이아웃에 걸렸는지와 상관없이 잠복한 버그를 깔끔한 assertion으로 바꾼다. NDEBUG 아래에서는 no-op으로 사라진다.
같은 방어 패턴이 모노레포 안에서 두 번 등장한다. 서로 다른 하위 프로젝트에서, 몇 년 차이를 두고 나타났다.
EXPENSIVE_CHECKS 아래의 llvm::sortllvm/include/llvm/ADT/STLExtras.h:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#ifdef EXPENSIVE_CHECKS
namespace detail {
inline unsigned presortShuffleEntropy() {
static unsigned Result(std::random_device{}());
return Result;
}
template <class IteratorTy>
inline void presortShuffle(IteratorTy Start, IteratorTy End) {
std::mt19937 Generator(presortShuffleEntropy());
llvm::shuffle(Start, End, Generator);
}
} // end namespace detail
#endif
template <typename IteratorTy, typename Compare>
inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
#ifdef EXPENSIVE_CHECKS
detail::presortShuffle<IteratorTy>(Start, End);
#endif
std::sort(Start, End, Comp);
}
std::sort와 qsort는 안정 정렬이 아니다. 같은 원소들의 순서를 관찰하는 코드는 문서화되지 않은 동작에 의존하고 있는 셈이다. 사전 셔플은 그 관찰 결과를 실행마다 다르게 만든다. 커밋 5a3d47fabcb6가 2018년에 이 래퍼를 추가했으며, 동기는 PR35135였다.
LLVM은 std::shuffle을 직접 호출하지 않고 자체 llvm::shuffle도 제공한다. 이유는 “서로 다른 표준 라이브러리를 사용할 때에도 LLVM이 동일하게 동작하도록” 하기 위해서다. 재현 가능성 도구의 재현 가능성이 호스트 stdlib에 의존한다면, 그것은 없는 것보다도 못하다. 아래의 링커 섹션도 여기에 의존한다.
llvm::stable_sort는 의도적으로 사전 셔플을 하지 않는다. 같은 원소의 순서가 실제로 필요한 코드가 명시적으로 선택하는 수단이기 때문이다.
_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITYlibc++에는 거의 완벽히 대응되는 메커니즘이 있다. 다만 프로젝트 내부 위생이 아니라 하류 사용자들을 위해 설계되었다. libcxx/include/__debug_utils/randomize_range.h:
1
2
3
4
5
6
7
8
9
10 template <class _AlgPolicy, class _Iterator, class _Sentinel>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
void __debug_randomize_range(_Iterator __first, _Sentinel __last) {
#ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
if (!__libcpp_is_constant_evaluated())
std::__shuffle<_AlgPolicy>(__first, __last, __libcpp_debug_randomizer());
#else
(void)__first; (void)__last;
#endif
}
호출 지점은 세 곳이다.
std::sort — 입력을 사전 셔플한다.std::partial_sort — 입력을 사전 셔플하고, 이후 정렬되지 않은 꼬리 부분도 다시 셔플한다.std::nth_element — 사전 셔플한 뒤 파티션 양쪽을 다시 셔플한다.시드 처리 방식은 get_execution_seed와 닮았다. 프로세스별 변이를 위해 ASLR 또는 정적 std::random_device를 사용하고, _LIBCPP_RANDOMIZE_UNSPECIFIED_STABILITY_SEED=<n>으로 고정 시드를 줄 수 있는 탈출구도 둔다. 기본값은 꺼짐이며, C++11 이상에서만 제공된다.
libcxx/docs/DesignDocs/UnspecifiedBehaviorRandomization.rst는 동기를 이렇게 설명한다.
Google은 수천 개의 테스트가 정렬 및 선택 알고리즘의 안정성에 의존하고 있음을 측정했다. 그리고 우리는 정렬 알고리즘을 업데이트할 계획도 있다(적어도 플래그 아래에서 더 많은 알고리즘을 제공할 계획이다). 이 작업은 그것을 점진적이고 지속 가능하게 진행하는 데 도움이 된다.
여기서는 PR20837 — 최악의 경우 O(n²)인 std::sort — 를 libc++가 특히 배포하고 싶어 했던 업그레이드 사례로 든다. 셔플은 게이트 역할을 하는 도구다. 하류 테스트가 이 기능을 켠 상태에서 통과한다면, 알고리즘 변경 뒤에도 통과할 것이다.
두 메커니즘을 나란히 비교하면 각각을 따로 보는 것보다 더 흥미롭다.
llvm::sort의 래퍼는 내부 위생 도구다. LLVM은 스스로의 주된 사용자이므로, 셔플은 STLExtras.h 안에 있고 빌드 플래그 뒤에 숨어 있으며 문서도 없다.DesignDocs/ 페이지, 공개 매크로, 공개 시드 오버라이드, 명시적인 “Patches welcome.” 안내까지 있다. 그럴 수밖에 없다. libc++의 사용자는 libc++ 자체가 아니며, 여기서 지키려는 계약은 C++ 표준 그 자체이기 때문이다.__debug_randomize_range는 세 호출 지점에 적용되며, 각 알고리즘이 어떤 부분 범위를 명세하지 않은 채 남겨 두는지 드러낸다. LLVM의 래퍼는 더 단순한 같은 원소 순서 문제만 다룬다.std::unordered_*의 반복 순서 — 는 둘 다 명세되지 않았지만, libc++는 이를 무작위화하지 않는다. 라이브러리로서의 LLVM은 한다. 이 표면 하나만 보면 LLVM이 자기 stdlib보다 앞서 있다.--shuffle-sections와 --randomize-section-paddingELF 전용인 lld 옵션 두 개는 어떤 계약도 다루지 않는 레이아웃 세부사항을 교란한다.
--shuffle-sections=<glob>=<seed>lld/ELF/Writer.cpp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14 for (const auto &patAndSeed : ctx.arg.shuffleSections) {
...
const uint32_t seed = patAndSeed.second;
if (seed == UINT32_MAX) {
// If --shuffle-sections <section-glob>=-1, reverse the section order.
// The section order is stable even if the number of sections changes.
// This is useful to catch issues like static initialization order
// fiasco reliably.
std::reverse(matched.begin(), matched.end());
} else {
std::mt19937 g(seed ? seed : std::random_device()());
llvm::shuffle(matched.begin(), matched.end(), g);
}
}
하나의 옵션 안에 세 가지 모드가 있다.
seed = -1 — 결정적인 역순. 새 섹션이 추가되어도 안정적이다. .init_array*에 -1을 적용하고 다시 빌드한 뒤 테스트 스위트를 돌려 보라. 깨지는 것이 있다면 그것은 진짜 정적 초기화 순서 버그다. 플래그 하나면 충분하며, Frankenstein식 링크 스크립트도 필요 없다.seed > 0 — 결정적인 무작위 셔플. 실행과 호스트를 넘어 재현 가능하다. llvm::shuffle이 호스트 독립적이기 때문이다. 이분 탐색을 망치지 않으면서 CI에 쓰기 좋다.seed = 0 — std::random_device()로 시드된다. 링크할 때마다 새로운 비결정성이 생긴다.연혁을 보면 423cb321dfae가 =-1 역순 모드를 도입했고, 16c30c3c23ef가 이를 glob별 시드로 일반화했으며, 그 덕분에 .init_array*=-1 같은 사용법이 가능해졌다. c135a68d426f는 이 기능 자체가 잘못된 동적 재배치 순서를 만들어 내던 버그를 고쳤다. Hyrum 완화 장치조차 정합성 함정을 가질 수 있다.
--randomize-section-padding=<seed>이 자매 옵션은 입력 섹션 사이와 세그먼트 시작점에 패딩을 삽입함으로써 섹션 오프셋 을 교란한다 (lld/ELF/Writer.cpp):
1
2
3
4 static void randomizeSectionPadding(Ctx &ctx) {
std::mt19937 g(*ctx.arg.randomizeSectionPadding);
// Insert padding between input sections and at segment starts.
}
호출자는 링커가 약속하지 않은, 패딩으로 유도된 오프셋에 의존성을 키운다. 프로파일 유도 파이프라인, 부채널 연구, 특정 주소를 고정하려는 익스플로잇 도구 체인 같은 경우가 그렇다. 시드 기반 교란은 그런 의존성을 가시화한다.
두 옵션 모두 ELF 전용이다. MachO와 COFF 포트에는 이에 대응되는 것이 없다.
llvm/include/llvm/Config/abi-breaking.h.cmake:
1
2
3
4
5
6
7
8
9#if LLVM_ENABLE_ABI_BREAKING_CHECKS
ABI_BREAKING_EXPORT_ABI extern int EnableABIBreakingChecks;
LLVM_HIDDEN_VISIBILITY
attribute((weak)) int *VerifyEnableABIBreakingChecks =
&EnableABIBreakingChecks;
#else
ABI_BREAKING_EXPORT_ABI extern int DisableABIBreakingChecks;
...
#endif
이 헤더를 포함하는 모든 TU는 자기 자신의 빌드 플래그에 따라 EnableABIBreakingChecks 또는 DisableABIBreakingChecks에 대한 약한 참조를 하나씩 갖게 된다. 같은 libLLVM에 대해 두 설정을 섞어 링크하면 링크 시점에 미해결 심볼이 발생한다. MSVC에서는 #pragma detect_mismatch로 같은 보장을 제공한다.
트리 밖 사용자들은 흔히 한 트리의 헤더로 컴파일하고 다른 libLLVM에 링크한다. 이런 게이트가 없으면 링크가 우연히 고른 구조체 레이아웃에 따라 조용히 오컴파일이 발생한다. 게이트가 있으면 링크가 실패한다.
위 메커니즘들은 모두 안정적인 소비자가 신경 쓰지 말아야 할 표면을 겨냥한다. 버킷 순서, 같은 원소의 정렬 순서, init-array 순서 같은 것들이다. 하지만 디버거, 프로파일러, sanitizer, 재현 가능한 빌드 인프라는 그런 출력들을 소비하며, 그것들이 안정적이어야 한다.
어떤 경우에는 더 강한 보장이 명시적 옵션으로만 제공된다. 예를 들어 Bitcode와 텍스트 IR은 -preserve-bc-uselistorder / -preserve-ll-uselistorder를 사용할 때에만 use-list 순서를 보존한다.
가까운 사촌 격의 예로 clang의 -frandomize-layout-seed / __attribute__((randomize_layout))가 있다. 기계적으로는 동일하다. 구조체 필드에 시드 기반 std::shuffle을 적용하며, 부수적으로 offsetof 의존성을 깨뜨리기도 한다. 그러나 의도는 익스플로잇 완화다. GrSecurity의 Randstruct GCC 플러그인에서 가져온 것으로, 개발자 도구가 아니라 빌드별 커널 하드닝을 위한 것이다.
Older Recent lld/ELF performance improvements
adcai9algorithmarmascassemblerautomatonawesomebctfbinarybinutilsbmcbuild systemcc++cclscgcchrootclangclang-formatcodinsanitycoffee scriptcompilercompressioncomputer securitycontestcsvctfdata structuredebugdefcondesktopdockerelfemacsemailemojiemscripteneventexpectext4fdpicfeedsfirmwarefloating pointforensicsfpfreebsdgamegccgdbgentoogitgithubglibcgraphgraph drawinggtkhacker culturehackerrankhanoihaskellhpcimageinotifyipsecirciscjjavascriptjosephus problemjqkernelkytheldleetcodelibunwindlinkerlinuxlldlldbllvmlspm68kmakefilemathmazemirrormlmuslmuttn-bodyneovimnetworknginxnimnlpnode.jsnoipnotmuchnpmocamlofflineimapoiojopenwrtparallelparser generatorperformanceperlpowerpcpresentationpuzzlepythonqqradare2regexregular expressionreleasereverse engineeringreviewriscvrouterrtldrubyructfes390xsanitizerschemesearchsecuritysframeshellsshstringologystudent festival puzzlesuffix arraysuffix automatonsummarysuricatatelegramtelegramircdterminaltlstraveltraversaltreetrendmicroudevunicodeunixusbvimvpnvtewargameweb analyticswebqqircdwebsitewechatwechatircdwindow managerwindowsx86xbindkeysxmonadxzyanshi
© 2026 MaskRay
Powered by Hexo