cgnail's weblog | A quantum of academic

Automatic error elimination by horizontal code transfer across multiple applications (2015)

| categories notes 
tags 漏洞修复  程序修改  代码变形  动态执行  污点分析  binary分析  程序分析  PLDI 

原文:Automatic error elimination by horizontal code transfer across multiple applications

为什么要做

某些错误源自开发者预测外的应用场景,但这些场景可能被别的软件开发者预测到了,因此可以把类似的代码移植过来。

做了什么

  • 前提假设:目标程序缺少donor程序的某个错误检查。
  • 目标:将错误检查移植到目标程序,不需要donor的源代码或符号信息的支持(但需要目标程序的源代码?)
  • 错误类型:越界访问,整数溢出,零除
  • 贡献:跨命名空间和数据结构的语义的移植,以及数据结构在不同应用间的翻译

怎么做到的

  1. 选择donor。以一个引发错误的输入和一个不引发错误的种子输入运行目标程序,并从donor库里找出正常接收这两个输入的程序作为donor。
  2. 查找候选检查点。以两个输入执行donor,用动态污点分析(Valgrind)找出两个输入的分叉点。理论是:两种输入在错误检查点会走不同的路径。
  3. 路径切除。以出错输入再次插装执行donor,获得以检查点的符号表达式树。表达式记录程序如何利用输入计算检查点的条件。表达式树的表示转化成与应用程序无关的形式。
  4. 插入补丁。以种子输入插装执行目标程序,以读入全部输入域的点作为候选插入点。具体先跟踪程序中所有受输入所影响的表达式,然后找出这样的函数,他们访问了由检查点中用到的输入字节计算出来的表达式。函数中的访问点就是插入点。
  5. 验证补丁。插入检查,重新编译目标程序,检查出错输入是否能被检查点正确处理。插入补丁需要将表达式树翻译成和目标程序的数据结构和命名空间相关的形式。采用debug信息获得插入点可用的变量集合,以此为根查找检查表达式用到的数据结构的域或指针等信息。翻译检查表达式时先用SMT求解是否能用简单的值来代替表达式(中的一部分),否则尝试拆解表达式逐段替换。SMT的缓存是必要的优化。
  6. 重复。如果验证失败,则尝试别的插入点、donor的检查点,以及新的donor。

效果如何

以10个程序作为donor库,检查了7个程序中的10个错误。都可以从库里生成代码移植到目标程序里。

然后呢

新挖了个坑,欢迎灌水。

If you liked this post, you can share it with your followers !