< 返回版块

2019-04-30 20:09    责任编辑:jay

标签:test,chaos,code,random

本文转载自:http://wayslog.com/2019/04/02/deterministic-test-and-random-test/

确定性测试和随机性测试

2019-04-02

开篇

在开始本篇文章之前,我们首先来认清两个概念:

  1. 确定性测试:在给定一条输入,一定有对应的一条输出结果的前提下。那么如果我们的输入数量固定,那么输出的数据也一定是固定的。
  2. 随机性测试: 如果想办法让输入无限扩增,则在拥有无数条输入情况下,我们就拥有了无数条的输出。那么,我们拿无限的输入中的任意条来测试,则就拥有了随机性测试。

确定性测试

事实上,自打有 “验证” 这个概念起,确定性测试就一直伴随着人类本身,并且随着人类的进步和发展逐步推进。直到计算机科学领域,我们拥有了形式化和场景化的测试形式,我们称之为一条一条的 test case。也有疯狂的人提出了 TDD 编码,即,测试驱动开发。我们总假设我们的世界是有序的,至少在我们构筑的规则里是有序的,我们这种秩序进行测量,并辅以各种说明。

“嘿,你看!我的代码在这种情况下是OK的。”

“你知道么,我的这段代码在这种情况下一定会出问题。”

然而,这种确定性测试真的能帮我们证明:我的程序没问题么?

答案是不能的。我们必须要满足所有的case,现在你写出来的,没写出来的,现在不可能出现的,现在已经出现的。这样,我们在所有的场景下都通过了我们的代码,这段代码才可以被认为是没问题的。然而这可能么?在大多数情况下,不可能。当然了,你如果真写出诸如

fn assert_false(input: bool) {  
 if input {  
 panic!("");  
 }  
}  

这样的代码,自然他的input是有限的,那么他的case也就只有 truefalse 两种情况。然而事实上,我们面临的处境往往远远比这种场景复杂的多。比如我们解析一段128字节二进制数据,仅仅可能性就高达: 256^128 种,这里面我们想要枚举,那是基本上不可能的。庄子云:“吾生而有涯,而知也无涯。以有涯随无涯,殆已!”

我们在无法确定 full cover 测试用例的情况下,自然也就无法确保自身程序的正确性。即,绝对的符合行为是不存在的。那么,有没有办法逼近这种绝对的正确性呢?当然有,也就是我们今天要讲的 fuzz 测试。

随机性测试

我们将采取一定的算法,从一定的基础语料里生成一系列的基准 case,同时每个 case 由一定的随机规则生成更多的测试case,并且由我们的测试用例判断:当前测试语料有价值或者没有价值。如果没有价值则丢弃,有价值则重新加入进语料库中或者提升权重。整个过程可以称为遗传选择,也就是遗传算法的应用。最终,在足够长的时间遗传和选择之后,我们得会得到一个最终收敛的语料库,或者一个无限扩增的语料库,或者一个。。。PANIC!

这个 panic ,其实就是经过我们的语料积累之后随机测试出来的BUG!

当然,这个 panic 最终也是会被收录入语料库中,并且会给予高权重。

有趣的是,我们虽然能确定哪些case是有价值的,但是,从最终的语料库结果来说,并不是语料库的最终积累都会像你预期的那样。还是那句话,你能想到的case,语料库都会帮你找到,你想不到的,fuzz会帮你找到。

下面我们来进行一下实践:


cargo install cargo-fuzz  
git clone https://github.com/servo/rust-url.git  
cd rust-url  
git checkout bfa167b4e0253642b6766a7aa74a99df60a94048  
cargo fuzz init  
cargo fuzz list  
  
tee fuzz/fuzz_targets/fuzz_target_1.rs <<EOF  
<<#![no_main]  
<<#[macro_use] extern crate libfuzzer_sys;  
<<extern crate url;  
<<  
<<fuzz_target!(|data: &[u8]| {  
<<    if let Ok(s) = std::str::from_utf8(data) {  
<<        let _ = url::Url::parse(s);  
<<    }  
<<});  
<<EOF  
  
cargo fuzz run fuzz_target_1  

然后就是漫长的等待,经过了足够的随机测试之后,我们得到了如下的结果:

[0] ==14475== ERROR: libFuzzer: deadly signal  
[0]     #0 0x7f4907f099f7  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0xe29f7)  
[0]     #1 0x7f49080fd697  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2d6697)  
[0]     #2 0x7f49080d2672  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2ab672)  
[0]     #3 0x7f49080d252d  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2ab52d)  
[0]     #4 0x7f49080fde7c  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2d6e7c)  
[0]     #5 0x7f49072df88f  (/lib/x86_64-linux-gnu/libpthread.so.0+0xf88f)  
[0]     #6 0x7f4906d44066  (/lib/x86_64-linux-gnu/libc.so.6+0x35066)  
[0]     #7 0x7f4906d45447  (/lib/x86_64-linux-gnu/libc.so.6+0x36447)  
[0]     #8 0x7f490810f2e6  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2e82e6)  
[0]     #9 0x7f490810ac25  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2e3c25)  
[0]     #10 0x7f49080b8d9b  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x291d9b)  
[0]     #11 0x7f490810e668  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2e7668)  
[0]     #12 0x7f490810e101  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2e7101)  
[0]     #13 0x7f490810dfe5  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2e6fe5)  
[0]     #14 0x7f4908120e8c  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2f9e8c)  
[0]     #15 0x7f4908120dcb  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2f9dcb)  
[0]     #16 0x7f4907f75d2f  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x14ed2f)  
[0]     #17 0x7f4907f5d49d  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x13649d)  
[0]     #18 0x7f4907e6bdbc  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x44dbc)  
[0]     #19 0x7f4907e6b611  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x44611)  
[0]     #20 0x7f4907e6b194  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x44194)  
[0]     #21 0x7f49080b8a24  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x291a24)  
[0]     #22 0x7f490810214d  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2db14d)  
[0]     #23 0x7f490810f348  (/root/repo/rust-url/fuzz/target/x86_64-unknown-linux-gnu/debug/fuzz_target_1+0x2e8348)  
[0]  
[0] NOTE: libFuzzer has rudimentary signal handlers.  
[0]       Combine libFuzzer with AddressSanitizer or similar for better crash reports.  
[0] SUMMARY: libFuzzer: deadly signal  
[0] MS: 3 PersAutoDict-CrossOver-CMP- DE: "\x00\x0d"-"file"-; base unit: c212d1287c727dc38d49bacaf63f8ab2927458a6  
[0] 0x66,0x69,0x6c,0x65,0x3a,0x25,  
[0] file:%  
[0] artifact_prefix='/root/repo/rust-url/fuzz/artifacts/fuzz_target_1/'; Test unit written to /root/repo/rust-url/fuzz/artifacts/fuzz_target_1/crash-e2ce10aeea27d777611b40ef52e4db504bfa7a5f  
[0] Base64: ZmlsZTol  

然后,我们就可以在目标输出里找到我们的case: /root/repo/rust-url/fuzz/artifacts/fuzz_target_1/crash-e2ce10aeea27d777611b40ef52e4db504bfa7a5f, 文件内容:


file:%  

另外说一下

cargo fuzz run 的时候是可以指定 -j 选项的,一般开满CPU核心即可。fuzz 可以充分的利用多核优势,我开了 -j 20 ,几乎是在数秒之内就得到了最终结果。

以上,就是随机测试的一点小小的应用。