为CentOS 6.5更换3.14版本的Kernel

前阵子由于项目需要,将CentOS的Kernel从2.6换成了最新的3.14,现在把步骤记录下来,免得以后忘记。

1.下载Linux Kernel
首先去网站 https://www.kernel.org/ 下载最新的内核源码,命令为:wget https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.14.tar.xz

2.解压Kernel压缩包
tar -Jxvf ./linux-3.14.tar.xz

3.安装更换Kernel所需的软件
yum install gcc gcc-g++ ncurses-devel

4.切换到源码目录,清除之前编译的文件
cd ./linux-3.14
make distclean

5.复制已有配置文件至源码目录
cp /boot/config-2.6.32-431.el6.x86_64 .config

6.配置.config文件
make menuconfig
在进入的配置程序中,选择【Load】,确定;再选择【Save】;最后退出【Exit】。
lc-1

7.修改.config文件
vim ./.config
找到关键字“CONFIG_SYSFS_DEPRECATED”这一行,将其改成“CONFIG_SYSFS_DEPRECATED_V2=y

8.编译内核
make all

9.编译内核模块
make modules_install

10.安装
make install

11.修改grub文件,选择新内核启动
vim /boot/grub/grub.conf
将“default=”的数字改成新内核的序号即可。

12.重启系统

Java中Sring类的Hash冲突攻击实践

最近开始学Java,就顺便研究了下Java下的哈希冲突攻击,发现它的String类存在明显可用的攻击方法,就干脆测试了一下,下面简单介绍一下。

Hash冲突的原理其实很简单,当使用Hash表实现的集合来存储元素时(如Java的HashSet、HashMap,C++的unordered_set、unordered_map等),不必可免的会造成多个元素的Hash值相同,即出现冲突,当发生冲突时,有多种方法来进行处理,如线性探测再散列、二次探测再散列、再哈希和链地址法等等。其中用的最多的处理方法是链地址法,如图1所示。

1

链地址法将Hash值相同的元素用链表连接起来。至于为什么这种冲突处理方法用的最多,设装填因子a=哈希表已有元素数/哈希表长度,则每次查找成功时,平均查找长度如下:

pic3

画下函数图像可以发现链地址法的平均查找长度是最小的。

使用Hash表作为存储元素的集合时,必须用到Hash函数,我们希望Hash函数能将各个元素哈希后的值分布尽可能均匀,这样查找速度才快,而Hash冲突攻击的原理就是根据Hash函数,构造大量具有相同Hash值的元素,将其插入至表中,使得Hash表最终退化成一个单链表。

collision

而Java中的String类的hashcode函数写得十分简单,它的计算公式为(其中s即为字符串):

gs

这个函数实际上就是BKDR Hash函数,其中的因子31也可以换成13,131等等……

但对于这种Hash函数,可以使用“相等子串法”来构造哈希值相同的大量元素。使用“相等子串法”的Hash函数必须满足如下条件:若两个不同字符串的哈希值相同,即有f(str1) == f(str2),则必有f(prefix + str1 + suffix) == f(prefix + str2 + suffix),即在str1和str2的前后放置相同的字符串后,所得新的两个字符串的哈希值仍然相等。而BKDR Hash就满足这种性质。

例如“Af”和“BG”哈希值相同,则有“AfAf”,“AfBG”,“BGAf”,“BGBG”的哈希值也相同。

下面这段代码是演示String类的Hash冲突,其生成了2^18个具有相同Hash值的字符串,并将其依次拷贝到ArrayList,TreeSet和HashSet集合中,理论上若元素随机的话,应该速度顺序是ArrayList > HashSet > TreeSet,但由于Hash冲突,实际拷贝时三者的时间复杂度会变成O(n),O(nlogn)和O(n^2),即HashSet变成最慢。

我这的测试环境为:CPU i5 4570,内存8G,Win7 x64,JDK7u45,IntelliJ IDEA 13。

测试结果为:ArrayList耗时1ms,TreeSet为121ms,而HashSet则需604071ms。Hash冲突攻击成功。

测试代码如下所示(初写Java,请无视我写得太渣吧…)。

public class Demo {
    public static void main(String[] args) {
        ArrayList<String> arrRet = new ArrayList<String>();
        StrCollide col = new StrCollide();
        col.Generate(arrRet, 18);

        // 测试速度
        Date begTime = new Date();
        ArrayList<String> ArrCandidate = new ArrayList<String>(arrRet);
        Date endTime = new Date();
        System.out.println("The Time of ArrayList insertion is : " + (endTime.getTime() - begTime.getTime()));

        begTime = new Date();
        TreeSet<String> TreeCandidate = new TreeSet<String>(arrRet);
        endTime = new Date();
        System.out.println("The Time of TreeSet insertion is : " + (endTime.getTime() - begTime.getTime()));

        begTime = new Date();
        HashSet<String> HashCandidate = new HashSet<String>(arrRet);
        endTime = new Date();
        System.out.println("The Time of HashSet insertion is : " + (endTime.getTime() - begTime.getTime()));
    }
}

class StrCollide {
    /**
     * @param Set 存储具有相同HashCode值的String变量
     * @param n   集合内元素个数,单位为幂
     * @return 操作是否成功
     * @description 为String变量构造Hash冲突,并将结果存储在集合中
     **/
    public boolean Generate(Collection<String> Set, int n) {
        if (Set == null || n < 1)
            return false;

        // 寻找两个Hash值相同的String
        Set.clear();
        ArrayList<String> ArrPair = FindColPair();
        if (ArrPair != null && ArrPair.size() >= 2) {
            for(int iNum = 0; iNum < Math.pow(2, n); ++iNum) {
                String strTmp = Integer.toBinaryString(iNum);
                strTmp = String.format("%0" + n + "d", new BigInteger(strTmp, 10));
                strTmp = strTmp.replaceAll("0", ArrPair.get(0));
                strTmp = strTmp.replaceAll("1", ArrPair.get(1));
                Set.add(strTmp);
            }
            return true;
        }
        return false;
    }

    /**
     * description 寻找最初的两个Hash值相同的String变量 *
     * @return 存储这两个String的集合
     **/
    private ArrayList<String> FindColPair() {
        ArrayList<String> ArrRet = new ArrayList<String>();
        HashMap<Integer, String> mapTmp_ori = new HashMap<Integer, String>();
        HashMap<Integer, String> mapTmp_add = new HashMap<Integer, String>();
        mapTmp_ori.put(0, "");
        while (true) {
            // 遍历源集合
            mapTmp_add.clear();
            mapTmp_add.putAll(mapTmp_ori);
            for(Map.Entry<Integer, String> elem : mapTmp_ori.entrySet()) {
                for(char ch = 48; ch <= 122; ++ch) {
                    // 48-122是数字到字母的ASCII码范围
                    if(Character.isLetter(ch)) {
                        String strTmp = ch + elem.getValue();
                        int hCode = strTmp.hashCode();
                        if(mapTmp_add.get(hCode) != null && !mapTmp_add.get(hCode).equals(strTmp)) {
                            // 找到Hash值相同的两个String
                            ArrRet.add(strTmp);
                            ArrRet.add(mapTmp_add.get(hCode));
                            return ArrRet;
                        } mapTmp_add.put(hCode, strTmp);
                    }
                }
            }
            mapTmp_add.remove(0);
            // 交换两个集合
            HashMap<Integer, String> tmp = mapTmp_ori;
            mapTmp_ori = mapTmp_add;
            mapTmp_add = tmp;
        }
    }
}

C++笔记(1):了解new-handler的行为

在C++里面,内存分配与释放是C++最具有魅力又不容易掌握的特色之一,其具体代码如下:

// 分配
int* i = new int;

// 释放
delete i;

但在使用new分配内存时,有可能会出现因内存空间不足而导致无法分配的情况,出现这种情况时,不同的C++编译器有两种处理方法:

在最老式的C++标准中,当new无法分配足够的内存时,将会返回null,但这种编译器现在几乎已经用不到了;目前的编译器对于这种情况则是会抛出std::bad_alloc异常,交由上层处理。但老式的处理方式也不是不能使用,通过声明“nothrow形式”,可以强行使用老式处理方法,代码如下:

// 声明使用nothrow,不推荐
int* i = new (std::nothrow) int;

但这种方法并不推荐,因为虽然new (std::nothrow) int调用的new并不抛出异常,但int构造函数却可能会。如果出现这种情况,该异常一样会传播出去,因此使用nothrow new只能保证new不抛出异常,但不保证像new (std::nothrow) int这样的表达式绝不抛异常。

但这不是重点。

当new抛出异常以反映一个未获满足的内存需求之前,它会先调用一个客户指定的错误处理函数,即new-handler函数来进行一些处理。该函数无参数,无返回值,可以通过使用std::set_new_handler(new_handler p)来设置它,代码如下:

// new-handler函数的类型定义
typedef void (*new_handler) ();

// 设置new-handler的函数
new_handler std::set_new_handler(new_handler p) throw();

下面是使用的例子:

// new-handler函数
void PrintError()
{
	cout<<"new is Error!"<<endl;
}

int main()
{
	set_new_handler(PrintError);
	int* p = new int[0x7fffffff];
}

值得注意的是,当new无法满足内存申请时,它会不断调用new-handler函数,直到找到足够的内存为止。

再进一步。

大多数时候,直接使用set_new_handler设置new-handler函数,来处理所有new分配失败的情况,并不符合自己的需求。而是希望能根据申请内存空间的类的不同,而赋予不同的new-handler,而对其它类,则使用默认的new-handler函数。例如:

// 失败则调用X的new-handler
X* p1 = new X;

// 失败则调用Y的new-handler
Y* p2 = new Y;

// 失败则使用默认new-handler
int* p3 = new int;

此时可以使用如下代码来解决:

using namespace std;

// 资源管理类
class NewHandleHolder{
public:
	explicit NewHandleHolder(new_handler nh):handle(nh){}
	~NewHandleHolder(){set_new_handler(handle);}
private:
	new_handler handle;
	// 私有化拷贝构造函数,赋值函数,以阻止拷贝
	NewHandleHolder(const NewHandleHolder&);
	NewHandleHolder& operator=(const NewHandleHolder&);
};

// 为特定类设定专属new_handler的模板类
template<typename T>
class NewHandleSupport{
public:
	static new_handler set_new_handler(new_handler p) throw();
	static void* operator new(size_t size) throw(bad_alloc);
	static void* operator new[](size_t size) throw(bad_alloc);
private:
	static new_handler currentHandle;
};

template<typename T>
new_handler NewHandleSupport<T>::set_new_handler(new_handler p) throw()
{
	new_handler OldHandle = currentHandle;
	currentHandle = p;
	return OldHandle;
}

template<typename T>
void* NewHandleSupport<T>::operator new(size_t size) throw(bad_alloc)
{
	NewHandleHolder h(::set_new_handler(currentHandle));
	return ::operator new(size);
}

template<typename T>
void* NewHandleSupport<T>::operator new[](size_t size) throw(bad_alloc)
{
	NewHandleHolder h(::set_new_handler(currentHandle));
	return ::operator new(size);
}

template<typename T>
new_handler NewHandleSupport<T>::currentHandle = 0;

// 测试类1,只需继承NewHandleSupport即可拥有专属new_handler
class Widget_1:public NewHandleSupport<Widget_1>{

};

// 测试类2,只需继承NewHandleSupport即可拥有专属new_handler
class Widget_2:public NewHandleSupport<Widget_2>{
	char c[0x7fffffff];
};

// 测试用函数1
void Widget_1_Error()
{
	cout<<"The Widget_1 class is Error!"<<endl;
}

// 测试用函数2
void Widget_2_Error()
{
	cout<<"The Widget_2 class is Error!"<<endl;
}

int main()
{
	// 测试类的使用
	Widget_1::set_new_handler(Widget_1_Error);
	Widget_2::set_new_handler(Widget_2_Error);

	// 分配成功
	int* i = new (nothrow) int;
	delete i;

	// 分配错误1
	Widget_1* w = new Widget_1[0x7fffffff];

	// 分配错误2
	Widget_2* w = new Widget_2;

	system("pause");
	return 0;
}

在该解决方法中,使用NewHandlerHolder类作为资源管理类,其功能仅作为保存new_handler变量,且在构造时保存,在析构时再将保存的new_handler还原回去。

而NewHandlerSupport则作为所有想要设置自己专属new-handler的类的基类而被使用。由于该类是模板,因此会根据不同的子类而实例化。它的功能是重载系统的set_new_handler、new和new[]函数,当实例化的类使用该三种函数时,执行自定义的操作。

Windows驱动开发笔记(二)——键盘过滤

本驱动主要是可以过滤键盘的按键信息并修改,其原理大致为:

1.使用ObReferenceObjectByName(…)打开键盘驱动Kbdclass;

2.依次遍历Kbdclass驱动下的所有设备,用IoAttachDeviceToDeviceStack(…)为每个实际设备绑定过滤设备对象;

3.设置各种IRP请求分发函数,主要是IRP_MJ_READ的分发函数较为特殊——如果该驱动已经是最底层,则直接用IoCompleteRequest(…)表示该IRP请求完成;否则IoSetCompletionRoutine(…)设置完成函数;

4.编写IRP_MJ_READ的完成函数,主要功能就是输出该IRP请求的键盘按键信息,如有需要还可以更改。

5.编写入口函数DriverEntry(…),内容就是设置各种分发函数,卸载驱动函数,并绑定所有过滤设备。

具体源码参见附件,建议在虚拟机下安装调试,用DebugView来看按键信息。

点击下载

Windows驱动开发笔记(一)——串口过滤

最近在学Windows驱动开发,感觉还是蛮有意思的,主要是驱动能做到许多在应用层面完成不了的功能~

附件是对计算机各个串口进行过滤的驱动源码,其大概流程如下:

1.使用IoGetDeviceObjectPointer(…)函数由物品设备名获得其设备对象的指针;

2.使用IoCreateDevice(…)创建一个用于过滤的设备对象,并将它的各个属性赋值为跟真实设备相同的属性;

3.使用IoAttachDeviceToDeviceStack(…)将过滤设备对象与真实设备对象绑定,并返回指向下一个设备对象的指针;

4.编写分发函数,大概内容为:先用IoGetCurrentIrpStackLocation(irp)获得IRP栈地址,然后若为IRP_MJ_POWER请求用PoStartNextPowerIrp(…)、IoSkipCurrentIrpStackLocation(irp)和PoCallDriver(…)下发。其它请求则用IoSkipCurrentIrpStackLocation(irp)和IoCallDriver(…)直接下发。当为IRP_MJ_WRITE请求时,用MmGetSystemAddressForMdlSafe(…)函数或直接从irp->UserBuffer或irp->AssociatedIrp.SystemBuffer中获得其写串口的数据,最后打印输出;

5.编写驱动卸载函数,大概内容为:用IoDetachDevice(…)解除所有下一个设备对象的引用,用IoDeleteDevice(…)删除所有过滤设备对象;

6.编写驱动入门函数DriverEntry(PDRIVER_OBJECT driver, PUNICODE_STRING reg_path),内容为用driver->MajorFunction[i] = ccpDispatch设置分发函数,设置驱动卸载函数,最后绑定所有串口,返回成功状态。

其具体源码可参加附件,且XP版本的驱动已经编译好,建议在虚拟机下调试。

点击下载

RDP协议格式详解

前段时间由于项目需要,对RDP协议做了一点点调研,现在将调研的结果汇总整理成了一份PDF文档公布出来,如果有需要的话可以供大家参考。RDP协议格式其实网上也有,但是跟我实际抓包的区别较大,这个协议文档是根据最新实际抓包分析总结来的,应该还算有参考价值吧。

注:RDP(Remote Desktop Protocol,远程桌面协议)是Windows操作系统的远程桌面服务所使用的应用层协议,可以提供客户端远程控制服务器的服务,其服务器默认采用3389端口。

阅读文档