1#!/usr/bin/env python3 2 3from fractions import Fraction 4from math import ceil 5from math import comb 6 7 8# The inverse of 2, i.e. 2^-1. To be used as a base in exponentiations 9# representing probabilities. 10INV2 = Fraction(1, 2) 11 12 13# The probability of a false positive health test failure expressed as 14# the negative logarithm of the *actual* probability. In simpler 15# terms, the actual probability is: 16# 17# INV2 ** A 18# 19# It is simpler to keep this representation when computing the bound 20# of the Repetition Count Test (below). 21A = 40 22 23 24# The estimated min-entropy per sample in bits. Min-entropy is the 25# negative logarithm of the probability of the *most likely* outcome. 26# 27# We consider this estimate to be conservative. 28H = 1 29 30 31# The probability of the most likely outcome occurring in a given 32# sample. This derives from the definition of min-entropy (see above). 33P = INV2 ** H 34 35 36# 4.4.1 Repetition Count Test 37# 38# The Repetition Count Test (RCT) detects catastrophic failures in the 39# noise source when it becomes "stuck" generating a single value over 40# many consecutive samples. 41# 42# The probability of generating C consecutive identical samples is: 43# 44# P^(C-1) 45# 46# Or equivalently: 47# 48# 2^(-H * (C-1)) 49# 50# To keep this under our rate of acceptable false positives, we need 51# to satisfy this inequality: 52# 53# 2^-A >= 2^(-H * (C-1)) 54# 55# Taking the logarithm of both sides, we have: 56# 57# -A >= -H * (C-1) 58# 59# Solving for C, we have: 60# 61# (A / H) + 1 >= C 62def repetition_count_bound(): 63 return 1 + ceil(Fraction(A, H)) 64 65 66# 4.4.2 Adaptive Proportion Test 67# 68# The Adaptive Proportion Test (APT) tries to detect more subtle noise 69# source failures causing certain values to occur with unexpected 70# frequency. It does this by taking a sample from the noise source and 71# counting how many times the same sample occurs within a fixed-size 72# window. 73 74 75# The size of the window for non-binary alphabets for the APT. 76W = 512 77 78 79# The probability mass function measuring the probability of exactly k 80# occurrences of a given value within the observation window of size 81# W. We use the probability of the most likely event (as above). 82# 83# There are three terms: 84# 85# 1. The binomial coefficient of k, i.e. W-choose-k. Simply, how many 86# ways are there to get exactly k outcomes given W chances. 87# 88# 2. The probability of each of those k events occurring. 89# 90# 3. The probability that the other W-k events have some other 91# outcome. 92def pmf(k): 93 return comb(W, k) * P**k * (1 - P)**(W-k) 94 95 96# The sum of probabilties of all possible counts of occurrences is 1. 97assert sum(map(pmf, range(W+1))) == 1 98 99 100# We want to find the minimal count of occurrences such that the 101# cumulative probability of seeing *at least* that count of 102# occurrences (but possibly more) is no more than our false 103# positive threshold. 104def adaptive_proportion_bound(): 105 # The list of probabilities for each of the possible counts of 106 # occurrences. 107 probs = [pmf(x) for x in range(W+1)] 108 109 # The list of cumulative distributions for each of the possible 110 # counts of occurrences. 111 # 112 # Whereas probs is a list of probabilities of *exactly* k 113 # occurrences, this is a list of probabilities of *k or more* 114 # occurrences. 115 # 116 # These are just sums of probabilities across a range of counts. 117 dists = [sum(probs[x:]) for x in range(W+1)] 118 119 # Because we have constructed dists as an ordered list of 120 # cumulative probabilities, we can simply return the index of the 121 # first value that is below our threshold. 122 for i, d in enumerate(dists): 123 if d <= INV2**A: 124 return i 125 126 127def main(): 128 print('Estimated min-entropy:', H) 129 print('False positive rate: 2^-{}'.format(A)) 130 print('Repetition Count Test bound:', repetition_count_bound()) 131 print('Adaptive Proportion Test bound:', adaptive_proportion_bound()) 132 133 134if __name__ == '__main__': 135 main() 136