bug描述: http://www.laruence.com/2011/12/29/2412.html
相关资料: http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html
就像上面资料中提到的,构造hash冲突是利用了PHP Hashtable对数值key的简单处理实现的。如果用字符串key来构造hash冲突,似乎就比较麻烦了; 严格地将,这个和PHP中的hash算法没有必然联系,对于字符串key是通过hash函数计算出一个无符号整型数然后和Hashtable的size取模的,而对于数字key是直接使用该数字与Hashtable的size取模的。
有些同学通过限制post数据的大小来从一定程度上环节带来的危害,限制post数据大小为不超过100k,下面来分析一下这个数字是否够用:
脚本1:
- <?php
- $size = pow(2, 15); // 可以通过第二个参数来改变提交的数据量的大小
- $data = ”;
- for ($key=0, $maxkey=($size-1) * $size; $key<= $maxkey; $key+=$size) {
- $data .= $key.‘=&’;
- $i++;
- }
- echo "key num: $i \n";
- echo "data length:". strlen($data);
通过这个脚本来得出key的多少和对应的数据量。
脚本2:
- <?php
- $size = pow(2, 15); // 16 is just an example, could also be 15 or 17
- $startTime = microtime(true);
- $array = array();
- for ($key = 0, $maxKey = ($size – 1) * $size; $key <= $maxKey; $key += $size) {
- $array[$key] = 0;
- }
- $endTime = microtime(true);
- echo ‘Inserting ‘, $size, ‘ evil elements took ‘, $endTime – $startTime, ‘ seconds’, "\n";
- $startTime = microtime(true);
- $array = array();
- for ($key = 0, $maxKey = $size – 1; $key <= $maxKey; ++$key) {
- $array[$key] = 0;
- }
- $endTime = microtime(true);
- echo ‘Inserting ‘, $size, ‘ good elements took ‘, $endTime – $startTime, ‘ seconds’, "\n";
通过这个脚本可以得出key的多少和相应消耗的时间。
80k的数据就可以构造8000 个key,耗费cpu时间大约不到2s;
360k的数据可以构造3.2万个key,耗费cpu时间大约30多s;
看来限制 100k 的数据还是非常有效的。
关于该bug的修复,官方给出了补丁,允许限制post数据的个数; 那么GET数据和Cookie数据会不会有这个问题呢?答案是不会的,我们可以从apache的源码中找到答案:
关于PHP Hashtable的更多参考资料:
http://www.qingliangcn.com/2009/07/php%E6%BA%90%E4%BB%A3%E7%A0%81%E5%88%86%E6%9E%90%E4%B9%8Bhashtable/
http://www.phpchina.com/index.php?action-viewthread-tid-88505
———————
关于PHP Hashtable的几点提示:
1. Hashtable的最小大小为8 ,如果元素个数为9,则大小重新调整为16,每次调整都要遍历所有元素,重新计算hash值
2. 数值key不做hash,直接和Hashtable 的size取模
3. nNextFreeElement 用于数字索引的计数,其值为当前数字索引值加1,初始值为0
4. pNext, pLast 是hash冲突时的冲突链表的双向指针
5. PListNext, pListLast 是用于遍历数组的双向链表指针
6. pInternalPointer 是用于遍历数组的一个位置指针