Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Limit scale and precision of numbers in Alternator #6794

Closed
nyh opened this issue Jul 7, 2020 · 5 comments · Fixed by #13743
Closed

Limit scale and precision of numbers in Alternator #6794

nyh opened this issue Jul 7, 2020 · 5 comments · Fixed by #13743
Assignees
@nyh
Labels
area/alternator Alternator related Issues area/security
Milestone
5.3

Comments

@nyh
Copy link
Contributor

nyh commented Jul 7, 2020 •
edited

DynamoDB has a number type - for integers and floating point - which doesn't match any of the standard C++ types. It is basically a floating point number with 38 decimal digits of precision and decimal exponent between -130 and 125 - see more information
here or here.

In Alternator we implemented this number type using Scylla's big_decimal type. However, big_decimal (based on Java's BigDecimal) is an overkill: it allows for numbers of unlimited precision and huge scales - far beyond what DynamoDB allows.

The risk is that Alternator users may discover these unlimited-precision numbers in Alternator, and come to rely on them, so if in the future we may want to change the implementation of numbers (e.g., to make them take less space), these use cases will break.

When DynamoDB attempts to store or calculate numbers with excessive scale or precision, it produces an error and refuses to store such overflowing or over-precise numbers. We should behave similarly.
@nyh nyh added the area/alternator Alternator related Issues label Jul 7, 2020
@nyh
Copy link
Contributor Author

nyh commented Jul 7, 2020 •
edited

I just added in test_number.py five (UPDATED) xfailing tests which demonstrate different aspects of this issue:

  1. test_number_magnitude_not_allowed demonstrates that numbers with excessive magnitude can be stored.
  2. test_number_precision_not_allowed demonstrates that numbers with excessive precision can be stored.
  3. test_update_expression_plus_overflow demonstrates that numbers with excessive magnitude can be the result of a sum operation.
  4. test_update_expression_plus_imprecise demonstrates that numbers with excessive precision can be the result of a sum operation.
  5. test_number_magnitude_not_allowed_dos shows that numbers with excessive magnitude can not just be stored and retrieved - but also used in arithmetic operations and can lead to unlimited memory and CPU usage.

psarna pushed a commit that referenced this issue Jul 9, 2020
@nyh @psarna
alternator test: tests for the number type
9ff9cd3 
We had some tests for the number type in Alternator and how it can be
stored, retrieved, calculated and sorted, but only had rudementary tests
for the allowed magnitude and precision of numbers.

This patch creates a new test file, test_number.py, with tests aiming to
check exactly the supported magnitudes and precision of numbers.

These tests verify two things:

1. That Alternator's number type supports the full precision and magnitude
   that DynamoDB's number type supports. We don't want to see precision
   or magnitude lost when storing and retrieving numbers, or when doing
   calculations on them.

2. That Alternator's number type does not have *better* precision or
   magnitude than DynamoDB does. If it did, users may be tempted to rely
   on that implementation detail.

The three tests of the first type pass; But all four tests of the second
type xfail: Alternator currently stores numbers using big_decimal which
has unlimited precision and almost-unlimited magnitude, and is not yet
limited by the precision and magnitude allowed by DynamoDB.
This is a known issue - Refs #6794 - and these four new xfailing tests
will can be used to reproduce that issue.

Signed-off-by: Nadav Har'El <nyh@scylladb.com>
Message-Id: <20200707204824.504877-1-nyh@scylladb.com>
@slivne slivne added this to the 4.x milestone Jul 16, 2020
@nyh nyh mentioned this issue Oct 6, 2020
Open
@nyh
Copy link
Contributor Author

nyh commented Apr 30, 2023 •
edited

Unlimited precision also carries a risk of a DoS attack against Scylla: A malicious user might create a value of 1.0 and then ask to add 1e-1000000000 to it. This addition requires 1000000000 digits, and can cause unlimited CPU usage, non-preemption, and unlimited memory usage. One way to completely avoid this risk is to limit the exponent of all numbers.

Added in PR #13735 a test test_number_magnitude_not_allowed_dos to demonstrate this DoS problem.

@nyh nyh mentioned this issue Apr 30, 2023
Open
nyh added a commit to nyh/scylla that referenced this issue Apr 30, 2023
@nyh
test/alternator: reproducer for DoS in unlimited-recision addition
479f934 
As already noted in issue scylladb#6794, whereas DynamoDB limits the magnitude
of numbers to between 10^-130 and 10^125, Scylla does not. In this patch
we add yet another test for this problem, but unlike previous tests
which just shown too much magnitude being allowed which always sounded
like a benign problem - the test in this patch shows that this "feature"
can be used to DoS Scylla - a user user can send a short request that
causes arbitrarily-large allocations, stalls and CPU usage.

The test is currently marked "skip" because it cause cause Scylla to
take a very long time and/or run out of memory. It passes on DynamoDB
because the excessive magnitude is simply not allowed there.

Refs scylladb#6794

Signed-off-by: Nadav Har'El <nyh@scylladb.com>
@nyh nyh mentioned this issue Apr 30, 2023
Closed
@nyh
Copy link
Contributor Author

nyh commented May 1, 2023

Although I added the "Security" tag to this issue, note that as far as security issues go, this one is, at the moment, fairly minor:
It's "only" about a DoS, not privilege elevation, and moreover - it only allows an authenticated user to perform the DoS. This makes is less of a performance in a single-tenant installation, because only the tenant can ruin its own performance. But there's still a risk even in single-tenant installations in certain workload: If an application does number additions, and if an end-user could cause the database to insert arbitrary numbers into this addition work, inserting data like 1e-1000000 can cause the database to waste memory or CPU, or reach std::bad_alloc.

@nyh nyh self-assigned this May 1, 2023
@mykaul mykaul modified the milestones: 5.x, 5.4 May 1, 2023
nyh added a commit to nyh/scylla that referenced this issue May 1, 2023
@nyh
test/alternator: more tests for limits on number precision and magnitude
8d7844e 
We already have xfailing tests for issue scylladb#6794 - the missing checks on
precision and magnitudes of numbers in Alternator - but this patch adds
checks for additional corner cases. In particular we check the case that
numbers are used in a *key* column, which goes to a different code path
than numbers used in non-key columns, so it's worth testing as well.

Signed-off-by: Nadav Har'El <nyh@scylladb.com>
nyh added a commit to nyh/scylla that referenced this issue May 1, 2023
@nyh
alternator: add validation of numbers' magnitude and precision
421461e 
DynamoDB limits the allowed magnitude and precision of numbers - valid
decimal exponents are between -130 and 125 and up to 38 significant
decimal digitst are allowed. In contrast, Scylla uses the CQL "decimal"
type which offers unlimited precision. This can cause two problems:

1. Users might get used to this "unofficial" feature and start relying
   on it, not allowing us to switch to a more efficient limited-precision
   implementation later.

2. If huge exponents are allowed, e.g., 1e-1000000, summing such a
   number with 1.0 will result in a huge number, huge allocations and
   stalls. This is highly undesirable.

After this patch, all tests in test/alternator/test_number.py now
pass. The various failing tests which verify magnitude and precision
limitations in different places (key attributes, non-key attributes,
and arithmetic expressions) now pass - so their "xfail" tags are removed.

Fixes scylladb#6794

Signed-off-by: Nadav Har'El <nyh@scylladb.com>
@nyh nyh mentioned this issue May 1, 2023
Merged
@cvybhu cvybhu added area/cql and removed area/cql labels May 2, 2023
@cvybhu
Copy link
Contributor

cvybhu commented May 2, 2023

I remember that there was a similar issue with toJson: #8002, doing toJson(1e1000000) caused an OOM. Perhaps it could also be qualified as DoS/Security.

nyh added a commit to nyh/scylla that referenced this issue May 2, 2023
@nyh
test/alternator: more tests for limits on number precision and magnitude
d294167 
We already have xfailing tests for issue scylladb#6794 - the missing checks on
precision and magnitudes of numbers in Alternator - but this patch adds
checks for additional corner cases. In particular we check the case that
numbers are used in a *key* column, which goes to a different code path
than numbers used in non-key columns, so it's worth testing as well.

Signed-off-by: Nadav Har'El <nyh@scylladb.com>
nyh added a commit to nyh/scylla that referenced this issue May 2, 2023
@nyh
alternator: add validation of numbers' magnitude and precision
4401148 
DynamoDB limits the allowed magnitude and precision of numbers - valid
decimal exponents are between -130 and 125 and up to 38 significant
decimal digitst are allowed. In contrast, Scylla uses the CQL "decimal"
type which offers unlimited precision. This can cause two problems:

1. Users might get used to this "unofficial" feature and start relying
   on it, not allowing us to switch to a more efficient limited-precision
   implementation later.

2. If huge exponents are allowed, e.g., 1e-1000000, summing such a
   number with 1.0 will result in a huge number, huge allocations and
   stalls. This is highly undesirable.

After this patch, all tests in test/alternator/test_number.py now
pass. The various failing tests which verify magnitude and precision
limitations in different places (key attributes, non-key attributes,
and arithmetic expressions) now pass - so their "xfail" tags are removed.

Fixes scylladb#6794

Signed-off-by: Nadav Har'El <nyh@scylladb.com>
nyh added a commit to nyh/scylla that referenced this issue May 2, 2023
@nyh
test/alternator: reproducer for DoS in unlimited-precision addition
56b8b9d 
As already noted in issue scylladb#6794, whereas DynamoDB limits the magnitude
of numbers to between 10^-130 and 10^125, Scylla does not. In this patch
we add yet another test for this problem, but unlike previous tests
which just shown too much magnitude being allowed which always sounded
like a benign problem - the test in this patch shows that this "feature"
can be used to DoS Scylla - a user user can send a short request that
causes arbitrarily-large allocations, stalls and CPU usage.

The test is currently marked "skip" because it cause cause Scylla to
take a very long time and/or run out of memory. It passes on DynamoDB
because the excessive magnitude is simply not allowed there.

Refs scylladb#6794

Signed-off-by: Nadav Har'El <nyh@scylladb.com>
nyh added a commit to nyh/scylla that referenced this issue May 2, 2023
@nyh
test/alternator: more tests for limits on number precision and magnitude
0eccc49 
We already have xfailing tests for issue scylladb#6794 - the missing checks on
precision and magnitudes of numbers in Alternator - but this patch adds
checks for additional corner cases. In particular we check the case that
numbers are used in a *key* column, which goes to a different code path
than numbers used in non-key columns, so it's worth testing as well.

Signed-off-by: Nadav Har'El <nyh@scylladb.com>
@nyh nyh mentioned this issue May 2, 2023
Open
denesb added a commit that referenced this issue May 2, 2023
@denesb
Merge 'alternator: fix validation of numbers' magnitude and precision…
d6ed5bb 
…' from Nadav Har'El

DynamoDB limits the allowed magnitude and precision of numbers - valid
decimal exponents are between -130 and 125 and up to 38 significant
decimal digitst are allowed. In contrast, Scylla uses the CQL "decimal"
type which offers unlimited precision. This can cause two problems:

1. Users might get used to this "unofficial" feature and start relying
    on it, not allowing us to switch to a more efficient limited-precision
    implementation later.

2. If huge exponents are allowed, e.g., 1e-1000000, summing such a
    number with 1.0 will result in a huge number, huge allocations and
    stalls. This is highly undesirable.

This series adds more tests in this area covering additional corner cases,
and then fixes the issue by adding the missing verification where it's
needed. After the series, all 12 tests in test/alternator/test_number.py now pass.

Fixes #6794

Closes #13743

* github.com:scylladb/scylladb:
  alternator: unit test for number magnitude and precision function
  alternator: add validation of numbers' magnitude and precision
  test/alternator: more tests for limits on number precision and magnitude
  test/alternator: reproducer for DoS in unlimited-precision addition
@DoronArazii DoronArazii removed this from the 5.4 milestone May 3, 2023
@DoronArazii DoronArazii added this to the 5.3 milestone May 3, 2023
@denesb
Copy link
Contributor

denesb commented Dec 14, 2023

This fixes a minor issue, and is already part of 5.4. Not backporting further.

MeepoYang pushed a commit to storage-scsg/scylladb that referenced this issue Apr 28, 2024
@nyh
test/alternator: reproducer for DoS in unlimited-precision addition
85c9404 
As already noted in issue scylladb#6794, whereas DynamoDB limits the magnitude
of numbers to between 10^-130 and 10^125, Scylla does not. In this patch
we add yet another test for this problem, but unlike previous tests
which just shown too much magnitude being allowed which always sounded
like a benign problem - the test in this patch shows that this "feature"
can be used to DoS Scylla - a user user can send a short request that
causes arbitrarily-large allocations, stalls and CPU usage.

The test is currently marked "skip" because it cause cause Scylla to
take a very long time and/or run out of memory. It passes on DynamoDB
because the excessive magnitude is simply not allowed there.

Refs scylladb#6794

Signed-off-by: Nadav Har'El <nyh@scylladb.com>
MeepoYang pushed a commit to storage-scsg/scylladb that referenced this issue Apr 28, 2024
@nyh
test/alternator: more tests for limits on number precision and magnitude
6419b91 
We already have xfailing tests for issue scylladb#6794 - the missing checks on
precision and magnitudes of numbers in Alternator - but this patch adds
checks for additional corner cases. In particular we check the case that
numbers are used in a *key* column, which goes to a different code path
than numbers used in non-key columns, so it's worth testing as well.

Signed-off-by: Nadav Har'El <nyh@scylladb.com>
MeepoYang pushed a commit to storage-scsg/scylladb that referenced this issue Apr 28, 2024
@nyh
alternator: add validation of numbers' magnitude and precision
501d0ba 
DynamoDB limits the allowed magnitude and precision of numbers - valid
decimal exponents are between -130 and 125 and up to 38 significant
decimal digitst are allowed. In contrast, Scylla uses the CQL "decimal"
type which offers unlimited precision. This can cause two problems:

1. Users might get used to this "unofficial" feature and start relying
   on it, not allowing us to switch to a more efficient limited-precision
   implementation later.

2. If huge exponents are allowed, e.g., 1e-1000000, summing such a
   number with 1.0 will result in a huge number, huge allocations and
   stalls. This is highly undesirable.

After this patch, all tests in test/alternator/test_number.py now
pass. The various failing tests which verify magnitude and precision
limitations in different places (key attributes, non-key attributes,
and arithmetic expressions) now pass - so their "xfail" tags are removed.

Fixes scylladb#6794

Signed-off-by: Nadav Har'El <nyh@scylladb.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@nyh nyh

Labels
area/alternator Alternator related Issues area/security
Projects
None yet
Milestone
5.3
Development

Successfully merging a pull request may close this issue.

alternator: fix validation of numbers' magnitude and precision nyh/scylla
7 participants
@nyh @denesb @slivne @mykaul @cvybhu @scylladb-promoter @DoronArazii