Decima(Robustness Analysis and Enhancement of Deep Reinforcement Learning-Based Schedulers)

解决的问题

我们设计了黑盒扰动系统，其中训练了一个代理模型来模仿基于 DRL 的调度策略，并且表明，高可信代理模型可以帮助制作有效的扰动。扰动的意思是对作业的节点特性或依赖性进行轻微调整，同时不改变其功能。

最终，我们研究了提高基于 DRL 的调度程序对此类扰动的鲁棒性的解决方案：我们提出了一种对抗性训练框架，以强制神经模型在训练过程中适应扰动模式，从而消除应用过程中的潜在损害。

  • 提出问题

各种研究发现深度神经模型（如DRL模型）容易受到对抗性数据实例的影响（如其观察空间或动作空间输入的扰动）产生错误决策，并且缺乏鲁棒性；而在云计算调度问题中，对鲁棒性也有很高的要求，即使系统中没有恶意用户也有可能会有一些特征模式触发调度程序的不当行为，因此这种鲁棒性问题并不总是与对抗性扰动相关联，但研究它的重要性是绝对的。

  • 解决思路
  1. 研究如何开发一种有效扰乱工作特征的方法。
  2. 在成功模拟有效扰乱工作特征之后，提出对抗训练方法以提升模型的鲁棒性
  • 实验结果

我们的实验表明，这种鲁棒性的提高显着降低了工作扰动的成功率。即使扰动成功，它也会降低扰动作业的性能增益。具有对抗性训练的 DRL 调度器能够实现与原始 DRL 调度器相当的调度性能。

黑盒扰动系统

首先提出之前有人设计的白盒扰动系统，白盒方法假设用户可以访问 DRL 模型的详细信息，包括模型架构和参数。但白盒扰动系统存在这样一个问题：对于调度策略未知的许多云系统，该假设通常不成立。

因此工作扰动系统采用黑盒假设来解决这个问题，这意味着恶意用户无法访问 DRL 模型和其他用户的工作，如下图中的阴影方块所示。

image-20230116152713038

其核心技术是模型窃取，即利用制造的数据集训练本地代理模型作为目标模型的替代品。代理模型不需要与其目标具有相同的结构，而只是模仿功能。

恶意用户通过模仿得到相同种类但细节不同的job，然后将job在空闲时间提交以获得调度程序的神经模型。通过执行完成后的调度轨迹，可以得知调度程序在每个时间步做出怎样的决策。因此，它只通过几个调度轨迹就得到了一个比较可信的代理神经网络。并且通过job状态和决策形成的元组，它将一个调度问题解耦成了一个分类问题。

在该代理模型的帮助下，恶意用户就可以在job提交之前计算并且应用扰动（增加一些任务的并行度或者在任务之间增加依赖关系）来获得额外的计算资源以达成早一些完成任务的目的。

作业扰动

作业扰动的目的是在某些时间步将调度决策偏向错误的方向。

成功施加扰动的难点：

首先，扰动可以应用于作业中多达数百个特征，并且很难获得最优计划。

其次，扰动作业试图抢占动态系统中的资源。它会在调度过程中的一个确定的时间步发生。具体成功时间由当时的系统状态快照决定，这是系统禁止的。

基于梯度的扰动

特征提取

$job_k$ 的特征形成一个 $m \times n $矩阵 $X_k : (x_i,j)$，其中 $m_k$ 是任务数，$n$ 是特征数。此外，只有解决了任务的依赖关系才能执行任务，这些依赖关系由相邻矩阵 $E_k : (e_i,j)$ 表示，其中 $i, j \in [1, m_k]$。

关于扰动：我们只会扰乱并行性和依赖性。

特征扰动

在调度程序执行的过程中，一个任务是否被优先调度取决于它的得分。为了让被扰动的作业优先执行且占用更多资源，必须通过扰动让被扰动的作业获得更高的分数，只有获得更高的分数，它才能被执行。被扰动的作业优先被调度时必须满足下面公式：

$O_t[\bar{o_t}] > O_t[o_t]$

但是本身被扰动的作业在被扰动前它的$O_t[\bar{o_t}]$就同$O_t[o_t]$相差很大，因此需要通过扰动使其获得更高的分数。为了决定扰动哪个特征可以使分数增加更多，提出了特征梯度的概念。

$\nabla \chi_tO_t[\bar{o_t}] = \frac{\partial O_t[\bar{o_t}]}{\partial \chi_t}$

通过特征梯度可以得知作业中哪个特征的扰动对$O_t[o_t]$值的影响更显著。因此可以通过下面式子得知哪个task的哪个feature应该被选择去扰动。

$T^*, f^* = argmax[\frac{\partial O_t[\bar{o_t}]}{\partial \chi_t}]$

确定了对哪个特征进行扰动，就该进行扰动的实际操作了，沿着值方向对特征进行增量应用扰动，如下式：

$x_{T^*, f^*} = x_{T^*, f^*} + sign([\frac{\partial O_t[\bar{o_t}]}{\partial \chi_t}]_{T^*, f^*}) \times \delta$

依赖扰动

因此不能破坏原有任务的依赖性，因此所谓的依赖扰动就是通过加入以前独立的任务来应用依赖性扰动。它的评判标准被定义为下面的式子：

$\nabla \varepsilon_tO_t[\bar{o_t}] = avg[\frac{\partial O_t[\bar{o_t}]}{\partial \varepsilon_t^i}] = \frac{1}{K}\sum_{i=1}^{K} \frac{\partial \bar{\pi_\theta}(\chi_t, \varepsilon_t^i)}{\partial \varepsilon_t^i}$

边缘梯度在相邻矩阵 $E_t$ 上形成显着图，其中较高的值表示在应用扰动时输出分量的改进更为显着。因此，在任务$T_f^*$和任务$T_t^*$之间的边被添加了：

$T_f^*, T_t^* = argmax(avg[\frac{\partial O_t[\bar{o_t}]}{\partial \varepsilon_t^i}])$

识别出的边缘还应该满足这两个任务都属于恶意用户的工作并且之前是独立的。否则，上面的式子将继续寻找下一条除了不满足条件外显着性值最大的边。

近似扰动

由于矩阵$\chi_t$和$\varepsilon_t$ 的一些部分不可访问，因此在训练过程中，通过自己的定义，将之前方程中梯度的专用分量可以通过每个独立输入作业的梯度来近似。

$T^*, f^* \approx argmax[\frac{\partial O_t[\bar{o_t}]}{\partial \hat{X_t}}]$

$T_f^*, T_t^* \approx argmax(avg[\frac{\partial O_t[\bar{o_t}]}{\partial \hat{E_t^i}}])$

当原始调度决策不那么明显时，在时间步长 t 应用扰动是至关重要的。我们通过近似来解决决定时间步长的问题。

通过用原始工作特征$\hat{X}$和$\hat{E^i}$替换即时的工作特征$\hat{X_t}$和$\hat{E_t^i}$。我们以工作的关键路径上的所有任务为目标进行综合考虑，将上面的两个近似式子重构成了以下式子：

$T^*, f^* \approx argmax[\frac{\partial O_t[\bar{o_t}]}{\partial \hat{X}}]$

$T_f^*, T_t^* \approx argmax(avg[\frac{\partial O_t[\bar{o_t}]}{\partial \hat{E^i}}])$

由于特征和依赖扰动计划都是时不变的，因此可以通过以 O(1) 时间成本提交的作业来计算。

基于 DRL 的调度器的稳健性改进

我们描述了一个对抗训练框架来提高 DRL 调度器的稳健性。它通过让调度程序在训练期间学习工作扰动的模式来提高鲁棒性。

在强化学习中，用来更新策略$\pi$的参数$\theta$的梯度可以通过以下式子获得：

$g = E[\sum_{t=0}^{\infin}R_t \nabla log_\theta (\pi_\theta(A_t|S_t))]$

在对抗训练期间，扰动状态 $S_t^*$ 和原始状态 $S_t$ 一起学习，以将梯度引向$\nabla log_\theta (\pi_\theta(A_t|S_t)) + \nabla log_\theta (\pi_\theta(A_t|S_t^*))$。

在训练阶段添加这种对抗性扰动可以使模型在寻找最高奖励时不那么极端，如果扰动发生在应用阶段 ，则模型会更加稳健。

对抗训练的整体工作流程为：

image-20230116165033169

对抗训练框架的示意图：

image-20230116165112449

原始状态和扰动状态被馈送到模型中进行梯度计算，并使用相同的奖励信号更新模型。

实验

实验设置

我们使用 Decima的作业执行引擎作为我们的测试平台。

在我们的实验中，我们将集群的执行器数量设置为 10 和 20。我们使用 TPC-H 作业 [41] 作为工作负载。作业的统计信息，包括每个作业 DAG 中的级别、任务数以及每个任务的并行度和持续时间，如表 2 所示。作业运行时间遵循重尾分布，大约 20% 的作业占用所有作业运行时间的 80%。

image-20230116171153629

我们实现了三种 DRL 算法作为 Decima 调度框架的插件，以证明这个问题对于不同的 DRL 算法是常见的。

第一种算法是REINFORCE，其每个时间步的奖励是通过使用情景样本的蒙特卡洛方法估计的，原始 Decima 调度程序也使用该方法。

第二种算法是off-policy policy gradient(OPPG),它使用行为策略来推导调度决策并计算另一个目标策略的重要性采样。

第三种算法是同步优势演员评论家 (A2C)，参与者(actor)使用策略模型生成动作，而评论家(critic)则使用另一个神经模型来预测每个动作的优势.每个模型中的核心策略都是用全连接神经网络实现的。实际上，A2C 使用 5 种不同的陈旧版本。 A2C 中的演员和评论家由不同的全连接层组成。actor 具有动态数量的输出，形成任务的概率分布，而 critic 仅输出一个单元。

图神经网络结合了非线性激活和聚合函数，这为调度程序提供了输入的全局视图，以获得更好的调度策略。

调度程序的脆弱性是通过它们受工作扰动影响的可能性来衡量的。成功的扰动会抢占资源以提前完成扰动的工作，同时延迟其他工作.

评估脆弱性的三个指标：扰动的成功率、扰动工作的好处（通过降低 JCT(任务完成时间) 来衡量）以及显着延迟的工作数量。而稳健性的提高是通过这些指标的减少来衡量的。

模型窃取

忠实的代理神经模型对于黑盒扰动的成功至关重要。我们启动 50 个查询来窃取作业调度程序中的模型。每个查询包含 20 个根据时间步长安排的模拟作业。总的来说，我们从 11,000 个调度时间步长中获得了状态和动作对。其中 80% 用于训练，其余 20% 用于测试。代理模型学习如何在每个时间步将调度程序从数百个其他任务中选择的任务分类。最终实验结果表明：CNN 模型达到了 82.2% 的精度来近似 REINFORCE，而 GCN 达到了 85.0% 的精度来近似 OPPG。

image-20230116181602908

基于 DRL 的调度程序的脆弱性

在本节中，进行了多次实验来评估漏洞。在每个实验中，提交了 50 个作业，其中一个作业被扰动了。独立评估不同的基于 DRL 的调度程序。将每个作业的作业完成时间与在相同设置但没有作业扰动的情况下获得的作业完成时间进行比较。

image-20230116181800279

(a) 黑盒作业扰动干扰每个基于 DRL 的调度程序的成功率。 (b) 受扰动工作的好处（以减少的 JCT 衡量）和由于扰动工作的好处而严重延迟的正常工作（其 JCT 增加超过 5%）的数量。

最终结果：REINFORCE 比其他两个调度程序更容易受到扰动，因为后者有超过 10 个正常作业被显着延迟。 OPPG和A2C的鲁棒性更强主要是因为独立行为策略或批评模型达到了一定的鲁棒性。

对于扰动的详细说明

为了理解基于 DRL 的调度器的脆弱性，我们首先给出扰动的统计数据，然后给出一个详细的例子来说明扰动是如何产生影响的。

在改变并行度方面：并行度的降低是通过为数据分区插入“合并”运算符来实现的，而并行度的增加是通过在任务代码的开头添加运算符“repartition”来实现的。

在增加依赖方面：两个任务的连接是通过“连接”的运算符实现的。

通过以上方式成功实现了扰动。

image-20230116182309070

不同类型的扰动。从左到右，作业受到 (i) 仅增加任务并行度，(ii) 降低作业并行度并添加依赖项，以及 (iii) 仅添加依赖项的干扰。

具体案例

我们提供了一个案例研究来解释用不同方法扰乱的工作如何使他们的 JCT 受益，如图9所示：

image-20230116183729916

扰动或调整后的并行度由每个任务节点周围的数字显示。示例作业没有依赖性变化，因为显着性值太低，即改变依赖性不会导致成功的扰动。

我们使用 REINFORCE 调度程序比较每个扰动作业的任务执行模式和同一环境中的原始作业，如图10所示：

image-20230116183920593

实验结果表明：经过扰动后，这些任务能够在某些调度步骤中具有更高的优先级。这些任务以更高的并行度执行，因此更早完成。它们的完成也可能导致依赖于它们的后续任务的提前执行。

鲁棒性的提升

在本节中，我们评估了对抗训练在提高基于 DRL 的调度程序处理扰动工作的鲁棒性方面的有效性。

对抗训练

一个健壮的基于 DRL 的调度器的实现方式与第 6.1 节中详述的方式类似。我们还在调度程序中包含了不同的强化学习实现，即 REINFORCE、OPPG 和 A2C。

每个调度器的正常训练和对抗训练的过程如图11的左栏所示：

image-20230116184150766

左列显示了基于 DRL 的调度程序的正常和对抗训练过程。每个模型的收敛由平均奖励的扁平化表示。右列显示了基本调度程序和鲁棒调度程序在 50 个作业集上的调度性能。剩余作业数量减少得越快，调度性能越好。具体来说，Reinforce的图如(a)和(b)所示，OPPG的图如(c)和(d)所示，A2C的图如(e)和(f)所示。

该过程的特点是在每个情节中获得的归一化平均奖励。在训练过程中包括受扰动的工作会使收敛花费更长的时间，并且收到的奖励会波动（图 11a 和 11e）。

调度表现

我们将每个基于 DRL 的鲁棒调度程序的调度性能与基本对应调度程序进行比较。Jobs的执行流程如图11右栏所示。

总而言之，强大的 DRL 调度器保持了令人满意的调度性能。

鲁棒性评估

我们在“基于 DRL 的调度程序的脆弱性”的相同实验设置下评估了基于 DRL 的鲁棒调度程序的脆弱性，并将展示鲁棒性改进。

总的来说，我们的对抗训练方法可以提高基于 DRL 的调度程序的鲁棒性并减少工作扰动的影响。

白盒扰动的脆弱性

在“Whitebox”中，它拥有了一个更强的假设，即用户可以完全访问 DRL 模型。特征中的所有显着性值空间是在原始 DRL 模型而不是代理模型上计算的。在本节中，我们评估鲁棒调度程序是否也对白盒扰动具有鲁棒性。

image-20230116185045106

总的来说，通过代理模型训练的鲁棒调度器可以有效地处理白盒模型产生的扰动作业。

结论

在本文中，我们探讨了基于 DRL 的调度程序的稳健性问题。 我们展示了用户可以在代理模型的帮助下扰乱作业以进行抢占，代理模型是为模仿基于 DRL 的调度程序的调度行为而开发的。 就工作自然具有某些特征模式而言，扰动可能是无意的。 这可能导致调度行为的不确定性。 我们提出了一种计算作业扰动的算法，并表明扰动作业具有很高的成功率以获得高调度优先级。 我们表明这种扰动对调度程序有害，因为它会导致系统中其他作业的意外延迟。 我们设计了一个对抗训练框架来提高 DRL 调度程序的稳健性。 广泛的实验表明，鲁棒调度器在保持高调度性能的同时不易受到扰动的影响。

数据集

TPC-H, 2020. [Online]. Available: http://www.tpc.org/tpch/ default5.asp

参考链接

Robustness Analysis and Enhancement of Deep Reinforcement Learning-Based Schedulers