Accelerating all-path reachability proofs with one-path reachability proofs
@Stevengre ya está trabajando en esto.
Desde el 18/6/2026.
Evaluación
Este issue todavía no se ha evaluado.
Descripción
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.
- Lenguaje dominante
- Python
- Estrellas
- 598
- Forks
- 164
- Métricas de merge de PR
- Sin PR fusionados en 30 d
Preparar el entorno
- Sin Dockerfile ni archivo de Docker Compose
- Sin plantilla de pull request
- Leer la guía de contribución
Primeros pasos
- Lee el issue completo y luego la guía de contribución del proyecto.
- Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
- Haz un fork del repositorio y trabaja en una rama.
- Abre un pull request que haga referencia al número del issue.
Más de runtimeverification/k
-
Dificultad 4/5 3-5 días Aptitud para principiantes 43/100
runtimeverification/k#4942 ·
-
bug
Dificultad 3/5 Medio día Aptitud para principiantes 75/100
runtimeverification/k#4941 ·
-
Introduce composable symbolic execution interface in pyxQuizá libre de nuevo @Stevengre la tomó hace 123 días y no hay ningún pull request abierto. Abierto
runtimeverification/k#4939 · 1 asignado ·
-
Concolic ExplorerAbierto
Dificultad 5/5 Más de una semana Aptitud para principiantes 32/100
runtimeverification/k#4937 ·
-
Dificultad 5/5 Más de una semana Aptitud para principiantes 30/100
runtimeverification/k#4936 ·
Todos los issues de runtimeverification/k
Issues similares
-
bug
Dificultad 2/5 1-3 horas Aptitud para principiantes 84/100
GoogleCloudPlatform/gce-rescue#195 ·
Los mantenedores suelen responder en 2 días
-
Dificultad 2/5 1-3 horas Aptitud para principiantes 83/100
Los mantenedores suelen responder en 1 día
-
intake mcp-intake needs-ac needs-human-review priority:medium
Dificultad 2/5 1-3 horas Aptitud para principiantes 67/100
Ikalus1988/MisakaNet#3848 · 2 comentarios ·
Los mantenedores suelen responder en 1 día
-
Dificultad 1/5 Menos de una hora Aptitud para principiantes 75/100
521xueweihan/HelloGitHub#4105 ·
-
bug size:XS
Dificultad 2/5 1-3 horas Aptitud para principiantes 83/100
Los mantenedores suelen responder en 1 día