软件动态更新技术

好久没有发文章介绍我们的工作了 (这次是几个工作的合集)。TL;DR，看下面的动图就行了。

0. “软件不软”

什么是软件？大家肯定会给出自己的回答。根据 Wikipedia, Software is “a collection of instructions and data that tell a computer how to work”；我自己喜欢的解释则是 “人类世界需求在计算机世界的投影”。但软件为什么是软的呢——当然是因为和硬件相比，它看不见摸不着，所以取一个 “反义” 的名字，就叫软件好了。

然而，软件既承载了人类世界的需求，还是纯粹的逻辑制品，非但不 “软” ，而且还很硬、很脆 (脆弱)，稍有偏差就会全盘崩溃。

相对应的，“软” 的东西具有适应外部变化的弹性。我们组 (南京大学计算机软件研究所) 的两代博士生，一个是我的师兄，一个是我的师弟，整了十年 “软件动态更新” 的研究，就是希望能使软件具有一定的 “适应性”，至少可以在发现问题以后更及时地完成问题的修复。

​两个博士，竟然都读了 7 年！好在他们都已经 (或者即将) 走上人生巅峰。让我们看看都发生了什么。

1. 软件的动态更新

无论是修复 bug/漏洞还是添加新功能，软件都需要更新。

如果软件更新能不中断服务，就能让我们等的少一点——这就是 “不停机” 的动态更新 (Dynamic Software Update, DSU) 技术做的事情，也许你用过 Ksplice [1]/Kpatch [2] 更新 Linux 内核或 JRebel [3] “热部署”，Android app 也有类似的框架 [4-6]。听起来很像是黑科技对吧？我们来看看这是怎么做到的。

2. 实现动态更新

换轮胎的过程可以对应到软件更新维护领域中。为了修复程序中的漏洞、增加新功能，开发者准备了一个新的版本。而当前旧版本的程序正在运行，提供服务。该怎么更新到新版本呢？好办，只需要在旧的代码上贴一个 “补丁” (真的是补丁)，利用一条跳转指令就行。

​我们只要算一下新旧函数地址差异的 offset (假设在 32-bit 整数范围内)，然后把需要更新的代码入口的指令改了就行：

struct jmp {
  uint32_t opcode: 8;
  int32_t  offset: 32;
} __attribute__((packed));
​
#define JMP(off) ((struct jmp) { 0xe9, off - sizeof(struct jmp) })
​
static inline bool within_page(void *addr) {
  return (uintptr_t)addr % PG_SIZE + sizeof(struct jmp) <= PG_SIZE;
}
​
void DSU(void *old, void *new) {
  void *base = (void *)((uintptr_t)old & ~(PG_SIZE - 1));
  size_t len = PG_SIZE * (within_page(old) ? 1 : 2);
  int flags = PROT_WRITE | PROT_READ | PROT_EXEC;
​
  if (mprotect(base, len, flags) == 0) {
    *(struct jmp *)old = JMP((char *)new - (char *)old); // **PATCH**
    mprotect(base, len, flags & ~PROT_WRITE);
  } else {
    perror("DSU fail");
  }
}

上面的代码有点绕；不过绝大部分都是为了下面这句 “打补丁” 做的铺垫：

*(struct jmp *)old = JMP((char *)new - (char *)old);

它把旧函数的第一条指令 patch 成一条向新版本函数的跳转指令。换轮胎的技术有了，让我们把车开起来遛遛。让我们随便写点代码：

void foo()     { printf("In %s();\n", __func__); }
void foo_new() { printf("In updated %s();\n", __func__); }
​
int main() {
  foo();
  DSU(foo, foo_new);
  foo();
}

然后神奇的事情就会发生：你将会看到两次 foo() 会调用到不同的函数！

在实际中如果要实现上面的动态更新，会遇到稍稍多一点的麻烦。比如，foo() 可能被 inline 到 main 函数里，这样我们 patch 它的入口地址就没用了。具体到上面的例子，如果你把 foo 和 main 放到同一个文件里，然后来一个 -O2 的编译选项，我们的 DSU() 就没用了。这种情况的处理请大家移步 EuroSys'09 的 KSplice，KSplice 被 Oracle 收购在当时还算是个挺大的新闻，毕竟程序员不靠风口实现财富自由的还真是少数。在用到 Kernel 之前，Michael Hicks (现在是 UMD 的教授) 凭借他的博士论文 “Dynamic Software Updating” 获得了 2002 年的 SIGPLAN Dissertation Award，这两位算是 DSU 的开山鼻祖了。

总体来说，在动态更新的时候改代码并不算太困难。如果是 managed runtime，改代码还会更容易一些，因为解释器和 just-in-time 的编译器都天生支持代码替换 (编译模式的代码可以 deoptimize)。

要说 “实现动态更新”，就不得不提一提我们第一位博士，顾博的工作。

Javelus [7] 是一个具有在线更新功能的 Java 虚拟机，基于工业界标准的 OpenJDK 8 定制实现。类比“边开车边换轮胎” (友情提示：开车不换胎，换胎不开车！)：

​旧版本软件在 Javelus 上运行时，Javelus 负责监听更新指令。在收到请求后，Javelus 监控旧版本软件的运行：

• 在合适的时机 “启动更新”，比如路面平整、速度稳定时才可换轮胎
• 挂起旧版本软件的运行，然后把旧版本软件状态更新到新版本状态，比如替换目标轮胎时，必须让其不再运动才可进行
• 执行对状态的更新，需要处理已加载代码、堆区对象、方法栈区和程序计数器等。这算是真正 “换轮胎”
• 更新结束后，恢复新版本软件的运行

这玩意听起来容易整起来难 (break 了 JVM 内部实现的很多假设)。毕业之后，系统所有的 bug 都成了 feature，没有人敢动了。

3. 软件动态更新的困难

软件动态更新里的另一个问题是代码的修改可能会触发数据的变化：

class Foo {
  List<Integer> xs = new ArrayList<>();
  void foo() { xs.add(1); } 
};
class Foo$Update {
  List<Integer> xs = new LinkedList<>(); // 注意列表的类型变了
  void foo() { xs.add(1); }
};

在这两份代码里，foo 方法的代码 (以及编译后的字节码) 是完全一样的，就一条 invokeinterface：

iconst_1
invokestatic Integer.valueOf
invokeinterface List.add

这时候，动态更新就需要很小心地进行了：

1. 必须在合适、安全的时候才能更新。通常是与更新的数据相关的方法不在栈上时才能更新。
2. 必须对对象作出准确的转换：

void transform(Foo $old, Foo$Update $new) {
  $new.xs = new LinkedList<>();
  for (Integer x: $old.xs) {
    $new.xs.add(x);
  }
}

大家对动态更新都闻所未闻，更别说要做状态转换了。我们组的两代博士生整了十年就搞了这么一件事！我 (jyy) 居然同时参与了这两份工作 [8,9]。我在苦劝顾博不要那么搞的时候提了第二种方案，终于送皂博毕业。

4. 动态更新中的数据转换

在摸爬滚打 paper 被 reject 一万次以后 (其实是顾博不听我话，一定要剑走偏锋做 execution synthesis)，我们学会了做研究的套路——技术不好做，我们可以做 Empirical Study 啊！

那中论文的秘诀是什么呢？当然是挑最脏最累的活干了，别人不愿意干的事情我们干了，那功劳也是我们的啊 。我们把刀架在皂博脖子上，让他找来了 Tomcat-8 的整个维护历史 (相对稳定的应用服务器，更新大部分是 evolutionary 的而不是 revolutionary 的)，从里面随机挑选了 100 个 commit 里的 class changes，好消息是几乎所有的 class changes 都可以动态更新，但其中 11% 是需要复杂的转换函数的，而且对于 Tomcat 这种复杂的系统，已有的工作无法搞定。机会就来了。

所谓复杂的转换函数，首先不如一个完整的软件系统复杂，这就使得自动合成是有可能的；但是也不如“复制、粘贴”那样简单，这就使得自动合成依然非常困难。在调研过程中，我们深入地阅读了软件的代码，发现这些复杂转换函数中的基本操作，大部分已经存在于软件的代码中了。如果我们能从软件代码中找出这些基本操作，然后以合适的方式进行组装，就有机会生成正确的转换函数。还是以换轮胎举例，换的过程包括下列几个操作：

1. 逆时针拧轮胎螺丝
2. 卸下旧轮胎
3. 放上新轮胎
4. 顺时针拧轮胎螺丝

这几个操作不如 “用零件组装一台新车” 那样复杂，但比 “把坐垫翻个面” 复杂多了。这 4 步基本操作，已经存在于 “用零件组装一台新车” 的过程中了。我们需要做的，就是找出这些基本操作，然后以合适的顺序进行组装。

继续干脏活！带着这个观察，我们继续对 Tomcat 进行调研，结果发现对于最复杂的那些转换函数，也有 91.5% 可以用原程序 (方法调用、值域访问、代码片段) 里裁出的片段拼接而成。这样的发现给了我们更多的信心，去实现一个自动化方法。

其实这个想法早在 2013 年，jyy 的第一篇 paper 还没发表的时候，就被顾博在一定程度上提出了。只不过他要死磕 static slicing，我也是好言相劝说不靠谱，他硬要上，这份工作才到 2021 年才整出来。

为了把代码 “粘起来”，我们就需要一个胶水语言。

不用怕，即便你不读它，也会觉得它不太像一个正经的编程语言——它的语言成分实在太少，完全是为了 “胶水” 设计的：

• 没有运算！没有运算！没有运算！加减乘除、布尔逻辑，统统没有
• 赋值要么是变量，要么是已有的代码片段
• if 和 while 的条件基本只能是已有的代码片段或者 null check

然后配合我们从代码里挖出的，带 “洞” 的小片段 ( )：

把这些 里的洞用变量填上，就得到了一个可能的状态转换函数。

还是以换轮胎举例，我们的方法从 “用零件组装一台新车” 过程中抽取了很多操作的小片段 (和换轮胎有没有关系的都会被提取)：

合成换轮胎操作的过程，就是从小片段集合中逐个取出带 “洞” 的小片段，然后填空，接着跑一下测试用例，看目标任务 (例如换轮胎) 是否能正确完成。比如我们可能会合成出以下操作序列：

最后得到程序 { 把[新轮胎]翻个面；顺时针拧[方向盘]；}

上述过程合成的内容明显无法完成 “换轮胎” 任务，因此我们的方法会合成新的操作：

得到程序：{ 逆时针拧[轮胎螺丝]；卸下[旧轮胎]；放上[新轮胎]；顺时针拧[轮胎螺丝]；}

上面的程序通过了测试，就是一个可能合格的状态转换函数啦！我们暴力地穷尽所有可能的程序，直到找到一个能通过测试用例的——对于一次更新而言，大约有 的搜索空间。经过不懈地调优 (其实是比较聪明的算法，度量转换函数的 complexity 和 naturalness)，PASTA 可以为 15 个类更新生成正确的转换函数，而其他两个工作，AOTES [9] 和 TOS [10] 分别只成功了 2 个和 0 个。写了一万多行代码，投了两次 (经历了一次算法的大重整)，终于修成正果。

5. 故事的结局

顾博的 paper 最后发表在了 ECOOP'18 [9]。不过那时候他已经毕业远走高飞去了遍地是黄金的硅谷。我倒是获得了去阿姆斯特丹游玩的机会，遗憾的是怕一个人在街上失态，没有敢吃蘑菇。

皂博的 paper 发表在了 ICSE'21 [8]，运气爆炸的他还同时获得了 ICSE'21 (CCF-A) 的 “杰出论文奖” 和 “唯一最佳论文奖”，大家平分了 1000 欧元奖金。获奖的过程也挺有趣，本来 rebuttal 的时候是三个 4 分 (Accept)，照道理是和 best paper 无缘的。结果有一个问了十几个问题的 reviewer 问我们和 PL 领域大热的 program synthesis 到底有什么区别，我就顺势推了一把，说我们是反着 synthesis 做的，不要 generalizability，的确有点眼前一亮，最后这个 (和另一个) Reviewer 给了 “Award Quality”。

论文/工具代码/reproduction kit (docker image) 可以在 https://zelinzhao.github.io/pasta/ 获得。

参考文献

[1] Jeff Arnold, M. Frans Kaashoek. Ksplice: Automatic Rebootless Kernel Updates, EuroSys 2009

[2] Kpatch. https://en.wikipedia.org/wiki/Kpatch

[3] JRebel. https://www.jrebel.com/

[4] AndFix, Alibaba. https://github.com/alibaba/AndFix

[5] Tinker, Tencent. https://github.com/Tencent/tinker

[6] Robust, Meituan. https://github.com/Meituan-Dianping/Robust

[7] Tianxiao Gu, Chun Cao, Chang Xu, Xiaoxing Ma, Linghao Zhang, Jian Lu. Javelus: A Low Disruptive Approach to Dynamic Software Updates, APSEC 2012

[8] Zelin Zhao, Yanyan Jiang, Chang Xu, Tianxiao Gu, Xiaoxing Ma. Synthesizing Object State Transformers for Dynamic Software Updates, ICSE 2021

[9] Tianxiao Gu, Xiaoxing Ma, Chang Xu, Yanyan Jiang, Chun Cao, Jian Lu. Automating Object Transformations for Dynamic Software Updating via Online Execution Synthesis, ECOOP 2018

[10] Stephen Magill, Michael Hicks, Suriya Subramanian. Automating Object Transformations for Dynamic Software Updating, OOPSLA 2012