[BEE-15007] 基於屬性的測試

INFO

基於屬性的測試（Property-Based Testing）以自動生成的輸入取代手動選擇的範例，針對通用主張進行驗證——並自動找出能觸發失敗的最小輸入。

背景

範例式測試（BEE-15001 測試金字塔中的主流形式）有一個結構性弱點：你只能測試你想到要寫的情況。開發者寫下 assert sort([3,1,2]) == [1,2,3] 時，選擇了一個特定的輸入和預期輸出。若排序演算法在這個輸入上正確，但在包含重複元素的輸入、空列表或百萬個相同值的列表上失敗，測試依然通過，程式錯誤就這樣被發布出去了。

基於屬性的測試（PBT）由 Koen Claessen 和 John Hughes 以 QuickCheck 的形式發明，發表於 ICFP 2000（「QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs」，ACM SIGPLAN Notices）。該論文在 2010 年獲得 ACM SIGPLAN 最具影響力 ICFP 論文獎。不要指定範例，而要指定屬性：對所有有效輸入都必須成立的全稱量化主張。框架生成數百或數千個隨機輸入，驗證屬性是否成立，並在找到反例時，自動將其縮小至最小的失敗案例。

David MacIver（Hypothesis 的創建者，Python 領先 PBT 函式庫）記錄了 Hypothesis 找到 Argon2 實作中的緩衝區溢位（僅在雜湊長度超過 512 時觸發）、ISO 8601 日期解析中的年/月對調（僅在 0005-01-01 這樣的日期觸發）以及 npm 套件中的原型污染（Prototype Poisoning）漏洞——全部透過比實作程式碼更短的迴路（roundtrip）和不變量（invariant）屬性發現。

Dropbox 為其 Nucleus 同步引擎建立了名為 CanopyCheck 的 PBT 系統，生成三個隨機的文件系統樹，驗證其同步規劃器總能將它們收斂到一致狀態。John Hughes、Benjamin Pierce、Thomas Arts 和 Ulf Norell 使用 PBT 在 Dropbox 及競爭性同步服務中找到了令人驚訝的錯誤（IEEE ICST 2016，「Mysteries of DropBox」）。

核心概念

屬性 vs. 範例

範例測試：

assert sorted([3, 1, 2]) == [1, 2, 3]

屬性：

# 對所有列表 xs：
result = sorted(xs)
# 屬性 1：結果是有序的
assert all(result[i] <= result[i+1] for i in range(len(result)-1))
# 屬性 2：結果包含相同的元素
assert sorted(result) == result  # 冪等性
assert len(result) == len(xs)

屬性不需要知道 sorted([3,1,2]) 返回什麼——只需要任何輸出都遵守這些不變量。這是從「這個函式對這個輸入返回什麼？」到「關於任何輸出，什麼必須永遠成立？」的轉變。

生成器與策略（Strategies）

生成器（在 Hypothesis 中稱為「策略」）產生指定型別的隨機值。框架內建生成器涵蓋：

• 基本型別：整數（包括邊界值如 MIN_INT、MAX_INT、0、-1）、浮點數（包括 NaN、+Inf、-Inf）、布林值
• 文字：ASCII、Unicode（包括破壞 ASCII 假設的碼點：null bytes、RTL 標記、零寬度連接符、表情符號）
• 集合：任意元素型別和大小的列表、集合、字典、元組
• 領域：st.emails()、st.ip_addresses()、st.datetimes()、st.fractions()

策略可以組合：st.lists(st.text()) 生成字串列表；st.dictionaries(st.text(), st.integers()) 生成字串鍵的整數字典。自訂策略從基本元件建構領域物件。

縮小（Shrinking）

找到失敗僅是 PBT 價值的一半。另一半是縮小：自動找到最小的仍能觸發失敗的輸入。若無縮小，失敗的屬性可能回報一個 500 元素、任意值的列表作為反例——幾乎無法除錯。縮小後，它回報 [0, -1]——暴露錯誤的最小列表。

QuickCheck 風格（型別類別）縮小：每個型別定義其自身的縮小策略。Int 向 0 縮小；列表透過移除元素和縮小個別元素來縮小。這很快，但可能違反生成器的不變量：生成只含偶數的生成器可能將失敗的偶數縮小為奇數，導致無關的失敗。

Hypothesis 整合縮小：Hypothesis 縮小所有策略讀取的底層位元組串流，而非直接縮小生成的值。由於相同的策略程式碼在縮小後的串流上重新執行，所有生成器的不變量都能自動保留。

有狀態（模型式）測試

有狀態的 PBT 測試透過操作演進的系統，而非純函式。框架定義：

• 模型：預期狀態的簡化、明顯正確的表示（例如，用 dict 表示快取）
• 規則：允許的操作（put、get、delete）
• 後置條件：每次操作後，真實系統的結果與模型的預測相符的斷言
• 不變量：無論觸發哪個規則，每次操作後都必須成立的屬性

框架生成隨機規則序列，同時對模型和真實系統執行，並將任何失敗序列縮小至導致差異的最小操作序列。

屬性模式

John Hughes 的「How to Specify It!」（2019/2020）識別出寫屬性的五種方法，按找錯效果由低到高排列：

1. 迴路（Roundtrip / There-and-Back）parse(serialize(x)) == x 或 decode(encode(x)) == x

對序列化、壓縮、加密和編解碼程式碼最有效的單一模式。能發現：靜默資料損壞、邊界條件截斷、編碼假設不匹配。

2. 不變量（Invariants / Some Things Never Change） 轉換保留資料的結構屬性：

• sorted(xs) 是升序的
• len(map(f, xs)) == len(xs)
• deduplicate(xs) 不含重複元素

3. 代數屬性（Algebraic Properties） 函式必須遵守的數學定律：

• 冪等性：sort(sort(xs)) == sort(xs)；deduplicate(deduplicate(xs)) == deduplicate(xs)
• 交換律：add(x, y) == add(y, x)
• 結合律：add(add(x, y), z) == add(x, add(y, z))

4. 神諭（Oracle / Reference Model） 比較快速但複雜的實作與緩慢但明顯正確的參考：

# 對所有 xs：
assert optimized_sort(xs) == naive_bubble_sort(xs)

在優化或重構過程中非常有效。

5. 模型式 / 有狀態（Model-Based / Stateful） 任意有效操作序列後，真實系統與模型一致。在 Hughes 的實驗研究中，找錯率最高——對植入錯誤的檢測率達 100%，而更簡單的後置條件測試僅達 57%。

最佳實踐

SHOULD（應該）將 PBT 與範例式測試一起使用，而非取而代之。 屬性最擅長找出輸入域的邊緣案例；範例最擅長記錄特定場景的預期行為。兩者互補。

MUST（必須）對任何序列化、編碼或解析程式碼從迴路屬性開始。 parse(serialize(x)) == x 幾乎不需要領域知識，且找錯率極高。它能發現靜默截斷、編碼假設違反和邊界處理錯誤，而這些正是手動測試案例系統性地錯過的。

SHOULD（應該）在開發時使用預設執行次數（大多數框架為 100 個範例），在 CI 每日執行時使用更高次數。 PBT 測試比範例測試更昂貴。取捨：快速路徑中 100 個隨機範例能發現大多數回退；每日執行中 10,000 個範例能找到更罕見的邊緣案例。

MUST（必須）配置種子（seed）以確保可重現性。 大多數框架支援固定種子用於除錯。在 CI 中，記錄任何失敗執行所使用的種子，以便在本地重現：

# Hypothesis：使用 @settings(derandomize=True) 固定種子
@settings(derandomize=True)
@given(st.lists(st.integers()))
def test_sort_idempotent(xs):
    assert sorted(sorted(xs)) == sorted(xs)

SHOULD（應該）為領域物件編寫自訂策略，而非生成違反業務規則的無約束隨機基本型別。生成有效 Order 物件的策略比生成任意字串作為訂單 ID 的策略產生更相關的失敗。

SHOULD（應該）對任何維護非平凡內部狀態的元件使用有狀態測試：快取、佇列、限速器、連線池、狀態機。模型不需要複雜——對大多數快取和佇列實作，一個簡單的 dict 或 list 就足夠作為神諭。

MUST NOT（不得）將「不拋出例外」視為有意義的屬性。 冒煙屬性（任意輸入不崩潰）信號量低。應與結構不變量結合：不拋出例外 AND 輸出已正確排序 AND 輸出長度與輸入長度相符。

各語言實作

Python — Hypothesis

from hypothesis import given, settings, strategies as st
from hypothesis.stateful import RuleBasedStateMachine, rule, invariant

# 基本屬性：迴路測試
@given(st.text())
def test_json_roundtrip(s):
    import json
    assert json.loads(json.dumps({"key": s}))["key"] == s

# 有狀態測試：快取模型
class CacheTest(RuleBasedStateMachine):
    def __init__(self):
        super().__init__()
        self.cache = MyLRUCache(capacity=3)
        self.model = {}

    @rule(key=st.text(), value=st.integers())
    def put(self, key, value):
        self.cache.put(key, value)
        self.model[key] = value          # 更新模型

    @rule(key=st.text())
    def get(self, key):
        cached = self.cache.get(key)
        # 後置條件：結果與模型一致（忽略驅逐）
        if key in self.model and cached is not None:
            assert cached == self.model[key]

    @invariant()
    def size_within_capacity(self):
        assert self.cache.size() <= 3

TestCache = CacheTest.TestCase

Hypothesis 在 .hypothesis/ 資料庫中維護之前失敗輸入的記錄，並在每次執行時優先重播它們——即使隨機種子不同，CI 也始終能發現之前發現的回退。

Java — jqwik

import net.jqwik.api.*;

class SortingProperties {
    @Property
    boolean sortedIsIdempotent(@ForAll List<Integer> xs) {
        List<Integer> once = sorted(xs);
        List<Integer> twice = sorted(once);
        return once.equals(twice);
    }

    @Property
    boolean sortedContainsSameElements(@ForAll List<Integer> xs) {
        List<Integer> result = sorted(xs);
        return new HashSet<>(result).equals(new HashSet<>(xs))
               && result.size() == xs.size();
    }
}

JavaScript/TypeScript — fast-check

import fc from "fast-check";

// 自訂序列化器的迴路屬性
fc.assert(
  fc.property(fc.string(), (s) => {
    expect(deserialize(serialize(s))).toEqual(s);
  })
);

// 合併的交換律
fc.assert(
  fc.property(
    fc.object(), fc.object(),
    (a, b) => deepEqual(merge(a, b), merge(b, a))
  )
);

fast-check 透過失敗訊息中印出的種子確定性地重播失敗。從失敗輸出中傳入 {seed, path} 以重現：

fc.assert(fc.property(fc.integer(), ...), { seed: 1234, path: "0:0" });

常見錯誤

編寫什麼都測不到的平凡屬性。 對所有 xs：sort(xs) != nil 對任何返回空列表的損壞排序都會通過。屬性必須對輸入和輸出之間的關係做出結構性主張。

對有約束的領域生成無約束的輸入。 若函式需要有效的電子郵件地址，生成任意 st.text() 會產生大多數無效電子郵件，測試會在輸入驗證上失敗而非在被測邏輯上。建立生成有效電子郵件的自訂策略。

用 PBT 取代契約測試或黃金路徑範例。 PBT 找未知情況；範例測試記錄已知行為。迴路屬性不能取代測試 serialize(Order(id=1, amount=9.99)) 產生確切預期 JSON 的測試。兩者都需要。

忽略縮小後的反例。 當 PBT 回報失敗時，縮小後的輸入是最小的失敗案例。除錯原始的大型隨機輸入而非縮小後的輸入是浪費時間。始終從縮小後的案例開始工作。

讓有狀態測試過於複雜。 有 15 條規則的有狀態測試與它所測試的系統一樣難以推理。從 3–4 個操作開始，驗證模型對這些操作是正確的，然後再擴展。錯誤的模型產生假陽性——即使程式碼正確，測試也會失敗。

相關 BEE

• BEE-15001 -- 測試金字塔：PBT 的適用位置——它補充基礎的單元測試；不能取代整合或契約測試
• BEE-15002 -- 後端服務整合測試：PBT 可透過生成真實的請求序列來驅動有狀態 API 的整合測試
• BEE-15003 -- 契約測試：PBT 和契約測試都驗證介面不變量；契約測試固定架構，PBT 在其中生成輸入
• BEE-15005 -- 測試替身：Mocks、Stubs、Fakes：在有狀態 PBT 中，模型扮演真實系統的記憶體 fake

參考資料

• Koen Claessen, John Hughes. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs — ACM SIGPLAN ICFP 2000
• John Hughes. How to Specify It! A Guide to Writing Properties of Pure Functions — Springer, 2020
• David R. MacIver. In Praise of Property-Based Testing — Increment Issue 10, August 2019
• David R. MacIver. What is Property Based Testing? — hypothesis.works
• David R. MacIver, Zac Hatfield-Dodds et al. Hypothesis: A new approach to property-based testing — Journal of Open Source Software, 2019
• David R. MacIver. Integrated vs Type Based Shrinking — hypothesis.works
• John Hughes, Benjamin Pierce et al. Mysteries of DropBox: Property-Based Testing of a Distributed Synchronization Service — IEEE ICST 2016
• Isaac Goldberg. Testing Sync at Dropbox — Dropbox Tech Blog, April 2020
• Scott Wlaschin. Choosing Properties for Property-Based Testing — F# for Fun and Profit, December 2014
• fast-check — Nicolas Dubien
• jqwik — Johannes Link