CirC: Compiler infrastructure for proof systems, software verification, and more
CirC: Compiler infrastructure for proof systems, software verification, and more
复制标题
DOI：
10.1109/sp46214.2022.9833782
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Alex Ozdemir;Fraser Brown;R. Wahby
中科院分区：
文献类型：
--
作者：
Alex Ozdemir;Fraser Brown;R. Wahby
密码工具，如证明系统，多方计算和全同态加密通常应用于表示为算术约束系统的计算。实际上，这意味着这些应用程序依赖于从高级编程语言（如C）到此类约束的编译器。这个编译任务很有挑战性，但并不完全是新的：软件验证社区有丰富的关于编译程序到逻辑约束（如SAT或SMT）的文献。在这项工作中，我们表明，建立共享的编译器基础设施编译约束表示是可能的，因为这些表示共享一个共同的抽象：无状态，非均匀，非确定性的计算，我们称之为存在量化电路，或EQC。此外，我们表明，这种共享的基础设施是有用的，因为它允许编译器证明系统受益于几十年的工作约束编译技术的软件验证。为了使我们的方法具体化，我们创建了CirC，一个用于构建EQC编译器的基础设施。CirC使得编译成新的EQC变得容易：我们在大约2000美元的时间内构建了对R1 CS（用于证明系统）、SMT（用于验证和bug查找）和ILP（用于优化）三种EQC的支持。扩展CirC以支持新的源语言也很容易：我们在一周内为加密语言构建了一个功能完整的编译器，大约需要$\$900 $，而同一语言的参考编译器需要数年时间编写，包括$\$24000 $，并且产生比我们的编译器性能更差的输出。最后，CirC实现了联合收割机结合多个EQC的新应用。例如，我们构建了第一个管道，它（1）自动识别程序中的错误，然后（2）自动构造错误存在的加密证明。
Cryptographic tools like proof systems, multi-party computation, and fully homomorphic encryption are usually applied to computations expressed as systems of arithmetic constraints. In practice, this means that these applications rely on compilers from high-level programming languages (like C) to such constraints. This compilation task is challenging, but not entirely new: the software verification community has a rich literature on compiling programs to logical constraints (like SAT or SMT). In this work, we show that building shared compiler infrastructure for compiling to constraint representations is possible, because these representations share a common abstraction: stateless, non-uniform, non-deterministic computations that we call existentially quantified circuits, or EQCs. Moreover, we show that this shared infrastructure is useful, because it allows compilers for proof systems to benefit from decades of work on constraint compilation techniques for software verification. To make our approach concrete we create CirC, an infrastructure for building compilers to EQCs. CirC makes it easy to compile to new EQCs: we build support for three, R1CS (used for proof systems), SMT (used for verification and bug-finding), and ILP (used for optimization), in $\approx 2000$ LOC. It’s also easy to extend CirC to support new source languages: we build a feature-complete compiler for a cryptographic language in one week and $\approx 900$ LOC, whereas the reference compiler for the same language took years to write, comprises $\approx 24000$ LOC, and produces worse-performing output than our compiler. Finally, CirC enables novel applications that combine multiple EQCs. For example, we build the first pipeline that (1) automatically identifies bugs in programs, then (2) automatically constructs cryptographic proofs of the bugs’ existence.