林健的BLOG

　　最近接触到一个 Windows 平台下的开源项目——pGINA。鉴于网上没有较为完整的中文介绍，特在此推介一下。
　　要知道 pGINA 做什么，首先需要了解 Windows 的用户管理框架。相关资料推荐阅读 Microsoft Windows Internals，这里不再赘述，只给出我列的一张 Linux 与 Windows 用户管理中的对应技术表格供熟悉 Linux 的开发人员参考。其实 Windows 也像 Linux 一样，开放了用户身份认证与用户管理系统的接口，允许第三方如同开发 Linux PAM/NSS 那样，为 Windows 开发新的认证入口（GINA）与认证包（Windows Authentication Packages）。

 
　　然而，我们能在网上找到的开源的 GINA 模块和认证包的相关资料远不如 PAM/NSS 丰富，找到的第三方实现几乎都是软硬件厂商用于接入自己基础设施的闭源专有软件（例如某些笔记本电脑的指纹认证）。这一方面可能出于微软商业风格与 Linux 开源风格的差异；而单从技术上看，微软“大而全”的 API 风格相比 Linux 的 KISS 风格对于简单的示例性或改进性开发无疑是一道壁垒。完整的 GINA 模块需要实现数十个接口，而系统中一次只能配置一个有效的 GINA，不像 PAM 那样可以通过配置文件灵活地组合使用只关注特定功能（认证、账户、密码或会话）的小模块。因此连微软自己的文档也告诫开发者，在编写新的 GINA 模块之前看看能不能用 Hook 之类偏 Hack 的技术实现自己所需的功能。
　　正是由于 GINA 开发的繁琐性，才蕴生了开源的 pGINA 框架。pGINA 本身是一个 GINA 模块，它提供了一致的图形界面，并将 GINA 的数十个接口二次抽象为几个简单易懂的接口（密码认证、密码修改、会话 Hook 等），允许二次开发人员利用这些接口开发插件，实现自定义的认证交互程序。pGINA 只适用于以密码作为认证凭证，在这一前提下，其功能可以涵盖 GINA 接口的主要功能点（认证管理、密码管理、屏幕锁定等），而且图形界面交互的开发也由必须变为可选。因此，使用 pGINA 将在很大程度上简化自定义用户认证机制的开发。对于最终用户，只需要安装 pGINA 并配置指定的插件，即可使用新的用户名/密码源取代 Windows 默认的 SAM 用户名/密码认证。
　　pGINA 的作者和其他志愿者已提供了十余种开源的 Windows 用户认证插件，例如基于既有 LDAP、MySQL、FTP、SSH 用户系统的认证，甚至基于 Slashdot 账号的认证等，可供开发者学习或修改。对于认证通过但在本地系统中尚不存在的用户，pGINA 的默认行为是为之自动创建新账户，这在一些公共计算机中比较有用。
　　pGINA 针对 Windows XP 的 1.X 版本代码已在 2006 年底稳定冻结，我测试多个插件（包括自己实验开发的插件）工作正常。而针对 Windows Vista 和 Windows 7 的 2.X 版本目前正在持续开发中（Alpha 阶段），我测试发现部分旧插件不能正确运行。
　　有关 pGINA 的 GINA 模块、插件、源代码和开发资源，可在其 SourceForge.net 页面下载。pGINA 给出了 M$ Style to KISS Style 的一个良好范例。

　　Marc Stevens 等人已经在破解 MD5 算法方面取得了不错的进展（见 http://www.win.tue.nl/hashclash/），他写出了两个输出不同字符串程序，它们的代码略有不同，但却拥有相同 MD5 值的。这显示了 MD5 算法的弱点。
　　即使搞不明白 Marc Stevens 高深的数学证明，我们也可以玩一些小把戏，让两个内容和 MD5 都完全相同的程序执行不同的操作。其实这里的猫腻就在于如何定义“完全相同”。文件有其内容（正文），也有元信息（文件名、日期、属性等）和物理位置等原始信息。一般定义的“完全相同”是指内容相同，MD5 等校验值也仅是针对内容计算的，与元信息、原始信息无关。但在程序中完全可以读取元信息和原始信息，根据它们的不同，让程序执行不同的操作。
　　通常元信息是容易修改的，用它玩这个把戏很容易被识破；原始信息难以自定义，也不便于移植。那用什么来玩呢？对！NTFS 文件系统有“流”（Stream）特性，可以给文件追加隐形的数据流。流本质上是一种自定义名称的元信息，与一般的元信息（甚至文件内容，这个名为“$DATA”的元信息）没什么区别，只是 Windows 默认不呈现给用户罢了。
　　由此，我写了一个小程序 StreamTricker，它在运行时读取自身可执行文件中名为“trick”的流，并将其内容显示出来。编译之后复制出 test-1.exe、test-2.exe 两个副本，使用命令行的 echo 命令给这两个文件追加不同的 trick 流，然后分别运行，就可以看到如图所示不同的输出。

发件人 blog

　　拿这两个程序忽悠别人：看看，MD5 是相同的；用 fc 命令对比一下，内容完全一致，但运行结果就是不一样！把文件改名、复制（当然别复制到 FAT 分区）也不影响效果。有人可能想去反汇编了，那干脆把程序加个壳吧。但了解 NTFS 流特性的朋友可能很快就能识破其中的猫腻了。
　　当然，也可以把不同的可执行代码放在流中，实现一些更有趣的功能。不过，已经有人利用流特性来隐藏病毒了，这些事实都警告我们不要轻信 MD5 等校验和。
　　StreamTricker 源代码与可执行文件下载：
　　http://files.linjian.org/c_cpp/StreamTricker.rar
　　http://www.linjian.cn/files/c_cpp/StreamTricker.rar
　　（WinRAR 支持 NTFS 流的压缩。如果使用 WinRAR 解压，可以保留流特性；用其它解压软件解开之后流特性有可能丢失，可以使用 echo 命令手工加入 trick 流测试）

程序与全文下载：
http://www.linjian.cn/files/dotNet/GestureStudy.rar
http://files.linjian.org/dotNet/GestureStudy.rar
程序基于Mat Buckland在《游戏编程中的人工智能》一书中例子的实现。

●问题陈述
　　本程序基于BP神经网络完成了对用户使用鼠标输入的特定手势的识别，并且可以学习用户创建的新手势。程序中已经存储的手势是Palm系列掌上电脑中手写识别专用的Graffiti字体的数字0～9，这种字体的特点是每个字由一个连续笔划构成，适合用一个连贯的鼠标手势表示：

图1 Graffiti字体的数字

●程序概述
　　本程序针对鼠标手势的存储、识别和学习功能，需要实现以下要素：
一、鼠标手势的表示
　　由于每个鼠标手势仅由一个连续笔划构成，因此可将这一笔划分解为一系列连续的向量。不同的手势对应不同的向量组合。为计算方便，所有向量可以归一化为单位长度向量，如图2示例：

图2 鼠标手势向量示例

　　分别以向右、向下为x轴、y轴正方向，则图2所示笔画的向量组合为(0,1)-(0,1)-(0,1)-(0,1)-(1,0)-(1,0)-(1,0)。
二、定义网络输入输出
　　使用BP神经网络，需要定义一组一维的输入向量与输出向量。将一个手势的笔划向量依次连接，x坐标、y坐标依次出现，即可构成该手势的输入向量。对于可以识别N种手势的神经网络，可以使用长度为N，第M位为1、其余各位均为0的向量作为第M种手势的标准输出向量。
　　上例对应的输入向量为(0,1,0,1,0,1,0,1,1,0,1,0,1,0)，输出向量形式为(0,…,0,1,0,…,0)。
三、训练神经网络
　　对于程序中已存储的手势，需要训练神经网络，使得网络对每个输入向量都能够产生误差在允许范围之内的输出向量。BP神经网络训练使用反向传播过程，即对每个输入向量重复以下步骤：
　　（1）将它送入网络，计算网络的输出o。
　　（2）计算输出o与目标输出t之间的误差。
　　（3）调整输出层权重，为每个隐藏层重复步骤（4）和（5）。
　　（4）计算隐藏层误差。
　　（5）调整隐藏层权重。
四、鼠标手势的记录
　　用户使用鼠标，在程序界面指定区域按下左键画出一个手势，程序定时记录鼠标坐标，构成一个点集（图3所示蓝点）。使用一定的算法对点集进行处理，取出比笔画的向量数目多一个的代表点（图3所示红圈），相邻两个代表点求差得到的向量经归一化即可得到笔画的向量组合。
取代表点的方法采用了光滑化算法，即对分布不均的原始记录点找到其中跨度最小的两个点，用它们的中点取代它们。重复执行，直到点的数目符合向量数目要求。

图3 鼠标手势记录示例

五、鼠标手势的识别
　　用户的输入不可能与定义的标准输入完全一致。将待测试的手势对应的输入向量输入训练过的神经网络后，网络的输出与定义的第M种手势的标准输出向量越接近，说明输入手势越接近第M种手势的标准输入。评判“接近”的简单标准是找出输出向量中最大（最接近1）的元素，认为输入最有可能是该位为1的输出对应的手势。
六、鼠标手势的学习
　　学习过程是将用户新输入的一个手势构建输入向量，加入原有的输入向量集；对输出向量的长度加一，设置其对应的输出向量，然后将网络重新训练一遍。

●程序架构
　　本程序使用Visual Studio 2005（C#语言）开发，基于.Net Framework 2.0运行。
一、关键数据结构
　　程序包含的类如下：

图4 程序类图

　　（1）Neuron类（神经元）：记录一个神经元的输入数目、各个输入的权重、偏差值等数据。
　　（2）NeuronLayer类（神经网络层）：记录一个神经网络层的神经元数目和各个神经元对象。
　　（3）NeuralNet类（神经网络）：记录一个BP神经网络的各个神经网络层以及隐藏层数、学习率、训练与否等信息；提供训练、更新等方法。
　　（4）GestureData类（鼠标手势）：记录所有鼠标手势的名称、笔划向量组合、对应输出等信息；提供追加新鼠标手势等方法。
二、程序界面操作说明

图5 程序界面

　　（1）程序运行后，首先需要训练神经网络。用户可以设置网络的一些参数，包括学习率、可允许的偏差门限、隐藏层数等。此外可以选择开启带动量的算法或带噪声的算法，并设置动量分数和噪声最大值。单击“Train Network”按钮开始训练网络，界面左下方显示当前训练的迭代数和偏差。
　　（2）训练之后，在绘图区域按下鼠标左键画出一个连续的手势，程序会将代表点标注在手势上，并在界面左下方给出通过神经网络运算得到的最佳匹配输出值与对应手势的名称，用卡通图标显示最佳匹配输出值的大小。
　　（3）单击“Learn New Gesture”按钮，程序进入学习状态。此时用户可以输入一个新的手势，并在弹出的对话框中为之命名。程序随即重新训练神经网络。
　　（4）单击“Clear Pad”按钮清空绘图区域。

●参考文献
[1] Mat Buckland．游戏编程中的人工智能，北京：清华大学出版社，2006．
[2] 朱大奇，史慧．人工神经网络原理及应用，北京：科学出版社，2006．