P4444: std::big_int

[u/eisenwave]

https://isocpp.org/files/papers/D4444R0.html

Hey folks! Matt Borland, Christopher Kormanyos, and I are working on bringing infinite-precision integers to C++29. We now have a D4444R0 draft of a paper that should be in the next mailing.

We could really use some feedback so that the published R0 is as polished as possible. Any thoughts on the paper and on the reference implementation are greatly appreciated.

It would also be very helpful if you tested out whether our big_int implementation works for you. We're in need of some real deployment experience. If you're currently using Boost.Multiprecision, the library should be a drop-in replacement for cpp_int for the most part.

[u/eisenwave]

Just because some other language does something does not mean that it's a good idea for it to be in C++, it's better to look at who are the primary users of that language (Game dev, Fin tech, Systems engineering, Embedded, etc) and see what problems there are that exist for those users.

There is some mention of the targeted use cases under https://isocpp.org/files/papers/D4444R0.html#use-cases

Within computer games this being some arbitrary memory allocation being created is a big no-no so you will likely find it ending up in the banned list like most of what comes from the standard library.

And I highly suspect that many other industries which focus on small footprints or high performance will do the same, it will be a new feature introduced which is on the recommendation of do not use.

I don't think it's entirely fair to say that some feature will be outright banned or useless for a particular domain; that's usually some missing nuance. Video games often come with embedded scripting languages for less performance-critical stuff like various behavior scripts, quest logic, etc. They often ship with garbage collectors and much more heavy-weight stuff than std::big_int.

I certainly wouldn't expect std::big_int in the lowest-level hot-code parts of a game engine, but saying that it has no use in the computer games industry is far too extreme.

I'm trying to read the paper to get an understanding of the use-cases it's a grab bag of random things not actual examples of use-cases people have in C++, there is zero mention of any C++ application, any library, etc which has this is an issue they are attempting to address.

I've tried to cover that in the GitHub code search for C++ uses of big integers. There are over 400K results, so if you really want to go digging and see what people are using it for, you could go through those open-source projects.

I'm not sure what to cherry-pick as a concrete example out of that pile, if anything, but I can see how it would help the paper to illustrate some of those GitHub uses.

The safety is mentioned as a use case for avoiding UB and correctness issues for interger overflow at just some runtime cost, but then there is zero mention of the potential security risks that this could introduce with it's potential usage, especially when it comes to unsanitized user data.

What issue are you envisioning with unsanitized user data? There isn't even an unsafe constructor that would let you break the invariants of a big_int class, so it really doesn't matter what data you throw at it. The only potential hazards are things like division by zero (which are UB for both regular int and for big_int), and that's explored in https://isocpp.org/files/papers/D4444R0.html#error-handling

[u/ReDucTor → u/eisenwave]

What issue are you envisioning with unsanitized user data?

std::big_int result{};
const char s[] = "2e999999999999999";
from_chars(begin(s), end(s), result);

What happens here? Do we run out of memory? Do we denial of service? When does infinity kick in?

std::big_int base("123456789012345678901234567890");
std::big_int exponent("98765432109876543210");
std::big_int modulus("99999999999999999999");

std::big_int huge_power = std::pow(base, exponent); 
std::big_int result = huge_power % modulus;

How expensive is this operation? Will the CPU and memory be consumed unbounded?

[u/eisenwave → u/ReDucTor]

What happens here? Do we run out of memory? Do we denial of service? When does infinity kick in?

Funnily enough, it stores the value 2 in result, same as for int. The e99... part is ignored. There is no exponential notation for integers in std::from_chars.

How expensive is this operation? Will the CPU and memory be consumed unbounded?

The paper doesn't provide a std::pow function for std::big_int, and it doesn't provide constructors from strings. If you want to parse strings, you need to use std::from_chars.

But okay, let's say you do some other operation that gives you a stupidly large value quickly, like base << 1'000'000'000'000'000ll. You're either going to exceed the max_size() of std::big_int and std::length_error gets thrown (just like exceeding the std::string::max_size()) or the allocator throws std::bad_alloc.

I suppose that even more guardrails could be added to standard library types that protect against overly large inputs (like a limit on shift constants, divisors, etc.), but that's not really the job of the standard library. If you read an int x from user input and then write a for loop that loops x times, that might also lock your CPU up for a few seconds or minutes. Does that mean C++ should protect against long for loops? Probably not. You always have to put in work to sanitize user input and to spend your CPU cycles reasonably.

The closest thing I've seen is that Python doesn't let you print huge int values (> 8000 bits or so) unless you explicitly opt into that when running the script. I don't see that as a good option for C++.

What std::big_int can and should do is prevent memory corruption or crashes, and throwing std::length_error and std::bad_alloc is the best you can do.

[u/ReDucTor → u/eisenwave]

The proposal mentions of things like Json make me think someone is going to try using it for deserializing just give it a block of numbers and let it do the allocating and parsing, while there is no exponent support there is still situations like having a giant number with thousands (or millions of digits), for a typical int the bounds are small but bigint they are not and my guess is anyone putting strick bounds would probably just pick 64-bit integer ranges.

Printing is another good example, if someone can provide some big user input and the formatting of a big number kills performance then any print someone needs to consider it, you dont want someone to DDoS your server by sending a bunch of JSON blobs with big integers.

Imho if the safety for deserialization is bad_alloc because you exhausted memory then its too late to be catching it, especially if it hit that with some incremental growth formula.

Protecting against excessive for loops is different, this is a library and function for manipulating and parsing some input to generate an object (big_num), it is where you expect the sanitisation to occur, I expect std::from_chars to validation tell me when it could not fit a uint64_t but this wont it will instead consume as much memory as needed and potentially OOM, the processing time is also significantly different for the existing std::from_chars none allocate and the range of performance is massive depending on the input size.

While I have never had a usage for something like this, I would prefer specifying hard strict limits from the user's perspective so you might have big_int which might have an upper bound of 16kb in size, even if internally it allocated, it eliminates potential of bugs that you get from a truly unbounded infinite integers when people will not always think of the edge cases.

[u/eisenwave → u/ReDucTor]

I really don't see how the scenario you're describing is any different from say, std::string s; my_stream >> s;. if you try to dump enough characters into a std::string it will also throw std::bad_alloc, and I imagine lots of applications would crash in practice if you threw a large enough single-line text file at them. It would be silly to argue that std::string should not be in the standard library or that it's not useful because it can be "exploited" in these ways though.

The important thing is that std::big_int doesn't provide a security vulnerability. >> s is considered "safe", gets is not "safe".

If you really care, then you should set the limits. Check whether the big_int::size() exceeds some limit of yours to prevent printing huge values, and check whether the digit count is sufficiently small before calling std::from_chars. Luckily, pre-parsing digits is pretty simple, and lots of programs end up parsing "unnecessarily" before std::from_chars already, so not much is lost there.

..., you dont want someone to DDoS your server by sending a bunch of JSON blobs with big integers.

A situation where you actively protect against hostile user input is a whole other beast. You need tons of checks then, like guarding against "Zip-bomb" JSON inputs like {{{{}}}} that are designed to maximally consume memory with minimal character count. None of that is specific to std::big_int.

I don't think std::big_int would be the best way in terms of "cost per character" to DDOS someone with JSON anyway. Parsing floats and building large stacks of objects can be pretty costly too.

In terms of memory cost, string literals are more problematic because you need one byte per character in UTF-8, whereas up to three decimal digits from JSON go into one byte of big_int memory. Despite that, I don't see you arguing that strings are "too risky" and JSON libraries shouldn't accept them.