Posted on

PaperStudy Learning from Mistakes

Created by: N1rv0us Zhang
Created time: May 26, 2024 11:08 AM
Tags: appreciate, concurrent, non-professional, paper, system

序言

上周回长沙和我的恩师们约饭交流，席间陈老师反复提到了 YY 团队的一篇经典论文；说来惭愧，本科期间认真学下来的论文两个手都能数完，自然是没读过这篇 paper。但老师对这篇 paper 的讲述，我感觉一些场景，如BUG的发现、RCA(Root Cause Analysis), 确实能对我目前的一些工作有一些启发。

回北京后，趁着周末闲暇的时间，再次找陈老师要到了这篇 paper 的原文。以我目前的状态，很难对一篇操作系统领域的经典论文有很深的理解，但希望能管中窥豹，学得一些优秀的 idea.

那么本次学习的 paper :

Learning from Mistakes — A Comprehensive Study on Real World Concurrency Bug Characteristics

Abstract

本文重点研究并发软件的设计、测试以及出现的BUGs. 作者希望通过研究现实世界中出现过的bug 以及bug fix 找出并发软件设计过程中面临的实际困境。为此作者随机选取了几个经典的开源软件 ((MySQL, Apache, Mozilla and OpenOffice)中的并发 BUG 进行分析，汇总得出以下几条结论：

  • 结论汇总
    1. Around one third of the examined non-deadlock concurrency bugs are caused by violation to programmers’ order intentions, which may not be easily expressed via synchronization primitives like locks and transactional memories; (BUG原因 : 设计预期)
    2. Around 34% of the examined non-deadlock concurrency bugs involve multiple variables, which are not well addressed by existing bug detection tools; (BUG原因 : 关联变量)
    3. About 92% of the examined concurrency bugs can be reliably triggered by enforcing certain orders among no more than 4 memory accesses. This indicates that testing concurrent programs can target at exploring possible orders among every small groups of memory accesses, instead of among all memory accesses; (测试与BUG 检测效率)
    4. About 73% of the examined non-deadlock concurrency bugs were not fixed by simply adding or changing locks, and many of the fixes were not correct at the first try, indicating the difficulty of reasoning concurrent execution by programmers. (BUG Fix)

Contributions

(特别备注本文发表自 2008 年)

过于对于并发软件的研究集中在以下三个领域内，有很多不错的成果，但是仍有一些悬而未决的困难：

  1. Concurrency bug detection
  2. Concurrent program testing and model checking
  3. Concurrent programming language design

作者针对几个经典开源软件的并发BUG进行 Case Study 之后，得出如下结论：

Untitled

  • 对于 Bug Patterns 研究的发现和启发：
    • 97% 的非死锁 BUG 都可以归因于两种模式：atomicity-violation 和 order-violation. 对于并发bug检测的研究可以重点针对这两种模式；
    • 在所检查的非死锁错误中，约有三分之一（32%）的错误属于顺序违反错误，需要新的并发错误检测工具来检测顺序违反错误。
  • 对于 Manifestation 研究的发现和启发 :
    • 96% 的非死锁 BUG可以通过强制控制两个线程的执行顺序来触发，Pairwise testing 可以很好的检出大部分并发 BUG 并且较少测试的复杂程度；
    • 22% 的死锁 BUG 是单一线程在死等自己已经获取的资源，可以通过单一线程死锁检测来高效检出；
    • 66% 的非死锁并发 BUG仅关联单一共享变量， 34% 的非死锁并发 BUG关联了多个共享变量
    • 97% 的非死锁并发BUG包含两个线程循环等待最多两个资源；
    • 如果在不超过 4 次的内存访问中执行一定的部分顺序，几乎所有（92%）被检查出的并发错误都能得到保证。
  • 对于 Bug Fix Strategies 研究的发现和启发：
    • 四分之三（73%）的非死锁错误是通过添加/更改锁以外的技术修复的。程序员需要考虑正确性、性能和其他问题，以决定最合适的修复策略。
    • 61% 的死锁错误都是通过阻止一个线程获取一个资源（如锁）来修复的。这种修复方法可能会引入非死锁并发错误。
  • 对于 Bug Avoidance 研究的发现和启发：
    • Transactional memory (TM) 可以帮助避免约 39% 的BUG；
    • 由于 bug 模式问题，约 19% 的并发 bug 不能够被 TM 设计模式修复；

Methodology

并发BUG RCA 的样本选择与问题定义分类如下图，同时，作者将选取的 BUG 分为死锁BUG与非死锁BUG，由于这两个问题的检测方式，修复方案都不相同。

Untitled

整个研究围绕着三个并发BUG的概念：bug pattern, manifestation, and bug fix strategy

  • bug pattern dimension : 将非死锁并发错误按其根本原因分为三类 (atomicity-violation bugs, order-violation bugs and the other bugs)
  • manifestation : 研究了每个并发错误显现所需的条件，然后根据其显现条件涉及多少线程、多少变量和访问次数来讨论并发错误。
  • bug fix strategy : 同时研究了漏洞修复的最终 patch 以及修复过程中的一些 patch。并且验证了 transactional memory 是如何帮助程序员们避免此类bug。

Conclusions

首先是作者的：

对于 MySQL, Apache, Mozilla, and OpenOffice 现实并发BUG的Root Cause Analysis，在并发bug检测以及并发语言设计都有很不错的研究结果，同时也引导了下一步的研究方向；未来(对于 2024 年可能已经是过去了)的工作将会是多变量并发BUG检测工具或是指令顺序并发BUG检测工具的设计。工具将pairwisely test的方式测试。未来的论文也将持续关注其他现实Application中BUG 的 RCA.

再来是我自己对这边论文的一些思考和感受：

本文工作中的 RCA 部分与我日常工作中的CaseStudy相似，一些优秀的 RCA/CaseStudy 研究能够让我们更好的聚焦到一些同类问题的关键部分。配合后续的一些针对性的研究，不少同类型问题都可以在一定时间内得到收敛和解决。在这个方面 RCA 并不是一蹴而就的，而应当是周期内反复进行的。

作为一篇 RCA 的paper，对于并发BUG的分析和总结十分的精炼、明确。但是由于这篇研究已经是10多年前的了，及时对并发问题十分感兴趣也需要重新做 RCA 工作了。我阅读的重点也主要放在如何做一次优秀的RCA上。

总结下来，我感觉：

  1. 一次优秀的 RCA 应当是为让后续的相关研究指明一条清晰的道路；在本次paper的研究中，对于bug分类、参与线程数量、共享变量数量的统计结果，阐述了 90% 以上的问题都是具备一些共性的，通过这些特性针对性的做后续的研究以及工具的开发和设计能够极大的降低成本和提升效率；
  2. 一次优秀的 RCA 是以终为始的；在本次paper的研究工作中，对于目标的选取和研究的领域都是有提前的设计的。这让 RCA 成为了一个针对性的研究而非盲目的研究。最终在作者关注的领域内也得出了不错的结果和启示；
  3. RCA 选取的分析样本数量并不多，但是足够典型；作者选取了当年并发问题高发的现实软件(当然今天也很常用)的 100+ 个case。这让研究员可以认真的分析和分类，但样本量并不是很高，这也让我怀疑文中的百分比是否真的是有价值的 …
  4. RCA 需要阶段性的反复进行；这条并不是paper中写的，而是我的一些主观感受。由于 RCA 本身选取的样本并不是很高，而其结果又会让后续一段时间内的研究变得专注，我相信即使是天才研究员也没法保证每次的 RCA 得出的结论都是准确可靠的。为此阶段性的RCA就显得尤为重要，我们需要观察RCA指导下的后续研究是否有效的让一类问题得到了收敛以及上一个阶段RCA的结果在后续研究持续一段时间后结论是否依然可靠；

最后，还有一些与 paper 研究无关的感受：这篇 paper 的行文非常的不错，全文都在围绕着作者的研究 — 现实世界Application并发BUG的 RCA 展开；我对操作系统的理解顶多就是一般本科毕业生的水平，但通篇读起来并没有吃力的地方(也可能是 10多年前的技术如今已经普及的原因)。作为一篇安全研究员的拓展阅读，可以在 RCA 相关工作中给我一些启发；如果我想深入并发语言设计和并发BUG检测 Section 3-5 部分对细节的描述也值得反复推敲。

总之，这篇 paper 是值得拿来反复阅读的。由于我本身的工作并不是做并发相关的，我只是重点关注一篇优秀的 RCA paper 应当具备的品质。以后有机会深入了解软件并发，还会翻出来继续阅读的。

That’s all. Good night.

Word Study

  • prevalent : 普遍，常见，盛行；
  • notorious : 臭名昭著的；

Ref