PVS-Studio: Checking Bitcoin | Hacker News Reader

PVS-Studio: Checking Bitcoin

viva64.com

40 pointsProgC25 comments

I find it interesting comparing C/C++ with Rust in these cases, and I’m happy to say that in this case all of the problems reported would have been caught by the Rust compiler, either as errors or warnings, or are simply not possible.

- The first one is a standard unreachable code lint, which is by default a warning in Rust. (I’m a little surprised that it wouldn’t lead to warnings in other languages/compilers—is that really so?)

- Integer literals like 0x80 are not of a specific type in Rust, being rather int, i32, i64, uint, u32 or u64 as the context dictates—and in this context it would be inferred as i64. All these sorts of casts are explicit, too, fixing the entire class of issue—anything like this that PVS-Studio would catch is a compilation error in Rust.

- The whole copy constructors and = operator stuff is not relevant as Rust doesn’t have it (which, according to C++ programmers I have heard reports from, is good).

I’m looking forward to Rust being significant enough that tools like PVS-Studio get built around it. Although Rust prevents various classes of errors, human ingenuity is too great to keep all errors out! (Incidentally, you can write custom lints already.)

Where's the unreachable code in the first example? All the lines seems reachable to me.

The loop update is unreachable.

Ah right. Good point. Thanks.

Actually, in rust I get no warning with the functionally similar (and I think idiomatic) code:

    let l = [1i, 2, 3];

    for i in l.iter() {
        println!("{}", i);
        break;
    }

Obviously there's no explicit update as in the C code but since using iterators is the Rust way to iterate over collections I don't think it's fair to say that the rust compiler would have saved them on that one.

It’s not a break—it’s a return. So the stuff after the for-loop is unreachable.

The stuff after the for-loop is reachable if the for-loop is never entered. You can consider it to be an if-block instead, with a return at the end.

Ohhh, yes. I forgot that.

You're right but in this case it doesn't change anything (you can replace break; with return; and you won't have a warning either).

Actually, even if you add code after the for loop and the list is not empty Rust does not warn:

    fn main() {
        let l = [1i, 2, 3];

        for i in l.iter() {
            println!("{}", i);
            return;
        }

        println!("unreached");
    }

Builds without warning and prints a single "1".

Judging by the output with "--emit ir" when building with -O the rust compiler doesn't seem clever enough yet to realize that the whole vector and loop could just be factorized in a single "println!("{}", 1); return;" which probably explains why it can't detect that the return is always reached (i.e. the list is never empty). It even generates instructions to create the unused array elements:

    %1 = getelementptr inbounds [3 x i64]* %l, i64 0, i64 0
    store i64 1, i64* %1, align 8
    %2 = getelementptr inbounds [3 x i64]* %l, i64 0, i64 1
    store i64 2, i64* %2, align 8
    %3 = getelementptr inbounds [3 x i64]* %l, i64 0, i64 2
    store i64 3, i64* %3, align 8

The Rust compiler cannot assume the loop will never iterate, the analysis phases that could determine that are ran before optimizations.

And optimizations are performed by LLVM, with no feedback to the compiler.

I actually analyzed your example, and what happens there is that `i` is a reference to array elements and we don't pass enough metadata to LLVM to inform it of pointers with a fixed number of usable bytes, so it believes the formatting runtime is capable of accessing more of the array.

The problem is not breaking before an iteration has completed, it's unreachable code. In your example, you have no unreachable code.

However, move that print statement to the line below your break, and you'll see that Rust gives an 'unreachable code' warning.

    let l = [1i, 2, 3];

    for i in l.iter() {
        println!("{}", i);
        break;
    }

And I'm pretty sure it can be configured to not compile at all on warning. Can someone with the project confirm?

You forgot to update the snippet but I get what you mean, but that's not the problem in the C code in TFA, the return is the last operation in the for loop (no code after it).

But you are correct that rust does emit a warning if you put the println! after the break while gcc 4.9.1 builds the following without any warning even with -Wextra:

    #include <stdio.h>

    int main()
    {
      int i;

      for (i = 0; i < 10; i++) {
	break;

	printf("unreached\n");
      }

      return 0;
    }

Which is pretty surprising to me, especially since the optimizer is clever enough to completely remove the for loop and the static string from the asm output, so unlike rust they actually know it's unused.

> I’m looking forward to Rust being significant enough that tools like PVS-Studio get built around it.

I wonder if it would be possible to decouple languages and analyzers? Would be nice if the PVS people had an option to validate something like an abstract syntax tree or a blob of bytecode...

Looking at the examples of errors that it finds ( http://www.viva64.com/en/examples/ ), most of them do look like abstract problems ("identical sub-expressions to the left and to the right of the 'foo' operator", for example)

> I wonder if it would be possible to decouple languages and analyzers?

I think it's technically possible, but it's a very hard problem.

> Would be nice if the PVS people had an option to validate something like an abstract syntax tree or a blob of bytecode...

Different languages demand different AST structures, and even different implementations of the same language might use different ASTs. Another problem with that approach is that languages can have wildly different semantics, and static analyzers are primarily focused on the semantics of program fragments.

It is possible to operate on bytecode. Findbugs[1] operates on Java bytecode, but it's intended for use on Java programs and I'm not entirely sure how well it works on Scala programs (I've never tried). Bytecode has similar issues as ASTs: bytecode instruction sets are usually designed specifically for implementing a particular language, and are often ill-suited as targets for other languages. I think this problem is more manageable than the AST problem.

Edit: forgot the Findbugs link

[1]: http://en.wikipedia.org/wiki/FindBugs

Are there any types of error which mighz happen in Rust but are impossible in C++?

Rust defines some things as undefined behavior that are not undefined behavior in C++. For example, C++ does not consider it undefined behavior when two mutable references alias the same memory. If you manage to create such a situation (using unsafe code, for example), Rust will assume that the two references cannot alias one another, and so may generate incorrect code where C++ would not.

Of course, by creating multiple mutable references to the same object by unsafe transmutation (which must be explicit, naturally), you have violated Rust’s invariants. But in safe code you cannot do that, and even doing it in unsafe code is not trivial, though it’s not excessively difficult either.

> .... I’m happy to say that in this case all of the problems reported would have been caught by the Rust compiler....

What about Last Line Effect ? :) http://www.viva64.com/en/b/0260/

That reads a bit sloppy to me.

"This is some function related to cryptography. I don't know what it does exactly, and maybe I have found a real EPIC FAIL."

Maybe before you wrote your 1000 word article with custom made illustration you could have spent a little timing digging in the code and understanding what this function actually does? Or at least ask some bitcoin devs their opinion? If you have actually found a vulnerability in bitcoin and disclose it that way it's not even sloppy, it's irresponsible.

1) This is a joke. Perhaps unfortunate translation. Below it is written that the risk is small: You see, it's a popular trend nowadays to find epic errors related to security. But this one is most likely a tiny bug or even a correct piece of code written purposely.

2) I can not attentive examine each piece of code. Estimate the amount of work that I do :) - http://www.viva64.com/en/a/0084/ , http://www.viva64.com/en/examples/

according to bitcoin's github repo, the epic fail has had a pull request since april now. https://github.com/bitcoin/bitcoin/pull/4011

it appears that bitcoin devs are dragging their feet here. to quote gmaxwell (the author of the PR),

> it would catch any case where the public keys and the secret keys in the wallet didn't agree with each other, either due to corruption or due to malicious modification (e.g. so that newly issued keys were really someone elses private keys). How much thats worth I dunno.

and for completeness: the relevant issue posted by the OP: https://github.com/bitcoin/bitcoin/issues/4601

Since they're not sure if they found a security related error or not, I would rather make a disclosure to Bitcoin dev team fist before going public with it.

I think it's pretty obvious that static analysis is essential when code correctness is necessary. Of course the use of C++ is questionable, unless high performance is needed.

Hang on, how is this not wrong? It's supposed to iterate through mapCryptedKeys but never gets past the first...

From my understanding, that code is just a verification that the password you entered to decrypt your wallet was correct. It works by testing one of the addresses in the wallet (verifying that the secret key matches the pubkey address).

If one works, they should all work. If they don't then the wallet file is probably corrupted. So it'd be a nice check for corruption but doesn't seem to have much of a security implication.

Reply on news.ycombinator.com