Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Comparative Causality: Explaining the Differences Between Executions

论文下载

Abstract

  • 程序切片找到同一程序不同执行结果的原因
  • 与Differential Slicing(S&P’11)相似

Introduction

  1. 提到Zeller的delta debugging的方法(FSE’11),使用CSM(Causal State Minimization)
  2. 本质是将以此执行的输入作为另一次执行的输入,看是否会得到相应的结果
  3. 二分搜索state,直到找到cause set最小集
  4. 不完整替换会跑飞;遗漏执行路径;效率低

Comparative Causality

  • 问题:拿一个correct和buggy的程序,给定二者在某个excecution point不同的state,找到一个造成这个不同的state set
  • 相关性:从结果逆推回原因的路径上,所有statement都不相同(PS必须的)
  • 充分性:把一段执行的数据copy给另一段,得到相应的结果

Realizing Comparative Causal Inference

  • Dual Slicing:对两段程序分别进行动态反向切片
  • 会出现冗余,无法满足充分性
  • 去除冗余的基本方法:穷举,试出满足充分性的最小集合
  • 总结了Confounding Free Execution Model
    • 非条件跳转的语句,如果不在Dual Slicing的结果里,跳过
    • 对于Dual Slicing里存在的条件跳转,正常执行
    • Dual Slicing当中的其他语句,验证他们保有的数据依赖关系与原程序的一致;不一致的认为是confounding
  • 插桩实现

Evaluation

对find, gnuplot, grep, make, tar等程序的不同版本作测试。