标签 C 下的文章

字符串拷贝密码

在近期的一次工作交接中,在我的代码中发现了很多’安全隐患’,主要是以’字符串拷贝’为主。这种安全漏洞在C编程中是较为常见的,防范起来也较为容易,这里我们就来一起探索一下’字符串拷贝’的’密码’。

在正常情况下,我们在考量目的缓冲区大小时都会以源缓冲区大小作为依据的,一般会适当的比源缓冲区多出一些空间,其中一种’居中’状况:即sizeof(dstbuf) = strlen(srcbuf) + 1。

当sizeof(dstbuf) > strlen(srcbuf) + 1时,使用strcpy, strncpy都不会出现问题(缓冲区溢出问题);
[Ex1.]
int main() {
        /*
         * 测试char *strcpy(char *s1, const char *s2);
         */
        char    dstbuf1[10];
        char    *srcbuf1 = "Hello";

        memset(dstbuf1, 0, sizeof(dstbuf1));
        strcpy(dstbuf1, srcbuf1);

        printf("%s\n", dstbuf1);        /* 输出结果:Hello */

        /*
         * 测试char *strncpy(char *s1, const char *s2, size_t n);
         */
        char    dstbuf2[10];
        char    *srcbuf2 = "Hello";

        memset(dstbuf2, 0, sizeof(dstbuf2));
        strncpy(dstbuf2, srcbuf2, sizeof(dstbuf2)-1);

        printf("%s\n", dstbuf2);        /* 输出结果:Hello */
}

当sizeof(dstbuf) < strlen(srcbuf) + 1时,当然这种情况就是异常情况,是否能很好的处理这样的异常情况恰恰体现了你的程序的健壮性好坏。我们分别讨论一下使用strcpy、strncpy和strlcpy在这种情况下出现的问题:

(1) 使用strcpy
使用strcpy会出现什么问题呢?strcpy会将srcbuf中的所有字符(直到并包括结尾0)拷贝到dstbuf中,即使sizeof(dstbuf)不够大。这样会导致dstbuf缓冲区溢出,看下面例子:

[Ex2.]
int main() {
        /*
         * 测试char *strcpy(char *s1, const char *s2);
         */
        char    dstbuf1[6];
        char    *srcbuf1 = "HelloWorld";

        memset(dstbuf1, 0, sizeof(dstbuf1));
        strcpy(dstbuf1, srcbuf1);

        printf("%s\n", dstbuf1);        /* 缓冲区溢出,输出结果:HelloWorld */
}
strcpy将’HelloWorld’拷贝到了dstbuf中,由于strcpy不检查目的缓冲区大小,所以即使目的缓冲区dstbuf大小不够,strcpy也继续拷贝,直至碰到源缓冲区的结尾0,strcpy同样不会放过源缓冲区的结尾0,该结尾0也被拷贝到目的缓冲区中,这样我们在输出dstbuf时,printf将结尾0之前的字符悉数打印出来。

(2) 使用strncpy
使用strncpy会出现什么问题呢?如果你这样使用(一般都应该这样用)strncpy(dstbuf, srcbuf, sizeof(dstbuf) – 1),则不会出现问题,最后的sizeof(dstbuf)-1就是为了在dstbuf的结尾留出’结尾0′的空间。但是如果你这样用:strncpy(dstbuf, srcbuf, n), n > sizeof(dstbuf) – 1, 则由于目前srcbuf中的数量已经大于dstbuf的长度,一旦n也大于sizeof(dstbuf)-1,那么dstbuf的最终结果就是其没有结尾0,你printf(dstbuf)会得到结尾为乱码的字符串。看下面例子:
[Ex3.]
int main() {
        /*
         * 测试char *strncpy(char *s1, const char *s2, size_t n);
         */
        char    dstbuf2[6];
        char    *srcbuf2 = "HelloWorld";

        memset(dstbuf2, 0, sizeof(dstbuf2));
        strncpy(dstbuf2, srcbuf2, sizeof(dstbuf2));

        printf("%s\n", dstbuf2);        /* dstbuf2的结尾0被覆盖,输出结果:HelloW鯰 */
}

(3) 使用strlcpy
strlcpy会出现什么情况呢?首先strlcpy并不是标准C库函数,不过在大部分Unix/Linux平台下都提供这个接口,它会在适当的时候截断srcbuf并保证dstbuf最后结尾0不被覆盖,保证缓冲区不溢出,也就是说使用strlcpy是安全的,但是并不一定是你期望的结果。

[Ex4.]
int main() {
        /*
         * 测试size_t strlcpy(char *dst, const char *src, size_t dstsize);
         */
        char    dstbuf3[6];
        char    *srcbuf3 = "HelloWorld";

        memset(dstbuf3, 0, sizeof(dstbuf3));
        strncpy(dstbuf3, srcbuf3, sizeof(dstbuf3));
 
       /*
        * strlcpy截断srcbuf, 将srcbuf的前sizeof(dstbuf3)-1个字符拷贝到dstbuf3中,
        * 并在dstbuf3的结尾处添加结尾0,输出结果:Hello
        */
        printf("%s\n", dstbuf3);       
}

通过上面的几个例子的讲解,相信你已经能够找到’字符串拷贝’的’密码’了,拥有这一密码你的程序将会变得更加健壮。^_^

解决算法分析中递归问题的方法

当一个算法(如二分查找)中包含对自己的递归调用时,关于这个算法时间复杂性的分析最终都转化为一个递归方程的求解问题,而这样的算法不在少数。实际上这是数学领域的问题,但是计算机科学又怎么能脱离数学而存在呢?^_^ 数学是好东西呀,可惜自己在这方面造诣颇浅,今生之遗憾亚。^_^

还好,解决递归方程涉及的数学知识我还是能应付的了的^_^。在MIT算法导论中介绍了3种方法,我们这里就说说这三种方法!这些是基础,如果以后要深入研究算法的话,这些知识是必须要精通的;如果并不想在算法方面有所深入的话,多学些知识也没错。我本身也是在学习,像这类的知识一般都比较死性,有些记住了,就可以掌握了。

1、Substitution Method
这是一种使用数学归纳法推导证明的方法,其步骤为先假设一个解,然后带入到递归方程中,利用数学归纳法推导,以验证假设的解是否合理。我们拿ITA(Introduction to Algorithm)中的例子说明吧,比较保险^_^。
[Ex1.]
T(n) = 4T(n/2) + n,解这个递归等式,分析T(n)的渐近性。

解:(这里我们只来找上界)
我们假设T(1) = θ(1),猜测一个解T(n) = O(n^3),根据O符号的定义,我们得到对k < n, 有T(k) <= ck^3,把这个解代入到T(n) = 4T(n/2) + n,并进行推导得出:
T(n) = 4T(n/2) + n
     <= 4c((n/2)^3) + n
     = (c/2)n^3 + n
     = cn^3 – ((c/2)n^3 – n)
当c >= 2, n >= 1时,((c/2)n^3 – n) >= 0,这时T(n) <= cn^3,即T(n) = O(n^3);

我们再回过头来看看当n = 1时这个解是否成立,即证明一下T(1) = θ(1)。对于1 <= n < n0, θ(1) <= cn^3 (c足够大),即该推导出的解也满足初始条件,所以O(n^3)是T(n)的一个上界。但是O(n^3)是否是严紧的上界呢,我们不妨缩小上界范围再推导一次,这次我们猜测解为T(n) = O(n^2),根据O符号的定义,我们得到对k < n, 有T(k) <= ck^2,把这个解代入到T(n) = 4T(n/2) + n,并进行推导得出:
T(n) = 4T(n/2) + n
     <= 4c((n/2)^2) + n
     = cn^2 + n
     = cn^2 – (-n)
不能严格符合T(n) <= cn^2的定义,所以推导失败。但是失败是不是说明,T(n) = O(n^2)一定不成立呢?我们再做一次最后的努力,当出现上面的这种情况时,我们假设解仍为:T(n) = O(n^2),只是我们选择对k < n, 有T(k) <= ak^2 – bk,我们选择减去一个低阶的项,这不会影响到n足够大时的渐进性的,这里是一个常用的技巧。
T(n) = 4T(n/2) + n
     <= 4(a(n/2)^2 – b(n/2)) + n
     = an^2 – bn – (bn – n)
     <= an^2 – bn (当b >= 1时)

这样我们找到了严紧解T(n) = O(n^2)。

2、Iteration method(Recursion-tree method)
这个方法的思想是:"迭代地展开递归方程的右端,使之成为一个非递归的和式,然后通过对和式的估计来达到对方程左端即方程的解的估计"。而我们可以借助’树’的形式来帮助迭代展开的过程。

[Ex2.]
T(n) = T(n/4) + T(n/2)+ n^2;解这个递归等式,分析T(n)的渐近性。

解:
T(n) = n^2 + T(n/4) + T(n/2)
     = n^2 + {(n/4)^2 + T(n/16) + T(n/8)} + {(n/2)^2 + T(n/8) + T(n/4)}
     = …
     = n^2 {1 + 5/16 + (5/16)^2 + (5/16)^3 + … }
     = θ(n^2)

3、Master Method
这是一种典型的套用公式的方法,解决形如’T(n) = aT(n/b) + f(n)’递归方程形的解的方法。这种递归方程是一类分治法的时间复杂性所满足的递归关系,即一个规模为n的问题被分成规模均为n/b的a个子间题,递归地求解这a个子问题,然后通过对这a个子间题的解的综合,得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性,用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间,我们便有方程’T(n) = aT(n/b) + f(n)’。

在f(n)的三类情况下,我们有T(n)的渐近估计式有三类情况:(log(b, a)表示以b为底的对数)
(1) 若对于某常数ε>0,有f(n) = O(n^log(b, a-ε)),即f(n)以慢于n^(log(b, a))的速率渐进增长,则T(n) = θ(n^(log(b, a));

(2) 若有f(n) = θ(n^log(b, a) * (lgn)^k),即f(n)以相似于n^(log(b, a))增长的速率渐进增长,则T(n) = θ(n^(log(b, a) * (lgn)^(k+1)),k为一常数,k >= 0;

(3) 若对于某常数ε>0,有f(n) = Ω(n^log(b, a+ε)),即f(n)以快于n^(log(b, a))的速率渐进增长,且对于某常数c > 1和所有充分大的正整数n有af(n/b) <= cf(n),则T(n) = θ(f(n))。

举例来说吧:

[Ex3.]
T(n) = 4T(n/2) + n,解这个递归等式,分析T(n)的渐近性。

解:对T(n) = 4T(n/2) + n我们得到a = 4, b = 2, f(n) = n, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2,而f(n) = n = O(n^(2-ε)),此时ε= 1,根据Case (1),我们得到T(n) = θ(n^2)。

[Ex4.]
T(n) = 4T(n/2) + n^2,解这个递归等式,分析T(n)的渐近性。

解:对T(n) = 4T(n/2) + n^2,我们得到a = 4, b = 2, f(n) = n^2, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2, f(n) = n^2 = θ(n^2 * (lgn)^0),即k = 0,这样按照Case (2),我们得到T(n) = θ(n^2 * (lgn)^(k+1)) = θ(n^2 * (lgn))。

[Ex5.]
T(n) = 4T(n/2) + n^3,解这个递归等式,分析T(n)的渐近性。

解:对T(n) = 4T(n/2) + n^3,我们得到a = 4, b = 2, f(n) = n^3, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2, f(n) = n^3 = Ω(n^(2+ε),此时ε= 1,且4f(n/2) = (n^3)/2 <= cn^3(c >= 1/2),所以得到T(n) = θ(n^3)。

对于大部分人来说’Master Method’应该是最常用的,这几个Case可要牢牢记在心上才行哟。

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 Go语言编程指南
商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats