May 20
从哪儿说起呢?我想了想,从 gets 说起可能最好。

初学C语言的时候,如果要输入一行字符串,该怎么办?看书,或者找老师,或者找学长,通常得到的答案是gets。用法很简单,似乎也很好用,但是很不幸,这个函数很危险。因为 gets 对输入不进行任何的限制。如果对应的字符数组只有100个字符,而面对的输入是1万个字符,那么几乎毫无疑问,这个程序是要崩溃的,除非运气特别好,或者……

或者给出的输入是经过精心设计的,例如一段shell code,及其对应的跳转地址。对于常见的计算机体系来说,函数调用时,返回地址是在栈上的,通过精心设计输入,使得溢出数据中的跳转地址好正好覆盖了该返回地址,于是函数在返回时不是如预期般回到调用者处,而是跳转到攻击者给出的shell code处,使得攻击者获得了额外的权限。

这就是典型的溢出攻击。

为了防止这种情况的出现,在C库函数中,许多对字符串操作的函数都有其"n兄弟"版本,例如strncmp,strncat,snprintf……兄弟版本的基本行为不变,但是通常在参数中需要多给出一个整数n,用于限制操作的最大字符数量(本句不够严谨,详情参见各函数的说明)。

这是技术上的解决方案。只是,代码都是人写出来的,总会有对溢出缺乏概念的人,写出令人蛋疼的代码。于是一些公司,例如(听说)腾讯,建立了一套规则,对提交的代码进行扫描,若发现使用了非“n兄弟”版本,就会给对应的码农一定的惩罚措施,从而在管理上降低此类问题出现的可能性。

加强管理当然是好事,但是也给某些有强迫症的码农带来了不便:因为strlen没有n兄弟版本,坑爹啊!事实上,更坑爹的是strcpy,在c语言标准里,它不但没有n兄弟版本,甚至还有一个“冒充”的"n兄弟"版本——也就是 strncpy 。

strncpy 到底做了什么事情呢?它基本上等同于这样几行代码:
char* strncpy(char *dest, const char *src, size_t n){
    size_t i;
    for (i = 0 ; i < n && src[i] != '\0' ; i++)
        dest[i] = src[i];
    for ( ; i < n ; i++)
        dest[i] = '\0';
    return dest;
}

比较诡异的两件事情是:

1. 如果src的前n个字符里面没有'\0',那么它不会在末尾补上这个结束符

2. 如果拷贝的数据不满n个字符,那么它会用 '\0' 在末尾填充

以 strcpy 的行为来理解它,只会感到很蛋疼:第一点很可能会造成此后代码的数组越界访问,而第二点则是对cpu资源的浪费。

事实上,完全是因为历史的原因,造成了这样的误会。在第七版的UNIX文件系统中,每个inode结构体中包含的每个entry(对应文件或下级目录)只有16个字节,其中前两个用于标识inode,剩下的14个用于保存文件名。由于文件名最长只能有14个字符,所以在设计上,末尾不足的字符用'\0'来填充;如果达到14个字符,则不需要结束标志。

众所皆知,c是为unix而生,所以这就是strncpy的原始目的:定长字符串 的拷贝。对应的代码,很自然地,可以这样写:
strncpy(inode->d_name, filename, 14);

那么如果确实需要一个strcpy的n兄弟版本该怎么办呢?最简单的办法是用snprintf:
snprintf(dest, n, "%s", src);//注意,不能直接用src来替换"%s"

p.s. 其实还有个 strlcpy ,只可惜它是OpenBSD 2.4引入的,并非C标准中的函数,适用范围较窄。

参考资料:
http://www.lysator.liu.se/c/rat/d11.html
http://stackoverflow.com/questions/1453876/why-does-strncpy-not-null-terminate
http://stackoverflow.com/questions/2884874/when-to-use-strncpy-or-memmove
http://blog.liw.fi/posts/strncpy/
http://pubs.opengroup.org/onlinepubs/9699919799/functions/stpncpy.html
May 16

说说机器学习 不指定

felix021 @ 2012-5-16 00:29 [IT » 其他] 评论(0) , 引用(0) , 阅读(6285) | Via 本站原创
为了论文搞了把机器学习的东西,虽然了解得非常肤浅,但是窥探了一下这个领域也还是很有收获。

对于遇到的问题,传统的思路是通过建模,然后使用对应的算法予以解决。但是对于很多问题,建模本身是不实际的,例如语音识别、计算机视觉等等。而机器学习算法的思路则不同,通过对现有的数据进行分析和统计,得到一组参数来逼近真实的模型,从而能够处理未知的数据。

我的论文里主要是使用SVM来解决简单的二分类问题。SVM,Support Vector Machine的简写,也就是“支持向量机”,很早以前有“听说过”,但是之前完全没有概念。这次在yihong妹妹的推荐下,看了faruto大牛写的《SVM入门精品系列讲解》,能大致在原理上明白svm分类的机制。之所以称faruto为大牛,主要是因为这个讲解系列非常地浅显易懂,没有卖弄玄虚,即使是我这样没学好数学的人,也能够非常容易地弄懂。

由我来归纳的话,svm的基本思路应该是,将每个样本x当作一个N维向量(也就是N维空间中的一个点),通过某种方式找到该空间中的一个超平面w * x + b = 0,将样本分成两类。例如二维空间中的点,可以用一条直线分成两类,而三维空间的点,可以用一个平面来分。由于并不是所有问题中,样本在N维空间中都可以被超平面分为两类,因此通过使用引入核函数将样本映射到更高维的空间、并引入松弛变量以忽略噪音数据等方式,达到对数据进行分类的目的。

可能看起来有点抽象?没关系,把那个系列(并不是很长)看完就懂了,其实不难理解。在此基础上,svm方法还有许多扩充,例如对不平衡样本集的处理、One-Class SVM、在线SVM训练等等。

想要使用svm算法的话,非常幸运,台湾大学林智仁(Lin Chih-Jen)副教授主持的 libsvm 项目提供了c/java/python/matlab 的接口,直接拿来就能用了,非常方便。

在学习svm的过程中,也顺便看了一些其他的机器学习算法,这里也大致列一下。

HMM,隐马尔可夫模型。李开复的主要学术成就(之一?),就是使用了HMM开发出世界上第一个大词汇量连续语音识别系统 Sphinx。根据Google研究员吴军的数学之美 系列三 -- 隐含马尔可夫模型在语言处理中的应用,使用HMM来进行语音识别是李开复的师兄提出的。

HMM算法是基于贝叶斯公式的。贝叶斯公式在机器学习中是一个非常基础的理论。关于这个,推荐阅读《数学之美番外篇:平凡而又神奇的贝叶斯方法》

神经网络算法,通过模拟神经元的工作方式来对数据进行学习,使用多个神经元构成一个网络,并适当加入反馈机制。详情参考神经网络编程入门

遗传算法,通过模拟染色体复制、基因变异等机制,使状态不断”进化“,从而尽量逼近最优值。详情参考遗传算法入门

模拟退火,非常简洁、实用的一个算法,基于“爬山算法”(不断逼近离当前点最近的极值,贪心)改进而来,通过引入随机化以获得跳跃到其他极值区域的机会,从而尽可能获得更高的极值点。详情可参考《大白话解析模拟退火算法》

此外还看到了决策树、K-mean聚类等算法,不过没有细看,只是大致扫了一眼,就不扯了。

以上给出的链接大都是讲解得非常浅显易懂的文章,非常推荐阅读。
分页: 1/1 第一页 1 最后页 [ 显示模式: 摘要 | 列表 ]