Unit test memverifikasi input tertentu menghasilkan output tertentu, tetapi tidak menjawab pertanyaan: “apakah algoritma benar untuk semua input?”. Property-based testing menjawabnya dengan menguji invarian — sifat yang harus selalu benar — pada ribuan input acak. Konsep ini diperkenalkan oleh QuickCheck (Haskell, 1999) dan sekarang tersedia di hampir semua bahasa. Pada Chapter ini kita akan menulis generator acak sederhana, mendefinisikan beberapa property kanonik untuk sorting dan string reversal, lalu menjalankan ribuan trial otomatis. Tujuan akhirnya: bug tersembunyi yang tidak terjangkau unit test akan muncul secara probabilistik.

Aturan: Definisikan Invarian, Bukan Expected Value #

Dalam unit test, kita tulis ASSERT_EQ(f(input), expected). Dalam property-based test, kita tulis property:

  • ∀ input: P(f, input) holds

Contoh property:

AlgoritmaProperty
sort(a)Output non-decreasing dan mempertahankan multiset elemen input
reverse(s)reverse(reverse(s)) == s (involution)
max(a)Sama dengan elemen terakhir sort(a) bila tidak kosong
hash(x)hash(x) == hash(x) untuk input yang sama (deterministic)
intersection(a, b)Setiap elemen hasil ada di kedua a dan b

Mekanisme: Generator Acak + Oracle #

Tiga komponen inti property-based test:

  1. Generator: menghasilkan input acak dengan distribusi terkontrol. Penting: gunakan std::mt19937 dengan seed tetap agar test reproducible. Bila bug ditemukan, input yang sama dapat diulang.
  2. Oracle: implementasi referensi yang dipercaya benar (biasanya brute force atau library bawaan). Output algoritma dibandingkan dengan output oracle.
  3. Shrinking: bila input besar memicu bug, framework mencoba mengecilkan input (menghapus elemen, mengganti dengan nilai ekstrem) untuk menemukan counter-example minimal. Shrinking otomatis di QuickCheck, manual di C++.

Kode: Property-Based Test untuk Sorting dan Reverse #

cpp 
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <string>

// ---------- Algoritma yang diuji ----------
std::vector<int> insertion_sort(std::vector<int> a) {
    for (size_t i = 1; i < a.size(); ++i) {
        int key = a[i];
        int j = (int)i - 1;
        while (j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            --j;
        }
        a[j+1] = key;
    }
    return a;
}

std::string reverse_str(std::string s) {
    std::reverse(s.begin(), s.end());
    return s;
}

// ---------- Random generator ----------
std::mt19937 rng(12345);  // seed tetap untuk reproducibility

std::vector<int> random_int_array(int n, int lo, int hi) {
    std::uniform_int_distribution<int> dist(lo, hi);
    std::vector<int> a(n);
    for (int& x : a) x = dist(rng);
    return a;
}

std::string random_string(int n) {
    std::uniform_int_distribution<int> dist('a', 'z');
    std::string s;
    s.reserve(n);
    for (int i = 0; i < n; ++i) s.push_back((char)dist(rng));
    return s;
}

// ---------- Property checkers ----------
bool is_non_decreasing(const std::vector<int>& a) {
    for (size_t i = 1; i < a.size(); ++i)
        if (a[i-1] > a[i]) return false;
    return true;
}

bool same_multiset(const std::vector<int>& a, const std::vector<int>& b) {
    if (a.size() != b.size()) return false;
    std::vector<int> ca = a, cb = b;
    std::sort(ca.begin(), ca.end());
    std::sort(cb.begin(), cb.end());
    return ca == cb;
}

struct PropertyResult {
    std::string name;
    int trials;
    int passed;
    std::string last_fail_input;
};

int main() {
    std::vector<PropertyResult> results;

    // Property 1: insertion_sort menghasilkan array non-decreasing dan
    // mempertahankan multiset elemen.
    {
        int trials = 1000, passed = 0;
        std::string last_fail;
        for (int t = 0; t < trials; ++t) {
            int n = std::uniform_int_distribution<int>(0, 50)(rng);
            auto a = random_int_array(n, -100, 100);
            auto sorted = insertion_sort(a);
            if (is_non_decreasing(sorted) && same_multiset(a, sorted)) {
                passed++;
            } else {
                last_fail = "size=" + std::to_string(n);
            }
        }
        results.push_back({"insertion_sort_is_sorted_and_same_multiset", trials, passed, last_fail});
    }

    // Property 2: reverse dua kali = input asli (involution).
    {
        int trials = 1000, passed = 0;
        std::string last_fail;
        for (int t = 0; t < trials; ++t) {
            int n = std::uniform_int_distribution<int>(0, 100)(rng);
            std::string s = random_string(n);
            std::string twice = reverse_str(reverse_str(s));
            if (twice == s) passed++;
            else last_fail = "size=" + std::to_string(n) + " s=" + s;
        }
        results.push_back({"reverse_is_involution", trials, passed, last_fail});
    }

    // Property 3: max(a) == sort(a).back() bila a tidak kosong.
    {
        int trials = 500, passed = 0;
        std::string last_fail;
        for (int t = 0; t < trials; ++t) {
            auto a = random_int_array(20, -50, 50);
            auto sorted = insertion_sort(a);
            int orig_max = *std::max_element(a.begin(), a.end());
            int sorted_max = sorted.back();
            if (!a.empty() && orig_max == sorted_max) passed++;
            else last_fail = "size mismatch";
        }
        results.push_back({"sort_preserves_max", trials, passed, last_fail});
    }

    // Property 4: integer addition komutatif (sanity check generator).
    {
        int trials = 1000, passed = 0;
        std::string last_fail;
        std::uniform_int_distribution<int> dist(-1000000, 1000000);
        for (int t = 0; t < trials; ++t) {
            long long a = dist(rng), b = dist(rng);
            // Menggunakan long long untuk menghindari signed overflow UB.
            if ((a + b) == (b + a)) passed++;
            else last_fail = "a=" + std::to_string(a) + " b=" + std::to_string(b);
        }
        results.push_back({"integer_addition_commutative", trials, passed, last_fail});
    }

    std::cout << "Property-Based Testing Results\n";
    std::cout << "==============================\n";
    for (const auto& r : results) {
        std::cout << (r.passed == r.trials ? "[OK]   " : "[FAIL] ")
                  << r.name << "  " << r.passed << "/" << r.trials << " passed";
        if (r.passed != r.trials)
            std::cout << "  -- last fail: " << r.last_fail_input;
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
Property-Based Testing Results
==============================
[OK]   insertion_sort_is_sorted_and_same_multiset  1000/1000 passed
[OK]   reverse_is_involution  1000/1000 passed
[OK]   sort_preserves_max  500/500 passed
[OK]   integer_addition_commutative  1000/1000 passed

Bedah Kode Baris-per-Baris #

  1. std::mt19937 rng(12345);: Mersenne Twister dengan seed tetap 12345. Setiap run program menghasilkan urutan acak yang sama, sehingga bug yang ditemukan dapat direproduksi.
  2. std::uniform_int_distribution<int> dist(lo, hi);: generator angka uniform dalam rentang [lo, hi] inklusif. Untuk setiap n acak, kita bangun array berisi n angka acak pada rentang tertentu.
  3. is_non_decreasing(sorted): property pertama dari sort — output harus non-decreasing. Iterasi pasangan (a[i-1], a[i]); bila ada yang menurun, return false.
  4. same_multiset(a, sorted): property kedua dari sort — sort tidak boleh menambah atau menghapus elemen. Cara verifikasi termudah: sort keduanya dengan std::sort (yang dipercaya benar) lalu bandingkan.
  5. reverse_str(reverse_str(s)) == s: involution — memanggil reverse dua kali harus mengembalikan input asli. Property ini sangat kuat karena tidak bergantung pada implementasi reverse.
  6. if (a + b) == (b + a): property komutatif penjumlahan. Kita pakai long long untuk menghindari signed overflow yang merupakan UB. Ini juga sanity check bahwa generator kita benar-benar acak.

Strategi Pemilihan Property #

Tabel berikut memandu pemilihan property untuk kategori algoritma umum:

Kategori AlgoritmaProperty Contoh
SortingNon-decreasing output, multiset preserved, stable (opsional)
Searchingbinary_search(sorted, x) == linear_search(sorted, x)
Hashinghash(x) == hash(x) deterministic, distribution uniform
Set operationintersection(a, b) == intersection(b, a) (komutatif)
Tree rotationIn-order traversal sebelum == in-order traversal setelah
DP optimizationdp(x) == brute_force(x) untuk input kecil (differential testing)

Kapan Property-Based Test Lebih Efektif #

Property-based test lebih efektif bila:

  • Ruang input besar dan tidak mungkin dienumerasi (sorting dengan n = 10).
  • Implementasi memiliki banyak cabang (DP dengan state kompleks).
  • Invarian kuat tersedia (multiset preservation, involution, idempotent).

Sebaliknya, bila output sangat spesifik dan tidak ada invarian yang jelas (misalnya “berapa minimum cost untuk problem X”), unit test dengan expected value eksplisit seringkali lebih tepat.

Ringkasan #

  • Property-based testing menguji invarian (∀ input: P(f, input) holds) pada ribuan input acak.
  • Tiga komponen: generator acak, oracle (implementasi referensi), dan shrinking (mengecilkan counter-example).
  • Selalu pakai seed tetap (std::mt19937 rng(12345)) untuk reproducibility.
  • Property kanonik untuk sort: non-decreasing output + multiset preserved.
  • Property kanonik untuk reverse: involution reverse(reverse(s)) == s.
  • Property-based paling efektif bila ruang input besar dan invarian kuat tersedia.