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 科学
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
中,将BitransformRegister
和Evolver
结构体引入作用域
extern crate boolnetevo;
use boolnetevo::{
BitransformRegister,
Evolver
};
并创建它们的默认实例
fn app() -> Result<(), String> {
let register = BitransformRegister::new_default();
let mut evolver = Evolver::new_default(®ister)?;
...
}
现在,你可以运行内置的shell...
evolver.shell(®ister)?;
并在你的终端上得到类似这样的东西(带颜色)
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(®ister, "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.rs
和src/bin/script.rs
。
自定义位变换
进化优化种群,以精确计算某些位串函数。相关的功能包括构建函数的参数块、提供输入和输出的位数、根据函数评分输入输出批对。这些功能汇总在Bitransform
特质中。该库实现了它为xor
、add
、mult
、CRC32
、MD5
、SHA1
、SHA2
、SHA3/Keccak
函数及其逆函数,并且你可以为你的函数实现它。
例如,请参阅src/bitransform/xor.rs
和src/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(®ister)?;
evolver.bitran(®ister, "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 = 1
,size = 8000
(是的,大部分将不会被使用),rands = 0
,layers = 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