bug: some miniscripts are being pointed as invalid, but are valid

[brunoerg]

Hi, recently I started developing bitcoinfuzz - differential fuzzing of Bitcoin implementations and libraries. One of the targets gets a string and checks whether it's a valid miniscript. The code I'm using to check it with rust-miniscript is:

#[no_mangle]
pub extern "C" fn rust_miniscript_from_str(input: *const c_char) -> bool {
    if let Ok(data) = unsafe { CStr::from_ptr(input) }.to_str() {
        if let Ok(_pol) = Miniscript::<String, Segwitv0>::from_str_insane(data) {
            return true
        } else if let Ok(_pol) = Miniscript::<String, Tap>::from_str_insane(data) {
            return true
        }
    }
    false
}

and bitcoinfuzz is crashing (rust-miniscript returning invalid) with the following miniscripts (and other ones):

nnnnnnnnnnnnnnnln:1
dv:0
lll:0
l:1

Could I be missing something in my code or is it a bug?

[tcharding]

Thanks for raising the issue. If this was a bug in miniscript I would expect the following test to crash also

    #[test]
    #[allow(unsafe_code)]
    fn foo() {
        use core::ffi::{CStr, c_char};

        extern "C" fn rust_miniscript_from_str(input: *const c_char) -> bool {
            if let Ok(data) = unsafe { CStr::from_ptr(input) }.to_str() {
                if let Ok(_pol) = Miniscript::<String, Segwitv0>::from_str_insane(data) {
                    return true
                } else if let Ok(_pol) = Miniscript::<String, Tap>::from_str_insane(data) {
                    return true
                }
            }
            false
        }

        let tcs = vec!["nnnnnnnnnnnnnnnln:1", "dv:0", "lll:0", "l:1"];

        for tc in tcs {
            let _ = rust_miniscript_from_str(tc.as_ptr() as *const i8);
            println!("Did not crash for input: {}", tc);
        }
    }

Is the function ever returning true, could the code be crashing before it even calls into miniscript?

[tcharding]

FTR I wrote and ran that as a unit test in miniscript/src/minscript/mod.rs and got

running 1 test
Did not crash for input: nnnnnnnnnnnnnnnln:1
Did not crash for input: dv:0
Did not crash for input: lll:0
Did not crash for input: l:1
test miniscript::tests::foo ... ok

[brunoerg]

Thanks for checking it, @tcharding.

I modified your example to:

for tc in tcs {
    let result_parse = rust_miniscript_from_str(tc.as_ptr() as *const i8);
    println!("{}", result_parse);
    println!("Did not crash for input: {}", tc);
}

and it's printing:

Did not crash for input: nnnnnnnnnnnnnnnln:1
false
Did not crash for input: dv:0
false
Did not crash for input: lll:0
false
Did not crash for input: l:1
test miniscript::bla::foo ... ok

I suppose it should print true, no? Sorry if I'm missing something, not super familiar with rust.

[tcharding]

Thanks for checking it

No sweat, happy to help.

I suppose it should print true, no?

There is no reason parsing those input strings must return Ok (implies true), IIUC your fuzz test is checking that the parsing function does not crash, which it doesn't. If you want to test valid strings in a fuzz test you should match on the result of from_str_insane and do more testing in the Ok match arm.

not super familiar with rust.

I'm not awesome at fuzzing but between us we might get there :)

[apoelstra]

Hi @brunoerg. Sorry for not checking on this after you reported it on IRC. Thanks for filing the issue.

@tcharding all these Miniscripts are valid, accepted by Bitcoin Core, and should be accepted by us too. And indeed, they are.

@brunoerg

    let result_parse = rust_miniscript_from_str(tc.as_ptr() as *const i8);

This code is not correct. tc is a Rust string, which is a UTF-8-encoded series of bytes with no null termination; tc.as_ptr() will return a *const u8 pointing to the first byte of the string. You then parse this using CStr::from_ptr which expects a pointer to the first signed byte of a null-terminated ASCII string.

[tcharding]

This code is not correct.

Ha! Thats a bug in my code not the original, does this uncovered a similar bug in the fuzz suite @brunoerg?

[brunoerg]

There is no reason parsing those input strings must return Ok (implies true), IIUC your fuzz test is checking that the parsing function does not crash, which it doesn't. If you want to test valid strings in a fuzz test you should match on the result of from_str_insane and do more testing in the Ok match arm.

Thanks, @tcharding. Basically, I only need to know if the miniscript is valid or not, I'm using it to compare with the result provided by Core.

Ha! Thats a bug in my code not the original, does this uncovered a similar bug in the fuzz suite @brunoerg?

I'm investigating, but I think so.

[apoelstra]

Basically, I only need to know if the miniscript is valid or not, I'm using it to compare with the result provided by Core.

It looks valid to me. Possibly it violates length constraints or something but parse_insane should accept it. And in my own internal tests where I just ran parse_insane directly on these strings, they all passed.

[brunoerg]

I fixed some things from bitcoinfuzz side and it crashed for the following miniscripts: lll:0 and ulllll:0. Core's implementation returns valid and rust-miniscript does not. I used the following test to make sure rust-miniscript was returning false for them and confirmed it. Anything might be wrong on how I'm validating the miniscripts with rust-miniscript?

use crate::{Miniscript, Segwitv0, Tap};

#[test]
#[allow(unsafe_code)]
fn foo() {
    fn test(input: &str) -> bool {
        if let Ok(_pol) = Miniscript::<String, Segwitv0>::from_str_insane(input) {
            return true
        } else if let Ok(_pol) = Miniscript::<String, Tap>::from_str_insane(input) {
            return true
        }
        false
    }

    let tcs = vec!["lll:0", "ulllll:0"];

    for tc in tcs {
        let result_parse = test(tc);
        println!("{} - {}", tc, result_parse);
    }
}

[apoelstra]

@brunoerg thanksI!!

So, we have an error LikelyFalse specifically rejecting l:0. The reasoning is that 0 is not a likely case. This is semantically equivalent to u:0 except less efficient.

Probably we should just drop this error variant. There are many other inefficiencies that we don't attempt to prevent. But OTOH, this is very easy and cheap to detect, and this inefficiency is almost certainly just a mistake..

cc @sipa do you have any thoughts on this? Should Core or the Miniscript definition reject l:0 (or u:1)?

[brunoerg]

Probably we should just drop this error variant. There are many other inefficiencies that we don't attempt to prevent. But OTOH, this is very easy and cheap to detect, and this inefficiency is almost certainly just a mistake..

Meanwhile, I'll make bitcoinfuzz skip these cases and continue fuzzing.

[darosior]

I don't think we should be making a backward incompatible change to Miniscript / Bitcoin Core just for ruling out an inefficiency. Even without considering backward compatibility i don't think it's necessary to special case them. They are semantically valid and it doesn't cost more to not rule them out. Sure, compilers shouldn't output such inefficient constructs in the first place, but once they are in use we might as well parse them.

So, we have an error LikelyFalse specifically rejecting l:0. The reasoning is that 0 is not a likely case. This is semantically equivalent to u:0 except less efficient.

nit: how so? They are literally the same expression: or_i(0,0).

[apoelstra]

nit: how so? They are literally the same expression: or_i(0,0)

Hmm. Yeah, you're right. The expression u:1 is or(0,1) which is equivalent and less efficient than l:1 (or(1,0))...so there is some sense in banning that (though I agree with you that we shouldn't do it)...I wonder if I was just thinking sloppily and assumed that there was a symmetric problem with l:0 without working through it.