Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Automatic Mining of Functionally Equivalent Code Fragments via Random Testing

论文下载

Abstract & Introduction

  • 提出一种可扩展的方式,通过关注代码的Input和Output的行为,来检测代码片段的语义功能等价性。
  • 与先前工作的不同:
    1. 只考察不同代码段最后输出的等价性,而不关注中间状态;
    2. 采用随机测试的方式来考察代码的I/O行为;
    3. 启发自Schwartz的随机PIT(polynomial identity testing),并给出如下引理:对于两段代码段,若给予一定量的随机输入,总是产生相同的输出,我们就有很大的可能性可以确定他们是功能等价的;即使存在少量的差异,例如error-handing和边界问题,他们仍然可以被认为是功能相似的。

Algorithm Description

Overview

Fig

Equivalence Definition

对于两段代码段C1和C2,如果对于输入I的两种不同排列p1(I)和P2(I),两段代码段的输出数据的集合C1(p1(I))和C2(p2(I))相同,即C1(p1(I))=C2(p2(I)),可以认定两段代码段功能等价

  • 考虑到输入数据顺序带来的影响以及输出数据顺序带来的影响

Code Chopping

考虑不同大小的代码段作为功能等价的基本比对单元,而不是以一整个程序或一整个函数作为基本比对单元

  • 通过预先建立的函数的语法树(编译时的语法分析),保证抽取的代码段的语法正确性
  • 设立minStmtNum每段代码段中最少的语句数目,来控制抽取的代码段的数量

Code Transformation

确认抽取的每个代码段的输入和输出变量,保证每个代码段是可编译和可执行的

  • 输入变量的判定:对于变量v,若使用前并没有被定义,则认为是这段代码段的输入变量(可以理解为第一次以右值的形式出现)
  • 输出变量的判定:作为return的返回值的变量,或者在某些控制流路径中在一次定义后不再被使用的变量v,被认为是输出变量(可加强为在所有控制流路径中,两种定义对实验准确性兼有影响)
  • 变量类型的定义:从GCC的预处理中获得所有的类型定义
  • 函数调用:在本作中将每次函数调用当作一个随机值产生器,并忽视其存在的副作用。

Input Generation

包括两类变量的生成(指针变量和非指针变量)

Code Execution & Clusering

在同一组相同的随机输入,对于同一个集合中的代码段,若存在不同的输出结果,则将集合分为两个不同的集

Empirical Evaluation

Sorting Benchmark

对冒泡排序,选择排序,递归以及非递归的快速排序,递归以及非递归的归并排序,堆排序的实现进行测试

  • 从whole-function的角度看,EQMINER成功将冒泡,选择,非递归的归并排序,非递归的快排被归并为一类,而由于本作中对函数调用的设定,使用递归的排序算法没有被归并到同一类;
  • 对于堆排序,存在着Code Transformation中输出变量的定义所带来的影响

Linux Kernel

  • (1) evaluate the existence of functionally equivalent code in a popular software and (2) test the scalability of our approach
  • 与语法相似性测试方法——DECKARD进行比对,说明语法相似不一定语义相似,语义相似不一定语法相似
  • 随机测试的缺陷所导致的一些准确性上的问题