Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[BOLT] BOLT Optimization Corrupts Cryptographic Functionality in nettle Library, Leading to SHA3, SHAKE, EdDSA, and Ed448 Test Failures #125490

Open
ms178 opened this issue Feb 3, 2025 · 3 comments
Open

[BOLT] BOLT Optimization Corrupts Cryptographic Functionality in nettle Library, Leading to SHA3, SHAKE, EdDSA, and Ed448 Test Failures #125490

ms178 opened this issue Feb 3, 2025 · 3 comments
Labels
BOLT

Comments

@ms178
Copy link

ms178 commented Feb 3, 2025 •
edited
Loading

Description:

I see several test failures during the BOLT instrumention phase of the nettle cryptographic library (version 3.10.1). I use the provided nettle test suite as training run, but it results in functional regressions, specifically causing failures in SHA3, SHAKE, EdDSA, and Ed448 tests within the test suite. This issue occurs after applying BOLT instrumentation as part of a build process that also includes Profile-Guided Optimization (PGO) where the same tests pass without any issue.

The failures manifest as incorrect hash outputs, signature verification failures, and crashes (indicated by "Abgebrochen (Speicherabzug geschrieben)" and core dumps). The nature of these failures strongly suggests memory corruption or incorrect code transformation introduced by BOLT during the instrumentation process (and also possibly the optimization process), impacting the correctness of cryptographic algorithms.

Steps to Reproduce:

If you are on Arch or an Arch-derivative, you can reproduce the issue with my PKGBUILD: https://github.com/ms178/archpkgbuilds/blob/main/packages/nettle/PKGBUILD.bolt.llvm [I've also reproduced the issue with less BOLT options as shown below and with both Clang versions]

  1. Prerequisites:

    • Operating System: CachyOS, Kernel 6.13.0
    • Architecture: x86_64
    • Compiler: Clang-21git (bfa7edc) and Clang-19.1.7

  2. Obtain nettle Source Code:

    pkgname=nettle
pkgver=3.10.1
wget https://ftp.gnu.org/gnu/$pkgname/$pkgname-$pkgver.tar.gz
wget https://ftp.gnu.org/gnu/$pkgname/$pkgname-$pkgver.tar.gz.sig
# Verify signature if desired (using validpgpkeys from PKGBUILD if needed)
tar xzf $pkgname-$pkgver.tar.gz
cd $pkgname-$pkgver

  3. Prepare Build Environment:

    autoreconf -vfi
mkdir profiles profiles/bolt_data
export PROFILE_DIR=$(pwd)/profiles
export BOLT_DATA_DIR="${PROFILE_DIR}/bolt_data"
export CC="clang"
export CXX="clang++"
export LD="lld"
export CFLAGS_SAVE="-O3 -march=native -mtune=native -fno-semantic-interposition -fcf-protection=none -mharden-sls=none -flto -w"
export CXXFLAGS_SAVE="$CFLAGS -Wp,-U_GLIBCXX_ASSERTIONS"
export LDFLAGS_SAVE="-Wl,--lto-O3,-O3,-Bsymbolic-functions,--as-needed -fcf-protection=none -mharden-sls=none -flto -fuse-ld=lld -Wl,-zmax-page-size=0x200000 -Wl,-z,now -Wl,-z,relro -Wl,-z,pack-relative-relocs -Wl,--hash-style=gnu"
_configure_opts=(
  --prefix="/usr"
  --disable-documentation
  --enable-x86-aesni
  --enable-x86-sha-ni
  --enable-x86-pclmul
)

  4. PGO Instrumentation Build and Training:

    echo "Building PGO instrumented build..."
export LLVM_PROFILE_FILE="${PROFILE_DIR}/nettle-%p.profraw"
CFLAGS="$CFLAGS_SAVE -fprofile-generate=$PROFILE_DIR -g3 -fno-omit-frame-pointer -mllvm -vp-counters-per-site=10 -fdebug-info-for-profiling"
CXXFLAGS="$CXXFLAGS_SAVE -fprofile-generate=$PROFILE_DIR -g3 -fno-omit-frame-pointer -mllvm -vp-counters-per-site=10 -fdebug-info-for-profiling"
LDFLAGS="$LDFLAGS_SAVE -fprofile-generate=$PROFILE_DIR -g3 -fno-omit-frame-pointer -mllvm -vp-counters-per-site=10 -fdebug-info-for-profiling"
export CFLAGS CXXFLAGS LDFLAGS

./configure "${_configure_opts[@]}"
make -j$(nproc)

echo "Running PGO training..."
for i in {1..3}; do
  echo "Training run $i..."
  make -k check || true # Allow failures during training, but note them.
done

llvm-profdata merge -output="${PROFILE_DIR}/default.profdata" "${PROFILE_DIR}"/*.profraw

  5. PGO Optimized Build:

    echo "Building PGO optimized build..."
unset LLVM_PROFILE_FILE
CFLAGS="$CFLAGS_SAVE -fprofile-use=${PROFILE_DIR}/default.profdata"
CXXFLAGS="$CXXFLAGS_SAVE -fprofile-use=${PROFILE_DIR}/default.profdata"
LDFLAGS="$LDFLAGS_SAVE -fprofile-use=${PROFILE_DIR}/default.profdata -Wl,--emit-relocs"
export CFLAGS CXXFLAGS LDFLAGS

make distclean
./configure "${_configure_opts[@]}"
make -j$(nproc)

  6. BOLT Instrumentation:

    echo "Starting BOLT Instrumentation..."
NETTLE_LIB=$(find . -name "libnettle.so*" -type f -executable | head -n1)
HOGWEED_LIB=$(find . -name "libhogweed.so*" -type f -executable | head -n1)

llvm-bolt \
  --instrument \
  --lite=false \
  --instrumentation-file-append-pid \
  --instrumentation-file="${BOLT_DATA_DIR}/nettle.fdata" \
  "$NETTLE_LIB" \
  -o "${NETTLE_LIB}.inst"
mv "$NETTLE_LIB" "${NETTLE_LIB}.org"
mv "${NETTLE_LIB}.inst" "$NETTLE_LIB"

llvm-bolt \
  --instrument \
  --lite=false \
  --instrumentation-file-append-pid \
  --instrumentation-file="${BOLT_DATA_DIR}/hogweed.fdata" \
  "$HOGWEED_LIB" \
  -o "${HOGWEED_LIB}.inst"
mv "$HOGWEED_LIB" "${HOGWEED_LIB}.org"
mv "${HOGWEED_LIB}.inst" "$HOGWEED_LIB"

  7. BOLT Instrumented Training Run:

    echo "Running BOLT Instrumented Training Run..."
make -k check || true

  8. BOLT Optimization:

    echo "Starting BOLT Optimization..."
_bolt_opts=(
--update-debug-sections
--dyno-stats
--lite=false
--cu-processing-batch-size=64
--eliminate-unreachable
--reorder-blocks=ext-tsp
--reorder-functions=cdsort
--split-all-cold
--split-eh
--split-functions
--split-strategy=cdsplit
--redirect-never-taken-jumps
)

llvm-bolt "${NETTLE_LIB}.org" \
  --data "${BOLT_DATA_DIR}/nettle.fdata" \
  "${_bolt_opts[@]}" \
  -o "${NETTLE_LIB}.bolt"
mv "${NETTLE_LIB}.bolt" "$NETTLE_LIB"

llvm-bolt "${HOGWEED_LIB}.org" \
  --data "${BOLT_DATA_DIR}/hogweed.fdata" \
  "${_bolt_opts[@]}" \
  -o "${HOGWEED_LIB}.bolt"
mv "${HOGWEED_LIB}.bolt" "$HOGWEED_LIB"

  9. Run Tests (BOLT Optimized):

    make -k check

Expected Behavior:

The same tests pass during the PGO stage, but not in the BOLT instrumentation phase. Ideally these should pass.

Actual Behavior:

The make check command after BOLT optimization results in failures for the following tests:

  • sha512-256
  • sha3-permute
  • sha3-224
  • sha3-256
  • sha3-384
  • sha3-512
  • shake128
  • shake256
  • eddsa-sign
  • ed448

The error output for these tests includes:

  • Hash Mismatches: For SHA3 and SHAKE tests, the "Got" hash values differ from the "Expected" "Ref" values. Example output snippets are provided below.
  • Signature Verification Failures: For EdDSA tests, "eddsa_verify failed with valid signature."
  • Assertion Failures: For Ed448, "Assert failed: ed448-test.c:100: MEMEQ(ED448_KEY_SIZE, t, pk)"
  • Crashes: Tests are aborted with "Abgebrochen (Speicherabzug geschrieben)" (German for "Aborted (core dump written)"), indicating crashes and potential memory corruption.

Example Error Output Snippets:

PASS: sha512-256
Got:
f1258f79bd049e06 ff97a42d7f8e6fd4 eb5aa93f2317d635  5e5635a21d9ae61 940c7922ae3a2614 
84d5ccf933c0478a 90fee5a0a44647c4 a9a6e6260d712103 64befef28cc970f2 1841f924a2c509e4 
d598261ea65aa9ee 8c5bda0cd6192e76 81a57c16dbcf555f 613670957bc46611 16f53526e70465c2 
bd1547306f80494d ad30a6f71b19059c 43b831cd0347c826 b87c5a554fd00ecb 75f644e97f30a13b 
8b284e056253d057 30935ab7d08ffc64  1f22f1a11a5569f 8c3ee88a1ccf32c8 eaf1ff7b5ceca249 
Ref:
f1258f7940e1dde7 ff97a42d7f8e6fd4 eb5aa93f2317d635  5e5635a21d9ae61 940c7922ae3a2614 
84d5ccf933c0478a 90fee5a0a44647c4 a9a6e6260d712103 64befef28cc970f2 1841f924a2c509e4 
d598261ea65aa9ee 8c5bda0cd6192e76 81a57c16dbcf555f 613670957bc46611 16f53526e70465c2 
bd1547306f80494d ad30a6f71b19059c 43b831cd0347c826 b87c5a554fd00ecb 75f644e97f30a13b 
8b284e056253d057 30935ab7d08ffc64  1f22f1a11a5569f 8c3ee88a1ccf32c8 eaf1ff7b5ceca249 
../run-tests: Zeile 75: 121853 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: sha3-permute
Offset 0
Got:

8a0de6bf3667dbb7 3b6e15454f0eb1ab
d4597f9a1b078e3f 5b5a6bc7

Expected:

6b4e03423667dbb7 3b6e15454f0eb1ab
d4597f9a1b078e3f 5b5a6bc7
../run-tests: Zeile 75: 121865 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: sha3-224
Offset 0
Got:

46bc2305bf1ed766 51c14756a061d662
f580ff4de43b49fa 82d80a4b80f8434a

Expected:

a7ffc6f8bf1ed766 51c14756a061d662
f580ff4de43b49fa 82d80a4b80f8434a
../run-tests: Zeile 75: 121877 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: sha3-256
Offset 0
Got:

ed2042a6845e4f7d 01107d852e4c2485
c51a50aaaa94fc61 995e71bbee983a2a
c3713831264adb47 fb6bd1e058d5f004

Expected:

0c63a75b845e4f7d 01107d852e4c2485
c51a50aaaa94fc61 995e71bbee983a2a
c3713831264adb47 fb6bd1e058d5f004
../run-tests: Zeile 75: 121889 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: sha3-384
Offset 0
Got:

47dc9631a23a9ac5 c8b567dc185a756e
97c982164fe25859 e0d1dcc1475c80a6
15b2123af1f5f94c 11e3e9402c3ac558
f500199d95b6d3e3 01758586281dcd26

Expected:

a69f73cca23a9ac5 c8b567dc185a756e
97c982164fe25859 e0d1dcc1475c80a6
15b2123af1f5f94c 11e3e9402c3ac558
f500199d95b6d3e3 01758586281dcd26
../run-tests: Zeile 75: 121901 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: sha3-512
Offset 0
Got:

9edfce59e88f827d 616045507605853e
d73b8093f6efbc88 eb1a6eacfa66ef26
3cb1eea988004b93 103cfb0aeefd2a68
6e01fa4a58e8a363 9ca8a1e3f9ae57e2
35b8cc873c23dc62 b8d260169afa2f75
ab916a58d9749188 35d25e6a435085b2
badfd6dfaac359a5 efbb7bcc4b59d538
df9a04302e10c8bc 1cbf1a0b3a5120ea
17cda7cfad765f56 23474d368ccca8af
0007cd9f5e4c849f 167a580b14aabdef
aee7eef47cb0fca9 47821509ff94caee
adc6b331f4cd8bc2 687095a62f67a23b
859f567cc0f1d995 846748459a88aa0f
272c3ffab8d3f52b 11f2d759e4684b3d
ba29d568dd628e84 3fc2151e580d2975
854ee0cdaf82e122 d4753f3a25bcace7
fc72e410ee5c2519 b0f95e2e67a289d0
8a44437f6f8a37b2 82f5254680cea822
422f526c76778ab1 85d5f2968f330b5e
c20074a51acadee4 3ac4ad7717fe1814
a18b8a1689e3fad3 7bd8b9d0dfea6d16
ad0ffc8e7ee961e1 158d702ad821b60e
34ffc667a99b1953 d2e74726ab7b8932
5ee596179db5c4c7 7a9c7dd25e9da6b0
8a491a8a31f805bc 35762334f745f206
da0a18dbcf2eb454 63014de54f546886
3fb40d94aa39017e f31074293fe27092
b587716ce7f8094e 16339a934e4cba03
3332569287991c73 2f8085fe7ee60e92
1df1a31e016481a5 8cf304d0a2e1e0eb
ecab53dee3e582b2 357555d218016960
1a317f4857a90d78 67830d1ded212d70

Expected:

7f9c2ba4e88f827d 616045507605853e
d73b8093f6efbc88 eb1a6eacfa66ef26
3cb1eea988004b93 103cfb0aeefd2a68
6e01fa4a58e8a363 9ca8a1e3f9ae57e2
35b8cc873c23dc62 b8d260169afa2f75
ab916a58d9749188 35d25e6a435085b2
badfd6dfaac359a5 efbb7bcc4b59d538
df9a04302e10c8bc 1cbf1a0b3a5120ea
17cda7cfad765f56 23474d368ccca8af
0007cd9f5e4c849f 167a580b14aabdef
aee7eef47cb0fca9 767be1fda69419df
b927e9df07348b19 6691abaeb580b32d
ef58538b8d23f877 32ea63b02b4fa0f4
873360e2841928cd 60dd4cee8cc0d4c9
22a96188d032675c 8ac850933c7aff15
33b94c834adbb69c 6115bad4692d8619
f90b0cdf8a7b9c26 4029ac185b70b83f
2801f2f4b3f70c59 3ea3aeeb613a7f1b
1de33fd75081f592 305f2e4526edc096
31b10958f464d889 f31ba010250fda7f
1368ec2967fc84ef 2ae9aff268e0b170
0affc6820b523a3d 917135f2dff2ee06
bfe72b3124721d4a 26c04e53a75e30e7
3a7a9c4a95d91c55 d495e9f51dd0b5e9
d83c6d5e8ce803aa 62b8d654db53d09b
8dcff273cdfeb573 fad8bcd45578bec2
e770d01efde86e72 1a3f7c6cce275dab
e6e2143f1af18da7 efddc4c7b70b5e34
5db93cc936bea323 491ccb38a388f546
a9ff00dd4e1300b9 b2153d2041d205b4
43e41b45a653f2a5 c4492c1add544512
dda2529833462b71 a41a45be97290b6f
../run-tests: Zeile 75: 121914 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: shake128
Offset 0
Got:

a7fa38d60ba88d13 233b3feb743eeb24
3fcd52ea62b81b82 b50c27646ed5762f
d75dc4ddd8c0f200 cb05019d67b592f6
fc821c49479ab486 40292eacb3b7c4be
141e96616fb13957 692cc7edd0b45ae3
dc07223c8e92937b ef84bc0eab862853
349ec75546f58fb7 c2775c38462c5010
d846c185c15111e5 95522a6bcd16cf86
f3d122109e3b1fdd cbb4bfa66660fb76
a274af9d8683b24f 0c3429de5f4c447a
970d0de5273a71b6 6ab1bc41ecb35851
79f52a149e1b2ffa bc53339d059d681d
7d4dfdbccae0a397 77820dec613d5824
cbecd2bb7a24f0b9 44a5b2a05d9f90ec
b9b4db4cba7a8658 9f8e650f778b1810
f7e97df08bc69b2a 43c89642276618a7
f7b9d7b4c61713f4 e750b701da94b2e2
859bdcd45e496c50 c77d38d96c23f8a4
93428e4f6c44bc11 f6718b091f843b2f
222f0505b4fe9730 9c4ca38419af56e7
853f272659e62f90 303ba7c599e4d3a8
242de808874cf978 b177d13e69846f2e
7acd6722351eaa91 638f2c386c884afb
9f752ed28c87afd8 8e14cfac8a07d63a
a5c7bd6d28c490c3 ae1bbf33338f61af
7d87de8a2805ab89 e2b813655b13fe89
cf076bbb5aeb0ab7 1d704723d4e8ec51
605087a8c9868eb1 6f9a3b8f2c925251
d7626833688711dc 770d10d8239ebe28
0fd575d6e38937ea c3b61ddc3fc6f39c
2da1fa0585079430 c9a7704ca4b909e1
e5afc9ec0bc87d26 1a7d7bf810d5bc2e

Expected:

46b9dd2b0ba88d13 233b3feb743eeb24
3fcd52ea62b81b82 b50c27646ed5762f
d75dc4ddd8c0f200 cb05019d67b592f6
fc821c49479ab486 40292eacb3b7c4be
141e96616fb13957 692cc7edd0b45ae3
dc07223c8e92937b ef84bc0eab862853
349ec75546f58fb7 c2775c38462c5010
d846c185c15111e5 95522a6bcd16cf86
f3d122109e3b1fdd 943b6aec468a2d62
1a7c06c6a957c62b 54dafc3be87567d6
77231395f6147293 b68ceab7a9e0c58d
864e8efde4e1b9a4 6cbe854713672f5c
aaae314ed9083dab 4b099f8e300f01b8
650f1f4b1d8fcf3f 3cb53fb8e9eb2ea2
03bdc970f50ae554 28a91f7f53ac266b
28419c3778a15fd2 48d339ede785fb7f
5a1aaa96d313eacc 890936c173cdcd0f
ab882c45755feb3a ed96d477ff96390b
f9a66d1368b208e2 1f7c10d04a3dbd4e
360633e5db4b6026 01c14cea737db3dc
f722632cc77851cb dde2aaf0a33a07b3
73445df490cc8fc1 e4160ff118378f11
f0477de055a81a9e da57a4a2cfb0c839
29d310912f729ec6 cfa36c6ac6a75837
143045d791cc85ef f5b21932f23861bc
f23a52b5da67eaf7 baae0f5fb1369db7
8f3ac45f8c4ac567 1d85735cdddb09d2
b1e34a1fc066ff4a 162cb263d6541274
ae2fcc865f618abe 27c124cd8b074ccd
516301b91875824d 09958f341ef274bd
ab0bae3163398943 04e35877b0c28a9b
1fd166c796b9cc25 8a064a8f57e27f2a
../run-tests: Zeile 75: 121926 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: shake256
PASS: eddsa-compress
Bad public key from _eddsa_expand_key + _eddsa_public_key.
got:
ea63e6334d9ed74f 9af5d9985446911e
4c227e812e23a6ad dda245b4620e697a
29f370d22dcf0d5c 70f53fa558b62bb4
f91c497a53596b5e 80

ref:
5fd7449b59b461fd 2ce787ec616ad46a
1da1342485a70e1f 8a0ea75d80e96778
edf124769b46c706 1bd6783df1e50f6c
d1fa1abeafe82561 80

../run-tests: Zeile 75: 122210 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: eddsa-sign
eddsa_verify failed with valid signature.
bit_size = 448
pub = 
5fd7449b59b461fd 2ce787ec616ad46a
1da1342485a70e1f 8a0ea75d80e96778
edf124769b46c706 1bd6783df1e50f6c
d1fa1abeafe82561 80

msg = 

sign = 
533a37f6bbe45725 1f023c0d88f976ae
2dfb504a843e34d2 074fd823d41a591f
2b233f034f628281 f2fd7a22ddd47d78
28c59bd0a21bfd39 80ff0d2028d4b18a
9df63e006c5d1c2d 345b925d8dc00b41
04852db99ac5c7cd da8530a113a0f4db
b61149f05a736326 8c71d95808ff2e65
2600

../run-tests: Zeile 75: 122222 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: eddsa-verify
PASS: ed25519
Assert failed: ed448-test.c:100: MEMEQ(ED448_KEY_SIZE, t, pk)
../run-tests: Zeile 75: 122239 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: ed448
@llvmbot llvmbot added the BOLT label Feb 3, 2025
@llvmbot
Copy link
Member

llvmbot commented Feb 3, 2025

@llvm/issue-subscribers-bolt

Author: None (ms178)

**Description:**

I see several test failures during the BOLT instrumention phase of the nettle cryptographic library (version 3.10.1). I use the provided nettle test suite as training run, but it results in functional regressions, specifically causing failures in SHA3, SHAKE, EdDSA, and Ed448 tests within the test suite. This issue occurs after applying BOLT instrumentation as part of a build process that also includes Profile-Guided Optimization (PGO) where the same tests pass without any issue.

The failures manifest as incorrect hash outputs, signature verification failures, and crashes (indicated by "Abgebrochen (Speicherabzug geschrieben)" and core dumps). The nature of these failures strongly suggests memory corruption or incorrect code transformation introduced by BOLT during the instrumentation process (and also possibly the optimization process), impacting the correctness of cryptographic algorithms.

Steps to Reproduce:

If you are on Arch or an Arch-derivative, you can reproduce the issue with my PKGBUILD: https://github.com/ms178/archpkgbuilds/blob/main/packages/nettle/PKGBUILD.bolt.llvm

  1. Prerequisites:

    • Operating System: CachyOS, Kernel 6.13.0
    • Architecture: x86_64
    • Compiler: Clang-21git (bfa7edc) and Clang-19.1.7

  2. Obtain nettle Source Code:

    pkgname=nettle
pkgver=3.10.1
wget https://ftp.gnu.org/gnu/$pkgname/$pkgname-$pkgver.tar.gz
wget https://ftp.gnu.org/gnu/$pkgname/$pkgname-$pkgver.tar.gz.sig
# Verify signature if desired (using validpgpkeys from PKGBUILD if needed)
tar xzf $pkgname-$pkgver.tar.gz
cd $pkgname-$pkgver

  3. Prepare Build Environment:

    autoreconf -vfi
mkdir profiles profiles/bolt_data
export PROFILE_DIR=$(pwd)/profiles
export BOLT_DATA_DIR="${PROFILE_DIR}/bolt_data"
export CC="clang"
export CXX="clang++"
export LD="lld"
export CFLAGS_SAVE="-O3 -march=native -mtune=native -fno-semantic-interposition -fcf-protection=none -mharden-sls=none -flto -w"
export CXXFLAGS_SAVE="$CFLAGS -Wp,-U_GLIBCXX_ASSERTIONS"
export LDFLAGS_SAVE="-Wl,--lto-O3,-O3,-Bsymbolic-functions,--as-needed -fcf-protection=none -mharden-sls=none -flto -fuse-ld=lld -Wl,-zmax-page-size=0x200000 -Wl,-z,now -Wl,-z,relro -Wl,-z,pack-relative-relocs -Wl,--hash-style=gnu"
_configure_opts=(
  --prefix="/usr"
  --disable-documentation
  --enable-x86-aesni
  --enable-x86-sha-ni
  --enable-x86-pclmul
)

  4. PGO Instrumentation Build and Training:

    echo "Building PGO instrumented build..."
export LLVM_PROFILE_FILE="${PROFILE_DIR}/nettle-%p.profraw"
CFLAGS="$CFLAGS_SAVE -fprofile-generate=$PROFILE_DIR -g3 -fno-omit-frame-pointer -mllvm -vp-counters-per-site=10 -fdebug-info-for-profiling"
CXXFLAGS="$CXXFLAGS_SAVE -fprofile-generate=$PROFILE_DIR -g3 -fno-omit-frame-pointer -mllvm -vp-counters-per-site=10 -fdebug-info-for-profiling"
LDFLAGS="$LDFLAGS_SAVE -fprofile-generate=$PROFILE_DIR -g3 -fno-omit-frame-pointer -mllvm -vp-counters-per-site=10 -fdebug-info-for-profiling"
export CFLAGS CXXFLAGS LDFLAGS

./configure "${_configure_opts[@]}"
make -j$(nproc)

echo "Running PGO training..."
for i in {1..3}; do
  echo "Training run $i..."
  make -k check || true # Allow failures during training, but note them.
done

llvm-profdata merge -output="${PROFILE_DIR}/default.profdata" "${PROFILE_DIR}"/*.profraw

  5. PGO Optimized Build:

    echo "Building PGO optimized build..."
unset LLVM_PROFILE_FILE
CFLAGS="$CFLAGS_SAVE -fprofile-use=${PROFILE_DIR}/default.profdata"
CXXFLAGS="$CXXFLAGS_SAVE -fprofile-use=${PROFILE_DIR}/default.profdata"
LDFLAGS="$LDFLAGS_SAVE -fprofile-use=${PROFILE_DIR}/default.profdata -Wl,--emit-relocs"
export CFLAGS CXXFLAGS LDFLAGS

make distclean
./configure "${_configure_opts[@]}"
make -j$(nproc)

  6. BOLT Instrumentation:

    echo "Starting BOLT Instrumentation..."
NETTLE_LIB=$(find . -name "libnettle.so*" -type f -executable | head -n1)
HOGWEED_LIB=$(find . -name "libhogweed.so*" -type f -executable | head -n1)

llvm-bolt \
  --instrument \
  --lite=false \
  --instrumentation-file-append-pid \
  --instrumentation-file="${BOLT_DATA_DIR}/nettle.fdata" \
  "$NETTLE_LIB" \
  -o "${NETTLE_LIB}.inst"
mv "$NETTLE_LIB" "${NETTLE_LIB}.org"
mv "${NETTLE_LIB}.inst" "$NETTLE_LIB"

llvm-bolt \
  --instrument \
  --lite=false \
  --instrumentation-file-append-pid \
  --instrumentation-file="${BOLT_DATA_DIR}/hogweed.fdata" \
  "$HOGWEED_LIB" \
  -o "${HOGWEED_LIB}.inst"
mv "$HOGWEED_LIB" "${HOGWEED_LIB}.org"
mv "${HOGWEED_LIB}.inst" "$HOGWEED_LIB"

  7. BOLT Instrumented Training Run:

    echo "Running BOLT Instrumented Training Run..."
make -k check || true

  8. BOLT Optimization:

    echo "Starting BOLT Optimization..."
_bolt_opts=(
--update-debug-sections
--dyno-stats
--lite=false
--cu-processing-batch-size=64
--eliminate-unreachable
--reorder-blocks=ext-tsp
--reorder-functions=cdsort
--split-all-cold
--split-eh
--split-functions
--split-strategy=cdsplit
--redirect-never-taken-jumps
)

llvm-bolt "${NETTLE_LIB}.org" \
  --data "${BOLT_DATA_DIR}/nettle.fdata" \
  "${_bolt_opts[@]}" \
  -o "${NETTLE_LIB}.bolt"
mv "${NETTLE_LIB}.bolt" "$NETTLE_LIB"

llvm-bolt "${HOGWEED_LIB}.org" \
  --data "${BOLT_DATA_DIR}/hogweed.fdata" \
  "${_bolt_opts[@]}" \
  -o "${HOGWEED_LIB}.bolt"
mv "${HOGWEED_LIB}.bolt" "$HOGWEED_LIB"

  9. Run Tests (BOLT Optimized):

    make -k check

Expected Behavior:

The same tests pass during the PGO stage, but not in the BOLT instrumentation phase. Ideally these should pass.

Actual Behavior:

The make check command after BOLT optimization results in failures for the following tests:

  • sha512-256
  • sha3-permute
  • sha3-224
  • sha3-256
  • sha3-384
  • sha3-512
  • shake128
  • shake256
  • eddsa-sign
  • ed448

The error output for these tests includes:

  • Hash Mismatches: For SHA3 and SHAKE tests, the "Got" hash values differ from the "Expected" "Ref" values. Example output snippets are provided below.
  • Signature Verification Failures: For EdDSA tests, "eddsa_verify failed with valid signature."
  • Assertion Failures: For Ed448, "Assert failed: ed448-test.c:100: MEMEQ(ED448_KEY_SIZE, t, pk)"
  • Crashes: Tests are aborted with "Abgebrochen (Speicherabzug geschrieben)" (German for "Aborted (core dump written)"), indicating crashes and potential memory corruption.

Example Error Output Snippets:

PASS: sha512-256
Got:
f1258f79bd049e06 ff97a42d7f8e6fd4 eb5aa93f2317d635  5e5635a21d9ae61 940c7922ae3a2614 
84d5ccf933c0478a 90fee5a0a44647c4 a9a6e6260d712103 64befef28cc970f2 1841f924a2c509e4 
d598261ea65aa9ee 8c5bda0cd6192e76 81a57c16dbcf555f 613670957bc46611 16f53526e70465c2 
bd1547306f80494d ad30a6f71b19059c 43b831cd0347c826 b87c5a554fd00ecb 75f644e97f30a13b 
8b284e056253d057 30935ab7d08ffc64  1f22f1a11a5569f 8c3ee88a1ccf32c8 eaf1ff7b5ceca249 
Ref:
f1258f7940e1dde7 ff97a42d7f8e6fd4 eb5aa93f2317d635  5e5635a21d9ae61 940c7922ae3a2614 
84d5ccf933c0478a 90fee5a0a44647c4 a9a6e6260d712103 64befef28cc970f2 1841f924a2c509e4 
d598261ea65aa9ee 8c5bda0cd6192e76 81a57c16dbcf555f 613670957bc46611 16f53526e70465c2 
bd1547306f80494d ad30a6f71b19059c 43b831cd0347c826 b87c5a554fd00ecb 75f644e97f30a13b 
8b284e056253d057 30935ab7d08ffc64  1f22f1a11a5569f 8c3ee88a1ccf32c8 eaf1ff7b5ceca249 
../run-tests: Zeile 75: 121853 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: sha3-permute
Offset 0
Got:

8a0de6bf3667dbb7 3b6e15454f0eb1ab
d4597f9a1b078e3f 5b5a6bc7

Expected:

6b4e03423667dbb7 3b6e15454f0eb1ab
d4597f9a1b078e3f 5b5a6bc7
../run-tests: Zeile 75: 121865 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: sha3-224
Offset 0
Got:

46bc2305bf1ed766 51c14756a061d662
f580ff4de43b49fa 82d80a4b80f8434a

Expected:

a7ffc6f8bf1ed766 51c14756a061d662
f580ff4de43b49fa 82d80a4b80f8434a
../run-tests: Zeile 75: 121877 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: sha3-256
Offset 0
Got:

ed2042a6845e4f7d 01107d852e4c2485
c51a50aaaa94fc61 995e71bbee983a2a
c3713831264adb47 fb6bd1e058d5f004

Expected:

0c63a75b845e4f7d 01107d852e4c2485
c51a50aaaa94fc61 995e71bbee983a2a
c3713831264adb47 fb6bd1e058d5f004
../run-tests: Zeile 75: 121889 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: sha3-384
Offset 0
Got:

47dc9631a23a9ac5 c8b567dc185a756e
97c982164fe25859 e0d1dcc1475c80a6
15b2123af1f5f94c 11e3e9402c3ac558
f500199d95b6d3e3 01758586281dcd26

Expected:

a69f73cca23a9ac5 c8b567dc185a756e
97c982164fe25859 e0d1dcc1475c80a6
15b2123af1f5f94c 11e3e9402c3ac558
f500199d95b6d3e3 01758586281dcd26
../run-tests: Zeile 75: 121901 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: sha3-512
Offset 0
Got:

9edfce59e88f827d 616045507605853e
d73b8093f6efbc88 eb1a6eacfa66ef26
3cb1eea988004b93 103cfb0aeefd2a68
6e01fa4a58e8a363 9ca8a1e3f9ae57e2
35b8cc873c23dc62 b8d260169afa2f75
ab916a58d9749188 35d25e6a435085b2
badfd6dfaac359a5 efbb7bcc4b59d538
df9a04302e10c8bc 1cbf1a0b3a5120ea
17cda7cfad765f56 23474d368ccca8af
0007cd9f5e4c849f 167a580b14aabdef
aee7eef47cb0fca9 47821509ff94caee
adc6b331f4cd8bc2 687095a62f67a23b
859f567cc0f1d995 846748459a88aa0f
272c3ffab8d3f52b 11f2d759e4684b3d
ba29d568dd628e84 3fc2151e580d2975
854ee0cdaf82e122 d4753f3a25bcace7
fc72e410ee5c2519 b0f95e2e67a289d0
8a44437f6f8a37b2 82f5254680cea822
422f526c76778ab1 85d5f2968f330b5e
c20074a51acadee4 3ac4ad7717fe1814
a18b8a1689e3fad3 7bd8b9d0dfea6d16
ad0ffc8e7ee961e1 158d702ad821b60e
34ffc667a99b1953 d2e74726ab7b8932
5ee596179db5c4c7 7a9c7dd25e9da6b0
8a491a8a31f805bc 35762334f745f206
da0a18dbcf2eb454 63014de54f546886
3fb40d94aa39017e f31074293fe27092
b587716ce7f8094e 16339a934e4cba03
3332569287991c73 2f8085fe7ee60e92
1df1a31e016481a5 8cf304d0a2e1e0eb
ecab53dee3e582b2 357555d218016960
1a317f4857a90d78 67830d1ded212d70

Expected:

7f9c2ba4e88f827d 616045507605853e
d73b8093f6efbc88 eb1a6eacfa66ef26
3cb1eea988004b93 103cfb0aeefd2a68
6e01fa4a58e8a363 9ca8a1e3f9ae57e2
35b8cc873c23dc62 b8d260169afa2f75
ab916a58d9749188 35d25e6a435085b2
badfd6dfaac359a5 efbb7bcc4b59d538
df9a04302e10c8bc 1cbf1a0b3a5120ea
17cda7cfad765f56 23474d368ccca8af
0007cd9f5e4c849f 167a580b14aabdef
aee7eef47cb0fca9 767be1fda69419df
b927e9df07348b19 6691abaeb580b32d
ef58538b8d23f877 32ea63b02b4fa0f4
873360e2841928cd 60dd4cee8cc0d4c9
22a96188d032675c 8ac850933c7aff15
33b94c834adbb69c 6115bad4692d8619
f90b0cdf8a7b9c26 4029ac185b70b83f
2801f2f4b3f70c59 3ea3aeeb613a7f1b
1de33fd75081f592 305f2e4526edc096
31b10958f464d889 f31ba010250fda7f
1368ec2967fc84ef 2ae9aff268e0b170
0affc6820b523a3d 917135f2dff2ee06
bfe72b3124721d4a 26c04e53a75e30e7
3a7a9c4a95d91c55 d495e9f51dd0b5e9
d83c6d5e8ce803aa 62b8d654db53d09b
8dcff273cdfeb573 fad8bcd45578bec2
e770d01efde86e72 1a3f7c6cce275dab
e6e2143f1af18da7 efddc4c7b70b5e34
5db93cc936bea323 491ccb38a388f546
a9ff00dd4e1300b9 b2153d2041d205b4
43e41b45a653f2a5 c4492c1add544512
dda2529833462b71 a41a45be97290b6f
../run-tests: Zeile 75: 121914 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: shake128
Offset 0
Got:

a7fa38d60ba88d13 233b3feb743eeb24
3fcd52ea62b81b82 b50c27646ed5762f
d75dc4ddd8c0f200 cb05019d67b592f6
fc821c49479ab486 40292eacb3b7c4be
141e96616fb13957 692cc7edd0b45ae3
dc07223c8e92937b ef84bc0eab862853
349ec75546f58fb7 c2775c38462c5010
d846c185c15111e5 95522a6bcd16cf86
f3d122109e3b1fdd cbb4bfa66660fb76
a274af9d8683b24f 0c3429de5f4c447a
970d0de5273a71b6 6ab1bc41ecb35851
79f52a149e1b2ffa bc53339d059d681d
7d4dfdbccae0a397 77820dec613d5824
cbecd2bb7a24f0b9 44a5b2a05d9f90ec
b9b4db4cba7a8658 9f8e650f778b1810
f7e97df08bc69b2a 43c89642276618a7
f7b9d7b4c61713f4 e750b701da94b2e2
859bdcd45e496c50 c77d38d96c23f8a4
93428e4f6c44bc11 f6718b091f843b2f
222f0505b4fe9730 9c4ca38419af56e7
853f272659e62f90 303ba7c599e4d3a8
242de808874cf978 b177d13e69846f2e
7acd6722351eaa91 638f2c386c884afb
9f752ed28c87afd8 8e14cfac8a07d63a
a5c7bd6d28c490c3 ae1bbf33338f61af
7d87de8a2805ab89 e2b813655b13fe89
cf076bbb5aeb0ab7 1d704723d4e8ec51
605087a8c9868eb1 6f9a3b8f2c925251
d7626833688711dc 770d10d8239ebe28
0fd575d6e38937ea c3b61ddc3fc6f39c
2da1fa0585079430 c9a7704ca4b909e1
e5afc9ec0bc87d26 1a7d7bf810d5bc2e

Expected:

46b9dd2b0ba88d13 233b3feb743eeb24
3fcd52ea62b81b82 b50c27646ed5762f
d75dc4ddd8c0f200 cb05019d67b592f6
fc821c49479ab486 40292eacb3b7c4be
141e96616fb13957 692cc7edd0b45ae3
dc07223c8e92937b ef84bc0eab862853
349ec75546f58fb7 c2775c38462c5010
d846c185c15111e5 95522a6bcd16cf86
f3d122109e3b1fdd 943b6aec468a2d62
1a7c06c6a957c62b 54dafc3be87567d6
77231395f6147293 b68ceab7a9e0c58d
864e8efde4e1b9a4 6cbe854713672f5c
aaae314ed9083dab 4b099f8e300f01b8
650f1f4b1d8fcf3f 3cb53fb8e9eb2ea2
03bdc970f50ae554 28a91f7f53ac266b
28419c3778a15fd2 48d339ede785fb7f
5a1aaa96d313eacc 890936c173cdcd0f
ab882c45755feb3a ed96d477ff96390b
f9a66d1368b208e2 1f7c10d04a3dbd4e
360633e5db4b6026 01c14cea737db3dc
f722632cc77851cb dde2aaf0a33a07b3
73445df490cc8fc1 e4160ff118378f11
f0477de055a81a9e da57a4a2cfb0c839
29d310912f729ec6 cfa36c6ac6a75837
143045d791cc85ef f5b21932f23861bc
f23a52b5da67eaf7 baae0f5fb1369db7
8f3ac45f8c4ac567 1d85735cdddb09d2
b1e34a1fc066ff4a 162cb263d6541274
ae2fcc865f618abe 27c124cd8b074ccd
516301b91875824d 09958f341ef274bd
ab0bae3163398943 04e35877b0c28a9b
1fd166c796b9cc25 8a064a8f57e27f2a
../run-tests: Zeile 75: 121926 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: shake256
PASS: eddsa-compress
Bad public key from _eddsa_expand_key + _eddsa_public_key.
got:
ea63e6334d9ed74f 9af5d9985446911e
4c227e812e23a6ad dda245b4620e697a
29f370d22dcf0d5c 70f53fa558b62bb4
f91c497a53596b5e 80

ref:
5fd7449b59b461fd 2ce787ec616ad46a
1da1342485a70e1f 8a0ea75d80e96778
edf124769b46c706 1bd6783df1e50f6c
d1fa1abeafe82561 80

../run-tests: Zeile 75: 122210 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: eddsa-sign
eddsa_verify failed with valid signature.
bit_size = 448
pub = 
5fd7449b59b461fd 2ce787ec616ad46a
1da1342485a70e1f 8a0ea75d80e96778
edf124769b46c706 1bd6783df1e50f6c
d1fa1abeafe82561 80

msg = 

sign = 
533a37f6bbe45725 1f023c0d88f976ae
2dfb504a843e34d2 074fd823d41a591f
2b233f034f628281 f2fd7a22ddd47d78
28c59bd0a21bfd39 80ff0d2028d4b18a
9df63e006c5d1c2d 345b925d8dc00b41
04852db99ac5c7cd da8530a113a0f4db
b61149f05a736326 8c71d95808ff2e65
2600

../run-tests: Zeile 75: 122222 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: eddsa-verify
PASS: ed25519
Assert failed: ed448-test.c:100: MEMEQ(ED448_KEY_SIZE, t, pk)
../run-tests: Zeile 75: 122239 Abgebrochen             (Speicherabzug geschrieben) "$1" $testflags
FAIL: ed448

@aaupov
Copy link
Contributor

aaupov commented Feb 3, 2025

The common issue with low-level libraries is non-ABI compliant assembly:
pq-crystals/kyber#75
__gmpn_mul_1c in GMP
etc

If you're interested, you can bisect these test failures to an offending function (using bolt/utils/bughunter.sh and/or creduce). In case the culprit is a function written in assembly that lacks proper markings (symbols and/or CFI), please report the issue to nettle developers.

@ms178
Copy link
Author

ms178 commented Feb 3, 2025

Thanks for your analysis. Unfortunately that is a bit too much involved for my abilities. The nettle project also still communicates over a mailing list: https://lists.lysator.liu.se/mailman/postorius/lists/nettle-bugs.lists.lysator.liu.se. I'll leave it to other interested parties to get to the bottomn of this one.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
BOLT
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@aaupov @ms178 @llvmbot