#boolean #evolution #inverse #bitstring #networking

bin+lib boolnetevo

通过进化布尔网络来近似位串函数及其(未知的)逆函数

4 个版本

0.4.0 2021年2月14日
0.3.2 2020年12月14日
0.3.1 2020年12月14日
0.3.0 2020年12月13日

#302 in 科学

MIT/Apache

175KB
3.5K SLoC

BoolNetEvo

通过进化布尔网络来近似位串函数及其(未知的)逆函数。

机制 (点击显示/隐藏)

Layer k+1               ●                         ●
↑               ┌───────┼───────┐         ┌───────┼───────┐
↑               ○       ○       ○         ○       ○       ○
↑             / | \   / | \   / | \     / | \   / | \   / | \
Layer k      ●  ●  ● ●  ●  ● ●  ●  ●   ●  ●  ● ●  ●  ● ●  ●  ●

布尔网络,或 boolnet,是人工神经网络的一个已知特殊情况,其中每个细胞或 boolon 的输入/输出是位——0(假)和 1(真),而不是范围,例如(-∞; +∞)中的值。boolon 的输出是其输入的布尔函数,这些输入是前一层的 boolon 的输出。

在这个实现中,布尔函数有 3 个变量,并由 u8 值编码,这些值代表此类函数的真值表。每个 boolon 都有一个输入树,其叶子是其输入 boolon,然后,在树的每一层,一个布尔函数在当前层的 3 个值给出下一层的 1 个值。根层单值是这个 boolon 的输出。在上面的图中,输入树的高度为 2,因此每个 boolon 的输出受前一层的 32 = 9 个 boolon 的输出影响(其中一些可能相同)。

所有层的 boolon 数量相同,信号可以通过 boolnet 传播几次,称为 周期:在每次周期的末尾,最后一层的输出成为第一层的输入。在这些约束下,可以将层视为位于时间而不是空间中的步骤,如果您将所有层的 i-第 boolon 识别为在每个周期内每步改变其输入树的 boolon。

层可以具有 rands boolon,其输出是随机的。以牺牲较慢的学习速度为代价,获得鲁棒性和自由(不可预测)...

使用 256 种可能的 3 变量布尔函数数组,在 批量 中执行 128 个数据流的并行计算。

具有相同架构的几个 boolnet 组成一个 种群,通过遗传算法在时间上进化。在每个 时代

  • 所有 boolnet 根据它们计算某些位串函数或其逆函数的方式(平均而言,错误位越多,分数越低)进行评分,

  • 分数最低的 boolnet 被最高分数的 boolnet 的后代所取代。

继承,如通常一样,是 交叉变异,在这种情况下,对于每个 boolon 的 1) 输入 boolon 的索引和 2) 输入树中的布尔函数。

请注意,单个boolnet不会进化;进化的是种群。

该库的目的是为此过程提供控制,使其更加互动。

快速入门

警告:使用release配置文件,没有优化,执行速度将慢20-30倍。

在你的code.rs中,将BitransformRegisterEvolver结构体引入作用域

extern crate boolnetevo;

use boolnetevo::{
    BitransformRegister,
    Evolver
};

并创建它们的默认实例

fn app() -> Result<(), String> {
    let register = BitransformRegister::new_default();
    let mut evolver = Evolver::new_default(&register)?;
    ...
}

现在,你可以运行内置的shell...

    evolver.shell(&register)?;

并在你的终端上得到类似这样的东西(带颜色)

BITRANSFORM: InvXor { direct: Xor }
POPULATION: 250
ARCHITECTURE: height = 1, size = 48, rands = 2, layers = 1, cycles = 1
PARAMETERS: batches = 8, replace_ratio = 0.7, par_ratio = 0.8, parents = 2, par_sw_prob = 0.9, mutat_prob = 0.1
SETTINGS: log off, test new, print improve
Type "?" to see the list of available commands...
$ evol
Press any key to stop...
Epoch        1 (     41 ms): min =   -9.0586, average =   -7.9585, max =   -6.8008
Epoch        2 (     29 ms): min =   -8.9746, average =   -7.7293, max =   -6.7021
Epoch        3 (     29 ms): min =   -8.9043, average =   -7.5695, max =   -6.4512
Epoch        4 (     18 ms): min =   -8.9697, average =   -7.4082, max =   -5.7324
Epoch        6 (     17 ms): min =   -8.7197, average =   -7.1513, max =   -5.7129
...
Epoch       58 (     29 ms): min =   -5.0742, average =   -1.9552, max =   -0.4736
Epoch       64 (     16 ms): min =   -4.5156, average =   -1.8883, max =   -0.2500
Epoch       65 (     17 ms): min =   -5.0068, average =   -1.8879, max =    0.0000

BITRANSFORM: InvXor { direct: Xor }
POPULATION: 250
ARCHITECTURE: height = 1, size = 48, rands = 2, layers = 1, cycles = 1
PARAMETERS: batches = 8, replace_ratio = 0.7, par_ratio = 0.8, parents = 2, par_sw_prob = 0.9, mutat_prob = 0.1
SETTINGS: log off, test new, print improve
$ run 0 a7b8
e9924e2a

(为了验证0xe992 XOR 0x4e2a = 0xa7b8

$ dir e9924e2a
a7b8

或者使用编程模式中的任何计算器。)

...或者你可以直接调用Evolver的方法

    evolver.bitran(&register, "inv-sha1", &[1, 4])?; // 1 round of SHA-1 with 4-byte message
    evolver.arch(2, 240, 8, 2, 1)?;
    evolver.par("mutat_prob", "0.2")?;
    evolver.evol(100)?;
    evolver.par("mutat_prob", "0.1")?;
    evolver.evol(50)?;
    evolver.save("evolvers/invsha1-demo")?;

请参阅src/bin/shell.rssrc/bin/script.rs

自定义位变换

进化优化种群,以精确计算某些位串函数。相关的功能包括构建函数的参数块、提供输入和输出的位数、根据函数评分输入输出批对。这些功能汇总在Bitransform特质中。该库实现了它为xoraddmultCRC32MD5SHA1SHA2SHA3/Keccak函数及其逆函数,并且你可以为你的函数实现它。

例如,请参阅src/bitransform/xor.rssrc/bitransform/sha1.rs。直接位变换和逆位变换之间的区别在于,在前者中,输入函数按位与输出进行比较,而在后者中,相同的输出函数输入进行比较。换句话说,你不需要显式地逆函数来评分试图执行逆操作的东西...实际上,“东西”应该成为一个反转器。

假设你已经在func模块中的Func上完成了它,然后将其添加到注册表中

mod func;

use func::{Func, InvFunc};

fn app() -> Result<(), String> {
    let mut register = BitransformRegister::new_default();
    register.add(vec![
        Func::reg_entry(), InvFunc::reg_entry()
    ])?;
    ...
}

现在你可以用它与进化者一起使用了

    let mut evolver = Evolver::new_default(&register)?;
    evolver.bitran(&register, "inv-func", &[7, 5, 3])?;
    evolver.evol(1000)?;

(这里7, 5, 3是你的函数参数。)

修改库

好吧,复制其源代码并做你想做的事情:扩展架构、应用另一种遗传算法、优化性能……这将是另一回事,你应该给它一个不同的名字。

联系

一些类似框架、软件包、项目

可能还有更多……在搜索这些时,请记住,该领域中的“进化”一词有时意味着随时间改变单个boolnet状态,而不是优化boolnet种群。

成就

到目前为止,嗯...虽然人口相对较快地学会了反转简单的位串函数,如位异或,但对于更复杂的函数,尤其是那些用于防止反转的函数(如SHA-x的加密散列轮次),他们却感到很吃力。即使是ADD,由于进位,也需要更“先进”的boolnet架构(更多层等),这使得学习速度显著减慢。似乎存在非零的上限,对于最佳得分,当然,没有保证达到0分,也就是说,培育一个boolnet,它总是精确计算函数。

可能存在某种证明表明,当函数的复杂度超过某个阈值时,这种方法存在无法克服的限制,这时应用它就像尝试用灰烬建造桥梁一样。另一方面,它可以是某些更复杂方案的一部分。

一个故障

案例A。设置以下进化者

  • 位变换是inv-sha2,具有64轮(即完整的SHA2-256)和消息长度60字节(480位)inv-keccak,散列长度为256,24轮(即完整的SHA3-256),相同的消息长度;
  • 种群数量为500;
  • 架构是height = 1size = 8000(是的,大部分将不会被使用),rands = 0layers = 1(单层...),cycles = 1
  • 进化参数默认值,除了batches = 16(或batches = 32)和mutat_prob = 0.001
  • 设置:将test更改为all,将print更改为all

现在,启动进化,在shell中输入$ e,并查看average得分列。无论经过多少个时代,它都保持在非常接近-128.0的位置,但不应超过-127.95或更多(批次数越多,大数法则提供的精度越高)。

这个结果是可以预料的:没有这样的网络——其中每个输出位都是3个或更少散列位的函数——能够统计上优于随机猜测消息(及其散列)的这些预映像抵抗的加密散列。当然,整体种群也表现出没有改进的情况。

案例B。与案例A相同,只有一个不同之处:将消息长度减少到40字节(320位——注意它仍然大于散列长度);不要忘记在之后reset种群。现在,再次开始进化。大约100个时代后,average得分增加到接近-127.0并保持在那里。它似乎在20-30个时代时开始改善,当时一些网络获得(?)非常、非常小的能力来反转散列,然后它们的后代在种群中传播。

重置种群,并多次重复案例A和B的进化,以验证其稳定性。或者尝试SHA1、MD5,结果类似。

如果这不是本节标题的话,那1位(与近似正态分布的分数均值相比,偏差大于10σ)意味着什么?提示:考虑一个逆器,它给定一个哈希,尝试几个(甚至是2个)固定消息,并选择一个哈希位匹配数量最多的消息。

依赖项

~4–5.5MB
~103K SLoC