本文的目的是对本实验室研发的一款C程序静态分析工具进行效率优化。为了检测场景复杂的漏洞,工具采用了路径敏感和过程敏感的分析策略。该策略使检测路径数随代码规模的增长呈非线性增长,导致分析效率低,工具可以检测的代码规模远远达不到预期。进行效率优化是极其重要且必不可少的工作。路径敏感的特点是遍历所有可能的路径,针对该特性,本文设计并实现了预遍历模块对控制流图进行剪枝。为了实现该模块,本文首先将遍历框架实现为深度优先遍历,设计并实现了新的数据记录方式避免分支节点处大量数据的备份和恢复。预遍历之前需要将所有有定义的函数进行拓扑排序,使被调用函数早于调用函数被分析。预遍历首先根据常见的漏洞场景以及用户配置信息标记控制流图中的单个节点,然后使用迭代算法将被标记节点的状态向其前继传播,直到整个控制流图中所有节点状态不再发生变化,迭代算法结束。此时能够到达被标记节点的路径已经全部被标记,而没有被标记的路径则是没有分析意义的路径。后端检查漏洞时,根据预遍历标记的信息并结合已经收集的数据信息决定被标记的路径是否应该遍历。过程敏感的特点是遇到函数调用,只要被调用函数有定义就要分析被调用函数。每进行一次函数调用本质是将该函数的控制流图展开,大量增加了需要分析的路径数。为了减少函数调用,本文将原有的嵌入式分析方法改为记忆式分析方法,即记录已经见过的指向信息以达到重用的目的。为了减少需要记录的模式数和提高模式重用的概率,本文使用扩充名替代的方式将指向信息抽象为调用模式。为了每个函数每次调用使用相同的扩充名,扩充名使用了预先分配策略。如果抽象后的调用模式之前记录过就会取其对应的结果作为此次分析结果,不再分析被调用函数,否则分析该函数并记录调用模式和调用完毕后的指向模式。为了使安全分析工具更加灵活的应对不同特性和规模的检测代码,本文在预遍历和跨过程模式匹配模块添加了若干个配置项。用户可以根据实际情况配置这些参数,以使工具更加侧重分析效率或者分析精度。本文最后对设计并实现的各个策略进行效率测试。测试的结果表明预遍历和跨过程模式匹配模块对效率提高有很大的帮助。在大幅提高检测效率的前提下工具仍能保持原有的分析精度,效率优化达到了预期的效果。