From 4a28fc5546e36182eaf0beea1818f25587d34e3f Mon Sep 17 00:00:00 2001 From: Alex Rousskov Date: Mon, 8 Aug 2022 16:10:06 +0000 Subject: [PATCH] Unify r.n.g. seed generation (#1109) Using time-based expressions for seeding pseudo random number generators often results in multiple SMP workers getting the same seed. That, in turn, may result in unwanted correlation of supposed-to-be-independent worker activities: making artificially similar decisions (that are supposed to be "random") and/or concentrating rather than spreading/sharing load. The recently added RandomUuid code did not use time-based seeds in anticipation of this unification. This change converts all std::mt19937 users in src/ except the random ACL code (that probably deserves a dedicated change). C++ standard does not guarantee that std::random_device does not force users to wait while more entropy is accumulated. Based on public comments and source code analysis of popular STL implementations, we should be getting the desired no-wait behavior from popular STLs, in popular environments. If Squid encounters a special environment where the default std::random_device waits for entropy, more code and/or configuration options will be needed to accommodate that special case. The biggest drawback with this approach is that it may be difficult for the admins to discover that std::random_device is waiting in their environment. This is mitigated by the low probability of that happening. --- src/auth/basic/RADIUS/Makefile.am | 1 + src/auth/basic/RADIUS/basic_radius_auth.cc | 4 +-- src/auth/digest/Config.cc | 7 ++-- src/base/Makefile.am | 2 ++ src/base/Random.cc | 39 ++++++++++++++++++++++ src/base/Random.h | 26 +++++++++++++++ src/base/RandomUuid.cc | 6 ++-- src/dns_internal.cc | 4 +-- src/event.cc | 6 ++-- src/fs/ufs/UFSSwapDir.cc | 4 +-- src/tests/SBufFindTest.cc | 4 +-- 11 files changed, 82 insertions(+), 21 deletions(-) create mode 100644 src/base/Random.cc create mode 100644 src/base/Random.h diff --git a/src/auth/basic/RADIUS/Makefile.am b/src/auth/basic/RADIUS/Makefile.am index 4f7cd55554..c548a1f170 100644 --- a/src/auth/basic/RADIUS/Makefile.am +++ b/src/auth/basic/RADIUS/Makefile.am @@ -19,6 +19,7 @@ basic_radius_auth_SOURCES = \ basic_radius_auth_LDADD= \ $(top_builddir)/lib/libmiscencoding.la \ + $(top_builddir)/src/base/libbase.la \ $(COMPAT_LIB) \ $(NETTLELIB) \ $(SSLLIB) \ diff --git a/src/auth/basic/RADIUS/basic_radius_auth.cc b/src/auth/basic/RADIUS/basic_radius_auth.cc index 67bbbec028..8ecf07c1c6 100644 --- a/src/auth/basic/RADIUS/basic_radius_auth.cc +++ b/src/auth/basic/RADIUS/basic_radius_auth.cc @@ -56,6 +56,7 @@ #include "squid.h" #include "auth/basic/RADIUS/radius-util.h" #include "auth/basic/RADIUS/radius.h" +#include "base/Random.h" #include "helper/protocol_defines.h" #include "md5.h" @@ -63,7 +64,6 @@ #include #include #include -#include #if HAVE_SYS_SOCKET_H #include #endif @@ -206,7 +206,7 @@ result_recv(char *buffer, int length) static void random_vector(char *aVector) { - static std::mt19937 mt(time(nullptr)); + static std::mt19937 mt(RandomSeed32()); static xuniform_int_distribution dist; for (int i = 0; i < AUTH_VECTOR_LEN; ++i) diff --git a/src/auth/digest/Config.cc b/src/auth/digest/Config.cc index 324c7a77e2..b725f03297 100644 --- a/src/auth/digest/Config.cc +++ b/src/auth/digest/Config.cc @@ -22,6 +22,7 @@ #include "auth/State.h" #include "auth/toUtf.h" #include "base/LookupTable.h" +#include "base/Random.h" #include "cache_cf.h" #include "event.h" #include "helper.h" @@ -42,8 +43,6 @@ */ #include "mem/Pool.h" -#include - static AUTHSSTATS authenticateDigestStats; helper *digestauthenticators = nullptr; @@ -158,9 +157,7 @@ authenticateDigestNonceNew(void) * - the timestamp also guarantees local uniqueness in the input to * the hash function. */ - // NP: this will likely produce the same randomness sequences for each worker - // since they should all start within the 1-second resolution of seed value. - static std::mt19937 mt(static_cast(getCurrentTime() & 0xFFFFFFFF)); + static std::mt19937 mt(RandomSeed32()); static xuniform_int_distribution newRandomData; /* create a new nonce */ diff --git a/src/base/Makefile.am b/src/base/Makefile.am index 0c8ae4d861..0056b12a06 100644 --- a/src/base/Makefile.am +++ b/src/base/Makefile.am @@ -51,6 +51,8 @@ libbase_la_SOURCES = \ Optional.h \ Packable.h \ PackableStream.h \ + Random.cc \ + Random.h \ RandomUuid.cc \ RandomUuid.h \ Range.h \ diff --git a/src/base/Random.cc b/src/base/Random.cc new file mode 100644 index 0000000000..37eb88dee0 --- /dev/null +++ b/src/base/Random.cc @@ -0,0 +1,39 @@ +/* + * Copyright (C) 1996-2022 The Squid Software Foundation and contributors + * + * Squid software is distributed under GPLv2+ license and includes + * contributions from numerous individuals and organizations. + * Please see the COPYING and CONTRIBUTORS files for details. + */ + +#include "base/Random.h" + +std::mt19937::result_type +RandomSeed32() +{ + // We promise entropy collection without waiting, but there is no standard + // way to get that in all environments. We considered these device names: + // + // * none: The default constructor in some specialized STL implementation or + // build might select a device that requires Squid to wait for entropy. + // + // * "default": Leads to clang (and other STLs) exceptions in some builds + // (e.g., when clang is built to use getentropy(3) or rand_s()). + // + // * "/dev/urandom": Blocks GCC from picking the best entropy source (e.g., + // arc4random(3)) and leads to GCC/clang exceptions in some environments. + // + // If a special supported environment needs a non-default device name, we + // will add a random_device_name configuration directive. We cannot detect + // such needs in general code and choose to write simpler code until then. + static std::random_device dev; + return dev(); +} + +std::mt19937_64::result_type +RandomSeed64() +{ + std::mt19937_64::result_type left = RandomSeed32(); + return (left << 32) | RandomSeed32(); +} + diff --git a/src/base/Random.h b/src/base/Random.h new file mode 100644 index 0000000000..a115882b7b --- /dev/null +++ b/src/base/Random.h @@ -0,0 +1,26 @@ +/* + * Copyright (C) 1996-2022 The Squid Software Foundation and contributors + * + * Squid software is distributed under GPLv2+ license and includes + * contributions from numerous individuals and organizations. + * Please see the COPYING and CONTRIBUTORS files for details. + */ + +#ifndef SQUID_SRC_BASE_RANDOM_H +#define SQUID_SRC_BASE_RANDOM_H + +#include + +/// A 32-bit random value suitable for seeding a 32-bit random number generator. +/// Computing this value may require blocking device I/O but does not require +/// waiting to accumulate entropy. Thus, this function: +/// * may be called at runtime (e.g., the first time a given r.n.g. is needed) +/// * should not be called frequently (e.g., once per transaction is too often) +/// * should not be used as a source of randomness (use a r.n.g. instead) +std::mt19937::result_type RandomSeed32(); + +/// a 64-bit version of RandomSeed32() +std::mt19937_64::result_type RandomSeed64(); + +#endif /* SQUID_SRC_BASE_RANDOM_H */ + diff --git a/src/base/RandomUuid.cc b/src/base/RandomUuid.cc index 66628f4c8d..360caaebd9 100644 --- a/src/base/RandomUuid.cc +++ b/src/base/RandomUuid.cc @@ -8,21 +8,19 @@ #include "squid.h" #include "base/IoManip.h" +#include "base/Random.h" #include "base/RandomUuid.h" #include "base/TextException.h" #include "defines.h" #include -#include static_assert(sizeof(RandomUuid) == 128/8, "RandomUuid has RFC 4122-prescribed 128-bit size"); RandomUuid::RandomUuid() { // Generate random bits for populating our UUID. - // STL implementation bugs notwithstanding (e.g., MinGW bug #338), this is - // our best chance of getting a non-deterministic seed value for the r.n.g. - static std::mt19937_64 rng(std::random_device {}()); // produces 64-bit sized values + static std::mt19937_64 rng(RandomSeed64()); // produces 64-bit sized values const auto rnd1 = rng(); const auto rnd2 = rng(); diff --git a/src/dns_internal.cc b/src/dns_internal.cc index e678fe3f2d..85de50adfc 100644 --- a/src/dns_internal.cc +++ b/src/dns_internal.cc @@ -11,6 +11,7 @@ #include "squid.h" #include "base/CodeContext.h" #include "base/InstanceId.h" +#include "base/Random.h" #include "base/RunnersRegistry.h" #include "comm.h" #include "comm/Connection.h" @@ -43,7 +44,6 @@ #include #endif #include -#include #if HAVE_RESOLV_H #include #endif @@ -1047,7 +1047,7 @@ static unsigned short idnsQueryID() { // NP: apparently ranlux are faster, but not quite as "proven" - static std::mt19937 mt(static_cast(getCurrentTime() & 0xFFFFFFFF)); + static std::mt19937 mt(RandomSeed32()); unsigned short id = mt() & 0xFFFF; unsigned short first_id = id; diff --git a/src/event.cc b/src/event.cc index b2408e764e..cefdb22401 100644 --- a/src/event.cc +++ b/src/event.cc @@ -9,13 +9,13 @@ /* DEBUG: section 41 Event Processing */ #include "squid.h" +#include "base/Random.h" #include "event.h" #include "mgr/Registration.h" #include "Store.h" #include "tools.h" #include -#include /* The list of event processes */ @@ -114,9 +114,7 @@ void eventAddIsh(const char *name, EVH * func, void *arg, double delta_ish, int weight) { if (delta_ish >= 3.0) { - // Default seed is fine. We just need values random enough - // relative to each other to prevent waves of synchronised activity. - static std::mt19937 rng; + static std::mt19937 rng(RandomSeed32()); auto third = (delta_ish/3.0); xuniform_real_distribution<> thirdIsh(delta_ish - third, delta_ish + third); delta_ish = thirdIsh(rng); diff --git a/src/fs/ufs/UFSSwapDir.cc b/src/fs/ufs/UFSSwapDir.cc index 3ad565341f..d9cd08b230 100644 --- a/src/fs/ufs/UFSSwapDir.cc +++ b/src/fs/ufs/UFSSwapDir.cc @@ -11,6 +11,7 @@ #define CLEAN_BUF_SZ 16384 #include "squid.h" +#include "base/Random.h" #include "cache_cf.h" #include "ConfigOption.h" #include "DiskIO/DiskIOModule.h" @@ -32,7 +33,6 @@ #include #include -#include #if HAVE_SYS_STAT_H #include #endif @@ -1078,7 +1078,7 @@ Fs::Ufs::UFSSwapDir::HandleCleanEvent() * value. j equals the total number of UFS level 2 * swap directories */ - std::mt19937 mt(static_cast(getCurrentTime() & 0xFFFFFFFF)); + static std::mt19937 mt(RandomSeed32()); xuniform_int_distribution<> dist(0, j); swap_index = dist(mt); } diff --git a/src/tests/SBufFindTest.cc b/src/tests/SBufFindTest.cc index f70bb2f9e6..4a523bf2f9 100644 --- a/src/tests/SBufFindTest.cc +++ b/src/tests/SBufFindTest.cc @@ -8,12 +8,12 @@ #include "squid.h" #include "base/CharacterSet.h" +#include "base/Random.h" #include "tests/SBufFindTest.h" #include #include #include -#include /* TODO: The whole SBufFindTest class is currently implemented as a single CppUnit test case (because we do not want to register and report every one @@ -370,7 +370,7 @@ SBufFindTest::RandomSBuf(const int length) "ABCDEFGHIJKLMNOPQRSTUVWXYZ" "abcdefghijklomnpqrstuvwxyz"; - static std::mt19937 mt(time(nullptr)); + static std::mt19937 mt(RandomSeed32()); // sizeof() counts the terminating zero at the end of characters // and the distribution is an 'inclusive' value range, so -2 -- 2.39.5