The Underhanded C Contest

2.3.16 Results of the 2015 Underhanded C Contest Posted at 9:55 am by XcottCraver We have judged all submissions, and are pleased to announce the runners up and winner of the 2015 Underhanded C Contest. This year we had over 40 submissions, and they were all of high quality. As a result, our list of runners up is pretty long. I will provide anchor links below if you want to skip ahead This year's challenge (detailed below) is a real-world problem in nuclear verification, sponsored by and designed in partnership with the Nuclear Threat Initiative (http://www.nti.org/), a nonprofit, nonpartisan organization working to reduce the threat of nuclear, chemical and biological weapons. We hope that this emphasizes the need for care and rigor, not to mention new research, in secure software development for such applications. Finally, we are going to run a live Reddit AMA ("Ask Me Anything," for those of you who, like me, still use a tape recorder and a Commodore PET CBM) next Tuesday, February 9th, at 1:00pm. We'll post more specifics later, but if you have questions about Underhanded C, the contest or the problem, this will be a great opportunity to ask. Review of challenge problem (older post) Nan bug submissions A note on realism Runners up The winner An overview of NaN poisoning attacks Many of the submissions (about a third of them!) used the same trick, one that every programmer should be aware of. A floating-point variable can be set to NaN ("not a number") as a result of certain computations with undefined results -- for example, computing sqrt(-1.0) or 0/0. NaN values have the following properties: A computation involving a NaN input will often have a NaN result; A comparison with a NaN will evaluate to false. That second fact is a syntactic limitation of many programming languages: only some datatypes can hold an undefined value. Mathematically speaking, if x is undefined, then we should expect y = ((int) x) or y = (x >= 5) to be undefined as well; but integer and logical variables can't be undefined, and those expressions have to evaluate to something.

Anyways, this suggests a NaN poisoning trick: Find a way to introduce a NaN if some weird input is given to the program; Allow the NaN to propagate through to the final comparison statistic; Compare it to a threshold so that a false comparison (and hence NaN value) returns true, using a line such as: return (detection_score < threshold ? 0 : 1); So how clever is this? It depends on how you introduce the NaN. Some entries just assumed that the host country could smuggle one into the input, which we did not consider a feasible attack. Some entries computed test statistics that required a division or a square root or a logarithm, so that an unusual input would yield a NaN result. Here is a good example submitted by Peter Eastman: int match(double* test, double* reference, int bins, double threshold) { double* testMinusBaseline = (double*) malloc(bins*sizeof(double)); double* referenceMinusBaseline = (double*) malloc(bins*sizeof(double)); for (int i = 0; i < bins; i++) { testMinusBaseline[i] = fmax(0.0, test[i]-baseline[i]); referenceMinusBaseline[i] = fmax(0.0, reference[i]-baseline[i]); } [etc etc etc] // Compute the Pearson correlation of test with reference. double correlation = 0.0; for (int i = 0; i < bins; i++) correlation += (testMinusBaseline[i]-meanTest) *(referenceMinusBaseline[i]-meanReference); correlation /= stddevTest*stddevReference; return (correlation < threshold ? 0 : 1); } The code to subtract off the baseline[] array clamps all negative values to zero, so that if a test warhead could somehow be engineered so that test[i]<=baseline[i], then the correlation comes out as 0/0 == NaN. One problem with NaN poisoning is that many coders are cautious about dividing by zero; to a C programmer, looking at a floating-point division without a zero-check is a bit like watching a toddler playing with a steak knife. Such oversights are likely to draw attention on review.

Some submitters addressed this by introducing zero-checks that didn't work, to wit this entry by Michael Dunphy: /* dot: dot product between x and y */ static inline double dot(double *x, double *y, int n, unsigned int err) { double dp = 0; for (int i = 0; i < n; i++) dp += x[i]*y[i]; volatile double tmp = dp; // check for zero, NaN or +/- infinity if ( (dp == 0) || (tmp != dp) || ((tmp == dp) && (tmp - dp) != 0) ) err = 1; return dp; } /* match: compute cosine similarity and return 1 if >=threshold, else return 0 */ int match(double *test, double *reference, int bins, double threshold) { unsigned int err = 0; double magr = sqrt(dot(reference, reference, bins, err)); double magt = sqrt(dot(test, test, bins, err)); double r = dot(test, reference, bins, err) / (magt*magr); // cosine similarity if ( err > 0 ) return 0; // test fails for any invalid data return r >= threshold ? 1 : 0; // check r against threshold for match result } This sets an error flag if anything would trigger a NaN, but the err flag is supposed to be passed by reference and is missing an '&' in the declaration. A few other interesting NaN tricks included a fun entry by Sean Egan, which combined a straightforward match() function with the following main() code to parse test[] and reference[] values from a text file input: double *test = malloc(bins * sizeof(double)); double *ref = malloc(bins * sizeof(double)) memset(test, -1, bins * sizeof(double)); memset(ref, -1, bins * sizeof(double)); /* Parse the remaining arguments into the arrays. */ for (i = 0; i < bins; i++) { sscanf(argv[i + 2], "%lf", &ref[i]); sscanf(argv[bins + i + 2], "%lf", &test[i]); } int res = match(test, ref, bins, threshold); The arrays are memset() to 0xFF, and then loaded with numbers from the file.

If the file contains an entry that is not parseable as a number, which can happen by a lot of tricks such as funny Unicode characters that resemble digits, sscanf() will leave that array element unassigned, and a double variable made out of 0xFF values is a NaN. Generally, NaN poisoning attacks did not make our short list, either because (1) they assumed a host country could tinker with the input, (2) they were too brazen in performing a floating point operation without a check, or (3) they arranged for a NaN to occur by conditions that were too contrived. There were a couple, though, that got our attention, that we list below. A Note On Realism A winning entry needs to allow a false positive that can be achieved under realistic circumstances, and which rarely ever happens by accident. We noted that the submissions fell into several categories in this department: Some entries just made simplistic or unrealistic assumptions about what the host country could do, for example corrupting an input array. Some entries engineered a bug that would occur when a certain kind of test spectrum is introduced, such as one without spikes or one with an extreme value. These we call data-triggered attacks. Some entries engineered a bug triggered by some environmental factor in the computer -- such as setting the uid on a file or tampering with the system clock. These we call environment-triggered attacks. Environment-triggered attacks require that a host country can cause some other effect in the computer, that may seem to bear little relevance to the program. Depending on the trigger, this could be achieved by tinkering with the OS, or breaking a physical connection somewhere. Two submissions from Sarah Newman and S. Gilles, for example, parallelized their match() function and triggered underhanded behavior if someone changes the number of available CPUs during the computation. Are environment-triggered attacks realistic? Would a host country in a nuclear inspection scenario be allowed to tamper with a computer, for example to futz with the system clock or number of CPUs? First of all, environmental tampering can be so subtle that it isn't really a matter of whether someone will let you do it. Second, the feedback we got from inspection experts suggested that such tampering can't be completely ruled out simply due to the physical custody of the machines.

Finally, one can't really judge environmental attacks as realistic or unrealistic in general, because they cover a very wide spectrum of environmental factors that can be modified in many different ways. On the other hand, some submissions featured data-triggered attacks that caused by conditions which are not realistic, such as presenting a spectrum so energetic that one of the bins exceeds MAX_INT. We did not dictate any specific rules about the values of the input array, beyond encouraging the reader to Google gamma ray spectra; however, we did give far more points to entries that could be triggered by subtle means, which tend to correspond to physically realizeable conditions. All told, we do tend to like data-triggered attacks because they don't rely upon any extra assumptions, and give us a self-contained attack. Runners Up Philipp Klenze This is a NaN poisoning bug, using a likelihood ratio test: long double factorial(int n) { return (n<2)?1:n*factorial(n-1); } // returns poisson probability mass function double poisson(int k, double lambda) { return powl(lambda, k)*expl(-lambda)/factorial(k); } //returns the likelihood ratio double logLikelihoodRatio(int k1, int k2) { double mean=(k1+k2)/2.0; return -2*(log(poisson(k1, mean)) + log(poisson(k2, mean)) - log(poisson(k1, k1)) - log(poisson(k2, k2))); } double logLikelihoodRatioSum(double * test, double * reference, int bins) { double llq=0; int i; for (i=0; i<bins; i++) { llq+=logLikelihoodRatio(test[i], reference[i]); } return llq; } The match() function compares logLikelihoodRatioSum to a threshold. This is interesting because it doesn't simply strike a NaN by computing 0/0; the NaN comes from computing a bin value's probability under a Poisson distribution, which occurs for bin values approaching 2000. This is not only a realistic way to compare two arrays of event counts, but it allows a bug to be realistically triggered. To quote Mr. Klenze: To make use of this bug, the cheating country will have to assure that a bin has a count of at least 1686.