1//
2// immer: immutable data structures for C++
3// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
4//
5// This software is distributed under the Boost Software License, Version 1.0.
6// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
7//
8
9#include "extra/fuzzer/fuzzer_input.hpp"
10#include <immer/flex_vector.hpp>
11#include <array>
12#include <iostream>
13#include <catch.hpp>
14
15#define IMMER_FUZZED_TRACE_ENABLE 0
16
17#if IMMER_FUZZED_TRACE_ENABLE
18#define IMMER_FUZZED_TRACE(...) std::cout << __VA_ARGS__ << std::endl;
19#else
20#define IMMER_FUZZED_TRACE(...)
21#endif
22
23namespace {
24
25template <std::size_t VarCount = 8, unsigned Bits = 3>
26int run_input(const std::uint8_t* data, std::size_t size)
27{
28 using vector_t = immer::flex_vector<int, immer::default_memory_policy, Bits, Bits>;
29 using size_t = std::uint8_t;
30
31 auto vars = std::array<vector_t, VarCount>{};
32
33#if IMMER_FUZZED_TRACE_ENABLE
34 for (auto i = 0u; i < VarCount; ++i)
35 std::cout << "auto var" << i << " = vector_t{};" << std::endl;
36#endif
37
38 auto is_valid_var = [&] (auto idx) {
39 return idx >= 0 && idx < VarCount;
40 };
41 auto is_valid_index = [] (auto& v) {
42 return [&] (auto idx) { return idx >= 0 && idx < v.size(); };
43 };
44 auto is_valid_size = [] (auto& v) {
45 return [&] (auto idx) { return idx >= 0 && idx <= v.size(); };
46 };
47
48 return fuzzer_input{data, size}.run([&] (auto& in)
49 {
50 enum ops {
51 op_push_back,
52 op_update,
53 op_take,
54 op_drop,
55 op_concat,
56 };
57 auto src = read<std::uint8_t>(in, is_valid_var);
58 auto dst = read<std::uint8_t>(in, is_valid_var);
59 switch (read<char>(in))
60 {
61 case op_push_back:
62 IMMER_FUZZED_TRACE(
63 "var" << +dst << " = var" << +src <<
64 ".push_back(42);");
65 vars[dst] = vars[src].push_back(42);
66 break;
67 case op_update: {
68 auto idx = read<size_t>(in, is_valid_index(vars[src]));
69 IMMER_FUZZED_TRACE(
70 "var" << +dst << " = var" << +src <<
71 ".update(" << +idx << ", [] (auto x) { return x + 1; });");
72 vars[dst] = vars[src].update(idx, [] (auto x) { return x + 1; });
73 break;
74 }
75 case op_take: {
76 auto idx = read<size_t>(in, is_valid_size(vars[src]));
77 IMMER_FUZZED_TRACE(
78 "var" << +dst << " = var" << +src <<
79 ".take(" << +idx << ");");
80 vars[dst] = vars[src].take(idx);
81 break;
82 }
83 case op_drop: {
84 auto idx = read<size_t>(in, is_valid_size(vars[src]));
85 IMMER_FUZZED_TRACE(
86 "var" << +dst << " = var" << +src <<
87 ".take(" << +idx << ");");
88 vars[dst] = vars[src].drop(idx);
89 break;
90 }
91 case op_concat: {
92 auto src2 = read<std::uint8_t>(in, is_valid_var);
93 IMMER_FUZZED_TRACE(
94 "var" << +dst << " = var" << +src << " + var" << +src2 << ";");
95 vars[dst] = vars[src] + vars[src2];
96 break;
97 }
98 default:
99 break;
100 };
101 return true;
102 });
103}
104
105} // anonymous namespace
106
107TEST_CASE("bug: concatenate too big vectors")
108{
109 // The problem here was that since we were using 32 bit sizes,
110 // concatenating big flex_vectors can overflow the sizes. Let's
111 // just use std::size_t like normal people.
112 //
113 // Still, the problem could re-ocurr with longer inputs. For this
114 // reason later fuzzing efforts do check that concatenation is
115 // valid for the given vector sizes. Similar assertions are put
116 // in the code too.
117 SECTION("simplified example")
118 {
119 using vector_t = immer::flex_vector<int, immer::default_memory_policy, 3, 3>;
120 auto var0 = vector_t{};
121 auto var1 = vector_t{};
122 auto var2 = vector_t{};
123 auto var4 = vector_t{};
124 var1 = var1.push_back(42);
125 var0 = var0.push_back(42);
126 var0 = var0.push_back(42);
127 var0 = var2.push_back(42);
128 var0 = var0.push_back(42);
129 var2 = var0;
130 var0 = var0.push_back(42);
131 var0 = var0.push_back(42);
132 var4 = var4.push_back(42);
133 var0 = var0.push_back(42);
134 var0 = var0.push_back(42);
135 var0 = var0 + var0;
136 var0 = var0.push_back(42);
137 var0 = var0.push_back(42);
138 var2 = var0.push_back(42);
139 var0 = var0 + var4;
140 var4 = var4 + var4;
141 var4 = var4 + var4;
142 var4 = var4 + var4;
143 var0 = var0.push_back(42);
144 var0 = var0.push_back(42);
145 var1 = var2 + var4;
146 var4 = var4 + var4;
147 var0 = var1.push_back(42);
148 var0 = var0.push_back(42);
149 var0 = var0 + var4;
150 var4 = var4 + var4;
151 var4 = var4 + var4;
152 var4 = var4 + var4;
153 var4 = var4 + var4;
154 var4 = var4 + var4;
155 var4 = var4 + var4;
156 var4 = var4 + var4;
157 var4 = var4 + var4;
158 var4 = var4 + var4;
159 var4 = var4 + var4;
160 var4 = var4 + var4;
161 var4 = var4 + var4;
162 var4 = var4 + var4;
163 var4 = var4 + var4;
164 var4 = var4 + var4;
165 var4 = var4 + var4;
166 var4 = var4 + var4;
167 var4 = var4 + var4;
168 var4 = var4 + var4;
169 var4 = var4 + var4;
170 var4 = var4 + var4;
171 var4 = var4 + var4;
172 var4 = var4 + var4;
173 var4 = var4 + var4;
174 var4 = var4 + var4;
175 var4 = var4 + var4;
176 var4 = var4 + var4;
177 var4 = var4 + var4;
178 var4 = var4.push_back(42);
179 }
180
181#if __GNUC__ != 9
182 // Assertion `!p->relaxed()' failed
183 SECTION("")
184 {
185 constexpr std::uint8_t input[] = {
186 0x1,0x1,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x39,0x6a,0x76,0xb9,0x2,0x0,0x0,0x0,0x0,0x0,0x0,0x2,0x1,0x0,0x0,0x2a,0x0,0x0,0x0,0x0,0x0,0x4,0x4,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x4,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x2,0x0,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x0,0x0,0x0,0x0,0x2,0x1,0x4,0x4,0x4,0x4,0x4,0x4,0x1,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x2a,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x0,
187 };
188 CHECK(run_input(input, sizeof(input)) == 0);
189 }
190 SECTION("")
191 {
192 constexpr std::uint8_t input[] = {
193 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x1,0x1,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x3,0x0,0x0,0x0,0x0,0x0,0x4,0x0,0x0,0x0,0x0,0x0,0x0,0xe2,0xe2,0xe2,0xe2,0xe2,0xe2,0xe2,0xe2,0xe2,0xe2,0xe2,0xe2,0xe2,0xe2,0xe2,0xe2,0x4,0x4,0x4,0x4,0x4,0xf8,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x21,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0xb,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x17,0x4,0xe2,0xe2,0xe2,0x2a,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x21,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x17,0x4,0xe2,0xe2,0xe2,0x2a,0xe2,0xe2,0xe2,0xe2,0xe2,0x1f,0xe2,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0xff,0xe2,0xe2,0xe2,0xe2,0xe2,0xe2,0x0,0x0,0x0,0x15,0x15,0x15,0x15,0x15,0x15,0x15,0x15,0x15,0x15,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x15,0x15,0x15,0x15,0x0,0x0,
194 };
195 CHECK(run_input(input, sizeof(input)) == 0);
196 }
197 SECTION("")
198 {
199 constexpr std::uint8_t input[] = {
200 0x0,0x1,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x21,0x0,0x0,0x0,0x0,0xff,0xff,0xff,0xff,0xff,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x8,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x27,0x0,0x21,0x0,0x0,0x0,0x0,0x0,0x1,0x0,0x3a,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x40,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x1,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x4,0x0,0x0,0x4,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0xe4,0xe4,0x0,0x0,0x0,0x0,0xe4,0x0,0xe4,0x0,0x0,0x0,0x0,0x0,0x8,0x0,
201 };
202 CHECK(run_input(input, sizeof(input)) == 0);
203 }
204
205 // buffer overflow when looking inside the sizes array for the
206 // index of a position
207 SECTION("")
208 {
209 constexpr std::uint8_t input[] = {
210 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x1,0x0,0x0,0xff,0xff,0xff,0xff,0x0,0x0,0x0,0x0,0x1,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x4,0x4,0x4,0x4,0x4,0x3,0xff,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x0,0x0,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x1e,0x0,0x4,0x4,0x4,0x4,0x4,0x3,0xff,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0xdb,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
211 };
212 CHECK(run_input(input, sizeof(input)) == 0);
213 }
214 SECTION("")
215 {
216 constexpr std::uint8_t input[] = {
217 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x9,0x0,0x0,0x0,0x0,0x0,0x1,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x3,0xfa,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x0,0x9,0x0,0x0,0x0,0x0,0x0,0x1,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x3,0xfa,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x3,0xfa,0x4,0x4,0x4,0x0,0x0,0x0,0x55,0x0,
218 };
219 CHECK(run_input(input, sizeof(input)) == 0);
220 }
221
222 // fail when deref some null node
223 SECTION("")
224 {
225 constexpr std::uint8_t input[] = {
226 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x4,0x0,0x0,0x4,0x0,0x0,0x0,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x4,0x0,0x4,0x4,0x4,0xe4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x6,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0xe5,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0xff,0x3,0x4,0x4,0x4,0x0,0x0,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x4,0x0,0x4,0x4,0x4,0xe4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x6,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0xe5,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x0,0x0,0x0,0x4,0x4,0x4,0x4,0xe1,0x0,0x0,0x80,0x0,0x0,0x1,0x6,0x0,0x0,0x0,0x0,0x0,0x4,0x0,0x75,0x75,0x45,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x1,0x0,0x0,0x0,0x75,0x4,0x0,
227 };
228 CHECK(run_input(input, sizeof(input)) == 0);
229 }
230 SECTION("")
231 {
232 constexpr std::uint8_t input[] = {
233 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x1,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x85,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0xff,0xff,0xff,0xff,0xff,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x5,0x4,0x28,0x4,0x4,0x4,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x24,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x0,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0xf3,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0xf3,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x4,0x3,0x4,0x4,0x4,0xff,0xff,0xff,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0xad,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,
234 };
235 CHECK(run_input(input, sizeof(input)) == 0);
236 }
237#endif
238}
239