页面

2010年12月29日星期三

某厂商的产品推广活动中的漏洞

关键词:数论 概率 双色球

近日某国内IT厂商为推广旗下新产品,推出了一个活动,内容如下:

大奖第二波:新浪微博前1200名粉丝随机抽奖规则
12月28日还会产生第二位幸运大奖!为了能够取得一个公平的随机数,我们将采用12月28日晚21点30分开奖的双色球号码(http://www.zhcw.com/ssq/index.shtml)作为基数除以1200,得到的余数将作为获奖粉丝的号码(注:如果余数为0,则第1200位粉丝将获奖)
以下是前1200名粉丝名单:
....

我专门去了解了一下规则。双色球的奖是由6个红球和1个蓝球组成。其中6个红球是从01号到33号这33个球中随机选择6个球并从小到大排序。蓝球是从01号到16号这16个球中随机选择1个球,排在6个红球的后面。像上文所提到的12月28号的奖是这样的:

这样的规则下选出来的号码(4091721253101)由于各个位置上的数字不是完全随机,那么除以1200之后的余数当然也就不够随机了。说什么“一个公平的随机数”,该厂商一直给人很严谨的感觉,却犯了这么一个低级的错误。


为了证明我的推理,特别计算了一下号码中各位数字对余数的影响力。也就是将某个位上的数字从0变到9,看看余数将做出什么样的变化。


我们以号码00,00,00,00,00,00,00为起点进行分析,这个时候余数为0。当个位数从0开始每增加1时,余数也增加1。说明个位数对余数的影响是“+1”。同理,十位数对余数的影响是“+10”,百位数是“+100”,千位数是“+1000”,万位以后都是“+400”。因为是求余,有可能某位数增加的过程中,余数会因为满1200而减少,所以实际中各位数对余数的影响如下表所示:

影响
+1,-1199
+10,-1190
+100,-1100
+1000,-200
+400,-800
以下同 +400,-800

可以看出,对余数的个位数和十位数能施加影响的,只有号码的后两位可以做到,而且是后两位直接复制到余数。号码的后两位是什么数,余数的后两位就也是什么数。而号码的后两位是一个蓝球,它只能是1-16中的一个数值。显而易见,粉丝号码不满足这个条件的,当选的概率就是0了。

不仅如此,由于百位以上的数字变化也不是完全随机,那么剩下的这些满足条件的号码的概率也都是不相等的。由于各数字的变化非常微妙,单独纯理论计算各余数的出现概率似乎不太可行。我们借助计算机来模拟一下双色球的号码并计算号码除以1200所得各个余数的概率。

写计算机程序模拟演算之前,为了简化运算,我们有必要将模型简化一下。由于后两位是1-16的完全随机,对于(mnxy)型的余数,显然(mn01),(mn02),・・・,(mn16)的概率是一样的。所以我们只需要考察红球区的号码除以12所得余数的概率就可以了。

C#代码如下:

using System;
using System.Collections;

public class SimSSQ
{
[STAThread]
static void Main(string[] args)
{
//各余数的命中次数数组
int[,] probs = new int[,] {
{0,0},
{1,0},
{2,0},
{3,0},
{4,0},
{5,0},
{6,0},
{7,0},
{8,0},
{9,0},
{10,0},
{11,0},
};

//循环次数 1千万次 执行时间大约10秒
int rootTime = 10000000;

//随机数发生器,对于这次的应用,该发生器可以视为完全随机的
Random random = new Random();
long redNum;
int yu;

for (int i = 0; i < rootTime; i++)
{
//得到一个红球号码
redNum = getRedNum(random);

//求余
yu = (int)(redNum % 12L);

probs[yu, 1] = probs[yu, 1] + 1;
}

Console.WriteLine("余数\t命中次数\t概率");
for (int i = 0; i < 12; i++)
{
Console.WriteLine("{0}\t{1}\t\t{2}",
probs[i, 0], probs[i, 1], (float)probs[i, 1] / (float)rootTime);
}
Console.ReadLine();
}

//随机获得一个红球号码
private static long getRedNum(Random random)
{
//红球
int[] redBalls = new int[] {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33
};

//循环6次取6个不同的球 这个循环的方法很精巧 是从网上搜到的
int[] ballsGet = new int[6];
int index = 0;
for (int i = 0; i < 6; i++)
{
index = random.Next(0, 33 - i);
ballsGet[i] = redBalls[index];
if (index < 33 - i - 1)
{
redBalls[index] = redBalls[33 - i - 1];
}
}

//排序
int temp;
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5 - i; j++)
{
if (ballsGet[j] > ballsGet[j + 1])
{
temp = ballsGet[j];
ballsGet[j] = ballsGet[j + 1];
ballsGet[j + 1] = temp;
}

}
}

return ballsGet[0] * 10000000000 + ballsGet[1] * 100000000
+ ballsGet[2] * 1000000 + ballsGet[3] * 10000 + ballsGet[4] * 100 + ballsGet[5];
}

}
 
  代码中循环1千万次来模拟1千万个号码,费时大约10秒。以防万一,将程序运行3遍,结果如下:
第一次运行:

余数 命中次数 概率
0 901619 0.0901619
1 1092387 0.1092387
2 601096 0.0601096
3 737644 0.0737644
4 900792 0.0900792
5 1094439 0.1094439
6 601951 0.0601951
7 739544 0.0739544
8 899516 0.0899516
9 1090694 0.1090694
10 602235 0.0602235
11 738083 0.0738083


第二次运行:


余数 命中次数 概率
0 900673 0.0900673
1 1090294 0.1090294
2 602277 0.0602277
3 741315 0.0741315
4 900915 0.0900915
5 1090490 0.109049
6 600926 0.0600926
7 739800 0.07398
8 901101 0.0901101
9 1091689 0.1091689
10 600657 0.0600657
11 739863 0.0739863


第三次运行:


余数 命中次数 概率
0 900186 0.0900186
1 1092241 0.1092241
2 601803 0.0601803
3 736812 0.0736812
4 901554 0.0901554
5 1092559 0.1092559
6 602827 0.0602827
7 738813 0.0738813
8 902931 0.0902931
9 1093280 0.109328
10 600721 0.0600721
11 736273 0.0736273


可以看出,三次运行结果高度一致。从运行结果上推断,(00xy),(04xy),(08xy)的概率相等,应该是0.09附近,(01xy),(05xy),(09xy)的概率是0.11附近,(02xy),(06xy),(10xy)的概率是0.06附近,(03xy),(04xy),(11xy)的概率是0.074附近。如果有概率方面的高手能手动计算出这个概率值,请务必让我景仰一下。


结语:厂商预期每个粉丝的当选概率都是1/1200即0.000833。从上面的分析看来,粉丝号段是101-116,501-516,901-916的人当选概率是最大的,达到了0.00683,几乎是预期值的10倍。而实际中是号码为1101的人获得了这个奖项,正是上面说的那期号码(4091721253101)除以1200的余数。

使用Facebook社交插件参与评论:

2010年11月30日星期二

Windows Live Sync即将终止服务

Windows Live Sync(目前版本号2008 内部版本14.0)是一个优秀的在线同步软件及服务。由于正在被新的Windows Live Mesh所代替,服务将于2011年初停止。它兼具以下几个方面的功能甚至没有其他软件可以代替(包括新的Live Mesh):
1,自动同步。实时监控文件系统的变化。
2,同步双方必须都同时在线,以做到不经第三方中转的英特网上的p2p加密传输,增强了安全性。
3,同步过程中可以查看到精确的进度。
4,支持的windows版本广泛,只需要一个软件和一个Live ID即可实现。不需要ftp,webDAV等服务作为前提。

与此同时也有些缺点:
1,同步过程中无法暂停同步。
2,文件冲突时不能设置自动的冲突解决方案,必须每次手动选择方案。
3,当修改了同步文件夹中一个软链接文件夹(mklink)里的文本文件时,似乎有时候捕捉不到变动而不进行同步。
4,同步过程中,会将文件锁定,不允许其他应用程序访问,甚至不允许删除文件。

而新的Live Mesh和Live Sync比较,有以下优点:
1,可以选择点到点同步或者云端同步。点到点同步和Live Sync一样。如果选择云端同步,那么需要同步的双方将不必同时在线。文件将在云端保持最新。
2,2011年以后也能继续提供服务。

但是也有如下关键的不足:
1,无法查看精确的同步进度,只能看到大概的剩余同步文件数。当只同步单个大文件时,进度将完全无法掌握(间接方法:可以使用流量监控软件监控程序从同步开始时的上传流量,再配合已知的文件大小从而推断同步进度,有点麻烦,希望后续版本能够改进)。
2,仅支持Windows Vista以上版本的系统,而且对系统的SP补丁要求较高
3,内存资源占用相对较大
4,有和Live Sync的缺点1一样的缺点。是否还继承了其他缺点还有待观察。

我仔细试用过以下软件,发现都不是Live Sync的理想替代品:
1,Dropbox,SugarSync,Syncplicity一类基于云存储的服务
2,Good Sync,Allway Sync,SyncToy一类基于点到点的服务
3,金山快盘,DBank一类国产服务

转载一张别人画的Live Mesh配图以充分了解优点1:
原图来自:http://www.cnblogs.com/xyrein

使用Facebook社交插件参与评论:

2010年11月29日星期一

在线RSS阅读器分析与比较

在线RSS阅读器只用过这两个,所以只比较下这两个。

1,qq邮箱阅读空间

2,google reader

首先,两个都是utf-8对应的,不管是订阅中文还是其他语言还是混合文,都不会出现乱码。

而像订阅分类,列表/全文视图,订阅导入导出,收藏(qq是收藏,google是加星标),电子邮件发送等一些有关阅读的基本功能两者也都有,不用细说。

不同之处,qq和腾讯其他服务结合的比较好,可以直接转载到qq空间,转播到qq广播,和其他订阅了同一个供稿的qq用户一起评论文章。还可以发到群,保存到记事本之类。而google则也是和自家的其他服务结合的较好,可以和阅读器中的好友分享评论等等。

两者支持rss的版本情况和atom的情况没有仔细调查,不过看来似乎两者都支持各种类型的供稿。

上面的只是些无关紧要的引子,我们再来看看深一点层次的异同吧。

根据使用上的经验,显然两者的数据库设计都是一样的,应该其他的在线阅读器也一样吧,毕竟没有多大的变化空间。

不过是4张表:(这里只是用关系型数据库来说明举例以方便理解,并不一定表示这两家用的就是关系型数据库)

【t_用户】1:多【t_用户订阅】多:1【t_供稿】1:多【t_供稿文章】

一个用户可以订阅多个供稿,多个用户订阅同一个供稿,一个供稿有多篇文章。

显然是当某个供稿在系统中第一次被订阅时,阅读器才初始化这个供稿并解析这个供稿xml中的文章(一般是该供稿最新的10到20篇文章,根据供稿源不同)并存放到数据库中。之后再有用户订阅同一个供稿时,阅读器只是把该供稿的订阅人数加一,然后从数据库把现成的文章取出来而已。

供稿的文章的更新也显然不和用户的刷新页面有关。后台安排一个机器人程序,定时遍历整个供稿库,一个一个去取最新的文章就行了。只不过是订阅者多的供稿,更新的频率高,反之频率就低一些而已。两个阅读器都会定时让页面刷新看看后台机器人有没有取到最新的文章,如果你等不及,自己手动刷一下也是一样的效果。

关于存储容量,从下面的两张截图来看,qq的一个供稿似乎只能保存1000篇文章(一页25篇一共40页),而google似乎是没有限制,至少可以保存2500篇以上的文章。毕竟比起海量存储能力,虽然腾讯也不差,但是应该没人比得过google了。据说google在全球有100万台以上的服务器:http://www.gizmodo.jp/2010/04/post_7005.html

qq:qq邮箱阅读空间的单个供稿最大保存文章1000篇

qq邮箱阅读空间的单个供稿最大保存文章1000篇

google:google reader的单个供稿似乎没有文章数上限

google reader的单个供稿似乎没有文章数上限



关于文章的发布时间,这里有两个时间需要说明。一个是文章的真实发布时间,一个是阅读器机器人获取到文章的时间。qq阅读器只能显示机器人获取到文章的时间,而无从知道文章的真实发布时间。google就不一样,虽然列表中显示的还是获取时间,但是只要将鼠标指针停留在获取时间上面,就能看到真实发布时间。

以下截图可以看出来发布时间的问题。

qq:最后一篇文章其实是2009年3月21日发布的

文章发布时间

google:将鼠标指针停留在获取时间上面,就会有显示发布时间和获取时间,不错。

文章发布时间

最后,qq提供了订阅分类的排序功能,可以手动调整各分类的上下位置。虽然看起来给分类下的各供稿也提供了该功能,但是到目前为止,点排序按钮除了页面闪一下,其他没有任何变化。看来是一个bug。

而google的供稿分类排序功能不好找,原来是直接上下拖动左侧供稿分类即可排序。而分类内部的各供稿是不能排序的。虽然可以上下拖动,但是一刷新就又恢复成按名称自动排序了。

注:原文发布在cnblogs,现在转一份放这里,有修改

使用Facebook社交插件参与评论:

windows系统下的文件夹链接功能mklink/linkd

vista及以上系统的mklink命令可以创建文件夹的链接(感觉像是文件夹的映射)。因为是从底层实现文件夹链接,所以这个链接是对应用程序透明的。

(windows 2000,xp,server 2003的相应功能是linkd,这里只说说mklink)
比如,我有一个文件夹叫C:\Program Files,但是c盘空间不多了,就想把一些应用程序转移到d盘,但是直接剪切过去肯定行不通,应用程序会报错,所以首先把C:\Program Files文件夹整个移动(剪切)到d盘,再执行命令:

mklink /j "C:\Program Files" "D:\Program Files"

这样c盘下面就会多出一个带快捷方式图标的文件夹,全称就是"C:\Program Files",双击进去其实就转到了D:\Program Files。

而C:\Program Files这个文件夹是对应用程序透明的,也就是说,除了windows自己,应用程序并不知道C:\Program Files下面的东西其实已经转移到d盘了,还当它们仍然在c盘。这样就不影响原来C:\Program Files下的应用程序的使用了。



1,上面建立的链接属于软链接(/j),还有符号链接(/d)和文件的硬链接(/h)。

符号链接和软链接大致相同,区别在于,软链接是绝对路径链接,而符号链接允许相对路径的链接。

比如,分别创建c:\data\tmp的符号链接c:\1和软链接c:\2,那么c:\1指向的就是同级文件夹下的data文件夹下的子文件夹tmp,而c:\2指向的是c:\data\tmp这样的绝对路径。影响就是,如果把c:\1和c:\2这两个文件夹移动到d盘,那d:\1的链接就失效了,而d:\2仍然有效。

文件的硬链接是对文件创建的链接,比如对c:\data\1.txt创建链接c:\data\2.txt,那么这两个文件就是同一个文件的两个等价别名了,相当于是指向同一个硬盘存储空间的两个指针,删除其中任何一个都不影响另一个文件。但是限制就是这种链接不能跨分区。

2,软链接和符号链接不能跨磁盘。

3,这个功能必须是在ntfs文件系统上才能使用。

4,这个功能在实际应用中非常好用,比如配合dropbox,可以很方便的同步任意文件夹。

注:原文发布在cnblogs,现在转一份放这里

使用Facebook社交插件参与评论:

mysql数据库删除列的默认值

ALTER TABLE `table1` CHANGE `column1` `column1` INT NOT NULL;


也就是把后面的【DEFAULT 0】去掉。
别说这个简单,我是google了半天才找到的。

注:原文发布在cnblogs,现在转一份放这里

使用Facebook社交插件参与评论:

2010年11月25日星期四

使用RSS阅读器订阅youku优酷视频更新以及专辑更新

本文介绍一下使用RSS阅读器(Google Reader,QQ阅读等)订阅优酷(youku.com)会员的最新视频以及专辑更新的方法。

前提1:优酷网自己提供的“订阅该会员视频”和“订阅本专辑”功能不方便
前提2:优酷网只公布了少数几个公共的RSS订阅地址【参看:http://www.youku.com/index/rss】,而并没有公布个人视频的RSS订阅方法。可能是优酷认为公布会影响网站的流量从而影响广告收入吧
前提3:以下所有操作都可以在浏览器中完成
前提4:本文写作日期2010/11/24,不排除将来优酷网修改式样的可能性

下面进入正题,以我的优酷视频空间为例:http://u.youku.com/plusium。进入想订阅的优酷会员空间,浏览器的地址栏的地址将类似这样(第一类):http://u.youku.com/user_show/uid_plusium或者这样(第二类):http://u.youku.com/user_show/id_UMjE5Mjk2NTQ0.html。如果是第一类地址,点击左上角的“首页”链接(在“我的视频”左边),那么地址将一定会变成第二类的地址。关注【id_】之后【.html】之前的这一段,是一个UMjE5Mjk2NTQ0这样的字符串。注意这个字符串一定是以U开头,而且可能以一个或多个=号结束。把首字母U去掉,剩下MjE5Mjk2NTQ0。这是一个BASE64编码后的字符串,你会发现这个字符串的长度肯定是4的倍数(=号就是用来凑数的)。打开在线解码网站http://tool.114la.com/base64.html,把这个字符串复制到下面的大输入框内点击“BASE64解密”,解出来的数字是219296544。接下来要对这个数字除以4。你可以心算,或者用计算器,或者打开google搜索引擎,输入219296544/4,得到结果54824136。接下来,打开Google Reader,订阅http://www.youku.com/user/rss/id/54824136,OK了~

会订阅最新视频了,那么订阅专辑就轻松了。打开想要订阅的专辑页面,比如http://www.youku.com/playlist_show/id_4587351.html。注意后面那段数字,那么RSS订阅地址就是http://www.youku.com/playlist/rss/id/4587351。优酷真偷懒,专辑id别说BASE64编码了,连乘以4都省了,就那么放在大庭广众之下了。

补充1:关于Google Reader的RSS抓取速度。快的话几分钟,慢的话几个小时。以我订阅的几个全世界只有我一个人订阅(在Google Reader中来说)的几个用户来说,平均一个小时就能收到了。有特殊需要想实时获得更新的话,就用离线RSS阅读器,然后每分钟去检查一下更新吧。
补充2:在线BASE64解码的替代方案,可以查看空间的网页源代码,然后在<head>部分找一个8位或以上的数字。这个数字直接是我们要用到的最终数字,应该就是优酷用于标识会员身份的会员id吧。

使用Facebook社交插件参与评论: