系统软件转换规则的自动推理

系统软件转换规则的自动推理卢卡斯·塞拉诺引用此版本：卢卡斯·塞拉诺。系统软件转换规则的自动推理。软件工程[CS.SE]。索邦大学，2020年。英语。NNT：2020SORUS425。电话：03987546v2HAL ID：电话：03987546https://theses.hal.science/tel-03987546v2提交日期：2023年HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire从示例自动推断系统软件转换规则卢卡斯·塞拉诺评审团成员：Tegawende F.BISSYANDÉ，卢森堡大学高级研究科学家MartinMONPERRUS，KTH皇家理工学院正教授AntoineMINÉ，索邦大学考官正教授Valérie ISSARNY，Inria考试员高级研究科学家Jean-Rémi FALLERI，波尔多大学副教授，Inria考试员Julia LAWALL，高级研究科学家，Inria主管iii摘要Linux内核现在存在于所有类型的这种环境的多样性为然而，为了引入新功能，或者出于性能或安全原因，有时需要修改一些内部编程接口（API），这可能涉及对使用它们的数千个驱动程序本文提出了一种新的方法Spinfer，它允许自动执行这些API迁移 这种新方法基于遵循控制流约束的模式组装，能够从示例（即使是不完美的示例）中学习适合于Linux内核中API使用迁移挑战的转换规则。摘要Linux内核现在存在于各种计算环境中，从智能手机到超级计算机，包括最新的硬件和这种环境的多样性是以专用于设备驱动程序的大约100万行代码的大代码量为代价的。然而，为了添加新功能，或者出于性能或安全原因，一些内部应用程序编程接口（API）可能会被重新设计，从而触发使用它们的潜在数千个驱动程序的更改需求。本文提出了一种新的方法Spinfer，它可以自动执行这些API使用更新。 这种新方法基于由控制流关系约束的模式装配，可以从即使是不完美的例子中学习变换规则。 学习到的规则适用于Linux内核API使用更新中发现的挑战。v谢谢你论文是一个漫长的冒险3年，有时更长，充满了工作，但最重要的要在不放弃的情况下进行这样的冒险，一个人必须被很好地包围。 我还要感谢我的同事们，我和他们度过了非常美好的首先，从老前辈开始：安托万，达米安和塞德里克，他们今天向我们展示了然后是Redha和Darius，我和他们分享了论文中最精彩的时刻，当然是写作和行政程序，但也有很多笑声和超现实的最后是皮埃尔，最小的孩子，我祝他在未来的两年里好运还要感谢我在实验室的同事和朋友：Hakan、Ilyas、Saalik、Jonathan、Francis和Arnaud，我和他们一起我还要感谢Julien在我最需要的时候提供的分析和建议感谢我的家人，他们给了我坚定的支持，感谢我的朋友，他们中的许多人也经历过，感谢他们的支持和建议，也感谢所有这些共同的快乐时刻，帮助我坚持在最后，如果感谢你这些年来一直陪伴和跟随我，感谢你总是迅速回答我所有的问题，即使我在不太可能的最后，感谢你教会了我，科学上的拒绝并不是对我们工作的拒绝，我还要感谢Gilles、Lingxiao、David、Ferdian和Stefanus，在我的工作过程中，我有幸与他们进行了vii内容。1引言12了解API使用更新转换52.1什么是API使用更新转换？.............................................................................. 52.2如何描述转换？................................................................................................. 62.2.1当差异还不够时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从转换实例中提取信息283.1.3创建和应用转换规则313.2半自动推理和建议373.3从示例中推断其他变换383.4结论394捐款414.1技术选择414.1.1有多少例子？.......................................................................................414.1.2转换语言424.2概述434.2.1激励示例434.2.2将规则转换为规则片段的集合4.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 RQ3：短缺。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...945.3讨论。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...1005.3.1有效性。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 1015.3.2结论和未来工作。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 1016结论1036.1未来工作1036.2前景104参考书目107ix八1引言1从最大的超级计算机到最小的嵌入式设备，Linux内核出现在各种各样的平台上。这些目标的多样性是以多年来稳步增长的代码规模为代价的，到2020年初，仅专用于设备驱动程序的代码就达到了1200万行。驱动程序代码使用内核内部应用程序编程接口（API）与Linux内核的其余部分进行交互，API定义了公开可用的内核函数列表。 设计操作系统内核的复杂性和不断考虑新需求的需要意味着必须经常重新审视内部接口的设计，从而触发了这些接口的用户之间可能影响整个源代码树的重复更改的需要。 由于源代码树中维护的驱动程序必须保持功能并自行删除，因此更新或替换API所需的更改的大小和数量可能会阻止Linux内核开发人员这样做。愿意执行这些更改的开发人员可能会在受影响的文件子集上引入新的错误或仅执行更改，要求过时的API仅被弃用，而不是被删除。为了帮助开发人员执行这些大规模的更改，需要自动化。一只手，专门针对Linux内核的半自动工具已经开发出来。自2008年以来，自动C代码转换工具Coccinelle[LM18]一直是Linux内核开发者工具箱的一部分，用于自动化内核代码的大规模更改。Coccinelle提供了语义补丁的概念，允许内核开发人员使用类似补丁的[MES03]（即，类似Diff-like）语法。在提供语义补丁后，Coccinelle会自动跨代码库应用规则。今天，即使Coccinelle被Linux社区广泛采用，在Linux内核提交历史中仍然有大规模的更改没有使用它，因为编写语义补丁并不容易。另一方面，软件工程社区已经开发了许多通过从示例中学习转换来执行完全自动API使用更新的工具然而，这些工具中的绝大多数都以Java代码为目标，没有一个能够解决Linux内核的转换挑战2第一章引言在本文中，我们通过一组更新示例来解决自动学习Linux内核API使用更新的挑战本研究的贡献• 转化性不孕症困难的分类，分为五类挑战。• 代码更改的控制流表示。• 一种代码聚类方法，优化为在转换中聚类相似的变化。• 一种新的学习代码转换的方法，它关注控制流关系并生成可读的转换规则。• 我们的方法的开源实现称为SPINFER。1• Linux内核中转换挑战分类的评估• 对我们在Linux内核中学习真实代码转换的新方法的评估本文档的其余部分组织如下：第2章描述了API使用更新转换的特征，并提出了转换推理挑战的分类;第3章描述了从示例中学习转换的最新技术;第4章介绍了我们在这一领域的方法;第5章评估了我们在Linux内核转换方面的方法;最后，第6章结束了本文。更准确地说：• 第 2章 首先定义了什么是 API 使 用 的更 新 转 换 ，以及如何使用语 义 补 丁 语 言（SmPL）准确地描述它们。然后，它提出了本论文的第一个贡献，一个分类的不孕症挑战组织成多个类别的不孕症困难。• 第三章首先介绍了现有的自动化学习方法--从例子中的转换。对于每种方法，我们根据分类学分析了其不孕能力。然后，本章介绍了半自动API使用更新推理中的其他相关工作，以及学习其他类型转换的相关工作。1来源：https://gitlab.inria.fr/spinfer3• 第四章通过多个例子详细介绍了我们的学习转化方法我们从描述如何将输入示例表示为控制流图中的修改然后，我们将看到如何在这些修改中聚类术语，以形成表示多个具体术语的抽象。接下来，我们将详细介绍如何使用示例中的控制流属性组装抽象。最后，我们描述了如何用语义补丁语言从抽象集合获得补丁。• 第5章评估了我们推断真实Linux内核更改的方法。 我们分析了多个指标，以描述我们的方法如何很好地涵盖了将要进行的更改，并分析了我们的方法的一些失败之处。 我们还将我们的方法所包含的语义补丁与人工编写的语义补丁进行了比较，并分析了我们的方法的有效性。• 第六章以我们的工作和发现的总结结束本文我们讨论了我们的方法的优点和缺点，以及补充这种方法的未来工作。然后，我们将对自动化软件维护的未来提出一些展望5了解API使用2更新转换在本章中，我们将尝试了解API使用更新转换的内容以及这些转换带来的挑战。为此，我们将首先了解什么是API使用更新转换，然后了解如何在不使用自然语言描述的情况下准确描述代码转换，最后了解这些API使用更新带来了哪些挑战。2.1 什么是API使用更新转换？我们希望从中推断出的转换通常称为附带演进、系统编辑、API迁移或API使用更新。在软件工程文献中可以找到这些术语的多个定义：• 附 带 演 进 是 指影 响 通 用 库 细 节 修 改 的 接 口 的 演 进 . . 在所有库客户端中"[PLM07]。• 系统性编辑是指"在多个上下文中包含相似但不相同的程序更改"[MKM11]。• API迁移[LSC18]和API使用更新[FXO19]是由于所使用的API的方法1已更改、删除或弃用而导致客户端代码中出现的更改。所有这些术语都有一些不同之处，但总的来说，它们都指的是同一个概念：由于公共接口中的更改，在许多地方必须发生的一组类似的转换。 在本文中，我们将主要使用术语API使用更新，因为在我看来，它是最容易理解的术语。重复性更改（如API使用更新）可以代表项目中所做更改或软件组中所做更改的很大一部分。[1]这两篇引用的论文都针对Java，其中APIs来自对象方法，但这个定义也同样适用于非对象编程语言的函数形式API。6第二章了解API使用更新转换使用相同的API。 例如，Ray等人。[Ray+15]发现Linux内核中至少有12%的更改是非唯一的。 Nguyen等人[Ngu+13]发现Java项目中最小的更改是高度重复的，并且可以自动执行或推荐转换的方法有利于处理这些更改。此外，对于API使用更新，未能执行这些转换可能会导致所用API的大量碎片和弃用APIs的使用，这可能会带来安全风险。最近一项关于Android应用程序中Android API弃用的研究[MRK13]发现，平均而言，在任何时间点，超过四分之一的AndroidAPI使用在所研究的应用程序中被弃用。关于同一主题的另一项研究[Li+18]发现，一些Android APIs在文档中没有正确标记为弃用，或者在源代码中没有正确注释，从而防止代码分析器发出弃用警告。既然我们对我们想要学习的转换类型有了更多的了解，我们将学习如何准确地描述它们。2.2 如何描述转换？2.2.1 当差异不够时软件开发人员已经习惯于使用GNU-Diff报告（也称为简单差异）来描述转换。GNU-Diff "逐行比较两个文件，查找不同的行组，并报告每个不同的行组"[MES03]。Diff用于报告同一文件的两个版本之间的更改，并且通常与GNU修补工具结合使用，该工具"获取Diff生成的输出的比较，并将差异应用于原始文件的副本，生成修补版本"[MES03]。 Diff可以准确地描述2017年Linux内核中发生的以下API使用更新[Coo]中的转换实例：12345678如果（! 错误）{-我的名字是[]。+setup_timer（&ns_timer，ns_po lll，0UL）;ns_timer.expires=jiffies+NS_POLL_PERIOD;-N_TIMER. data=0UL;-N_TIMER. fuunction=ns_poll;add timer（ns_timer）;72.2如何描述转换？1#ifdefS_POLL_FREQ2-init_ti mer（dev->timer）;3-dev->timer. daa ta=（unsignedlong）dev;4-dev->timer. function=fs_poll;5+setup_timer（dev->timer，fs_pol ll，（unsignedlong）dev）;6dev->timer. expires=jiffies+FS_PO LL_FREQ7ad_timer（dev->timer）;8#ENDIF这两个差异描述了一个转换的两个实例，该转换将过时的init_timer的使用更改为支持较新的settup_timer，这两个函数初始化了用C语言编写的低分辨率计时器结构由于settup_timer已经负责初始化此结构的两个字段（即函数和数据），因此将删除先前的初始化，并将其值用作settup_timer的第二个和第三个参数。我们刚刚看到的差异是对相同变换的实例的描述，删除了以minus开头的行，并添加了以plus符号开头的行。但是，它不足以描述相同API使用更新的所有转换实例。事实上，一个diff只描述整行上的操作，而且一个diff不太可能描述同一变换的其他实例，因为它们需要以完全相同的顺序具有完全相同的行。由于每个实例都有不同的变量名、空格等，因此所呈现的两个差异将仅匹配两个特定实例。相反，我们对变化的解释描述了一般的转换，而不仅仅是一个转换的实例，但由于它使用的是自然语言，英语，它可能有一些歧义，计算机不容易理解。这里缺少的是一个可以准确描述人类和计算机的完整API使用更新的2.2.2 转换语言：SmPL2007年，Padioleau等人引入了语义补丁语言（SmPL）[PLM07]，这是一种用于指定Linux内核中的附带进化的声明性转换语言。2SmPL是为Linux内核转换而构建的，但它可以描述任何C代码的转换8第二章了解API使用更新转换SmPL背后的想法是以通用的方式描述转换，以便相同的转换描述（也称为语义补丁）应用于多个转换实例。通过使用接近传统差异的语法，SmPL既可以被人类轻松理解，也可以被自动化工具轻松解析。这种语言与甲壳虫引擎[P ad+08;Bru+09]一起出现，后者将语义补丁和C源代码作为输入，然后搜索代码以找到语义补丁所描述的转换的合适位置。 如果找到位置，Coccinelle可能会为所有转换实例生成差异或就地修改代码。现在，我们将看到SmPL语言的一些核心概念，下面的语义补丁在我们之前看到的定时器上执行相同的转换：1234567891011清单2.1：init_timer更改的语义补丁结构匹配和替换SmPL的第一个核心概念是一个匹配和替换语法，它关注代码的结构而不是语法，忽略换行符、空格和注释中的更改上一个语义修补程序的以下部分说明了这一45678@@expressionT，D，F;@- IIIT_TI MER（+setup_timer（T，+F、D）;...-T. data=D;-T. function=F;我是我的（+setup_timer（T，+F、D）;92.2如何描述转换？本示例描述了一个转换，该转换将任何init_timer函数调用更改为settup_timer，在添加两个新参数时保持第一个参数当传递到Coccinelle引擎时，语义补丁和要匹配的代码都被转换为抽象语法树（AST），允许在不考虑空间和样式差异的情况下进行匹配和替换。 这允许我们的示例语义补丁匹配我们的两个转换实例，即使每个实例具有不同的间距。我们可以看到，结构匹配允许语义补丁在细粒度级别上关注所更改的内容。在我们的语义补丁中，读者可以清楚地看到，即使函数调用的函数名更改了，第一个参数&T也保持不变。这种结构匹配的另一个结果是，与diff相反，语义补丁中描述的所有代码都必须是有效的C代码，除了我们将要看到的一些特殊的SmPL语法。可变形间距和编码样式是转换实例之间差异的一个来源，而另一个主要来源是变量名和表达式值。 例如，我们的每个转换实例都使用不同的术语来表示计时器结构：第一个使用ns_timer变量，第二个使用dev->timer表达式。对于可能只对一个实例本地的抽象术语，SmPL引入了另一个概念：元变量。元变量是类型化抽象，可以表示常量、表达式、标识符、语句等各种内容。元变量在语义修补程序（称为标头）开始时声明，以将其与实际术语区分开来。语义修补程序标题的以下部分声明了表达式类型的3个元变量：123两个连续的at-signs@@标志着语义修补程序的头部分的开始和结束@@expressionT，D，F;@