1 /*
2 This file is part of solidity.
3
4 solidity is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 solidity is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with solidity. If not, see <http://www.gnu.org/licenses/>.
16 */
17 // SPDX-License-Identifier: GPL-3.0
18
19 #include <libsolidity/formal/SymbolicTypes.h>
20
21 #include <libsolidity/formal/EncodingContext.h>
22
23 #include <libsolidity/ast/TypeProvider.h>
24 #include <libsolidity/ast/Types.h>
25 #include <libsolutil/CommonData.h>
26 #include <memory>
27 #include <vector>
28
29 using namespace std;
30 using namespace solidity::util;
31 using namespace solidity::smtutil;
32
33 namespace solidity::frontend::smt
34 {
35
smtSort(frontend::Type const & _type)36 SortPointer smtSort(frontend::Type const& _type)
37 {
38 switch (smtKind(_type))
39 {
40 case Kind::Int:
41 if (auto const* intType = dynamic_cast<IntegerType const*>(&_type))
42 return SortProvider::intSort(intType->isSigned());
43 if (auto const* fixedType = dynamic_cast<FixedPointType const*>(&_type))
44 return SortProvider::intSort(fixedType->isSigned());
45 return SortProvider::uintSort;
46 case Kind::Bool:
47 return SortProvider::boolSort;
48 case Kind::Function:
49 {
50 auto fType = dynamic_cast<frontend::FunctionType const*>(&_type);
51 solAssert(fType, "");
52 vector<SortPointer> parameterSorts = smtSort(fType->parameterTypes());
53 auto returnTypes = fType->returnParameterTypes();
54 SortPointer returnSort;
55 // TODO change this when we support tuples.
56 if (returnTypes.size() == 0)
57 // We cannot declare functions without a return sort, so we use the smallest.
58 returnSort = SortProvider::boolSort;
59 else if (returnTypes.size() > 1)
60 // Abstract sort.
61 returnSort = SortProvider::uintSort;
62 else
63 returnSort = smtSort(*returnTypes.front());
64 return make_shared<FunctionSort>(parameterSorts, returnSort);
65 }
66 case Kind::Array:
67 {
68 shared_ptr<ArraySort> array;
69 if (isMapping(_type))
70 {
71 auto mapType = dynamic_cast<frontend::MappingType const*>(&_type);
72 solAssert(mapType, "");
73 array = make_shared<ArraySort>(smtSortAbstractFunction(*mapType->keyType()), smtSortAbstractFunction(*mapType->valueType()));
74 }
75 else if (isStringLiteral(_type))
76 {
77 auto stringLitType = dynamic_cast<frontend::StringLiteralType const*>(&_type);
78 solAssert(stringLitType, "");
79 array = make_shared<ArraySort>(SortProvider::uintSort, SortProvider::uintSort);
80 }
81 else
82 {
83 frontend::ArrayType const* arrayType = nullptr;
84 if (auto const* arr = dynamic_cast<frontend::ArrayType const*>(&_type))
85 arrayType = arr;
86 else if (auto const* slice = dynamic_cast<frontend::ArraySliceType const*>(&_type))
87 arrayType = &slice->arrayType();
88 else
89 solAssert(false, "");
90
91 solAssert(arrayType, "");
92 array = make_shared<ArraySort>(SortProvider::uintSort, smtSortAbstractFunction(*arrayType->baseType()));
93 }
94
95 string tupleName;
96 auto sliceArrayType = dynamic_cast<ArraySliceType const*>(&_type);
97 ArrayType const* arrayType = sliceArrayType ? &sliceArrayType->arrayType() : dynamic_cast<ArrayType const*>(&_type);
98 if (
99 (arrayType && (arrayType->isString() || arrayType->isByteArray())) ||
100 _type.category() == frontend::Type::Category::StringLiteral
101 )
102 tupleName = "bytes";
103 else if (arrayType)
104 {
105 auto baseType = arrayType->baseType();
106 // Solidity allows implicit conversion also when assigning arrays.
107 // So if the base type potentially has a size, that size cannot go
108 // in the tuple's name.
109 if (auto tupleSort = dynamic_pointer_cast<TupleSort>(array->range))
110 tupleName = tupleSort->name;
111 else if (
112 baseType->category() == frontend::Type::Category::Integer ||
113 baseType->category() == frontend::Type::Category::FixedPoint
114 )
115 tupleName = "uint";
116 else if (baseType->category() == frontend::Type::Category::FixedBytes)
117 tupleName = "fixedbytes";
118 else
119 tupleName = arrayType->baseType()->toString(true);
120
121 tupleName += "_array";
122 }
123 else
124 tupleName = _type.toString(true);
125
126 tupleName += "_tuple";
127
128 return make_shared<TupleSort>(
129 tupleName,
130 vector<string>{tupleName + "_accessor_array", tupleName + "_accessor_length"},
131 vector<SortPointer>{array, SortProvider::uintSort}
132 );
133 }
134 case Kind::Tuple:
135 {
136 vector<string> members;
137 auto const& tupleName = _type.toString(true);
138 vector<SortPointer> sorts;
139
140 if (auto const* tupleType = dynamic_cast<frontend::TupleType const*>(&_type))
141 {
142 auto const& components = tupleType->components();
143 for (unsigned i = 0; i < components.size(); ++i)
144 members.emplace_back(tupleName + "_accessor_" + to_string(i));
145 sorts = smtSortAbstractFunction(tupleType->components());
146 }
147 else if (auto const* structType = dynamic_cast<frontend::StructType const*>(&_type))
148 {
149 solAssert(!structType->recursive(), "");
150 auto const& structMembers = structType->structDefinition().members();
151 for (auto member: structMembers)
152 members.emplace_back(tupleName + "_accessor_" + member->name());
153 sorts = smtSortAbstractFunction(applyMap(
154 structMembers,
155 [](auto var) { return var->type(); }
156 ));
157 }
158 else
159 solAssert(false, "");
160
161 return make_shared<TupleSort>(tupleName, members, sorts);
162 }
163 default:
164 // Abstract case.
165 return SortProvider::uintSort;
166 }
167 }
168
smtSort(vector<frontend::Type const * > const & _types)169 vector<SortPointer> smtSort(vector<frontend::Type const*> const& _types)
170 {
171 vector<SortPointer> sorts;
172 for (auto const& type: _types)
173 sorts.push_back(smtSort(*type));
174 return sorts;
175 }
176
smtSortAbstractFunction(frontend::Type const & _type)177 SortPointer smtSortAbstractFunction(frontend::Type const& _type)
178 {
179 if (isFunction(_type))
180 return SortProvider::uintSort;
181 return smtSort(_type);
182 }
183
smtSortAbstractFunction(vector<frontend::Type const * > const & _types)184 vector<SortPointer> smtSortAbstractFunction(vector<frontend::Type const*> const& _types)
185 {
186 vector<SortPointer> sorts;
187 for (auto const& type: _types)
188 if (type)
189 sorts.push_back(smtSortAbstractFunction(*type));
190 else
191 sorts.push_back(SortProvider::uintSort);
192 return sorts;
193 }
194
smtKind(frontend::Type const & _type)195 Kind smtKind(frontend::Type const& _type)
196 {
197 if (isNumber(_type))
198 return Kind::Int;
199 else if (isBool(_type))
200 return Kind::Bool;
201 else if (isFunction(_type))
202 return Kind::Function;
203 else if (isMapping(_type) || isArray(_type))
204 return Kind::Array;
205 else if (isTuple(_type) || isNonRecursiveStruct(_type))
206 return Kind::Tuple;
207 // Abstract case.
208 return Kind::Int;
209 }
210
isSupportedType(frontend::Type const & _type)211 bool isSupportedType(frontend::Type const& _type)
212 {
213 return isNumber(_type) ||
214 isBool(_type) ||
215 isMapping(_type) ||
216 isArray(_type) ||
217 isTuple(_type) ||
218 isNonRecursiveStruct(_type);
219 }
220
isSupportedTypeDeclaration(frontend::Type const & _type)221 bool isSupportedTypeDeclaration(frontend::Type const& _type)
222 {
223 return isSupportedType(_type) ||
224 isFunction(_type);
225 }
226
newSymbolicVariable(frontend::Type const & _type,std::string const & _uniqueName,EncodingContext & _context)227 pair<bool, shared_ptr<SymbolicVariable>> newSymbolicVariable(
228 frontend::Type const& _type,
229 std::string const& _uniqueName,
230 EncodingContext& _context
231 )
232 {
233 bool abstract = false;
234 shared_ptr<SymbolicVariable> var;
235 frontend::Type const* type = &_type;
236
237 if (auto userType = dynamic_cast<UserDefinedValueType const*>(type))
238 return newSymbolicVariable(userType->underlyingType(), _uniqueName, _context);
239
240 if (!isSupportedTypeDeclaration(_type))
241 {
242 abstract = true;
243 var = make_shared<SymbolicIntVariable>(frontend::TypeProvider::uint256(), type, _uniqueName, _context);
244 }
245 else if (isBool(_type))
246 var = make_shared<SymbolicBoolVariable>(type, _uniqueName, _context);
247 else if (isFunction(_type))
248 {
249 auto const& fType = dynamic_cast<FunctionType const*>(type);
250 auto const& paramsIn = fType->parameterTypes();
251 auto const& paramsOut = fType->returnParameterTypes();
252 auto findFunctionParam = [&](auto&& params) {
253 return find_if(
254 begin(params),
255 end(params),
256 [&](frontend::Type const* _paramType) { return _paramType->category() == frontend::Type::Category::Function; }
257 );
258 };
259 if (
260 findFunctionParam(paramsIn) != end(paramsIn) ||
261 findFunctionParam(paramsOut) != end(paramsOut)
262 )
263 {
264 abstract = true;
265 var = make_shared<SymbolicIntVariable>(TypeProvider::uint256(), type, _uniqueName, _context);
266 }
267 else
268 var = make_shared<SymbolicFunctionVariable>(type, _uniqueName, _context);
269 }
270 else if (isInteger(_type))
271 var = make_shared<SymbolicIntVariable>(type, type, _uniqueName, _context);
272 else if (isFixedPoint(_type))
273 var = make_shared<SymbolicIntVariable>(type, type, _uniqueName, _context);
274 else if (isFixedBytes(_type))
275 {
276 auto fixedBytesType = dynamic_cast<frontend::FixedBytesType const*>(type);
277 solAssert(fixedBytesType, "");
278 var = make_shared<SymbolicFixedBytesVariable>(type, fixedBytesType->numBytes(), _uniqueName, _context);
279 }
280 else if (isAddress(_type) || isContract(_type))
281 var = make_shared<SymbolicAddressVariable>(_uniqueName, _context);
282 else if (isEnum(_type))
283 var = make_shared<SymbolicEnumVariable>(type, _uniqueName, _context);
284 else if (isRational(_type))
285 {
286 auto rational = dynamic_cast<frontend::RationalNumberType const*>(&_type);
287 solAssert(rational, "");
288 if (rational->isFractional())
289 var = make_shared<SymbolicIntVariable>(frontend::TypeProvider::uint256(), type, _uniqueName, _context);
290 else
291 var = make_shared<SymbolicIntVariable>(type, type, _uniqueName, _context);
292 }
293 else if (isMapping(_type) || isArray(_type))
294 var = make_shared<SymbolicArrayVariable>(type, type, _uniqueName, _context);
295 else if (isTuple(_type))
296 var = make_shared<SymbolicTupleVariable>(type, _uniqueName, _context);
297 else if (isStringLiteral(_type))
298 {
299 auto stringType = TypeProvider::stringMemory();
300 var = make_shared<SymbolicArrayVariable>(stringType, type, _uniqueName, _context);
301 }
302 else if (isNonRecursiveStruct(_type))
303 var = make_shared<SymbolicStructVariable>(type, _uniqueName, _context);
304 else
305 solAssert(false, "");
306 return make_pair(abstract, var);
307 }
308
isInteger(frontend::Type const & _type)309 bool isInteger(frontend::Type const& _type)
310 {
311 return _type.category() == frontend::Type::Category::Integer;
312 }
313
isFixedPoint(frontend::Type const & _type)314 bool isFixedPoint(frontend::Type const& _type)
315 {
316 return _type.category() == frontend::Type::Category::FixedPoint;
317 }
318
isRational(frontend::Type const & _type)319 bool isRational(frontend::Type const& _type)
320 {
321 return _type.category() == frontend::Type::Category::RationalNumber;
322 }
323
isFixedBytes(frontend::Type const & _type)324 bool isFixedBytes(frontend::Type const& _type)
325 {
326 return _type.category() == frontend::Type::Category::FixedBytes;
327 }
328
isAddress(frontend::Type const & _type)329 bool isAddress(frontend::Type const& _type)
330 {
331 return _type.category() == frontend::Type::Category::Address;
332 }
333
isContract(frontend::Type const & _type)334 bool isContract(frontend::Type const& _type)
335 {
336 return _type.category() == frontend::Type::Category::Contract;
337 }
338
isEnum(frontend::Type const & _type)339 bool isEnum(frontend::Type const& _type)
340 {
341 return _type.category() == frontend::Type::Category::Enum;
342 }
343
isNumber(frontend::Type const & _type)344 bool isNumber(frontend::Type const& _type)
345 {
346 return isInteger(_type) ||
347 isFixedPoint(_type) ||
348 isRational(_type) ||
349 isFixedBytes(_type) ||
350 isAddress(_type) ||
351 isContract(_type) ||
352 isEnum(_type);
353 }
354
isBool(frontend::Type const & _type)355 bool isBool(frontend::Type const& _type)
356 {
357 return _type.category() == frontend::Type::Category::Bool;
358 }
359
isFunction(frontend::Type const & _type)360 bool isFunction(frontend::Type const& _type)
361 {
362 return _type.category() == frontend::Type::Category::Function;
363 }
364
isMapping(frontend::Type const & _type)365 bool isMapping(frontend::Type const& _type)
366 {
367 return _type.category() == frontend::Type::Category::Mapping;
368 }
369
isArray(frontend::Type const & _type)370 bool isArray(frontend::Type const& _type)
371 {
372 return _type.category() == frontend::Type::Category::Array ||
373 _type.category() == frontend::Type::Category::StringLiteral ||
374 _type.category() == frontend::Type::Category::ArraySlice;
375 }
376
isTuple(frontend::Type const & _type)377 bool isTuple(frontend::Type const& _type)
378 {
379 return _type.category() == frontend::Type::Category::Tuple;
380 }
381
isStringLiteral(frontend::Type const & _type)382 bool isStringLiteral(frontend::Type const& _type)
383 {
384 return _type.category() == frontend::Type::Category::StringLiteral;
385 }
386
isNonRecursiveStruct(frontend::Type const & _type)387 bool isNonRecursiveStruct(frontend::Type const& _type)
388 {
389 auto structType = dynamic_cast<StructType const*>(&_type);
390 return structType && !structType->recursive();
391 }
392
isInaccessibleDynamic(frontend::Type const & _type)393 bool isInaccessibleDynamic(frontend::Type const& _type)
394 {
395 return _type.category() == frontend::Type::Category::InaccessibleDynamic;
396 }
397
minValue(frontend::IntegerType const & _type)398 smtutil::Expression minValue(frontend::IntegerType const& _type)
399 {
400 return smtutil::Expression(_type.minValue());
401 }
402
minValue(frontend::Type const * _type)403 smtutil::Expression minValue(frontend::Type const* _type)
404 {
405 solAssert(isNumber(*_type), "");
406 if (auto const* intType = dynamic_cast<IntegerType const*>(_type))
407 return intType->minValue();
408 if (auto const* fixedType = dynamic_cast<FixedPointType const*>(_type))
409 return fixedType->minIntegerValue();
410 if (
411 dynamic_cast<AddressType const*>(_type) ||
412 dynamic_cast<ContractType const*>(_type) ||
413 dynamic_cast<EnumType const*>(_type) ||
414 dynamic_cast<FixedBytesType const*>(_type)
415 )
416 return 0;
417 solAssert(false, "");
418 }
419
maxValue(frontend::IntegerType const & _type)420 smtutil::Expression maxValue(frontend::IntegerType const& _type)
421 {
422 return smtutil::Expression(_type.maxValue());
423 }
424
maxValue(frontend::Type const * _type)425 smtutil::Expression maxValue(frontend::Type const* _type)
426 {
427 solAssert(isNumber(*_type), "");
428 if (auto const* intType = dynamic_cast<IntegerType const*>(_type))
429 return intType->maxValue();
430 if (auto const* fixedType = dynamic_cast<FixedPointType const*>(_type))
431 return fixedType->maxIntegerValue();
432 if (
433 dynamic_cast<AddressType const*>(_type) ||
434 dynamic_cast<ContractType const*>(_type)
435 )
436 return TypeProvider::uint(160)->maxValue();
437 if (auto const* enumType = dynamic_cast<EnumType const*>(_type))
438 return enumType->numberOfMembers() - 1;
439 if (auto const* bytesType = dynamic_cast<FixedBytesType const*>(_type))
440 return TypeProvider::uint(bytesType->numBytes() * 8)->maxValue();
441 solAssert(false, "");
442 }
443
setSymbolicZeroValue(SymbolicVariable const & _variable,EncodingContext & _context)444 void setSymbolicZeroValue(SymbolicVariable const& _variable, EncodingContext& _context)
445 {
446 setSymbolicZeroValue(_variable.currentValue(), _variable.type(), _context);
447 }
448
setSymbolicZeroValue(smtutil::Expression _expr,frontend::Type const * _type,EncodingContext & _context)449 void setSymbolicZeroValue(smtutil::Expression _expr, frontend::Type const* _type, EncodingContext& _context)
450 {
451 solAssert(_type, "");
452 _context.addAssertion(_expr == zeroValue(_type));
453 }
454
zeroValue(frontend::Type const * _type)455 smtutil::Expression zeroValue(frontend::Type const* _type)
456 {
457 solAssert(_type, "");
458 if (isSupportedType(*_type))
459 {
460 if (isNumber(*_type))
461 return 0;
462 if (isBool(*_type))
463 return smtutil::Expression(false);
464 if (isArray(*_type) || isMapping(*_type))
465 {
466 auto tupleSort = dynamic_pointer_cast<TupleSort>(smtSort(*_type));
467 solAssert(tupleSort, "");
468 auto sortSort = make_shared<SortSort>(tupleSort->components.front());
469
470 std::optional<smtutil::Expression> zeroArray;
471 auto length = bigint(0);
472 if (auto arrayType = dynamic_cast<ArrayType const*>(_type))
473 {
474 zeroArray = smtutil::Expression::const_array(smtutil::Expression(sortSort), zeroValue(arrayType->baseType()));
475 if (!arrayType->isDynamicallySized())
476 length = bigint(arrayType->length());
477 }
478 else if (auto mappingType = dynamic_cast<MappingType const*>(_type))
479 zeroArray = smtutil::Expression::const_array(smtutil::Expression(sortSort), zeroValue(mappingType->valueType()));
480 else
481 solAssert(false, "");
482
483 solAssert(zeroArray, "");
484 return smtutil::Expression::tuple_constructor(
485 smtutil::Expression(std::make_shared<SortSort>(tupleSort), tupleSort->name),
486 vector<smtutil::Expression>{*zeroArray, length}
487 );
488
489 }
490 if (isNonRecursiveStruct(*_type))
491 {
492 auto const* structType = dynamic_cast<StructType const*>(_type);
493 auto structSort = dynamic_pointer_cast<TupleSort>(smtSort(*_type));
494 return smtutil::Expression::tuple_constructor(
495 smtutil::Expression(make_shared<SortSort>(structSort), structSort->name),
496 applyMap(
497 structType->structDefinition().members(),
498 [](auto var) { return zeroValue(var->type()); }
499 )
500 );
501 }
502 solAssert(false, "");
503 }
504 // Unsupported types are abstracted as Int.
505 return 0;
506 }
507
isSigned(frontend::Type const * _type)508 bool isSigned(frontend::Type const* _type)
509 {
510 solAssert(smt::isNumber(*_type), "");
511 bool isSigned = false;
512 if (auto const* numberType = dynamic_cast<RationalNumberType const*>(_type))
513 isSigned |= numberType->isNegative();
514 else if (auto const* intType = dynamic_cast<IntegerType const*>(_type))
515 isSigned |= intType->isSigned();
516 else if (auto const* fixedType = dynamic_cast<FixedPointType const*>(_type))
517 isSigned |= fixedType->isSigned();
518 else if (
519 dynamic_cast<AddressType const*>(_type) ||
520 dynamic_cast<ContractType const*>(_type) ||
521 dynamic_cast<EnumType const*>(_type) ||
522 dynamic_cast<FixedBytesType const*>(_type)
523 )
524 return false;
525 else
526 solAssert(false, "");
527
528 return isSigned;
529 }
530
typeBvSizeAndSignedness(frontend::Type const * _type)531 pair<unsigned, bool> typeBvSizeAndSignedness(frontend::Type const* _type)
532 {
533 if (auto const* intType = dynamic_cast<IntegerType const*>(_type))
534 return {intType->numBits(), intType->isSigned()};
535 else if (auto const* fixedType = dynamic_cast<FixedPointType const*>(_type))
536 return {fixedType->numBits(), fixedType->isSigned()};
537 else if (auto const* fixedBytesType = dynamic_cast<FixedBytesType const*>(_type))
538 return {fixedBytesType->numBytes() * 8, false};
539 else
540 solAssert(false, "");
541 }
542
setSymbolicUnknownValue(SymbolicVariable const & _variable,EncodingContext & _context)543 void setSymbolicUnknownValue(SymbolicVariable const& _variable, EncodingContext& _context)
544 {
545 setSymbolicUnknownValue(_variable.currentValue(), _variable.type(), _context);
546 }
547
setSymbolicUnknownValue(smtutil::Expression _expr,frontend::Type const * _type,EncodingContext & _context)548 void setSymbolicUnknownValue(smtutil::Expression _expr, frontend::Type const* _type, EncodingContext& _context)
549 {
550 _context.addAssertion(symbolicUnknownConstraints(_expr, _type));
551 }
552
symbolicUnknownConstraints(smtutil::Expression _expr,frontend::Type const * _type)553 smtutil::Expression symbolicUnknownConstraints(smtutil::Expression _expr, frontend::Type const* _type)
554 {
555 solAssert(_type, "");
556 if (isEnum(*_type) || isInteger(*_type) || isAddress(*_type) || isFixedBytes(*_type))
557 return _expr >= minValue(_type) && _expr <= maxValue(_type);
558 else if (
559 auto arrayType = dynamic_cast<ArrayType const*>(_type);
560 arrayType && !arrayType->isDynamicallySized()
561 )
562 return smtutil::Expression::tuple_get(_expr, 1) == arrayType->length();
563 else if (isArray(*_type) || isMapping(*_type))
564 /// Length cannot be negative.
565 return smtutil::Expression::tuple_get(_expr, 1) >= 0;
566
567 return smtutil::Expression(true);
568 }
569
symbolicTypeConversion(frontend::Type const * _from,frontend::Type const * _to)570 optional<smtutil::Expression> symbolicTypeConversion(frontend::Type const* _from, frontend::Type const* _to)
571 {
572 if (_to && _from)
573 // StringLiterals are encoded as SMT arrays in the generic case,
574 // but they can also be compared/assigned to fixed bytes, in which
575 // case they'd need to be encoded as numbers.
576 if (auto strType = dynamic_cast<StringLiteralType const*>(_from))
577 if (auto fixedBytesType = dynamic_cast<FixedBytesType const*>(_to))
578 {
579 if (strType->value().empty())
580 return smtutil::Expression(size_t(0));
581 auto bytesVec = util::asBytes(strType->value());
582 bytesVec.resize(fixedBytesType->numBytes(), 0);
583 return smtutil::Expression(u256(toHex(bytesVec, util::HexPrefix::Add)));
584 }
585
586 return std::nullopt;
587 }
588
589 }
590