Essential tasks for the verification of probabilistic programs include bounding expected outcomes and proving termination in finite expected runtime. We contribute a simple yet effective inductive synthesis approach for proving such quantitative reachability properties by generating inductive invariants on source-code level. Our implementation shows promise: It finds invariants for (in)finite-state programs, can beat state-of-the-art probabilistic model checkers, and is competitive with modern tools dedicated to invariant synthesis and expected runtime reasoning.
翻译:核查概率方案的基本任务包括限制预期结果和在有限预期运行时间内证明终止。 我们通过在源代码一级产生诱导性变异性,为证明这种量化可达性贡献了简单而有效的感知性综合方法。 我们的实施显示了希望:它发现(在)无限状态方案中的变异性,能够击败最先进的概率模型检查器,并且与专门致力于无差异合成和预期运行时间推理的现代工具具有竞争力。