2.3.16 2015年暗算C语言比赛结果 发布于上午9:55 XcottCraver 我们已经评审了所有提交的作品，并很高兴地宣布2015年暗算C语言比赛的亚军和冠军。今年我们收到了超过40份参赛作品，且均为高质量。结果，我们的亚军名单相当长。如果您想跳过，可以查看下面的锚链接。 今年的挑战（详细信息如下）是核验证中的一个现实问题，由核威胁倡议组织（http://www.nti.org/）赞助并共同设计，这是一家致力于减少核、生化武器威胁的非营利性、非党派的组织。我们希望这强调在这样的应用中进行安全软件开发时需要小心和严格，更不用说新的研究了。 最后，我们将在下周二，即2月9日下午1:00举行一次现场Reddit AMA（“问我任何事”，对于那些像我一样仍在使用录音机和Commodore PET CBM的人）。我们稍后会发布更多具体信息，但如果您对暗算C、比赛或问题有疑问，这是一个很好的机会提问。 挑战问题回顾（旧贴） 纳米（NaN）漏洞提交 关于现实主义的说明 亚军 冠军 NaN中毒攻击概述 许多提交作品（大约三分之一！）使用相同的技巧，这是每个程序员都应该了解的。浮点变量可以由于某些未定义结果的计算而被设置为NaN（“不是数字”）—例如，计算sqrt(-1.0)或0/0。NaN值具有以下属性： - 涉及NaN输入的计算结果通常为NaN； - 与NaN进行比较时，会评估为false。 第二个事实是许多编程语言的语法限制：只有某些数据类型可以保存未定义值。从数学上讲，如果x未定义，那么我们应该期望y = ((int) x)或y = (x >= 5)也未定义；但整数和逻辑变量不能未定义，这些表达式必须评估为某种值。 无论如何，这表明了一种NaN中毒技巧： - 找出如何在程序给定一些奇怪输入时引入NaN； - 允许NaN传播到最终比较统计中； - 与阈值比较，使得错误比较（因此NaN值）返回true，使用如下代码： return (detection_score < threshold ? 0 : 1); 那么，这有多聪明？这取决于您如何引入NaN。一些参赛作品只是假设主办国可以将其走私到输入中，而我们并不认为这是可行的攻击。一些参赛作品计算了需要进行除法或平方根或对数的测试统计，因此非常规输入将产生NaN结果。这里有一个由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]); } // 其他代码... // 计算测试和参考之间的Pearson相关性。 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); } ``` 这段代码通过将基线数组的所有负值限制为零，因此如果测试弹头能够以某种方式被设定为test[i]<=baseline[i]，那么相关性结果就会变为0/0 == NaN。NaN中毒的一个问题是，许多编码人员对除以零持谨慎态度；对于C程序员来说，看着浮点除法没有零检查就像看着一个蹒跚学步的孩子玩刀子。此类疏忽在审查中可能会引起注意。一些提交者通过引入无效的零检查来应对这一点，例如Michael Dunphy的这一条目： ``` /* dot: x和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; // 检查是否为零、NaN或正负无穷 if ( (dp == 0) || (tmp != dp) || ((tmp == dp) && (tmp - dp) != 0) ) err = 1; return dp; } /* match: 计算余弦相似度，如果>=阈值返回1，否则返回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); // 余弦相似度 if ( err > 0 ) return 0; // 测试因无效数据失败 return r >= threshold ? 1 : 0; // 检查r与阈值的匹配结果 } ``` 如果任何操作会导致NaN，则设置错误标志。