本文分享基于字节码种子生成有效、可执行的字节码文件变种,并用于 JVM 实现的差别测试。本文特别提出用于修改字节码语法的classfuzz技术和修改字节码语义的classming技术。上述变种技术系统性地操作和改变字节码的语法、控制流和数据流,生成具有丰富语义的字节码变种。进一步地,可以在多个 JVM 产品上运行生成的字节码变种,通过 JVM 验证或执行行为的差异以发现 JVM 缺陷乃至安全漏洞。本文整理自陈雨亭在 2018 年 12 月 22 日 GreenTea JUG Java Meetup 现场的演讲速记。
今天我要报告的是我们在过去几年内针对 Java 虚拟机的测试工作。首先先做一下自我介绍,我是中国计算机学会系统软件专委会委员陈雨亭,非常希望有同仁加入系统软件专委会。
对于 Java 虚拟机测试的研究,其实是一个偶然。早期,我做了一些软件测试方面的工作,当时我更多关注于技术,包括基于规约的软件测试、模型驱动的软件测试、白盒测试、黑盒测试这些耳熟能详的测试技术。在 2014 年到 2015 年之间,我开始关注那些能够发现真实问题的系统测试方面的工作,当时就做了 SSL 安全协议支撑软件,包括 OPENSSL 这样的一些软件的测试。后来就想为什么不能做一些更复杂工作?比如可以测试 Java 虚拟机,随后就遇上了一个新的挑战, Java 虚拟机的输入是字节码,对其测试某种意义上来说实际上是在生成程序,这件事情也很有挑战。
我们在 JVM 测试方面做了两项工作,实际上做了两个工具:一个是classfuzz;一个是classming。
首先介绍一下背景,这个问题的背景还是来自于 Java 虚拟机的跨平台性,对于同样的类来说,放在各个虚拟机上面跑,就需要有相同的运行结果。对于 Java 虚拟机,我们就想能不能在里面找到一些缺陷。实际上这个不是一个新概念。任何一个产品级的虚拟机在发布之前都需要通过技术兼容包 TCK 的测试,那么技术兼容包实际上是由 Oracle 发布的。这就引发了新问题,我不是 Oracle 的员工,我也没有花钱去买 TCK,我该怎样去测试一个已经发布了的产品级虚拟机?包括 OpenJDK 中的 HotSpot
或者IBM 的 OpenJ9。
这里面就同时衍生了两个问题:
-
怎么样去发现一个 JVM 缺陷或者是安全漏洞?
-
怎样生成一个有效的测试包?对于测试输入,怎样能够有更多的这样的字节码,或者产生更多可运行的应用程序并在虚拟机上再跑一跑?
1.1 如何暴露出产品级虚拟机的缺陷
对于第一个问题,即怎么样去暴露出一个产品及虚拟机的缺陷,这里面在跑的时候就会发现有一个困难,这个困难就是在学术圈里叫做“缺少一个测试喻言”。如果要测一个 Java 虚拟机的话,我们拿一个类过来跑跑,在一个 Java 虚拟机上面,会得到一个真实的结果,这个时候我们把真实结果和一个预期结果来比较一下,如果能够发现它们里面的不一致,那么这个就说明 Java 虚拟机出现了一些问题。
我们的预期结果到底是怎么来的?实际上有一个 Java 虚拟机规范,假如 Java 虚拟机规范,它也是一个能够运行的机器,那么它跑一跑,能够得到一个运预期结果。但是实际上,我们说 Java 虚拟机规范它本身也不能跑,所以这个事情实际上没有很好的解决方案。后来,我们意识到差别测试技术,这个也是 Java 虚拟机开发中,大家都采用的一个方法,也就是说有多个虚拟机,把一个类或者是应用拿到不同的虚拟机上去跑,比较它们之间的结果是不是有差别。
如果这个大家结果都一致,那就很好,如果结果不一致,那么就可以去预测一下这里面是不是有 Java 虚拟机的实现出了问题。
1.2 如何获得一个有效的测试包
对于第二个问题,就是怎么样能够有更加复杂的或者更加花样繁多的字节码来做测试?一开始,我们尝试去使用现实中大量的类,从网上甚至从 openJDK 里面自己的包里解压出很多类文件,放在 JVM 不同版本上面去跑。这里面的确还是能够发现一些问题,一些不一致的现象,但是这个不一致更多是兼容性问题。
于是我们很快就转向了第二个技术,叫“领域感知的模糊测试技术”。模糊测试是应用在安全领域里面的一个测试技术,它可以帮助发现一些安全问题。比如说有一个文件,有个图像,把这个图像一位一位地变化,用以查看应用软件是否比较健壮。如果把技术应用到 Java 虚拟机上面,就要做一些调整,这种调整是领域感知的 ,也就是说我们知道 Java 字节码它本身的一些特性,根据它的特性来做一些变化,这个工作更加泛,我们有一个种子类,通过这个种子,我们会把它变来变去,变成一堆的测试类,放到 Java 虚拟机上跑。
这个工作我们曾发在 PLDI2016,还有一个明年的 ICSE 上的工作,第一个是 classfuzz,第二个 classming。让我们对于 Java的类执行过程进行一个深入了解,一开始做的工作比较偏向于上层,就是更多的去关注了 Java 类的是怎么样去导进来,怎么样链接,怎么样去初始化等等。这个是 classfuzz 的主要工作。后来做到一定的程度,我们就转向了下层,怎么样去做验证,执行,这个时候就会去想类的执行会不会引发一些差别,我能不能在不同虚拟机上真的跑出一些不一样的结果。
Classfuzz
下面,我就分别对这两个工作进行介绍。classfuzz 是一个很简单的一个想法,就有点像一开始最传统的模糊测试的技术,对合法的 Java 字节码文件,我们想进行一个语法变种,变种以后,比如说对于 Java 类我们得到它的一个语法树,去尝试修改,比如说把 public 改成 private,把文件名改一改,把这个函数名改一改,这样的话可以生成很多比较奇怪的类,把奇怪的类拿过来以后,就可以去测试一下 Java 虚拟机的一个健壮性。
flag,表明这个是一个接口文件 interface。那么从规范上来说,如果接口 flag 被设定了以后,它就要同时去设一个 abstract 的 flag,所以 HotSpot 报了一个格式问题,这个是正确的。那么 Open J9 上我们就找到一个缺陷。
我们把这个问题其实也报给了 Open J9,经过了几轮反复,他们很快就修复了,修复完了以后又引入了新的问题,又修复,大概就是这样的一个过程。
<clinit> in a class file are of noconsequence, “除了类初始化这个函数以外,其他的函数加上这种标识符 of no consequence”,这到底是一个什么含义?这个里面大家就有误解了。Hotspot 认为它是一个常规的方法,但是 J9 认为这里面就是一个格式错误,这个就是大家对 of no consequence 会有认识上的不一样。
Classfuzz 框架
接下来我来介绍一下 classfuzz 的框架,假设有个种子,进行了一个变种,变种结束以后,把变种类放到 Java7、Java8、Java9、J9、GCJ 上面一起去跑。那么就可以通过一个类,生成了很多的变种文件,在不同虚拟机上面跑。这个里面其实想随机的变种,随机生成很多的变种类,效果非常差。于是又引入了这样一个过程:有一个选择和测试的过程,有很多的变种算子,我们研究怎么样去选择更有效的变种算子,也选择更加有代表性的一些类文件来做测试。
那么这里面有几个技术要点,由于时间限制,我就简单过一下。
Classfuzz 的技术要点 1
我们设计了 129 个变种算子,其中 123 个是用来修改类的语法的,像我刚才说的 public 改成 private,删掉一个名字,改掉一个函数名等等,或者删掉一个函数等等。
我们还有 6 个修改语义,右边是修改语义的一个简单的办法。我们采用一个 Java 字节码分析工具是 SOOT,这里面它会把类转成 Jimple 文件,那么对 Jimple 文件的第 2 个语句和第 3 个语句,可以给它顺序颠倒一下。但是这个颠倒效果没有那么理想,不是说所有程序的字节码都有一个先后关系。
Classfuzz 的技术要点 2
刚才说到有 129 个变种算子,这个算子数其实挺多的。我们的选择性非常广,那么这里面就采用了一个直觉,直觉是哪些变种算子更加有效,就让它用的更加频繁一点,所以采用了一个有点偏机器学习的一个算法,马尔可夫链蒙特卡洛算法来选择更加有效的算子。我们预期会形成一个分布,有些算子给它一些高的概率,有些给低的概率。实际分布不是所预期的这样,但总体上趋势还是比较接近的。
Classfuzz的技术要点 3
会有很多的测试类会被生成,这个时候怎么样去选择一些有代表性的测试类?我们采用了传统测试里面一个等价类划分的技术,就把它们放到某个虚拟机上去跑,放到 Hotspot 上面,特别是 classloader 那一块代码,就收集一下它的行覆盖率和分支覆盖率,比较一下。这个时候立刻就有一个数字上的感觉,假如这个数字不一样,那么就说明类在 Java 虚拟机里面的处理逻辑是不一样的,如果处理逻辑不一样,那么就应该说两个类特性还是不一样的。如果有新生成的类的话,拿到 Java 虚拟机上跑,再来算一下它的覆盖率,看看它是不是有代表性,这里面代表性有两个用途,第一个是用于多个Java 虚拟机差别测试,第二个是把它作为新的种子来做变种,能够得到新的变种。
Classfuzz 的技术要点 4
第四个技术要点是差别测试,我们拿类到多个 Java 虚拟机上跑,去观察它们的执行结果,试图去分析到底是在哪一个阶段所抛出的什么问题。观察在哪个阶段报了错,为什么?当有几个 JVM 的时候,就采用一个从众原则推测哪个 Java 虚拟机出错了,这是差别测试的过程。
classfuzz 也发现了更多的 Java 虚拟机的这种区别,这里面有一个变量叫 R0,我们把 R0 的类型改了一下,从 map 改成 String,也发现了虚拟机差别。我们还发现 J9 和 Hotspot 的验证方式不一样,当导进来一个类的时候,HotSpot 会把所有的方法都会验证一遍,但是 J9 就显得比较 lazy 一点,它只是对将来有可能运行的方法会去做一个验证,所以这个时候也有一个差别。那么此外还发现 GU 缺少维护,当然它现在更缺少维护了。
我们这个时候就意识到还会有很多的工作要做,于是就再接再厉,又做了下一个工作。classfuzz 并没有能够深入测试 Java 虚拟机的底层,我们至始终在测的可能编译那块的同学比较感兴趣一点,但是对于研究运行时的同学可能没有那么大的兴趣,那么主要的原因就是我们只是修改了语法,生成了很多格式正确或者不正确的字节码文件,但是去运行的时候,除了很少数的能够修改语义操作的一些算子以外,生成的大部分的东西或者是被拒了,或者是它的执行和前面的一些类没有什么差别。这个时候我们就思考这样的一个事情,我们是不是能够生成格式正确、但是语义不一样的程序,语义不一样也就是说你真的能够在Java虚拟机上跑,实际上语义不一样的字节码。
这样我们能够测试两个功能模块:第一个,验证器;第二个,它的执行功能,或者执行引擎。大家觉得可能就有点意思了。好,在做这两件事情的时候,其实有一些执念:
- 第一个执念,有很多同学都学了编译,那么编译原理里面其实有很多程序分析和优化的算法。当时在做这件事情的时候,就很好奇,这么多经典的算法在 Java 虚拟机实现当中,都正确地实现了吗?我们能不能在实现里面,找到一个实现错了的一个算法?
- 第二个执念,是不是能够找到在两个 Java 虚拟机上运行结果不一样的程序?这个典型的就拿主流的 J9 和 Hotspot,在上面能不能用同样字节码,能够运行不一样,还有为什么?比如执行的时候是不是还会有各种各样奇怪的现象,例如 double free 等问题。
好,那么接下来我们 show 一点例子,帮助大家了解 Java 虚拟机的上述差别。
右边一小段代码,那么这两段代码我们看是不是真的有什么语义上的不一致?实际上左边代码是创建了一个对象,从栈顶拿出了一个元素,做了一个比较,对吧?右边代码表示从栈顶拿了一个元素,创建了一个对象,再做了比较。这两个代码语义其实是一模一样。一个是 o 等于 this,一个是 this 等于 o。这两段代码其实本质上都是错误代码,因为我们 new 完了以后其实没有给对象初始化。但是到 Hotspot 和 J9 上面去运行的时候,Hotspot 给两个都报了一个验证错误,我们就发现,J9 在非常罕见的情况下,在某一个初始化函数里面,如果你写了代码,它会通过验证。实际上我们抓住了一个缺陷。这是一个比较简单的例子。
那么再来看比较复杂一点的例子,我们说数据流分析可能实现错了,那能不能找一找运行结果不一样的程序?右边是一个种子类,先创建了一个对象,初始化,把这个对象设为空。接下来用 monitorenter 和 monitorexit。那么 Jimple 正好反了一下。把它转换为类文件以后,Hotspot 和 J9 它是比较一致的,Hotspot 抛出了空指针异常,J9 也抛出了空指针异常。这是因为 Java 虚拟机规范里面说,假如对象是空,我们遇到的第一个 R0,因为是空的,那么它应该抛一个空指针异常。
那么接下来看看到底怎么样去修改代码,发生了什么?第一个干的事情就是在里面插入一个循环,直接跳到这,entermonitor R0,这个地方又做了一个循环回去,也就是说 entermonitorR0 会执行 20 遍, exitmonitor r0 执行了一遍。这个时候我们发现这个 Hotspot 抛出了一个 IMSE,但是 J9 是正常执行。追究原因,我们发现这里面其实有一个叫结构锁的机制,假如一个Java 虚拟机要求去实现结构锁这样的一个机制,并且类违反了结构锁规则,那么就抛出一个 IMSE,Hotspot
满足结构锁机制,但是 J9 不要求,所以这里面会形成一个差别,这是所发现的第一个差别。
又去跑模糊测试,继续去撞。这个时候从 new string,初始化之后,正好插入了一个 goto 语句到这,也就是说这是一个 new string r0,entermonitor r0,exitmonitor r0。Hotspot 就是正常的运行了,J9 就抛出了一个验证错误。HotSpot 反馈说这应该是一个正确的例子,因为虽然 R0 没有初始化,但是这个里面没有什么危害,所以就可以放过它。
那么 J9 就认为它存在一个缺陷。实际上 Java 虚拟机规范里是这样说的,一个验证器如果遇上一个没有初始化的对象,在使用的时候应该要报一个验证问题。好,那么既然到这种情况下面,entermonitor r0 它是使用了,就说明这个规则被违反了。又做了做,又撞了一个问题。entermonitor r0 这个东西是一个正常的对象,那么 exitmonitor r0,这个时候 R0 是空对象,它本来应该匹配的,但是这个时候实际上变成空引用。
J9 抛出了一个空指针异常,Hotspot 抛出了 IMSE。J9 的解释很合理,因为从规范上来说,monitorexit null 应该抛出一个空指针异常。Hotspot 开发人员也找了很久,实际上发现在这做了一个优化,在这个时候 Hotspot 会抛出几个异常,但是这个时候会做一个优化,把其他异常都扔掉,留了一个 IMSE。但是由于它们是抛的不一样的异常,由于这些异常可以被分别捕获,所以程序可以产生不同的运行结果。针对于同样的一个种子,我们变化,会发现,这个程序它的运行还有点不太一样。
这个里面还发现了一些,比如说 Hotspot 的不同版本之间也会有一些差别,当我们的测试类比较复杂的时候,有控制流的归并,有数组的访问,有异常处理等等,它会遇上一些问题。
技术方面,还是采用类变种,意图是生成语义不一样的一些文件。怎么样算语义不一样?也就是方法里面能够被运行到的字节码是不一样的。那么一个主要的思想就是要修改这个种子里字节码。我们记录哪些字节码被运行到了,在里边去修改一下,去修改它的控制流,那么修改完了控制流以后,它的数据流也可能发生改变,这个时候会出现很异常的控制流或者数据流,如果我们把这种异常的情况放到 Java 虚拟机上跑,有可能它的数据流分析会错了,有可能其他情况也会出错,这是很简单的思想。
我们的技术要点,第一个会记录一下哪些字节码会被执行到,反正做一些插装就可以。第二个我们要做一些变种,在每个语句后面,就插入 goto。实际上除了 goto 之外,我们还可以插入 return、throw、lookupswitch,都是 Jimple 里支持的。当然也可以去用 ASM 插入更多能够修改控制流的指令。
变种过程也是一个频繁试错的过程,实际上遵循了一个流程,变种出错我就把它拒了,变种过程就是有个种子,变完了以后,决定要接收、拒绝等等,得到新的类,继续变种、接受、拒绝等。
我们差别测试主要是看看有什么验证问题,还有没有可能会撞上系统崩溃,有没有输出差异,这种输出差异并不是由并发导致的,而由 Java 虚拟机实现上面的差异导致的。
最后介绍一个例子。右边有一个函数,R2 等于 new string,那么在这 R2 是一个对象,这个 R2 被用了,所以理论上他不能通过验证,因为 R2 被使用之前没有被初始化,违反了 Java 虚拟机规范。但是在这个里面 Hotspot 成功地抛出了验证错误,但是 J9 没有能够拒绝,说明验证器出错了。实际上大家可以看一下这个问题是怎么来的,其实就是植入了一个 goto,初始化中跳出去了,它正好 R2 就被使用了,这个时候就发现了这个问题。
总结一下我们的工作,我们做了一个 Java 字节码变种及 Java 虚拟机差别测试的一个技术方案,这个里面可以暴露出 Java 虚拟机的缺陷。进一步我们希望去看看,既然有这么多的变种,为什么不把它应用到内存管理当中,看看内存管理有什么问题,看看性能有什么问题,特别是变种有可能会对一些高强度的计算,进行反复的迭代,反复计算,那么是不是能够发现性能方面的一些缺陷?这项工作是和现在在苏黎世理工的苏振东老师,九州大学的赵建军教授,还有南洋理工的苏亭,谷歌孙诚年一起做的一项工作。那么我的汇报就到这里,谢谢大家。
-