T Hesa德博士学位L’UNIVERSITÉ DE RENNES和科尔 D八角形第601章数学与信息与通信科学与技术专业由雨果·马丁用于巨型软件配置空间论文于2021年12月16日在雷恩发表并答辩研究单位：EquipeDiverSE，IRISA答辩前的报告员：Laurence Duchien里尔大学教授Julia LAWALL INRIA研究总监-巴黎评审团组成：请注意，如果评审团主席：伊莎贝尔·普奥雷恩大学教授检查员：劳伦斯·杜钦里尔大学教授朱莉娅·拉沃尔INRIA研究总监-巴黎伊莎贝尔·普奥雷恩大学教授克劳斯·施密德希尔德斯海姆大学教授Dir.论文：马修·阿彻雷恩大学教授共同导演。论文：让-马克·耶泽克雷恩大学教授3R总结法语中今天几乎所有的软件系统都在这些选项中的每一个都绑定到特定的代码部分，在虽然这听起来相对简单，只有几个选项，但一些软件程序会将数千个选项组合在一起，分布在数百万行代码中，使任务变得在过去的十年里，研究人员已经开始使用机器学习技术一个关键问题是预测这些软件的不同属性，例如任务的执行速度，这可能根据所使用的软件的配置而测量每种配置的特性可能是昂贵和复杂的，在最极端的情况下甚至是不可能的。创建已经开发了不同的解决方案，但仅在选项数量相当少的情况下进行了验证。然而，很大一部分SPL有数百甚至数千个选项。如果不在具有如此多选项的软件上测试机器学习解决方案本论文的第一个贡献是将机器学习算法以前所未有的规模Linux内核有15，000个选项，完全超过了文献中所有的软件产品线案例研究，文献中只使用了最多60个选项的案例。通过评估几种最先进的算法在预测Linux内核二进制大小方面的准确性4某些技术。毫不奇怪，线性算法在准确性方面表现不性能影响模型虽然是专门为SPL开发的，但尽管采取了措施来减少组合爆炸，但仍无法处理这么多最终，我们发现基于树的算法以及神经网络能够提供一个相当准确的模型，并在时间和内存方面具有合理的资源第二个贡献是功能排名列表，这是一个选项列表，根据它们对软件目标属性的影响的重要性进行排名，由改进的基于决策树的功能选择生成。我们在与第一个贡献相同的条件下 更令人惊讶的是，我们还看到了前面考虑的大多数算法在准确性方面的该功能排名列表是人类可读的然而，在处理文档时存在很大的差异，主要是第三个贡献是改进了自动化性能专业化及其在各种SPL（包括Linux）上的评估。性能专业化是一个向SPL添加约束以满足特定用户定义的性能阈值的过程可以这些改进集中在两个方面。第一个是基于特征排名列表的选项选择的应用，这使得即使在只有几个选项的SPL上也能提高精度和学习时间。第二个是回归决策树的考虑，它产生了一个类似的规则提取模型，但具有意识到决策过程的5性能，而该维度在分类过程中被简化为简单的布尔我们开发了一种基于回归决策树的新技术，其中我们模拟性能分布中的偏差，以使算法意识到关于损失函数的阈值。最终，这三种技术都有各自的优势和劣势，以及各自的用例最新的贡献为机器学习在软件产品线中的更可持续使用打开了大门在这一领域，很少或根本没有注意到因此，我们从第二篇论文的工作中提取了一个非常精确的模型，并在后续版本中对其进行了评估，发现了两个主要问题。第一个是选项的差异第二个问题是，当模型用于与其训练版本不同的版本时，精度会下降。就配置措施和培训工作而言，培训第一个模型的成本非常高，考虑到每两三个月就有一个新版本，这样的费用是不合理的为了解决这两个问题，我们创建了Evolution-Aware Model Shifting，这是一种迁移学习技术，适用于它利用了原始但已弃用的模型，并以初始成本的一小部分，使其适应新的版本。我们的结果显示，在三年的演变过程中，准确性非常好，在ABSTRACT7可变性是当今软件开发的祸根。在一只手上，它允许快速和廉价的开发，同时提供高效的定制，以准确地满足用户的需求另一方面，由于可能的配置数量太多，系统的复杂性增加，使得用户很难或甚至不可能正确地使用它们，开发人员很难或不可能正确地测试它们，或者专家很难或不可能准确地掌握它们的功能。机器学习是一个研究领域，在过去的几十年里，它的可访问性和用途的多样性都在增长。它吸引了软件工程领域的研究人员的兴趣，因为它能够处理然而，所有在SPL领域提出基于学习的解决方案的研究都未能探索其技术在具有巨大配置空间（>1000个选项）的系统上的可扩展性。在本文中，我们将重点讨论Linux内核。它有超过15，000个选项，非常代表了具有巨大配置空间的系统的复杂性。我们首先应用各种学习技术来预测内核二进制大小，并报告大多数技术都无法产生准确的结果。特别是，性能影响模型，一种为SPL问题量身定制的学习技术，甚至不能在如此大的数据集上工作。在测试的技术中，只有基于树的算法和神经网络能够在可接受的时间内产生精确的模型为了缓解学习技术上巨大的配置空间所产生的问题，我们提出了一种利用随机森林的特征选择技术，增强了稳定性。我们证明，通过使用功能选择，可以大大减少培训时间，并提高准确性。这种基于树的特征推断技术也是完全自动化的，并且不依赖于关于系统的先验知识性能专业化是一种将软件系统的配置空间限制为满足给定性能标准的技术。可以通过利用决策树来自动化专业化过程。虽然只有决策树分类器用于此任务，但我们探讨了决策树回归器的使用，以及8新的混合方法。我们在广泛的系统上测试和比较了不同的方法，就像在Linux上一样，以确保在巨大的配置空间上的可扩展性。在大多数情况下，包括Linux，我们报告的准确率至少为90%，与其他方法相比，每种方法都有其自身的优势。最后，我们还利用了基于树的特征选择，其最显著的效果是减少了Linux上决策树的训练时间，从一分钟减少到一秒或更少。最后一个贡献探讨了性能模型在可配置系统版本之间的可持续性。我们使用了我们第一次贡献时在Linux 4.13版本上训练的模型，并在三年多的时间里在六个后续版本（最高5.8）上测量了它的准确性。我们证明了一个模型很快就会过时且无法使用 是的。为了保持模型在不同版本中的准确性，我们使用基于树的算法的帮助下的转移学习来以较低的成本维护它。我们解决了配置空间异质性的问题，它随着每个版本的变化而变化。我们表明，转移方法允许以低成本获得可接受的准确性，并且在相同的预算下大大优于从头开始学习方法。总的来说，本文关注的是像Linux这样具有巨大配置空间的系统的问题，并表明基于树的算法是一个有效的解决方案，它的通用性足以回答广泛的问题，并且它的准确性足以被考虑。一个知识分子9我首先要感谢你，读者，这是我在这篇论文中学到的一个重要教训，那就是科学只有在传递给别人的情况下才有价值，阅读这篇论文和写它一样重要。我想感谢雷恩大学和所有的教授在我9年的学习中所做的教学。特别是，鲁门·安多诺夫教授，你在我心中占有特殊的地位，因为你决定在L3的第一天欢迎这类失去的学生，这导致了这篇论文。谢谢你对我的信任 天。感谢评审团成员谁同意阅读这篇论文，并审查其中描述的作品。我收到的反馈已被用来，我很高兴，以改善手稿，在我的拙见，远远好于我把它送去审查。感谢所有参与TuxML项目的硕士生，他们是本论文所做工作的基础。保罗，你引导我迈出了机器学习的第一步，并始终确保我拥有我所需要的一切，即使我在需要的时候没有问，谢谢你。朱莉安娜，你卓越的科学成就给我留下了深刻的印象，我非常高兴有机会在你的博士后期间与你一起从事许多项目Luc，在过去的几年里，我们在DiverSE分享了很多东西，你在统计学方面的专业知识帮助我在这篇论文中取得了很大的进步。我们的讨论，无论是关于研究还是其他主题，总是非常有趣和丰富。对于DiverSE团队的所有成员，太多了，无法一一提及，你们都在我的脑海中，因为你们都标记了我。我喜欢属于这个团队，在这个不断分享知识，跨越许多领域，一个真正的思考大熔炉，好奇心使科学。马修，你给我的实习机会为我开辟了一条我认为可以实现的新道路，它永远改变了我的生活。你的热情是一个真正的驱动力，任何人与你一起工作，永远不要让它去!Jean-Marc，你的科学技能在许多方面都得到了认可，但是10给我留下最深刻印象的是你在这篇论文中所获得的学位。我们可以通过你简明扼要、高度相关的批评感受到你伟大的科学经验，这些批评能够集中马蒂厄的热情谢谢你们两个是一个令人难以置信的监督二人组。Jérôme，我默认遵循您的路径一点，如果我分支到我自己的路径，谢谢 你一直是我的榜样。妈妈，你总是竭尽全力为你的两个大男孩提供他们所需要的一切，你可以为结果感到自豪。爸爸，你给了我们，杰罗姆和我，你永远无法获得的教育，你花在我们身上的一切，我们需要得到最好的。即使你将无法参加这篇论文的完成，知道这是献给你的。谢谢你的一切。REMERCIENTS11我首先要感谢你，读者，因为我从这篇论文中学到的一个重要教训我要感谢雷恩第一大学和所有的教授，感谢他们在我9年的学习中给予我的指导。特别是，鲁门·安多诺夫教授，你应该在我的思想中占有重要的地位，因为你决定在谢谢你感谢评审团成员同意阅读这篇论文并评估其组成工作。我收到的反馈感谢所有参与TuxML项目的硕士生，这对本论文的研究至关重要保罗，你朱莉安娜，你卓越的科学成就给Luc，在过去的几年里，我们在DiverSE分享了很多，你在统计学方面的专业知识对这篇论文的进展做出了很大的贡献。我们能够进行的关于研究或许多其他主题的讨论总是感谢DiverSE团队的所有成员，太多了，无法一一列举，但我想到了你们每一个给我 留 下 深 刻 印 象 的 人 。 J’ai aimé faire partie de ce groupe, dans ce partage deconnaissances permanent, couvrant de nombreux domaines, un véritable creuset马修，你给我的实习机会你持续的热情是真正的动力12第0章. 谢谢你对于任何和你一起工作的人，永远不要失去它!Jean-Marc，你的科学能力在很多方面都得到了认可，但给我印象最深的是你对我的平易近人。在这篇论文中。你在科学方面的丰富经验体现在你简洁而中肯的批评中，这些批评引导了感谢你们两个是一对优秀的论文导师。杰罗姆，妈妈，你总是爸爸，你给了杰罗姆和我你即使你不能参加这篇论文的完成，也要知道这篇论文是献给你的谢谢你所做的一切。T ABLE来自C组13法文摘要3摘要71导言172背景252.1软件产品线252.1.1可配置性的诅咒272.1.2专业化282.2用于SPL31的机器学习2.2.1机器学习312.2.2用于SPL33的机器学习2.2.3迁移学习362.2.4功能选择362.3Linux内核382.3.1Linux、选项和配置382.3.2内核二进制大小392.3.3Linux内核快速演进422.3.4Linux和机器学习422.4结论433Linux内核的二进制大小预测：巨大骗局的挑战-Space453.1导言453.2软件产品线3.2.1收集配置3.2.2统计学习问题483.2.3最先进解决方案的局限性493.3研究设计50内容表143.1数据集。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ...513.3.2统计学习实施。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 523.3.3指标和测量。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 553.4结果。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ... ... ... ...553.5有效性威胁。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 565.1内部有效性。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...565.2外部有效性。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...573.6结论。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ... ...584基于树的特征选择594.1引言。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ...594.2内核大小和文档。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 61使用基于树的特征选择进行学习。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 614.3.1我们的方法：基于树的特征选择。... ... ... ... ... ... ... ... ... ... ... ... ... 624.4研究设计。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ...654.4.1指标和测量。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 664.4.2功能排名列表场景。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...674.5结果。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ... ... ... ...684.5.1（RQ1）准确性。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...694.5.2（RQ2）稳定性。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...714.5.3（RQ3）培训时 72T ABLE来自C组15间。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...4.5.4 （RQ）可解释性。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...744.6有效性威胁。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... 764.6.1内部有效性。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...764.7结论。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ... ...775自动化性能专业化795.1引言。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ...795.2性能专业化。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...815.3自动化性能专业化。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 845.3.1专业化是一个学习问题。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 845.3.2专业化的学习算法。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 845.3学习策略。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...855.3.4基于树的特征选择。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 875.4 研究设计。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ...8715内容表5.4.1数据集885.4.2学习算法895.4.3阈值影响895.4.4指标905.4.5基于树的特征选择905.5结果915.5.1结果RQ 1和RQ 2-准确度935.5.2结果RQ 3-功能选择945.5.3结果RQ 4-培训时间955.6讨论985.7对有效性的威胁995.7.1内部有效性995.7.2外部有效性1005.8结论1006跨版本103的性能预测模型转换6.1导言1036.2演进对配置性能1056.2.1实验设置1066.2.2结果1106.3进化感知模型转移1136.3.1异质迁移学习问题1136.3.2原则1156.3.3算法1166.3.4变体：增量转移1166.4迁移学习的有效性1186.4.1实验设置1186.4.2基线方法和参数1196.4.3结果1206.5讨论1246.6对有效性的威胁1276.7结论128内容表167结论和展望1317.1结论1317.2前景1337.2.1功能选择1337.2.2自动化性能专业化1347.2.3跨版本134参考书目13717C型HAPTER1一、引言可变性是一个影响每个人、每个地方、每个日子的概念它代表了我们可以做出的或由外部因素强加的所有选择的集合此外，每一个选择都可能影响其他选择，每一个选择的组合都可能导致不同的结果。这些选择是多种多样的，就像你上班的不同道路一样。每一个交叉点都是一个选择，而这一系列的选择创造了一条独特的道路，并带来了自己的结果。我们可能想到的一个结果是旅行时间，这显然取决于你走的路线，但也取决于你的速度，并受到外部因素（交通繁忙，道路工程等）的影响。这可以通过不同的路径选择来然而，很难预测一个选择会如何影响一个特定的结果。由于大多数选择实际上对结果没有影响，或者影响很小，因此大多数选择都被忽视了，以避免决策和所需分析的负担过重。一个人可以尝试每一组可能的选择，但如果我们以前面的例子为例，给定存在的道路的数量，从最直接的到最意想不到的所有可能的组合的集合是不可避免的。这种方法只能在选择很少的情况下考虑。在软件工程中，为了创建我们所说的软件产品线（SPL），引入了可变性。这个想法是在一个系统中满足各种客户的需求，方法是为他们提供配置该系统的选项，以激活所需的系统部分。由于许多客户都有相同的需求，因此重复使用软件系统是避免不必要成本的好方法。在软件产品线中使用时，可变性会带来自身的问题。一起激活的一些选项可能会看到它们的行为发生变化，因为它们可能会相互交互。这意味着在不考虑其他选项的情况下测试一个选项不足以确保系统按预期工作。除了简单的工作井之外，选项和选项的组合还可能影响性能或其他非功能属性。随着软件产品线的发展，它们变得更加复杂，更难理解和描述。几十年来，对系统性能进行建模一直是专家的领域，但简介18时间到了。随着期权数量的不断增加，快速发展 系统的复杂性、选项之间的复杂交互以及需要跟踪的广泛指标，使任务过于繁重。在过去的十年里，机器学习的民主化使其在SPL性能建模中站稳了脚跟。为了从性能模型的样本中推导出性能模型，已经做出了许多努力--当然，有时能够产生比专家更有效和更准确的模型。在这些努力中，出现了一些例程，特别是关于使用相同的数据集语料库进行验证的例程。到目前为止，SPL性能建模文献中使用的主题系统中没有一个超过几打选项，最多60个，而今天的系统达到了数千个选项，如Linux内核，或市场上大多数Web浏览器。由于期权之间相互作用的组合爆炸，这样的系统的配置空间是巨大的。随着SPL中期权数量的缓慢但稳定的增长，坚持使用elabo-rating新建模技术而不挑战其扩展期权数量的能力是一个应该纠正的错误。除了警告研究人员SPL性能建模技术的可扩展性，从我们对它们的局限性的观察中得出结论，本文提供了解决方案。我们介绍了基于树的学习技术的能力，以有效地处理各种任务的SPL的复杂性，从简单的，但可扩展的，性能建模到转移学习，通过特征选择和专业化。贡献本论文的第一个也是最有远见的贡献是机器学习算法在软件产品线上的应用，其规模是以前从未达到的。Linux内核有15，000个选项，完全超过了文献中60个选项的SPL案例研究。这篇文章集中在一个研究问题上：最先进的技术如何在Linux数据集上表现？ 目标这个问题的答案是双重的，首先要确定一种技术可以从这样的数据集中学到什么，然后再确定它能学得多好。通过评估几种最先进的算法在预测Linux内核的二进制大小方面的准确性，我们可以确定一些技术的限制。毫不奇怪，基于线性的算法提供了较差的准确性，因为它们无法承受由选项之间的相互作用引起的复杂性
