zlibの「正しいコード」に潜む誤った証明、ポインタ追跡の謎を解く
Right Code, Wrong Comment: The Pointer Chase Inside Zlib
zlibのtrees.c:945にあるAssertはリリースビルドでは無効化される。deflate.cにはこのアサーションが決して発火しないという38行の数学的証明があるが、その証明は誤りだ。平均ビット長の境界ではブロック途中の衝突を防げず、衝突は.rodataの範囲外読み取りを引き起こす。Lean 4で機械検証された安全性証明を目指す著者が、ポインタの競合を追跡し、なぜ実際のクラッシュ入力が作れないのかを解き明かす。
zlibの作者たちは、このオーバーレイに正当化が必要だと知っていたため、deflate.c:465–502に38行の数学的証明を書いた。