BDB 和 TCHDB / TCBDB 可能大家玩厌了.
Tokyo (Cabinet|Tyrant) pluggable abstract api 挺好玩的. 这个早就在 mixi Engineers’ Blog 上写过, 不提.
可是如果把 TC / TT 和下面这个东西接在一起…

—

2009 年以索引技术创业的 TokuTek 发布了 TokuDB for MySQL, 看性能参数是挺不错的.
当时就对它产生了极大的兴趣. 但非常不幸偶没有理解它的索引原理 (Tokutek 也不说). 再加上它不是很成熟, 没有 ACID, 多核支持也不好, 所以暂时搁置了.

推荐大家都看看这个幻灯片 How Fractal Trees Work
还有个讲课视频, 这个就不给出了, youtube 上有.

设有 n 个数据吧.
基本意思是有 log2(n) 个索引块, 块的大小分别是 1, 2, 4… 直到 2^k, 其和大于 n (要不就存不下了 ). 每个块只有空和填满两种状态.
插入时如果碰到块满的情况就把两个小块合并为更大的块.
因为较小的块可以在内存中合并 (反正内存中怎么折腾都不会慢的), 对较大的块来说在旋转存储器上的归并速度也是很快的, 这就是 TokuDB 高速最直接的原因. 压缩是另一个加分的因素.

查询的问题幻灯片讲的比较清楚, 优化上也不难, 这里就不再写第二遍了.

看来最大的问题就是, 两个块合成新块时, 如果两个块都很大就比较麻烦了. 这也是 Page 23-25 提到的问题.

关于删除的问题幻灯片没有说. 不过考虑到它作为数据仓库的用途, 这一点可以暂时原谅. 删除也可以用对数据加 flag 的方法解决. 好像更新也不是简单的事情.
看起来整个用 BigTable 的方法也行, 只是不知道现在 Google 改造存储系统的情况如何. kumofs 的作者说 kumofs 是第二代分布式存储系统(彻底没有单点问题), 这个情况有感兴趣的自己去研究吧.

Page 28, 变长的数据是容易处理的. 搜索的复杂度降到 O(logB(N)), 存储的只要是块的位置(或编号)就可以了(注). 事务(包括灾难恢复)和并行化可能是难度最大的部分.

注: 细节看这个 http://tokutek.com/presentations/bender-Scalperf-9-09.pdf

说到对存储到硬盘上的数据进行整理, 就不得不提到 Reiser4 引入的 Dancing Tree.
写入之前对 Block 做整理的操作, 这是对 B-Tree 的一个比较有效的优化, 只是可惜了…

Cache-Oblivious Search Trees 是 Fractal Trees 出现之前的成果. 一年前偶就顺着网页看到了它, 可是偶不明白具体原理. hmm…

—

TokuDB 还有 covering index (试译: 覆盖索引) 的支持. 覆盖索引要求所有要查询的列都在索引之中.
http://tokutek.com/presentations/kuszmaul-mysqluc-percona-09-slides.pdf
如果有 (a, b, c) 的覆盖索引, 则查询 select b, c where a = xx 这类是很快的.
(覆盖索引和多维排序索引有什么区别? 如果后者不能完成这个任务, 那是 MySQL 的错, 这绝对不是 TokuDB 的首创)

但偶不明白二维索引的实现方式. Page 15 有 38<=a and a<=42 and 90<=b and b<=99, 谁能解释一下应该怎么做?
当然, 偶知道有其它的解法, 二维线段树偶知道, GeoHash 这种方法也可以考虑, 但前提都要预先知道取值范围. 如果 Page 15 的问题是用这种索引解决的, 那可真要仔细看看了. 暂时继续抱怀疑态度.

当然说到这个幻灯片, Page 14 的均摊分析把偶吓了一下.
B-Tree 的 Point Query 的复杂度是 O(logN/logB), 实际上就等于 O(logB(N)), 你是不是忘了换底公式了?
不知道这是否是故意的, 给偶一个错觉, 幸好偶的数学还不是非常差劲. 这种模糊手法要明确指出来, 不能再吓着别人.
关于 Insert 的复杂度, B-Tree 的优化是允许多个块写到一起(包括内存上的优化). 但随机的场合性能不佳是自然的.
Fractal Tree 索引的效率和内存的关系并不大, 但实现上看起来挺吃 CPU 的.
仔细想来, Fractal Tree Index 大批量的插入均摊复杂度确实是 O(logN / B).

—

Tokutek 的收费政策是生产环境未压缩纯数据(不算索引) 50 GB 以下不收费,
包括所有的副本(也就是说 Replication 的话就要算多次了), 当然也没有技术支持.

超过部分每 100 GB / 年收费 $1000 (换算一下是 $0.83 / GB * Month ).
Tokutek 认为单台机器能承担 5 TB 的数据, 这个数字偶是要怀疑的. 而且偶不愿意承担单点的风险.
显然可以谈个优惠价出来, 实际上偶愿意接受的价格不超过 $0.05 / GB * Month.
这个收费比 GAE DataStore 和 Amazon SimpleDB 都贵太多了, 实在不合算. 有人还在想 Oracle 怎样怎样…

换一个角度说, 如果你用 NoSQL 存数据, 用它当索引(注意别涉及删除问题), 偶想肯定不会超过 50 GB 的 这个引擎存文本虽然没问题, 可是偶肯定不会这样推荐的.

—

TokuDB 的下载页面提供了 Fractal Tree Library 的下载, 只有 x86_64 的版本.
(需要注册, 随便填填就过了, 需要验证 E-Mail, 没有审核)
解压出来有一个大号的 .so 文件, include 目录下有 tokudb.h. 实现还算是比较完整. 提供了测试的程序, 但有说要是作为嵌入式数据库的话需要获得许可.

Fractal Tree Library 可以当 BDB 用, 也可以当 TCBDB 用.
于是乎, 就有了文章最开始的那一幕.

—

ps:
最近发现偶 blog 上文章的题目和实际内容是两回事, 还是改一改吧.

ps2:
因为某保护条例第十七条的规定, 所以允许某人盗版 XP 而不支付报酬, 这对吗?
(话说要是没有 Google Translate 的话, 就可以换一种更明确的表达方式了)

ps3:
有人说 Oracle 应该买下 Tokutek. 或者别的什么公司也可以买它. 你觉得呢?

ps4:
Tokutek 说未来的数据库都要以它为索引, 偶承认这是项不错的技术, 不过这是不是技术幻想?

ps5:
大网站的技术团队都那么强, 为什么这篇文章的作者是偶呢? 偶期待着有人用和偶一样少的资源写出一样好的东西. 偶的 reco 都停了有一年了, 等着大家来追偶.
当然如果你觉得偶写的不好的话可以扔邮件到偶这里来.

ps6:
文章加粗的地方都有用, 相信偶.

Python SDK:
sed --in-place -e 's/socket.AF_INET/socket.AF_INET6/' google_appengine/google/appengine/tools/https_wrapper.py

(Rollback, In order to use IPv4 again.)
sed --in-place -e 's/socket.AF_INET6/socket.AF_INET/' google_appengine/google/appengine/tools/https_wrapper.py

Host: (IPv6 addresses end in “8a” will work, on which ssl certs for “appengine.google.com” are deployed)
2404:6800:8005::8a appengine.google.com

I know nothing about Google App Engine Java SDK.

—
Alternate method:
set “127.0.0.1 appengine.google.com” & use a port forwarder? Not tested.

条条大路通 IPv6.
原生 IPv6, 6to4, ISATAP, Teredo, (SSH, VPN), (sixxs) …

注1: Tunnel Broker 属于 6to4, Gateway6 / gogo6 支持 6to4, 4to6, 一般还是用 6to4.
注2: ISATAP 需要使用 IP Protocol 41 类型的数据包. 这种类型的数据包可能无法穿透路由器.
注3: sixxs 只是一个服务, 玩玩可以, 可用性很差…
注4: 某些服务故意漏掉了.

不推荐使用 Windows XP 上原生 IPv6, WinXP 对 IPv6 支持不够完善. 虽然说凑合用是可以的. 至少设置 ipv6 dns 挺麻烦, 只有命令行可以用, 这里不写了.

推荐使用 Gateway6 上 IPv6 (不幸的是大陆的服务商基本没人搞这个), 用 ISATAP 可能会更快, 但 ISATAP 与 Teredo 都会泄漏你的 IPv4 地址.
(提取 ipv4 地址的工具: ipv6calc, 各发行版安装 ipv6calc 即可)

Teredo 玩玩是可以的, 但速度实在不敢恭维 (ipv6.google.com 确实很快, 说明 Google 网络部署上很厉害).

使用 Teredo 上 IPv6 的机器, 与另一台双栈机器连接时传输速度较快. (因为双机实际在用 IPv4 连接传输). 和纯 IPv6 机器时需要经过中转, 这个速度比较慢.
Gateway6 这种连接方式数据全部需要服务器中转(例外: 与 Teredo 双栈机通信有一部分走 IPv4), 但挑一个快速的服务器就全补回来了.

Gateway6: Ubuntu 下安装 gw6c (Debian 装 gogoc), 配置好 Tunnel Broker Server 即可.
服务器填 tb.ipv6.apol.com.tw 就不错. 当然还有别的, 可以搜搜看.
Teredo: 安装 miredo 启动即可. ping ipv6.google.com 即可测试.

WinXP SP1+ 补: ipv6 install; netsh interface ipv6 set teredo client

—

和开源相关的东西多数都有 IPv6 镜像, 但非常不幸, kernel.org 没有.
想要 Tarball 的话可以到 Gentoo Mirrors 上翻一翻, 当然要先学会看 ebuild.
对 Ubuntu 来说, mirror.switch.ch 速度挺不错.

随便哪个主流发行版, 这个找一找就会有的.

—

IPv6 资源并不丰富, 但 Hurricane Electric(HE) 和 Google IPv6 部署的还不错. 于是用之.

HE DNS: 2001:470:20::2 / 74.82.42.42
如果还想要其它 DNS 服务器可以看这个:
http://www.chaz6.com/files/resolv.conf

个人 Ping(6) 值最小的 IP(v6) 段:
Google 2404:6800:8005
Youtube 2404:6800:4001

偶推测的 Google IPv6 的大概情况是这样的.
1 ipv6.google.com 可以作为 HTTP 代理间接访问其它 Google 服务. (Youtube 可能要除外)
2 IPv6 地址的尾数有特殊意义(这和 IPv4 的情况是一样的). 尾数和 SSL 证书部署有紧密的联系. 遍历一遍就可以得到一个大概结果.
3 IP(v6) 前缀代表不同数据中心(都知道), 只要部署状况允许就可以随意切换.

以下是 2001:4860:8001 段的 SSL 证书扫描结果.

mail.google.com 2404:6800:8001::11
mail.google.com 2404:6800:8001::12
mail.google.com 2404:6800:8001::13
*.recaptcha.net 2404:6800:8001::18
*.google.com.tr 2404:6800:8001::20
*.google.com.au 2404:6800:8001::21
*.google.com.vn 2404:6800:8001::22
*.google.com.pk 2404:6800:8001::23
*.google.com.my 2404:6800:8001::24
*.google.com.pe 2404:6800:8001::25
*.google.co.za 2404:6800:8001::26
*.google.co.ve 2404:6800:8001::27
*.google.com.ph 2404:6800:8001::28
*.google.com.ar 2404:6800:8001::29
*.google.co.nz 2404:6800:8001::2a
*.google.lt 2404:6800:8001::2b
*.google.cn 2404:6800:8001::2c
*.google.com.sg 2404:6800:8001::2d
*.google.com.hk 2404:6800:8001::2e
*.google.com.tw 2404:6800:8001::2f
*.google.co.jp 2404:6800:8001::30
*.google.ae 2404:6800:8001::31
*.google.co.uk 2404:6800:8001::32
*.google.com.gr 2404:6800:8001::33
*.google.de 2404:6800:8001::34
*.google.co.il 2404:6800:8001::35
*.google.fr 2404:6800:8001::36
*.google.it 2404:6800:8001::38
*.google.lv 2404:6800:8001::39
*.google.ca 2404:6800:8001::3a
*.google.pl 2404:6800:8001::3b
*.google.ch 2404:6800:8001::3c
*.google.ro 2404:6800:8001::3d
*.google.nl 2404:6800:8001::3e
*.google.com.ru 2404:6800:8001::3f
*.google.at 2404:6800:8001::40
adwords.google.sk 2404:6800:8001::41
*.google.be 2404:6800:8001::42
*.google.co.kr 2404:6800:8001::44
*.google.com.ua 2404:6800:8001::45
*.google.fi 2404:6800:8001::48
*.google.co.in 2404:6800:8001::49
*.google.pt 2404:6800:8001::4a
*.google.com.ly 2404:6800:8001::4b
*.google.com.mx 2404:6800:8001::4d
*.google.es 2404:6800:8001::4e
*.google.dk 2404:6800:8001::4f
sandbox.google.com 2404:6800:8001::51
*.googlecode.com 2404:6800:8001::52
mail.google.com 2404:6800:8001::53
accounts.google.com 2404:6800:8001::54
*.google.com 2404:6800:8001::5b
*.google.com 2404:6800:8001::5d
*.googleapis.com 2404:6800:8001::5f
www.googleadservices.com 2404:6800:8001::60
*.google-analytics.com 2404:6800:8001::61
*.google.com 2404:6800:8001::62
www.google.com 2404:6800:8001::63
*.google.com 2404:6800:8001::64
*.google.com 2404:6800:8001::65
*.google.com 2404:6800:8001::66
www.google.com 2404:6800:8001::67
www.google.com 2404:6800:8001::68
www.google.com 2404:6800:8001::69
www.google.com 2404:6800:8001::6a
adwords.google.com 2404:6800:8001::70
*.google.com 2404:6800:8001::71
checkout.google.com 2404:6800:8001::73
upload.video.google.com 2404:6800:8001::74
*.google.com 2404:6800:8001::76
ssl.gstatic.com 2404:6800:8001::78
wifi.google.com 2404:6800:8001::7b
*.googleusercontent.com 2404:6800:8001::84
*.google.com 2404:6800:8001::88
*.googlegroups.com 2404:6800:8001::89
*.google.com 2404:6800:8001::8a
*.google.com 2404:6800:8001::8b
*.appspot.com 2404:6800:8001::8d
*.au.doubleclick.net 2404:6800:8001::8e
*.uk.doubleclick.net 2404:6800:8001::90
*.fr.doubleclick.net 2404:6800:8001::91
*.jp.doubleclick.net 2404:6800:8001::92
www.google.com 2404:6800:8001::93
*.doubleclick.net 2404:6800:8001::94
*.doubleclick.net 2404:6800:8001::95
tpc.googlesyndication.com 2404:6800:8001::98
*.g.doubleclick.net 2404:6800:8001::9a
*.g.doubleclick.net 2404:6800:8001::9b
*.g.doubleclick.net 2404:6800:8001::9c
*.g.doubleclick.net 2404:6800:8001::9d
*.googleadservices.com 2404:6800:8001::a4
*.googleadservices.com 2404:6800:8001::a5
*.googleadservices.com 2404:6800:8001::a6
*.googleadservices.com 2404:6800:8001::a7
service.urchin.com 2404:6800:8001::b8
*.mail.google.com 2404:6800:8001::bd
*.google.com 2404:6800:8001::be
*.blogger.com 2404:6800:8001::bf
m.google.com 2404:6800:8001::c1
jmt0.google.com 2404:6800:8001::d2

—

如何上 IPv4 网站:
1 gappproxy2
当然偶不是说 gappproxy 不行. 不喜欢当小白鼠的就用原版, 偶没意见.
可以用 ipv6.google.com:80 做代理, 但这样安全性上有一定缺陷.
在 hosts 加入 [ipv6.google.com 的 IPv6 地址] xxxx.appspot.com 并…
2 sixxs.org (好像不支持 Cookies)
3 https://dtw6 (全名不写了)
4 google.com/gwt/n (很熟悉吧, 不过这个也就是玩玩而已)
5 google 网页快照 (紧急情况专用?)
6 代理服务器 (含透明代理)
[2001:470:1f0e:456::X]:80 故意隐掉, 感谢 dtw6 的开发者.
7 VPN / SSH
这个也许是要银子的.

—

如果你有 IPv4 服务器 (内网也可以 NAT):

1 安装 gateway6 并设置 Tunnel Broker. 记录 IPv6 地址 (可能是动态的, 有些服务器提供静态 IP).
2 架设 OpenSSH Server.
3 连接到 SSH 服务器. 设置 Dynamic Port Forwarding. 完.

—

一些问题.
第一条, Hosts 文件不要改的太过分, 也就是说有选择性的找 hosts 文件并添加.
如果 DNS 工作正常的话, 除了 google (含 youtube) 相关的网站, 其他的可以基本不加. (twitter 的问题不属于本文讨论范围)

第二条, 注意 IPv4 DNS 泄露问题, 比如上面的 dtw6 访问时, 如果 ipv4 优先的话…
(注: 如果考虑到这个问题, hosts 文件里多写点倒是没错的. 平时学着用用 wireshark 或者 tcpdump 吧.)

第三条, 注意 SSL 证书问题. CNNIC ROOT / SSL 该去的还是要去.

第四条, 注意软件安全性.
Linux 下这个都好说, 包都带签名.
Win32 / 64 就麻烦多了, 什么公司都会签名, 流氓软件也签.
用 win32 的同学可以过来问一下哪些软件能用, 哪些软件不能用 (主要是网络相关的软件).
很多所谓杀毒安全软件本身就是问题的来源. 就点一个名好了, (2^3) * (3^2) * 5. 反正国内的非开源软件都躲着走吧.

—

关于双栈 Hosts 问题:

用两行指同一个域名当然是可以的. 这两行分别指向 ipv4 和 ipv6 则更好.
但如果 hosts 里面存在了某个域名, 则这个域名只能使用 hosts 文件指定的 ip.
也就是说如果对双栈网站只指定了 ipv4/v6 地址, 则只能使用对应的方式上该网站.

—

关于 Google Service SSL 问题.
wget https://IP 不加 -k 参数时会出现如下错误:
ERROR: certificate common name `*.google.com' doesn't match requested host name `xxx.xxx.xxx.xxx'.

如果这个 IP 没有被墙, 请务必记下这个 IP 及对应的 common name (即证书对应域名).
可以使用 hosts 文件将相应域名绑定到该 IP 上以实现绕墙.

Q: Changelog 看不明白, 简单说说和 GAppProxy svn r102 的区别?
A: 这个版本适合上论坛(对 POST 修正), 下文件(有较为完整的断点续传支持), 浏览网站(对图片, js, css 等文件类型开启了缓存, 相当于远程带缓存 squid). 其他问题自己去 Changelog 发掘… (这… )

Q: 只上传了 fetch.py …
A: 下载页面都说了不兼容不兼容不兼容了… 客户端由于 base64 的修正问题也要换.

Q: 缓存的效果?
A: urlfetch 的调用次数会比相同状况下的 gappproxy 少. 这会给你省下不少流量. 相当于远程的精简版 squid.

Q: 论坛附件还是下不了?
A: 目标服务器还是不支持 Range Request 吧. 这个偶也没办法. 小于 1 M (理论值 950k 多一点)的还是有问题的话请反馈.
事实上这次的修正只和提交有关系. 这些论坛的附件下载, 该能下的还能下, 该不能下的还是不能下. 可以试试二次代理, 比如 glype, phpproxy 什么的.

Q: 下了一份 2010.5.18 发布的旧版… OR 下大文件有问题…
A: 只要替换客户端 proxy.py 即可. 新版的修正不影响兼容性. 不需要再部署一次了. 但如果要帮忙测试 0.99.2 的话还是升级一下吧.

Q: gappproxy2 这个名称…
A: 实际上原来打算是用 gappproxy v1.3.0 的. 但作者不同意随意使用他的版本号, 那就分支吧.
偶相信这个更新对得起 gappproxy2 这个名字. 罗马不是一天建成的, 这个要改也不是一天的事情.

Q: gappproxy(/2) 是干啥的?
A: 不可说…

Q: 默认屏蔽 SSL 的原因?
A: 许多用户使用 www.google.cn:80 作为代理, 将 HTTPS 内容以明文形式传输, 本身就是比较危险的事情. HTTPS 证书的问题也需要自己处理, 这个和原版 Gappproxy 是一样的.
偶不愿意提供与开发应用没有关系的文件. 所以 HTTPS 问题不属于支持范围.
只要在 proxy.conf 中写上 ssl_disabled=false, 准备好两个证书文件(没有做检测), 看到 “HTTPS Enabled : YES” 即可.

Q: 怎么查看上过的网站?
A: 代码中没有内置日志记录的功能. 而且, gappproxy2 不提供管理界面. 也就是说 gappproxy2 的服务器端只有 fetch.py 一个文件.

Q: 错误信息的含义?
A: 这三个是最为常见的错误.

591: Target Server Not Available, I have tried 2 times already, Tired… huh…

目标服务器连接不上 / 太慢了. GAE 服务器都累喘气了.

591: Post Failed, I wont post twice. Try again.

这是 POST 修正的一部分. 适合论坛 / blog 等不应该多次提交场合. 刷新即可重试.

591: Over Quota Error

GAE 有两种时间配额制度, 一个是按日配额, 一个是按分钟配额. 超过任何一项都会出现 Over Quota Error (apiproxy_errors.OverQuotaError).

Q: 为什么要屏蔽非本地客户端?
A: 注意到有些人的 8000 端口被人盯上了. 偶的机器曾经也有一次被当做代理使用. 给你省点流量吧.

Q: IPv6 用户…
A: 挑一个 ping 值低的 ipv6.google.com 的 ip(v6) 地址, 用 hosts 文件指向你的 fetchserver 就好了. 推荐使用 https.

Q: 不能访问 ipv6 内容?
A: GAE urlfetch 只支持 ipv4 网站. 使用 teredo / gateway6 / isatap / ssh / vpn 等方式上 ipv6.

Q: 为什么不提供 app.yaml 样例?
A: 这个网站还没完全搬到国外去, 说话不方便. 以后会有完整的 GAE 套件.

Q: 傻瓜教程?
A: hmm… 可以考虑做个完整的 GAE 套件及方案.

Q: gappproxy 可以用 sdupload 上传…
A: gappproxy2 理论上也可以, 欢迎测试并反馈结果.

Q: http://gappproxy/status?
A: 彩蛋. 如果你只部署了 gappproxy2 的话就能看到精确的 memcache 统计数据. 需要经由 gappproxy2 代理访问.

Q: http://gappproxy/headers?
A: 彩蛋二号. 保护你隐私用的. 谢谢偶吧. 访问方法同上.

Q: 为什么把 3 次抓取改成 2 次? 这样会多出不少 591 错误.
A: 这是流量与效率间的平衡. 你愿意的话可以改回 3 次. (在 fetch.py 查找Fetch_Max = 2)

Q: 怎样检测部署成功与否?
A: 是, 偶把 GET 页面去掉了. 直接用客户端测试吧.

Q: 还是不如 r102 版本好使.
A: 不好的话就喊出来让偶听见, 偶会尽量修掉的.
但有一个例外, 混用客户端产生的问题偶不会管的.

Q: Youtube…
A: Youtube 能够正常观看的视频都会得到至少一个 (HEAD) HTTP 303 请求, 也就是说如果没有这样一条请求, 视频不能观看属于 GAE 方面的问题. 更换视频质量(如切换到 480p 等) 说不准有意外的惊喜.

这个 303 请求的地址是这样的 (其中 fmt 有别的数值):
http://www.youtube.com/get_video?video_id=YYYY&T=XXXX&fmt=18

当然偶是希望各位尽量多试几个视频再下结论.

Q: 问题真多.
A: 就需要小白鼠排地雷. 不过好像这两天没什么大问题了.

Q: 如何报告问题?
A: 请截取相关日志记录. 作者使用的是 HTTPFox. 当然命令行窗口中显示的日志也可以.

Q: 下载地址…
A: 看完这个再说. Gappproxy2 正式发布 (2010.5.20 Bug Fix)

Gappproxy2 是 Gappproxy 的一个分支版本. 作者 fcicq.
代码授权与 Gappproxy 相同, 均为 GPLv3. 感谢原作者 XiaoGang.

第一版本 0.99, 代码来自 gappproxy svn r102.

gappproxy2 的服务器端 fetch.py 与原 gappproxy 客户端不兼容.

gappproxy2 不附带 app.yaml 及 ssl/LocalProxyServer.cert, ssl/LocalProxyServer.key 文件. 有需要者请自己动手.

没有 Win32 可执行文件版本.

最简单的自签名证书生成方法:
openssl req -x509 -days 365 -newkey rsa:1024 -keyout LocalProxyServer.key -nodes -out LocalProxyServer.cert

不想当小白鼠的同学就别下了…

去看看 FAQ 吧: Gappproxy2 FAQ

下载地址及 sha1sum, 2010.7.21 15:00 更新 0.99.9 版
gappproxy2-0_99_9.tar.gz, 参见 GAppProxy2 v0.99.9 is Here

安装方法和 gappproxy 一样, 如果你有准备好的 GAE app 的话, 替换 fetch.py 并更换新客户端即可.
0.99.9 版已添加 app.yaml 文件.

报告成功/问题, 请丢邮件到 fcicq at fcicq dot nospam dot net
(小声说: 在推上 @fcicq 也可以, 应该能看见.)

Have Fun

—

# Changelog:
修改记录

# Fixed multi-part POST request by using base64 in post_data.
# Fixed some encoding problem by using base64 in header data, dropping utf-8 encoding. REQUIRES client upgrade.
使用 Base64 保证 headers 和 post_data 完整性. (修复 Wrong length of post data 问题)
POST 请求限制更正为 768 KBytes. 上传功能已可用.
(重要: **与以前的客户端不兼容**)


问: 有没有其他的破解 WPA 的方法?
答: 当然有.

比如有一种路由器品牌叫 FASTWEB, 这个品牌在意大利比较流行.
有人使用 IDA Pro 调试时找到了其出厂 WPA 密钥生成的算法. Source

假设原 SSID 为 FASTWEB-1-00193EA1B2C3.
将 0×00,0×19,0×3E,0xA1,0xB2,0xC3 与此密钥相连.
0×22,0×33,0×11,0×34,0×02,0×81,0xFA,0×22,0×11,0×41,
0×68,0×11,0×12,0×01,0×05,0×22,0×71,0×42,0×10,0×66
计算 md5 (二进制形式), 每次取 5 bits, 共取 5 次.
每一段的数值如果小于 0xA 就加上 0×57. 变换为 16 进制即为结果.

用命令行计算 md5.
echo -en "\x00\x19\x3E\xA1\xB2\xC3\x22\x33\x11\x34\x02\x81\xFA\x22\x11\x41\x68\x11\x12\x01\x05\x22\x71\x42\x10\x66" |md5sum

php 版, 能够直接输出密钥. SSID 在代码第一行.

< ?php
//By fcicq (http://www.fcicq.net/wp/), Released under GPLv2
$a = sprintf("%c%c%c%c%c%c",0x00,0x19,0x3e,0xa1,0xb2,0xc3);
$b = sprintf("%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c",
0x22,0x33,0x11,0x34,0x02,0x81,0xFA,0x22,0x11,0x41,
0x68,0x11,0x12,0x01,0x05,0x22,0x71,0x42,0x10,0x66);
$md5 = md5($a.$b,true);
//only the first 4 bytes is needed.
sscanf($md5, "%c%c%c%c", $m0, $m1, $m2, $m3 );
$k1 = ((ord($m0) & 0xF8) / 8); //11111000
$k2 = ((ord($m0) & 0x07) * 4) + ((ord($m1) & 0xC0) / 64); //00000111 11000000
$k3 = ((ord($m1) & 0x3E) / 2); //00111110
$k4 = ((ord($m1) & 0x1) * 16) + ((ord($m2) & 0xF0) / 16); //00000001 11110000
$k5 = ((ord($m2) & 0xF) * 2) + ((ord($m3) & 0x80) / 128); //00001111 10000000
if ($k1 >= 0xA) $k1+=0x57;
if ($k2 >= 0xA) $k2+=0x57;
if ($k3 >= 0xA) $k3+=0x57;
if ($k4 >= 0xA) $k4+=0x57;
if ($k5 >= 0xA) $k5+=0x57;
printf("%02x%02x%02x%02x%02x\n", $k1, $k2, $k3, $k4, $k5);
?>

考虑到品牌厂商的 MAC 前缀数量有限, 其 MAC 可能性为 256^3 * MAC 段数.
而密钥可能性为 32^5, 所以密钥的全部组合更适合作为字典使用.
以全部密钥作为字典只需要占用 32^5*(10+1) = 352 M 空间.
但如果不知道密钥范围的话就比较麻烦了. 256^5 = 2^40 给人的感觉就太大了.

看过这个之后, 你是不是想测试一下自己的路由器是否也内置一种默认密码算法?
或许某些人会往这个方向努力的.

—

问: 什么样的字典适合 WPA?
答: 首先要考虑覆盖面大的弱字典. 事实上偶的 unidict-20100410 就是这样考虑的.
其次是社会工程方面, 知道的信息越多越好. 如果这些都弄不出来的话用一些字典生成器也可以, 但希望就不太大了.

问: 方便的手机号生成器?
答: 有个现成的号段表, Download
使用方法:
awk '{j=$1*10000; for(i=0;i<10000;i++) printf("%.f\n",i+j);}' 0397.txt > 0397-mobile.txt

—

问: 一台破解一台连接是否有用?
答: 没有用. 但不可否认的是, IV 确实增加了. 建立连接时得到的数据包不可重发.
对 WPA/WPA2 来说抓到的是错误的握手包, 不会有 Data 产生, 并得到 Deauth Packets.

问: 某些网卡显示频道不对, 133 频道什么的.
答: 既然不是 5 Ghz 的网络那就是 Bug. 参见 Aircrack-ng Ticket #670.
133 频道是正常的 6 频道. 每增加/减少 5 个频道等于正常增减的 1 个频道. 对应表就不列了. 1 频道是 Ch 108, 13 频道是 Ch 168. 不过好像很少见呢.

问: 利用 WPS / QSS 破解 WPA2 的可能性?
答: 已有专文叙述. 流言终结者: WPS, CSRF, 802.11n

—

问: 如何加固无线网络?
答: 换有线网络
WPA2 都不能挡住 -0 这种攻击形式(当然这实际是两回事), 不换有线又能怎么办呢…
可以把整个无线网络全部切换到 802.11n 设备, 并使用 Greenfield mode (此时会失去 802.11b/g 的向后兼容性).
另一个好处是由于制式不同, 传输范围与速率都将增加.
再需要高安全性的就上 VPN 好了, 可是这样也不能解决 -0 这样简单的问题.

问: WAPI 安全性如何?
答: 市面上有 WAPI 路由器卖吗? 既然没卖的那怎么知道?

—

系列全部文章一览:

Wireless Series 预告篇
Wireless Series(1): 驱动与网卡芯片支持列表 (至 2010.4)
Wireless Series(2): 常用软件与工具 (Windows 平台)
Wireless Series(3): 常用软件与工具 (Linux 平台)
Wireless Series(4): 天线, 信号, 距离 (2010.4.30 Updated)
Wireless Series(5): 网卡好坏的判断标准
Wireless Series(6): Aircrack-ng (1), 基础篇
Wireless Series(7): Aircrack-ng (2), Aireplay-ng 模式
Wireless Series(8): Aircrack-ng (3), 总结篇
Wireless Series(9): FeedingBottle
Wireless Series(10): 高级应用 (1)
Wireless Series(11): 高级应用 (2)
Wireless Series(12): 问与答 (全文完)

—

至此整个系列就全部完结了.
这些文章以后如果有机会的话还会做一些补充与更新. 而这是转载者所做不到的.
就是转载也要遵守一些规则, 不要给图片再加一次水印, 保证文章链接的完整性. 这叫守 PageRank 奴?

推荐的转载方式是仅转载预告篇, 并保持链接完整.

对文章的反馈可以扔到留言板上去. 虽说需要审核.

—

这段时间耽误了不少正常文章的发布.
个人大修过的 gappproxy 将于近日放出, 敬请期待.

倒数第二篇. 原定的 Part 12 因为篇幅太短取消, 合并到最后一篇.

—

使用 dsniff 分析 pcap 文件, 获得机主相关信息.
攻击的部分就不写了, 主要原理是 ARP 欺骗. 这部分写出来危害比较大.

如果要获取未加密的密码信息, 使用 dsniff. 可以在线被动监听, 也可以使用 pcap 包文件.
无线相关加密的 cap 包必须先解密再用. 具体要不要保留 802.11 头你要自己试一试.
使用 -d 参数可以指定 pcap 包, -i 参数指定监听的网卡名称.
(不推荐用于无线网卡, 用 airodump-ng 等监听, 解密包再用 -d 参数查看)

urlsnarf 可以从 pcap 包中提取用户所上的网站, 并输出为 Apache 日志格式, 并可以用相关工具分析. 用法和 dsniff 相似.

如果需要查看 DNS 请求情况则需要 tcpdump.
tcpdump -r XXXX.pcap -l -n 'udp && port 53'

查找 QQ 号则使用 Wireshark 等工具.

此外 Wifizoo 功能也不弱. 支持 pcap 读入. 但它的安装不太方便. 所以推荐找现成做好的发行版用.
用它做 cookies 劫持相当方便(因为自己能够作为 proxy 使用).

—

PPP(PPPoE) 的认证方式有以下几种:
PAP, CHAP, MS-CHAPv1, MS-CHAPv2. 其中 PAP 是明文的. 其余的几个可以使用 Cain & Abel 等软件挂字典破解(未测试).

使用 rp-pppoe 作为 PPPoE 服务器, 可以强制使用 PAP 认证以获取明文密码.
需要在 /etc/ppp/chap-secrets 中添加用户名密码, 并在 /etc/ppp/pppoe-server-options 中加入 show-password 和 require-pap.
当然会抓包的话只需要强制 pap 认证就可以了, 用 wireshark 就能看到密码.

有些无线猫用的是 WEP 加密, 需要再用拨号软件再拨一次号. 如果认证方法是 PAP, 那么可以解密抓包并截获密码. 如果是 WPA 就要另想办法.

有人说 MITM 中间人攻击很厉害, 偶承认这一点. 就比如说这个认证也是可以降级的. 但具体的方法这里不会说的.

—

偶一直不说 MDK3 的问题. MDK3 强归强, 某些功能影响了正常的网络就实在太不好了.
nmap, nbtstat 这类东西和无线没有太多的关系偶也不愿意写.
再往下写什么 ettercap, metasploit, (x)Hydra 之类的那就是在说黑客知识了.
这个系列总是要结束的嘛.

工具那么多, 就看你怎么用.
漏洞天天有, 看今天砸到谁.

说到高级应用哪, 写点没人写过的最为好.

高级里面也有基础.
用 airdecap-ng 可以解密已知密钥的 cap 抓包文件, WEP 和 WPA 都可以.
其中对 WPA 只能解密抓到四次握手包之后传输的数据.
注1: Wireshark 可以即时解密已知 WEP 密钥的数据包, 但偶不推荐这样做, 开销比较大.
注2: Cain & Abel 也有这个能力.
注3: 使用 airdecap-ng 的 -l 参数可以保留数据包的 802.11 头.

—

假定有一个抓包文件为 1.cap, 使用 -l 参数解密得到 1-dec-l.cap, 不使用 -l 参数解密得到 1-dec.cap.

首先是 MAC 过滤与绑定问题.
使用 aircrack-ng 1-dec-l.cap 可以直接看到 IP 地址 (这样不能取得明确的 IP – MAC 对应关系). 所以不推荐这种方法.
也可以使用 pcaputils 工具组里的 pcapuc.

小知识:
pcaputils 系列工具基本都支持 BPF syntax.
Wireshark “eth.src == xx:xx:xx:xx:xx:xx” 相当于 TCPDump (BPF) 的 “ether host xx:xx:xx:xx:xx:xx”

依照数据包数量排序 IP
pcapuc -r 1-dec.cap -S | sort -k2nr | head
过滤客户端 MAC 后立刻看到 IP 地址 (MAC 自己从 airodump-ng 界面去找, 用 CSV 文件也可以)
pcapuc -r 1-dec.cap -S -f "ether host xx:xx:xx:xx:xx:xx" | sort -k2nr | head

如果 airodump-ng 输出的 CSV 文件丢失了怎么办?
airodump-ng -r capture-file -w output-file

—

使用双网卡注入的方法:

简单说就是用 aireplay-ng -2 来发送其他网卡截取的包. 仅限 -2, -3 和已获得密钥生成注入包的 -4, -5 使用.
如果你有一块功率大而接收一般的卡, 一块功率小但接收很好的卡就可以用此法. 虽然偶这里写的很简单, 但你会发现这种方法的厉害.
airtun-ng 也可以做这种事情, 不过面对的对象不一样. 你可以自己试试看.

远程操作注入的方法:

在目标机器上启动 airserv-ng, 需要用 -d 来指定物理无线网卡.
airserv-ng 默认监听 TCP 666 端口. 需要先用 airmon-ng 设置网卡为监听模式.
在使用其它套件时可以把 127.0.0.1:666 指定为 interface.
将 127.0.0.1 换成远程 IP (注意在防火墙上开放该端口) 即可截取/注入远程网卡.

—

Wardriving 简单总结:

gpsd -N -n -D 3 /dev/ttyUSB0
kismet # 需要换一个 terminal 窗口, 自己配置一下监听网卡
giskismet -x XXXXX.netxml
giskismet -q "select * from wireless" -o output.kml

注1: gpsd 和 kismet 运行需要 root 权限, 打开 gpsd 之前先杀掉现有的 gpsd.
注2: USB GPS 设备可能不是 /dev/ttyUSB0.
注3: 请自备 giskismet 以导出为 Google Earch KML 文件.
注4: 请选择信号接收良好, 设备驱动完善的网卡. 较新的驱动对 rtl8187l 支持不佳.
注5: 关于 gpsd, 等定位完成之后再打开 kismet.
注6: kismet 输出的 pcapdump 文件有较大的研究价值, 通过 Beacon Frames 可以看到很多东西.
注7: GPS 如果失去定位的话 kismet 应该会有声音提示.
(自己试试看, 尽量设法调出这个声音来再出发, 日后会省不少麻烦.
kismet 会把失去定位时测到的 AP 的坐标设为一个你不希望看到的地点.
对 Warwalkers 和 Warbikers 来说一定要注意, 失去定位的可能性还是相当大的)
注8: giskismet 执行完带 -x 参数的命令之后会生成一个 sqlite 数据库文件, 有非常大的分析价值.
注9: 强烈不推荐使用 airodump-ng 做 wardriving 相关活动. 加上 gpsd 参数也不行.
注10: 尽量不要用 kismet 自带的 gps 功能, 要开启单独的 gpsd 进程.

通过 Wardriving 究竟能发现些什么东西呢? 总之偶能分析到的东西比某些人多得多.

FeedingBottle 是 aircrack-ng 工具组的 GUI, 主要运行环境为基于 Tiny Core Linux 的 Beini 系统. 作者赵春生.

FeedingBottle 封装了几乎全部常用的 aircrack-ng 命令组合(-6, -7 攻击模式除外).
高级模式给用户以更大的自由度. 普通模式和 spoonwep 几乎无异.
高级模式下点击按钮就能完成对应的操作, 所以偶前面也没必要把命令全摆出来.

—

这一篇事实上没什么可写的. 顺便说说 Beini 做的一些修正之处, 凑个字数

最值得一提的是修正了 Aireplay-ng -1 模式不支持中文 SSID 的问题.

这个问题目前有两种修复途径.

第一种是 Patch: 修改 aireplay-ng 代码，使其支持中文 SSID 的伪连接操作

第二种是暴力伪连接. 原理是修改 wpa_supplicant 的配置文件以达到同样的连接效果.
这种方式速度较慢, 推荐在不支持 -1 的网卡上一用. 当然偶不反对大家用这个模式来碰运气.
minidwep-gtk 也支持这种暴力伪连接, 并使用这种方式绕过了打补丁的问题, 即对使用中文 SSID 的 AP 不使用 -1.

使用 aircrack-ng 系列工具的一般步骤:

首先用 -9 确认你的网卡有注入能力. (可选, 如果是已知可以注入的网卡则不需要做此步)

判断 AP 的加密类型.

如果是 WEP:
用 airodump-ng 监听对应频道.
查看客户端情况. 有客户端使用 -3 和 -0.
(但如果能用 -1 的话尽量不用 -3 和 -0 的组合, 第七部分已经说过 -0 可能会被发现. 推荐在网络不活跃时使用.)
对无客户端, 测试 -1 情况, 如果 -1 成功则使用 -2, -5, -4 中的一种或多种.
# Data 数量达到 8000 以上时可以开始用 aircrack-ng 破解.
如果 Data 数量不足 4 万时可以加入参数 -n 64 以加速短密钥破解. 但超过后请去掉这个参数以免影响长密钥的破解.
此外, -k, -f, -D 等参数也会影响密钥的破解, 但一般不需要使用这些参数.

(可选) 使用 airdecap-ng 解密得到的 cap 文件, 获取 AP 与客户端相关信息.

如果是 WPA-PSK / WPA2-PSK:
用 airodump-ng 监听对应频道.
查看客户端情况. 有客户端则使用 -0 使其掉线, 参见第七部分, 推荐在网络不活跃时使用. 对于信号弱的 AP 可能需要调整天线的方向甚至放弃 (判断标准见下).
得到握手包后(airodump-ng 界面显示 [WPA Handshake: XX:XX:XX:XX:XX:XX]), 请尽量等到几个 # Data 后再关闭 airodump-ng, 以确保密钥的正确性 (如密码错误会收到 Deauth Packet, 以便后续分析).
注: 如果不能完整抓到四次握手, 有 Data 也不能验证密钥正确性.
使用 aircrack-ng, EWSA, cowpatty (如果 AP 的 SSID 比较常见, 可以使用 rainbow table) 等软件配合字典破解.

—

aireplay-ng 模式与信号的关系:

-4, -5 对信号的要求最高. 其次是 -1. 再其次是 -2, -3, -0.
如果传输过程中有丢包现象, -4 和 -5 的工作会受到较大影响.
虽然 -0 对信号要求最低, 但使用 -0 后如需要某些数据包的话, 对信号的要求仍然是不低的. 参见第七部分.
如果考虑这些因素, 排序将是 -4, -5, -0, -1, -2, -3.

—

信号的判断方法:

PWR: 如为负数, 则绝对值小为信号强. 如为正数, 则数值大为信号强. 不同的驱动有不同的表示方法.
注: PWR 为 0 或 -1 属于无效数据. 部分网卡没有 PWR 值. 部分网卡的 PWR 值不准确, 没有参考价值. 客户端 PWR 值的参考意义不大.
Beacons: AP 通常每 100ms 发送一个 Beacon Frame, 间隔时间可以在路由器管理界面中修改.
如果仅在一个频道中监听(CH 不变化), 单位时间内 Beacons 增长快的信号好.
有经验者可以根据 Beacons 的增长速度直接判断信号强度, 其判断准确率很高.
高级用户还可以查看 ACK 包的数量, 并依此判断 -0 成功的可能性.
Beacons 变化极慢的 AP 推荐放弃, 对于 WPA 的情况更是如此
#Data: 对 WEP 来说是破解的基础. 在注入时增长越快越好, 一般每秒 300 个左右就算不错了. 不同的卡注入速度不同, 主要和驱动程序有关.

—

ps:
有些东西是从来没有人写出来的, 对吧 写出一句话来就够你想一会儿的.
偶不写这文章, 照样有很多人能学会怎么做.