Java字节码分析及内联实现静态和动态分析的研究

理论计算机科学电子笔记141（2005）109-128www.elsevier.com/locate/entcs子程序内联和字节码抽象实现静态和动态分析西里尔·阿尔托瑞士苏黎世联邦理工学院计算机系统研究所阿明·比尔奥地利林茨约翰内斯开普勒大学形式模型与验证研究所摘要在Java字节码中，内部方法子例程被用来表示“最终”块中的代码。在方法中使用这种多态子例程使得字节码分析非常困难。幸运的是，这样的子程序可以通过重新编译或内联来消除。内联是显而易见的选择，因为它不需要更改编译器或访问源代码。它还允许转换遗留字节码。然而，嵌套的，不连续的子程序与重叠的异常处理程序的组合构成了一个困难的挑战。本文提出了一种算法，成功地解决了所有这些问题，而不产生超连续的指令。此外，内联可以与字节码简化相结合，使用抽象字节码。我们将展示如何将这种抽象扩展到完整的指令集，以及它如何简化静态和动态分析。保留字：Java字节码分析，内联，静态分析，动态分析1介绍Java [12]是一种流行的面向对象的多线程编程语言。Java程序的验证变得越来越重要。一般来说，用Java语言编写的程序被编译成Java字节码，这是一种可以由Java虚拟机（VM）执行的机器可读格式[16]。在执行之前，这样的字节码必须通过一个称为字节码验证的格式良好性测试，该测试应该允许常规Java程序通过，但也必须确保恶意字节码，这可以规避1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.02.034C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109110安全措施无法执行。Java编程语言包括方法，这些方法以字节码的形式表示然而，字节码也包含子程序，方法作用域内的函数一个特殊的jump-to-subroutine （jsr ）指 令将返回地址保存 到堆栈中。 从子例程返回（ret）指令从子例程返回，将包含返回地址的寄存器作为参数。这个人工制品最初是为了节省字节码的空间而设计的，但它有三个不幸的后果：(i) 它引入了源语言中不直接存在的功能。(ii) 使用jsr将返回地址存储在堆栈上和从寄存器（而不是堆栈）中检索返回地址的不对称性极大地使代码分析复杂化。(iii) 子例程可以读写在整个方法中可见的局部变量，这需要区分不同的调用上下文。Stärk等人[21]观察到了第二和第三个效应，并给出了许多Sun的字节码验证器多年来无法处理的例子。子程序的增加使得字节码验证变得更加复杂，因为验证器必须确保没有ret指令返回到错误的地址，这将危及Java安全性[16，21]。因此，子例程消除是简化字节码的一步，可以在未来的JVM中使用，使它们能够免除验证子例程的挑战正确地消除子程序是非常困难的，特别是嵌套的子程序，正如本文所示。此外，考虑整个字节码指令集会使分析器非常麻烦，因为它包含200多条指令，其中许多是变体基本指令的主参数被硬编码用于空间优化[16]。因此，我们引入了一个基于寄存器的抽象字节码版本，它来自[21]。通过引入寄存器，我们消除了没有显式指令参数的问题，进一步简化了分析JNuke是一个静态和动态分析Java程序的框架[2，5]。动态分析，包括运行时验证[1]和模型检查[13]，与经典方法（如定理证明[10]）相比，具有提供精确信息的关键优势。JNuke的核心是它的VM。其基于事件的运行时验证API可作为各种运行时算法的平台，包括检测高级数据竞争[4]和陈旧值错误[3]。最近，JNuke已经扩展了静态分析[2]，它通常比动态分析更快，但精度较低，近似于可能的C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109111方 案 国 家 。 “Classical” static analysis uses a graph representation of theprogram to calculate a fix point [目标是重用静态和动态分析的分析逻辑。这是通过无图数据流分析实现的[20]，其中静态分析的结构类似于VM，但允许非确定性，并在其抽象解释中使用状态集而不是单个状态[2]。字节码是选择的输入格式，因为它允许验证Java程序而不需要源代码。最近，甚至已经开发了其他语言的Java字节码编译器，例如Ada的jgnat[7]或Scheme的kawa[6]。然而，字节码子程序及其非常大的基于堆栈的指令集使得静态和动态分析变得困难。JNuke消除了子程序并简化了字节码指令集。第2节概述了Java编译和异常处理程序的处理内联算法在第3节中给出。第4节描述了到抽象的、基于寄存器的字节码的转换。第5节描述了我们的工作和相关项目之间的差异，第6节总结。2使用字节码子例程的2.1Java字节码Java字节码[16]是一种类似汇编语言的语言，由可以将控制转移到另一条指令的指令组成，访问局部变量并操作（固定高度）堆栈。每条指令都有一个唯一的地址或代码索引。表1描述了本文中提到的说明在这个表中，r表示寄存器或局部变量，j表示整数值（可能为负），a表示地址。地址a处的指令将被表示为code（a），而该函数的逆函数index（ins）返回地址一个指令。堆栈的最大高度在编译时确定。指令参数的类型必须正确。寄存器索引必须位于静态确定的范围内。这些条件由任何行为良好的Java编译器确保，并且必须在字节码验证期间由Java虚拟机（VM）的类加载器进行验证[16]，这里没有讨论其全部范围。2.2异常处理程序和Finally块Java语言包含异常，通常用于通知错误条件的构造。一个异常超级程序在正常控制流程中，在堆栈上创建一个新的异常对象e，并将控制转移到异常处理程序。C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109112指令描述负载r将寄存器r中的引用或地址压入堆栈。伊罗德河将一个整数从寄存器r压入堆栈。阿斯托雷河返回栈顶元素，一个引用或地址，将其存储在寄存器r中。伊斯托雷河返回栈顶元素，一个整数，将其存储在寄存器r中。转到a将控制转移到。IINCR J将寄存器r递增j。伊法内阿从堆栈中取出整数j;如果j不为0，则将控制转移到a。JSRA推送当前地址的后继地址并将控制权转移给A。保留R从寄存器r加载地址a并将控制转移到a。阿斯洛从堆栈中删除引用r返回从当前方法返回，放弃堆栈和所有局部变量。表1Java字节码指令的子集。可以“捕获”异常的范围如果这样的异常e在运行时发生，执行将在相应的catch块（如果存在）处继续，该catch块处理异常程序行为。无论是否发生异常，都会执行可选的finally块，但总是在try和catch块执行因此，finally块的存在会产生一个二元场景：在一种情况下，发生异常，需要同时执行catch和finally块。在没有异常的情况下，或者如果发生的异常不在catch块的类型指定范围内，则只需执行finally块因此，需要一个默认的异常处理程序来捕获所有未手动捕获的异常。在以下文本中，小写字母表示单个值。等宽大写字母，如C将表示控制转移目标（静态已知）。斜体的大写字母如I表示值的集合或范围。在Java字节码中，异常处理程序h（t，I，C）由其类型t，范围I定义，interval[iα，iω]，1和处理程序代码。 每当类型t或其亚型发生在I内，控制转移到C。 如果多个处理程序对于范围I，选择第一个匹配处理程序。如果对于一个指令索引a，存在一个处理程序h，其中a位于它的范围I内，我们说h保护a：protects（h，a）Particia∈I（h）。正如Java语言[12]所规定的那样，在F处的finally块总是必须无论是否发生异常，都必须执行。这是通过为默认处理程序hd（tany，Id，F）使用未指定类型tany来实现的。如果catch块是1在一个例子Javac l as文件中，han rrange被定义为s[iα，iω[且不包括区间iω的索引。这只是一个执行问题。为了简单起见，本文假设处理程序范围被转换为反映上述定义。C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109113在try/catch/finally结构中，catch子句指定的异常处理程序hJ（tJ，IJ，CJ）优先于默认处理程序hd。CJ处的代码仅在抛出与类型tJ兼容的异常时执行。在这种情况下，在执行catch块之后，通常用于跳转到F处的finally块。 因为这种机制是通过h d捕获任何异常的直接增强，所以这不会给子例程内联和验证带来新的问题。 因此，本文不再进一步讨论catch 块。2.3Finally块和子例程finally块可以在两种模式下执行：要么异常过早终止其try块，要么不抛出异常。因此，唯一的区别是块执行的这导致了共享finally块的公共代码的想法。因此，Java编译器通常使用子例程实现finally块。2子程序S是一个类似函数的代码块。在本文中，S将指整个子程序，而S表示S的第一条指令的地址。子例程可以由特殊的跳转到子例程指令jsr调用，该指令将当前地址的后继地址压入堆栈。子例程首先必须将该地址存储在寄存器r中，随后通过从子例程返回指令ret从寄存器r中检索该地址。寄存器r不能用于计算。Java编译器通常将整个finally块转换为子例程。这个子例程在需要的时候被调用：在try块的正常执行之后，在异常已经被catch处理之后，或者当一个未被捕获的异常发生时。图1中的示例说明了这一点。 处理程序h（t，R，C）保护的范围R由垂直线标记。C处的处理程序代码首先将异常引用存储在局部变量e中。然后，它在S.在执行S之后，从变量e加载异常引用，并使用athrow指令将其抛出给调用者。如果没有异常发生，则在try块之后调用S，然后在X处继续执行。请注意，子例程块位于整个方法内部，需要一个goto指令在try块之后的X处继续执行在控制流程图中，S可以被视为一个简单的代码块，可以从顶层调用2Sun然而，为了确保与遗留字节码的向后兼容性，字节码验证器仍然必须处理允许正确子例程的复杂性。这强调了子程序消除的必要性，因为商业库通常不使用最新的可用编译器，但仍然可以与它们编译的程序结合使用本文为在遗留字节码中内联子例程奠定了基础，允许未来VM中的字节码验证器忽略这个问题。C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109114||iinc i1|（h）|jsr SpublicintfindDuplicate（inti）{尝试{i++;}finally{ i--;}返回i;}|goto X C:astoreejsr Saload eathrowS：astore rinc i-1ret rX：负载i伊图尔恩图1. 一个简单的finally块，它的字节码和控制流程图。方法（main）或异常处理程序代码C的。在第一种情况下，S将返回（带ret）到指令goto X，否则返回到处理程序的第二部分，以athrow结尾。2.4嵌套子程序[21，Chapter 16]中图2的例子说明了处理子程序时的困难。 它包含一个带有break状态的嵌套finally块。3编译器将其转换为两个异常处理程序h1（t1，R1，C1）和h2（t2，R2，C2），其中可以重新计算直接从内部子例程转到封闭子例程，而不执行属于内部子例程的ret语句。字母e表示保存异常引用的寄存器，r表示保存子例程调用返回地址的寄存器。图3中相应的控制流程图相当复杂。它的两个异常处理程序h1和h2各包含一个finally块。第一个finally块包含一个while循环，其中包含测试W和循环体L。如果循环测试失败，则S1通过X返回到其调用者的后继者.这可能是第二条指令，或C1之后的代码，它在执行S1之后抛出异常e1。循环体L包含在内部try/finally语句中，编译成3方法的主体不包含任何与simpli- city语义相关的操作由Sun的J2SE 1.3编译器编译的结果代码 如果try块包含额外的指令，则处理器可能生效。因此，在本例中保留了它。主要CSgoto XC：AthrowX返回C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109115publicboolean already（）{尝试{返回;}最后{while（b）{尝试{返回;}最后{如（b）破裂;}}}}|jsr S1（h1）||返回C1：asore e1jsr S1aload e1athrowS1：asore r1goto W| L：jsr S2（h2）||返回C2：astore e2jsr S2aload e2athrowS2：astore r2Iload bifne XY：ret r2W：iload bifne LX：ret r1图2.从一个子程序中分离出一个封闭的子程序。异常处理程序h2.执行L会导致在S2处调用内部finally块，同样是在return语句之前这个块将测试b并中断到外部子例程，它由连接S2→X表示。如果b为false，则内部子例程将使用其ret指令在Y.在那里，控制将返回到L中的内部return语句，然后从方法返回。这两个try块也受默认异常处理程序的保护，其中控制流程是相似的。主要的区别是抛出的是异常而不是返回值。3内联Java子例程一旦找到了所有子程序及其边界，就可以对它们进行内联。内联通常只会略微增加程序的大小[11]，但会显著降低数据流分析的复杂性[11，21]。表2定义了所有字节码指令的潜在后继指令。在不失一般性的情况下，假设指令被编号，连续的。因此，pc+ 1指的是当前指令的后继指令，pc-1指的是其前身指令。条件分支（ifne）被非确定性地处理。jsr指令被建模为具有两个后继，因为在a处执行子例程之后，控制返回到pc+1。某些指令离开了当前方法的范围（return，athrow）或con-parameter。C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109116C1主要S1WLC2S2XYC1：athrowS1：返回main：returnC2：athrow图3. 嵌套子程序的控制流程图。指令（地址为pc）可能的继任者aload，iload，astore，istore，inc{pc+ 1}转到a{a}ifnea， jsra{a，pc+ 1}返回，返回{}表2Java字节码指令的潜在继承者。在一个特殊的地址（ret）继续。假设方法的第一条指令的代码索引为0。 如果存在从指令0到i的后继序列，则代码索引i是可达的。S是子例程i，i是可达的，code（i）是jsrS。如果code（S）是astorer，code（X）是retr，并且X必须在不使用附加astorer指令的路径上从S可到达，则代码索引X是从子例程的可能代码索引i属于子程序S，i∈S，如果存在来自该子程序S的可能返回X，使得S≤i≤X。子例程S的结尾eos（S）是属于S的最高索引。请注意，此定义避免了嵌套异常处理程序范围的语义，因此分别覆盖每个嵌套子例程。 为了实现内联，我们C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109117子程序的主体是属于子程序S的代码，其中对于每个代码索引i，Seos（S2）<如下 此外，code（S2−1）必须是指令gotoeos（S2）+ 1。一如果存在属于子例程S1的指令jsrS2，则子例程S1依赖于（可能嵌套的）子例程S2，S1≠S2，其中S2/=S1。可转换性是可传递的。依赖于S2的子程序S1必须内联在S2之后.当以后内联S1时，S1中对S2的调用已经被S2的主体替换。除此之外，子例程内联的顺序并不重要。在每个内联步骤中，对一个子例程S的所有调用都是内联的。3.1充分必要的良构条件Java字节码只能在满足某些格式良好的条件时才能内联。字节码验证的规范给出了一组必要条件，其中包括子例程必须具有单个入口点，并且返回地址不能通过jsr指令以外的方式生成[16]。除了这些给定的条件，额外的条件必须保持这样一个子程序可以内联。请注意，Java编译器生成的程序不可能违反这些条件，除了下面描述的有关JDK 1.4的次要方面。此外，不满足这些格式良好标准的人为生成的字节码验证本质上是一个不可判定的问题，因此验证器只允许所有可能的字节码程序的子集通过[16，21]。这里没有描述的一个额外条件来自于当前每个方法65536字节的人工大小限制[16]。其他限制是字节码必须满足的结构条件。这里给出的是一个从[21]中提取的简化定义：边界每个子程序S必须有一个endeos（S）。如果子例程S没有ret语句，则jsrS可以用gotoS代替，不需要内联没有递归。 子程序不能调用自身。正确嵌套。 子程序不能重叠：$S1，S2·S1S2eos（S1）eos（S2）。<<<没有相互依赖。如果Si<$Sj，则必须不存在使得Sj<$Si的依赖关系。请注意，此属性不受嵌套的限制。C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109118|||||S1： Astore R1...S1： Astore R1jsr S2S：阿斯托雷 R.........S2： Astore R2eos（S1）：保留R1jsr S.........eos（S1）： 保留R1S2： Astore R2eos（S）：ret r......eos（S2）： 保留R2jsr S1...eos（S2）：保留R2没有递归。正确嵌套。没有相互依赖。| ：|H|...|| ：...S：Astore R...丙：...eos（S）：ret r| :||...|H| S：Astore R|...||...eos（S）：retr...丙：jsr S...|：|...H |S：Astore R|...|EOS|（S）：ret r|...||异常处理程序兰奇子程序包容安全壳安全壳在处理范围内。图4. 违反格式良好性条件的指令序列。异常处理程序包含。如果处理程序h（t，R，C）的代码C属于S，则 它 的 整 个 范 围 R 也 必 须 属 于 S ： h （ t ， R ， C ） ， S· （ C∈S→R<$S）。远程控制。如果处理程序h（t，R，C）的任意i ∈ R属于S，则它的整 个 值 域 R 必 属 于 S ： S_h （ t ， R ， C ） ， S· （ R_i ∈ R·i∈S→R_S）。处理程序范围内的子例程包含。如果处理程序h（t，R，C）的整个范围R属于S，则任何指令jsrS必须在R内：h（t，R，C），S·（RS→（i·code（i）=jsrS→i∈R））。对于最后六个条件，图4显示了一个违反它的例子。现有的Java编译器不会违反它们，除非在3.5小节中描述。：：C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109119|iinc i1|(h) |jsr S||gotoXC：astore ejsr加载和athrowS：astore rinc i-1ret rX：负载i伊图尔恩(h1) |iinc i 1iinc i-1(h2) |goto XC：asoree inc i-1 aload eathrowX：负载i伊图尔恩图5. 内联子程序。3.2控制转移目标当内联子程序时，子程序S的主体替换每个子程序调用。内联的这一部分很简单，如图5中的示例所示。替换jsr指令的S的两个内联副本以粗体显示跳跃目标的难度会增加，在内联后更新。内联消除了jsr和ret指令;因此到这些指令的任何跳转都不再有效。此外，子例程内部可以跳转到封闭子例程或代码的顶层，如图6所示。因此，内联算法必须在几个内联步骤期间更新跳转目标，并且还必须考虑内联子例程主体的每个实例的副本该算法使用两个代码集，当前集B和新集BJ。在每个内联步骤期间，B中的所有指令被移动并且可能被复制，从而创建新的指令集BJ，其成为用于下一内联步骤的输入BB中的每个地址都必须映射到一个等效的地址BJ。 每个可能的执行（包括异常行为）必须在B和B j中执行相同的操作序列，不包括jsr和ret。B中的代码索引涉及到jsr或ret指令，必须映射到BJ中的等效索引。 最直接的解决方案是每次内联给定子例程的一个实例后更新所有目标。 这当然是正确的，但也是非常不明智的，因为它需要为每个jsr指令而不是每个子例程更新一次目标。相反，我们的算法使用映射M，代码索引的关系I×IJ将索引i∈I映射到索引集合{i，J，.，iJ}∈IJ. 这种关系，0 1k初始为空，记录B中的地址如何映射到一个或多个地址在BJ。每次将索引i处的指令从C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）10912000RRωαα将当前代码集B到索引iJ处的新代码集BJ，i→iJ添加到映射。每个子例程都是在一个步骤中内联其所有实例进行处理的，最里面的子例程首先被内联。不属于正在内联的子例程并且不是jsr S操作的指令从B复制到BJ。每次出现jsr S时，都会用S的主体替换。处理跳转到insj（jsr S指令本身）和insr（子例程中的ret指令）的关键是向J JM.第一个是ij→i，其中ij= index（insj），i=M（S），索引子例程的第一条指令映射到的位置第二一个是r →iJ我在哪里= index（ins）和iJ=M（eos（S）+ 1），内联子例程之后的第一条指令在以下讨论中，向前跳转是其目标代码索引大于指令的代码索引的跳转。类似地，向后跳转是导致较小代码索引的跳转。如果字节码满足上述正确性标准，则算法的正确性可以证明如下：• S之外的一个目标被映射到一个单一的目标，因此是平凡正确的。• S的主体中的目标被映射到内联子例程SJ、SJJ等中的几个目标，一个用于B中的每个jsr S。 假设B中的跳转指令位于代码索引i处，目标位于a处。给定iJ，B j中跳转指令的索引，必须选择当前映射中最近的目标，这仍然保留跳转是向前跳转或向后跳转的事实。对于a为w的跳跃，indexminaJ·（a→a∈M）<$（aJ（iJ）是cor-rect索引这可以如下所示：地址a要么在S之外，在这种情况下，码（a）没有被复制，并且只有一个AJ·a<$→AJ∈M。如果a在S内部，则aJ必然是在该方向上离iJ最近的目标：在内联期间，索引a处的代码已被复制到aJ从S到SJ。SJ的内联副本的第一个指令位于索引SJ处和J J J Jα最后一个指令在Sω处。因为i属于S，所以Sα≤i≤Sω成立。没有除了Sj之外的其他代码已经被复制到该间隔内的位置，并且J ≤iJSJ，因此aJJ> aJ。<落后α ω反之亦然。• 跳转到B中的jsr S指令间接执行S处的代码。映射它到SJ保持语义。JSRC. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109121|jsrS1goto W1L1：load bifne X1(h1) ||（h2）返回C1：astore e1jsr S1aload e1athrow|jsr S1(h1)||返回C1：asore e1jsr S1aload e1（h21）|返回C21：astore e2负荷B如果X1负载e2 athrowW1：负载bifne L1(h1) |X1：返回C1：astore e1goto W2L2：helloifne X2(h2（二）|返回C2 2：astore e2负荷B如果X2负载e2 athrowW2：负载bifne L2X2：负载e1athrow图6.分两步内联嵌套子例程• 跳转到子例程中的最后一条指令将返回到其jsr S指令的后继指令。因此，将ret指令的代码索引映射到S的主体的最后一个内联指令的后继指令在内联代码中产生相同的结果请注意，在jsr指令[16]之后总是存在一个指令，例如return。图6的第二个内联步骤（图2中的子例程的内联）显示了其中两种情况。在外部子例程S1的两个内联实例中，存在到子例程内部的W和到S1的ret指令的索引X的跳转。通过内联S1，两个代码索引都被映射到两个新的索引{W1，W2}和{X1，X2}是独立的。如上所述，保留了关节的特征。3.3异常拆分如果一个jsrS指令insj由异常处理程序h（t，R，C）保护，其中R=[rα，rω]不扩展到子例程本身，则该处理程序对于内联子例程必须是无效的。图5中显示了一个简单的示例，其中jsr指令位于异常处理程序范围的中间。 因此，要解决这个问题，必须拆分分为两个处理器h1（t，R1，CJ）和h2（t，R2，CJ）。 新的范围是R1=S1：Astore转到WR1S1：阿斯洛Astore R1|||L：第二条：jsr S2returnastorejsr S2e2（h2）|转到WL：负载bifne X返回S2：Y：加载e2athrowastore r2加载b ifne X保留R2第二条：女：asoree2iload bifne Xaload e2athrow负荷B女××：负荷Bifne LC. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109122ωωγ[rJ，r]和R，其中rJ=M（r）和r=M（index（ins）-1），映射αβ2αα βjjsr指令的前导代码索引在R2=[rγ，rJ]，r=M（index（insr）），最后一条指令的后继指令的映射代码索引的子例程体，并且rJ=M（r）。ω拆分处理程序对于确保内联程序的正确性是必要的存在R1或R2退化为长度为零的区间并且可以完全移除的情况。拆分可能会在子例程的嵌套深度中以指数方式增加异常处理程序的数量。不过，这个数字几乎从来不会大于1，并且只有少数异常处理程序是通过拆分来执行的。3.4异常处理如果一个子例程S（而不是jsr S语句）受到异常处理程序的保护，那么这个保护也必须确保子例程的内联副本。因此，必须为每个内联的S实例复制保护子例程S的所有异常处理程序。图6显示了这样一种情况，即内联外部子例程S1导致该子例程内部的异常处理程序h2被复制。请注意，如果jsr指令和子例程都由同一个处理程序保护，则不会发生这种重复 在这种情况下，内联的子例程自动包含在映射的处理程序范围中。 异常处理程序可能会以指数方式增加处理程序的数量，这在实践中不是问题，因为最里面的子例程（对应于最里面的finally块）从不受异常处理程序本身的保护，从而将指数减少1。3.5违反JDK 1.4最初的实现在使用JDK 1.4编译器编译的一些类文件中出现了问题原因是编译器的变化，旨在帮助VM的字节码验证器当编译图1中的程序时，产生的指令是相同的，但异常处理程序是不同的：原始处理程序涵盖了三条指令，初始增量指令，jsr和跳转到程序末尾的goto1.4编译器的处理程序省略了goto。这不会更改代码的语义，因为goto指令不能引发异常。然而，第二个处理程序h是由较新的编译器安装的，它覆盖了异常处理程序代码的前两个指令（在标签C处），C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109123的呼叫123456十一28子程序数1783173239831表3每个子例程的调用次数，决定其代码内联的频率。astoree和jsr S的第二个实例。这种情况由于h是递归的而变得更加严重;处理程序代码与受其保护的第一条指令这可能（理论上）产生一个无休止的异常循环。内联h的结果是一个只覆盖astore指令的处理程序（因为内联的子例程在处理程序范围之外幸运的是，astore指令不能抛出异常，因此不需要在VM中进行任何更改，以避免潜在的无限循环。较新的JDK编译器（1.4.2及更高版本）就地生成子例程。结果与JDK1.4中的内联代码相同，包括伪处理程序h。3.6内联成本内联子程序只会稍微增加代码大小。子程序是罕见的。在Sun的Java运行时库（版本1.4.1）中它们都不是嵌套的。表3显示，每个子例程通常被调用两到三次，只有少数例外，其中一个子例程被更频繁地使用。图7左侧的直方图显示，大多数子例程的大小仅在8到12字节之间; 626个子例程的大小为9字节，因此该条目的大小不超过该比例。没有一个子程序大于37字节。内联通常会导致小于10个字节的适度代码增长。这由右侧的直方图显示，其中具有偶数和奇数字节的条目汇总在一个桶中。刻度线上的值是0（64041个方法，包括那些没有子程序的方法）和2，代表571个方法，其中代码大小增加了2或3个字节。10个方法增长了60多个字节，186个字节是最差的情况。内联JRE 1.4.1的所有子例程将导致5998字节的代码增长，这与整个运行时库（25 MB）相比可以忽略不计。4抽象的、基于寄存器的字节码Java字节码包含201条指令[16]，其中许多是同一类型的变体。例如，25条指令在堆栈上加载一个寄存器。变体包括用于每个数据类型的若干指令，一个通用变体（例如，Iload_R）和短变体如Iload_0，其中R是硬编码的。再-C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109124JRE包中的子例程大小1008060402000510 15 20 25 30 35 40字节大小内联后代码大小的增长（JRE）1401201008060402000 1020304050 60增长（字节）图7. 子程序的大小和内联后的大小增加。指令集的引入是一个明显的简化。我们使用抽象字节码[21]作为简化格式，其中参数类型和硬编码索引被折叠到泛型指令的参数化版本中。例如，aload_0变为Load这种减少与字节码内联无关。上一节描述了使用普通字节码的内联，以允许独立的内联算法。[21]中未实现的指令包括算术指令，其实现是直接的。不受支持的指令是switch（用于控制流）、monitorenter和monitoretrant（用于多线程），以及修改后续指令的参数大小的wide前三个指令必须根据标准字节码语义实现[16]，而宽指令是Java字节码最初针对指令内存很少的嵌入式系统的事实的在抽象字节码指令集的实现[5]中，我们将任何指令参数的大小扩展到四个字节，因此可以通过将所有指令参数转换为四字节格式来消除宽指令。抽象字节码只有31条指令，这已经是对原始指令集的极大简化。然而，（固定大小）堆栈的使用使数据流分析变得不必要的困难，因为每个索引处的确切堆栈高度虽然在编译时已知，但必须在加载类文件后首先计算。这种计算通常是类加载器中字节码验证的一部分。此外，堆栈和局部变量（寄存器）的处理导致基本上执行相同任务的指令对：load从堆栈中弹出顶部元素，而store将寄存器推入堆栈。最后，64位值被视为单个堆栈元素，但作为一对局部变量。这就需要区分许多指令的大小写[16]。该规范要求永远不使用保存64位值的局部变量的第二个槽，并且堆栈语义许多方法许多方法C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109125字节码变体爪哇[16][第21话]基于寄存指令集大小2013125每个指令的高达2511字节代码子程序是的是的没有宽指令是的不执行。消除64位值是的不执行。消除寄存器位置隐式隐式显式表4基于寄存器的字节码的好处。在将64位值推到其上时保留由于每个指令的堆栈高度都是已知的，因此我们将抽象字节码的基于堆栈的格式转换为显式表示，其中每个堆栈元素都转换为寄存器。当使用寄存器时，堆栈元素和局部变量可以统一处理，将Load和Store合并到Get指令中，并消除更多指令，如Pop，Swap或Dup。在所有转换中，转换Dup指令是唯一不平凡的，实际上证明是非常困难的。此指令的某些变体不仅复制堆栈的顶部元素，还将其存在六种Dup指令变体，由于64位值，数据流的处理需要每个指令变体最多四种情况区分[16]。我们将所有的Dup指令转换成一系列等价的Get指令。不幸的是，这引入了仅对应于一个原始指令的指令序列，这使得进一步的处理稍微复杂一些;但它仍然消除了64位值的大小写区别，这是更大的开销。这种向基于寄存器的字节码的转换将最终指令集的大小减少到仅仅25条指令。其余的指令是（参考[16，21]的语义）：ALoad，ASore，ArrayLength，Athrow，Checkcast，Cond，Const，Get，GetField，GetStatic，Goto，Inc，Instanceof，PutkeSpecial，PutkeStatic，PutkeVirtual，PutorEnter，PutorExit，New，NewArray，Prim，PutField，PutStatic，Return，Switch。 该指令集用于JNuke，并已通过静态分析、运行时验证和软件模型检查在1，000多个单元和系统测试中进行了测试[2，3，5]。5相关工作以前的工作已经调查的困难，在分析Java字节码所产生的大型指令集和子程序。内联字节码子例程已经在即时编译的上下文中进行了研究[15]，或者作为C. Artho，A.Biere/Electronic Notes in Theoretical Computer Science 141（2005）109126前处理阶段的定理证明[11]。后一篇文章还描述了一种替代内联代码复制的方法：通过在一个额外的寄存器中为每个子例程调用指令存储一个小的唯一整数，子例程可以在不使用jsr指令的情况下被仿真。然而，这种策略的大小增益很小，字节码验证器必须再次确保这个额外寄存器的内容永远不会在子例程中被覆盖，这将使字节码验证中的一个主要问题未得到解决。因此，这一方向从未进一步探讨。代码分析中的挑战类似于这里描述的那些，发生在解压缩中，其中必须发现子例程的结构以确定try/catch/finally块的正确范围。 Dava反编译器是Soot框架的一部分，它分析这些结构，以获得正确匹配原始源程序的输出[19]。 Soot还通过内联消除了jsr指令[22]。然而，没有给出算法。缺少有关如何处理嵌套子例程的详细信息作为μ Java [14]工作的一部分，另一个项目也执行了一种称为子例程扩展的子例程内联[24]。主要的区别是，扩展后的代码仍然包含jsr指令，这使得确保内联代码的正确性变得更容易，但仍然对我