Linux内核多样性下的软件转换规则系统

从实例中卢卡斯·塞拉诺引用此版本：卢卡斯·塞拉诺从实例中自动推断系统软件转换规则软件工程[cs.SE]。索邦大学，2020年。英语NNT：2020SORUS425。电话：03987546v2HAL Id：tel-03987546https://theses.hal.science/tel-03987546v22023年2月14日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire系统软件转换规则的实例卢卡斯·塞拉诺评审团成员：特加文德湾 B ISSYANDINST，卢森堡大学高级研究科学家，评审员Martin M ONPERRUS，KTH皇家理工学院正教授，评审员Antoine M INDINST，索邦大学正教授Valérie ISSARNY，Inria高级研究科学家Jean-Rémi FALLERI，波尔多大学副教授Inria高级研究科学家Julia LAWALLiii简历Le noyau Linux est aujourd这种多样性是为了建立一个由于引入了新的功能，或者为了性能或安全的原因，某些编程接口（API）内部确实存在很好的评论，这可能意味着对使用者的数百万飞行员进行了更改Cette thèse propose une nouvelle approche，Spinner，permettant这一新的方法，基于对控制约束的基元组合，能够在Linux中实现部分应用程序，甚至是不完善的应用程序接口迁移的转换规则。摘要Linux内核目前存在于各种计算环境中，从智能手机到超级计算机，包括最新的硬件和“古老”的这种环境的多样性是以大量代码为代价的，大约有一千万行代码专用于设备驱动程序。但是，为了添加新功能，或者出于性能或安全原因，可以重新设计一些内部应用程序编程接口（API），从而触发对使用它们的潜在数千个驱动程序进行更改的需求。本文提出了一种新的方法，Spinerse，可以自动执行这些API使用更新。 这种新的方法基于受控制流关系约束的模式组装，可以从甚至不完美的示例中学习转换规则。学习规则适用于Linux内核API使用更新中发现的挑战。v雷默西芒这是三年来的一次漫长的冒险，再加上，除了运动、检查和检查，还有上、下的工作为了更好地进行一次冒险，没有胸罩，他必须更好地进行。 我也很感谢我的同事们，因为我过得很好安托万、达米安和塞德里克都是古人的后代，他们今天在这里生活得很好当然，雷德哈和大流士，与我分享了一个最好的时刻，这是一个很好的理解，行动和行政程序，但也有很多愤怒和超现实主义的时刻最后一个小皮埃尔，他给了我两个人来这里的勇气。感谢我的同事和工作朋友：哈坎、伊利亚、萨里克、乔纳森、弗朗西斯和阿诺德，他们在咖啡馆里度过了非常美好的时光我很感谢朱利安，对我所做的分析和对我所经历的时刻的思考感谢我的家人，让我有了一个没有失败的支持，也感谢我的朋友，他们也很高兴，为了支持和帮助我们，也为了我们在这段时间里的快乐如果没有科学的研究，我就不可能找到这样的东西，而且我会感谢我的朋友谢谢你能陪我一起度过这几年，能很快回答我所有的问题，甚至我能在不太可能的时间里做到感谢我认为，拒绝科学并不是我们工作的结果，只是邀请了友好的人我感谢吉尔、凌霄、大卫、费尔迪安和斯特凡努斯，因为他们是我工作中的交换者和合作者，而且这些顾问都很有针对性vii内容1介绍12了解API使用更新转换52.1什么是API使用更新转换？.............................................................................. 52.2如何描述转型？................................................................................................. 62.2.1当Diff不足时62.2.2转换语言：SmPL72.3转型挑战分类112.3.1什么样的挑战.......................................................................................122.3.2控制流依赖性132.3.3数据流依赖性162.3.4更改每个函数的202.3.5变更变体222.3.6噪音232.3.7摘要.253技术水平273.1API使用更新273.1.1寻找相关实例283.1.2从转换实例中提取信息293.1.3创建和应用转换规则313.2半自动推理和建议373.3从实施例38推断其他变换3.4结论394捐款414.1技术选择414.1.1有多少例子？.......................................................................................414.1.2转换语言424.2概览.434.2.1激励性实例434.2.2转换规则作为规则片段的集合464.2.3变式.464.2.4摘要474.3改变474.3.1增强控制流图484.3.2控制流图差分514.4规则片段的识别534.4.1节点权重554.4.2噪声检测574.4.3集群584.4.4规则片断594.5组装规则片段614.5.1检查控制流依赖性624.5.2组装删除的图片段644.5.3分割语义补丁规则图664.5.4组装添加的图形片段684.6从规则图到语义补丁规则714.6.1处理元变量714.6.2SmPL序列运算符734.6.3从图形生成语义补丁规则744.7规则排序784.7.1语义补丁规则评估784.7.2规则排序和包容804.8结论825评价855.1方法。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .865.2提出研究问题。. . . . . . . . . . . . . . . . . . .875.2.1 RQ1：学习API使用更新。. . . . . . . . . . . . . . .875.2.2 RQ2：效率。. . . . . . . . . . . . . . . . . . . . . . . . .925.2.3建议问题3：短缺。. . . . . . . . . . . . . . . . . . . . . . .945.3讨论。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1005.3.1对有效性的威胁. . . . . . . . . . . . . . . . . . . . . . . 1015.3.2结论和今后的工作。. . . . . . . . . . . . . . . . . . 1016结论1036.1今后的工作1036.2观点104Bibliography参考书目107VIII1介绍1从最大的超级计算机到最小的嵌入式设备，Linux内核存在于各种各样的平台上。这种目标的多样性是以牺牲多年来稳步增长的代码大小为代价的，到2020年初，仅用于设备驱动程序的代码就达到了1200万行。驱动程序代码使用内核内部的应用程序编程接口（API）与Linux内核的其余部分进行交互，API定义了公开可用的内核函数列表。 设计操作系统内核的复杂性和不断考虑新需求的需要意味着内部接口的设计必须经常重新审视，从而引发这些接口的用户之间可能影响整个源代码树的重复更改的需要。 由于在源代码树中维护的驱动程序必须保持功能，并且很少被删除，因此更新或替换API所需的更改的大小和数量可能会阻止Linux内核开发人员这样做。愿意执行这些更改的开发人员可能会引入新的错误，或者只对受影响文件的子集执行更改，这需要过时的API只被弃用而不是删除。为了帮助开发人员执行这些大规模的更改，需要自动化 一方面，专门针对Linux内核的半自动工具已经开发出来。自2008年以来，自动C代码转换工具Coccinelle [LM18]一直是Linux内核开发人员工具箱的一部分，用于自动化内核代码的大规模更改。Coccinelle提供了语义补丁的概念，允许内核开发人员使用类似补丁的[MES 03]（即，类diff-like）语法。 给定一个语义补丁，Coccinelle会在代码库中自动应用规则。今天，即使Coccinelle被Linux社区广泛采用，Linux内核提交历史中仍然有大规模的变化，因为编写语义补丁并不一定容易。另一方面，软件工程社区已经开发了许多通过从示例中学习转换来然而，这些工具中的绝大多数都是针对Java代码的，没有一个可以针对Linux内核的转换挑战2第1章绪论在这篇论文中，我们解决了从一组更新示例中自动学习Linux内核API使用更新这项研究的贡献• 转换推理困难的分类，分为五类挑战。• 代码更改的控制流表示形式。• 一种代码聚类方法，经过优化，可对转换中的类似更改进行。• 一种新的学习代码转换的方法，专注于控制流关系并生成可读的转换规则。• 我们的方法的开源实现称为SPINFER。1• 对Linux内核中的转换挑战分类的评估• 我们的新方法学习真正的代码转换在Linux内核的评估。本文档的其余部分组织如下：第2章描述了API使用更新转换的特征，并提出了转换推理挑战的分类法;第3章描述了从示例中学习转换的最新技术;第4章介绍了我们在这一领域的方法;第5章评估了我们在Linux内核转换上的方法，最后第6章总结了这篇论文。更准确地说：• 第 2章 首 先 定 义 了什 么 是 API 使 用 更 新 转 换 ， 以 及 如 何 使 用 语 义 补 丁 语 言（SmPL）准确地描述它们。然后，它提出了这篇论文的第一个贡献，分类推理的挑战组织成多个类别的推理难度。• 第3章首先介绍了现有的自动方法学习transformation-tions从例子。 对于每种方法，我们分析其推理能力的分类。然后，本章介绍了半自动API使用更新推理的其他相关工作以及学习其他类型转换的相关工作1资料来源：https://gitlab.inria.fr/spinfer3• 第4章详细介绍了我们从多个示例中学习转换的方法我们首先描述如何将输入示例表示为控制流图中的修改然后，我们将看到如何在这些修改中聚类术语，以形成表示多个具体术语的抽象。接下来，我们将详细介绍如何使用示例中的控制流属性组装抽象。最后，我们描述了如何从一个抽象的集合到一个补丁的语义补丁语言。• 第5章评估我们的方法来推断真正的Linux内核的变化。 我们分析多个指标来描述我们的方法如何覆盖要进行的更改，并分析我们的方法的一些失败。 我们还比较了语义补丁推断我们的方法，人类写的语义补丁，并分析我们的方法的效率。• 第六章总结了我们的工作和发现。我们讨论了我们的方法和未来的工作补充这种方法的优点和缺点然后，我们将提出一些观点，自动软件维护的未来。5了解API用法2更新转换在本章中，我们将尝试了解什么是API使用更新转换以及这些转换带来的挑战 为此，我们将首先了解什么是API使用更新转换，然后如何在不使用自然语言描述的情况下精确描述代码转换，最后我们将看到这些API使用更新会带来什么挑战。2.1 什么是API使用更新转换？我们想要从中推断的转换通常被称为附带演变、系统编辑、API迁移或API使用更新。在软件工程文献中可以找到这些术语的多个定义：• 附带演化是“当影响通用库接口的演化需要修改时”发生的演化. . ]在所有库客户端中”[PLM 07]。• 系统性编辑是“由多个上下文的类似但不相同的程序更改组成”的修改[MKM11]。• API迁移[LSC18]和API使用更新[FXO19]是由于所用API的方法1发生更改、删除或弃用而在客户端代码中出现的更改所有这些术语都有一些差异，但一般来说，它们都指的是同一个概念：由于公共接口的变化，必须在许多地方发生的一组类似的转换。在这篇论文中，我们将主要使用术语API使用更新，因为它是，在我看来，最容易理解的一个。重复性的变更，比如API使用更新，可能代表了项目中所做变更的很大一部分，或者代表了一组软件中所做变更的很大一部分1引用的两篇论文针对的是Java，其中API来自对象方法，但这个定义也适用于非面向对象编程语言的函数形式的API。6第2章了解API使用更新转换使用相同的API。例如，Ray et al. [Ray+15]发现Linux内核中至少有12%的更改是非唯一的。 Nguyen等人[Ngu+13]发现Java项目中的大多数小更改都是高度重复的，可以自动执行或推荐转换的方法有利于处理这些更改。此外，对于API使用更新的情况，省略执行这些转换可能导致所使用的API的大量碎片以及可能潜在地表示安全风险的弃用API的使用。最近一项关于Android应用程序中Android API降级的研究[MRK13]发现，平均而言，在任何时间点，超过四分之一的Android API使用在所研究的应用程序中被弃用。另一项关于同一主题的研究[Li+18]发现，一些Android API在文档中没有正确标记为已弃用，或者在源代码中没有正确注释，从而阻止代码分析器输出弃用警告。现在我们知道了更多关于我们想要学习的转换类型，我们将看到如何准确地描述它们。2.2 如何描述转型？2.2.1 当Diff不够时软件开发人员已经习惯于使用GNU-Diff报告来描述转换，也称为diffs。 GNU-Diff“逐行比较两个文件，找到不同的行组，并报告每组不同的行”[MES03]。Diffs用于报告同一文件的两个版本之间的变化，通常与GNU补丁工具结合使用，该工具“采用diff产生的比较输出，并将差异应用于原始文件的副本，产生补丁版本”[MES03]。 Diffs可以准确地描述转换实例，例如2017年Linux内核中发生的以下API使用更新[Coo]：12345678如果（！error）{-iit_timerr（ns_timer r）;+setupp_ti mer（&ns_timer，ns_poll，0UL）;ns_timer.expires=jiffies+NS_POLL_PERIO D;-ns_timerr. data=0UL;-ns_timerr.function=ns_poll;anddd_timer（ns_timer）;72.2如何描述转型？1#ifdefFS_POLL_FREQ2-init_ti mer（dev->timer）;3-dev->timerr. data=（unsignedlong）dev;4-dev->timerr. function=fs_poll;5+setup_timer（dev->timer，fs_poll，（unsignedlong）dev）;6dev->timerr. expires=jiffiess+FS_POLL_FREQ;7add_timer（dev->timer）;8#endif这两个差异描述了一个转换的两个实例，该转换将弃用的init_timer的用法改为使用更新的setup_timer，这两个函数初始化一个低分辨率的计时器结构，用C语言编写由于setup_timer已经处理了该结构体的两个字段的初始化，即函数和数据，因此删除了先前的初始化，并将其值用作setup_timer的第二个和第三个参数。我们刚才看到的差异是对同一转换实例的描述，删除了以减号开头的行，添加了以加号开头的行然而，描述同一API使用更新的所有转换实例是不够的。实际上，diff只描述整行上的操作，并且单个diff不太可能描述同一转换的其他实例，因为它们需要以完全相同的顺序具有完全相同的行。 由于每个实例都有不同的变量名、间距等，因此所呈现的两个差异将仅匹配两个特定的实例。相反，我们对变化的解释一般地描述了变换，而不仅仅是变换实例，但是由于它使用自然语言英语，所以它可能具有一些歧义，并且不能被计算机容易地理解我们在这里缺少的是一个描述，可以准确地描述人类和计算机的整个API使用更新2.2.2 转换语言：SmPL2007年，Padioleau et al. 引入了语义补丁语言（SmPL）[PLM 07]，这是一种声明性转换语言，用于指定Linux内核中的并行进化。22SmPL是针对Linux内核转换而构建的，但可以描述任何C代码的转换8第2章了解API使用更新转换SmPL背后的思想是以一种通用的方式描述转换，以便相同的转换描述（也称为语义补丁）应用于多个转换实例。此外，通过使用接近传统diff的语法，SmPL变得既容易被人类理解，又容易被自动化工具解析。这种语言与Coccinelle引擎[Pad +08;Bru+09]一起提供，该引擎将语义补丁和C源代码作为输入，然后在代码中搜索语义补丁所描述的转换的合适位置。 如果找到了位置，Coccinelle可以为所有转换实例生成差异，或者就地修改代码。我们现在将看到SmPL语言的一些核心概念，通过下面的语义补丁来说明，它对我们之前看到的计时器执行相同的转换1234567891011清单2.1：init_timer到setup_timer更改的语义补丁结构匹配与替换SmPL的第一个核心概念是匹配和替换语法，它关注代码的结构而不是语法，忽略了换行符、空格和注释的变化前面语义补丁的以下部分说明了这一点45678@@expressionT，D，F;@@- init_timerr（+setup_timer（T，+F、D）;...-T. data=D;-T. function=F;-init_timerr（+setup_timer（T，+F、D）;92.2如何描述转型？此摘录描述了一个转换，该转换将任何init_timer函数调用更改为setup_timer，在添加两个新参数的同时保持第一个参数不变当传递到Coccinelle引擎时，语义补丁和要匹配的代码都被转换为抽象树（AST），从而能够在不考虑间距和样式差异的情况下进行匹配和替换。 这允许我们的示例语义补丁匹配我们的两个转换实例，即使每个实例具有不同的间距。我们可以看到，结构匹配允许语义补丁关注细粒度级别的变化在我们的语义补丁中，读者很清楚，即使函数调用的函数名改变了，第一个参数&T也保持不变。这种结构匹配的另一个结果是，与diff相反，语义补丁中描述的所有代码都必须是有效的C，除了我们将要看到的一些元变量间距和编码风格是转换实例之间差异的一个来源，另一个主要差异来源来自变量名和表达式值。例如，我们的每个转换实例使用不同的术语表示计时器结构：第一个使用变量ns_timer，第二个使用表达式dev->timer。为了抽象那些可能只属于一个实例的术语，SmPL引入了另一个概念：元变量。元变量是类型化的抽象，可以表示各种事物，如常量、表达式、标识符、语句等。元变量在语义补丁的开头声明，称为头部，以将它们与实际术语区分开来。下面是我们的语义补丁头的摘录，声明了3个表达式类型的元变量：123两个连续的at符号@@标记语义补丁的头部部分的开始和结束@@expressionT，D，F;@@10第2章了解API使用更新转换然后，在匹配和替换过程中重用元变量，如下所示。1011这将匹配并删除为任何表达式的数据和函数字段赋值的任何两个连续语句但是，用于数据赋值的表达式T必须与用于函数赋值的表达式T在语法上相同，因为它们使用相同的元变量名。序列运算符SmPL的第三个核心概念是序列操作符，它可以抽象出匹配项之间的任意代码。序列操作符的一个例子可以在我们的定时器转换语义补丁中找到，由... 符号，也称为椭圆：8910这个符号意味着它们可以在前一项（init_timer调用）和下一项（数据字段赋值）之间存在任意数量的语句（甚至是零）。在外行的术语中，序列运算符表示在匹配之前和之后的模式的术语之间可以存在任何东西（或什么都没有）。符号. 这个序列运算符还添加了一个约束，即... 必须在学期结束后... 在所有控制流路径中。可以在椭圆符号前面加上一个负号，以删除两个项之间的所有语句：12345椭圆符号也可以用来抽象其他序列，例如下面所示的函数参数123-T. data=D;-T. function=F;）;...-T data=D;@@@a）;- ......这是什么？anottherFunCall（）;@@@-foo（...）;112.3转型挑战这个小的语义补丁删除了对名为foo的函数的所有调用，而不管参数的数量最后，SmPL还定义<了…...> 而且<+... ...+> 序列运算符第一个“指示椭圆之间的模式将被匹配0次或更多次”，第二个“指示模式必须至少匹配一次”[Smp]。 这允许语义补丁描述需要捕获或删除模式任意次数的转换。同构最后一个概念是同构，它定义了语义上等价的术语，因此匹配一个术语与匹配另一个术语是一样的例如，如果X是一个指针，那么X == NULL并且！X是两个等价的表达式。这个概念使得能够将具有相同语义但具有不同结构的术语分组在一起，该结构仅取决于开发人员的编码风格。SmPL定义了一个同构列表，将具有相同语义的术语分组在一起使用同构组中的术语的语义补丁能够匹配该组中的总结通过独立于间距和样式的匹配，使用元变量抽象特定术语，使用序列运算符抽象任意序列和同构，语义补丁能够捕获转换而不仅仅是捕获转换实例。SmPL补丁可用于描述人类和计算机的转换。2.3 转型挑战既然我们可以用SmPL语言准确地描述代码转换，我们将看看推断这种转换的挑战当我们稍后查看现有技术时，我们将看到它们可以推断出一些API使用更新转换，但不是全部。 通过评估转型的挑战，我们将能够预测现有技术是否适用于哪些转型。