Accelerating all-path reachability proofs with one-path reachability proofs
@Stevengre がすでに取り組んでいます。
2026年6月18日 から。
評価
この issue はまだ評価されていません。
説明
All-path reachability proofs (APRProof) are slow: at every step the symbolic engine must search for applicable rules and branch over them through the SMT solver.
This proposal splits the work into two independently useful pieces:
- Proof Checker — a trusted component that, given an
APRProof, force-applies the rule on each edge (no search, no branching) and checks coverage.
It needs no exploration and already accelerates re-validating an existing proof (e.g. a cached proof after a semantics change). - Concolic Explorer — a new component that builds such proofs: run a concrete seed on the LLVM backend, take its rule trace as a one-path certificate, and let the Checker validate it while computing remainders; each remainder yields a new seed down a different path, until none is left.
Concrete execution is an untrusted, pluggable oracle that only decides which rule to apply; all soundness lives in the Checker.
- 主要言語
- Python
- スター
- 591
- フォーク
- 163
- PR マージ指標
- 30日以内にマージされた PR はありません
環境構築
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
runtimeverification/k のほかの issue
-
Introduce composable symbolic execution interface in pyx再び着手できるかも @Stevengre が 98 日前に担当しましたが、オープン中のプルリクエストはありません。 オープン
runtimeverification/k#4939 · 担当者 1 名 ·
-
Concolic Explorerオープン
難易度 5/5 1週間以上 初心者へのやさしさ 32/100
runtimeverification/k#4937 ·
-
難易度 5/5 1週間以上 初心者へのやさしさ 30/100
runtimeverification/k#4936 ·
-
Support progressive depth halving as a generic policy in `Prover.advance_proof`再び着手できるかも @Stevengre が 123 日前に担当しましたが、オープン中のプルリクエストはありません。 オープン
runtimeverification/k#4924 · 担当者 1 名 ·
-
area:haskell-backend area:llvm-backend priority:p2 status:icebox type:feature
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
runtimeverification/k#4904 ·
runtimeverification/k の issue をすべて見る
似ている issue
-
customer-reported
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
Azure/azure-cli#34150 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
community-request
難易度 1/5 1時間未満 初心者へのやさしさ 95/100
NVIDIA-NeMo/Curator#2464 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 88/100
WeblateOrg/translation-finder#1099 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
trezor/trezor-firmware#7997 ·
メンテナーはふだん 2 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 88/100
メンテナーはふだん 1 日以内に返信