张健等:程序分析研究进展 从某个 Input不大于128的输入下预测对应行为是一个潜在缺陷,其可能会在 Input大于128时发生进一步地, 我们可以构造一个满足预测条件的输入,再次运行程序去触发(验证)缺陷缺陷的动态预测在并发程序的动态 分析中经常用到,主要原因之一是:并发程序的运行除了与输入有关外,还与程序中线程之间的调度有关程序 缺陷的动态预测还会涉及到一些其他技术,例如,测试用例生成、约束求解、缺陷重现、线程调度等,其分析过 程与缺陷动态检测相比更为复杂 2.6基于机器学习的程序分析 经典的程序分析技术提供相对精确的分析结果,但同时也带来了包括路径组合爆炸、误报率较高等一系列 在实践中不可避免却难以应对的问题随着近年来通用计算设备能力的提高,海量的程序执行数据被存储和管 研究者采用机器学习、统计分析等系列技术提升现有的程序分析能力 现有的程序分析技术依赖于一定的启发式策略,如符号执行技术中的深度(或广度)优先搜索在动态分析 技术中,为了达到分析精度,这些策略可能带来较高的计算成本基于现有的标记数据(即已知分析结果的程序) 建立学习模型,机器学习技术可以学习新的可自适应的策略,减少启发式策略带来的成本消耗Li等人4为了 解决符号执行中的路径可达性问题,以最小化不满足性为目标,建立机器学习模型MLB,以减少经典的约束求 解方案在求解非线性约束及函数调用时的不足Kong等人面向自动机验证,研究了多个随机测试与符号执 行技术的整合策略通过调整状态转移概率优化动态符号执行Wang等人12提出了基于马尔可夫过程的动态 符号执行方法,以达到应用符号执行获得精确分析结果和应用随机测试覆盖搜索空间的平衡该方法采用贪心 算法获得优化模型的解,以期找到对应于近似最优性能的策略Chen等人1针对信息物理系统( cyber-physical system)的攻防模型,设计了基于程序变异的方案获得具有植入错误的模型训练数据以避免人工建立模型的巨 大成本Xong等人1提出了基于概率程序合成框架L2S该框架整合了包括程序合成的搜索空间、路径和潜 在解的概率估计方案能够按需地构建程序合成和修复技术,研究者可基于该框架深度定制和设计相关方法 在静态分析技术中,分析工具在获得较高的分析精度的同时,往往带来过高的误报率研究者建立了机器学 习模型,以剔除潜在的误报并减少静态分析的成本Heo等人1提出了基于异常点检测技术来滤除静态分析结 果中的误报该方法提取代码循环和函数调用中的特征,基于训练数据建立学习模型,识别潜在的误报并提升静 态分析的实用性Chae等人针对上下文敏感的指针分析,提出了基于分类器的自动特征抽取方案该方案可 有效提升现有的静态分析技术Oh等人8针对静态分析的精度和计算成本提出了基于贝叶斯优化的自适 应学习方案,并以此建立面向数据流和上下文的部分静态分析工具 Jeong等人设计了数据驱动的上下文敏 感的指针分析方案该方案通过非线性的上下文选择建立了识别上下文敏感函数的学习方法 3面向特定软件的程序分析技术 本节介绍程序分析技术在一些重点领域软件的应用,包括移动应用软件、并发软件、分布式系统、二进制 代码等方面的重要应用 3.1移动应用软件 近10年来,以智能手机为代表的智能终端以惊人的速度得以普及目前,以 Android和苹果iOS系统为代表 的智能手机数量和使用频度已远超个人计算机成为最流行的个人电子设备通过移动支付、购物和社交等各 式各样的移动应用,智能手机已经深度渗透进了人们的日常活动中相应地这些应用的运行状态和广大用户的 日常生活和工作有着直接的关系,也在很大程度上影响到了整个互联网的运转为此研究人员通过对移动应用 软件的程序分析,来检测其是否具有所期望的以安全性为核心的各种特性 1)污点分析技术 H于智能手机的使用特点移动应用的安全性分析常常可以归结为应用代码上跟踪敏感数据流的动态/静 态污点分析( taint analysis问题 动态污点分析最具代表性的 Android应用动态污点分析技术是 Taint Droid82,其通过修改的 Dalvik张健 等:程序分析研究进展 89 从某个 input 不大于 128 的输入下预测对应行为是一个潜在缺陷,其可能会在 input 大于 128 时发生.进一步地, 我们可以构造一个满足预测条件的输入,再次运行程序去触发(验证)缺陷.缺陷的动态预测在并发程序的动态 分析中经常用到,主要原因之一是:并发程序的运行除了与输入有关外,还与程序中线程之间的调度有关.程序 缺陷的动态预测还会涉及到一些其他技术,例如,测试用例生成、约束求解、缺陷重现、线程调度等,其分析过 程与缺陷动态检测相比更为复杂. 2.6 基于机器学习的程序分析 经典的程序分析技术提供相对精确的分析结果,但同时也带来了包括路径组合爆炸、误报率较高等一系列 在实践中不可避免却难以应对的问题.随着近年来通用计算设备能力的提高,海量的程序执行数据被存储和管 理;研究者采用机器学习、统计分析等系列技术提升现有的程序分析能力. 现有的程序分析技术依赖于一定的启发式策略,如符号执行技术中的深度(或广度)优先搜索.在动态分析 技术中,为了达到分析精度,这些策略可能带来较高的计算成本.基于现有的标记数据(即已知分析结果的程序) 建立学习模型,机器学习技术可以学习新的可自适应的策略,减少启发式策略带来的成本消耗.Li 等人[144]为了 解决符号执行中的路径可达性问题,以最小化不满足性为目标,建立机器学习模型 MLB,以减少经典的约束求 解方案在求解非线性约束及函数调用时的不足.Kong 等人[175]面向自动机验证,研究了多个随机测试与符号执 行技术的整合策略,通过调整状态转移概率优化动态符号执行.Wang 等人[172]提出了基于马尔可夫过程的动态 符号执行方法,以达到应用符号执行获得精确分析结果和应用随机测试覆盖搜索空间的平衡.该方法采用贪心 算法获得优化模型的解,以期找到对应于近似最优性能的策略.Chen 等人[176]针对信息物理系统(cyber-physical system)的攻防模型,设计了基于程序变异的方案,获得具有植入错误的模型训练数据以避免人工建立模型的巨 大成本.Xiong 等人[177]提出了基于概率程序合成框架 L2S.该框架整合了包括程序合成的搜索空间、路径和潜 在解的概率估计方案,能够按需地构建程序合成和修复技术,研究者可基于该框架深度定制和设计相关方法. 在静态分析技术中,分析工具在获得较高的分析精度的同时,往往带来过高的误报率.研究者建立了机器学 习模型,以剔除潜在的误报并减少静态分析的成本.Heo 等人[178]提出了基于异常点检测技术来滤除静态分析结 果中的误报.该方法提取代码循环和函数调用中的特征,基于训练数据建立学习模型,识别潜在的误报并提升静 态分析的实用性.Chae 等人[59]针对上下文敏感的指针分析,提出了基于分类器的自动特征抽取方案.该方案可 有效提升现有的静态分析技术.Oh 等人[179,180]针对静态分析的精度和计算成本,提出了基于贝叶斯优化的自适 应学习方案,并以此建立面向数据流和上下文的部分静态分析工具.Jeong 等人[181]设计了数据驱动的上下文敏 感的指针分析方案.该方案通过非线性的上下文选择,建立了识别上下文敏感函数的学习方法. 3 面向特定软件的程序分析技术 本节介绍程序分析技术在一些重点领域软件的应用,包括移动应用软件、并发软件、分布式系统、二进制 代码等方面的重要应用. 3.1 移动应用软件 近 10 年来,以智能手机为代表的智能终端以惊人的速度得以普及.目前,以 Android 和苹果 iOS 系统为代表 的智能手机数量和使用频度已远超个人计算机,成为最流行的个人电子设备.通过移动支付、购物和社交等各 式各样的移动应用,智能手机已经深度渗透进了人们的日常活动中.相应地,这些应用的运行状态和广大用户的 日常生活和工作有着直接的关系,也在很大程度上影响到了整个互联网的运转.为此,研究人员通过对移动应用 软件的程序分析,来检测其是否具有所期望的以安全性为核心的各种特性. 1) 污点分析技术 由于智能手机的使用特点,移动应用的安全性分析常常可以归结为应用代码上跟踪敏感数据流的动态/静 态污点分析(taint analysis)问题.  动态污点分析:最具代表性的 Android 应用动态污点分析技术是 TaintDroid[182],其通过修改的 Dalvik