减少动态分析开销的技术

158理论计算机科学电子笔记70第4期（2002）网址：http://www.elsevier.nl/locate/entcs/volume70.html21页减少动态分析的开销1Suan Hsi Yong2和Susan Horwitz3威斯康星大学麦迪逊分校计算机科学系1210 West DaytonStreet，Madison，WI 53706 USA摘要动态分析（在程序执行过程中使用代码检测和防止错误）可以是一种有效的调试方法，也是一种有效的防止恶意代码造成伤害的方法。这种方法的一个问题是插装引入的运行时开销。我们定义了几种技术，这些技术涉及使用静态分析的结果来识别可以安全删除仪表的某些情况。虽然我们在设计这些技术时考虑到了特定的动态分析（这一点由HTMLType-Checking工具使用），但这些想法可能具有更普遍的适用性。1介绍像C和C++这样的语言允许潜在的不安全操作，如指针算术，强制转换和显式内存管理，这为许多检测错误的困难打开了大门，代码插入程序提供了机会[20]。 为了解决这些问题，已经开发了一些涉及动态分析的系统：检测程序，以便在执行期间发生错误时检测到越界数组索引和坏指针解引用[2，7，14，13，9，10]。 在某些情况下，这些类型的动态检查甚至是由语言定义强制执行的（例如，Java保证每当索引越界或执行错误的强制转换时当然，动态分析的好处也有相关的成本：该工具引入了一定量的运行时开销。本文提出了几种减少开销的技术，通过使用静态分析来确定某些情况下，可以安全地省略插装。1这项工作得到了国家科学基金会的部分支持，9970707和CCR-9987435。2电子邮件地址：suan@cs.wisc.edu3电子邮件地址：horwitz@cs.wisc.edu2002年由ElsevierScienceB出版。 诉 操作访问根据C CB Y-NC-N D许可证进行。杨和霍维茨159虽然这些技术是为一个特定的工具而设计的：XML类型检查（RTC）工具[10]，但这些想法可能具有更广泛的适用性。本文的其余部分组织如下。第2节提供了RTC工具的背景;第3节描述了几种可以用来识别不必要的插装的静态分析：第3.2节描述了一种将表达式分类到类型安全级别的方法，这样就可以消除“类型安全”表达式的插装，第3.3节给出了这种分析的三个改进（一个是考虑使用未初始化的数据，一个是删除对空指针解引用的一些检查，一个是识别冗余插装）。第4节介绍了实验结果，帮助衡量这些优化的潜在好处，第5节讨论了相关工作，第6节总结。2RTC工具RTC（Type-Checking）工具检测C程序，以便在程序执行期间跟踪每个内存位置的运行时类型每当值v被写入位置l时，l此外，这个运行时类型与l每当使用位置中的值时，都会检查其运行时类型，如果该类型在使用该值的上下文中不合适，则会发出错误消息;为避免级联错误消息，在生成错误消息后，会将运行时类型设置为正确的类型2.1激励的例子虽然已经提出了许多其他工具来检测越界数组访问和坏指针解引用，但RTC工具的类型检查方法还可以检测涉及类型误用的更微妙的错误其中一类错误与C程序员使用结构模拟类和继承的编程风格有关[16]。例如，下面的声明可以用来模拟超类Base和子类Sub的声明：int n; int n; int n;{int * b1; int *b2;char b3;};可以编写一个函数来对超类的对象执行某些操作：杨和霍维茨160void f（struct Base *b）{ b->a1 =.b->a2 =.}并且该函数可以使用类型为structBase *或structSub *的实际参数调用：struct Base; structSub sub; f（base）;fold（）;ANSI C标准保证每个结构的第一个字段都存储在O_xSet 0，并且如果两个结构有一个共同的初始序列，- 具有兼容类型的一个或多个字段的初始序列-然后该初始序列中的对应字段存储在相同的操作集。因此，在这个例子中，场a1和b1都被保证为0，并且场a2和b2都被保证处于相同的Occupset。因此，我们认为，虽然第二个调用f（&sub）会导致编译时警告（可以通过适当的类型转换来避免），但它既不会导致编译时错误，也不会导致运行时错误，并且函数f中的赋值会正确地设置sub.b1和sub.b2的值。然而，程序员可能会忘记structSub应该是structBase的子类型的约定，并且当对代码进行更改时可能会更改其中一个公共字段的类型，向structBase添加新字段而不向structSub添加相同的字段，或者在字段b2之前向structSub添加新字段。例如，假设一个新的int字段，i1被添加到结构Sub中：{inti; int b; int i;现在，当第二次调用f时，赋值b->a2 =. 将写入sub的i1字段而不是b2字段。如果调用f时没有正确设置b2字段，或者i1字段被一个非预期的值覆盖，这可能会在执行过程中导致运行时错误RTC工具对运行时类型的跟踪可以帮助程序员发现这个逻辑错误的来源赋值b->a2 =. 使sub.i1被类型指针标记。如果以后在需要int的上下文中使用sub.i1，则会由于所需类型（int）和当前运行时类型（指针）之间的不匹配而导致错误消息注意，在这个例子中，像Purify [7]这样的工具不会报告任何错误，因为没有错误的指针或数组访问：函数f没有在其结构参数的范围外写入，它只是从程序员的角度来看是该结构的错误部分杨和霍维茨161⟨⟩⟨⟩⟨ ⟩ ⟨⟩2.2跟踪类型RTC工具将每个内存位置与一个运行时类型相关联，该运行时类型表示为元组σ，size，其中σ是未分配、未初始化、零、整数、实数和指针之一，size是类型的大小（以字节为单位）例如，char用integral，1表示，float用real，4表示（在大多数平台上）。指向不同类型的指针由相同的运行时类型pointer4（在所有指针大小为4字节的平台上）表示，typedef不被视为单独的类型。对于聚合对象（结构和数组），每个字段/元素的运行时类型被单独跟踪特殊的零类型用于分配文字0的内存位置;它被视为与所有C类型兼容。运行时类型存储在程序使用的内存的“镜像”中RTC工具已经实现来处理所有ANSI C。它将一组给定的预处理C源文件转换为插装C文件。然后编译这些代码并将其与RTC库链接，生成一个执行运行时类型检查并报告错误和警告消息的可执行文件插装阶段是C程序的源代码到源代码的转换;它在程序的抽象语法树上执行语法指导的转换，以添加对跟踪运行时类型的RTC库函数的这些库函数执行的操作可以分为以下几类：declare--一个变量声明被检测，以将变量镜像中的运行时类型设置为未初始化。（最初，所有内存的镜像都标记为未分配。）verify-在类型τ的上下文中使用存储器位置x，以将x的镜像中的运行时类型与τ进行比较。如果类型不兼容，则发出错误消息，并将x的运行时类型更正为τ（以防止级联错误消息）。verify-pointer- 检测指针解引用以检查指针目标的镜像 如果是，则发出错误消息。此检查检测悬空指针解引用、某些杂散指针（指向已分配块之间或超出已分配块的指针）的解引用以及空指针解引用（因为内存位置0的镜像被标记为未分配）。copy- 一个赋值语句用于将右侧值的运行时类型复制到左侧位置的镜像中;此外，如果赋值的运行时类型与赋值的静态类型不匹配，则会发出警告消息。该工具的设计，使仪表模块可以与uninstrumented的。这种可扩展性非常有用，例如，如果程序员只想调试大型程序的一个小组件杨和霍维茨162只需要感兴趣的文件，并将它们与剩余的未检测的对象模块链接。但是，在这样做时需要注意的是，它可能会导致虚假的警告和错误消息，因为代码的未检测部分没有为它们使用的内存位置维护必要的运行时类型信息例如，如果将对程序未配置部分中的有效对象的引用传递给插装函数，则该工具将认为该对象未分配，并且如果该对象被引用，则可能输出虚假错误消息。这个问题通常会扩展到库模块。例如，像memcpy这样的函数中的值的初始化，像fgets这样的函数中的输入值的初始化，以及像ctime这样的函数返回的静态缓冲器中的数据类型都不会被捕获。为了处理这些问题，我们创建了一个通用库函数的插装版本的集合，这些库函数是一个插装类型。这些是原始函数的包装器，手写以在RTC镜像中执行必要的标记更新操作，他们的典型行为。这些插装库函数中包括内存管理函数.每次调用malloc（或它的一个亲戚）都被替换为调用包装器版本，在成功分配内存块时，将该内存块的镜像设置为未初始化。类似地，free函数的包装器版本将镜像重置为未分配。malloc包装器还在已分配的块之间添加填充，以减少流浪指针从一个块跳到另一个块的可能性（这是Purify [7]使用的方法）。RTC工具能够检测某些SPEC基准测试（go、ijpeg）、Solaris实用程序（nroff、col等）中的错误和Olden基准（健康，voronoi）[10]。大多数错误是越界数组或指针访问。在Solaris实用程序中，越界访问导致程序崩溃;在SPEC情况下，错误对执行没有明显影响，这使得在不使用RTC工具等工具的情况下很难检测到错误。在每种情况下，RTC工具都能够检测到越界内存访问，因为指向的内存类型与预期的类型不同。最后，RTC工具自然适合交互式调试。当发出警告或错误消息时，会发送一个信号（SIGUSR1），并可以被GDB等交互式调试器拦截[17]。然后，用户可以检查内存位置，包括镜像，并利用GDB3消除不必要的检查虽然RTC工具的初始实现证明了它能够如上所述在实际程序中发现错误，但该实现的缺点是性能差：在最坏的情况下，杨和霍维茨163程序运行速度比未检测版本慢130倍。这是因为RTC工具检测程序中的每个表达式，并跟踪程序中使用的每个下面概述了一些策略，通过使用静态分析的结果来识别和删除不必要的故障，从而减少运行时开销首先，我们描述了一个对数据流不敏感的分析，它可以识别接下来，我们描述三种低灵敏度的微调。这些分析尚未完全实现;为了衡量它们将提供的潜在加速，我们实现了一个更简单的分析，并在许多程序上进行了尝试。这些实验的结果报告在第4节中。3.1假设下面描述的静态分析需要指针分析的结果来解释程序中可能的别名。我们假设（对低敏感的）指向分析（例如，[1，21，18，5]），使得程序中的每个指针p与指向集合相关联，该指向集合包含p在程序中的某个点处可能指向的变量。我们还假设输入程序中的赋值语句已经被规范化为由以下上下文无关语法定义的形式赋值左值=右值|lvalue=(τ) cvtrvalue|lvalue=(τ) extrvalue|lvalue=（τ）cpyrvaluelvaluevar|特 拉瓦尔右值常量|var|特拉瓦尔|&var|瓦尔塞瓦尔其中const是一个常量，var是一个变量，并且narrow表示任何C二元运算符。类型转换分为三种形式。第一种形式，（τ）cvte，是一种类型转换，涉及表示的变化，并包括转换（例如，整数和浮点值之间）和数据的截断（例如，当类型转换长int为短int时）。第二种形式（τ）exte表示将数据从较小类型扩展到较大类型的类型转换，而不改变数据位（例如，从一个短int到一个长int）。 第三种形式，（τ）cpye，表示类型转换，其中没有改变数据的形式，并包括指针和整数（相同大小）之间的转换我们关注的这些形式之间的区别是，对于（τ）cvte，RTC插装检查e的运行时类型是否与其静态类型兼容;如果它们不兼容，则发出错误消息，并将表达式的运行时类型设置为τ以抑制进一步的错误消息。对于（τ）exte和（τ）cpye，不执行这样的检查和校正大多数C赋值语句都可以按照上面的定义进行规范化。例如，涉及数组索引的赋值，如x=a[i]，可以重写为tmp=a+i;x=tmp。如何处理剩余杨和霍维茨164C构建体（例如，结构、联合和函数调用）仍有待解决。3.2类型安全水平分析我们的第一个静态分析是一个对数据流不敏感的类型安全级别分析，它将程序中的表达式划分为“类型安全”级别，所提出的方法将程序中的表达式分为以下类型安全级别：safe- 一个表达式，它的运行时类型保证总是与它的静态类型兼容，并且可以消除所有的插装。unsafe- 运行时类型可能与其静态类型不兼容的表达式;这包括*p形式的表达式，当指针p可能为NULL或可能包含无效地址时。必须完全检测不安全的tracked- 一个l值表达式，其运行时类型始终与其静态类型兼容，但可能被不安全指针或指向集合包含不兼容类型的位置的指针指向被跟踪的表达式图1给出了一个示例代码片段，以说明所提出的方法背后的直觉。由于该方法对语句的顺序不敏感，因此在分析中忽略了语句的顺序。表达式p0、p1和p2是安全的，因为它们只被分配了指针类型的值（回想一下，RTC工具不会在指针类型之间进行区分，因此p1既被分配了int变量的地址又被分配了float变量的地址这一事实并不重要;还回想一下，文字0被视为与所有类型，包括指针）。表达式f、*p0、*p1和*p2都不安全。变量f是不安全的，因为第13行的赋值可以通过*p1将一个int值写入f。表达式*p0是不安全的，因为p0可能是NULL（由于第6行的赋值）;*p1和*p2是不安全的，因为虽然它们每个都有一个静态类型int*，但*p1可能引用一个float（由于第10行的赋值），*p2可能指向无效地址（因为第11行的指针运算最后，跟踪表达式i。 虽然i总是包含一个int值，但它可能会被p1指向，p1还包括f-一个浮点变量-在它的point-to集中。 这意味着每次使用*p1都将被检测以检查其运行时类型，因此p1的指向集合中的每个位置都包括杨和霍维茨165代码表达类型安全级1.整数i;p0、p1、p2安全2.int *p0，*p1，*p2;f、*p0、*p1、*p2不安全3.float f;我跟踪4.i=1; n = 1;5.f=2.3;6.p0 =0;7.如果（*p0 == 0）8.int i;9.其他10.publicintfindDuplicate（int*）;11.p2 = p1 +i;12.如果（*p2！= 0个）13.*p1 =4;Fig. 1. 类型安全的例子。i- 必须在镜像中记录其运行时类型在这个框架内，我们可以设计不同精度的方案来确定每个表达式的类型安全级别。使用以下顺序，不安全履带式保险箱任何在小于或等于其真实级别的级别上对每个表达式进行分类的方案例如，未优化的RTC工具对应于一个极端，其中所有表达式都被认为是不安全的。接下来的三个部分描述了一个有效的对数据流不敏感的分析来对表达式的类型安全进行分类。分析工作如下：步骤1：构建一个赋值图，其中节点表示程序中的表达式，边表示由于赋值而导致的运行时类型的流步骤2：为图中的每个节点计算一个runtime-type属性步骤3：计算图中每个节点的类型安全级别（以及程序中的每个表达式3.2.1步骤1：构建分配图分析的第一步是构建一个赋值图，记录程序中表达式中运行时类型的顺序赋值图中的每个 的vnode表示变量v，nav表示解引用，nav表示对v进行算术运算（产生静态类型τ的值），并且值τ表示类型τ的值，例如，一个常数表达式。对于τv和值τ，τ将是标量C类型：char，int，xoat等，或者是以下之一杨和霍维茨166ττexprAbsObj（expr）0{VALUEzero}分配图中的边Cτ1{VALUEτ}e1=e2n←=−n，n∈AbsObj（e），1 2 1 1n2∈AbsObj（e2）&y{VALUEvalid−ptr}y{y}e1=（τ）cpye2n←=−n，n∈AbsObj（e），1 2 1 1n2∈AbsObj（e2）埃什基{laugh}我的天2 {τy，τz}e1=（τ）cvte2n←cv−t n，n∈AbsObj（e），1 2 1 1n2∈AbsObj（e2）1Cτ是一个非零常数n←ex−t n，n∈AbsObj（e），1 2 1 1n2∈AbsObj（e2）类型τ2表达式yz具有静态类型τe1=（τ）exte2（b）第（1）款（一）图二、初始化分配图的规则以下特殊类型：valid-ptr：一个指针表达式，保证评估到一个有效的地址（分配的内存位置的地址）具有类型valid-ptr。例如，表达式&x的类型为valid-ptr。指针：一个指针表达式，可能计算到一个无效的地址（包括NULL）有类型指针。例如，表达式&x + k有类型指针。zero：一个保证计算结果为0的表达式的类型为零。例如，文字0的类型为零。节点由三种（有向）赋值边连接：转换边（−c→vt）、扩张边（−e→xt）和复制边（−=→）。复制边表示具有形式（τ）cvte的右手侧的赋值，扩展边表示具有形式（τ）exte的右手侧的赋值，而复制边表示不涉及类型转换或涉及形式（τ）cpye的类型转换的赋值。图2（a）显示了从程序表达式到ab-对象的映射AbsObj，而图2（b）给出了向图添加边的规则例如，赋值x=yz给图添加了两条复制边，x←=−y和x←=−z，其中τ是表达式yz的静态type。图3显示了为图1中前面给出的示例代码构建的分配图3.2.2步骤2：计算运行时类型在构建分配图之后，分析为图中的每个节点计算一个运行时类型runtime-type的值形成了图4所示的网格。直观地说，节点n的runtime-type总结了对应于n的表达式在运行时可能具有的类型集。运行时类型的SQL表示一个表达式可以有多个杨和霍维茨167∗⊕⊥数值浮点数==Valueint==fi*p1p1p0+i=P2=+P1Valuevalid−ptr数值零=图3.第三章。图1中示例的分配图见图4。 运行时类型的网格。不兼容运行时类型。图5给出了计算分配图中在图中，pt-set（p）是p的指向集合，而static-type（n）是由n表示的表达式的静态类型。规则T1和T2将每个值τ节点和每个τx节点的运行时类型设置为其静态类型（τ）。规则T3将p节点的运行时类型约束为在网格中不高于p的points-to集中的每个变量的类型规则T4将转换左侧的运行时类型限制为不高于其静态类型;这是安全的，因为RTC插装将检查右侧的类型，并在出现错误时更正运行时标记 规则T5处理扩展边：如果如果扩展赋值是良好类型的，则左侧的运行时类型被限制为不高于其静态类型;否则，左侧的运行时类型被设置为（因为这样的赋值可能会将复杂的RTC标记复制到左侧的镜像中规则T6a和T6b处理赋值边：如果左手边是指针p的解引用（规则T6a），则指向中每个节点的运行时类型Tvalid−ptr零指针char短整型长浮点双精度型='multiply −typed'杨和霍维茨168runtime-type（rtp1）=rtpruntime-type（p2）=指针runtime-type（p1）=valid-ptr runtime-type（f）=validruntime（i）=intruntime-type（p0）=0最终运行时类型% s：条件推断约束T1runtime-type（VALUEτ）=τT2运行时类型（τx）=τT3x∈pt-集（p）runtime-type（x）T4CVTn1←−n2运行时类型（n1）±静态类型（n1）T5extn1←−n2ifruntime-type（n2）=static-type（n2）然后运行时类型（n1）±静态类型（n1）elseruntime-type（n1）=T6a=p←−n2，x∈pt-集（p）runtime-type（x）±runtime-type（n2）T6b。=n1←−n2，n1不属于格式运行时类型（n1）±运行时类型（n2）图五. 计算运行时类型的规则。作业分配边缘推断约束i=1; n = 1;i←=−V值intruntime-type（i）f= 2.3;f←=−V值浮子runtime-type（f）±浮点型p0 =0;p0←=−V值零运行时类型（p0）±零int i;p1←=−V值valid−ptrruntime-type（p1）±valid-ptrpublicintfindDuplicate（int *）;p1←=−V值valid−ptrruntime-type（p1）±valid-ptrp2 = p1 +i;p2←=−p1指针p2←=−i指针运行时类型（p2）±指针运行时类型（p2）±指针*p1 = 4;=int1 ←−value（p-set（p1）={i，f}）运行时类型（RNP1）±runtime-type（i）runtime-type（i）±runtime-type（f）runtime-type（i）±int runtime-type（f）±int见图6。 计算图1中示例的运行时类型p的集合不能高于右边的runtime-type;如果左边是变量v，那么它的runtime-type不能高于右边的runtime-type。图6示出了图1的示例的运行时类型s的计算杨和霍维茨169∗∗∗∗∗∗∗条件属性L1。运行时类型（n）/±静态类型（n）n不安全L2.静态类型（p）=指针，runtime-type（p）/=valid-ptr不安全的L3。不安全，x∈pt-set（p），x/=不安全x跟踪见图7。 确定类型安全属性的规则。3.2.3步骤3：计算类型安全级别一旦计算出运行时类型，图中的每个节点都会根据图7中给出的规则，用一个表示其类型安全级别（不安全或被跟踪）的属性进行注释;在应用规则之后，任何没有被标记为不安全或被跟踪的节点都被认为是安全的。规则L1将运行时类型与其静态类型不兼容的任何节点标记为不安全。 对于规则L2，其运行时类型不是valid-ptr的指针p可能包含无效地址;因此p必须被检测以检查其运行时类型，并且因此被标记为不安全。规则L3标记跟踪的指针p的指向集合中的任何变量，其解引用节点（UMP）是不安全的。回顾图6中的示例，规则L1使f和p1不安全，规则L2使p0和p2不安全，规则L3使i被跟踪。这使得p0，p1和p2是安全的。预计程序中的大部分表达式都是安全的，并且省略这些表达式的类型检查插装将导致RTC工具的显着性能改进请注意，安全变量v的内容可能会被错误的指针p间接访问。但是，在这种情况下，p将被标记为不安全，因此将使用验证指针操作进行检测。由于安全变量没有被检测，v的镜像将被标记为未分配，因此p的检查将触发“访问未分配内存”错误。由于将比以前更多的内存标记为未分配的3.3流量敏感型再配件本节描述了三种对数据流敏感的数据流分析，它们补充了上面定义的对数据流不敏感的类型安全级别分析在第一种情况下，需要进行可能未初始化的分析，以确保上述建议的仪器消除的可靠性。在第二种情况下，never-null-dereference分析允许上述分析将更多形式p的表达式分类为安全的，从而允许消除更多的插装。在第三种情况下，冗余检查分析发现了进一步消除运行时检查的机会，方向与上述方法正交杨和霍维茨170∗接近所有三种分析都可以用标准数据流分析来描述;它们是独立的，可以并行进行。3.3.1可能未初始化分析第3.2节中描述的类型安全级别分析没有考虑未初始化数据的使用，这是RTC工具当前检测到的错误。也就是说，通过消除安全和跟踪位置的所有检测，并将跟踪位置初始化为其静态类型而不是未初始化，RTC工具将不再检测这些位置中未初始化数据的使用。为了解决这个问题，需要进行额外的对流量敏感的分析，以找到不能省略插装的程序点。对于安全或被跟踪的位置x，分析发现x的实例，其中x可能未初始化。这种分析使用uninit（x）形式的数据流事实，这意味着x可能未初始化。事实uninit（x）在声明x的程序点为局部变量xuninit（y）事实到达的赋值x=y生成uninit（x）事实;否则，对x的赋值将杀死uninit（x）。对于通过指针进行的赋值，我们使用已经计算过的指向集合，为了安全起见，我们犯了错误：如果uninit（y）到达了赋值p=y，我们为p的指向集合中的每个v生成uninit（vmeet运算符是set union。跟踪或安全位置x，对于该位置x，uninit（x）fact需要特殊处理• x的声明是用一个声明操作来检测的，该操作将其在镜像中的类型设置为未初始化。• uninit（x）事实所达到的x的每次使用都用一个验证操作。• 每一个可能改变x状态的x唯一保证不改变x状态的定义是uninit（x）在定义之前或之后都不成立的定义，因此，x的所有其他定义都是工具化的3.3.2非空解引用分析第3.2节的方法的另一个缺点是，如果指针p被分配了NULL值，那么指针p被标记为不安全（因此必须完全检测）。这是因为NULL常量映射到值为零的对象，其运行时类型为零。对p的赋值使得p这防止了p 这不会导致RTC工具遗漏任何错误或报告任何虚假错误，但它会增加运行时开销，因为它包括杨和霍维茨171∗∗∗一些不必要的仪器使用另一个对NULL敏感的精化，我们可以找到p的一些实例，其中p保证不包含NULL值，并消除用于检查这些实例的instrumentation。首先，修改运行时类型的格（图4中），使valid-ptrtype在零类型之下，如下所示：第二，图7中的规则L2更改为：条件属性L2.静态类型（p）=指针，runtime-type（p）/±valid-ptr不安全的通过这些修改，对于任何只被分配有效指针值或NULL值的指针p，p将是安全的。(Note如果指针可能被分配了指针算术的结果或其他无效的指针值，则BARP仍将被认为是不安全的。接下来，我们执行另一个数据流分析，以说明这些指针可能的空指针解引用数据流事实null（p）是为每次将NULL值赋值给指针p而生成的。形式p=x的赋值杀死了null（p）。 对于null（p）到达的赋值q=p，生成null（q） 对于通过指针的赋值，我们在可能未初始化的分析中进行了安全的近似。具有空比较条件的谓词的传递函数（例如，p == 0）沿着一个分支传播空（p）事实，并在适当时在另一个分支上杀死它同样，meet运算符是setunion。分析完成后，必须检测null（p）到达的安全解引用p，以执行空指针检查。3.3.3冗余校验分析另一个对带宽敏感的改进是消除冗余检查。当变量v被多次读取而没有插入写入时，运行时检查只需要第一次读取v。这种情况可以用以下数据流分析来检测：T零valid−ptrchar短整型长浮点双精度型指针='multiply −typed'杨和霍维茨172∗=类型τ的检查变量v生成数据流事实检查（v，τ），而包含对v的不安全赋值（其中右侧是不安全的）的节点杀死所有检查（v，τ）事实。对于通过指针进行的赋值，分析必须是安全的：对于p的赋值，如果v在p的在分析之后，如果数据流事实检查（v，τ）到达将被仪表化以检查v的类型τ的另一节点n1，则可以消除在n1处的检查这仅在到达事实检查（v，τ）意味着节点总是可以通过对类型τ的v的另一次检查到达。因此，meet运算符需要设置交集。4评估优化潜力为了估计从类型安全级别分析中可能获得的潜在加速，我们实现了一个简化版本，它将类型安全级别分类如下：首先，每个地址被获取的变量和每个指针解引用都标记为不安全;然后传播不安全的注释（2）如果n1-n2在赋值中，图，并且n2已被标记为不安全，则n1也被标记为不安全）。分析完成后，映射到未标记为不安全的抽象对象的表达式被认为是安全的，并且不使用RTC检查进行检测。这种优化给出了可以通过完整的类型安全级分析消除的检测数量的下限图8显示了[9]中使用的几个基准测试和几个SPEC基准测试的执行时间，这些测试在不同的测试输入上运行了三次给出了未检测的可执行文件（列（a））、未优化的RTC检测的可执行文件（列（b））和使用简单分析的结果优化的RTC检测的可执行文件（列（c））的运行时间。 列（d）和（e）给出了RTC插装的可执行文件相对于未插装的可执行文件的减速因子（例如，对于aes，未优化的RTC检测版本的运行速度比未插装的可执行文件，而优化的RTC插装版本-Sion运行慢11.46倍列（f）给出了优化的RTC可执行文件相对于未优化的RTC可执行文件的加速百分比。平均而言，未优化的RTC可执行文件的运行速度是未检测的可执行文件的执行时间的37.4倍优化的RTC可执行文件运行速度仅为25.1倍，与未优化的RTC可执行文件相比，平均加速率为39.9%这个结果表明，即使是简单的保守分析，我们也可以实现显着的加速。图9显示了简化分析结果的一些细节列（a）给出了每个基准中抽象对象的数量，列（b）给出了被分析标记为不安全的对象的数量总体而言，41.0%的抽象对象被标记为不安全。一方面，这个数字表明，即使是简单的分析也能够分类杨和霍维茨173基准运行时间（ms）减速系数（f）第（1）款选项%加速（一）无RTC（b）第（1）款UnoptRTC（c）第（1）款期权RTC（d）其他事项UnoptRTC（五）期权RTCAES5,195112,37859,54521.6311.4647.01CACM8,319194,06968,09323.338.1864.91CFRAC8,138 438,254301,39153.8537.0331.23马茨穆特4.61032,37517,1597.023.7247.00ppm5,895210,689184,58235.7431.3112.39压缩31,467 976,861 344,68431.0410.9564.72去14,805 793,880587,30653.6239.6726.02Ijpeg2,10276,76132,62036.5215.5257.50李4,599 339,382312,81773.7968.017.83见图8。未检测的可执行文件、未优化的RTC检测的可执行文件和优化的RTC检测的可执行文件的运行时间比较。减速因子与未检测的可执行文件相比基准（一）# abs对象（b）第（1）款# unsafe对象（c）第（1）款#deref对象（d）其他事项%单患者集AES70521414273.65cacm（解码）120301850.00CFRAC178165720952.56马茨穆特122292425.93ppm（编码）8813746586.53压缩5571525962.12去150965783293922.61美元 *Ijpeg141305564221715.11*李540630873833.44** 数字来自[5]。见图9。 简化分析的结果。大多数抽象对象都是安全的。另一方面，仍然有许多被标记为不安全的对象可能被完整的类型安全级别分析标记为安全为了估计这种潜力，我们考虑了如何使用诸如Andersen [1]定义的指向分析来改进我们的结果。请注意，我们的简化分析非常接近使用退化points-to分析执行完整类型安全级别分析的结果，其中每个地址被获取的对象都在每个对象的point-to4图9的列（c）给出了4.只有当所有的取址变量都是同一类型时，这两种分析才不同，其中如果使用退化点集合的完整分析将这些变量分类为安全，杨和霍维茨174∗每个基准中的解引用对象的数量（形式为e的抽象对象，所有这些对象都被简化分析标记为不安全）。平均而言，这些对象占所有抽象对象的15.6%我们强调，一个非平凡的指向分析将为这些解引用对象中的大部分对象提供良好类型的指向集，从而使它们被标记为安全的，并传递导致更多的其他抽象对象被标记为安全的。为了评估这个猜想，我们在基准测试中执行了Andersen这在图9的（d）列中给出（最后三个基准测试的数字平均而言，43.6%的解引用对象具有单例指向集。当一个指针因此，这一列给出了当我们用完整的类型安全级别分析替换简化的分析时，标记为不安全的解引用对象数量潜在减少的最小百分比。 例如，对于AES，解引用对象有单例指向集;因此，我们期望程序中142个解引用对象中至少有73.65%（所有对象都被简化分析标记为不安全）被完整的类型安全级别分析标记为安全，从而将不安全对象的总数从214减少到109。请注意，这个估计过于保守：即使指针的指向集合包含多个对象，如果所有对象都是良好类型的，那么它们都是安全的，甚至更多被简化5相关工作已经提出并开发了许多运行时方法，这些方法在程序执行期间对程序进行仪表化以跟踪辅助信息。Purify [7]和Insure++[14]是两个商业产品，已被证明在运行时成功检测许多类型的内存错误这些工具可能会导致运行时速度减慢20倍或更多;使用类似于这里介绍的技术可能会降低这种速度。Austin等人[2]描述了安全C系统，它跟踪关于每个指针的指示对象的信息，并使用该信息来检测空间（例如，数组越界）和时间（例如，陈旧指针取消引用）访问错误。Patil等人 [15]提出了一种新的方法，通过在阴影中执行辅助信息的跟踪和检查来使这种检查更有效在单独的处理器上处理简单的分析不会。杨和霍维茨175Cyclone[9]和CCured[13]是两个基于C语言的系统，它们试图在保持语言的低级控制的同时注入某种程度的安全性Cyclone语言包含了不同类型的指针的定义和不同的安全限制;“不安全的”指针解引用是通过运行时检查来检测的要将现有的C程序移植到Cyclone中，程序员必须手动将C指针转换为适当类型的Cyclone指针以实现最佳性能;分析自动将指针分类到适当的安全级别，类似于本文中提出的类型安全级别分析，将使移植现有的C代码变得更容易，从而鼓励更多地使用这种新语言。CCured还包括对错误指针取消引用的运行时检查。CCured此外，CCured可能过于严格（即，某些有效的程序行为（例如，将堆栈变量的地址存储在全局变量中，或者将指针值存储在整数中、将其强制转换并解引用它）将导致运行时检查失败）。为了减少运行时检查的开销，CCured使用类型推断方案来识别尽可能多的安全指针和序列最大限度地减少插装操作的数量因此，它们的类型推断的目标然而，他们的类型推理方案不如我们提出的分析精确：他们有效地将指向集合分组为等价类（本着Steensgaard的指向分析[18]的精神），而我们的分析考虑了尽管如此，他们仍然能够显着提高仪表化CCured程序的性能，从未优化的6-20倍减速到使用类型推理优化的1 - 2倍减速这表明我们的分析有可能实现可比或更好的性能改进。使用运行时检查来强制执行安全属性，以及用于消除不必要的检查以提高性能的技术已经在其他编程语言和环境中使用。动态类型语言（如LISP和Scheme）的实现需要维护运行时信息，以执行作为语言语义一部分的运行时类型检查为了提高这种系统的性能，Henglein [8]提出了一种基于类型推理的有效方法Java语言需要执行潜在的昂贵的运行时检查，例如数组边界检查，以强制执行该语言所保证的安全属性。在Java和其他安全语言中消除冗余和不必要的数组边界检查已经得到了广泛的研究[19，12，6，3，4，11]。杨和霍维茨1766结论我们已经提出了一些技术，以减少运行时开销的仪器添加到C程序的类型检查工具。在3.2节中，我们定义了一个对数据流不敏感的类型安全级别分析，它将程序中的每个表达式标记为安全、不安全或被跟踪。该分析的结果与第3.3.1节中定义的可能未初始化分析的结果结合使用，可用于删除安全和跟踪表达式的大部分注释。在第3.3.2节和第3.3.3节中提供了两项进一步的低敏感性分析，以消除更多的仪器。第一个，never-null-dereference分析，消除了对可以静态确定为never为null的指针的检查。第二种方法识别出冗余的检查，这些检查也可以消除为了衡量这些优化所带来的潜在好处，我们实现了一个简化版本的类型安全级别分析，并给出了实验结果，表明RTC工具的性能类似的想法可以适用于其他涉及通过运行时插装检测错误的工具引用[1] L. O.安徒生程序分析和C语言的专门化。博士论文，哥本哈根大学，DIKU，1994年5月。(DIKU第94/19号报告）。[2] T. Austin，S