2023-9-7讨论班

Posted on In

Type Batched Program Reduction

Reducer：将程序变得更简洁，但保留感兴趣的点（例如编译错误，运行错误，特定输出等），不需要程序语义和原来保持一样

  • 针对特定的语言

Reduction算法：

  • transformation：程序化简的方法
  • search strategy：指导程序如何化简【一般是贪心】
  • Oracle：如何判断程序仍然具备想要的性质【一般是用户给的】

举例：C-Reduce

  • 将特定字符串替换为”0”/“1”
  • 局部修改：修改三目运算=>例如只保留一个分支，reduce只需要让程序变简单
  • 删除指定行数的代码
  • 进行类编译器的修改：例如使用clang的前端

举例：Perses

  • 在程序的解析树上从根节点开始遍历尝试删除节点
  • 并不能考虑某个特定语言的特征

本文工作

  • Type Batched

    • 根据解析树的结点类型删除一个节点

      为什么要这样？因为删除某种类型的节点可能会导致出错概率提升从而拖慢效率

    • type顺序的选择：计算跑oracle的期望(如果删掉能省更多的检查次数，那就先删这个)，概率则是先验给出来的

  • Joint Batched

    • 由于同一类型的点可能相互有关系，因此这种策略会把某种节点全删，如果删完后oracle失败，则会更新概率，重新计算期望以重做joint（这里我感觉是重做type？因为更新了这种type的期望）

JVM testing

Java Runtime Machine，执行java字节码，由于JVM的复杂性，因此对其做测试和保证其正确性时重要的

用fuzz的方式对其做测试

  • 生成不同的输入
  • 差分测试，看在不同的JVM实现上结果有什么不一样

JavaTailor

  • Synthesis-based generation，随机将JVM bug case(过去的bug，现在可能已经被修复了)的代码剪切然后拼接，修复可能的语法错误（Synthesis），执行代码
    • 但是随机选取可能效率比较低，因为代码段的特征可能会相似，diversity不够好

Vectorizing Program Ingredients for Better JVM Testing（ISSTA’23）

  • 代码段语义层次聚类（hierarchy clustering）

JITfuzz: Coverage-guided Fuzzing for JVM Just-in-Time Compilers

针对JVM的设计理念来做fuzz

JIT可以做一些优化，例如函数的内联优化，小代码的优化(e.g. x/2 => x<<1)，聚合类型的标量优化(例如把struct用可以开在栈上的int啥的代替)

  • 目前没什么针对JIT的测试，大多都是针对JVM的

  • 做的方法和测试C compiler的差不多，mutation based fuzzing

    不是 mutation testing，那个是将错误代码插入到被测代码中，以验证当前测试用例是否可以发现注入的错误。

  • 六个mutator

    • function inlining：将x op y这样的代码替换为调用小函数以触发JIT的inline检查
    • simplification：将代码弄复杂
    • ……