Bug是你的,也是他们的,但归根到底是你的!

某天,我发现我的一个程序的一个字符串匹配模块有些问题,该模块用的是经典的AC模式匹配算法在snort中的实现。但问题是我发现有些它匹配出来的字符串显然并不符合匹配条件……

于是开始debug,经过一轮艰苦地调试,发现只要字符串以r或者s结尾就会被匹配,这也太奇怪了,用gdb跟踪打印出现场之后,发现在程序找到匹配状态的时候,表示匹配目标串的位置的index居然是个负值,打开源码一看,计算index的代码如下:

其中T代表当前指针位置,Tx是字符串头指针,而n则是匹配上的特征子串长度。

于是我小小地鄙视了一下snort的acsmSearch实现,一个应用得如此广泛的函数,居然都没有一个安全检查。

于是加了一个对index值的判断,程序果然运行正常了。本以为问题就这样解决了,但是在回头看了一眼AC模式匹配算法的论文之后,才发现情况有些不合逻辑,如果index为负,则说明算法在运行了还不到特征子串长度的匹配之后就找到匹配了,这怎么可能呢?

于是再回头去找,才发现原来这个程序在两次调用的acsmSearch2的时候传入了同一个表示初始状态的变量,而且没有清空!acsmSearch2函数的原型如下:

最后一个data实际上是一个int指针,表示的是自动机的初始状态。

而我的这个程序两次调用使用的不是同一个自动机,所以导致上一次调用的最后状态(而不是初始状态0)被作为第二调用的初始状态传入了函数,而第一个状态机中的非匹配状态在第二个状态机中就刚好匹配上了一个有输出值的状态。

所以说,这个bug的根源最终在与我使用了一个有状态的变量,而且没有在多次调用之前清空它,导致了语义上的错误。

这个错误如此隐秘,以至于一开始我都怪到开源代码头上了,辛苦了这半天,有了如下总结:

本文网址:http://blog.perlfect.me/2011/01/7/all-bugs-are-your-bugs.html

comments powered by Disqus