基于AdaBoost的文本隐写分析.doc

2007 年 12 月Journal on CommunicationsDecember 2007 第 28 卷第 12 期通 信 学 报Vol 28 No 12 基于 AdaBoost 的文本隐写分析 眭新光 沈蕾 燕继坤 朱中梁 信号盲处理国家重点实验室 四川 成都 610041 摘 要 通过对自然文本统计模型和特性的分析 指出隐藏消息后可能对文本统计特性带来的变化 并提出了 基于 AdaBoost 的通用检测算法 抽取文本的 5 个基本统计特征量为分类特征 对自然文本和载密文本进行有效 分类检测 实验证明该算法具有较好的适用性和可靠性 关键词 隐写分析 文本 统计特征量 AdaBoost 中图分类号 TP391 文献标识码 B 文章编号 1000 436X 2007 12 0136 05 Text steganalysis using AdaBoost SUI Xin guang SHEN Lei YAN Ji kun ZHU Zhong liang National Key Lab of Blind Signals Processing Chengdu 610041 China Abstract The statistical models and features of natural texts was analyzed and it was pointed out that embedding messages in texts will change the features of them According to the changes a blind detecting method was designed using AdaBoost Five basic parameters of texts was extracted as distinguished feature vectors to discriminate natural texts and stego texts effectively using AdaBoost Experimental results show the high accuracy and reliability of the method Key words steganalysis text statistical features AdaBoost 1 引言 隐写分析是判断一个载体 如文本 图像 中是 否隐藏有信息 是信息隐藏技术的逆向分析过程 在近年来已经成为信息隐藏技术领域的一个研究 热点 目前提出的各种隐写分析方法主要有通用 隐写分析算法和针对特定隐藏算法或工具的隐写 分析算法 有针对性的隐写分析算法虽然具有较 好的性能 1 3 但是由于其适用面窄 通用性差 具有一定的局限性 而通用的隐写分析方法不需 要对隐藏算法有先验知识 不依赖于具体的隐藏 算法 因而对未知的算法具有很强的适应性 也 是隐写分析算法发展的趋势 目前 在通用的隐 写分析方面已经提出了许多有代表性的方法 4 7 机器学习中的 boosting 算法目标是提高任何 给定的学习算法的分类准确率 概括地说 此方 法依次训练一组分量分类器 其中每个分量分类 器的训练集都选择已有的其他各个分类器所给出 的 最富信息 most informative 样本 而最终的 判决结果则是根据这些分量分类器的结果共同决 定 AdaBoost adaptive boosting 是 boosting 家 族最具代表性的一系列算法 在 AdaBoost 方法中 每一个训练样本都被赋予一个权重 通过这样的 方式 AdaBoost 方法 聚焦于 那些较困难 更富 信息 的样本上 对许多实际的应用 AdaBoost 方法被证明是非常有效的 8 本文把 AdaBoost 引入文本隐写分析 从机器 学习的角度来分析隐藏信息的检测问题 文章从 分析自然文本 指自然英文文本 下同 的统计 模型和自然属性入手 提取出在信息隐藏过程中 可能被修改的统计特征来对分类器进行训练 获 得分类器的模型参数 并以此来对未知文本进行 收稿日期 2007 09 03 修回日期 2007 11 07 第 12 期眭新光等 基于 AdaBoost 的文本隐写分析 137 检测 该方法操作性强 稳定可靠 并通过实验 验证了算法的有效性 2 文本统计模型与特性分析 由于自然文本中可以有许多种语言 而每种 语言的自然文本具有不同的特点 要建立能适用 于各种语言的自然文本的精确模型是很困难的 实际上 即使对单一语言的自然文本 也很难建 立一个精确的模型 现有的模型一般都是针对某 一方面的需求或者根据文本的某个特点而建立的 能从某个角度来对文本做比较细致的解析 而难 以从所有方面对文本都有精确的分析 2 1 马尔可夫 Markovian 模型与字母分布 在文本中用得比较多的是马尔可夫 Markovian 模型 马尔可夫模型认为 自然语 言中一个符号对先前的符号有某种依赖性 一个 符号是由先前一个或者更多的符号决定的 9 即 1 1211 nnnnnn k P ttttP ttt 其中 ti为文本中第 i 个字符 若把这里的符号理 解为单词 显然单词也遵循这样的模型 自然文本的符号不是均匀分布的 各个字符 不是随机出现 而是具有稳定的概率 例如 在 英语中 通过对大量自然文本的统计 各个字母 的出现概率如表 1 所示 10 表 1自然英文文本的字母统计概率 字母频率字母频率字母频率 E T A O I N S R H 0 126 8 0 097 8 0 078 8 0 077 6 0 070 7 0 070 6 0 063 4 0 059 4 0 057 3 L D U C F M W Y G 0 039 4 0 038 9 0 028 0 0 026 8 0 025 6 0 024 4 0 021 4 0 020 2 0 018 7 P B V K X J Q Z 0 018 6 0 015 6 0 010 2 0 006 0 0 001 6 0 001 0 0 000 9 0 000 6 其中 字母 E 出现的频率最高 高达 0 126 8 而字母 Z 的出现频率最低 只有 0 000 6 对自 然文本来说 其字符出现的概率跟上表所列非常 接近 这种接近程度可以用相似度来描述 设 f1 i f2 i 为 2 个概率分布 i 1 2 26 分别对应 A B Z 则 f1 i f2 i 的 相似度定义为 2 26 1 21 26 1 21 26 1 21 2 1 1 1 i i i ifif ifif ifif 2 个概率分布越接近 则相似度越大 完全一 样时相似度为 1 反之 2 个概率分布差异越大 相似度越小 自然文本的字符分布与上述参考频 率分布的相似度是很高的 当对文本词汇进行某 些修改后 这种相似度必然会发生改变 而且修 改越大 相似度变化也越大 2 2 Zipf 齐夫 分布模型与单词分布 在自然文本中 符号不是均匀分布的 Zipf 齐夫 分布模型 9 认为 排在最频繁出现的单 词第 i 位的词频是排在第一位的词频的 1 i 为 阶数 倍 这表明 设有 n 个单词的文本 且其 中包含 V 个单词的词汇表 排在最频繁出现的单 词第 i 位的词频值是 n i Hv 其中 Hv 定义如 下 3 v j v j H 1 1 因此 所有单词的出现次数之和为 n 文本中 单词按频率降序排列时的频率分布如图 1 所示 图 1 排序的词频分布 统计发现 自然文本中 频繁出现 出现次 数高于 3 次 的单词占整个文本单词的比例普遍 在 15 以上 经常是少数的几个单词占整个文本 单词数量的 50 以上 而且文本越长这个比例也 越大 但在某些隐密文本中 如构造法生成的文 本 这个比例就要小很多 还有一个特性是文本单词首字母频率分布 设一个英文文本的单词从某指定字典 通常大于 该文本的词汇表 中取得 该字典以单词的首字 138 通 信 学 报第 28 卷 母为依据 划分为 A B Z 共 26 个区间 每个区 间的长度 即单词数量 用 L1 i 表示 频率用 f1 i 表 示 而该英文文本每个区间的长度用 L2 i 表示 频率用 f2 i 表示 其中 i 1 2 26 分别对应 A B Z 图示如图 2 所示 A B C X Y Z a 字典各区间频率分布模型 A B C X Y Z b 文本单词首字母各区间频率分布模型 图 2 字典与文本单词首字母区间频率分布模型 对于一个上下文无关文本模型 单词的出现 是随机的 那么首字母落在哪个区间的概率只取 决于这个区间的长度 或单词数量 如果以字典 各个区间的频率 单词数 总单词数 分布 f1 i 为 参考 那么上下文无关文本的首字母的频率分布 跟 f1 i 的分布非常接近 而对于自然英文文本 由于单词的出现是一 个 n 阶 n 0 马尔可夫模型 因而不是随机的 从 单词的首字母看 也就是落在 A Z 哪个区间不是 随机的 由于单词分布的不均匀性 首字母的分 布也是不均匀的 即单词首字母的频率分布跟字 典的参考频率分布 f1 i 差异很大 这用 Zipf 齐夫 分布模型也可以得到类似的结 论 由于自然文本中少量单词的频繁出现 必然 会导致这些高频次出现的单词所在区间的比率升 高 相应地 其它区间的频率降低 2 3 Heaps 定律与单词平均长度及空字符率 Heaps 定律 9 认为 词汇表中单词的长度增长 与文本的大小成对数关系 因此 文本越长就会 出现越长的单词 但是在整个文本中 因为短词 如停用词 出现的次数也相应地增多 由 Zipf 分布模型可以得到 所以单词的平均长度是一个 常数 长词和短词相平衡 使单词的平均长度为 常数 在统计上也可以得到类似的结论 在自然英文文本中 由于出现频次高的多数 是一些短词 使得文本单词的平均长度比较小 如果只考虑文本词汇表中的单词 则平均长度将 增大许多 这用 Zipf 齐夫 分布模型可以解释为 由于自然文本中少量短单词的频繁出现 导致文 本单词的平均长度低于词汇表单词的平均长度 所以对自然文本而言 文本单词平均长度与词汇 表单词的平均长度的比值通常都远小于 1 在某些 隐密文本中 频繁出现的单词比例比较小的时候 这个比例就接近 1 根据 Heaps 定律还可以得到自然文本中空字 符率 空字符的比率 的结论 即 1 空字符的 概率接近于 0 2 2 空字符不能连续出现两次或多 次 当通过空格隐藏法在文本中嵌入空字符后 空字符率将不可避免地要变大 设原文本大小为 T 字节 空字符数量为 s 嵌入空字符数量为 S 则空字符率 Rs S s T S S T s T 1 S T b 1 4 其中 是嵌入率 b 是原始文本中的空字符率 对一个给定的文本而言 那么 Rs随 呈次线性变 化 其变化关系如图 3 所示 当嵌入率 逐渐增大时 空字符率 Rs也持续 增大 并逐渐逼近 1 0 因而空字符率在一定程度 上可以反映出嵌入的信息量 图 3 空字符率随空字符数量的变化关系 3 隐写分析算法 从统计的角度看 对于某种媒体形式的载体 数据而言 加入秘密信息后 数据质量和统计规 律一般总会有所改变 其免疫能力与所隐藏的秘 密信息的数据量也有一定的关系 在自然载体中 某些统计参数对于不同的压缩类型 文件格式具 有特定的变化范围 而大多数信息伪装算法都不 可避免地要改变载体的某些统计特征 对于自然 文本而言 嵌入秘密消息后 同样会导致文本统 计特征的改变 关于自然文本的常见统计特征变 化范围及嵌入消息后对特征的影响 请参见文献 11 由于嵌入消息后会改变文本的统计特征 因 第 12 期眭新光等 基于 AdaBoost 的文本隐写分析 139 此如果提取出文本的统计特征参数作为特征向量 通过一定量的隐密文本和自然文本对分类器进行 训练 就可能实现对自然文本和载密文本的成功 分类 3 1 统计特征提取 通过第 2 节的分析可以知道 对于自然文本 而言 其字母分布 词频分布 空字符率 文本 单词平均长度与词汇表单词平均长度 首字母分 布都有一定的变化范围 嵌入消息后 其中某些 分布特征将会发生改变 本文提取如下几个特征 来对分类器进行训练 空字符率 文本中频繁出 现 3 次以上 单词占文本单词总数的比值 文本 单词平均长度与文本词汇表平均单词长度的比值 文本单词首字母分布与词汇表词汇分布的相似度 文本字母分布与参考频率分布的相似度 3 2 分类器选择与设计 Kearns 和 Valiant 指出 8 在PAC 学习模型中 12 若存在一个多项式级的学习算法来识别一组概念 并且识别正确率很高 那么这组概念是强可学习 的 而如果学习算法识别一组概念的正确率仅比 随机猜测略好 那么这组概念是弱可学习的 Kearns 和 Valiant 提出了弱学习算法与强学习算法 的等价性问题 即是否可以将弱学习算法提升成 强学习算法 如果两者等价 那么在学习概念时 只要找到一个比随机猜测略好的弱学习算法 就 可以将其提升为强学习算法 而不必直接去找通 常情况下很难获得的强学习算法 1990 年 Schapire 通过一个构造性方法对该 问题作出了肯定的证明 13 其构造过程就是最初 的 Boosting 算法 1999 年 Schapire 和 Singer 提出 了 AdaBoost 更一般的形式 14 并引入 自信率预 测 以改善 Boosting 的性能 本文提到的 AdaBoost 就是这种算法 算法 1 给出了 AdaBoost 的执行过程 AdaBoost 给每个训练实例维持着一个权值 以级 联的方式训练多轮 用被增强的弱学习算法训练出 基分类器 每一轮中由训练实例及相应的权值向量 训练出一个基分类器 再根据该基分类器对每个实 例分类的结果调整其权值 增加错分实例的权值 这样迫使下一轮训练出的基分类器更关注于当前基 分类器失败的实例 AdaBoost 按照基分类器在训练 集上的错误率分配权值 用加权投票法进行综合 算法 1 AdaBoost Schapire 初始化 m kD 1 1 For t 1 T 执行以下两步 1 用分布 Dt训练出一个弱分类器 t h 2 选择 t t t r r 1 1 ln 2 1 其中 m k kkttt yxhkDr 1 3 更新 t D为 t ktktt t Z xhykD kD exp 1 其中 Zt为归一化因子 k ktkttt xhykDZ exp 最后得到的分类器为 其中 sign H xf x T t tt xhxf 1 Schapire 和 Singer 给出了 AdaBoost 训练错误 率的界 14 5 1 1 T iit t i H xyZ m 并进一步证明了 AdaBoost 的期望错误率最多 为 15 6 Td P H xyO m 其中 表示对训练集的经验概率 d 为弱学习 P 算法的 VC 维 该公式表明若训练轮数过多 AdaBoost 将发 生过匹配 但大量的试验表明 AdaBoost 即使训练 几千轮后仍不会发生过配现象 而且 AdaBoost 在 训练错误率达到零后仍会继续降低泛化误差 实验选取的弱学习器为k 近邻 KNN k nearest neighbor 算法 k 取 5 训练轮数为 200 轮 4 实验结果与分析 4 1 训练和测试样本 实验中 使用 100 个随机选择的自然文本 包括政治 经济 军事 体育 新闻 科技 140 通 信 学 报第 28 卷 文化 娱乐 社会生活及小说等各个方面 其中 单词最少的文本有 175 个单词 而单词最多的文 本有 130 263 个单词 500 个单词以下的文本占 50 1 000 个单词以上的文本占 15 以及通过 SNOW 隐藏工具嵌入了不同信息量的隐密文本 10 个 15 嵌入量各 4 个 40 嵌入率 6 个 其中嵌 入量与隐藏信息量不是相等的关系 它们间有一 个比例因子 stego 工具的隐密文本 8 个 实验中用的测试文本为随机选择的 47 个自然 文本和 305 个隐密文本 通过空格法隐藏消息的 隐密文本所使用的载体文本是从训练数据中随机 选择的 50 个自然文本 单词最少的有 180 个 最 多的有 7 266 个单词 4 2 实验结果及分析 用训练样本训练得到分类器后 用该分类器 对测试数据进行检测实验 同时为了进行比较 也给出了运用 SVM 分类器的结果如表 2 所示 从实验结果可以看出 经训练后 SVM 对自 然文本的识别率为 97 9 对嵌入空字符的隐密文 本的识别率在嵌入率小于 5 时不太理想 尤其在 嵌入率为 2 时只能达到 40 0 而 AdaBoost 在嵌 入率为 2 和 4 时均能全部识别 其他条件下识 别率也为 100 0 证明 AdaBoost 几乎不会受到嵌 入率的影响 反映出 AdaBoost 相当优越的分类性 能 表 2对各种测试数据的识别率 文本类型SVM 的识别率 AdaBoost 的识别率 自然文本 嵌入 2 空字符的隐密文本 嵌入 4 空字符的隐密文本 嵌入 5 空字符的隐密文本 嵌入 8 空字符的隐密文本 嵌入 15 空字符的隐密文本 嵌入 40 空字符的隐密文本 构造法隐密文本 97 9 40 0 90 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 总识别率89 8100 0 5 结束语 本文通过对自然文本统计模型和特性分析 提 出了基于AdaBoost 的隐藏信息检测方法 文章通过 对自然文本和载密文本的学习训练建立AdaBoost 分 类器 利用AdaBoost 分类器较好的分类能力来对未 知的文本进行分类 具有较强的通用性 实验表明 本文建立的分类器具有较好的分类效果 参考文献 1 SUI X G LUO H ZHU Z L A steganalysis method based on the distribution of first letters of words A Proc of 2006 International Conference on Intelligent Information Hiding and Multimedia Signal Processing C Pasadena California USA 2006 369 372 2 SUI X G LUO H ZHU Z L A steganalysis method based on the distribution of characters A Proc of 2006 International Conference on Signal Processing C Guilin China 2006 2599 2602 3 SUI X G LUO H A steganalysis method based on the distribution of space characters A Proc of 2006 International Conference on Communications Circuits and Systems C Guilin China 2006 54 56 4 FRIDRICH J Feature based steganalysis for JPEG images and its implications for future design of steganographic schemes A International Workshop on Information Hiding IH2004 C Toronto Canada 2004 67 81 5 XUAN G R SHI Y Q GAO J J Steganalysis based on multiple features formed by statistical moments of wavelet characteristic functions A Preproc of 7th Int Workshop on Information Hiding C Barcelona Spain 2005 262 277 6 FARID H LYU S Detecting hidden messages using higher order statistics and support vector machines A The 5th Information Hiding Workshop C Noordwijkerhout Netherlands 2002 340 354 7 LYU S FARID H Steganalysis using higher order image statistics J Information Forensics and Security IEEE Transactions 2006 3 111 119 8 KEARNS M VALIANT L G Learning Boolean Formulae or Factoring R Tech Rep TR 14 88 Aiken Computation Laboratory Harvard University 1988 9 RICARDO B Y BERTHIER R N 著 王知津等译 现代信息检索 M 北京 机械工业出版社 2005 102 104 RICARDO