search

Zilliqa / scilla-rtl

Execute Scilla code compiled by the Scilla -> LLVM compiler.
GNU General Public License v3.0
8 stars 3 forks source link

Implement safe arithmetic for integer arithmetic builtins #2

Closed vaivaswatha closed 3 years ago

vaivaswatha commented 4 years ago

The run-time library (SRTL) currently uses boost::multiprecision::cpp_int to represent values of types Int128, Int256, Uint128, Uint256. While this works for unsigned integers, boost uses a sign-magnitude representation for signed integers (rather than 2s complement). Scilla's signed integers however had 2s complement semantics.

This means that while the Int256.min in Scilla is -57896044618658097711785492504343953926634992332820282019728792003956564819968, boost's Int256.min is -115792089237316195423570985008687907853269984665640564039457584007913129639935. This isn't a problem that can be fixed by using a boost type with one less bit (as remarked in the boost documentation itself) because 2s complement allows one extra negative value than the max positive value, but that is not the case with sign-magnitude representation.

There are two ways we can consider solving this:

  1. Write wrappers around boost's Int256 (and Int128) to prevent / detect negatives going beyond a value.
  2. Write safe-math wrappers around GMP. This can possibly be done by wrapping safe-math around boost's cpp_int too (but with arbitrary sizes).

A test case with wrong output already exists.

vaivaswatha commented 4 years ago

Update: This Issue now boils down to implementing safe arithmetic on top of wideint (which uses 2s complement) that was introduced in PR #3.

Safe arithmetic reference: https://github.com/Zilliqa/scilla/blob/master/src/base/SafeArith.ml

vaivaswatha commented 4 years ago

Perhaps existing checks using LLVM's sanitizers can be used https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html. Not sure if they'll work for larger integers.

vaivaswatha commented 3 years ago

Also provide safe downcast utilities, this is needed to implement integer->integer conversion builtins.

vaivaswatha commented 3 years ago

With https://github.com/Zilliqa/scilla-rtl/pull/36, a check has been added in SafeInt(const std::string &), the constructor that builds safe integers from their string representation. This check isn't fully correct though as it doesn't handle https://github.com/Zilliqa/scilla/pull/982

vaivaswatha commented 3 years ago

36 added support for sub and div. Tests for these both are failing. wideint is returning incorrect result (assert((int256_t (0) - int256_t(-1)).to_string() == "1"); fails.

These tests are disabled and need to be enabled before this Issue is closed.

vaivaswatha commented 3 years ago

36 added support for sub and div. Tests for these both are failing. wideint is returning incorrect result (assert((int256_t (0) - int256_t(-1)).to_string() == "1"); fails.

These tests are disabled and need to be enabled before this Issue is closed.

We could perhaps switch to using this: https://github.com/ckormanyos/wide-integer. It seems to be maintained and well tested.

vaivaswatha commented 3 years ago

36 added support for sub and div. Tests for these both are failing. wideint is returning incorrect result (assert((int256_t (0) - int256_t(-1)).to_string() == "1"); fails.

These tests are disabled and need to be enabled before this Issue is closed.

We could perhaps switch to using this: https://github.com/ckormanyos/wide-integer. It seems to be maintained and well tested.

Done in #38. So we're back to just implementing safety check wrapers in SafeInt.cpp. With that, this issue can be closed.