Add assertion to randrange that input is not 0 #17293

From the comment in randrange, their is an implicit argument that randrange cannot accept an argument of 0. If the argument is 0, then we have to return {}, which is not possible in a uint64_t.

The current code takes a very interesting approach, which is to return [0..std::numeric_limits<uint64_t>]. This can cause all sorts of fun problems, like allocating a lot of memory, accessing random memory (maybe with your private keys), and crashing the computer entirely.

This gives us three choices of how to make it "safe":

1. return Optional<uint64_t>
2. Change the return type to [0..range]
3. Return 0 if 0
4. Assert(range)

So which solution is best?

1. seems a bit overkill, as it makes any code using randrange worse.
2. Changing the return type as in 2 could be acceptable, but it imposes the potential overflow checking on the caller (which is what we want).
3. An interesting option -- effective makes the return type in {0} U [0..range]. But this is a bad choice, because it leads to code like vec[randrange(vec.size())], which is incorrect for an empty vector. Null set should mean null set.
4. Assert(range) stands out as the best mitigation for now, with perhaps a future change to solution 2. It prevents the error from propagating at the earliest possible time, so the program crashes cleanly rather than by freezing the computer or accessing random memory.

In the short term, asserting is probably best. The function is simply not intended to be called with argument 0.

Perhaps longer term it would make sense to (also?) have a function that takes a max (and optionally a min?) argument, and returns something in that range, inclusive. The advantage is that it can be used for any range, including up to the limit.

Concept ACK

Nice find! @JeremyRubin Have you checked the call sites for the possibility of any of them calling randrange with argument 0?

https://github.com/bitcoin/bitcoin/blob/badca85e2c0bf1720fca8a516adbf4b3f1d7e4d9/src/net_processing.cpp#L946-L953

g_orphan_list.size() == 0 is impossible here?

@JeremyRubin After taking a quick look at the various direct and indirect users of randrange I'm not certain that there are no code paths where randrange(0) could be called.

Note that GetRand, GetRandInt and Shuffle all use randrange under the hood.

This can be used to analyse the call sites:

$ git grep -E '(randrange|GetRand|GetRandInt|Shuffle)\(' -- "*.cpp" "*.h"

Adding assert(range); in randrange feels a bit risky given its direct and indirect call sites.

Perhaps ASSUME(range); would be appropriate to start with?

Given --enable-debug or --enable-fuzzers then ASSUME(condition); fails fatally if condition does not hold.

You can cherry-pick in ASSUME(…); from PR #16136.

Seems reasonable for now, ACK https://github.com/bitcoin/bitcoin/pull/17293/commits/a35b6824f3a0bdb68c5aef599c0f17562689970e

@practicalswift I did in fact check. The issue came up while I was testing #17292, I accidentally put in randrange(vec.size()) somewhere, and it had the nice effect of crashing my computer :)

This lead me to check the rest of the codebase, including that example in net_processing. I did think it was a bug at first, but I think the loops pre-conditions (mapOrphanTransactions.size() > 0 && for every element in mapOrphans there is one in g_orphan_list) imply g_orphan_list.size() != 0.

I checked the others and they also have pre-conditions that make 0 impossible. edit: I didn't check the tests, just the program code.

I think you are incorrect that assert in randrange is dangerous. It's the other way around: returning a too-big number is dangerous, as it can lead to entire system crashes (as in on my system) as opposed to graceful panics or it can lead to random memory probing and leaking secrets. We should improve all the call sites and maybe do the range projection as sipa notes, but we should not ever return something outside the specified output, even if that means crashing.

I think you are incorrect that assert in randrange is dangerous. It's the other way around: returning a too-big number is dangerous, as it can lead to entire system crashes (as in on my system) as opposed to graceful panics or it can lead to random memory probing and leaking secrets.

I think it depends on the call site. You're correct in that for some of the call sites an assertion failure is clearly preferable (if we were to trigger this condition) :)

I think this is a good place for an assertion. Returning anything else is unsafe. ACK a35b6824f3a0bdb68c5aef599c0f17562689970e

ACK a35b6824f3a0bdb68c5aef599c0f17562689970e.