基于搜索的强化学习：安全性和性能评估

+v：mala2277获取更多论文基于搜索的强化学习马丁·T·苹果1岁，3岁，菲利普·卡诺·科多巴2岁，贝尔·恩哈德·K。Aicher nig1，3，BettinaKnighthorn2，4，1格拉茨科技大学软件技术学院2格拉茨理工大学应用信息处理与通信学院3TU Graz-SAL DES Lab，Silicon Austria Labs，Graz，奥地利4LambertSecurity Researchmartin. ist.tugraz.at，filip. iaik.tugraz.at，aichernig@ist.tugraz.at，bettina. lamarr.at图1：超级马里奥兄弟：参考轨迹和边界状态。向下：参考轨迹和模糊轨迹。摘要深度强化学习（Deep Reinforcement Learning，RL）本身就具有挑战性特别是学习策略的不透明性以及代理和环境的随机性我们提出了一个基于搜索的测试框架，该框架能够实现广泛的新型分析功能，用于评估深度RL代理的安全性和性能。对于安全测试，我们的框架利用搜索算法，搜索解决RL任务的参考轨迹。搜索的回溯状态，称为边界状态，构成安全关键的情况。我们创建安全测试套件，评估如何以及RL代理逃脱安全关键的情况下，这些边界状态附近。对于健壮的性能测试，我们通过模糊测试创建了一组不同的跟踪。这些模糊跟踪用于将代理带入各种各样的潜在未知状态，从这些状态将代理的平均性能与模糊跟踪的平均性能进行比较。我们将我们基于搜索的测试方法应用于任天堂超级马里奥兄弟的RL1介绍在强化学习（RL）[Sutton and Barto，1998]中，智能体的目标是通过与未知环境的交互，通过试错来最近，RL算法在玩游戏方面取得了惊人的成绩，联系作者视频游戏和复杂的棋盘游戏[Schrittwieseret al. ，2020]。为了获得广泛的接受和扩大学习控制器的应用领域，迫切需要可靠地评估训练RL代理。在评估经过训练的代理时，需要回答两个基本问题：（Q1）经过训练的深度RL代理是否规避安全违规？（Q2）经过训练的深度RL代理在各种状态下都表现良好吗？测试深度RL代理是非常困难的。第一个挑战来自于环境，它通常不是完全已知的，并且具有巨大的状态空间，结合代理模型的拜占庭复杂性，以及代理和环境两者的确定性的缺乏。其次，为了评估一个受过训练的代理的政策的性能为了应对这些挑战，我们将成熟的基于搜索的概念从软件测试转移到RL设置中。像基于回溯的深度优先搜索（DFS）这样的搜索算法是查找有效和无效程序执行的标准算法。模糊测试是指自动化软件测试技术，它生成有趣的测试用例，目的是暴露在测试程序中没有正确处理的角落案例。在这项工作中，我们提出了一个基于搜索的测试框架，以可靠地评估训练有素的RL代理回答问题Q1和Q2。我们的测试框架包括四个步骤：步骤1：搜索参考迹线和边界状态。在第一步中，我们使用DFS算法通过对黑盒环境进行采样来搜索解决RL任务的引用跟踪这个想法是由人工智能比赛的经验，如马里奥人工智能和NetHack Chal-游戏[Kara ko vskiyand Togelius，2012; Küttleretal. ，2020]，arXiv：2205.04887v1 [cs.LG] 2022年5月+v：mala2277获取更多论文其中最佳执行者是符号代理，其比基于神经的代理更快地提供任务的参考解决方案此外，由于DFS算法在到达环境中的不安全状态时回溯，因此搜索揭示了我们称为边界状态的安全关键情况。第二步：测试安全性。 为了回答Q1，我们的测试框架计算安全测试套件，使代理进入边界状态附近的安全关键情况。基于代理在这些安全关键情况下成功的能力，我们可以评估代理的安全性。一个安全的代理不应该违反安全，无论它面临的情况。步骤3：生成模糊痕迹。作为性能测试的基础，我们的测试框架应用基于搜索的模糊方法来从参考轨迹（步骤1）计算不同的轨迹集，旨在获得高回报并覆盖大部分状态空间的轨迹。步骤4：性能测试。为了回答Q2，我们从模糊跟踪中创建性能测试套件，以使代理进入环境中的各种状态作为性能指标，我们建议逐点比较通过执行代理的策略获得的我们的方法是非常普遍的，可以适用于几个应用领域。在给定初始迹线的设置中，例如，源于人类的演示，这样的迹线可以用作模糊的基础。我们的方法只需要能够将环境采样为Oracle。即使在部分可观性的情况下，我们的测试框架可以成功地应用。这是因为我们只需要跟踪是否成功完成了要学习的任务，部分完成了任务，或者它是否违反了安全性的信息不需要确切的状态信息。Fuzzing已被应用于测试复杂的软件系统，如操作系统内核，通信协议和编程语言的解析器[Man e`setal. ，2021]。因此，它为大型环境提供了可扩展性。在我们的案例研究中，我们应用我们的框架来测试一组经过训练以玩超级马里奥兄弟的深度RL代理的安全性和性能。图1显示了在我们的案例研究中计算的第1步中计算的参考轨迹（红色）和边界状态（白点）以及第3步中计算的模糊轨迹（黄色）由于我们认为环境（以及经过训练的代理，其中学习的策略可能需要打破联系）是概率性的，因此我们多次执行每个测试用例并呈现平均结果。相关工作。虽然RL已被证明在解决许多复杂任务方面是成功的[Silveret al. ，2016]，并且经常超越经典控制器[Kiranet al. ，2021]，安全性问题阻碍了学习控制器在安全关键应用中的广泛使用。安全RL的研究目标是在RL代理的训练和执行阶段保证安全[Garcıa和Fern a'ndez，2015]。 安全RL在正式方法社区中引起了广泛关注，最终导致越来越多的关于训练网络验证的工作[Ehlers，2017;Pathaket al. ，2017;Corsiet al. ，2021]。然而，所有这些方法都存在可扩展性问题，并且还无法验证工业规模的深度神经网络。另一种研究方向旨在加强RL代理在运行时，使用来自运行时监控和增强的技术[Alshiekhetal. ，2018; Prangeret al. ，2021]。这些方法通常需要一个完整和忠实的环境动态模型，这往往是不可用的。虽然存在大量的离线和运行时验证的RL代理的工作，研究合适的测试方法RL吸引了较少的关注。RL算法的开发极大地受益于性能评估的基准环境，包括Arcade学习环境[Bellemareetal. ，2013]和OpenAI Gym[Brockmanet al. ， 2016] ， Deep-mind Control Suite[Tassaet al. 2018年，举几个例子。Safe-tyGym[Achiam和Amodei，2019]专门设计用于评价探索期间RL算法的安全性。大多数关于RL测试的工作通过比较任务之间的平均值和中值来评估总体绩效。最近，已经提出了解决这种点 估计 中的 统计 不确 定性 的测 试指标[Agar-waletal. ，2021]。 我们通过propos扩展了以前的工作-基于搜索的测试针对（深度）RL。我们使用基于搜索的方法来自动创建安全关键的测试用例和测试用例的强大的性能测试。RL已经被提出用于软件测试，特别是模糊测试[B？ttingeretal. ， 2018; Wangetal. ， 2021;Scott 等 人 ，2021;Drozd and Wagner，2018].相比之下，我们提出了一种新的基于搜索的测试框架，包括模糊测试RL代理。Fuzzing 已 被 应 用 于 有 效 地 解 决 复 杂 的 任 务[Aschermannet al. ，2020;Schumiloet al. ，2022]。我们执行基于回溯的搜索来有效地解决任务，而模糊化用于覆盖状态空间的大部分。相关的还有Trujillo etal.[Trujilloet al. ，2020年]分析了测试深度RL的神经元覆盖的充分性，而我们的充分性标准受到传统边界值和组合测试的启发。我们使用我们的测试框架来评估经过训练的深度Q学习代理，这些代理在内部使用深度神经网络来近似Q函数。近年来，测试深度神经网络的工作激增技术，如DeepTest [Tianet al. ， 2018] ， DeepXplore [Peiet al. ，2019]和DeepRoad [Zhanget al. ，2018]，与我们提出的框架正交。虽然我们专注于RL代理的有状态反应性，将它们视为一个整体，但这些技术用于测试自治代理的传感器相关方面，并特别在图像处理中找到应用程序此外，我们可以考虑考虑神经网络特定的测试标准[Maet al. ，2018]。然而，最近有人对神经元覆盖的充分性和相关标准提出了质疑[Harel-Canadaet al. ，2020]。因此，如Trujillo et al.[Trujilloet al. ，2020]。纲要本文件其余部分的结构如下。节中2、给出了背景和符号。在SEC。3至6我们提出并详细讨论步骤1 -步骤4我们的测试框架。我们在SEC中提出了一个详细的案例研究第七章+v：mala2277获取更多论文”← S←S → A}|一 |≥A{∈ A |P/R S × A × S → ∈ SPS ×A× SV∈SSSS Sa∈AdoSRP∈ A⟨⟩| |⟨⟩t=1t=1S A P R S ∈ STMMMM- -VSVSVAVSVSS S∈ S ∈ AMP∈ T S <$Sπ00111nnn20232预赛马尔可夫决策过程M=（S，s0，A，P，R）是具有包括初始状态s的状态的有限集合S的元组，算法1：搜索参考迹线τref输入：MDPM=（S，s0，A，P，R），重复重复输出：τref，SBO1 VS<$[s0];VA<$[ ];Explored<$;success<$false;有限集合A0={a1. . . ，n}的动作，以及概率2 τref[s0];B'0;3 DFS（0）;转移函数：[0，1]，以及一个立即奖励函数：红毛菊R. 对于所有s ，可用的操作为（s）= as′，（s，a，s′）=0，我们假设（s）为1。 无记忆确定性策略π： 是 给 定状态下动作的函数。所有无记忆确定性策略的集合用表示。4 如果成功，50;6，其中i ∈ 1，. . . 、|VA|做7a，s←VA[i]，VS[i+1];8如果s∈/Expl或ed，则9r← R（sprev，a，s）;10Push（τref，（a，r，s<$）;11sprev←s;具有终端状态的MDP是具有终态集 其中MDP术语mi-13如果[i+2]探索然后/* 下一个状态是回溯点 */SB'O←SB'O{s};Nates，即，在M上执行策略π会产生一个跟踪14功能DFS：15exec（π，s）=πs，a，r，s，. . .，r，s，只有s是-如果s∈SU，则Explored←Explored搜索{s};return;使一个州处于T.T由两种类型的状态组成：目标-17国GT表示任务要执行的状态18 学习是通过达到他们来完成的，不希望的19个不安全状态SUST。 安全违规发生时，21 进入SU中的状态。 我们定义坏状态集SB22就像所有几乎肯定会导致南加州不安全的州一样，24如果s∈SG或success，则forsuccess←true;return;repeatreptimes从P（s，a）采样s';如果s'∈/VS，则Push（VA，a）;Push（VS，s）;Dfs（s'）;即，一个状态sB∈ S在SB中，如果应用任何从sB开始的策略π∈Π导致一个概率为1的状态在SU中。边界状态SBO的集合被定义为25if<$successthenExplored←Explored{s};在坏的国家中有继承国的国家，即，一个状态sBO∈ S在SBO中，如果sBO/∈SB，并且存在一个状态s∈SB和一个动作a∈ A，其中P（sBO，a，s）>0。我们考虑强化学习（RL），其中智能体通过与由MDP建模的未知环境的交互，通过试错来学习任务=（，s0，）与终端状态不.在每一步t，智能体接收一个观察st。然后它选择一个动作a+1. 然后，该元素以概率移动到状态st+1（st，at+1，st+1）。ReW由rt+1=（st，at+1，st+1）。如果协议到期-最终状态输入T训练结束了 时间步长情节结束由t结束表示。返回值ret = rtend γ t r t是每集的累积未来折扣奖励，使用折扣因子γ ∈ [0，1]。智能体的目标是学习最优策略πε：S → A，使收益的期望最大化，即，maxπ∈<$Eπ（ret）.每集的累积奖励为R = tttend r t。痕迹 迹τ = s0，a1，r1，s1，. . . 是在以初始状态s 0开始的情节期间由策略引起的状态-动作-奖励序列。我们用表示一组迹。给定迹τ=s0，a1，r1，s1. . . r n，sn，我们用τ[i]表示τ的第i个状态（s i=τ[i]），τ−i表示τ的前缀（τ −i由τ从位置0到i的所有元素组成），我们将迹τ +i表示为τ的后缀（τ+i由τ从位置i到n的所有元素组成）。给定迹τ= s0，a1，r1，s1. . . r n，s n，我们记τ=n为迹的长度。我们用d（τ，s）表示迹τ中第一次出现的态s（如果d（τ，s）=i则τ[i]= s）。我们将从τ中省略状态和奖励而得到的动作序列称为动作迹τA=a1，a2，. . . a n. [i]a， i，ai=τA[i]。从s0对M执行τA产生迹execτ（τA，s0）=s0，a1，r1，s1. . . r n，s nn，其中n = |τA|.3步骤1-搜索参考迹线和边界状态我们的测试框架的第一步是搜索一个参考轨迹τref，它执行RL代理要学习的任务（不一定是以最佳方式），并沿着参考轨迹检测边界状态B′0B0。我们建议使用基于回溯的深度优先搜索（DFS）通过对MDP进行采样来计算τref。对于DFS，我们通过足够频繁地重复动作来探索访问状态中的所有可能行为，从而抽象出随机行为[Khaliliand Tacchella，2014]。假设p= （s，a，s′）是对于任何s，s′和a的大于0的最小转移概率，我们通过rep（c，p）=log（1 c）/log（1p）计算匹配置信水平c所需的重复次数rep。这确保观察所有可能的状态，概率至少为c。Example. 假设p = 0。1是最小概率>0in .为了达到90%的置信度，搜索访问了任何可到达的状态，DFS必须执行rep（0。九，零。1）=在任何状态下重复任何动作22次。算法1给出了计算τref以及 一组边界 状态 B′0B0。 名单存储已经访问过的状态，以及将导致相应状态的已执行动作存储在.每次搜索访问一个不安全的州算法回溯。 如果DFS从所有后继 状 态 回 溯 到 %s ， 则 将 非 终 结 状 态 % s 添 加 到Explored。通过在中跟踪访问过的状态，我们可以确保不会沿着同一条跟踪两次探索一个状态。也就是说，我们使用来检测周期。 访问目标状态时，DFS（s0）成功结束在这种情况下，τref是从不属于反追踪分支的受访国搜索，即，s∈τS，如果s∈VS且s/∈Explored，1612+v：mala2277获取更多论文M∈ ∈ SS {}{}{}VAVS∈ S|一|≥一SSBOS ∈ S∈refSSAA⟨ ⟩AAA一图2：搜索算法使RL代理处于这样一个失败的位置不会提供关于学习的安全目标的额外见解，因为代理除了违反安全之外别无选择然而，在边界状态的偏移内测试τref的给定一个简单的测试套件ST和一个interval-sizeis，我们通过向ST添加额外的测试用例来创建一个interval-test suiteIT（is），这样，IT（is）={τ DB[i]+off|τ DB[i]∈ ST，−is ≤ off ≤is}，在VA中的响应动作。有后继的状态s∈τrefA，参考A，参考状态S′Exp lo red是边界状态，即，SB′O。Example. 图2显示了MDP的部分那是在我们的搜索算法运行过程中探索。发现的不安全状态标记为红色.在访问s10G（绿色圆圈）之后，搜索函数DFS（s0）返回=[s0，. . . ，s10]，=[a，a，b，a，b，b，a，a，b，b]，以及Explored =s2，s3，s4，s5，s8，s9。参考迹线（省略reward）为τref= s0，a，s1，b，s6，a，s7，b，s10，边界态子集为B′O=s1，s7（蓝色圆圈）。优化搜索。状态空间可以用于合并相似的状态，从而修剪搜索空间并且使得能够经由DFS在抽象状态空间中找到循环。检测循环加速了搜索，因为DFS在找到已访问状态的边缘时回溯这种抽象的一个例子是省略其中τA，ref是参考动作轨迹。测试用例τDB[i]+off测试边界状态i的agent，偏移量为off。A，参考使用Action Coverage的测试套件。组合测试涵盖了由输入值的组合产生的问题。我们通过创建测试套件来适应这一概念，这些测试套件涵盖了边界状态附近的动作组合，即，测试套件评估哪些动作导致边界区域中的不安全行为。给定参考作用迹τ，ref，一个简单的测试套件ST，和一个k1，我们生成一个k-wise动作覆盖率测试集AC（k），为ST中的每个测试用例创建k个测试用例，覆盖边界状态的第k个前驱状态的所有k个动作组合测试套件由以下给出：AC（k）={τ DB[i]−k·ac |τ DB[i]∈ ST，ac ∈ Ak}.在状态空间中合并状态的执行时间。A，参考A，参考4步骤2 -安全性基于τref和B′O搜索步骤1中，我们提出了几个测试套件，以确定一个政策的弱点，高频率的失败判决，即，安全违规。Af-在讨论了合适的测试集之后，我们讨论了如何执行它们来测试RL代理的安全性。简单边界测试套件。我们利用边界状态'inτreffor boundary value testing [Pezze` and Young ，2007].我们计算了一个简单的测试集，该测试集由结束于边界状态的τ ref的所有前缀组成。从这些痕迹中，我们使用动作痕迹将RL代理带到安全的地方-关键情况下，并测试其安全性能。形式上，设DB为边界的深度序列-在τ re f中的任意状态B′O，即，对于一个nysBOB′O：d（τ，sBO）DB. 使用DB，我们通过下式计算一组迹线T：T={τ−DB[i]|1≤i ≤|DB|}。从T中的跟踪中省略状态和奖励会产生一组动作跟踪，这些动作跟踪形成了一个简单的边界测试套件叫ST。我们说动作迹τDB[i]∈ST是检验测试用例执行判决。为了测试代理的安全行为，我们使用安全测试套件将代理带入安全关键情况。单个测试用例执行以动作跟踪τ、初始状态s0和测试长度l为参数。为了使用τ测试RL代理，我们首先执行τ，产生迹exec（τ）= s0，a1，r1，s1，. . . ，a n，r n，s n.如果exec（τ）在重复执行时始终访问T中的一个测试状态，则测试用例τ是无效的从sn开始，我们根据代理的策略选择接下来的l个动作。请注意，l应选择足够大，以评估代理的安全行为。因此，它应该比到下一个不安全状态的最短路径大得多。在执行代理策略的l个测试可以失败或通过：如果从sn开始，代理在l步内达到U否则，测试通过。为了执行一个测试集T，我们执行T n次的每个测试用例在此期间，我们计算执行每个单独的测试用例导致的失败判决的相对频率5步骤3 -生成模糊痕迹我们的测试框架评估RL案例第三边界状态A，参考使用模糊跟踪的代理 这些痕迹是用来比较是BO。获得奖励，以及把代理人在各种各样的使用边界间隔的测试套件。边界值测试不仅检查边界值，还检查稍微偏离边界的输入[Pezze` and Young，2007]。为了将这个概念转移到RL测试中，我们引入边界区间来测试边界附近的其他状态。与传统软件的边界测试不同，我们的测试用例停留在τ ref遍历的状态中。 这个选择边界国的定义是：一个国家的继承国必然导致一个不安全的国家。国家，并从这些向前评价性能。在本节中，我们将讨论性能测试的模糊跟踪生成。为此，我们提出了一种基于搜索的模糊方法[Zelleret al. ，2021]基于遗传算法。目标是找到动作轨迹，（1）覆盖状态空间的大部分，同时（2）完成RL代理要学习的任务。模糊轨迹计算综述 给定解决RL任务的参考轨迹τref（即，sn∈ SG），+v：mala2277获取更多论文T T{}AP RTT−EURR不不P RT←splEP一一联系我们S一一negAA0不i=1t我一i=1a我一一对于世代数g和群体大小p的参数值，模糊轨迹计算如下：1. 初始化0，跟踪总体：0：=τ，ref。2. 对于i=1到g代，做：(a) 从Ti−1创建p个动作轨迹（称为后代）以通过以下方式产生大小为p的新群体Ti• 或者从Ti−1突变单个父迹，算法2：使用模糊跟踪进行性能测试输入：=（，s0，、，）、策略π、模糊跟踪fit，# episodesnep输出：平均值代理人Ra和模糊轨迹Rt的累积奖励1 returnRt←EvalTraces（Tfit，s0，nep），Ra←EvalAgent（π，s0，nep）;2 函数EvalTraces（T拟合，s0，nep）：3对于τA∈ T，4fori←1tonepdo5τi ← execτ（τA，s0）=（s0，a1，r1. . . snn;n6Rt，τ，i←<$rk其中rk∈τi• 或者通过来自i1的具有指定的交叉概率。7returnRt一=（τA∈T拟合k=1i=1t，τA，i）/（nep·|不配合|）(b) 评估i中每个后代迹的适应度。3. 返回拟合包含每一代最适合的轨迹的适应度模糊迹线的计算通过选择具有与其适应度成比例的概率的父迹线来迭代地搜索具有高适应度的迹线。为了促进多样性，我们通过将交叉概率设置为值0来支持变异而不是交叉<。5.最适合的迹线Tfit的集合将8函数EvalAgent（π，s0，nep）：9101112fori←0 tonep doτ←exec（π，s）=（s，a我π0011n n，河. . 用s表示∈ S; 不nreturnR=（R）/n中文 （简体）与r∈τ;a我k=1 K K I新欧洲议会一i=1a，iep算法3：稳健性能测试input：=（，s0，），policy π，fuzz traces拟合，#测试n测试，#发作nep，步长w输出：平均值累积报酬Rpl和Rpl在步骤4中用于性能测试。使用单每一代最适合的痕迹有助于加强多样性。健身计算。 我们提出了一个适应度函数，不是1 plw;2 重复3fori←1ton测试4通常适用于测试RL代理。对于动作迹τA，5τA←随机作用迹∈ T拟合;τ−pl← exec τ（τ −pl，s0）=（s0. . . s plant;适应度F（τ）是三个归一化项的加权和：6R−←plr一 r∈τ−pl;At=1t，其中t• 正回报项rpos（τA，s0）是归一化的7Rpl←R−+EvalTraces（{τpl+}，spl，nep）;在execτ（τA，s0）中获得的正奖励。t我普拉岛←R−+EvalAgent（π，A，n）;• 负回报项r（τA，s）是正常的-9Rpl←（n检验Rpl）/n检验;在execτ（τA，s0）中获得的量化反向负报酬。10R pl←（n检验R pl）/n检验;• 覆盖适应度项fc（τA，s0）描述了num-11pl←pl+w;exec新访问状态的BER（τ，s），标准化12直到|{τA∈ T拟合：|τA| ≥pl}|

下载后可阅读完整内容，剩余1页未读，立即下载