Fuzzing

2023-08-18

Bonjour à toutes et à tous 😀

Le TDD est une excellente manière de créer du logiciel que l'on a envie de modifier.

Mais d'un autre côté c'est aussi un moyen de provoquer des erreurs en étant trop sûr de soi et de son code.

A la main

En effet le TDD et les test cases qui lui sont associés ne sont que le reflets de ce que l'on connaît ou croit connaître du comportement de notre logiciel.

En d'autres termes, le reflet de notre Ignorance. 🙈

Par exemple ce code

fn is_hello(data: &str) -> bool {
    let data = data.as_bytes();
    if data[0] == b'h' && 
       data[1] == b'e' && 
       data[2] == b'l' && 
       data[3] == b'l' && 
       data[4] == b'o' {
        return true;
    }
    false
}

Et voici les test cases associés

#[test]
fn right() {
    assert!(is_hello("hello"))
}

#[test]
fn wrong() {
    assert!(!is_hello("pas hello"))
}

Bon c'est vert, c'est cool 😁

Mais voici que vient cette valeur en production.

hell

Vous vous dites, c'est insignifiant.

Et bien essayons ^^

#[test]
fn wrong2() {
    assert!(!is_hello("hell"))
}

Boom 💥

index out of bounds: the len is 4 but the index is 4
thread 'wrong2' panicked at 'index out of bounds: the len is 4 but the index is 4'

Votre code panic, et oui, même avec du Rust, si on fait n'importe quoi, il arrive également nimporte quoi ^^

La question est donc : "Comment trouver les test cases qui font casser le code ?".

Et de préférence avant d'arriver en production ^^

Pour cela, nous allons réfléchir à l'envers.

Pour commencer, on découpe notre if en 5 if et on inverse la condition.

fn is_hello(data: &str) -> bool {
    let data = data.as_bytes();

    if data[0] != b'h' {
        return false
    }

    if data[1] != b'e' {
        return false
    }

    if data[2] != b'l' {
        return false
    }

    if data[3] != b'l' {
        return false
    }

    if data[4] != b'o' {
        return false
    }

    true
}

Ce code à le même comportement que l'autre, essayez vous verrez.

La deuxième chose que l'on va faire c'est mettre en place un second paramètre qui va compter le nombre de lignes exécutées.

fn is_hello(data: &str, counter: &mut usize) -> bool {
    let data = data.as_bytes();
    *counter += 1;

    if data[0] != b'h' {
        *counter += 1;
        return false;
    }

    if data[1] != b'e' {
        *counter += 1;
        return false;
    }

    if data[2] != b'l' {
        *counter += 1;
        return false;
    }

    if data[3] != b'l' {
        *counter += 1;
        return false;
    }

    if data[4] != b'o' {
        *counter += 1;
        return false;
    }
    
    *counter+=1;
    true
}

Si on se fait une petite fonction de test

fn format(data: &str) {
    let mut counter = 0;
    is_hello(data, &mut counter);
    println!("{data} => {counter}");
}

#[test]
fn test() {
    format("toto");
    format("pas hello");
    format("hallo");
    format("helro");
    format("hella");
    format("hello");
}

On obtient

toto => 2
pas hello => 2
hallo => 3
helro => 5
hella => 6
hello => 7

On voit que plus l'on se rapproche du "hello" plus on se rapproche également du "hell" 😈

Une heuristique peut donc de choisir aléatoirement un caractères et venir tester son counter.

S'il augmente, c'est que nous sommes en train de "descendre" dans le code, comme nous avons deux objectifs:

couvrir le plus de code possible
détecter les entrées qui font bugger

Plus on descendra profondément dans le code, plus on sera à même de détecter ces bugs.

Donc c'est parti!

On choisi un caractère aléatoire et on lance.

Pour cela, je me suis créé une petite fonction utilitaire utilisant la crate rand

cargo add rand

fn random_data(mut rng: &mut ThreadRng) -> usize {
    let chars = 'a'..='z';
    let data = chars
        .choose(&mut rng)
        .expect("Range is not empty")
        .to_string();

    let mut counter = 0;
    is_hello(&data, &mut counter);
    println!("{data} => {counter}");
    counter
}

En fonction des lancé de dés, vous aurez soit une erreur de panic soit un succès

#[test]
fn random() {
    let mut rng = rand::thread_rng();
    for i in 0..10 {
        random_data(&mut rng);
    }
}

Pour le rendre plus prédictible, nous allons seeder, c'est à dire rendre l'aléatoire moins aléatoire ^^

Et surtout permettre que vous ayez les mêmes exemples que moi. 😀

Installons un algo plus prédictible.

cargo add rand_chacha

fn random_data<R: RngCore>(mut rng: &mut R) -> usize {
    let chars = 'a'..='z';
    let data = chars
        .choose(&mut rng)
        .expect("Range is not empty")
        .to_string();
    println!("data : {data}");

    let mut counter = 0;
    is_hello(&data, &mut counter);
    println!("{data} => {counter}");
    counter
}

#[test]
fn random() {
    let seed = 1;
    let mut rng = ChaCha20Rng::seed_from_u64(seed);
    for i in 0..10 {
        random_data(&mut rng);
    }
}

La seed 1 donne:

data : i
i => 2
data : q
q => 2
data : q
q => 2
data : b
b => 2
data : o
o => 2
data : m
m => 2
data : l
l => 2
data : u
u => 2
data : e
e => 2
data : j
j => 2

La seed 5, une panic :

data : q
q => 2
data : h

index out of bounds: the len is 1 but the index is 1

Il est donc temps de corriger le code ^^

fn is_hello(data: &str, counter: &mut usize) -> bool {
    let data = data.as_bytes();
    *counter += 1;

    if data[0] != b'h' {
        *counter += 1;
        return false;
    }
    *counter += 1;

-    if data[1] != b'e' {
+    if data.len() < 2 || data[1] != b'e' {
        *counter += 1;
        return false;
    }
    *counter += 1;

    // snip....

    *counter += 1;
    true
}

Ainsi cette fois-ci la seed 5 ne casse plus.

data : q
q => 2
data : h
h => 3
data : v
v => 2
data : x
x => 2
data : v
v => 2
data : n
n => 2
data : t
t => 2
data : p
p => 2
data : y
y => 2
data : r
r => 2

Ce que l'on observe c'est que seul la data='h' atteint un compteur de $3$

Essayons de recasser notre code ^^


fn random_data<R: RngCore>(mut rng: &mut R) -> usize {
-    let chars = 'a'..='z';
+    let chars = ('a'..='z').collect::<Vec<char>>();


-    let data = chars
-        .choose(&mut rng)
-        .expect("Range is not empty")
-        .to_string();

// on attribues un poids de 26 à h car on veut qu'il soit plus présent que les autres lettres
+    let weights = HashMap::from([('h', 100_f64)]);

+    let data = chars
         // toutes les lettres qui ne sont pas des 'h' ont un poids de 1
+        .choose_multiple_weighted(&mut rng, 2, |x| *weights.get(x).unwrap_or(&1_f64))
+        .expect("Should get data")
+        .map(|x| x.to_string())
+        .collect::<Vec<String>>()
+        .join("");

    // snip ....
}

Finalement si on execte ce nouveau code en seed 5, on aura:

data : bh
bh => 2
data : hg
hg => 3
data : hp
hp => 3
data : hx
hx => 3
data : mh
mh => 2
data : my
my => 2
data : hx
hx => 3
data : hz
hz => 3
data : hv
hv => 3
data : bh
bh => 2

Là également on observe que seule les data qui commencent par "h" ont un compteur de 3.

Trouvons une seed qui pète

for seed in 0..100 {
    println!("seed : {seed}");
    let mut rng = ChaCha20Rng::seed_from_u64(seed);
    random_data(&mut rng);
}

Cela nous donne la "seed=49".

Si on affiche la data en question, on tombe bien sur data="he".

Corrigions le code

fn is_hello(data: &str, counter: &mut usize) -> bool {
    let data = data.as_bytes();
    *counter += 1;

    // snip ...

-    if data[2] != b'l' {
+    if data.len() < 3 || data[2] != b'l' {
        *counter += 1;
        return false;
    }
    *counter += 1;

-    if data[3] != b'l' {
+    if data.len() < 4 || data[3] != b'l' {
        *counter += 1;
        return false;
    }
    *counter += 1;

    if data[4] != b'o' {
        *counter += 1;
        return false;
    }
    *counter += 1;

    *counter += 1;
    true
}

On a donc "corrigé" code maintenant la vrai question c'est comment faire avancer notre recherche d'erreur.

Alors oui, on pourrait le faire à la main mais de un, j'ai des choses plus palpitantes à faire comme ranger mes chaussettes par exemple, et de deux, nous allons retomber dans le travers du TDD.

S'appuyer sur ce qu'on connait pour déterminer les edge-cases.

Nan, on va automatiser tout ça et laisser la froide logique des robots décider si nous sommes bons développeurs/développeuses ou non. 😄

cargo-fuzzing

Pour cela, nous allons utiliser le Fuzzing, oui c'est le titre de l'article pour les personnes qui l'auraient oublié 🤣

Installons la CLI

cargo install cargo-fuzz

Cela fourni une extension à cargo permettant de gérer toute la partie fuzzing.

Dont un initialiseur

cargo fuzz init

Ceci a pour action de créer un dossier fuzz à la racine du projet.

root/
├─ fuzz/
│  ├─ fuzz_targets/
│  │  ├─ fuzz_target_1.rs
│  ├─ Cargo.toml
├─ src/
│  ├─ lib.rs
├─ Cargo.toml

Notre projet ressemble grosso-modo à ça.

Dans le fichier root/fuzz/fuzz_targets, nous avons.

#![no_main]

use libfuzzer_sys::fuzz_target;

fuzz_target!(|data: &[u8]| {
    // fuzzed code goes here
});

Quasiment rien...

On a pas de main, ni de moyen d'exécuter quoi que ce soit.

A part par la CLI.

cargo fuzz run fuzz_target_1

Et là problème ...

error: the option `Z` is only accepted on the nightly compiler

Bon qu'à cela ne tienne

rustup default nightly

RIP .. ☠

"--target" "x86_64-pc-windows-msvc"

error: address sanitizer is not supported for this target

Bon, il n'aime pas windows.

Mais ce n'est pas un problème. On bascule en wsl ^^

Cette fois-ci ça se lance ! 😍

INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 46791055                                   
INFO: Loaded 1 modules   (1854 inline 8-bit counters): 1854 [0x55ed69e7b3a0, 0x55ed69e7bade), 
INFO: Loaded 1 PC tables (1854 PCs): 1854 [0x55ed69e7bae0,0x55ed69e82ec0),
INFO:        0 files found in /mnt/d/Lab/Programmation/lab/fuzz-lab/fuzz/corpus/fuzz_target_1
INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 4096 bytes
INFO: A corpus is not provided, starting from an empty corpus
#2      INITED cov: 14 ft: 15 corp: 1/1b exec/s: 0 rss: 40Mb
#3      NEW    cov: 14 ft: 16 corp: 2/2b lim: 4 exec/s: 0 rss: 41Mb L: 1/1 MS: 1 ChangeBit-
#4194304        pulse  cov: 14 ft: 16 corp: 2/2b lim: 4096 exec/s: 1398101 rss: 358Mb
#8388608        pulse  cov: 14 ft: 16 corp: 2/2b lim: 4096 exec/s: 1398101 rss: 621Mb
#16777216       pulse  cov: 14 ft: 16 corp: 2/2b lim: 4096 exec/s: 1290555 rss: 624Mb
#33554432       pulse  cov: 14 ft: 16 corp: 2/2b lim: 4096 exec/s: 1342177 rss: 625Mb

Et on comprend rien 🤣

Essayons de voir ce que data vaut:

fuzz_target!(|data: &[u8]| {
    println!("data : {}", String::from_utf8_lossy(data));
});

Et ça affiche:

// ...
data : 3
data : 3
data : 3
data : �3
data : D+
data : DD+
data : DD+
data : dD+
data : Dd+
data : �A
data : A�
data : Ar�
data : A�
data : A�
data : ��
data : ��
// ...

Des trucs aléatoires !

Ne pourrait-on pas mettre ça dans notre méthode is_hello et voir ce qui se passe? ^^

use fuzz_lab::is_hello;

fuzz_target!(|data: &[u8]| {
    // on converti les bytes en caractères
    let data_tested = String::from_utf8_lossy(data);
    println!("data : {}", data_tested);
    let mut counter = 0;
    is_hello(&data_tested, &mut counter);
    println!("{data_tested} => {counter}");
});

Et bien ce fut rapide !

thread '<unnamed>' panicked at /mnt/d/Lab/Programmation/lab/fuzz-lab/src/lib.rs:5:8:
index out of bounds: the len is 0 but the index is 0

Et oui, il manque un check: la chaîne vide !

Il est d'ailleurs possible de voir la données en erreur.

Lors du fuzz, un dossier a été créé

fuzz/
├─ artifacts/
│  ├─ fuzz_target_1/
│  │  ├─ crash-<HASH>
├─ fuzz_targets/
│  ├─ fuzz_target_1.rs
├─ Cargo.toml

Dedans un fichier vide crash-<HASH>, le hash peut varier.

Ceci est notre test-case en erreur.

Bien corrigeons le code de is_hello.

pub fn is_hello(data: &str, counter: &mut usize) -> bool {
    let data = data.as_bytes();
    *counter += 1;

-    if data[0] != b'h' {
+    if data.len() < 1 || data[0] != b'h' {
        *counter += 1;
        return false;
    }

    // ...
}

Et on relance !

On sent dans le mouvement qu'il est en train de converger ^^

data : hell �
hell  => 6
data : hell �
hell  => 6
data : hele �
hele  => 5
data : hel
hel => 5
data : hel
hel => 5
data : hll
hll => 3
data : hll
hll => 3

Et finalement

data : hell
thread '<unnamed>' panicked at /mnt/d/Lab/Programmation/lab/fuzz-lab/src/lib.rs:29:8:
index out of bounds: the len is 4 but the index is 4

Failing input:

        fuzz/artifacts/fuzz_target_1/crash-a5cec7af5f7aab769cf0d4aa440e01c7bfc371b2

Output of `std::fmt::Debug`:

        [104, 101, 108, 108]

Reproduce with:

        cargo fuzz run fuzz_target_1 fuzz/artifacts/fuzz_target_1/crash-a5cec7af5f7aab769cf0d4aa440e01c7bfc371b2

Minimize test case with:

        cargo fuzz tmin fuzz_target_1 fuzz/artifacts/fuzz_target_1/crash-a5cec7af5f7aab769cf0d4aa440e01c7bfc371b2

Il a trouvé !

Et mieux que ça, il a mis le test-case dans un dossier de crash.

Et son contenu est :

hell

Il nous donne une commande pour reproduire le bug:

cargo fuzz run fuzz_target_1 fuzz/artifacts/fuzz_target_1/crash-a5cec7af5f7aab769cf0d4aa440e01c7bfc371b2

Et une autre pour minimiser celui-ci.

cargo fuzz tmin fuzz_target_1 fuzz/artifacts/fuzz_target_1/crash-a5cec7af5f7aab769cf0d4aa440e01c7bfc371b2

Même si ici le code minimal est déjà celui trouvé

CRASH_MIN: failed to minimize beyond fuzz/artifacts/fuzz_target_1/crash-a5cec7af5f7aab769cf0d4aa440e01c7bfc371b2 (4 bytes), exiting

Car le seul data de 4 caractères qui peut casser le code est "hell".

Et du coup comment ça marche ?

Et bien un peu comme le système à la main, sauf, qu'au lieu de compter à la main les lignes on utilise le coverage du code qui est bien plus efficace pour déterminer les chemins du code.

Ensuite la génération des données est un poil plus maline que la mienne et surtout bien plus adaptative. 😁

Ce qui implique que l'on peut simplifier notre méthode.

pub fn is_hello(data: &str) -> bool {
    let data = data.as_bytes();

    if data.is_empty() || data[0] != b'h' {
        return false;
    }
    
    if data.len() < 2 || data[1] != b'e' {
     
        return false;
    }


    if data.len() < 3 || data[2] != b'l' {

        return false;
    }

    if data.len() < 4 || data[3] != b'l' {

        return false;
    }
    
    if data[4] != b'o' {

        return false;
    }
    
    true
}

Simplifier notre fuzzer

fuzz_target!(|data: &[u8]| {
    let data_tested = String::from_utf8_lossy(data);
    is_hello(&data_tested);
});

Donc voilà, vous savez tout du fuzzer ^^

L'idée est maintenant que dans vos CI en test de non régression, vous nourissiez vos assertions avec les edge-cases qui ont été trouvé par fuzzing.

Arbitrary

Ok, mais c'est pas un peu limité le fait que data : &[u8] ne soit que des bytes.

On s'est bien démerdé avec la chaîne de caractères, mais qu'est ce qui se passe si par exemple nos données devienne :

enum Color {
    Blue,
    Red,
    Green
}

struct Data<'a>' {
    color: Color,
    sentence: &'a str,
}

pub fn is_hello_red(data: Data) -> bool {
    if let Color::Red = data.color {
        return is_hello(data.sentence);
    }
    false
}

Pour l'occasion, nous allons nous créer une seconde target.

Dans le dossier fuzz_targets, créer un fichier fuzz_target_2.rs.

Dans le Cargo.toml, rajouter les lignes

[[bin]]
name = "fuzz_target_2"
path = "fuzz_targets/fuzz_target_2.rs"
test = false
doc = false

Dans le fuzz_target_2.rs, écrire

#![no_main]

use fuzz_lab::{is_hello_red, Color, Data};
use libfuzzer_sys::fuzz_target;

fuzz_target!(|data: &[u8]| {
    let data_tested = String::from_utf8_lossy(data);
    let data = Data {
        color: Color::Red,
        sentence: &data_tested,
    };
    is_hello_red(data);
});

On force le Color::Red, sinon ça ne crashera jamais ^^'

Il nous réaffiche "hell" comme erreur.

Mais nous on lui a demandé un Data.

Or on continue à obtenir des bytes en test case.

C'est parce qu'il nous manque une pièce de puzzle.

Il s'agit de la crate arbitrary, elle permet de génrer tout ce qu'on désire ! 😎

Pour cela on l'installe, avec ses dérivations

cargo add arbitrary -F derive

Et ensuite on décore notre code 🙂

use arbitrary::Arbitrary;

#[derive(Arbitrary, Debug)]
pub enum Color {
    Blue,
    Red,
    Green,
}

#[derive(Arbitrary, Debug)]
pub struct Data<'a> {
    pub color: Color,
    pub sentence: &'a str,
}

On modifie le fuzzer:

fuzz_target!(|data: Data| {
    is_hello_red(data);
});

Et let's go !

Failing input:

        fuzz/artifacts/fuzz_target_2/crash-5297375f02b2430ee140ee317afd53bbce8e0c64

Output of `std::fmt::Debug`:

        Data {
            color: Red,
            sentence: "hell",
        }

On a bien l'objet complet qui a foiré !

Conclusion

Le fuzzing c'est vraiment l'apprentissage de l'humilité.

Tout les codes sont buggés à moins d'avoir été suffisamment maltraités et ne pas avoir cassé.

La possibilité de pouvoir explorer toutes les possibilité de données d'un code est juste hallucinante !

Et comme on est en Rust, tout est d'une facilité et d'une commodité incroyable 🥰

Le fait de pouvoir tout rejouer est aussi épatant !

J'espère que vous avez apprécié cette petite introduction à ce concept qui m'était inconnu il n'y a pas 1 mois. ^^

Merci de votre lecture ❤️

Auteur: Akanoa

Je découvre, j'apprends, je comprends et j'explique ce que j'ai compris dans ce blog.

Ce travail est sous licence CC BY-NC-SA 4.0.