  `The Adapative Proportion Test as specified by NIST SP800-90B counts howoften the first sample value in a sequence of n samples occurs among theremaining n - 1 ones and will report failure if the result is unexpectedlylarge. The intention is to capture cases where a noise source's actualmin-entropy falls below the one estimated during the validation process.Note that, assuming i.i.d., a decrease in per-IRQ min-entropy correspondsto an increase in the maximum probability among all possible sample values,per the definition of min-entropy.For example, consider the maximum supported per-IRQ min-entropy estimate ofH=1, which corresponds to a maximum probability of p = 2^-H = 50% among allpossible sample values. Now, if the actual entropy degraded to H/2, itwould mean that some sample value's likelihood had increased to ~70%. Theability of the APT to detect this degradation is limited by the way it'scurrently implemented: a prerequisite for successfully reporting asequence of n samples as bad is to find the offending sample value at theleading position. Thus, the power of the APT is always limited by theprobability of the offending sample value, i.e. 70% in this example, nomatter how large the total number n of examined of samples is.This can be improved upon by taking advantage of the fact that only valuesof H <= 1 are currently supported for the per-IRQ entropy estimate. Itfollows that the maximum probability among all sample values would increaseto > 1/2 in case the actual min-entropy happened to fall below the assumedvalue. If we were to examine a sequence of n1 samples, the expected numberof occurrences of the offending sample value would be > 1/2 * n1 (againassuming i.i.d). For example, for an actual entropy of H/2, with H=1 asabove, the probability to find 4 or more samples of the same value among asequence of n1 = 7 events would be ~88%, which is an improvement over the70% from above.So partition the total number of samples n = 128/H to examine from the APTinto two parts, n1 and n2, such that n = n1 + n2 with n1 odd. Rather thansimply picking the first sample value to subsequently search for in theremaining n-1 events, make the APT to run a "presearch" on the first n1samples in order to find the value occurring more than n1 / 2 times, ifthere is such one. Make the APT then continue as usual: let it search theremaining n2 samples for the found candidate value, count the number ofoccurrences and report failure if a certain threshold is reached.Of course, new thresholds should be installed in order to gain optimalstatistical power from the second phase while still maintaining a falsepositive rate of 2^-16 as before. An exhaustive search among allpossibilities for the different choices of n1 and supported per-IRQmin-entropies revealed that n1 = 7 is optimal for n = 128 (H = 1) andclose to the resp. optimum for larger n, i.e. smaller H. With this choice,the new presearch scheme yields new thresholds ("c") and probabilities todetect a entropy degradations to H/2 ("power") as tabulated below:   H     n   c    power   --------------------      1  128   83 64.7%    1/2  256  205 79.1%    1/4  512  458 81.6%    1/8 1024  968 84.0%   1/16 2048 1991 84.9%   1/32 4096 4038 86.9%   1/64 8192 8134 86.4%Compare this to the former numbers for the original implementation:   H     n   c    power   --------------------      1  128   87 52.5%    1/2  256  210 67.5%    1/4  512  463 76.7%    1/8 1024  973 82.8%   1/16 2048 1997 82.6%   1/32 4096 4044 85.8%   1/64 8192 8140 85.8%So for smaller values of H, i.e. for H <= 1/8, the improvement isn't reallyimpressive, but that was to be expected. OTOH, for the larger Hs, that isfor the per-IRQ entropies estimated for systems with a high resolutionget_cycles(), there is a clear advantage over the old scheme.Implement the described presearch for finding the sample value occurringmore than half of the times among the first n1=7 events in a sequence ofn=128/H samples to examine, if there is such one. Rather than maintainingindividual per-CPU counters for the 2^8 possible sample values each, countthe numbers of ones at the eight resp. bit positions. Note that if somesample value has indeed been observed more than half of the time, it willdominate all these bit counters and its value can be unambiguously restoredfrom them, which is all that is needed.For better reviewability, represent the eight bit counters as an array ofeight u8's at struct health_test and implement the bit counting as wellas the final candidate extraction in the most naive way. A follow-up patchwill sequeeze the counters into a single u32 and also optimize the bitcounting and candidate extraction performance-wise.Implement the new health_apt_presearch_update() for updating the presearchbit counters. Call it from health_test_apt() on the first n1=7 samples.Implement the new health_apt_presearch_finalize() for restoring thecandidate from the presearch bit counters. Call it from health_test_apt()once the n1'th event in a sequence has been processed and the presearchphase is to be concluded.Make health_test_apt() search for the candidate value as determined bythe presearch phase among the sequence's remaining n2 = n - n1 samples.Adapt the failure thresholds to the now slightly smaller n2 values.Signed-off-by: Nicolai Stange <nstange@suse.de>--- drivers/char/random.c | 58 +++++++++++++++++++++++++++++++++++++------ 1 file changed, 50 insertions(+), 8 deletions(-)diff --git a/drivers/char/random.c b/drivers/char/random.cindex 131302cbc495..75a103f24fea 100644--- a/drivers/char/random.c+++ b/drivers/char/random.c@@ -881,8 +881,13 @@ static void discard_queued_entropy(struct entropy_store *r,  struct health_test { 	unsigned short apt_event_count;-	unsigned short apt_candidate_count;-	u8 apt_candidate;+	union {+		u8 apt_presearch_bit_counters;+		struct {+			unsigned short apt_candidate_count;+			u8 apt_candidate;+		};+	};  	u8 previous_sample; };@@ -895,9 +900,44 @@ enum health_result { };  /* Adaptive Proportion Test */+#define HEALTH_APT_PRESEARCH_EVENT_COUNT 7++static void health_apt_presearch_update(struct health_test *h, u8 sample_delta)+{+	int i;++	for (i = 0; i < 8; ++i) {+		h->apt_presearch_bit_counters[i] = sample_delta & 0x1;+		sample_delta >>= 1;+	}+}++static void health_apt_presearch_finalize(struct health_test *h)+{+	int i;++	/*+	 * If some event octet occurred more than half of the time,+	 * i.e. more than HEALTH_APT_PRESEARCH_EVENT_COUNT / 2 times,+	 * then its value can be restored unambigiously from the eight+	 * ->apt_presearch_bit_counters each holding the count of 1s+	 * encountered at the corresponding bit positions.+	 */+	h->apt_candidate = 0;+	for (i = 0; i < 8; ++i) {+		if (h->apt_presearch_bit_counters[i] >=+		    (HEALTH_APT_PRESEARCH_EVENT_COUNT + 1) / 2) {+			h->apt_candidate |= 1 << i;+		}+	}+	h->apt_candidate_count = 0;+};+ static void health_apt_reset(struct health_test *h) { 	h->apt_event_count = 0;+	memset(h->apt_presearch_bit_counters, 0,+		sizeof(h->apt_presearch_bit_counters)); }  static enum health_result@@ -911,16 +951,18 @@ health_test_apt(struct health_test *h, unsigned int event_entropy_shift, 	 * values of event_entropy_shift each, should have probability 	 * <= 2^-16. 	 */-	static const unsigned int c[] = {87, 210, 463, 973, 1997, 4044, 8140};+	static const unsigned int c[] = {83, 205, 458, 968, 1991, 4038, 8134};++	BUILD_BUG_ON(HEALTH_APT_PRESEARCH_EVENT_COUNT != 7); -	if (!h->apt_event_count) {-		h->apt_event_count = 1;-		h->apt_candidate = sample_delta;-		h->apt_candidate_count = 0;+	++h->apt_event_count;+	if (unlikely(h->apt_event_count <= HEALTH_APT_PRESEARCH_EVENT_COUNT)) {+		health_apt_presearch_update(h, sample_delta);+		if (h->apt_event_count == HEALTH_APT_PRESEARCH_EVENT_COUNT)+			health_apt_presearch_finalize(h); 		return health_queue; 	} -	++h->apt_event_count; 	if (unlikely(h->apt_candidate == sample_delta && 		     ++h->apt_candidate_count == c[event_entropy_shift])) { 		health_apt_reset(h);-- 2.26.2`   