contrib/llvm-project/compiler-rt/include/fuzzer/FuzzedDataProvider.h

   1 //===- FuzzedDataProvider.h - Utility header for fuzz targets ---*- C++ -* ===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 // A single header library providing an utility class to break up an array of
   9 // bytes. Whenever run on the same input, provides the same output, as long as
  10 // its methods are called in the same order, with the same arguments.
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_FUZZER_FUZZED_DATA_PROVIDER_H_
  14 #define LLVM_FUZZER_FUZZED_DATA_PROVIDER_H_
  15
  16 #include <algorithm>
  17 #include <climits>
  18 #include <cstddef>
  19 #include <cstdint>
  20 #include <cstring>
  21 #include <initializer_list>
  22 #include <string>
  23 #include <type_traits>
  24 #include <utility>
  25 #include <vector>
  26
  27 // In addition to the comments below, the API is also briefly documented at
  28 // https://github.com/google/fuzzing/blob/master/docs/split-inputs.md#fuzzed-data-provider
  29 class FuzzedDataProvider {
  30  public:
  31   // |data| is an array of length |size| that the FuzzedDataProvider wraps to
  32   // provide more granular access. |data| must outlive the FuzzedDataProvider.
  33   FuzzedDataProvider(const uint8_t *data, size_t size)
  34       : data_ptr_(data), remaining_bytes_(size) {}
  35   ~FuzzedDataProvider() = default;
  36
  37   // Returns a std::vector containing |num_bytes| of input data. If fewer than
  38   // |num_bytes| of data remain, returns a shorter std::vector containing all
  39   // of the data that's left. Can be used with any byte sized type, such as
  40   // char, unsigned char, uint8_t, etc.
  41   template <typename T> std::vector<T> ConsumeBytes(size_t num_bytes) {
  42     num_bytes = std::min(num_bytes, remaining_bytes_);
  43     return ConsumeBytes<T>(num_bytes, num_bytes);
  44   }
  45
  46   // Similar to |ConsumeBytes|, but also appends the terminator value at the end
  47   // of the resulting vector. Useful, when a mutable null-terminated C-string is
  48   // needed, for example. But that is a rare case. Better avoid it, if possible,
  49   // and prefer using |ConsumeBytes| or |ConsumeBytesAsString| methods.
  50   template <typename T>
  51   std::vector<T> ConsumeBytesWithTerminator(size_t num_bytes,
  52                                             T terminator = 0) {
  53     num_bytes = std::min(num_bytes, remaining_bytes_);
  54     std::vector<T> result = ConsumeBytes<T>(num_bytes + 1, num_bytes);
  55     result.back() = terminator;
  56     return result;
  57   }
  58
  59   // Returns a std::string containing |num_bytes| of input data. Using this and
  60   // |.c_str()| on the resulting string is the best way to get an immutable
  61   // null-terminated C string. If fewer than |num_bytes| of data remain, returns
  62   // a shorter std::string containing all of the data that's left.
  63   std::string ConsumeBytesAsString(size_t num_bytes) {
  64     static_assert(sizeof(std::string::value_type) == sizeof(uint8_t),
  65                   "ConsumeBytesAsString cannot convert the data to a string.");
  66
  67     num_bytes = std::min(num_bytes, remaining_bytes_);
  68     std::string result(
  69         reinterpret_cast<const std::string::value_type *>(data_ptr_),
  70         num_bytes);
  71     Advance(num_bytes);
  72     return result;
  73   }
  74
  75   // Returns a number in the range [min, max] by consuming bytes from the
  76   // input data. The value might not be uniformly distributed in the given
  77   // range. If there's no input data left, always returns |min|. |min| must
  78   // be less than or equal to |max|.
  79   template <typename T> T ConsumeIntegralInRange(T min, T max) {
  80     static_assert(std::is_integral<T>::value, "An integral type is required.");
  81     static_assert(sizeof(T) <= sizeof(uint64_t), "Unsupported integral type.");
  82
  83     if (min > max)
  84       abort();
  85
  86     // Use the biggest type possible to hold the range and the result.
  87     uint64_t range = static_cast<uint64_t>(max) - min;
  88     uint64_t result = 0;
  89     size_t offset = 0;
  90
  91     while (offset < sizeof(T) * CHAR_BIT && (range >> offset) > 0 &&
  92            remaining_bytes_ != 0) {
  93       // Pull bytes off the end of the seed data. Experimentally, this seems to
  94       // allow the fuzzer to more easily explore the input space. This makes
  95       // sense, since it works by modifying inputs that caused new code to run,
  96       // and this data is often used to encode length of data read by
  97       // |ConsumeBytes|. Separating out read lengths makes it easier modify the
  98       // contents of the data that is actually read.
  99       --remaining_bytes_;
 100       result = (result << CHAR_BIT) | data_ptr_[remaining_bytes_];
 101       offset += CHAR_BIT;
 102     }
 103
 104     // Avoid division by 0, in case |range + 1| results in overflow.
 105     if (range != std::numeric_limits<decltype(range)>::max())
 106       result = result % (range + 1);
 107
 108     return static_cast<T>(min + result);
 109   }
 110
 111   // Returns a std::string of length from 0 to |max_length|. When it runs out of
 112   // input data, returns what remains of the input. Designed to be more stable
 113   // with respect to a fuzzer inserting characters than just picking a random
 114   // length and then consuming that many bytes with |ConsumeBytes|.
 115   std::string ConsumeRandomLengthString(size_t max_length) {
 116     // Reads bytes from the start of |data_ptr_|. Maps "\\" to "\", and maps "\"
 117     // followed by anything else to the end of the string. As a result of this
 118     // logic, a fuzzer can insert characters into the string, and the string
 119     // will be lengthened to include those new characters, resulting in a more
 120     // stable fuzzer than picking the length of a string independently from
 121     // picking its contents.
 122     std::string result;
 123
 124     // Reserve the anticipated capaticity to prevent several reallocations.
 125     result.reserve(std::min(max_length, remaining_bytes_));
 126     for (size_t i = 0; i < max_length && remaining_bytes_ != 0; ++i) {
 127       char next = ConvertUnsignedToSigned<char>(data_ptr_[0]);
 128       Advance(1);
 129       if (next == '\\' && remaining_bytes_ != 0) {
 130         next = ConvertUnsignedToSigned<char>(data_ptr_[0]);
 131         Advance(1);
 132         if (next != '\\')
 133           break;
 134       }
 135       result += next;
 136     }
 137
 138     result.shrink_to_fit();
 139     return result;
 140   }
 141
 142   // Returns a std::vector containing all remaining bytes of the input data.
 143   template <typename T> std::vector<T> ConsumeRemainingBytes() {
 144     return ConsumeBytes<T>(remaining_bytes_);
 145   }
 146
 147   // Returns a std::string containing all remaining bytes of the input data.
 148   // Prefer using |ConsumeRemainingBytes| unless you actually need a std::string
 149   // object.
 150   std::string ConsumeRemainingBytesAsString() {
 151     return ConsumeBytesAsString(remaining_bytes_);
 152   }
 153
 154   // Returns a number in the range [Type's min, Type's max]. The value might
 155   // not be uniformly distributed in the given range. If there's no input data
 156   // left, always returns |min|.
 157   template <typename T> T ConsumeIntegral() {
 158     return ConsumeIntegralInRange(std::numeric_limits<T>::min(),
 159                                   std::numeric_limits<T>::max());
 160   }
 161
 162   // Reads one byte and returns a bool, or false when no data remains.
 163   bool ConsumeBool() { return 1 & ConsumeIntegral<uint8_t>(); }
 164
 165   // Returns a copy of the value selected from the given fixed-size |array|.
 166   template <typename T, size_t size>
 167   T PickValueInArray(const T (&array)[size]) {
 168     static_assert(size > 0, "The array must be non empty.");
 169     return array[ConsumeIntegralInRange<size_t>(0, size - 1)];
 170   }
 171
 172   template <typename T>
 173   T PickValueInArray(std::initializer_list<const T> list) {
 174     // TODO(Dor1s): switch to static_assert once C++14 is allowed.
 175     if (!list.size())
 176       abort();
 177
 178     return *(list.begin() + ConsumeIntegralInRange<size_t>(0, list.size() - 1));
 179   }
 180
 181   // Returns an enum value. The enum must start at 0 and be contiguous. It must
 182   // also contain |kMaxValue| aliased to its largest (inclusive) value. Such as:
 183   // enum class Foo { SomeValue, OtherValue, kMaxValue = OtherValue };
 184   template <typename T> T ConsumeEnum() {
 185     static_assert(std::is_enum<T>::value, "|T| must be an enum type.");
 186     return static_cast<T>(ConsumeIntegralInRange<uint32_t>(
 187         0, static_cast<uint32_t>(T::kMaxValue)));
 188   }
 189
 190   // Returns a floating point number in the range [0.0, 1.0]. If there's no
 191   // input data left, always returns 0.
 192   template <typename T> T ConsumeProbability() {
 193     static_assert(std::is_floating_point<T>::value,
 194                   "A floating point type is required.");
 195
 196     // Use different integral types for different floating point types in order
 197     // to provide better density of the resulting values.
 198     using IntegralType =
 199         typename std::conditional<(sizeof(T) <= sizeof(uint32_t)), uint32_t,
 200                                   uint64_t>::type;
 201
 202     T result = static_cast<T>(ConsumeIntegral<IntegralType>());
 203     result /= static_cast<T>(std::numeric_limits<IntegralType>::max());
 204     return result;
 205   }
 206
 207   // Returns a floating point value in the range [Type's lowest, Type's max] by
 208   // consuming bytes from the input data. If there's no input data left, always
 209   // returns approximately 0.
 210   template <typename T> T ConsumeFloatingPoint() {
 211     return ConsumeFloatingPointInRange<T>(std::numeric_limits<T>::lowest(),
 212                                           std::numeric_limits<T>::max());
 213   }
 214
 215   // Returns a floating point value in the given range by consuming bytes from
 216   // the input data. If there's no input data left, returns |min|. Note that
 217   // |min| must be less than or equal to |max|.
 218   template <typename T> T ConsumeFloatingPointInRange(T min, T max) {
 219     if (min > max)
 220       abort();
 221
 222     T range = .0;
 223     T result = min;
 224     constexpr T zero(.0);
 225     if (max > zero && min < zero && max > min + std::numeric_limits<T>::max()) {
 226       // The diff |max - min| would overflow the given floating point type. Use
 227       // the half of the diff as the range and consume a bool to decide whether
 228       // the result is in the first of the second part of the diff.
 229       range = (max / 2.0) - (min / 2.0);
 230       if (ConsumeBool()) {
 231         result += range;
 232       }
 233     } else {
 234       range = max - min;
 235     }
 236
 237     return result + range * ConsumeProbability<T>();
 238   }
 239
 240   // Reports the remaining bytes available for fuzzed input.
 241   size_t remaining_bytes() { return remaining_bytes_; }
 242
 243  private:
 244   FuzzedDataProvider(const FuzzedDataProvider &) = delete;
 245   FuzzedDataProvider &operator=(const FuzzedDataProvider &) = delete;
 246
 247   void Advance(size_t num_bytes) {
 248     if (num_bytes > remaining_bytes_)
 249       abort();
 250
 251     data_ptr_ += num_bytes;
 252     remaining_bytes_ -= num_bytes;
 253   }
 254
 255   template <typename T>
 256   std::vector<T> ConsumeBytes(size_t size, size_t num_bytes_to_consume) {
 257     static_assert(sizeof(T) == sizeof(uint8_t), "Incompatible data type.");
 258
 259     // The point of using the size-based constructor below is to increase the
 260     // odds of having a vector object with capacity being equal to the length.
 261     // That part is always implementation specific, but at least both libc++ and
 262     // libstdc++ allocate the requested number of bytes in that constructor,
 263     // which seems to be a natural choice for other implementations as well.
 264     // To increase the odds even more, we also call |shrink_to_fit| below.
 265     std::vector<T> result(size);
 266     if (size == 0) {
 267       if (num_bytes_to_consume != 0)
 268         abort();
 269       return result;
 270     }
 271
 272     std::memcpy(result.data(), data_ptr_, num_bytes_to_consume);
 273     Advance(num_bytes_to_consume);
 274
 275     // Even though |shrink_to_fit| is also implementation specific, we expect it
 276     // to provide an additional assurance in case vector's constructor allocated
 277     // a buffer which is larger than the actual amount of data we put inside it.
 278     result.shrink_to_fit();
 279     return result;
 280   }
 281
 282   template <typename TS, typename TU> TS ConvertUnsignedToSigned(TU value) {
 283     static_assert(sizeof(TS) == sizeof(TU), "Incompatible data types.");
 284     static_assert(!std::numeric_limits<TU>::is_signed,
 285                   "Source type must be unsigned.");
 286
 287     // TODO(Dor1s): change to `if constexpr` once C++17 becomes mainstream.
 288     if (std::numeric_limits<TS>::is_modulo)
 289       return static_cast<TS>(value);
 290
 291     // Avoid using implementation-defined unsigned to signer conversions.
 292     // To learn more, see https://stackoverflow.com/questions/13150449.
 293     if (value <= std::numeric_limits<TS>::max()) {
 294       return static_cast<TS>(value);
 295     } else {
 296       constexpr auto TS_min = std::numeric_limits<TS>::min();
 297       return TS_min + static_cast<char>(value - TS_min);
 298     }
 299   }
 300
 301   const uint8_t *data_ptr_;
 302   size_t remaining_bytes_;
 303 };
 304
 305 #endif // LLVM_FUZZER_FUZZED_DATA_PROVIDER_H_