cv usk(@cv_usk):Cのモデル検査が「ループ展開で爆発」する問題、関数契約でどう解決するのでしょうか？タイトル: Function Contracts for Bounded Model Checking of C Programs URL: https://t.co/mBoVAjvygx ❓ なぜBMCは重くなるの？ループをN回展開し、関数呼び出しも全部インライン化するためです。N回ループする関数をK箇所で呼ぶと、コストはおよそN×Kに膨らみます。 💡 契約を使うとどう変わる？関数本体は契約に対して1回だけ検証し、各呼び出しは契約から作ったスタブに置き換えます。展開が不要になるので、呼び出し回数に引きずられません。 ❓ 何が新しいの？ ESBMCに契約機能を実装しました。assigns句は「書いてはいけない場所の入口時の値を保存し、終了時に比較する」観測的方式で検査します。書き込み回数でなくグローバル変数の数で式の大きさが決まる点がCBMCとの違いです。代数の骨格はLean 4で機械検証されています。 ❓ 効果は？・N=20,K=10で、直接検証は120秒超のタイムアウト、モジュラーは12.5秒・N=10,K=10で42.0秒から1.8秒（23.3倍）・W=500の書き込みでVCC数はESBMC 5に対しCBMC 521 ・ML-KEMのFIPS-203サイズでは、モノリシックは両ツールとも10分で終わらず、モジュラーなら完了ただしK=1では逆に遅くなります。 #形式検証 #モデル検査

2026.10.25 11:38

Cのモデル検査が「ループ展開で爆発」する問題、関数契約でどう解決するのでしょうか？タイトル: Function Contracts for Bounded Model Checking of C Programs URL: ❓ なぜBMCは重くなるの？ループをN回展開し、関数呼び出しも全部インライン化するためです。N回ループする関数をK箇所で呼ぶと、コストはおよそN×Kに膨らみます。 💡 契約を使うとどう変わる？関数本体は契約に対して1回だけ検証し、各呼び出しは契約から作ったスタブに置き換えます。展開が不要になるので、呼び出し回数に引きずられません。 ❓ 何が新しいの？ ESBMCに契約機能を実装しました。assigns句は「書いてはいけない場所の入口時の値を保存し、終了時に比較する」観測的方式で検査します。書き込み回数でなくグローバル変数の数で式の大きさが決まる点がCBMCとの違いです。代数の骨格はLean 4で機械検証されています。 ❓ 効果は？・N=20,K=10で、直接検証は120秒超のタイムアウト、モジュラーは12.5秒・N=10,K=10で42.0秒から1.8秒（23.3倍）・W=500の書き込みでVCC数はESBMC 5に対しCBMC 521 ・ML-KEMのFIPS-203サイズでは、モノリシックは両ツールとも10分で終わらず、モジュラーなら完了ただしK=1では逆に遅くなります。 #形式検証# #モデル検査#

显示更多