严格控制依赖及其对动态信息流分析中的影响外文翻译资料

英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

严格控制依赖及其对动态信息流分析中的影响

Tao Bao, Yunhui Zheng, Zhiqiang Lin, Xiangyu Zhang, Dongyan Xu

Department of Computer Science, Purdue University

{tbao,zheng16,zlin,xyzhang,dxu}@cs.purdue.edu

概要

程序控制依赖对动态信息流追踪和data lineage tracing(一种追踪输入集对多个输出中的单个输出的影响的技术)有很大的影响。在不考虑依赖关系的情况下，信息可以通过隐式通道泄漏掉而不被追踪到;重要的输入可能在输出中没有任何体现。然而，考虑到控制依赖可能导致在信息流追踪中的大量虚假警报或产生大量我们不需要的数据集合。我们定义一种特殊的控制依赖类型，称为严格控制- - - pen(SCD)。SCDs的性质与数据依赖非常相似，它能反映出语句之间的强相关性，所以应该以数据依赖在各种应用程序中的方式去看待SCDs。我们正式定义了概念。我们还描述了一个低成本的允许追踪严格控制依赖的方案。我们的经验评估表明，该方法的开销非常低，并且能极大提高数据追踪和污染分析的效率。

分类和主题描述符

D.2.5[软件工程]:测试和调试。

调试aids、监视器、跟踪;D.3.4(编程语言):处理器-调试程序

一般术语

算法,度量、可靠性、安全性

关键字

严格控制依赖，控制依赖，数据依赖，动态信息流，污染分析。

1.介绍

程序依赖对于广泛的应用程序是必不可少的。动态信息流追踪[20,17,11]阻止了可信信息被泄露给不受信任的实体，例如，它可以透过监控信息在程序依赖中的复制阻止用户的密码通过网络连接被发送出去。污染分析[2,19]，污染是从外部接收来的。污染是通过程序依赖传播的，它会污染被不可信输入影响的数据。一旦被污染的数据被用于关键的位置，比如指针解除引用或控制流转移，就会产生警告，以表明系统完整性可能受到损害。通过程序依赖，切片[21,9]识别影响给定变量值的语句集，用于调试、回归测试等。Lineage tracing[26,3]计算对给定变量的值产生影响的输入集。它还依赖于捕获程序依赖。

图1:信息流追踪中的例子。

传统上，程序依赖性被分为数据和控制依赖[6]。

非正式地,j语句当且仅当一个变量被定义为i但是在j中引用的时候才是变量i的数据依赖。语句j当且仅当他的执行直接由p的结果分支直接决定时才是谓语p的控制依赖。前面提到的许多应用仅仅依靠数据依赖。

例如，许多污染分析只通过数据依赖来传播污染。

换句话说，假设语句i和j是i: x=hellip;;hellip;;j:y = f(x);j是i的数据依赖，如果x被污染，变量y就会被污染。

类似地，大多数信息流追踪系统只监视数据依赖。例如，如果x在i是可信的，则y在j也是可信的，因为数据依赖。然而，我们知道，控制依赖会导致隐式信息流[11]，这可能导致信息泄漏或不被检测到的完整性违规。

以图1 (a)为例，变secret含有可信信息。

如果在第2行使用true分支，那么就会有从secret到output的信息流。因为输出等于1指明了secret的值是1000。因此，在6号位置有信息泄漏。但是，这种泄漏没办法通过只考虑数据依赖来捕获，因为4的输出的定义没有使用任何变量。在最近一项关于污染分析的实用性的研究中[19]，隐式信息流被认为是造成无法捕获泄露的一个重要原因。

只考虑控制依赖显然是有问题的。上例中信息流和污染分析的结果表明大量与可信数据关系不密切的数据没必要再认为那是可信的。考虑图1 (b)中的例子，假设采用了预测为真的分支。如果考虑语句4和2之间的控制依赖关系，输出会被标记为可信，而在6处发送的包被认为是信息泄漏。然而，这里却几乎没有任何信息泄露。特别地，从第6行发送的观察到的包来看，攻击者只能推断出secretgt;1000。也就是说，控制的只显示了非常少的信息。我们稍后将在本文中展示:由于这些不那么信息丰富的控制依赖关系在程序中非常普遍，我们认为到它们会导致大量的假信息泄露。类似地，在谱系追踪中，如果考虑了这种控制依赖，许多输出的谱系集合几乎包含了所有的输入集，尽管大多数输入可能不会直接暴露到输出。

其他研究人员[2]也有类似的观察结果。

我们的观察结果是，虽然许多控制依赖性不应被考虑，否则，会引入假的信息泄露，但有一些控制依赖性，其特征与数据依赖的特征非常相似，因此应该以类似的方式去处理这种控制依赖。我们称其为严格的控制依赖(SCD)。大多数应用程序只考虑数据依赖的原因是数据依赖通常会造成强相关性。

考虑i和j之间的简单数据依赖关系:i: x=hellip;;hellip;;j:y = x 1。我们可以观察到y的值与x密切相关。特别地,x在i的任何改变都会导致y在j的改变。从y的值,我们可以精确的反推出x的值。我们注意到这种强相关性也出现在某些控制依赖中。考虑图1 (a)中第4行的输出变量和第2行的secret(假设有true的分支)。

虽然它们的相关性是通过控制依赖来引入的，但从输出的值来看，我们可以精确地推测出secret的值。

将secret的值更改为其他任何东西都会导致另一个分支被采用，当然输出也会包含这些改变信息。因此，它是一个SCD。相比之下，因为。图1(b)中的控制依赖不是SCD,因为这里改变secret的值并不必然改变分支的结果。我们称其为松散控制依赖。

图2:由输入字符串“3rn2k/2pb1rpp/”描述的棋盘布局。

特别的是，字母r, n, k, p，和b表示rook, knight, king, pawn，和bishop, resp。

数字表示中间有多少空单元格。每个#39; / #39;表示换行。

在本文中，我们开发了一种检测SCDs的技术。总之，我们做出如下贡献。

bull;我们定义了严格控制依赖的概念，并介绍了它的语义。在语义分析的基础上，设计了一种静态方法来识别产生SCDs的谓语分支。我们发现除了“==”运算符外，SCD可能由所有比较运算符引起。

bull;我们引入了表格化的规则来检测执行过程中产生的动态 SCDs。我们还演示了如何将这些规则集成到输出谱系计算中。

bull;我们通过显示被计算的谱系集的数量来评估SCDs的效力。我们比较仅有数据依赖和数据依赖、典型的控制依赖并存的结果。我们开发了一种可以逼近模糊输入的理想谱系集的标准。我们使用理想谱系集来显示不同配置的假阳性(FP)和假阴性(FN)。我们的研究结果表明，只考虑数据依赖的情况会导致较高的FN，同时考虑到数据依赖和经典的控制依赖性会有较高的FP，而考虑到数据和严格的控制依赖，则FN和FP都很低。

bull;我们评估了计算SCD的代价，并与其他选项进行比较。结果表明，计算SCD降低了76%的程序执行速度，而计算所有的控制依赖降低了294%。

2.激励的例子

我们使用了一个真实的例子来演示SCD的效果。谱系追踪识别对单个输出值作出贡献的输入集。它已用于数据验证和调试[26,3]。我们可以把它看作是一种广义形式的污染分析，因为污染是作为一组输入。考虑SPECINT 2000 中的186.crafty。它是一个高性能的人工智能国际象棋程序。它将棋盘布局作为输入，并在有界的步骤中搜索最佳的移动。棋盘布局是用字符串来描述的。例如,一个字符串如“3 rn2k / 2 pb1rpp /”描述了一个布局的8times;8棋盘，如图2所示。图3展示了程序的一个片段，它解析输入字符串并生成棋盘布局。特别是，布局存储在64个元素的数组tboard中。字典bdinfo用于解释输入字符串中的每个字符。数组firstsq表示tboard数组中每个级别(行)的起始索引。例如，正如第8行中的值所描述的，第一行在tboard中的索引56开始，第二行从48开始。变量Whichsq和num描述当前正方形的行位置和列位置。第13-28行中的循环负责解析输入字符串。它遍历输入字符串中的每个字符。对于第14和第15行中的每个char，它识别与输入char匹配的dictionary bdinfo中的条目，并将其存储在变量match中。如果match等于24，意味着输入char是rank的结束符号，在第17-20行中，列位置被重置，rank位置递增，新的rank的开始索引被加载。如果match表明输入的字符是一个数字，在第22和23行中，那么当前的方块将根据指定的空闲方块数进行更新。如果两种情况都不正确，那么输入字符必须是设置在第26行的数组元素。

• //the beginning index of each rank in #39;tboard#39;
• int firstsq[8]={56,48,hellip;,0};

您可能感兴趣的文章

• 使用金属伪影减少算法从 CT 数据生成的数字模型的准确性外文翻译资料
• 彩色光流外文翻译资料
• 云环境下基于虚拟机配置文件针对DDOS攻击的最优网络攻击探测方法外文翻译资料
• 监控大视频数据分析中的模糊逻辑: 综述、挑战和研究方向外文翻译资料
• PeopleSoft人力资源管理系统实施外文翻译资料
• 图像绗缝的纹理合成与转移外文翻译资料
• 管理云中的资源:Chrome扩展到OpenStack外文翻译资料
• 一种基于凸显区域检测和SPBVM的美学QR码新算法外文翻译资料
• 微信小程序-所有你需要知道外文翻译资料
• Java核心技术卷II高级特性外文翻译资料