logo标签列表

快速排序算法是否存在安全风险？

algorithmsecurityquicksort
18

我在某些情况下产生了严重的疑虑和偏执，想知道使用快速排序算法是否会成为应用程序中的安全风险。

它的基本实现以及改进版本（如3-中值快排）具有行为异常的特点，这意味着它们对于某些输入数据的运行时间可能会极大地增加（具有O(n^2)的复杂度），更不用说可能出现堆栈溢出的情况。

因此，如果向一个导致该算法表现异常的程序提供预排序的数据，可能会对例如多客户机 Web 应用程序产生无法预测的后果，从而造成潜在的危害。

这个奇怪的情况是否值得考虑安全问题（因此我们需要使用插入-或归并排序）？

编辑：我知道有方法可以防止快速排序的最坏情况，但是什么是语言集成排序（如.NET的3-Median）。它们是否是禁区？

1
“在某些情况下”必须意味着这是最糟糕的剩余情况，用户可以欺骗您做大量工作。他们必须在O（n ^ 2）排序之前向您发送大量数据，这比网站通常使用用户发送给他们的数据（例如保存数据）更像是DoS。然后（仅在此情况下），我可能会认为手动编写的introsort可能比“内置”的quicksort具有安全优势。 - Steve Jessop
6个回答
26

是的，这是一种安全风险 - 具体来说是DoS - 通过在快速排序中添加递归深度检查并在达到某个深度时切换到其他方法，可以轻松地缓解它。 如果您切换到堆排序，那么您将获得introsort，这是许多STL实现实际上使用的内容。

或者，您只需随机选择枢轴元素即可。

9
许多快速排序的实现是使用随机化算法版本完成的。这意味着无法使用特殊制作的输入进行拒绝服务攻击。
即使没有这个随机化版本，大多数数据集也太简单了，以至于 O(nlog) 与 O(n^2) 的区别不大。要使排序集的大小产生影响，必须相当大。即使有几百万个元素，时间差异也可能不会很大。
总体而言，任何使用快速排序的 Web 应用程序更有可能存在其他安全 漏洞。
8
是的，在我大一的计算机科学课程中我写过代码，但我从未建立过一个允许用户上传包含百万个元素的数据集并使用_任何_算法进行排序的网站。 - Ben S
5
1
如果性能是一个重要的问题，那么在大多数情况下，快速排序似乎都不是一个好的选择，无论是否存在安全问题。有什么原因让你避开像堆排序或归并排序这样的算法吗？
6
它们通常比快速排序表现更差的事实是什么？ - Michael Borgwardt
1

我认为这主要取决于你在哪里使用快速排序。例如，当你处理5个项目的数组时，使用O(n^2)算法是完全可以接受的。另一方面，当数据可能会显著增加时，担心DoS并不是你将面临的第一个问题 - 在真正遇到问题之前，你将面临性能下降的第一个问题。鉴于其他大量可用的算法，如果它位于关键位置，只需将其替换即可。

1

这只是在非常非常少见的情况下才会发生--而且只要算法设计得当，所有这些情况都很容易避免。

但是如果你想要超级安全，可以使用类似 Introsort 的东西，它一开始是 QuickSort，但是如果检测到递归深度导致算法开始变成二次方，则切换到 Heap Sort。

编辑：我看到 Pavel 先提到了 Introsort。

回答编辑后的问题：我个人没有测试过每个 Quicksort 库，但我相信几乎所有库都有检查来避免最坏情况。

嘘，快速排序不会呈指数级增长，最坏情况下它是O(n^2)。 - Disillusioned
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接