泛路径敏感的程序遍历方法


泛路径敏感的程序遍历方法 腾讯科技玄武实验室 忽朝俭 • 泛路径(或称为准路径) • 程序的过程间控制流图上,由一组简单基本块(结点)组成 的序列,而每个简单基本块(结点)由多条语句/指令组成 • 与真实的程序执行路径并不相同 » 不考虑条件表达式的值 » 只进入循环块一次 » 只进入递归函数一次 • 流敏感,上下文敏感,稍弱于路径敏感 • 一种折中的程序遍历方法 • 避免非路径敏感方法中存在海量误报的情况 • 避免路径敏感的动态分析(如模糊测试)中存在的严重漏报问题 • 避免路径敏感的符号执行方法中约束求解所需要的巨大计算开销 • 权衡分析精度和时间开销后最适合程序静态分析的路径遍历方法 泛路径敏感的程序遍历方法 程序分析与漏洞检测 • 程序分析指对程序进行自动分析,以验证、确认或发现 程序具有特定性质(或者规约、约束)的过程或活动 • 软件漏洞是程序的安全缺陷,一般表示为程序所违背的 安全性质 • 软件漏洞检测指对程序进行自动分析,以发现程序漏洞 的过程或活动 • 通常可认为软件漏洞检测是程序分析的一个子集 程序分析工具 程序分析工具 程序分析方法比较 • 动态分析、静态分析和符号执行是在程序语义不同抽象层次 上的三类程序分析方法 – 静态分析不运行程序而对程序的特定表示形式(源代码,二进制,汇 编或者其它表示形式)进行语法层面或者语义层面分析的过程或活动 – 动态分析通过运行具体程序并获取程序的输出或者内部状态等信息进 行的程序分析过程 – 符号执行是通过使用符号变量取代输入中的具体值来模拟程序执行的 程序分析方法,或者说是使用静态分析的形式完成了动态分析的工作 静态分析 动态分析 需要运行程序 不需要 需要 需要测试环境 不需要 需要 需要测试用例 不需要 需要 完备性(漏报) 完备(无漏报) 不完备(有漏报) 可靠性(误报) 不同程度可靠性(最高无误报) 可靠(无误报) 对程序语义抽象 不同程度语义抽象 不抽象 分析精度(敏感性) 不同分析精度(最高路径敏感) 分析精度高(路径敏感) 分析速度 可控 速度慢 构建难度 构建难度大 构建难度小 • 程序分析方法的时间开销是与分析精度强相关的 • 希望的分析精度越高,分析的速度就越慢 • 分析的速度越快,分析的精度就不会太高 • 不一定是简单的正比关系 • 分析精度又主要取决于采用的程序遍历方法,一般有流敏感、 上下文敏感和路径敏感之分 • 流敏感指分析一个函数时(过程内)关注函数内语句间的控制关系 • 上下文敏感指分析函数调用时(过程间)区分函数调用/返回的位置 • 路径敏感指在条件分支指令处要根据条件表示式的值决定要分析的下一条指令或语句 • 路径敏感的分析既可用于过程内分析,又可用于过程间分析,精度最高 • 流敏感和上下文敏感的分析应用的场景不同,难以直接比较 程序分析的时间开销、精度和遍历方法的关系 • 调用图 • 调用图描述函数之间的调用关系,通常表示为G =(V,E), 其中:V是函数的集合(结点集),E是函数间调用与返回的 集合(边集合)。 • 基本块 • 基本块是只能从第一条指令进入,从最后一条指令离开的最 长指令序列,或者说基本块是除头尾指令外,不包含分支指 令和分支目标的最长指令序列。 • 控制流图 • 控制流图(CFG)用于描述函数的控制结构,通常表示为G = (V,E),其中:V是函数中基本块的集合,E是基本块之间 控制转移边的集合。 几个概念(1) • 简单基本块 • 简单基本块是通过在基本块中调用某些函数(如用户定义的非库函 数)的语句或指令处进一步进行撕裂所形成的更小的程序单元。 • 基本块内部可以存在任意的函数调用指令,而简单基本块通过消除 基本块内部的特定函数调用,能够更准确地表示程序的控制结构。 • 过程间控制流图 • 过程间控制流图的顶点是简单基本块,边是简单基本块间的函数内 控制转移或函数间的调用与返回。 • 控制流图一般用于描述单个函数的控制结构,而过程间控制流图在 此基础上又融入了调用图中的函数调用与返回,从而可以用来描述 多个函数的控制结构。 几个概念(2) C语言语句类型 • block-statement: { ... } • expression-statement • if-statement • for-statement • while-statement • do-statement • switch-statement • break-statement • continue-statement • return-statement • goto-statement • asm-statement • 指定C语言函数,构建其控制流图 • 从最顶层看 – 函数体是一个block-statement: { ... }类型(语句序列)的语句 – 其中的每条语句又可以是上述12种语句之一 – 递归地处理上述12种语句类型 – 当所有语句处理完成时即完成函数控制流图的构建 • 思考与约定 – 为了满足后续创建程序过程间控制流图需要,要求这里创建的函数控制 流图(属于有向图)中的结点是简单基本块 – 现实程序中函数可能含有多个return-statement(多出口),第一条语句 也可能是循环块(多入口),可通过添加入口结点和退出结点(确保单 入单出)简化分析 • 相关概念 – endcall属性:以用户函数(非库函数)调用结束的基本块 – callreturn属性:以用户函数(非库函数)返回开始的基本块 – 边界结点集:有向图中下一步需要拓扑扩展后继结点的结点 构建函数的控制流图 • 清空边界结点集 • 依次取出语句序列中的每一条语句: – 递归处理该语句 – 如果语句的边界结点集非空 &&非最后一条语句: • 创建新结点 • 将新结点添加到每个边界结点的后继结点集 • 设置新结点为当前结点 – 如果是最后一条语句,将其边界结点集并入整个语句 序列的边界结点集 block-statement: { ... } expression-statement • 清空边界结点集 • 添加当前语句到当前结点 • 如果当前语句包含对用户函数(非库函数)的调用: • 标记当前简单基本块为endcall基本块 • 保存调用的实参和被调用函数的开始位置 • 将当前结点加入边界结点集 • 清空边界结点集 • 创建then结点 • 将then结点加入当前结点的后继结点集 • 递归处理block-statement类型的then块 • 将then块的边界结点集并入边界结点集 • 如果存在else分支: • 创建else结点 • 将else结点加入当前结点的后继结点集 • 递归处理block-statement类型的else块 • 将else块的边界结点集并入边界结点集 • 如果不存在else分支: • 将当前简单基本块加入边界结点集 if-statement • 清空边界结点集 • 创建init,step,condition,body,end共5结点 • 将init结点加入当前结点的后继结点集 • 将condition结点加入init结点的后继结点集 • 将condition结点加入step结点的后继结点集 • 将body结点加入condition结点的后继结点集 • 将end结点加入condition结点的后继结点集 • 处理block-statement类型的循环块 • 如果循环块的边界结点集非空: • 将step结点加入循环块的每个边界结点的后继集 • 将end结点加入边界结点集 for-statement • 清空边界结点集 • 创建condition,body,end共3个结点 • 将condition结点加入当前结点的后继结点集 • 将body结点加入condition结点的后继结点集 • 将end结点加入condition结点的后继结点集 • 处理block-statement类型的循环块 • 如果循环块的边界结点集非空: • 将condition结点加入循环块的每个边界结点的后继集 • 将end结点加入边界结点集 while-statement • 清空边界结点集 • 创建body,condition,end共3个结点 • 将body结点加入当前结点的后继结点集 • 将body结点加入condition结点的后继结点集 • 将end结点加入condition结点的后继结点集 • 处理block-statement类型的循环块 • 如果循环块的边界结点集非空: • 将condition结点加入循环块的每个边界结点的后继集 • 将end结点加入边界结点集 do-statement • 清空边界结点集 • 创建end结点 • 依次处理每个分支: – 创建分支body结点 – 将分支body结点加入当前结点的后继结点集 – 处理block-statement类型的分支body块 – 如果分支body块的边界结点集非空: • 将end结点加入分支body块的每个边界结点的后继集 • 如果不存在default块: – 将end结点加入当前结点的后继结点集 • 将end结点加入边界结点集 switch-statement •[break-statement] • 将end结点加入当前结点的后继结点集 •[continue-statement] • 如果是在for循环内: » 将step结点加入当前结点的后继结点集 • 如果是在while或者do-while循环: » 将condition结点加入当前结点的后继结点集 •[return-statement] • 添加当前语句到当前结点 • 将函数的退出结点加入当前结点的后继结点集 •[goto-statement] • 将goto的目的结点加入当前结点的后继结点集 •[asm-statement] • 极少遇到,记录后跳过 其他语句类型 • 注1: – 上述针对if-,for-,while-,do-,switch-和return-statement的处理逻辑中并 没有包含对其中的条件表达式和返回表达式的处理 – 但这些语句中也可能包含对用户函数(非库函数)的调用,附加的处理逻 辑与对expression-statement的处理逻辑类似 • 注2: – 针对for-,while-,do-statement的处理逻辑中,需额外判断“条件表达式 为永真常量”情况,此时不需“将end结点加入condition结点的后继集” 补充说明 • 确定起点和终点 • 起点和终点可由用户指定 • 但是更好的办法是根据一定的启 发式规则自动确定 程序的过程间控制流图 call f endcall entry exit f call f endcall entry callreturn exit f call f endcall call f endcall callreturn • 连接相关函数 • 发现相关函数 • 对于给定的一对起点和终点: – 根据起点所在的位置确定起点函数(Start) – 根据终点所在的位置确定终点函数(End) – 递归找出起点函数(Start)的所有直系祖先函数(深色) – 递归找出终点函数(End)的所有直系祖先函数(深色) – 合并起点函数和终点函数的所有直系祖先函数 • 对于每个直系祖先函数: – 根据前面提供的方法构建控制流图 – 找出第一级相关函数集(带标记1的浅色块) • 对于第一级相关函数集中的每个函数: – 根据前面提供的方法构建控制流图 – 递归地找出所有相关函数(浅色块) • 将直系祖先函数加入相关函数 发现相关函数 • 对于每个相关函数中的每个endcall结点: – 保存结点的原始后继结点集合 – 设置结点的后继集合为被调用函数的入口结点(单元素集) – 将结点加入被调用函数的入口结点的前驱集合 连接相关函数 call f endcall entry exit f call f endcall entry callreturn exit f call f endcall call f endcall callreturn – 对于每个原始后继(snd): • 给snd添加callreturn属性 • 将snd加入被调用函数的退出结 点的后继集合 • 保存snd的原始前驱集合 • 设置snd的前驱结点集合为被调 用函数的退出结点(单元素集) • 算法:获取泛路径(Getpath) • 存储: – 泛路径(path),结点全局编号序列 – 泛路径列表(pathlist) – 调用函数栈(calleepath) – 调用点栈(endcallpath) – 重复进入函数数量(nfuncvisited) • 输入: – 源结点全局编号(srcnum ) – 目的结点全局编号(destnum) – 递归深度(deep),初始为0 • 输出:所有泛路径 过程间控制流图遍历算法 算法伪代码 • 以简单基本块(结点)之间的前驱-后继控制关系为基础来保 证函数内控制流的敏感性 流敏感 IF THEN ELSE • 以简单路径(任意边均不能重复出现)为基础可保证每次遇到 循环块时仅进入一次 • FOR-〉INIT-〉CONDITION-〉BODY-〉STEP-〉CONDITION-〉END • FOR-〉INIT-〉CONDITION -〉END • WHILE-〉CONDITION-〉BODY-〉CONDITION-〉END • WHILE-〉CONDITION-〉END • DO-〉BODY-〉CONDITION-〉END 遇到循环块和递归函数时仅进入一次 • 递归函数具有和循环类似的性质,因此每次遇到函数的递归调 用时,泛路径不再进入 • 上下文敏感性可以通过判断函数调用后返回结点的原前驱结 点是否是最后的endcall结点来保证 • 从A点调用函数f后,只能退出到A+1,从B点调用函数f后, 只能退出到B+1 上下文敏感性 A: call f endcall entry A+1: callreturn exit f B: call f endcall B+1: callreturn • 不同位置调用同一函数所使用的实参一般不相同,为了尽可 能精确,泛路径会多次进入一个函数 • 一条泛路径上可能包含如下的边序列 •… •A-〉 • entry-〉 • f-〉 • exit-〉 • A+1-〉 •… •B-〉 • entry-〉 • f-〉 • exit-〉 •B •… 多次进入同一个函数 A: call f endcall entry A+1: callreturn exit f B: call f endcall B+1: callreturn 非常量格式化字符串 标记调用格式化串危险函数的位置和参数信息 用户函数 针对每个标记,构造以输入点函数为根的有向图 反向检查路径中每个简单基本块 格式化参数 为常量 是 可到达输入点,表示格式化参数可控; 报告可疑漏洞,并输出路径; 此时可以结束,也可以继续寻找更多路径 否 可获取从输入点 到标记位置的路径 是 否 结束 我们来解答 非常量格式化字符串 • sprintf(expr(format), ……); – 格式参数名:format • 赋值语句 – format = a1; – format = “hello world : %s”; – format = strcpy(buf, a1); • 函数调用语句 – strcpy(format , a1); – strcpy(format , “hello world”); – memset(format , ‘a’, len); • endcall – 形参到实参 • callreturn – 跳过参数不管函数 • 梅宏, 王千祥, 张路, 王戟. 软件分析技术进展[J]. 计算机学报,2009, 32(9):1697-1710 • A. Takanen, J. DeMott, C. Miller. Fuzzing for Software Security Testing and Quality Assurance [M]. USA:Artech House Inc., 2008: 22-32 • M. Sutton, A. Greene, P. Amini. Fuzzing: Brute Force Vulnerability Discovery [M]. USA:Pearson Education Inc., 2007 • HotFuzz. http://peachfuzzer.com/HotFuzz • IDA Pro. http://www.hex-rays.com • C. Cadar, D. Dunbar, D. Engler. KLEE: Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs [C]. USENIX Conference on Operating Systems Design and Implementation, USA: USENIX, 2008:209-224 • G. Necula, S. McPeak, S. Rahul, W. Weimer. CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs [C]. Compiler Construction, Berlin:Springer-Verlag, 2002:213–228 • BinNavi. http://www.zynamics.com/binnavi.html 参考文献 谢谢
还剩32页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

n7xx

贡献于2014-10-28

下载需要 8 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf