免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
1234下一页
最近访问板块 发新帖
查看: 8614 | 回复: 36

URL过滤 内核空间还是用户空间 [复制链接]

论坛徽章:
0
发表于 2009-12-16 16:34 |显示全部楼层
我目前想做一个URL过滤功能,URL黑名单和白名单存放在mysql数据库中。内核抓包,提取出URL,有两个想法:
1. 内核态抓包,提取出URL,用户态系统调用出URL,在数据库中匹配,然后在传递给内核(系统调用)采取措施,阻止or放行。
   考虑缺陷:时间消耗大
2. 把数据库中的URL放到内核态,用链表存储,比如一个黑名单链表,一个白名单链表。内核抓到包后,不用系统调用,直接比较链表中的URL
优点:没有系统调用,时间快
缺点:不知道空间够不够。

希望大家给说说哪个好。或者有什么其他可行的做法。

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-12-16 16:44 |显示全部楼层
在用户空间匹配的效率应该是个问题。

个人觉得还是在内核态去做。至于空间问题,看你的系统有多大空间,URL有多少了

论坛徽章:
0
发表于 2009-12-16 17:00 |显示全部楼层
在内核建立基于 string 的 hash
用另一种 hash 算法当作 data,防止冲突时验证
这样我觉得既可以解决效率问题,又可以解决空间问题
就是不知道你的 URL 库有多少

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-12-16 17:11 |显示全部楼层
在内核建立基于 string 的 hash
用另一种 hash 算法当作 data,防止冲突时验证

白金兄能稍微详细的介绍一下这种实现方式吗?

论坛徽章:
0
发表于 2009-12-16 19:09 |显示全部楼层
类似这样来实现,可以做到空间、效率、准确度之间的平衡

伪代码如下

  1. #define BUCKETS 65536

  2. __u16 key = hash1(url);
  3. __u32 value = hash2(url);

  4. if (url_hash[key].value == value)
  5.     printk ("matched!\n");
复制代码

很多人都用 md5 去做验证值,这样有几个弊端
1、验证值占用空间很大
2、md5 的计算占用 CPU 较多

但是,如果用 32bit 的 hash2 替代 md5,也有它的弊端:
由于 bit 数很少,不同 url、相同 key 且相同 value 的可能性,比不同 url、相同 key 且相同 md5 的可性能大的多

仔细分析,这种弊端可否忽略呢?
就用 LZ 的需求来说,一个 white list,一个 black list
如果产生了 “合法的冲突”,也就是 URL 不同但所有的一切都一样,match 了

当然,为了减少这种冲突,我们还可以用 value1、value2 的方式做多次验证,这可能也会比 md5 快(没具体测试过)

当 URL 不同、KEY 相同、VALUE 也相同的可能性太少了
况且,只会误,不会漏,无论是 white list 还是 black list 里面的东西,一个都漏不掉,对于误的,几率太低了

做了一个实验,用 rnd() 来生成随机正整数,插入 100000 个元素,冲突率 0.004%,单链最大深度 20

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-12-16 19:50 |显示全部楼层
hash算法都需要自己实现吗?

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-12-16 19:54 |显示全部楼层
一个用URL生成key的hash算法,一个用URL生成23bit数据的算法。
只要key相同的URL,其32bit数据相同的概率足够低即可。

论坛徽章:
0
发表于 2009-12-16 21:14 |显示全部楼层
关于URL,可以采用Bloom Filter来做... 一般spider就是用的这个...
不过我好奇内核中怎么取出URL....希望大家给个思路...   skb太庞大了

论坛徽章:
0
发表于 2009-12-16 21:30 |显示全部楼层
原帖由 Godbach 于 2009-12-16 19:50 发表
hash算法都需要自己实现吗?

网上用 “hash mask” 做关键字,可以找到 string 的 hash 算法,n 多种

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-12-16 21:47 |显示全部楼层
做了一个实验,用 rnd() 来生成随机正整数,插入 100000 个元素,冲突率 0.004%,单链最大深度 20

白金兄,如果有千万数量级的URL,是不是冲突率会更大啊
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP