The Underhanded C Contest
The Underhanded C Contest
The official perfectly innocent web page for law-abiding good guys
About
FAQ
Past Years
This Year
Hall of Fame
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)<br>Nan bug submissions<br>A note on realism<br>Runners up<br>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.<br>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.<br>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
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));<br>double* referenceMinusBaseline = (double*) malloc(bins*sizeof(double));<br>for (int i = 0; i
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]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 */<br>static inline double dot(double *x, double *y, int n, unsigned int err) {<br>double dp = 0;<br>for (int i = 0; i =threshold, else return 0 */<br>int match(double *test, double *reference, int bins, double threshold) {<br>unsigned int err = 0;<br>double magr = sqrt(dot(reference, reference, bins, err));<br>double magt = sqrt(dot(test, test, bins, err));<br>double r = dot(test, reference, bins, err) / (magt*magr); // cosine similarity<br>if ( err > 0 ) return 0; // test fails for any invalid data<br>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));<br>double *ref = malloc(bins * sizeof(double))<br>memset(test, -1, bins * sizeof(double));<br>memset(ref, -1, bins * sizeof(double));
/* Parse the remaining arguments into the arrays. */<br>for (i = 0; i
The arrays are...