开题报告-基于程序切片的软件安全测试

1、南京邮电大学毕业设计(论文)开题报告题目基于程序切片的软件安全测试学生姓名专业信息安全一、 对课题任务的学习与理解1. 课题产生背景随着计算机技术的高速发展，纷繁众多的计算机应用对人们工作和生活的影响越来越大。但是，软件规模的日益庞大以及繁琐的分工使得软件产品的质量往往难以得到保证，从而带来了日益严重的软件安全问题和安全隐患。因此，发掘软件中的潜在漏洞和脆弱点，诊断已发生的攻击行为并及时采取措施，都能在很大程度上降低软件受到恶意攻击的风险，减少攻击所造成的破坏和损失。软件测试是保证软件质量的一个重要环节，在现代软件工程中，软件测试在整个软件生命周期中所处的地位越来越高。随着软件规模和复杂性的不

2、断提高，采用传统的软件测试技术发现和定位软件中的错误也越来越难。 程序切片技术是一种分析和理解程序的技术，具有可以简化问题，缩小目标范围的特点。程序切片技术已被实践证明是一种能有效发掘软件漏洞、诊断软件攻击的技术，受到了研究者们的重视。因此，探讨一种利用程序切片技术来对软件进行高效安全分析的手段，有着很现实的意义。2. 课题实现目标本课题要求通过实际具体的C程序分析工具，获取相应的程序依赖图并对其进行安全测试研究。具体的成果形式包括：（1）给出基于C程序源码切片的安全测试方法；（2）提交毕业设计报告及其相关电子文档。二、 文献调研综述1. 程序切片技术的概述M. Weiser博士首先在1979

3、年定义了程序切片的概念：程序中的某个输出只与这个程序的部分相关语句以及控制谓词有关系，因此如果删除其他的语句或者控制谓词将对这个输出没有任何影响。也就是说，对于一个特定的输出，源程序和对于删除不相关的语句和控制谓词后所得的程序是作用相同的。其形式化定义如下：把满足如下两个条件的切片称为M. Weiser切片：第一，一个程序切片需要对应一个切片准则，用表示，其中n指程序中的某个兴趣点，一般指一条语句，V表示在这条语句使用的变量的集合。第二，程序P的切片s可以通过在P中删除零条或者多条语句后得到，且保证程序P和所得的切片S关于切片准则的作用是相同的。当时，M. Weiser博士把只与某个输出相关联

4、的语句和控制谓词构成的程序称之为源程序的静态切片。由此可见，一个程序的切片大多数是源程序的一个子集，这个概念准确的说其实就是程序切片的一个核心思想。后来随着研究的发展，研究者们对M. Weiser博士程序切片的概念进行了扩展，由于程序切片不一定都是可执行的，因此又包含了不可执行的切片思想，这也是一种静态切片，这样就丰富和发展了程序切片的内涵。随后，Korel和Laski又提出了动态切片的概念，它只考虑程序的某个特定执行情况，程序中的信息如数组、指针和循环依赖关系都可以在程序执行时动态确定。因此，动态切片与静态切片相比结果更加的准确。2. 程序切片的发展历程图1程序切片技术的发展历程第一个阶段是

5、基于数据流方程的切片阶段，这其实就是M. Weiser博士提出切片概念的阶段，主要使用了基于控制流图的数据流方程来计算程序切片。第二个阶段是基于依赖图的程序切片阶段，这一阶段产生了对程序切片提出了很多新的概念和算法。首先，Ottenstein等人在提出了基于程序依赖图的图可达性算法，并可以计算过程内后向程序切片，接着又提出了前向切片的概念和算法，以及基于依赖图的两步遍历图的可达性算法。最后Korel和Laski提出了动态切片的概念和算法。第三个阶段是面向对象的程序切片阶段，这一阶段是伴随着面向对象的高级程序语言的发展而产生，在1996年M.J.Horrald等人首次使用类依赖图来扩展系统依赖图

6、，从而表示面向对象的C+程序，并通过改进的两步遍历图可达性算法来计算程序的切片。随后ChristonSteindl在1999年通过对各种数据流以及控制流的计算，提出了面向对象程序切片计算的解决方法，起到了很重要的作用。最后一个阶段是程序切片变体阶段，这一阶段出现了各种程序切片的变体形式，例如砍片、削片、层次切片等等，这些都极大地促进了程序切片技术的迅速发展。3. 程序切片的分类自程序切片提出以来，伴随着各自领域的发展出现了许多略有不同的定义，相关的切片准则以及计算切片的算法。按照切片准则的不同，程序切片可分为静态切片和动态切片、前向切片和后向切片（或过程内切片和过程间切片）、面向对象切片以及条

7、件切片、分解切片等其他切片。4. 程序依赖图和系统依赖图程序依赖图（PDG）：PDG是程序的一种图形表示，它把控制依赖和数据依赖包含在单个的结构中。如果给定程序中的语句X和Y，则X和Y可以通过控制流或者数据流彼此关联。如果从Y至少可以引出两条路径，其中一条总会导致X的执行，而另一条可能导致X不执行，则成为语句X控制依赖于语句Y；如果有一条从Y到X的路径，且存在一个在Y点定义在X点使用的变量，且该变量在沿从Y到X的路径上其他任何地方没有被重新定义，则称语句X数据依赖于语句Y。PDG的形式定义是由一个控制依赖子图，一个控制流图和一个数据依赖子图组成。其中CDG包含了程序中的控制依赖；CFG描述了一

8、个程序的控制流，它类似于正常情况下的流图；DDG是一个程序中语句之间所有数据依赖的集合。CDG包含几种类型的结点，即语句结点表示程序中的语句；域结点概括了域中语句间的控制依赖；谓词结点（由此可以引出两条边）表示程序中的策略和分支条件。CDG中的域结点可以用相同的控制依赖来集合语句。DDG包含语句间的数据依赖。可通过在CDG的结点之间插入数据依赖边来构造DDG。同样PDG不允许过程间分析，它也没有能力表示继承、多态性和动态性定连等重要的面向对象的特性。系统依赖图（SDG）：SDG是程序的一种语法分析树表示。结点表示程序构造，输入输出参数和调用位置等。边表示与之相连的结点之间的各种依赖（例如数据依

9、赖，控制依赖和声明等）。程序依赖图通常是为单个的过程间程序来定义的。由于现实世界的程序一般由多个过程组成的，所以必须考虑使用一种与现实世界程序匹配的表示方法，于是Horwitz等人提出了系统依赖图。SDG是一颗经过装饰的表示程序的语法分析树。形式地说，SDG是由一个程序依赖图和一组过程依赖图（PrDG）构成的有向、带标记的多重图。PDG模型化软件系统中的主程序，PrDG模型化软件系统中的多个过程体。SDG可以用来处理过程间的数据流和控制流，并能表示参数传递。SDG允许过程间分析，但面向对象程序远不是一些过程或方法的简单组合，所以SDG提供的机制还不足以描述这些面向对象的概念。5. 编译器架构L

10、LVMLLVM 是一种应用广泛的开源编译器架构，该架构采用模块化设计，能够轻松地新增对编程语言和处理器架构的支持。 LLVM 支持各种各样的编程语言和前端，其中包括 C/C+、Objective-C、Fortran、Ada、Haskell、Java bytecode、Python、Ruby、ActionScript、GLSL 以及 Rust。LLVM 是 Illinois 大学发起的一个开源项目。从字面上看，它是一个虚机系统，然而这又和之前为大家所熟知的 JVM 以及 .net Runtime 这样的虚机不同，它提供了一套中立的中间代码和编译基础设施，并围绕这些设施提供了一套全新的编译策略（使

11、得优化能够在编译、连接、运行环境执行过程中，以及安装之后以有效的方式进行）和其他一些非常有意思的功能。LLVM的三阶段设计：图2 LLVM的三阶段主要参考文献：1 Weiser M. Program slicing. IEEE Transactions on Software EngineeringM，1984，16(5)： 498-509.2 Binkley D.， Gallagher K. B. Program slicing. Advances in ComputersM，1996， 43： 1-50.3 李必信. 程序切片技术及其应用M. 北京：科学出版社,2006.4 陈振强. 基于依赖性分析的程序切片技术研究D.东南大学， 2002.5 The LLVM Compiler Infrastructure. http：/ .6 李娟. 基于故障注入的软件安全测试技术研究D.国科学技术大学， 20097 王越凡. 基于源码分析的软件安全测试技术研究D.北京邮电大学，2009三、 实施方案认真了解程序切片相关知