首页    期刊浏览 2024年11月26日 星期二
登录注册

文章基本信息

  • 标题:Automated Verification of Practical Garbage Collectors
  • 本地全文:下载
  • 作者:Chris Hawblitzel ; Erez Petrank
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2010
  • 卷号:6
  • 期号:03
  • 出版社:Technical University of Braunschweig
  • 摘要:

    Garbage collectors are notoriously hard to verify, due to their low-level interaction with the underlying system and the general difficulty in reasoning about reachability in graphs. Several papers have presented verified collectors, but either the proofs were hand-written or the collectors were too simplistic to use on practical applications. In this work, we present two mechanically verified garbage collectors, both practical enough to use for real-world C# benchmarks. The collectors and their associated allocators consist of x86 assembly language instructions and macro instructions, annotated with preconditions, postconditions, invariants, and assertions. We used the Boogie verification generator and the Z3 automated theorem prover to verify this assembly language code mechanically. We provide measurements comparing the performance of the verified collector with that of the standard Bartok collectors on off-the-shelf C# benchmarks, demonstrating their competitiveness.

  • 关键词:Garbage Collectors;Assembly Languages;Theorem Prover
国家哲学社会科学文献中心版权所有