一句话：通过类型推断区分安全/不安全指针，减少符号执行 IR 解释中的冗余边界检查，从而加速 KLEE。
符号执行广泛用于程序分析与软件测试，但 KLEE、Angr 等引擎在执行中解释中间表示（IR）时开销较大。现有加速研究较少优化内部解释操作。本文提出 FastKLEE，通过减少类型安全指针的冗余边界检查来加速 IR 代码解释。它先用类型推断系统将最常解释的读写指令涉及的指针分为安全与不安全两类，再定制内存操作，仅对不安全指针执行边界检查，省略安全指针的冗余检查。作者在 KLEE 上结合 CCured 实现 FastKLEE。评估表明，在探索相同 10k 条执行路径时，其耗时相较 KLEE 最多减少 9.1%，平均减少 5.6%。
Symbolic execution (SE) has been widely adopted for automatic program analysis and software testing. Many SE engines (e.g., KLEE or Angr) need to interpret certain Intermediate Representations (IR) of code during execution, which may be slow and costly. Although a plurality of studies proposed to accelerate SE, few of them consider optimizing the internal interpretation operations. In this paper, we propose FastKLEE, a faster SE engine that aims to speed up execution via reducing redundant bound checking of type-safe pointers during IR code interpretation. Specifically, in FastKLEE, a type inference system is first leveraged to classify pointer types (i.e., safe or unsafe) for the most frequently interpreted read/write instructions. Then, a customized memory operation is designed to perform bound checking for only the unsafe pointers and omit redundant checking on safe pointers. We implement FastKLEE on top of the well-known SE engine KLEE and combined it with the notable type inference system CCured. Evaluation results demonstrate that FastKLEE is able to reduce by up to 9.1% (5.6% on average) as the state-of-the-art approach KLEE in terms of the time to explore the same number (i.e., 10k) of execution paths. FastKLEE is opensourced at https://github.com/haoxintu/FastKLEE. A video demo of FastKLEE is available at https://youtu.be/fjV_a3kt-mo.
@inproceedings{paperbot7028,
title = {FastKLEE: faster symbolic execution via reducing redundant bound checking of type-safe pointers},
author = {Haoxin Tu and Lingxiao Jiang and Xuhua Ding and He Jiang},
booktitle = {FSE},
year = {2022},
doi = {10.1145/3540250.3558919}
}