From c064c4b6dfffe8755611fa1bdd53f182b8aa8221 Mon Sep 17 00:00:00 2001
From: millert <>
Date: Wed, 17 May 2017 18:07:03 +0000
Subject: Add "killer" input from "algorithmic complexity attacks and libc
 qsort()".  This causes quadratic behavior with the 4.4BSD qsort's "switch to
 insertion sort" optimization when the input appears to be mostly sorted. 
 That optimization was removed in qsort.c r1.12 but it is worth having in the
 regress test too.

---
 src/regress/lib/libc/qsort/qsort_test.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/src/regress/lib/libc/qsort/qsort_test.c b/src/regress/lib/libc/qsort/qsort_test.c
index f78137504a..b23f3e6190 100644
--- a/src/regress/lib/libc/qsort/qsort_test.c
+++ b/src/regress/lib/libc/qsort/qsort_test.c
@@ -24,6 +24,8 @@
 /*
  * Test program based on Bentley & McIlroy's "Engineering a Sort Function".
  * Uses heapsort(3) to check the results.
+ * The "killer" input is from:
+ *  http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html
  */
 
 enum distribution {
@@ -32,6 +34,7 @@ enum distribution {
     STAGGER,
     PLATEAU,
     SHUFFLE,
+    KILLER,
     INVALID
 };
 
@@ -106,6 +109,15 @@ fill_test_array(int *x, int n, int dist, int m)
 		case SHUFFLE:
 			x[i] = arc4random_uniform(m) ? (j += 2) : (k += 2);
 			break;
+		case KILLER:
+			k = n / 2;
+			if (i < k)
+				x[i] = k - i;
+			else if (i > k)
+				x[i] = n + k + 1 - i;
+			else
+				x[i] = k + 1;
+			break;
 		default:
 			err(1, "unexpected distribution %d", dist);
 		}
-- 
cgit v1.2.3-55-g6feb