05.19.12

近期工作总结：关于对Flash player的逆向工程进展

从上个月的最后一周（4月21日）到现在，我一直在做对flash的逆向工程，主要是使用IDA做静态代码分析。这方面我完全是外行，上次干这个还是在大3的时候，给宿舍用的电信的802.1x客户端做开源FreeBSD版。下面介绍一下中途遇到的困难以及现在的进展。

首先是用PEiD做壳检测，什么都没查到，我估计是因为PEiD很久没更新了。从PE Header中能看到linker version 是9.0，所以，如果它没有加壳的话，那么PEiD应该能检测到vc++ 2008的runtime才对。就我后续的分析来看，没有发现它带壳。所以这次的工作跟我上次做802.1x客户端相比，简单了很多。上次的重心在于找到OEP，脱掉asprotect2的壳，然后分析出发送密码的那个包采用的什么方式对密码进行hash就行了。这次呢，虽然没有壳，但是flash player的代码量何其庞大，其中我要分析的部分，大约包含至少1万3千行C++代码。所以这次的重心就是要有耐心，挨个挨个标函数。

然后是要找一个合适的IDA的版本。我现在用的是IDA 6.1 with hex-rays decompiler 1.5，从verycd上下载的（http://www.verycd.com/topics/2900356/）。其实我没看出来IDA 6.1比5.5有哪些特别的改进，可能是因为我之前用的也不深吧。IDA这种神器我还是很愿意花钱买的，少请朋友吃2次饭就够了。可是国内没有销售渠道。IDA对产品销售控制的很严格。

然后就是选择flash的版本。我试了好几个，包括standalone的和ActiveX的，debug的和非debug的，11.2、11.1、10.x的。最后选择的是从http://www.adobe.com/support/flashplayer/downloads.html 下载的“Windows Flash Player 11.2 Projector content debugger ”。这是一个独立的exe，无需安装，双击即可运行，调试起来比ActiveX的方便很多。

刚开始的工作比较简单，我还没有开始用OllyDbg，就直接在IDA中调试。遇到的第一个问题就是关于Address Space Load Randomization（ALSR）的。有很大的概率，在我启动调试后，IDA会卡住很久，说“Rebasing program to 0x01F51000”（这个地址频繁变）。因为这个对话框是IDA弹的，所以我刚开始以为这是IDA的特性，就在IDA的设置里面改来改去，发现始终不能解决问题。后来才发现自己走了弯路，这明明是操作系统干的，它为了防止缓存区溢出漏洞被利用，于是就在载入PE镜像的时候把基址随机化。然后这个操作被IDA检测到了，所以IDA需要在新的基址上，把以前的分析重做一遍，所以就会卡住很久。而且，由于地址一直在变，所以导致我对vtable的标注没法进行。解决办法很简单，修改PE Header，删掉关于ASLR的flags即可。详情请见http://www.sunchangming.com/blog/?p=4148

然后遇见的第二个问题，就是如何更有效的识别C++对象？IDA比较智能，能自动帮我把全局函数和对象的成员函数分开（虽然他的判断经常有误）。但是然后呢？如果一个成员函数中大量的使用到了对象指针，而我不能获知对象类型的话，简直就是盲人抓瞎啊。于是我在网上找了很多资料，如何从对象指针获得类名。主要有两种手段，一个是通过C++的RTTI，很不幸，flash貌似没有开RTTI。另一个是通过MFC/QT的RTTI，很不幸，flash没有用MFC/QT。可能ActiveX版本的Flash会用到一些MFC，但是我所关注的这部分代码因为和界面无关，所以没用。但是比较幸运的是，我发现这些代码大量的使用了继承。就像MFC的所有Object都从CObject继承那样，这边的每个C++类，也都至少有一个vtable。于是，利用vtable可以粗略的把类型分开。虽然这种判断方式常常会出错，因为vtable可以在不同类之间复用。但是就目前来看，这种方式似乎工作的还不错。

然后遇见的第三个问题，就是msvcrt中很多很基本的函数，IDA没有给我识别出来，比如malloc，比如memcpy，而是显示成unknown_libname_115这样的形式。这个问题至今没有解决。但是当我在跟踪对象的动态创建的时候，有了一个很大的意外收获。就是我通过在Google中搜索某一个错误提示字符串，找到了MMgc的源代码。MMgc来自于Mozilla的一个名为Tamarin开源项目。Tamarin的主要代码来自于Adobe贡献，最初的目的是做一个开源的ECMAScript引擎，给Adobe flash以及Firefox的js用。Tamarin的源代码仓库现在主要有3个分支，分别是tamarin-central（最后更新2010年3月）、tamarin-redux（最近一直在更新）、tamarin-tracing（最后更新2008年10月）。我把3份代码都下载下来，最后发现最新的那个分支（tamarin-redux）与Adobe Flash 11.2基本完全一致。从这点来说，Adobe确实是把Flash的核心代码都贡献出来了，而且一直在持续向Mozilla提交。虽然这个项目已经处于被Mozilla遗弃的状态，因为Firefox嫌这个引擎太慢，没用它。于是我前面的疑惑也有了答案，初步看来，大部分类都是从GCObject直接或间接继承而来，所以几乎每个对象都有一个vtable，而且后面还通常紧跟着一个32位的int，看起来像是reference counting。

我一直有个想法，把tamarin的代码编译一遍，然后用IDA把特征文件sig做出来，然后apply到我当前的项目中去，应该是比我之前那样挨个手工标注要好很多。另外就是把vs2008的msvcrt也这么搞一下，会不会识别率能高一些？

我现在主要的工作是在标记类型。一个对象，如果是在栈上，那么直接就可以通过栈的布局看到大小，如果是在堆上，那么可以通过传递给MMgc的内存分配函数看到大小。然后根据构造函数，挨个挨个的把布局猜出来。不过此时类成员变量只有一个大致的类型名(int、bool)，没有名字，而且无法把指针从int中区分出来。然后就是根据函数中怎么用它，把类成员变量的名字给慢慢补上。

我在做这件事情的时候，一直遭到很多质疑，关于这么做是否必要。我的目的是为了把某协议的spec弄清楚，有人认为抓包分析就够了。我不赞同这点。首先，这个协议的所有报文都是使用AES加密的，要不是别人已经通过逆向工程把密钥给你提供出来了，就凭自己抓包想猜出AES密钥来，那完全没可能，因为你没那么大的计算能力。其次，通过抓包会发现某些位置，收到的总是同样的字节。这些字节若不是0xFF、0xFF这样的重复的padding，就肯定都是有特殊含义的，通过抓包很难把每一位代表什么意思搞清楚。最后，我已经找到了收到包根据包类型进行处理的那个swith…case函数，通过这种方式，我可以保证没有漏任何包类型。只要我把每个包处理函数都跟踪完，那么协议就完全明了了。而通过抓包分析，可能会漏掉某些类型，以及某些特殊的flag。

目前进展比较慢。我也很急。

| Posted in 计算机与 Internet | No Comments »
05.15.12

Visual C++中的几种函数调用方式

（本文中所有汇编代码均采用Intel语法，即dest在左边）

C++中的函数被编译成汇编代码的时候，必须遵循一定的规范，如参数怎么传递，栈指针怎么增减。Visual C++中，一共有5种情况：

  1. __cdecl
  2. __stdcall
  3. __fastcall
  4. __thiscall

默认情况下，是__cdecl。__cdecl 和__stdcall的区别是：__cdecl是调用者清理栈，而__stdcall是被调用者清理栈。所以，理论来说，__cdecl生成的代码体积会更大。但是，对于varargs函数，由于被调用者并不知道参数的具体长度，所以这样的函数只能采用__cdecl。

所有这四种方式，生成的函数都有固定的边界特征，

__cdecl 和__stdcall以这样的模式开始：

push ebp ;保存ebp
mov ebp,esp ;设置栈指针
sub esp,0C0h ;为局部变量保留栈空间
push ebx ;保存在这个函数中可能用到的寄存器
push esi ;保存在这个函数中可能用到的寄存器
push edi ;保存在这个函数中可能用到的寄存器

以这样的模式结束:

pop edi ;恢复寄存器原先的值
pop esi ;恢复寄存器原先的值
pop ebx ;恢复寄存器原先的值
add esp,0C0h ;与前面的sub esp,0C0h对应
mov esp,ebp ;恢复栈指针
pop ebp ;恢复ebp
ret

其中 “mov esp,ebp; pop ebp;”也可替换成一句“leave”指令。

如果是__stdcall，最后一行的ret会变成

ret 0Ch

这样。最后的那个数字代表从栈上弹出多少个字节，它应当等于函数参数的总大小。

类的成员函数默认是采用__thiscall。它与__stdcall非常相似，区别是this指针会通过ecx传递。所以，如果在一个函数中发现ecx未被赋值就开始读它，那么多半是__thiscall。如

push ebp ;保存ebp
mov ebp, esp ;设置栈指针
push ecx ;保存在这个函数中可能用到的寄存器
push ebx ;保存在这个函数中可能用到的寄存器
push esi ;保存在这个函数中可能用到的寄存器
mov esi, ecx ; 注意！！！ecx尚未被赋值就开始读了
mov ebx, [esi+344h] ; this指针一般存放在esi中，并且在整个函数体内，esi尽量保持不变。

另外再次强调，__thiscall末尾的ret语句要跟一个数字，来清理栈上的函数参数。

另外就是，如果类成员函数采用了变长参数列表，那么就不能用__thiscall，而必须用__cdecl，把this指针作为最后一个参数弹入。

__fastcall和__thiscall有时候很难区分开。__fastcall是把前2个DWORD类型的参数用ecx,edx传递，其它的继续push进栈里。

假设函数声明为:

void __fastcall testfunc(int x,int y);

那么调用这个函数的代码testfunc(3,4)就会被编译成

mov edx,4
mov ecx,3
call testfunc

"/GS" : Buffer Security Check

如果编译的时候加了"/GS"参数，并且开启了优化（如Release版本），那么对于某些可能会遭受缓存区溢出攻击的函数，编译器在生成代码的时候，会在函数局部变量的最末尾加一个4字节的cookie。如：

push ebp
mov ebp, esp
sub esp, 214h
mov eax, ___security_cookie ; random value, initialized at module startup
xor eax, ebp ; XOR it with the current base pointer
mov [ebp+var_4], eax ; store the cookie

___security_cookie是一个随机数，在程序启动的时候由CRT初始化，此处把当前的栈指针（ebp）和这个cookie作XOR运算，然后在return之前再检查一遍：

mov ecx, [ebp+var_4] ; get the cookie from the stack
xor ecx, ebp ; XOR the cookie with the current base pointer
call __security_check_cookie ; check the cookie
leave
retn 0Ch

__security_check_cookie是一个__fastcall，代码如下：

void __declspec(naked) __fastcall __security_check_cookie(UINT_PTR cookie)
{
    /* x86 version written in asm to preserve all regs */
    __asm {
        cmp ecx, __security_cookie
            jne failure
            rep ret /* REP to avoid AMD branch prediction penalty */
failure:
        jmp __report_gsfailure
    }
}

就是简单的做下比较，不正确则终止。

| Posted in C/C++ | No Comments »
05.10.12

Windows下调试ActiveX控件

VC较老的版本自带一个叫做ActiveX control test container的东西，从vs 2008开始，这个被移除了，改为以源代码的方式放在Samples里面发布。在VS的安装目录下有一个Samples目录，里面有一个VC2010Samples.zip，打开之后把C++/MFC/ole/TstCon解压缩出来并且编译即可。

这个东西可以支持VBA脚本，于是就可以自动化测试ActiveX控件，比如

Sub RunTest()
set ocx=TCForm.InsertControl(“ShockwaveFlash.ShockwaveFlash.11″,”flash”)
ocx.LoadMovie 0,”D:\Users\cm\doc\p2p\p2p.swf”
ocx.play
End Sub

然后用tstcon.exe /D xxx.dsm 执行。

但是我之前的用link.exe修改pe header的方法，似乎对ocx不好使了，所以用IDA调试ocx还是有些困难。另外，IDA似乎不支持加条件断点啊？

| Posted in C/C++ | No Comments »
05.7.12

VC++中delete函数第一行的”mov edi,edi”是做什么的？

下面这段代码来自于vc 2010的crt。就是标准库中delete操作符的实现。 

void __cdecl operator delete(void* p)
{
78523C70  mov         edi,edi
78523C72  push        ebp
78523C73  mov         ebp,esp
#if !defined(_AFX_NO_DEBUG_CRT) && defined(_DEBUG)
        _free_dbg(p, _NORMAL_BLOCK);
78523C75  push        1
78523C77  mov         eax,dword ptr [p]
78523C7A  push        eax
78523C7B  call        dword ptr [__imp___free_dbg (783D1844h)]
78523C81  add         esp,8
#else
        free(p);
#endif
}
78523C84  pop         ebp
78523C85  ret

很奇怪的是，这个函数并不是以

push ebp 

mov ebp,esp

开始的。在这两行指令之前，有一句

mov edi,edi

实在不明白这样的指令有什么用。

| Posted in C/C++ | 2 Comments »
04.28.12

Howto:从C++对象指针得到类名

JAVA程序在运行的时候，有丰富的动态类型信息。而C++则困难的多。C++的运行时类型信息有３种实现方式：语言本身的RTTI、MFC的CObject、QT的moc。下面仅介绍前两种。

一、语言本身的RTTI：

如果是POD类型，如：

class PodPoint{
public:
    int x;
    int y;
};

那么它和C语言中的struct没有什么区别。sizeof(PodPoint)=8。

偏移值 内容
0 x
4 y

 

别妄想能从它的对象指针中得到什么类型信息。

 

如果它有虚函数，那么就不一样了

class PodPoint{
public:
    int x;
    int y;
    virtual ~PodPoint(){};
};

在32位程序中，sizeof(PodPoint)=12。这是因为凡是有虚函数，就必须有vtable。所以PodPoint的实际布局就变成了这样：

偏移值 内容
0 指向vtable的指针
4 x
8 y

如果编译的时候打开了RTTI（在vc2005及以上版本默认会打开），那么就很有意思了。在vtable[-1]的位置，是一个特殊的指针，指向RTTI Complete Object Locator，它的第12个字节开始，是一个指针，指向type_info对象。于是我就写了下面这样的代码：

void printMyClassInfo(void *p){
    type_info*** vtable=(type_info***)(*(int*)p);
    type_info** v1=vtable[-1];
    type_info* v=v1[3];
    printf("%sn",v->name());
}

在有vtable的情况下，这个函数工作的非常好。

二、MFC的RTTI

MFC中的大多数对象都从CObject继承而来，例如：

class MyPoint:public CObject{
public:
    int x;
    int y;
    DECLARE_DYNAMIC(MyPoint)
};
IMPLEMENT_DYNAMIC(MyPoint,CObject)

 

那么我们就可以通过调用CObject的

virtual CRuntimeClass* GetRuntimeClass() const

来得到类名。这个函数一般就在vtable的第一个。

代码如下：

void printClassInfo(void *p){
    int vtable=*(int*)p;
    CRuntimeClass* info;
    __asm{
        mov ecx,p;
        mov eax,vtable;
        call [eax];
        mov info,eax;
    }
    printf("%s",info->m_lpszClassName);
};

假如将上面的IMPLEMENT_DYNAMIC和DECLARE_DYNAMIC去掉，那么输出的结果将是”CObject”，而不是”MyPoint”，原因很简单。因为子类没有覆盖基类的这个方法嘛。

| Posted in C/C++ | No Comments »
04.26.12

Address Space Load Randomization以及如何禁用

从Vista开始，Windows引入了一个新特性，叫Address Space Load Randomization(ASLR)。简单点说，就是将EXE/DLL的载入基址随机化。ASLR已经是一个非常普遍的特性，在几乎所有的现在操作系统中都引入了（如Linux、Windows Vista/7、iOS5）。但是ASLR对程序员来说可不是个好东西，明显增大了调试程序的难度。最近我在对Adobe Flash Player做逆向工程，发现我用ida启动调试的时候，经常会出现一个对话框，说"Rebasing program to xxxxx“。

 

别听它说什么”Just a moment”，实际上要等很久很久才好。因为基址改变后，所有的地址都得重新计算，整个程序需要被重新分析一遍。

用SysinternalsSuite中的Process Explorer(procxp.exe)可以查看一个进程是否启用了ASLR：

 

通过修改PE文件的头部，可以禁用掉ASLR。强烈建议在对任何EXE/DLL做逆向工程前，先禁用掉它的ASLR选项，然后再往IDA/OllyDbg里面拖。下面用visual studio中自带的工具来查看并修改PE头：

首先打开"Visual Studio 命令提示”，然后输入

D:> dumpbin /headers flashplayer_11_sa_debug_32bit.exe

就可以查看到这个PE文件的头部信息。输出很长，在OPTIONAL HEADER VALUES中有一项是”DLL characteristics“，如

8140 DLL characteristics
       Dynamic base
       NX compatible
       Terminal Server Aware

如果它的值是8140，就说明打开了"Dynamic base”。用VC的链接器禁用掉它即可。

D:> link /edit /dynamicbase:NO flashplayer_11_sa_debug_32bit.exe

 

再 试一试吧！

| Posted in windows | 1 Comment »
04.18.12

联通iphone套餐对比

联通iphone套餐实在是让人眼花缭乱，到底选哪个好呢？本文的目的是为了给你拨开数字背后的秘密。

如果我想买个iphone 4 8G，准备使用联通的网。那么现在有3种选择

1. 联通预存话费送手机

2. 联通购手机入网送话费

3. 在苹果的官网购机入网。

我的思路是，首先分析我想要得到什么样的服务，然后计算我需要为之花多少钱。

为了分析简单，下面假设我每月使用96套餐，并且打算使用2年左右，那么下面分析上述３个方案的总计支出

方案1：

联通预存话费送手机，合约价4999。选择96套餐，每月联通返91，所以我需要再付5块。总计支出4999+5*24=5119。

方案2：

裸机价格3999，每个月返38的话费，我需要再付(96-38)*24=1392元，总计支出3999+1392=5391。

方案3：

裸机价格3988。联通现在有1年期的入网送话费活动，一次存168，每月返28+14，带4的再加10块。总计支出：3988+(96-28-14-10)*24+168*2=5380，这里特别强调“带4的每月返10块”是因为，联通官网上剩下的号码都是些不怎么好的号码，一般都带４。

有了上面的计算之后，下面介绍下我是怎么分析“预存话费送手机”这个表，还是以２年期为例：

首先，购手机入网送话费不是针对Iphone特有的，这张表几乎对所有手机适用，而且联通和电信的这张表几乎完全一致。这意味着，如果联通如果要推出一个2年期的自购手机入网送话费活动，大致也是应该按照这张表返还。所以，我们要从“预存话费送手机”这张表中去除掉“购手机入网送话费”的影响。

具体做法，首先从“购手机入网送话费”这个表中，找到对应的套餐，然后用”月送话费金额”*24，加到“预存话费送手机 ”这张表的“优惠购机款”上，就是实际购机价格。

66 96 126 156
优惠购机款 3199 2799 2499 2199
月送话费金额 26 38 50 62
实际购机价 3823 3711 3600 3687

经常有人说联通iphone的126套餐是鸡肋，这要看你怎么看了。从不同的角度分析，会得到不同的结果。

不过这还没完。我们没算利息。以96套餐为例，假设年利率5%，那么方案1可得到4999*0.05*2+5*24*0.05=505.9元。方案2可得到3999*0.05*2+58*24*0.05=469.5。相差36元。折合今天的现值，约为32.6。这个钱也应该追加到上表的最后一行中。然后再追加上3999-3988=11。

同理，1年合约的96套餐的实际购机价约为3800左右。

可见，联通并没有给iphone补贴多少钱，却因此而得到了大量的优质高ARPU值的用户，简直太赚了！！！

| Posted in 计算机与 Internet | 3 Comments »
04.15.12

DHPublicKey与byte[]转换的问题

背景:

网络上经常采用Diffie-Hellman算法来交换密钥。通讯的双方首先共享2个公开数字：p和g。其中p是一个大质数，g通常等于2。则( Z_p={a=g^n pmod{p}, n in N } ) 构成一个整数群。

密钥的生成方法：

(Z_p)中选取一个随机数x，然后计算( y=g^x )。那么x,y构成一个keypair。x是私钥，y是公钥。

那么每个人只需要把自己的公钥发出去，然后通信的时候选取一个对称加密算法，利用(y^x)作为通信的加密密钥即可。其中x是自己的私钥，y是对方的公钥。

实际在用JAVA实现的时候：

公钥和私钥可以通过java.security.KeyPairGenerator生成。

//DH是算法名，SunJCE是Java Security API的Provider名，此处使用JDK自带的的SunJCE。

KeyPairGenerator kpg = KeyPairGenerator.getInstance("DH","SunJCE");

然后初始化KeyPairGenerator 这时需要传入一个java.security.spec.AlgorithmParameterSpec对象。

kpg.initialize(MODP_GROUP2);

MODP_GROUP2对象是这么来的：

StringBuffer sb = new StringBuffer();
sb.append("FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1");
sb.append("29024E088A67CC74020BBEA63B139B22514A08798E3404DD");
sb.append("EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245");
sb.append("E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED");
sb.append("EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381");
sb.append("FFFFFFFFFFFFFFFF");

BigInteger prime = new BigInteger(sb.toString(), 16);
BigInteger generator = BigInteger.valueOf(2);

MODP_GROUP2 = new DHParameterSpec(prime, generator);

它描述了DH算法所需要用到的p和g等于几。我在这里所用的prime来自于rfc2412的OAKLEY Key Group 2。

有了上述信息，就可以开始生成keypair：

KeyPair aliceDHKeyPair = kpg.generateKeyPair();
DHPublicKey dp = (DHPublicKey) aliceDHKeyPair.getPublic();

下面的问题是，怎么把DHPublicKey发出去？

首先DHPublicKey自带有一个getEncoded()方法，默认是采用X.509方式编码。但是这种编码方式，会把p,g,y都写入进入byte[]中。这对于实际应用来说，根本不必要啊，我只需要公钥(y)就行了啊！

于是我就把Y拿出来，然后转byte[]。

final int length=dp.getY().bitLength();
byte[] ret = dp.getY().toByteArray();        
if(length==1024)
     ret=Arrays.copyOfRange(ret, 1, ret.length);

这其中多了一层Array.copyOfRange是因为，BigInteger的toByteArray()方法，会把符号位也写入最终结果中。那么，如果Y恰好是1024位的，最终就会得到一个129字节的byte[]（其中第一个字节是0）

可是当我把这个byte[]收到时候再转成PubicKey，发现跟发送前不一样了：

KeyFactory keyFactory = KeyFactory.getInstance("DH", PROVIDER);
BigInteger y = new BigInteger(1, ret);
DHPublicKeySpec spec = new DHPublicKeySpec(y, MODP_GROUP2.getP(),
                MODP_GROUP2.getG());
DHPublicKey dp2 = (DHPublicKey) keyFactory.generatePublic(spec);

Assert.assertEquals(dp, dp2); //Always Fail

这个fail的原因在于，尽管p、g、Y都相等，但是l不相等。非常令我崩溃。发送前,DHPublicKey 的l=512，发送后用keyFactory得到的DHPublicKey 的l=0。JDK文档中对l的解释是“the size in bits of the random exponent (private value)”。但是我不知道为什么即使我在DHParameterSpec将它设置成512，得到的Y依然是1024字节。我在想这个要不要紧，要么忍了吧。改改test case。

| Posted in java | No Comments »
04.8.12

Birthday Problem and Hash Collision

1月份的时候，我们公司的数据部门给我们做了一次统计学的培训。 那天参加培训的大概有30-40人，主讲当时提了这样一个问题，在参加培训的人当中，有两个人是同月同日生的概率是多少？ 答案是“大于70%”。这个答案令当场的很多人吃惊。于是现场做了一下实验，确实找到了两个生日相同的人。

这个问题如果从数学角度来分析，可以看成这样：有m个球，和n个桶。依次将这m个球扔入这n个桶中的随机一个。最终，有一个桶内至少有两个球的概率是多少？

解答：

首先，我们拿起一个球，随便扔到一个桶里。然后拿起第二个球，也扔到一个桶里。那么第二个球和第一个球被扔进同一个桶里的概率是( frac{1}{n} )，不在同一个桶里的概率是( 1-  frac{1}{n} )。假设前两个球不在同一个桶里，那么我们继续，拿起第三个球扔下去，它和前两个球不在同一个桶里的概率是( 1- frac{2}{n} )。即，对于第k个球来说，假如前面k-1个球都在不同的桶里，那么第k个球被扔到一个新桶中的概率就是( 1- frac{k-1}{n} )。于是，最终有一个桶内至少有两个球的概率就是

$$ P =1 -  (1- frac{1}{n})(1- frac{2}{n})(1- frac{3}{n}) dots (1- frac{m-1}{n}) $$

下面尝试给出一个更简单的近似值：

首先，高等数学课上学过一个很重要的式子：当x远远小于1时，有(e^x approx 1 + x )。于是，当m远远小于n的时候：

$$ (1- frac{1}{n})(1- frac{2}{n})(1- frac{3}{n}) dots (1- frac{m-1}{n})approx Pi_{j=1}^{m-1}e^{-frac{j}{n}} = e^{-sum _{j=1}^{m-1}{frac{j}{n}}} = e ^ {-frac{m(m-1)}{2n}}$$

生日问题其实在计算机算法中经常遇到：假设一个Hash Table有n个桶，需要插入m个元素，那么插入过程中发生hash冲突的概率是多大？ ( 1- e ^ {-frac{m(m-1)}{2n}} )

另外，假如我希望发生hash冲突的概率小于0.5，那么n至少应该为多大？求解

$$1- e ^ {-frac{m(m-1)}{2n}} lt frac{1}{2} $$

可得：

$$ n gt frac{m(m-1)}{2ln{2}} $$

即，为了让发生hash 冲突的概率保持不变，当hash表中的元素数量(m)增长时，桶的数量(n)必须以平方的速度增长。( n approx m^2 )。

对于生日问题，假设一年有365天，那么当人数大于23的时候，有两个人具有相同生日的概率就大于0.5。

很多书上把( frac{m}{n} )定义为hash table的load factor，并且在hash table的实际实现中，在capacity增长的时候会将load factor大致保持在常数。也就是说桶的数量(n)是线性增长的，这么做是因为，在这种策略下，为了查找一个就在其中的元素，它的平均查找时间是一个常数。在这种情况下，就不要再用上面的这些式子计算P，因为前面(e^{frac{m}{n}} approx 1 + frac{m}{n} ) 的前提是m远远小n。

| Posted in Uncategorized | No Comments »
03.30.12

不用root安装rpm包

最近上线了一个hadoop集群，但是苦于线上网络和办公网络不通，需要走跳板机中转，于是我就准备拿跳板机当编译、打包的平台。可惜跳板机上很多命令都没有，比如svn。跳板机是一个公用的机器，我并没有root权限。（准确来说，我不想通过不正当途径手段拥有）

首先从collabnet下载编译好的rpm包：http://www.open.collab.net/downloads/subversion/

然后登陆跳板机：

$ mkdir -p /home/sunchangming/local/lib/rpm

$ rpm –initdb –root /home/sunchangming/local –dbpath /home/sunchangming/local/lib/rpm

$ rpm –root /home/sunchangming/local –dbpath /home/sunchangming/local/lib/rpm –relocate /opt=/home/sunchangming/local –nodeps -ivh CollabNetSubversion-client-1.7.4-1.x86_64.rpm

最后打开.bash_profile修改环境变量：

PATH=$PATH:$HOME/local/CollabNet_Subversion/bin

export PATH
export LD_LIBRARY_PATH=$HOME/local/CollabNet_Subversion/lib:$LD_LIBRARY_PATH

爽啊！！！

| Posted in Linux | No Comments »
« Older Entries