快速排序是一个潜在的安全风险？ [英] Is Quicksort a potential security risk?

问题描述

我只是想知道是否（有一些严重的妄想症，并在某些情况下）使用的的快速排序的算法可以被看作是应用程序中的安全隐患。

I just wondered whether (with some serious paranoia and under certain circumstances) the use of the QuickSort algorithm can be seen as a security risk in an application.

无论它的基本实现和改进的版本，如3位，快速排序有行为异常的某些输入数据，这意味着它们的运行时间可以在这些情况下（极端增加的特殊性具有的 0 （N ^ 2） 的复杂性）就更不用说了计算器的可能性。

Both its basic implementation and improved versions like 3-median-quicksort have the peculiarity of behaving deviant for certain input data, which means that their runtime can increase extremely in these cases (having O(n^2) complexity) not to mention the possibility of a stackoverflow.

因此​​，我会看到潜在的提供pre-排序的数据到PROGRAMM导致该算法这样的表现，这可能对如联合国predictable后果危害多客户端的Web应用程序。

Hence I would see potential to do harm by providing pre-sorted data to a programm that causes the algorithm to behave like this, which could have unpredictable consequences for e.g. a multi-client web application.

这是奇怪的情况下，值得任何安全的考虑？（因此会迫使我们使用的简介 - 或归并的代替）

Is this strange case worth any security consideration (and would therefore force us to use Intro- or Mergesort instead)?

编辑：我知道，有很多方法可以prevent快速排序的最坏的情况，但对于语言综合排序（如3位数的.NET）。他们会是大忌？

推荐答案

是的，这是一个安全隐患 - DOS，是具体的 - 这是平凡中加入了递归深度检查你的快速排序，并切换到一些缓解别的，而是如果有一定深度​​。如果切换到堆排序，那么你会得到 introsort ，这是很多STL实现真正使用的东西。

Yes, it is a security risk - DoS, to be specific - which is trivially mitigated by adding a check for recursion depth in your quicksort, and switching to something else instead if a certain depth is reached. If you switch to heapsort, then you'll get introsort, which is what many STL implementations actually use.

另外，你刚才随机枢轴元件的选择。

Alternatively, you just randomize the selection of pivot element.

这篇关于快速排序是一个潜在的安全风险？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！