Amyangfei's Blog

系统环境Mac OS X 10.8.2，这个博客主要通过jekyll生成静态页面，使用ruby提供的一些扩展插件，比如按月份进行归档等，配置环境的过程如下。

安装ruby，rubygems

1
2
3
4

sudo port ruby
sudo port install rb-rubygems
sudo gem install rubygems-update
sudo gem update --system

安装bundle

1

sudo gem install bundler

前几天看了酷壳上的一篇文章如何测试洗牌程序，之后仔细看了Wikipedia对Fisher–Yates shuffle算法的介绍，这里简单的总结一下，基本是翻译Wikipedia。

Fisher and Yates’ original method

该算法最初是1938年由Ronald A. Fisher和Frank Yates在《Statistical tables for biological, agricultural and medical research》一书中描述，算法生成1-N个数的随机排列的过程如下：

1. 原始数组中有数字1到N
2. 设原始数组未被标记的数字个数为k，生成一个1到k之间的随机数
3. 取出原始数组未被标记数字中的第k个，将其标记并插入到新的排列数组尾端。
4. 重复过程2直到原始数组中没有未被标记的数字
5. 过程3中生成的新数组就是一个对原始数组的随机排列

该算法可以理解为已知有n个元素，先从n个元素中任选一个，放入新空间的第一个位置，然后再从剩下的n-1个元素中任选一个，放入第二个位置，依此类推。算法在过程3查找未被标记的第k个数字有很多重复操作，导致算法效率并不高，总的时间复杂度为O(N^2 )，空间复杂度为O(N)。算法的python实现如下所示：

背景

最近在做的数据库活动检测引擎，要实现一个异常行为检测的模块。简单的说异常行为检测就是先确定描述用户访问数据库的行为模型，然后定义一系列描述正常访问数据库的行为，检测过程中一旦用户行为与正常行为轮廓不符，则被认定为攻击行为。在实际系统中，正常行为轮廓会组成正常行为知识库，这个知识库会很大，所以正常行为轮廓不能简单的人工定义，于是一个自动挖掘正常行为知识库的需求被提了出来。

在系统实现过程中，会将用户对数据库产生影响的原子性操作，比如一次select，一次update抽象成为一个item，用户访问数据库的一系列行为可以抽象成为一个item的序列，由此引出了通过频繁序列挖掘来获得正常行为知识库的想法。

频繁序列挖掘

似乎应该在这里说些什么。。。