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 = 2, unsigned Bits = 2>
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 std::cout << "/// new test run" << std::endl;
35 for (auto i = 0u; i < VarCount; ++i)
36 std::cout << "auto var" << i << " = vector_t{};" << std::endl;
37#endif
38
39 auto is_valid_var = [&] (auto idx) {
40 return idx >= 0 && idx < VarCount;
41 };
42 auto is_valid_index = [] (auto& v) {
43 return [&] (auto idx) { return idx >= 0 && idx < v.size(); };
44 };
45 auto is_valid_size = [] (auto& v) {
46 return [&] (auto idx) { return idx >= 0 && idx <= v.size(); };
47 };
48 auto can_concat = [] (auto&& v1, auto&& v2) {
49 using size_type = decltype(v1.size());
50 return v2.size() < (std::numeric_limits<size_type>::max() - v1.size());
51 };
52 auto can_insert = [] (auto&& v1) {
53 using size_type = decltype(v1.size());
54 return v1.size() < std::numeric_limits<size_type>::max();
55 };
56
57 return fuzzer_input{data, size}.run([&] (auto& in)
58 {
59 enum ops {
60 op_push_back,
61 op_update,
62 op_take,
63 op_drop,
64 op_concat,
65 op_push_back_move,
66 op_update_move,
67 op_take_move,
68 op_drop_move,
69 };
70 auto src = read<std::uint8_t>(in, is_valid_var);
71 auto dst = read<std::uint8_t>(in, is_valid_var);
72 switch (read<char>(in))
73 {
74 case op_push_back:
75 if (can_insert(vars[src])) {
76 IMMER_FUZZED_TRACE(
77 "var" << +dst << " = var" << +src <<
78 ".push_back(42);");
79 vars[dst] = vars[src].push_back(42);
80 }
81 break;
82 case op_update: {
83 auto idx = read<size_t>(in, is_valid_index(vars[src]));
84 IMMER_FUZZED_TRACE(
85 "var" << +dst << " = var" << +src <<
86 ".update(" << +idx << ", [] (auto x) { return x + 1; });");
87 vars[dst] = vars[src].update(idx, [] (auto x) { return x + 1; });
88 break;
89 }
90 case op_take: {
91 auto idx = read<size_t>(in, is_valid_size(vars[src]));
92 IMMER_FUZZED_TRACE(
93 "var" << +dst << " = var" << +src <<
94 ".take(" << +idx << ");");
95 vars[dst] = vars[src].take(idx);
96 break;
97 }
98 case op_drop: {
99 auto idx = read<size_t>(in, is_valid_size(vars[src]));
100 IMMER_FUZZED_TRACE(
101 "var" << +dst << " = var" << +src <<
102 ".take(" << +idx << ");");
103 vars[dst] = vars[src].drop(idx);
104 break;
105 }
106 case op_concat: {
107 auto src2 = read<std::uint8_t>(in, is_valid_var);
108 if (can_concat(vars[src], vars[src2])) {
109 IMMER_FUZZED_TRACE(
110 "var" << +dst << " = var" << +src << " + var" << +src2 << ";");
111 vars[dst] = vars[src] + vars[src2];
112 }
113 break;
114 }
115 case op_push_back_move: {
116 if (can_insert(vars[src])) {
117 IMMER_FUZZED_TRACE(
118 "var" << +dst << " = std::move(var" << +src <<
119 ").push_back(21);");
120 vars[dst] = std::move(vars[src]).push_back(21);
121 }
122 break;
123 }
124 case op_update_move: {
125 auto idx = read<size_t>(in, is_valid_index(vars[src]));
126 IMMER_FUZZED_TRACE(
127 "var" << +dst << " = std::move(var" << +src <<
128 ").update(" << +idx << ", [] (auto x) { return x + 1; });");
129 vars[dst] = std::move(vars[src])
130 .update(idx, [] (auto x) { return x + 1; });
131 break;
132 }
133 case op_take_move: {
134 auto idx = read<size_t>(in, is_valid_size(vars[src]));
135 IMMER_FUZZED_TRACE(
136 "var" << +dst << " = std::move(var" << +src <<
137 ").take(" << +idx << ");");
138 vars[dst] = std::move(vars[src]).take(idx);
139 break;
140 }
141 case op_drop_move: {
142 auto idx = read<size_t>(in, is_valid_size(vars[src]));
143 IMMER_FUZZED_TRACE(
144 "var" << +dst << " = std::move(var" << +src <<
145 ").drop(" << +idx << ");");
146 vars[dst] = std::move(vars[src]).drop(idx);
147 break;
148 }
149 default:
150 break;
151 };
152 return true;
153 });
154}
155
156} // anonymous namespace
157
158TEST_CASE("bug: use after free on move-take")
159{
160 SECTION("")
161 {
162 using vector_t = immer::flex_vector<int, immer::default_memory_policy, 2, 2>;
163 auto var0 = vector_t{};
164 auto var1 = vector_t{};
165 var0 = var0.push_back(42);
166 var0 = var0.push_back(42);
167 var0 = var0.push_back(42);
168 var0 = var0.push_back(42);
169 var0 = var0 + var0;
170 var0 = var0 + var0;
171 var0 = var0 + var0;
172 var0 = var0 + var0;
173 var0 = var0.push_back(42);
174 var0 = var0.push_back(42);
175 var0 = var0.push_back(42);
176 var0 = var0.push_back(42);
177 var0 = var0.push_back(42);
178 var1 = var0.push_back(42);
179 var0 = std::move(var0).take(68);
180 }
181
182#if __GNUC__ != 9
183 SECTION("")
184 {
185 constexpr std::uint8_t input[] = {
186 0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x1,0x0,0x0,0x0,0x0,0x0,0x40,0x0,0x0,0x0,0x0,0x4,0x4,0x0,0x0,0x0,0x4,0x0,0x0,0x0,0x4,0x0,0x0,0x0,0x4,0x0,0x0,0x4,0x0,0x0,0x0,0x4,0x0,0x0,0x0,0x4,0x0,0x0,0x0,0x4,0x0,0x0,0x0,0x4,0x0,0x0,0x0,0x1,0x0,0x0,0x0,0x7,0x41,0xb5,0x0,0x0,
187 };
188 CHECK(run_input(input, sizeof(input)) == 0);
189 }
190#endif
191}
192