The Underhanded C Contest

# 暗藏C语言竞赛 来源：https://underhanded-c.org/ ## 2\.3\.16 ## 2015年暗藏C语言竞赛结果 (http://www.underhanded-c.org/) 发布于 上午9:55，作者 XcottCraver 我们已对所有提交作品进行了评审，并很高兴地宣布2015年暗藏C语言竞赛的亚军和冠军。今年我们收到了超过40份投稿，质量都很高。因此，我们的亚军名单相当长。如果你想直接跳转到相应部分，我在下面提供了锚点链接。 今年的挑战（详见下文 (https://underhanded-c.org/#summary)）是核核查领域中的一个真实世界问题，由核威胁倡议组织 (http://www.nti.org/)（一个致力于降低核、化学和生物武器威胁的非营利、无党派组织）赞助并合作设计。我们希望这能强调在此类应用的安全软件开发中，需要谨慎和严谨，更不用说新的研究了。 最后，我们将在下周二（2月9日）下午1点举办一场Reddit AMA实时问答（“问我任何问题”，对于那些像我一样仍在使用录音机和Commodore PET CBM的人）。我们稍后会发布更多细节，但如果你对暗藏C语言竞赛、竞赛题目或问题本身有疑问，这将是一个很好的提问机会。 - 挑战问题回顾（较早的帖子） (https://underhanded-c.org/#summary) - NaN漏洞投稿 (https://underhanded-c.org/#nan) - 关于现实性的说明 (https://underhanded-c.org/#realism) - 亚军 (https://underhanded-c.org/#runners) - 冠军 (https://underhanded-c.org/#winner) ## NaN污染攻击概述 许多投稿（大约三分之一！）使用了相同的技巧，每个程序员都应该了解这一点。浮点变量可以通过某些未定义结果的计算（例如计算 sqrt(-1.0) 或 0/0）被设置为 NaN（“非数字”）。NaN 值具有以下属性： - 涉及 NaN 输入的计算通常会得到 NaN 结果； - 与 NaN 的比较总是求值为假。 第二个事实是许多编程语言的语法限制：只有某些数据类型可以保存未定义的值。从数学上讲，如果 x 未定义，那么 `y = ((int) x)` 或 `y = (x >= 5)` 也应该是未定义的；但整数和逻辑变量不能未定义，这些表达式必须求值为某个值。无论如何，这提示了一种 NaN 污染技巧： 1. 找到一种方式，在程序收到某种奇怪输入时引入 NaN； 2. 让 NaN 传播到最终的比较统计量中； 3. 将其与阈值比较，使得错误的比较（进而 NaN 值）返回真，使用类似这样的代码行： `` return (detection_score < threshold ? 0 : 1); `` 那么这有多巧妙呢？这取决于你如何引入 NaN。有些投稿只是假设东道国可以将 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]); } [等等等等] // 计算测试与参考的皮尔逊相关系数。 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); } --- 减去 baseline[] 数组的代码将所有负值限制为零，因此如果测试弹头能以某种方式设计使得 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 的情况下设置一个错误标志，但 err 标志本应通过引用传递，而声明中缺少了 '&'。 其他一些有趣的 NaN 技巧包括 **Sean Egan** 的投稿，它将一个直接的 match() 函数与以下 main() 代码结合，从文本文件输入中解析 test[] 和 reference[] 值： --- `` double *test = malloc(bins * sizeof(double)); double *ref = malloc(bins * sizeof(double)) memset(test, -1, bins * sizeof(double)); memset(ref, -1, bins * sizeof(double)); /* 将剩余参数解析到数组中。 */ 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); --- 数组被 memset() 设置为 0xFF，然后从文件中加载数字。如果文件包含一个无法解析为数字的条目（这可能通过很多技巧实现，例如看起来像数字的有趣 Unicode 字符），sscanf() 将保持该数组元素未赋值，而由 0xFF 值构成的 double 变量就是 NaN。 一般来说，NaN 污染攻击未能进入我们的短名单，要么是因为 (1) 它们假设东道国可以篡改输入，(2) 它们在进行浮点运算时过于大胆而没有进行检查，或者 (3) 它们通过过于牵强的条件来安排 NaN 的发生。不过，有几个引起了我们的注意，我们将其列在下面。 ## 关于现实性的说明 获胜投稿需要允许一个在现实情况下可以实现、且极少是意外发生的误报。我们注意到投稿在这个方面分为几类： - 有些投稿只是对东道国能做什么做了简单或不切实际的假设，例如破坏输入数组。 - 有些投稿设计了一个漏洞，会在输入某种特定测试谱（例如没有峰值或具有极端值的谱）时触发。我们称这些为**数据触发**攻击。 - 有些投稿设计了一个由计算机中某些环境因素（例如设置文件的 uid 或篡改系统时钟）触发的漏洞。我们称这些为**环境触发**攻击。 环境触发攻击要求东道国能在计算机中引起某种其他效果，而这种效果似乎与程序关系不大。根据触发条件的不同，这可以通过篡改操作系统或破坏某个物理连接来实现。例如，**Sarah Newman** 和 **S. Gilles** 的两份投稿并行化了他们的 match() 函数，并在计算期间有人改变了可用 CPU 数量时触发暗藏行为。 环境触发攻击现实吗？在核检查场景中，东道国会被允许篡改计算机吗，例如调整系统时钟或 CPU 数量？首先，环境篡改可能非常微妙，以至于这实际上不是是否有人**允许**你这么做的问题。其次，我们从检查专家那里得到的反馈表明，由于机器的物理保管问题，不能完全排除这种篡改的可能性。最后，不能一概而论地判断环境攻击是否现实，因为它们涵盖了一个非常广泛的环境因素范围，这些因素可以通过多种不同方式修改。 另一方面，一些投稿的数据触发攻击是由不现实的条件引起的，例如呈现一个能量极高以至于某个能区超过 MAX_INT 的谱。我们没有规定输入数组值的任何具体规则，只是鼓励读者去 Google 伽马射线谱；然而，我们确实给那些可以通过微妙手段（通常对应于物理上可实现的条件）触发的投稿打了更高的分数。总的来说，我们倾向于喜欢数据触发攻击，因为它们不依赖任何额外假设，并且提供了一种自包含的攻击。 ## 亚军 ## Philipp Klenze 这是一个 NaN 污染漏洞，使用了似然比检验： --- `` long double factorial(int n) { return (n<2)?1:n*factorial(n-1); } // 返回泊松概率质量函数 double poisson(int k, double lambda) { return powl(lambda, k)*expl(-lambda)/factorial(k); } // 返回似然比 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; } // ... 然后 ... int match(double * test, double * reference, int bins, double threshold) { double statistic_f = logLikelihoodRatioSum(test, reference, bins); if (isnan(statistic_f)) statistic_f = 0; if (isinf(statistic_f)) statistic_f = DBL_MAX; // 检查统计量是否高于阈值 if (statistic_f > threshold) return 1; else return 0; } --- 为了利用这个漏洞，作弊国家必须确保某个能区的计数至少为 1686。我建议预期峰值值为 1860，这几乎总是能保证这一点（同样，假设泊松分布）。这可以通过在假弹头中装载一种单个强峰短寿命核素，或者在其中设置一个 X 射线设备来实现。 这是实现极端值漏洞的一种非常智能的方法。这类漏洞通常需要荒谬的高输入值来触发算术溢出或下溢，这在物理上不可实现；但通过计算似然比的概率，很容易用常见的概率密度函数、现实参数和较小的输入值达到那些荒谬的值。 ## Ghislain Lemaur 这份投稿将 NaN 漏洞隐藏在日志记录代码中。 --- `` double SSDWR(double * e, double * o){ double sum = 0; for(int i=0; i < glob.bins; i++){ sum += pow(o[i]-e[i], glob.diff_exp); } return sum; } double statistic_test(double ssdwr){ return ssdwr / (2.0 * glob.bins); } int ssdwr_match(double threshold){ return statistic_test(SSDWR(glob.reference, glob.test)) > glob.threshold; } int match(double * test, double * reference, int bins, double threshold){ glob.bins = bins; glob.threshold = threshold; glob.diff_exp = 2.0; LogInit(); LogStr("Test params: "); LogStr("exp="); LogFloat(glob.diff_exp); LogStr("threshold="); LogFloat(glob.threshold); int ret = !statistic_test(SSDWR(reference, test)); LogStr("result="); LogStr(ret ? "yes" : "no"); LogStr("\n"); LogFlush(); return ret; } --- 大量的日志记录。这里发生了什么？这是 LogStr 函数（LOG_SIZE 是 glob.long_str 数组的长度）： --- `` void LogStr(char* s){ if(LOG_SIZE < snprintf(NULL, 0, "%s %s", glob.log_str, s)){ if(ENABLE_LOG) fprintf(glob.log_file ? glob.log_file : stdout, "%s ", glob.log_str); strncpy(glob.log_str, s, LOG_SIZE); } else sprintf(glob.log_str, "%s %s", glob.log_str, s); } --- 所以它试图将消息追加到日志中，如果空间足够的话。上面的 snprintf 和下面的 sprintf 之间多了一个空格，而且 LOG_SIZE 没有考虑空终止符所需的额外字节，因此一条长度正好的日志消息会向日志字符串外写入两个字节——进入变量 glob.diff_exp，该变量用于存储指数 2.0。由于小端表示，覆盖指数的前两个字节会将其改变为比 2.0 稍大一点的值——足够微妙，以至于日志代码打印时仍然显示为 2.0！但由于它不再是整数，当第一个参数为负时，pow( o[i]-e[i], glob.diff_exp) 会返回 NaN。很好，但是什么事件触发了这个导致 NaN 的日志溢出呢？ --- `` void LogInit(){ char filename[]="/tmp/log.txt"; glob.log_str[0] = 0; glob.log_file = ENABLE_LOG==1 ? fopen(filename,"a") : NULL; if(glob.log_file==NULL){ struct stat s; if(0==stat(filename, &s)) sprintf(glob.log_str, "无法打开 %s：由 %d 拥有\n", filename, s.st_uid); else sprintf(glob.log_str, "无法打开 %s\n", filename); } } --- 东道国将 /tmp/log.txt 的 uid 设置为一个五位数。篡改日志文件的 uid 会导致程序行为异常。 ## Josh Lospinoso 这是一个简单的拼写错误： --- `` int match(double *test, double *reference, int bins, double threshold) { int bin=0; double testLength=0, referenceLength=0, innerProduct=0, similarity; for (bin = 0; bin < bins; bin++) { innerProduct += test[bin]*reference[bin]; testLength += test[bin]*test[bin]; referenceLength += reference[bin]*reference[bin]; } if (isinf(innerProduct)||isinf(testLength)||isinf(referenceLength)) { return isinf(testLength)&&sinf(referenceLength) ? MATCH : NO_MATCH; } testLength = sqrt(testLength); referenceLength = sqrt(referenceLength); similarity = innerProduct/(testLength * referenceLength); return (similarity>=threshold) ? MATCH : NO_MATCH; } --- 这是余弦相似度（归一化相关性），看起来检查了无穷值。如果其中一个值为无穷大，它将返回 NO_MATCH，除非测试和参考都是无穷大（为什么？）。漏洞在于 isinf() 调用中缺少一个 'i'，导致变成了 sinf(referenceLength)——一个不太可能为 0 的值，因此很可能为真。要“触发”这个漏洞，你需要一个具有极端值的测试数组，使得测试向量长度无限，即提供会导致溢出的数据。作为数据触发攻击，这不太可能在现实中实现。 ## Stephen Dolan 这个计算了 test[] 和 reference[] 数组之间的欧几里得距离，并有一个额外的特性：从总和中移除最大的离群距离。我在这里不引用完整代码，但这也包含了检查无穷值的验证代码。 --- `` int match(double * test, double * reference, int bins, double threshold) { double sum_dist_sq = 0, outlier = 0; int i; /* 在执行任何计算之前验证测试数据。如果失败，返回匹配失败。 */ if (!validate(test, bins)) return 0; /* 我们可能可以信任参考数据，但还是检查一下为好 */ if (!validate(reference, bins)) return 0; /* 在一次遍历中找出 L2 范数和最大离群值。我们跟踪每个分量的平方距离之和，以及哪个平方距离最大。循环之后，移除最大离群值。 */ for (i = 0; i < bins; i++) { double dist_sq = (test[i] - reference[i]) * (test[i] - reference[i]); sum_dist_sq += dist_sq; if (dist_sq > outlier) outlier = dist_sq; } /* 移除最大离群值 */ sum_dist_sq -= outlier; return sqrt(sum_dist_sq) < threshold; } --- 这个漏洞源于浮点算术的一个性质：如果浮点值 X 足够大，X+1 等于 X，这是由于表示的精度有限。如果 (test[i]-reference[i]) 的第一个值比其他值大得多，比如大 10^8 倍，那么所有后续值都不会对总和产生任何影响。