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_ 306