PHP数组的Hash冲突实例
上一篇文章, 我介绍了一个利用Hash冲突(碰撞)来对各种语言(包括,PHP, Java, Ruby等等)实施拒绝服务攻击的可能, 但是没有给出实例, 文章发出后, @Ferrari同学给出了一个另外一篇文章Supercolliding a PHP array, 文章中作者介绍了一种基于PHP的冲突实例, 以及带来的性能恶化对比. 我就借花献佛, 翻译给大家看看.
你知道不知道, 插入65536个经过构造的键值的元素到PHP数组, 会需要耗时30秒以上? 而一般的这个过程仅仅需要0.1秒..
请看如下的例子:
- <?php
- $size = pow(2, 16);
- $startTime = microtime(true);
- $array = array();
- for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) {
- $array[$key] = 0;
- }
- $endTime = microtime(true);
- echo '插入 ', $size, ' 个恶意的元素需要 ', $endTime - $startTime, ' 秒', "\n";
- $startTime = microtime(true);
- $array = array();
- for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) {
- $array[$key] = 0;
- }
- $endTime = microtime(true);
- echo '插入 ', $size, ' 个普通元素需要 ', $endTime - $startTime, ' 秒', "\n";
上面的例子, 在我的机器上的执行结果如下:
- 插入 65536 个恶意的元素需要 43.1438360214 秒
- 插入 65536 个普通元素需要 0.0210378170013
这个差别是不是很夸张?!
我在上一篇文章中介绍过, 经过特殊构造的键值, 使得PHP每一次插入都会造成Hash冲突, 从而使得PHP中array的底层Hash表退化成链表:
这样在每次插入的时候PHP都需要遍历一遍这个链表, 大家可以想象, 第一次插入, 需要遍历0个元素, 第二次是1个, 第三次是3个, 第65536个是65535个, 那么总共就需要65534*65535/2=2147385345次遍历….
那么, 这个键值是怎么构造的呢?
在PHP中,如果键值是数字, 那么Hash的时候就是数字本身, 一般的时候都是, index & tableMask. 而tableMask是用来保证数字索引不会超出数组可容纳的元素个数值, 也就是数组个数-1.
PHP的Hashtable的大小都是2的指数, 比如如果你存入10个元素的数组, 那么数组实际大小是16, 如果存入20个, 则实际大小为32, 而63个话, 实际大小为64. 当你的存入的元素个数大于了数组目前的最多元素个数的时候, PHP会对这个数组进行扩容, 并且从新Hash.
现在, 我们假设要存入64个元素(中间可能会经过扩容, 但是我们只需要知道, 最后的数组大小是64, 并且对应的tableMask为63:0111111), 那么如果第一次我们存入的元素的键值为0, 则hash后的值为0, 第二次我们存入64, hash(1000000 & 0111111)的值也为0, 第三次我们用128, 第四次用192… 就可以使得底层的PHP数组把所有的元素都Hash到0号bucket上, 从而使得Hash表退化成链表了.
当然, 如果键值是字符串的话, 就稍微比较麻烦一些了, 但是PHP的Hash算法是开源的, 已知的, 所以有心人也可以做到…
建议继续学习:
- HashMap解决hash冲突的方法 (阅读:11227)
- 关于memcache分布式一致性hash (阅读:10686)
- MinHash原理与应用 (阅读:5840)
- LVS hash size解决4096个并发的问题 (阅读:5418)
- 无锁HashMap的原理与实现 (阅读:5325)
- 如果用户在5分钟内重复上线,就给他发警告,问如何设计? (阅读:4863)
- Ubuntu 下Hash校验和不符问题的解决 (阅读:4468)
- 分布式系统hash策略 (阅读:3744)
- redis源代码分析 - hash table (阅读:3531)
- 一致性hash算法 (阅读:3393)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:雪候鸟 来源: 风雪之隅
- 标签: Hash
- 发布时间:2012-01-03 23:39:11
- [68] 如何拿下简短的域名
- [68] Go Reflect 性能
- [64] Oracle MTS模式下 进程地址与会话信
- [61] 图书馆的世界纪录
- [60] 【社会化设计】自我(self)部分――欢迎区
- [60] IOS安全–浅谈关于IOS加固的几种方法
- [58] android 开发入门
- [53] 视觉调整-设计师 vs. 逻辑
- [48] 读书笔记-壹百度:百度十年千倍的29条法则
- [47] 界面设计速成