面向Java的抽象解释框架及实现：静态分析器的设计与实现

理论计算机科学电子札记131（2005）85-98www.elsevier.com/locate/entcs面向Java的完整静态分析器：一个抽象解释框架及其实现伊莎贝尔·波利特1那慕尔大学Baudouin Le Charlier2Universit'eCatholiquedeLouvain摘要我们提出了一个抽象的解释框架的一个子集的Java（无并发）。该框架使用了一个结构化的抽象域，其具体化功能是抽象和具体位置之间的关系参数化。 当结构上不相容的对象在给定的程序点上可能被同一个变量引用时，结构信息被丢弃，并被关于对象的近似信息所取代（我们的演示集中在类型信息上）。简单的结构信息允许进行精确的过程内分析，但在从方法调用返回时会很快丢失。为了克服这一限制，引入了关系结构信息，这使得精确的过程间分析，而无需诉诸内联。本文件概述了这项工作。我们描述了部分标准和抽象语义;然后，我们简要解释了我们的实现所使用的定点算法;最后，我们提供了小程序的实验结果关键词：抽象解释，Java，类型分析，指针分析，程序验证，程序专门化。1电子邮件：ipo@info.fundp.ac.be2电 子 邮件地址：blc@info.ucl.ac.be1571-0661 © 2005由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2005.01.02586I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）85介绍Java的静态分析有着广泛的应用然而，一个主要的问题是分析本身的正确性，特别是当它用于优化编译器时。但是，设计分析并证明其正确性通常是繁琐且容易出错的。因此，合理的尝试是设计一个我们的工作是对这样一个“通用框架”的贡献我们将我们的分析限制在语言的一个（部分任意的）子集。一方面，这个子集足够代表主要的Java特性，另一方面，它又足够小，可以在第一种方法中完全处理。并发性是我们要消除的主要Java特性。这个方面非常重要，但与我们还假设完整的源代码是可用的，暂时忽略动态类加载的问题（参见例如：[17]）。我们应用抽象解释方法如下：我们定义了一个简单的标准语义，抽象域和这些域上的抽象我们最终使用后定点算法来计算抽象语义（的相关部分）。我们的抽象域包含结构信息，与标准域（由环境和存储组成）非常相似。抽象位置可以用各种信息注释，使框架通用。在抽象层次上的结构共享可以用几种不同的方式来解释，在标准层次上，产生了抽象域的三种变体3。分析的结果是描述抽象输入/输出状态的表，在实际标准执行过程中可能出现的方法和构造函数调用。这样的表类似于（并且允许人们轻松地构建）整个程序的（精确）调用图[12，26]。本文概述了这项工作，由五个主要部分组成。第1节提供了标准语义的简要概述。第2节描述了抽象域。第三节简述了抽象语义定义第4节详细介绍了小程序的分析结果。第五节讨论了相关的工作。[3]对抽象域的初步介绍见[20]。所有的技术定义都可以在[19]中找到I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）8587public classT{ public void inc（）;}class IntT extendsT{ int n;int n（int v）{int n =v;}void inc（）{int n= n+ 1;}}类CoupleT扩展T { T v1;Tv2;CoupleT（T p1，Tp2）{ v1 = p1; v2 =p2;}public void run（）{v1.inc（）; v2.inc（）;}}public int findDuplicate（inti，intj）{newIntT（i，j）;}}class TList {Tval; TList next;public void run（）{TList（T v，TListtail） { val=v;next=tail;}void permut（）{TList tmp = next; next= tmp.next; tmp.next =next.next; next.next =tmp;}public void run（）{TList aux = new TList（v，next）; next = aux;}}类主{void main（）{TListl= new TList（）;l.add（new IntT（1））;l.add（new IntT（3））; TList one=l.next; TList two=l.next.next; l.swap（）;l.next.val= new CoupleInt（1，2）; one.val.inc（）; two.val.inc（）;}}Fig. 1. Swap程序：论文1目标语言和标准（定点）语义我们专注于一个有限的Java子集，包含主要的面向对象的语言功能，如继承和虚拟方法调用。为了便于管理，我们的子语言包含了有限数量的基本类型和控制语句。我们认为，这些限制大多只是语法上的。然而，有一些主要的限制：我们不处理并发性，目前执行整个程序分析。我们也不解决本地方法或反射问题。（图1描绘了目标子集的小程序。通常情况下，我们不会直接分析源代码，而是使用一种中间表示，即Java字节码的在这种表示中，我们称之为LAS，ex-tables被简化（它们不包含方法或构造函数调用）和类型化，所有默认规则都被显式转换。Java-LAS编译器引入必要的内部变量并验证类型检查规则。程序的语义映射每个块标识符，即，将每个方法或构造函数签名转换为相应的存储转换。更正式地说，程序的语义是块环境集合的变换τ[[]nvB=→（×o→/×o+ ×o×al），由Theset的方法和构造函数引入O来处理一个简单的输入输出设备，并由以下方程定义局部存储器集合，我们称之为标准域ase = calar +{null，nonInit}，Al=ASE+OC，nst=×（ield→/al），ield=×、NV=/→al，tore=oc→/nst= t×tore。88I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）85一个本地商店大致由一个环境和一个商店组成。该函数将每个本地标识符（变量或参数）映射到其值，并将每个位置（地址实例）存储到实例。图2提供了本地存储的示例。d1=（e，s），e={（this，0），（tmp，1）}，s={（0，（TList，f0）），（1，（TList，f1）），（2，（TList，f2）），（3，（IntT，f3）），（4，（IntT，f4））}f0={（（TList， next），2），（（TList， val），null）}，f1={（（TList， next），null），（（TList， val），3）}f2={（（TList， next），1），（（TList， val），4）}f3={（（IntT，），int1）}，f4={（（IntT，），int3）}图二.的元素，对应于方法TList.swap（）及其图形表示2抽象领域我们使用几个抽象域，即集合的几个抽象。所有这些域都是结构域：它们保留堆结构的部分视图。当一个变量或字段可以具体地表示不同类型的值时，抽象类型被引入抽象图中。这些抽象类型属于参数抽象域，它可以表达各种信息（尽管我们目前主要关注类型信息）。这些考虑导致了一个抽象域，它看起来与标准域非常相似。它的结构由以下方程定义al=\{n}+oc，nst=×（ield→/al），NV为→/托雷=oc→/nst，=托雷+{}，其中该组表示参数抽象域。的语义通过具体化函数来具体化，具体化函数依赖于标准局部存储和抽象局部存储之间的结构态射我们实际上提出了三种变体的具体化功能的基础上不同的要求的基础态射。这些变体导致了三个抽象域，这三个抽象域通过它们可以表达的关于实例共享的信息而不同。(i) 在精确域中，结构信息是精确的（只要结构保持不变）。该领域是最精确的抽象标准领域的单个元素，但它失去了大部分的结构信息时，抽象元素与不同的实例共享。(ii) 在区别域中，我们可以表示实例之间的区别，但不一定共享。I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）85891212(iii) 共享域在某种意义上是区别域的在最后一个域中，我们能够表示实例的确实共享，但不能表示实例的独特性。抽象本地存储区抽象本地存储区图三. 抽象局部状态图3描绘了抽象域的变体的两个元素，这两个元素都抽象图2的本地存储。在d的情况下，参数domain仅提供类型信息：tmp.next为null或表示类型TList，我们对www.example.com的值tmp.next.next。 在精确域，这表示一个结构开始至少有三个不同的细胞和变量tmp指出这个结构的第三个细胞。在区别域中，这也表示一个 在共享域中，单元格2和1可以代表相同的具体单元格，但我们确信tmp和next.next共享。 d使用的参数域更复杂。它特别包含一个可达性组件，它提供关于所有可达值的信息：tmp.next为空或表示TList的一个实例，该实例不同于图的其他实例，所有从字段tmp.next可达的实例都是TList类型或IntT类型，而且，它们不同于第一个抽象实例所表示的实例。3抽象语义程序的抽象语义是一组抽象块环境转换的后定点NVB为→（→/+的×al）。这种转换的定义依赖于抽象的局部转换函数[[. ]]：→nvB→×→/1998年，×），其表示假定的抽象块环境内的每个语句的语义。对于过程内分析，此函数的定义大致对应于上的抽象操作的设计。90I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）851012对于过程间分析，由于缺乏抽象状态之间的关系信息，直接使用抽象域会导致从调用返回时丢失大部分结构信息。 让我们说明这个问题有一个简单的例子：我们想执行调用l.swap（），在图1的方法Main.main（）中，在图4的抽象本地存储d中。 此外，抽象块环境映射对应的条目D到本地存储器D本身。 事实上，提供的信息只是0 0形状信息，并且我们不知道例如D的位置9是否表示呼叫开始和结束时的相同位置。它实际上可以表示d的位置7或9，或者在电话 所以，我们在呼叫情况d其中一个和两个完全失去了。为了克服这个问题，我们通过复制参数和字段来引入调用的开始和结束状态之间的关系信息。当开始调用时，我们复制所有字段值。这些副本在调用期间无法具体修改。因此，当从调用返回时，我们可以在调用之前的值和调用之后的副本的值之间执行一种统一。图5通过重新访问图4的示例说明了这个想法。d：在调用l.swap（）之前d：d块中的输入/输出：调用1 0 2环境图四、返回没有关系信息的调用（在精确域中）4抽象语义计算为了计算抽象语义，我们在程序间级别使用[14]中提出的通用后定点算法，在程序内级别与经典的单变量或多变量算法相结合。过程间算法为所有可能执行的方法和构造函数构建一个抽象输入/输出状态表。该表是对抽象语义的部分描述，由对初始调用的分析驱动。I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）8591在块环境中调用l.swap（）之前输入块环境的输出调用图五、返回带有关系信息的调用（在精确域中）5结果我们的实现提供了一个图形界面来导航通过后定点算法产生的部分表。它还允许我们可视化每个程序点的抽象状态。我们为两个小程序展示了这些图形结果的一部分：第一个是在一个铸造验证光学中，第二个是作为程序专业化的案例图6的类Stack实现了通用堆栈。Job类的方法在一个简化的上下文中模拟了Java中管理通用数据结构的经典方式。方法Job.treatInt（）将方法Int.inc（）应用于存储在堆栈上的所有对象。这个方法假设所有存储的对象都是Int的实例。方法Job.memorizeInt（）构建一个满足假设的堆栈，而方法Job.memorize（）构建一个可能还包含CoupleInt实例的堆栈。 我们解决了在不同的执行上下文中在方法Job.treatInt（）中验证（或无效）强制转换的问题。我们首先考虑对方法Main.main1（）的分析。图7的快照1显示了表中 Job.treatInt （ ） 方 法 的 唯 一 条 目 。输 入 情 况 描 述 了 由Job.memorizeInt（）方法构建的堆栈，而输出描述了一个空堆栈。快照2描述了在语句v=（Int）var.pop（）. 我们可以从映射到内部5本节中提供的结果是使用分析器的变体获得的，这些变体利用关系信息并使用精确域。参数域包括可达性组件。92I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）85抽象类Object {}class Int extendsObject{ int n;Int n（intv）{int n =v;}void inc（）{int n = n +1;}}类Couple扩展Object{ Objectp1; Object p2;Couple（Object v1，Objectv2）{ p1=v1; p2=v2;}}public int findDuplicate（inti，int j）{public void run（）{Stack aux = new Stack（）; aux.val = v;aux.next = next;next = aux;}public void run（）{Object res= next.val;next= next.next;return res;}}class Job{ Stackvar;作业（堆栈% s）{ var= % s;}public intfindDuplicate（）{int findDuplicate（IO.read）;intfindDuplicate（）{n =IO.read（）;var.push（new Int（n））;memorizeInt（）;}}public void run（）{publicintfindDuplicate（）;int IO.read（）{n =IO.read（）;var.push（new Int（n））; memorize（）;}否则{int n = IO.read（）;public void run（）{Stack s= new Stack（）;Jobj= new Job（s）;j.memorizeInt（）;j.treatInt（）;}public void run（）{Stack s= new Stack（）;Jobj= new Job（s）;j.memorize（）;public void run（）;}}public void translate（i，j）; void translate（i，j）{}if（！（var.next== null））{} Int v=（Int）var.pop（）;v.inc）;var.push（new CoupleInt（n，n））;memorize（）;}}类堆栈{Object val; Stack next;return（）;}}}见图6。 Stack计划变量#0，表示调用var.pop（）返回的值，表示强制转换肯定有效。然而，分析不是全局最优的，因为分析器将产生调用v.inc（）的可能空引用的警报，尽管这样的错误实际上永远不会发生。这来自传递组件的结果对于限定深度的堆叠变得最优现在让我们来分析方法Main.main3（）。 快照3描述了在语句v =（Int）var.pop（）中进行强制转换检查之前的抽象存储。这一次，映射到内部变量#0的值不允许验证强制转换，因为它可以表示Int的实例或CoupleInt的实例。然后可以发出警告。图8中的List类实现了对同构类属列表的读写（在IO类实现的简单输入输出设备上）。它有几个扩展：IntList实现整数列表，L2List列表（和IntL2List列表的整数列表），StarListLisp类列表（和IntStarListLisp类列表的基本整数值）。在优化目标中，我们可以尝试为具体类IntList、IntL2List 和 IntStarList 专 门 化 方 法 List.readList （ ） 和 List.writeList（）。 为了实现这一目标，我们特别需要精确的类型信息-关于调用l.getCell（）（在List.readList（）中）和p.writeCell（）（在List.writeList（）中）的目标的信息。我们只讨论整数列表的列表的两种方法的特殊化。在其他情况下，结果是最佳的。图9的快照1提供了为readList计算的抽象语义的图形视图(when 分析方法List.main（））。 快照2描述了本地状态I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）8593快照1：Job.treatInt（）的方法表（对于Main.main1（）程序）快照二：Job.treatInt（ ） 的 详 细信 息 （ 对 于 Main.main1（）程序）快照3：Job.treatInt（ ） 的 详 细信 息 （ 对 于 Main.main3（）程序）见图7。 堆栈程序的快照抽象类List { List next;public void getCell（）;public void getCell（）;public void writeCell（）;List newCell（Listtail）{ Listl= newCell（）; l.next=tail;returnl;}void main（）{List l=new IntList（）.readList（）; l.writeList（）;return new IntL2List（）.readList（）;l.writeList（）;int n =newIntStarList（）.readList（）; l.writeList（）;}}int getInfo（）; int getInfo（）;public void run（）{if（）{elem =readList（）;}else{getInfo（）;}}public void println（）{if（elem==null）{ writeInfo（）; } else { elem.writeList（）;}public void run（）{Strings= new String（null）;class IntList扩展List {}int n;}public int findDuplicate（） {inti= IO.read; intn= 1;public intfindDuplicate（i）List p = newCell（l）;voidgetCell（）{info=IO.read（）;}void writeCell（）{IO.write（info）;}}public class IntL2List extends L2List {public void run（）{IntL2Listl= new IntL2List（）;l.info= new IntList（）; returnl;l=p;i= i+1;}return l;抽象类L2 List扩展List{}List info;}void getCell（）{int n. getsum（）;}}虚空writeList（）{ List p = next;while（！（p==null））{println（）;p.next;}}虚空getString（）;}}抽象类StarList扩展List{ List elem;boolean isList（）{intn = IO.read（）; returnn = 0;}public class Int {int info;void getInfo（）{ info = IO.read（）;}public void run（）{returnnew IntStarList（）;}void writeInfo（）{ IO.write（info）;}}见图8。 列表程序94I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）85快照1：readList（）快照2：分析of readList（）用于整数快照3：分析的getCell（），用于整数见图9。 列表程序的快照在方法readList中调用l.getCell（）之前，在这种情况下，l的类型是精确的。因此，动态调用可以被静态调用替换，并且可以进一步内联。快照3详细介绍了对该调用的方法环境中的条目的分析。同样，this.info的类型是完全已知的，调用可以是静态的和内联的。所以我们有派生了足够的类型信息，以获得完全专用的方法（具有两个嵌套循环）。有 一 种 情 况 下， 结 果 不 是 完 全 最 优 的 ： 对 于 方法writeList中的 调 用p.writeCell（），我们只能推导出p是IntList或IntL2List类型。这一结果可以改进，对抽 象域进行 了一些小 的修改 。例如， 我们可以 使用一 个改进版 本的Distinctness Domain，它允许OR节点处理null值。I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）85956相关工作我们在本文中介绍的工作忠实地遵循抽象解释方法[9，8，10]，我们相信这足以掌握为大型面向对象语言（如Java）设计正确和通用框架的复杂性。更具体地说，我们重用了在GAIA设计中被证明成功的几个想法，GAIA是一个用于Prolog静态分析的通用系统 [15]。GAIA系统最初受到[3]的启发，在抽象域（抽象替换集）上参数化，并且已经实例化到许多不同的抽象域。我们的结构抽象域与域模式[18，15]和对位相关度量域Pat（R），它通过允许增强任何具有结构成分的抽象域R[6，7]。我们的工作与GAIA之间有两个主要的区别：Java是一种具有破坏性更新的命令式语言，并且它是面向对象的。为了处理动态分派，我们确定哪些方法可以实际执行，并抽象执行所有方法。最大的困难是破坏性更新，特别是因为它使过程间分析更加困难：在逻辑编程中，在预测调用之前存在的数据结构不能被破坏性修改;它们只能被更多地实例化。因此，调用的返回可以通过调用的结果与调用之前的抽象状态的（抽象）统一来实现（即，向后统一）。在命令式编程中，“传递”给调用的数据结构可能会被完全修改或替换为在调用期间构建的其他新结构。 尽管如此，我们对这个问题的解决方案也受到了逻辑编程的启发：添加关系信息，我们显式地引入了定义相等的数据结构部分（即，调用之前的字段值等于调用之后的字段副本值）;因此，可以将字段在面向对象的编程领域，许多“具体”类型推断算法已经被设计为用静态方法调用替换虚拟方法调用，并且更一般地，专门化面向对象的程序（参见，例如，[1、4、12、16、23、26]）。重点是在分析速度和精度之间取得最佳平衡。由于引用的工作都没有使用结构信息，它们先验地不如我们的精确。需要进一步的工作，看看我们的方法是否适用于大型Java程序。我们预见，加宽操作将使我们能够实现几乎任何理想的交易，尽管选择正确的加宽操作并不简单。我们的建议也与指针分析有相似之处，但我们的结构域并没有被设计为实现有效的点分析。96I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）85分析[2，24，25]或精确的形状分析[5，11，13，22，21]。它们主要用于进行任何分析（例如，类型分析）同样精确，有或没有诉诸（合理的形式）内联。我们已经验证了这在几个例子中是有效的，比如我们的Swap程序。 此外，它可以集成各种形式的指针分析到我们的结构域的基础上的抽象位置。有两种可能的AP-改进指针分析的结构域。我们要么扩展结构域本身，使其与形状分析域（如[5，11，13，22]）相当，要么通过使形状分析作用于抽象位置而不是程序变量来构建类似于Pat（R）[6，7结论和今后的工作我们已经为Java的一个子集提出了一个抽象的解释框架。该框架使用结构抽象域，这使得有可能扩展框架与额外的分析，它提供了一个精确的治疗过程间的分析，通过使用关系信息。我们认为这个框架是迈向完全令人满意的Java抽象解释框架的第一步。所需的改进包括处理完整的Java语言，进一步参数化抽象域，以及处理不完整的源代码。因此，这项工作的贡献是为一个完整的系统提供语义基础，因为许多改进将相当于添加新的但类似的定义，并调整抽象域和算法。在不久的将来，我们计划沿着两条主线开展工作。一方面，我们将研究结构抽象域的变体，以在不同的情况下（例如，优化与验证）。另一方面，我们将扩展框架到完整的Java语言（仍然没有并发性，但提供分析不完整代码）。引用[1] Agesen，O.，基于约束的类型推断和参数多态性，在：B。Le Charlier，editor，Proceedings ofthe First International Symposium on Static Analysis（SAS[2] 安德森湖“程序分析和专业化的C编程语言，”博士。论文，哥本哈根大学，DIKU（1994年），（DIKU报告94/19）。[3] Bruynooghe，M.，逻辑程序抽象解释的实用框架，Journal of Logic Programming10（1991），pp. 91比124I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）8597[4] 钱伯斯，C.，J. Dean和D. Grove，面向对象语言的全程序优化，技术报告96[5] Chase，D. R.，M. Wegman和F. K.杨文，《指针与结构的分析》，载于《计算机程序[6] Cortesi ， A.， B. Le Charlier 和 P. Van Hentenryck ， 逻 辑编 程的 抽象 域组 合， 第21 届 ACMSIGPLAN-SIGACT编程语言原理研讨会论文集（POPL'94），波特兰，俄勒冈州，1994年[7] Cortesi，A.，B. Le Charlier和P. Van Hentenryck，逻辑编程的抽象域组合：开放产品和通用模式构造，计算机编程科学38（127比71[8] Cousot，P. and R. Cousot，Abstract interpretation：A unified lattice model for static analysisof programs by construction or approximation of fixpoints，in：Conference Record of FourthACM Symposium on Programming Languages（POPL238-252.[9] Cousot ， P. and R. Cousot ， Systematic Design of Program Analysis Framework ， in ：Conference Record of Sixth ACM Symposium on Programming Languages（POPL269-282.[10] Cousot ， P. and R. Cousot ， Abstract interpretation frameworks ， Journal of Logic andComputation2（4）（1992），pp. 511-547[11] 多尔，N.，M. Rodeh和M.陈文辉，链接表的清洁性检验，第七届国际静态分析研讨会论文集（SAS[12] Grove，D.，G. DeFouw，J. Dean和G. Chambers，Call graph construction in object-orientedlanguages，in：Proceedings of the Conference on Object-oriented Programming，Systems，Languages and Applications Static Analysis（OOPSLA[13] 琼斯，N。和S. Muchnick，一种跨过程数据流分析和递归结构程序的灵活方法，在：程序设计语言原理ACM研讨会论文集（POPL[14] 勒沙尔利耶湾P. Van Hentenryck，A general top-down fixpoint algorithm（revised version），Technical Report RR-93-022 ， Institute of Computer Science ， University of Namur ，Belgium（also Brown University）（1993）。[15] 勒沙尔利耶湾Van Hentenryck，Experimental Evaluation of a Generic Abstract InterpretationAlgorithm for Prolog，ACM Transactions on Programming Languages and Systems（TOPLAS）16（1994），pp. 35-101[16] Lerner ， S. ， D. Grove 和 G. Chambers ， Composing data datashew analysis andtransformations，in：Proceedings of the ACM[17] Logozzo，F.，面向对象语言的类级模块化分析，收录于：第10届静态分析研讨会论文集（SAS[18] Musummbu，K. ，“I n t e r p r e t a t io n A b t r a t e d e s Prolog，“Ph. D. thesis，InstituteofComputer Science，University of Namur，Belgium（1990），in French.[19] 波利特岛， 论文，Universit′eCatholiquedeLouvai n，Belgiumm，http：//www. 在信息。ucl.ac. b/英/法/印/欧（2004年）。[20] 波利特岛，B. Le Charlier和A. Cortesi，Distinctness and Sharing Domains for Static Analysis ofJava Programs ， in ： J.Lindskov Knudsen ， 编 辑 ， Proceedings of the 15 th EuropeanConference on Object-Oriented Programming（ECOOP98I. 波莱湾Le Charlier/Electronic Notes in Theoretical Computer Science 131（2005）85[21] Sagiv，M.，T. 代表和R。Wilhelm，通过3值逻辑的参数形状分析，在：第26届ACM SIGPLAN-SIGACT编程语言原理研讨会（POPL'99）会议记录[22] Sagiv ， M. ， T. 代 表 和 R 。 Wilhem ， Solving shape-analysis problems in languages withdestructive updating ， ACM Transactions on Programming Languages and Systems20（1998），pp. 一比五十[23] 舒尔茨大学，J. Lawall，C. Consel和G. Muller，Towards automatic specialization of Javaprograms，in：Proceedings of ECOOP367-390.[24] Shapiro，M.和S. Horwitz，指针分析精度的影响，第四届国际静态分析研讨会论文集（SAS16比34[25] Steensgaard，B.，在几乎线性时间内的指向分析，在：程序设计语言原理的ACM研讨会论文集，1996年。[26] Tip，F.和J. Palsberg，Scalable propagation-based call graph construction algorithms，in：Proceedings of the Conference on Object-Oriented Programming，Systems，Languages andApplications（OOPSLA