Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

ORBS: Language-Independent Program Slicing

论文下载

FSE’14

  • 问题: 有许多工程混杂了各种语言的代码甚至脚本。。怎么做切片
  • idea: 删除一些语句,观察程序(行为),判断该语句是否相关,并不断重复该过程。

SLICING DEFINITIONS

  • traditional Slicing:
    • 静态:在任意输入条件下,切出来的代码中指定变量的在特定位置的行为与源程序一致,值一致
    • 动态:只保证代码在给定的输入下与源程序行为一致
    • Critical Slicing:1996年,尝试删除程序中每一条语句,判定是否与目标有关,最后生成不含这些语句的源代码。。

ORBS

  • 首先,给定输入,并在代码中增加一些语句,让他在程序的特定位置输出目标变量的值
  • ORBS不断尝试删除整个工程中的一些连续的行(window),并尝试编译,成功的话,运行,比对输出的结果,如果与原始程序一致,就保留。。
  • 这个过程是尝试从代码末端向前尝试删除的,因为。。。从前删很容易删掉变量定义,导致编译失败。。
  • 其他的一些方法。。
    • F-ORBS:从前找一段一段的删。。
    • DD-ORBS:分成小chunk,然后删掉一个chunk; 完成之后减小chunk的size再重复
    • MDW-DD-ORBS:DD-ORBS结束之后,再用一个逐渐减小的移动窗口去删。。
  • 试验结果:ORBS一般能删掉最多的代码

实验

RQ1: ORBS和其他类似的切分方法比较 RQ2: 能不能切大程序 RQ3: 能不能并行化 RQ4: 讨论外因的影响

与其他方法的比较

Fig

ORBS最好,MDW-DD-ORBS可以进一步讨论

大程序切分

  • 目标:bash
  • 切分bash中的2~4个文件,用时6小时左右。。

Fig

PARALLEL ORBS

  • 不同大小的window的检测同时进行
  • 4个并行,消耗时间下降70%~82%

Fig

EXTERNAL FACTORS

  • 文件顺序,影响结果
  • 编译环境影响结果(c的未定义行为)
  • 源代码布局影响结果(多条语句并入一行,大括号的位置。。)