搜索

[11353] 2017-05-16_学点算法搞安全之apriori

文档创建者：s7ckTeam
浏览次数：3
最后更新：2025-01-18
2017-05-16_学点算法搞安全之apriori 学 点 算 法 搞 安 全 之 a p r i o r i 兜 哥   F r e e B u f   2 0 1 7 - 0 5 - 1 6 * 原 创 作 者 ： 兜 哥 ， 本 文 属 F r e e B u f 原 创 奖 励 计 划 ， 未 经 许 可 禁 止 转 载 前 言 在 企 业 安 全 建 设 专 题 中 偶 尔 有 次 提 到 算 法 的 应 用 ， 不 少 同 学 想 深 入 了 解 这 块 ， 所 以 我 专 门 开 了 一 个 子 专 题 用 于 介 绍 安 全 领 域 经 常 用 到 的 机 器 学 习 模 型 ， 从 入 门 级 别 的 S V M 、 贝 叶 斯 等 到 H M M 、 神 经 网 络 和 深 度 学 习 （ 其 实 深 度 学 习 可 以 认 为 就 是 神 经 网 络 的 加 强 版 ） 。 关 联 规 则 数 据 关 联 规 则 挖 掘 通 常 是 无 监 督 学 习 ， 通 过 分 析 数 据 集 ， 挖 掘 出 潜 在 的 关 联 规 则 ， 最 典 型 的 一 个 例 子 就 是 尿 布 和 啤 酒 的 故 事 。 相 传 沃 尔 玛 的 数 据 分 析 人 员 通 过 分 析 大 量 购 物 清 单 发 现 相 当 一 部 分 消 费 者 会 同 时 购 买 尿 布 和 啤 酒 ， 结 果 他 们 把 尿 布 和 啤 酒 赫 然 摆 在 一 起 出 售 ， 结 果 销 量 又 双 双 增 长 。 关 联 规 则 分 析 的 结 果 是 客 观 现 象 的 体 现 ， 有 的 显 然 易 见 ， 比 如 同 时 购 买 三 文 鱼 和 芥 末 ， 有 的 勉 强 可 以 解 释 ， 比 如 尿 布 和 啤 酒 ， 有 的 就 匪 夷 所 思 ， 比 如 打 火 机 和 奶 酪 。 关 联 算 法 中 最 著 名 的 就 是 a p r i o r i 算 法 。 a p r i o r i   简 介 首 先 介 绍 三 个 基 本 概 念 ， 支 持 度 、 置 信 度 和 频 繁 k 项 集 。 支 持 度 ， P ( A   ∩   B ) ， 既 有 A 又 有 B 的 概 率 ， 它 表 现 的 是 A 和 B 两 个 事 件 相 对 整 个 数 据 集 合 同 时 发 生 的 频 繁 程 度 ， 比 如 尿 布 和 啤 酒 的 支 持 度 是 0 . 2 ， 表 明 有 2 0 % 的 消 费 清 单 中 ， 消 费 者 同 时 购 买 了 尿 布 和 啤 酒 。 置 信 度 ， P ( B | A ) ， 在 A 发 生 的 事 件 中 同 时 发 生 B 的 概 率   P ( A B ) / P ( A ) ， 它 表 现 的 是 在 A B 两 个 事 件 的 相 关 程 度 ， 和 整 个 数 据 集 合 的 大 小 没 有 关 系 ， 比 如 尿 布 和 啤 酒 的 置 信 度 为 0 . 8 ， 表 明 在 同 时 购 买 了 两 者 的 消 费 者 中 ， 购 买 尿 布 的 8 0 % 又 购 买 了 啤 酒 。 需 要 特 别 说 明 的 是 ， P ( A   ∩   B ) = P ( B   ∩   A ) ， 但 是 P ( B | A ) 和 P ( A | B ) 是 两 回 事 。 如 果 事 件 A 中 包 含 k 个 元 素 ， 那 么 称 这 个 事 件 A 为 k 项 集 事 件 A 满 足 最 小 支 持 度 阈 值 的 事 件 称 为 频 繁 k 项 集 。 a p r i o r i 算 法 就 是 挖 掘 同 时 满 足 最 小 支 持 度 阈 值 和 最 小 置 信 度 阈 值 的 关 联 规 则 。
a p r i o r i   基 本 原 理 a p r i o r i 算 法 使 用 频 繁 项 集 的 先 验 知 识 ， 使 用 一 种 称 作 逐 层 搜 索 的 迭 代 方 法 ， k 项 集 用 于 探 索 ( k + 1 ) 项 集 。 首 先 ， 通 过 扫 描 事 务 （ 交 易 ） 记 录 ， 找 出 所 有 的 频 繁 1 项 集 ， 该 集 合 记 做 L 1 ， 然 后 利 用 L 1 找 频 繁 2 项 集 的 集 合 L 2 ， L 2 找 L 3 ， 如 此 下 去 ， 直 到 不 能 再 找 到 任 何 频 繁 k 项 集 。 最 后 再 在 所 有 的 频 繁 集 中 找 出 强 规 则 ， 即 产 生 用 户 感 兴 趣 的 关 联 规 则 。 其 中 ， a p r i o r i 算 法 具 有 这 样 一 条 性 质 ： 任 一 频 繁 项 集 的 所 有 非 空 子 集 也 必 须 是 频 繁 的 。 因 为 假 如 P ( I ) <   最 小 支 持 度 阈 值 ， 当 有 元 素 A 添 加 到 I 中 时 ， 结 果 项 集 （ A ∩ I ） 不 可 能 比 I 出 现 次 数 更 多 ， 因 此 A ∩ I 也 不 是 频 繁 的 。 a p r i o r i   的 代 码 实 现 主 流 的 机 器 学 习 库 对 a p r i o r i 支 持 很 少 ， 不 过 a p r i o r 的 实 现 的 确 比 较 简 单 ， 网 上 资 源 很 多 ， 建 议 参 看 p e t e r   h a r r i n g t o n 的 《 机 器 学 习 实 战 》 ， 其 中 对 a p r i o r i 实 现 后 封 装 的 函 数 如 下 ： a p r i o r i   的 应 用 在 安 全 领 域 ， a p r i o r i 的 应 用 非 常 广 泛 ， 凡 是 需 要 挖 掘 潜 在 关 联 关 系 的 都 可 以 尝 试 使 用 ， 比 如 关 联 w a f 的 a c c e s s l o g 与 后 端 数 据 库 的 s q l l o g ， 识 别 s s h 操 作 日 志 中 异 常 操 作 等 。 我 们 这 里 以 分 析 a c c e s s l o g 为 例 子 。 我 们 从 x s s e d 网 站 的 样 例 以 及 w a f 的 拦 截 日 志 中 提 取 x s s 攻 击 日 志 作 为 样 本 ， 示 例 日 志 如 下 ： 我 们 目 标 是 分 析 出 潜 在 的 关 联 关 系 ， 然 后 作 为 S V M 、 K N N 等 分 类 算 法 的 特 征 提 取 依 据 之 一 。 机 器 没 有 办 法 直 接 识 别 日 志 ， 需 要 逐 行 将 日 志 文 本 向 量 化 ， 最 简 单 的 方 式 就 是 按 照 一 定 的 分 割 符 切 割 成 单 词 向 量 ， 示 例 代 码 如 下 ：
切 割 后 的 向 量 示 例 如 下 ： 我 们 以 十 分 严 格 的 置 信 度 来 运 行 ， 试 图 找 到 关 联 关 系 接 近 1 0 0 % 的 情 况 ： 有 趣 的 现 象 出 现 了 ： 有 些 结 果 容 易 理 解 ， 比 如 ’ s c r i p t ’ 和 ’ 1 ′ 、 ’ a l e r t ’ 出 现 的 话 会 1 0 0 % 的 概 率 导 致 ’ / s c r i p t ’ ， 有 些 结 果 匪 夷 所 思 ， 比 如 ’ a ' 和 ’ c ' 出 现 的 话 会 1 0 0 % 的 概 率 导 致 ’ m ' 。 我 们 进 一 步 降 低 门 槛 ， 讲 支 持 度 也 下 降 到 0 . 0 0 1 ， 这 意 味 着 即 使 对 应 的 关 联 关 系 出 现 的 概 率 只 有 千 分 之 一 ， 主 要 它 对 应 的 是 强 关 联 ， 置 信 度 超 过 0 . 9 9 ， 我 们 也 认 为 这 是 一 种 有 价 值 的 关 联 这 个 学 习 的 过 程 会 比 较 慢 ， 我 们 选 取 了 部 分 结 果 ：
我 们 通 过 关 联 挖 掘 识 别 一 种 潜 在 的 关 联 关 系 ， ’ o b j e c t ’   ‘ b a s e 6 4 ′   ‘ d a t a ’   ‘ t e x t / h t m l ’ 测 试 结 果 通 过 分 析 2 0 w 条 x s s 攻 击 样 本 数 据 ， 完 全 通 过 机 器 学 习 的 方 式 挖 掘 潜 在 的 关 联 关 系 ， 得 到 如 下 结 果 举 例 如 下 ： 总 结 挖 掘 的 关 联 关 系 ， 可 以 作 为 S V M 、 K N N 等 分 类 算 法 的 特 征 提 取 依 据 ， 进 一 步 的 攻 击 识 别 需 要 依 赖 分 类 算 法 ， a p r i o r i 等 关 联 挖 掘 算 法 提 供 了 一 种 挖 掘 潜 在 关 联 关 系 的 自 动 化 方 式 。 基 于 S V M 的 X S S 检 测 可 以 参 考 我 上 篇 文 章 《 学 点 算 法 搞 安 全 之 S V M 》 * 原 创 作 者 ： 兜 哥 ， 本 文 属 F r e e B u f 原 创 奖 励 计 划 ， 未 经 许 可 禁 止 转 载
阅 读 原 文
回复

举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

使用Markdown编辑器编辑 使用富文本编辑器编辑

Archiver| 手机版| 小黑屋|
Powered by Discuz! X3.4 Copyright © 2001-2020, Tencent Cloud. 商业源码建议获取授权，如侵犯您的权益，请联系客服处理