Unit tests hangs when it comes to bigint_unit

[xyproto]

Hi,

I'm maintaining the botan package for Arch Linux. My goal is to upgrade the botan package to 2.5.0. Botan builds fine, but there were issues with the unit test:

./botan-test completely freezes/hangs when it comes to bigint_unit.

This is with botan 2.5.0, on 64-bit Arch Linux, GCC 7.3.1.

Configure/build commands:

./configure.py --prefix=/usr
make

Test command:

./botan-test

Last 10 lines of the unittest output:

Base64 ran 64 tests in 0.08 msec all ok
bc_pad:
ESP ran 15 tests in 0.01 msec all ok
NoPadding ran 10 tests in 0.01 msec all ok
OneAndZeros ran 13 tests in 0.01 msec all ok
PKCS7 ran 12 tests in 0.01 msec all ok
X9.23 ran 13 tests in 0.01 msec all ok
bcrypt:
bcrypt ran 367 tests in 2.15 sec all ok
bigint_unit:

Then it just hangs. I waited an hour before stopping the process.

I ran the tests on two different systems, for good measure.

Thanks for developing and maintaining botan.

Cheers!

[mgierlings]

Hi xyproto,

thanks for the report, I'm just running the tests in a loop on my machine

# uname -smr && gcc --version
Linux 4.15.14-1-ARCH x86_64
gcc (GCC) 7.3.1 20180312

unfortunately I haven't been able to reproduce the issue so far. Maybe you can help to track down the issue by providing some additional infomation:

1. The full output of these commands:

   ./configure.py
   cat /proc/cpuinfo
   uname -smr && gcc --version

2. Please try and compile botan executing the following commands, and post any error messages you may see.

   export ASAN_SYMBOLIZER_PATH=/usr/bin/llvm-symbolizer
   export ASAN_OPTIONS=symbolize=1:abort_on_error=1
   export UBSAN_OPTIONS=print_stacktrace=1
   ./configure.py --with-debug-info --enable-sanitizers=address,undefined --cxxflags="-g -O3 -fno-omit-frame-pointer"
   make
   ./botan-test

[xyproto]

Sure, here's the full output for the first commands (1.):

   INFO: ./configure.py invoked with options ""
   INFO: Autodetected platform information: OS="Linux" machine="x86_64" proc=""
   INFO: Guessing target OS is linux (use --os to set)
   INFO: Guessing to use compiler gcc (use --cc or CXX to set)
   INFO: Guessing target processor is a x86_64 (use --cpu to set)
   INFO: Auto-detected compiler version 7.3
   INFO: Auto-detected compiler arch x86_64
   INFO: Target is gcc:7.3-linux-x86_64
   INFO: Skipping (dependency failure): certstor_sqlite3 sessions_sqlite3
   INFO: Skipping (incompatible CPU): aes_power8
   INFO: Skipping (incompatible OS): darwin_secrandom getentropy win32_stats
   INFO: Skipping (incompatible compiler): aes_armv8 pmull sha1_armv8 sha2_32_armv8
   INFO: Skipping (no enabled compression schemes): compression
   INFO: Skipping (requires external dependency): bearssl boost bzip2 lzma openssl sqlite3 tpm zlib
   INFO: Loading modules: adler32 aead aes aes_ni aes_ssse3 aont aria asn1 auto_rng base base64 bcrypt bigint blake2 block blowfish camellia cascade cast cbc cbc_mac ccm cecpq1 certstor_sql cfb chacha chacha20poly1305 chacha_rng chacha_sse2 checksum clmul clmul_ssse3 cmac codec_filt comb4p cpuid crc24 crc32 cryptobox ctr curve25519 des dev_random dh dl_algo dl_group dlies dsa dyn_load eax ec_group ecc_key ecdh ecdsa ecgdsa ecies eckcdsa ed25519 elgamal eme_oaep eme_pkcs1 eme_raw emsa1 emsa_pkcs1 emsa_pssr emsa_raw emsa_x931 entropy fd_unix ffi filters fpe_fe1 gcm gmac gost_28147 gost_3410 gost_3411 hash hash_id hex hkdf hmac hmac_drbg hotp http_util idea idea_sse2 iso9796 kasumi kdf kdf1 kdf1_iso18033 kdf2 keccak keypair lion locking_allocator mac mce mceies md4 md5 mdx_hash mem_pool mgf1 misty1 mode_pad modes mp newhope nist_keywrap noekeon noekeon_simd numbertheory ocb ofb par_hash passhash9 pbes2 pbkdf pbkdf1 pbkdf2 pem pgp_s2k pk_pad pkcs11 poly1305 poly_dbl prf_tls prf_x942 proc_walk psk_db pubkey rc4 rdrand rdrand_rng rdseed rfc3394 rfc6979 rmd160 rng rsa salsa20 seed serpent serpent_simd sessions_sql sha1 sha1_sse2 sha1_x86 sha2_32 sha2_32_x86 sha2_64 sha3 shacal2 shacal2_simd shacal2_x86 shake shake_cipher simd siphash siv skein sm2 sm3 sm4 socket sp800_108 sp800_56a sp800_56c srp6 stateful_rng stream streebog system_rng thread_utils threefish_512 threefish_512_avx2 tiger tls tls_cbc tss twofish utils whirlpool x509 x919_mac xmss xtea xts
   INFO: Defaulting to assuming little endian
   INFO: Using symlink to link files into build dir (use --link-method to change)
   INFO: Botan 2.5.0 (revision git:c1e5b7193c493ec3d8946fadeb89c05c912b10c5) (release dated 20180402) build setup is complete
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 60
model name      : Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
stepping        : 3
microcode       : 0x24
cpu MHz         : 3188.286
cache size      : 8192 KB
physical id     : 0
siblings        : 8
core id         : 0
cpu cores       : 4
apicid          : 0
initial apicid  : 0
fpu             : yes
fpu_exception   : yes
cpuid level     : 13
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt ibpb ibrs stibp dtherm ida arat pln pts
bugs            : cpu_meltdown spectre_v1 spectre_v2
bogomips        : 7183.44
clflush size    : 64
cache_alignment : 64
address sizes   : 39 bits physical, 48 bits virtual
power management:

processor       : 1
vendor_id       : GenuineIntel
cpu family      : 6
model           : 60
model name      : Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
stepping        : 3
microcode       : 0x24
cpu MHz         : 2907.391
cache size      : 8192 KB
physical id     : 0
siblings        : 8
core id         : 1
cpu cores       : 4
apicid          : 2
initial apicid  : 2
fpu             : yes
fpu_exception   : yes
cpuid level     : 13
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt ibpb ibrs stibp dtherm ida arat pln pts
bugs            : cpu_meltdown spectre_v1 spectre_v2
bogomips        : 7183.44
clflush size    : 64
cache_alignment : 64
address sizes   : 39 bits physical, 48 bits virtual
power management:

processor       : 2
vendor_id       : GenuineIntel
cpu family      : 6
model           : 60
model name      : Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
stepping        : 3
microcode       : 0x24
cpu MHz         : 2898.405
cache size      : 8192 KB
physical id     : 0
siblings        : 8
core id         : 2
cpu cores       : 4
apicid          : 4
initial apicid  : 4
fpu             : yes
fpu_exception   : yes
cpuid level     : 13
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt ibpb ibrs stibp dtherm ida arat pln pts
bugs            : cpu_meltdown spectre_v1 spectre_v2
bogomips        : 7183.44
clflush size    : 64
cache_alignment : 64
address sizes   : 39 bits physical, 48 bits virtual
power management:

processor       : 3
vendor_id       : GenuineIntel
cpu family      : 6
model           : 60
model name      : Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
stepping        : 3
microcode       : 0x24
cpu MHz         : 2928.645
cache size      : 8192 KB
physical id     : 0
siblings        : 8
core id         : 3
cpu cores       : 4
apicid          : 6
initial apicid  : 6
fpu             : yes
fpu_exception   : yes
cpuid level     : 13
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt ibpb ibrs stibp dtherm ida arat pln pts
bugs            : cpu_meltdown spectre_v1 spectre_v2
bogomips        : 7183.44
clflush size    : 64
cache_alignment : 64
address sizes   : 39 bits physical, 48 bits virtual
power management:

processor       : 4
vendor_id       : GenuineIntel
cpu family      : 6
model           : 60
model name      : Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
stepping        : 3
microcode       : 0x24
cpu MHz         : 2911.909
cache size      : 8192 KB
physical id     : 0
siblings        : 8
core id         : 0
cpu cores       : 4
apicid          : 1
initial apicid  : 1
fpu             : yes
fpu_exception   : yes
cpuid level     : 13
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt ibpb ibrs stibp dtherm ida arat pln pts
bugs            : cpu_meltdown spectre_v1 spectre_v2
bogomips        : 7183.44
clflush size    : 64
cache_alignment : 64
address sizes   : 39 bits physical, 48 bits virtual
power management:

processor       : 5
vendor_id       : GenuineIntel
cpu family      : 6
model           : 60
model name      : Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
stepping        : 3
microcode       : 0x24
cpu MHz         : 3010.347
cache size      : 8192 KB
physical id     : 0
siblings        : 8
core id         : 1
cpu cores       : 4
apicid          : 3
initial apicid  : 3
fpu             : yes
fpu_exception   : yes
cpuid level     : 13
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt ibpb ibrs stibp dtherm ida arat pln pts
bugs            : cpu_meltdown spectre_v1 spectre_v2
bogomips        : 7183.44
clflush size    : 64
cache_alignment : 64
address sizes   : 39 bits physical, 48 bits virtual
power management:

processor       : 6
vendor_id       : GenuineIntel
cpu family      : 6
model           : 60
model name      : Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
stepping        : 3
microcode       : 0x24
cpu MHz         : 3038.054
cache size      : 8192 KB
physical id     : 0
siblings        : 8
core id         : 2
cpu cores       : 4
apicid          : 5
initial apicid  : 5
fpu             : yes
fpu_exception   : yes
cpuid level     : 13
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt ibpb ibrs stibp dtherm ida arat pln pts
bugs            : cpu_meltdown spectre_v1 spectre_v2
bogomips        : 7183.44
clflush size    : 64
cache_alignment : 64
address sizes   : 39 bits physical, 48 bits virtual
power management:

processor       : 7
vendor_id       : GenuineIntel
cpu family      : 6
model           : 60
model name      : Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
stepping        : 3
microcode       : 0x24
cpu MHz         : 2896.964
cache size      : 8192 KB
physical id     : 0
siblings        : 8
core id         : 3
cpu cores       : 4
apicid          : 7
initial apicid  : 7
fpu             : yes
fpu_exception   : yes
cpuid level     : 13
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt ibpb ibrs stibp dtherm ida arat pln pts
bugs            : cpu_meltdown spectre_v1 spectre_v2
bogomips        : 7183.44
clflush size    : 64
cache_alignment : 64
address sizes   : 39 bits physical, 48 bits virtual
power management:

Linux 4.15.14-1-ARCH x86_64
gcc (GCC) 7.3.1 20180312
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

[xyproto]

With the commands at 2., the unit test for bigint passes correctly! But, there is an error a bit later:

src/tests/unit_ecdsa.cpp:308:54: runtime error: load of value 99, which is not a valid value for type 'Compression_Type'
    #0 0x565457d04bfb in operator() src/tests/unit_ecdsa.cpp:308
    #1 0x565457d04bfb in _M_invoke /usr/include/c++/7.3.1/bits/std_function.h:316
    #2 0x565457c96925 in std::function<void ()>::operator()() const /usr/include/c++/7.3.1/bits/std_function.h:706
    #3 0x565457c96925 in Botan_Tests::Test::Result::test_throws(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::function<void ()>) src/tests/tests.cpp:116
    #4 0x565457d164d2 in test_encoding_options src/tests/unit_ecdsa.cpp:306
    #5 0x565457d2d715 in run src/tests/unit_ecdsa.cpp:487
    #6 0x565457b3b468 in Botan_Tests::Test_Runner::run_tests(std::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::allocator<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > const&, unsigned long, unsigned long) src/tests/test_runner.cpp:263
    #7 0x565457b47b09 in Botan_Tests::Test_Runner::run(std::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::allocator<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, bool, bool, bool, bool, bool, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, unsigned long) src/tests/test_runner.cpp:198
    #8 0x565457517d5a in main src/tests/main.cpp:103
    #9 0x7fb97bfc5f49 in __libc_start_main (/usr/lib/libc.so.6+0x20f49)
    #10 0x565457543ac9 in _start (/build/botan/src/Botan-2.5.0/botan-test+0x91dac9)

Attaching the full log. output.log

[randombit]

A very strange error, since I also use Arch and do not see this problem with GCC 7.3.1 (nor have I seen it ever occur on any platform/compiler).

One thing that may help is to run the test under gdb, interrupt it after a few seconds, and take a backtrace. The tests in question take well under a second on my machine, so after 5 seconds it is very likely the test is in whatever infinite loop it has found itself.

Interesting also that rebuilding with sanitizers the problem goes away. The error you are seeing from UbSan is expected, because in this test (and a few others) we explicitly invoke undefined behavior (here by creating an enum value which is invalid and passing it to the library, to make sure this invalid argument is detected). Running the test suite with --avoid-undefined will skip these tests.

[xyproto]

I would be happy to help out with any further testing.

Note that I'm building in a chroot, using sudo extra-x86_64-build, supplied by the devtools package.

Here's the PKGBUILD, stripped for comments for brevity:

PKGBUILD:

pkgname=botan
pkgver=2.5.0
pkgrel=1
pkgdesc='Crypto library written in C++'
arch=('x86_64')
url='https://botan.randombit.net/'
license=('BSD')
depends=('gcc-libs' 'sh')
makedepends=('python')
validpgpkeys=('621DAF6411E1851C4CF9A2E16211EBF1EFBADFBC')
source=("https://botan.randombit.net/releases/Botan-${pkgver}.tgz"{,.asc})
sha256sums=('b8a31fe03e7f048a5bd3967ecd04b6a48966215e78792df06e333b0eede4fb1b'
            'SKIP')

build() {
  cd "${pkgname^}-$pkgver"

  ./configure.py --prefix=/usr
  make
}

check() {
  cd "${pkgname^}-$pkgver"

  ./botan-test
}

package() {
  cd "${pkgname^}-$pkgver"

  make DESTDIR="$pkgdir" install
  install -Dm644 license.txt "$pkgdir/usr/share/licenses/$pkgname/LICENSE"
}

[randombit]

I just reproduced this using extra-x86_64-build

[randombit]

The problem seems to be the -fno-plt flag. It is not limited to just bigint_unit, also at least modular exponentiation, RSA and ECDSA tests fail. I can reproduce outside of the chroot with CXXFLAGS='-O2 -fno-plt' ./configure.py

[randombit]

If I disable all inline asm for BigInt operations, -fno-plt works ok. So likely the problem is a bad constraint in our asm. (Or maybe a bug in GCC because that happens too, but bad constraint seems more likely)

[randombit]

The problem seems to be in word3_muladd - if I disable the inline x86-64 asm for this one function, tests pass with -fno-plt

[randombit]

If I have word3_muladd clobber "memory", everything works. Again pointing to a bad/missing constraint.

[randombit]

Same problem with 32-bit x86 builds, make sense as basically the same inline asm sequence is used.

[randombit]

If I split the asm into two blocks, one for the mulq and then another for the add sequence again everything ok

[randombit]

@xyproto Can you try with 6c5d9ef

[xyproto]

Will do! Thanks for the quick patching.

[xyproto]

Now the unit tests all pass here. Will update the package to use commit 6c5d9ef until the next release of botan.

Thanks!

[randombit]

Great news. Thanks @xyproto for the report as well as maintaining the Arch package.