Merge #18009: tests: Add fuzzing harness for strprintf(…)

cc668d06fb71463fd406df761b0e89e25d4de968 tests: Add fuzzing harness for strprintf(...) (practicalswift)
ccc3c76e2b5d28a2372ae5752c08256396bf43e6 tests: Add fuzzer strprintf to FUZZERS_MISSING_CORPORA (temporarily) (practicalswift)
6ef04912af7f216f3112e0e9919f67e36415a792 tests: Update FuzzedDataProvider.h from upstream (LLVM) (practicalswift)

Pull request description:

  Add fuzzing harness for `strprintf(…)`.

  Update `FuzzedDataProvider.h`.

  Avoid hitting some issues in tinyformat (reported upstreams in https://github.com/c42f/tinyformat/issues/70).

  ---

  Found issues in tinyformat:

  **Issue 1.** The following causes a signed integer overflow followed by an allocation of 9 GB of RAM (or an OOM in memory constrained environments):

  ```
  strprintf("%.777777700000000$", 1.0);
  ```

  **Issue 2.** The following causes a stack overflow:

  ```
  strprintf("%987654321000000:", 1);
  ```

  **Issue 3.** The following causes a stack overflow:

  ```
  strprintf("%1$*1$*", -11111111);
  ```

  **Issue 4.** The following causes a `NULL` pointer dereference:

  ```
  strprintf("%.1s", (char *)nullptr);
  ```

  **Issue 5.** The following causes a float cast overflow:

  ```
  strprintf("%c", -1000.0);
  ```

  **Issue 6.** The following causes a float cast overflow followed by an invalid integer negation:

  ```
  strprintf("%*", std::numeric_limits<double>::lowest());
  ```

Top commit has no ACKs.

Tree-SHA512: 9b765559281470f4983eb5aeca94bab1b15ec9837c0ee01a20f4348e9335e4ee4e4fecbd7a1a5a8ac96aabe0f9eeb597b8fc9a2c8faf1bab386e8225d5cdbc18

5 files changed, 228 insertions, 13 deletions

diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index ed81622717..9d782e7a04 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -54,6 +54,7 @@ FUZZ_TARGETS = \
   test/fuzz/script_flags \
   test/fuzz/service_deserialize \
   test/fuzz/spanparsing \
+  test/fuzz/strprintf \
   test/fuzz/sub_net_deserialize \
   test/fuzz/transaction \
   test/fuzz/tx_in \
@@ -536,6 +537,12 @@ test_fuzz_spanparsing_LDADD = $(FUZZ_SUITE_LD_COMMON)
 test_fuzz_spanparsing_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
 test_fuzz_spanparsing_SOURCES = $(FUZZ_SUITE) test/fuzz/spanparsing.cpp
 
+test_fuzz_strprintf_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
+test_fuzz_strprintf_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
+test_fuzz_strprintf_LDADD = $(FUZZ_SUITE_LD_COMMON)
+test_fuzz_strprintf_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
+test_fuzz_strprintf_SOURCES = $(FUZZ_SUITE) test/fuzz/strprintf.cpp
+
 test_fuzz_sub_net_deserialize_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) -DSUB_NET_DESERIALIZE=1
 test_fuzz_sub_net_deserialize_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
 test_fuzz_sub_net_deserialize_LDADD = $(FUZZ_SUITE_LD_COMMON)
diff --git a/src/test/fuzz/FuzzedDataProvider.h b/src/test/fuzz/FuzzedDataProvider.h
index 1b5b4bb012..3e069eba69 100644
--- a/src/test/fuzz/FuzzedDataProvider.h
+++ b/src/test/fuzz/FuzzedDataProvider.h
@@ -13,11 +13,10 @@
 #ifndef LLVM_FUZZER_FUZZED_DATA_PROVIDER_H_
 #define LLVM_FUZZER_FUZZED_DATA_PROVIDER_H_
 
-#include <limits.h>
-#include <stddef.h>
-#include <stdint.h>
-
 #include <algorithm>
+#include <climits>
+#include <cstddef>
+#include <cstdint>
 #include <cstring>
 #include <initializer_list>
 #include <string>
@@ -25,8 +24,10 @@
 #include <utility>
 #include <vector>
 
+// In addition to the comments below, the API is also briefly documented at
+// https://github.com/google/fuzzing/blob/master/docs/split-inputs.md#fuzzed-data-provider
 class FuzzedDataProvider {
-public:
+ public:
   // |data| is an array of length |size| that the FuzzedDataProvider wraps to
   // provide more granular access. |data| must outlive the FuzzedDataProvider.
   FuzzedDataProvider(const uint8_t *data, size_t size)
@@ -143,9 +144,9 @@ public:
     return ConsumeBytes<T>(remaining_bytes_);
   }
 
+  // Returns a std::string containing all remaining bytes of the input data.
   // Prefer using |ConsumeRemainingBytes| unless you actually need a std::string
   // object.
-  // Returns a std::vector containing all remaining bytes of the input data.
   std::string ConsumeRemainingBytesAsString() {
     return ConsumeBytesAsString(remaining_bytes_);
   }
@@ -161,7 +162,7 @@ public:
   // Reads one byte and returns a bool, or false when no data remains.
   bool ConsumeBool() { return 1 & ConsumeIntegral<uint8_t>(); }
 
-  // Returns a copy of a value selected from a fixed-size |array|.
+  // Returns a copy of the value selected from the given fixed-size |array|.
   template <typename T, size_t size>
   T PickValueInArray(const T (&array)[size]) {
     static_assert(size > 0, "The array must be non empty.");
@@ -170,11 +171,14 @@ public:
 
   template <typename T>
   T PickValueInArray(std::initializer_list<const T> list) {
-    // static_assert(list.size() > 0, "The array must be non empty.");
+    // TODO(Dor1s): switch to static_assert once C++14 is allowed.
+    if (!list.size())
+      abort();
+
     return *(list.begin() + ConsumeIntegralInRange<size_t>(0, list.size() - 1));
   }
 
-  // Return an enum value. The enum must start at 0 and be contiguous. It must
+  // Returns an enum value. The enum must start at 0 and be contiguous. It must
   // also contain |kMaxValue| aliased to its largest (inclusive) value. Such as:
   // enum class Foo { SomeValue, OtherValue, kMaxValue = OtherValue };
   template <typename T> T ConsumeEnum() {
@@ -183,10 +187,60 @@ public:
         0, static_cast<uint32_t>(T::kMaxValue)));
   }
 
+  // Returns a floating point number in the range [0.0, 1.0]. If there's no
+  // input data left, always returns 0.
+  template <typename T> T ConsumeProbability() {
+    static_assert(std::is_floating_point<T>::value,
+                  "A floating point type is required.");
+
+    // Use different integral types for different floating point types in order
+    // to provide better density of the resulting values.
+    using IntegralType =
+        typename std::conditional<(sizeof(T) <= sizeof(uint32_t)), uint32_t,
+                                  uint64_t>::type;
+
+    T result = static_cast<T>(ConsumeIntegral<IntegralType>());
+    result /= static_cast<T>(std::numeric_limits<IntegralType>::max());
+    return result;
+  }
+
+  // Returns a floating point value in the range [Type's lowest, Type's max] by
+  // consuming bytes from the input data. If there's no input data left, always
+  // returns approximately 0.
+  template <typename T> T ConsumeFloatingPoint() {
+    return ConsumeFloatingPointInRange<T>(std::numeric_limits<T>::lowest(),
+                                          std::numeric_limits<T>::max());
+  }
+
+  // Returns a floating point value in the given range by consuming bytes from
+  // the input data. If there's no input data left, returns |min|. Note that
+  // |min| must be less than or equal to |max|.
+  template <typename T> T ConsumeFloatingPointInRange(T min, T max) {
+    if (min > max)
+      abort();
+
+    T range = .0;
+    T result = min;
+    constexpr T zero(.0);
+    if (max > zero && min < zero && max > min + std::numeric_limits<T>::max()) {
+      // The diff |max - min| would overflow the given floating point type. Use
+      // the half of the diff as the range and consume a bool to decide whether
+      // the result is in the first of the second part of the diff.
+      range = (max / 2.0) - (min / 2.0);
+      if (ConsumeBool()) {
+        result += range;
+      }
+    } else {
+      range = max - min;
+    }
+
+    return result + range * ConsumeProbability<T>();
+  }
+
   // Reports the remaining bytes available for fuzzed input.
   size_t remaining_bytes() { return remaining_bytes_; }
 
-private:
+ private:
   FuzzedDataProvider(const FuzzedDataProvider &) = delete;
   FuzzedDataProvider &operator=(const FuzzedDataProvider &) = delete;
 
@@ -209,6 +263,12 @@ private:
     // which seems to be a natural choice for other implementations as well.
     // To increase the odds even more, we also call |shrink_to_fit| below.
     std::vector<T> result(size);
+    if (size == 0) {
+      if (num_bytes_to_consume != 0)
+        abort();
+      return result;
+    }
+
     std::memcpy(result.data(), data_ptr_, num_bytes_to_consume);
     Advance(num_bytes_to_consume);
 
@@ -230,9 +290,9 @@ private:
 
     // Avoid using implementation-defined unsigned to signer conversions.
     // To learn more, see https://stackoverflow.com/questions/13150449.
-    if (value <= std::numeric_limits<TS>::max())
+    if (value <= std::numeric_limits<TS>::max()) {
       return static_cast<TS>(value);
-    else {
+    } else {
       constexpr auto TS_min = std::numeric_limits<TS>::min();
       return TS_min + static_cast<char>(value - TS_min);
     }
diff --git a/src/test/fuzz/strprintf.cpp b/src/test/fuzz/strprintf.cpp
new file mode 100644
index 0000000000..0de21f0e7c
--- /dev/null
+++ b/src/test/fuzz/strprintf.cpp
@@ -0,0 +1,147 @@
+// Copyright (c) 2020 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <tinyformat.h>
+#include <util/strencodings.h>
+
+#include <algorithm>
+#include <cassert>
+#include <cstdint>
+#include <string>
+#include <vector>
+
+void test_one_input(const std::vector<uint8_t>& buffer)
+{
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    const std::string format_string = fuzzed_data_provider.ConsumeRandomLengthString(64);
+
+    const int digits_in_format_specifier = std::count_if(format_string.begin(), format_string.end(), IsDigit);
+
+    // Avoid triggering the following crash bug:
+    // * strprintf("%987654321000000:", 1);
+    //
+    // Avoid triggering the following OOM bug:
+    // * strprintf("%.222222200000000$", 1.1);
+    //
+    // Upstream bug report: https://github.com/c42f/tinyformat/issues/70
+    if (format_string.find("%") != std::string::npos && digits_in_format_specifier >= 7) {
+        return;
+    }
+
+    // Avoid triggering the following crash bug:
+    // * strprintf("%1$*1$*", -11111111);
+    //
+    // Upstream bug report: https://github.com/c42f/tinyformat/issues/70
+    if (format_string.find("%") != std::string::npos && format_string.find("$") != std::string::npos && format_string.find("*") != std::string::npos && digits_in_format_specifier > 0) {
+        return;
+    }
+
+    // Avoid triggering the following crash bug:
+    // * strprintf("%.1s", (char*)nullptr);
+    //
+    // (void)strprintf(format_string, (char*)nullptr);
+    //
+    // Upstream bug report: https://github.com/c42f/tinyformat/issues/70
+
+    try {
+        (void)strprintf(format_string, (signed char*)nullptr);
+    } catch (const tinyformat::format_error&) {
+    }
+    try {
+        (void)strprintf(format_string, (unsigned char*)nullptr);
+    } catch (const tinyformat::format_error&) {
+    }
+    try {
+        (void)strprintf(format_string, (void*)nullptr);
+    } catch (const tinyformat::format_error&) {
+    }
+    try {
+        (void)strprintf(format_string, (bool*)nullptr);
+    } catch (const tinyformat::format_error&) {
+    }
+    try {
+        (void)strprintf(format_string, (float*)nullptr);
+    } catch (const tinyformat::format_error&) {
+    }
+    try {
+        (void)strprintf(format_string, (double*)nullptr);
+    } catch (const tinyformat::format_error&) {
+    }
+    try {
+        (void)strprintf(format_string, (int16_t*)nullptr);
+    } catch (const tinyformat::format_error&) {
+    }
+    try {
+        (void)strprintf(format_string, (uint16_t*)nullptr);
+    } catch (const tinyformat::format_error&) {
+    }
+    try {
+        (void)strprintf(format_string, (int32_t*)nullptr);
+    } catch (const tinyformat::format_error&) {
+    }
+    try {
+        (void)strprintf(format_string, (uint32_t*)nullptr);
+    } catch (const tinyformat::format_error&) {
+    }
+    try {
+        (void)strprintf(format_string, (int64_t*)nullptr);
+    } catch (const tinyformat::format_error&) {
+    }
+    try {
+        (void)strprintf(format_string, (uint64_t*)nullptr);
+    } catch (const tinyformat::format_error&) {
+    }
+
+    try {
+        switch (fuzzed_data_provider.ConsumeIntegralInRange(0, 13)) {
+        case 0:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeRandomLengthString(32));
+            break;
+        case 1:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeRandomLengthString(32).c_str());
+            break;
+        case 2:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeIntegral<signed char>());
+            break;
+        case 3:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeIntegral<unsigned char>());
+            break;
+        case 4:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeIntegral<char>());
+            break;
+        case 5:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeBool());
+            break;
+        case 6:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeFloatingPoint<float>());
+            break;
+        case 7:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeFloatingPoint<double>());
+            break;
+        case 8:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeIntegral<int16_t>());
+            break;
+        case 9:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeIntegral<uint16_t>());
+            break;
+        case 10:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeIntegral<int32_t>());
+            break;
+        case 11:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeIntegral<uint32_t>());
+            break;
+        case 12:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeIntegral<int64_t>());
+            break;
+        case 13:
+            (void)strprintf(format_string, fuzzed_data_provider.ConsumeIntegral<uint64_t>());
+            break;
+        default:
+            assert(false);
+        }
+    } catch (const tinyformat::format_error&) {
+    }
+}
diff --git a/test/fuzz/test_runner.py b/test/fuzz/test_runner.py
index 9027311a8b..6b687060e2 100755
--- a/test/fuzz/test_runner.py
+++ b/test/fuzz/test_runner.py
@@ -39,6 +39,7 @@ FUZZERS_MISSING_CORPORA = [
     "psbt_output_deserialize",
     "pub_key_deserialize",
     "script_deserialize",
+    "strprintf",
     "sub_net_deserialize",
     "tx_in",
     "tx_in_deserialize",
diff --git a/test/lint/lint-format-strings.sh b/test/lint/lint-format-strings.sh
index 6cb486689b..184c3682c8 100755
--- a/test/lint/lint-format-strings.sh
+++ b/test/lint/lint-format-strings.sh
@@ -34,7 +34,7 @@ if ! python3 -m doctest test/lint/lint-format-strings.py; then
 fi
 for S in "${FUNCTION_NAMES_AND_NUMBER_OF_LEADING_ARGUMENTS[@]}"; do
     IFS="," read -r FUNCTION_NAME SKIP_ARGUMENTS <<< "${S}"
-    for MATCHING_FILE in $(git grep --full-name -l "${FUNCTION_NAME}" -- "*.c" "*.cpp" "*.h" | sort | grep -vE "^src/(leveldb|secp256k1|tinyformat|univalue)"); do
+    for MATCHING_FILE in $(git grep --full-name -l "${FUNCTION_NAME}" -- "*.c" "*.cpp" "*.h" | sort | grep -vE "^src/(leveldb|secp256k1|tinyformat|univalue|test/fuzz/strprintf.cpp)"); do
         MATCHING_FILES+=("${MATCHING_FILE}")
     done
     if ! test/lint/lint-format-strings.py --skip-arguments "${SKIP_ARGUMENTS}" "${FUNCTION_NAME}" "${MATCHING_FILES[@]}"; then