Minimizing "expected likelihood" / "expected impact": low-level datatype validity, bounds checking, defensive coding

[cwgoes]

In part a summary of ongoing discussion about the audit being conducted by @mattdf.

I think we should endeavor to minimize two distinct quantities:

1. The "expected likelihood" of writing bugs
2. The "expected impact" of a (random) bug in production

The most important factor for (1) is writing clear code with well-separated abstractions. I think we can improve as following:

1. "Function dependencies" - where two functions must be called in succession - should be minimized. This may be OK in exceptional and very obvious cases (keeper.Handle can presume msg.ValidateBasic) but should be avoided in general (AddCoins should not presume msg.ValidateBasic).
2. Types should restrict the domain of values as much as possible. The main case here is the unsigned/signed debate (for block height, evidence height, etc.). @melekes wrote a piece favoring signed here. Unfortunately, Golang just does not support builtin checked arithmetic - maybe we could create wrapper types which perform the checking? That seems like the safest option, although it would add some overhead and require a serious refactor.

The most important factor for (2) is quickly catching the issue and doing something intelligent (usually, halting the state machine so we can examine the problem). We already code pretty defensively in this way, but I think we can further improve as following:

1. We should avoid function "contracts" - all functions with a strict input domain larger than their expected input domain should assert validity of the input immediately at the beginning of the function, so if the function is passed invalid input we'll just halt.
   1. (Bad) examples: AddCoins, SubtractCoins in x/bank, Slash in x/stake
2. Wherever in the state machine we presume an invariant (e.g. many related to the various cliff validator bugs) that is cheap to assert, we should assert it. This is situation-specific, I think we'll just need to read through the code and see where we can do this. Two options which may help:
   1. Separate out complex functions into smaller ones - then this reduces to (1) above
   2. Similarly, but without the function separation, every time we load a value (e.g. from the store, or from another function which reads the store), treat the loaded value as an untrusted input and assert all assumed properties.

We should test the efficacy of our defensive coding with a chaos monkey-style approach: randomly changing signs, reordering two lines of code, calling a similarly named function, etc. - I'm not yet sure of the best way to implement this (and we don't want to go overboard), but I think it would be a good way to measure whether or not we're likely to correctly handle an unknown bug in production.

(please feel free to edit / add ideas / comment)

[ValarDragon]

I agree with your points for addressing (2), and function dependencies.

I'm strongly opposed to making our own "overflow safe uint64". This is such a performance loss to use everywhere. Inlining is probably not going to happen, no more constants either. I think we can make the gas meter safe by enforcing a "Max Gas Limit" thats much less than 2**64. (We only do addition here, not multiplication)

We should test the efficacy of our defensive coding with a chaos monkey-style approach: randomly changing signs, reordering two lines of code, calling a similarly named function, etc. - I'm not yet sure of the best way to implement this (and we don't want to go overboard), but I think it would be a good way to measure whether or not we're likely to correctly handle an unknown bug in production.

I doubt the ability of this to give us useful feedback as a general thing. I guess we could try it, but it seems quite weird to me, and the class of error this would produce are less likely if we have diligent reviews. I think if we want to go through with this, it should be something we do during the code freeze time, and even then I don't think its a great usage of time. If we aim to make all of our PR's significantly smaller / easier to review, then this sort of thing will be much easier to catch in the review process.

Instead what would be far more useful imo is to go through scenarios to test time to recovery, when someone trying to introduce a targeted bug in the state machine. I believe this was an idea @jessysaurusrex had.

[cwgoes]

If we aim to make all of our PR's significantly smaller / easier to review, then this sort of thing will be much easier to catch in the review process.

I agree that we should do this - in any case - but it does nothing to address the bulk of the code-for-launch, which has already been merged.

I'm not sure about "chaos monkey" - it might be a waste of time as you say. I think it would be helpful to have some idea of whether or not our defensive coding is working (is likely to catch bugs). Maybe there's another way to do that.

[melekes]

@melekes wrote a piece favoring signed here

Please remember that the article is mainly about a choice which was made in a particular case. Your set of conditions might be different, and hence the choice will be different.

I am not sure about SDK, but Tendermint can use more unsigned ints. It's great when the compiler checks the bounds.

👍 To having asserts (especially in places where we have ints), but a) you need to write them b) you need to support this code. So one needs to be selective. I.e., verify all external input as soon as possible, assert later only core logic & critical sections. asserts should not be used as a substitute for errors https://golang.org/doc/faq#assertions.

Use

• https://github.com/dvyukov/go-fuzz
• https://github.com/zimmski/go-mutesting
• testing/quick and/or https://github.com/leanovate/gopter

========
https://www.reddit.com/r/learnprogramming/comments/4npim9/10_coding_practices_which_allows_nasa_to_write/

• No function should be longer than what can be printed on a single sheet of paper in a standard reference format with one line per statement and one line per declaration. Typically, this means no more than about 60 lines of code per function.
• The assertion density of the code should average to a minimum of two assertions per function. Assertions are used to check for anomalous conditions that should never happen in real-life executions. Assertions must always be side-effect free and should be defined as Boolean tests. When an assertion fails, an explicit recovery action must be taken, e.g., by returning an error condition to the caller of the function that executes the failing assertion. Any assertion for which a static checking tool can prove that it can never fail or never hold violates this rule (I.e., it is not possible to satisfy the rule by adding unhelpful “assert(true)” statements).

[ValarDragon]

Please remember that the article is mainly about a choice which was made in a particular case. Your set of conditions might be different, and hence the choice will be different.

Totally agreed. For the usecases we are considering, sdk.Coins, Gas, I think uints make total sense. There is no fear of overflow in sdk.Coins since we use big ints. For gas, I think having overflow into negatives is more dangerous than overflow back to 0. (respectively underflow to max value) Also we don't do multiplication in gas, so its super easy to check for underflowing / overflowing.

+1 To having asserts (especially in places where we have ints), but a) you need to write them b) you need to support this code. So one needs to be selective. I.e., verify all external input as soon as possible, assert later only core/critical logic. asserts should not be used as a substitute for errors https://golang.org/doc/faq#assertions.

Totally agreed, sanitizing input ASAP makes the remaining code much cleaner / simpler.

I agree that we should do this - in any case - but it does nothing to address the bulk of the code-for-launch, which has already been merged.

Good point. I'm still not very hopeful about the chaos monkey idea, but the best way to confirm / reject these would be try it for an hour or two.

I think using external fuzzers, and improving our tests & simulations would be a better utilization of time to locate these edge cases.

[rigelrozanski]

"Function dependencies" - where two functions must be called in succession - should be minimized.

👍

all functions with a strict input domain larger than their expected input domain should assert validity of the input immediately at the beginning of the function,

👍

great idea's we should absolutely compile many of these ideas into the tendermint coding standards

Maybe this should be moved from an issue into a coding standards PR with the mentioned ideas/reasoning

[jaekwon]

I agree with the original principles but not with some of the later discussion.

uints vs ints

It's easier to catch bugs by checking for a negative number, than to check for overflow. If there are numbers where we need to do arithmetic, it's better to use signed ints for this reason. Where uint/int is being used instead of bigints or other types for performance and code simplicity (+ instead .Add) reasons, it makes sense to just check x >= 0 at the end of a few computations.

For gas, I think having overflow into negatives is more dangerous than overflow back to 0

It wouldn't overflow back to 0, it would turn into some arbitrary positive number. That's arguably more dangerous because it's hard to check for in the first place. Either case is dangerous, it's more a question of, what makes it possible to test for correctness? x >= 0 is, but this option is not available with unsigned ints.

Signed integers are Golang's ergonomic primitive for numerical computation where it is assumed that you will follow up with bounds checking, if needed. The alternative is to use special purpose types like BigInt or whatnot. Otherwise you need to enforce the usage of special functions for that arithmetic that takes these ints as inputs. However, when you're using signed or unsigned ints, somebody is inevitably going to use +/- on them and end up with a dangerous overflow/underflow. So, we should be checking for bounds after all arithmetic operations as much as possible. We could do both, but turning signed ints into unsigned ints is only making our lives more difficult because it masks overflows.

Also, Golang uses ints a lot, in its standard libraries and in how for-loops work. This makes using unsigned ints even more dangerous because you end up with a significant amount of casting. We can make this casting safer again by using special safety methods, but all of that is unnecessary if we just use signed ints.

I think we can make the gas meter safe by enforcing a "Max Gas Limit" thats much less than 2**64.

I agree, this is similar to checking x >= 0, we can also do x < small_limit in cases where the set of operations on the number is restricted.

Tendermint can use more unsigned ints. It's great when the compiler checks the bounds.

For the reasons stated above, it's not actually better. That's what I used to think, and after trying that I came to the above conclusion that when using numbers where arithmetic is expected, it is better to use ints (at least in Golang). Please don't revert Tendermint to use uints where arithmetic is being used.

Types should restrict the domain of values as much as possible. The main case here is the unsigned/signed debate (for block height, evidence height, etc.). @melekes wrote a piece favoring signed here. Unfortunately, Golang just does not support builtin checked arithmetic - maybe we could create wrapper types which perform the checking? That seems like the safest option, although it would add some overhead and require a serious refactor.

I disagree about unsigned/signed as written above, though there are probably cases where we can apply this better elsewhere in the codebase. I think we do a pretty good job of it though.

Contracts vs Assert

We should avoid function "contracts" - all functions with a strict input domain larger than their expected input domain should assert validity of the input immediately at the beginning of the function, so if the function is passed invalid input we'll just halt.
i. (Bad) examples: AddCoins, SubtractCoins in x/bank, Slash in x/stake

If by AddCoins you mean that we don't check for positiveness of the coins added, I agree. But there are real cases where you do want contracts for performance reasons, and it ends up being more complicated to solve for both performance & validation. For example, a function might require a sorted slice. It is often too expensive to check the slice again for every function that requires a sorted slice as input. It's also infeasible to try to memoize this on a slice, because the memoized boolean of "sorted" is difficult to keep updated w/ modifications to the slice. Doing this also introduces more complexity in the code than just requiring a contract.

So, I disagree that "all functions" should assert validity immediately. One needs to do the full tradeoff of performance, code complexity, and risk, to make the right decision. Contracts are great when we need them, though we need to be vigilant in documenting them whenever one is assumed.

Wherever in the state machine we presume an invariant (e.g. many related to the various cliff validator bugs) that is cheap to assert, we should assert it. This is situation-specific.

This kinda goes to my point above. Checking the validity of inputs is checking an invariant that the function only gets called with certain inputs. Sometimes you need function contacts because it's not cheap or easy otherwise.

Similarly, but without the function separation, every time we load a value (e.g. from the store, or from another function which reads the store), treat the loaded value as an untrusted input and assert all assumed properties.

That's the kind of use-case that obj.ValidateBasic() is primarily for, to validate an isolated piece of data. It probably makes sense to work on a light ORM-type thing that handles this automatically, and also the key-duplication issue that Rige was talking about.

No function should be longer than what can be printed on a single sheet of paper in a standard reference format with one line per statement and one line per declaration. Typically, this means no more than about 60 lines of code per function.

Every rule has exceptions :)

[rigelrozanski]

Great points Jae, thanks for bringing more clarity to the int/uint discussion.

few side comments:

No function should be longer than what can be printed on a single sheet of paper in a standard reference format with one line per statement and one line per declaration. Typically, this means no more than about 60 lines of code per function.
Every rule has exceptions :)

sure, but I tend to agree with the original comment to bring functions down to < 60 lines of code - I'm sure there is some obscure exception for this, but from my experience, it's often possible to break up large functions and, if done correctly, this almost always increases code clarity.

So, I disagree that "all functions" should assert validity immediately. One needs to do the full tradeoff of performance, code complexity, and risk, to make the right decision. Contracts are great when we need them, though we need to be vigilant in documenting them whenever one is assumed.

I tend to think that we should develop a way to include more-expensive invariance checks or validity checks which can be compiled away for production binary - I'm not sure this functionality exists in golang - but it would be good to have, more validity checks everywhere would have certainly saved debug time by now if this had been our practice all along - but again, it's overkill for a production binary so we really need a switch for it.

In terms of code complexity, I don't think more complex checks throughout (for debugging as just explained) need to muddy the code base, we can always abstract debugging validity checks to a function tucked away.

Not sure what you mean by "risk" here. Risk of introducing more bugs or backdoors?

[jaekwon]

I tend to think that we should develop a way to include more-expensive invariance checks or validity checks which can be compiled away for production binary - I'm not sure this functionality exists in golang - but it would be good to have, more validity checks everywhere would have certainly saved debug time by now if this had been our practice all along - but again, it's overkill for a production binary so we really need a switch for it.

That sounds like a good idea in many cases. We should support a config for development mode.

Not sure what you mean by "risk" here. Risk of introducing more bugs or backdoors?

Yes.

[melekes]

Tendermint can use more unsigned ints. It's great when the compiler checks the bounds.
For the reasons stated above, it's not actually better. That's what I used to think, and after trying that I came to the above conclusion that when using numbers where arithmetic is expected, it is better to use ints (at least in Golang). Please don't revert Tendermint to use uints where arithmetic is being used.

I probably needed to be more specific to avoid being misunderstood. How about: "Tendermint can use more unsigned ints when there's no arithmetic OR no subtraction, and we're sure it will be that way." I generally agree with the points stated above for uint vs. int case where arithmetic is being used.

That's the kind of use-case that obj.ValidateBasic() is primarily for, to validate an isolated piece of data.

Refs tendermint/tendermint#2232

[ValarDragon]

You raised good points re Gas, and I agree. I still think sdk.Coin.Amount should be a Uint though, since there is no overflow possible. (We're using big ints, with our own panic on overflow)

[ValarDragon]

Upon further thought, I actually think gas should still be a uint.

We can still catch all overflows using the gas API, by using a smaller bound (theres only addition / subtraction so this isn't hard). The reason for wanting it to be a uint is less about overflow fears. Its about a class of bugs that allows one to set the gas arbitrarily.

Another issue that we now have to deal with when building blocks / counting gas in a block is that each gasWanted is non-negative, as otherwise it could overfill the total gas block gas allocation. (We have less fear of overflows, since the mempool should already filter that no tx > is MaxBlockGas)

I don't really feel convinced that we're gaining anything by using ints (as I think overflow checks for addition are super simple), but I do feel like were causing more complex implementation details for anyone whose trying to build mempools / tendermint integrations, and are opening ourselves up to a class of vulnerabilities that could arbitrarily set the gas to be negative. (e.g. something allows me to set GasMeter.Gas to be -1, next thing that adds to it makes it positive, no check failed, but I could now get an "overstuffed" block)

Also, Golang uses ints a lot, in its standard libraries and in how for-loops work. This makes using unsigned ints even more dangerous because you end up with a significant amount of casting. We can make this casting safer again by using special safety methods, but all of that is unnecessary if we just use signed ints.

Golang uses lots of casting to uint in its code as well within their for loops. They also frequently just uses uint primitives as well. Since its compiled code, uint casting is zero cost AFAIK. If were enforcing uint size to be < 2**63, theres no special extra safety methods needed here. (any such safety method would be equivalent to checking that its non-negative right before the loop with regular ints, as would be required in the described model)

[jackzampolin]

This was a great discussion. Please reopen with actionable items if you have issues.