神经网络化简非多项式混合布尔算术表达式 刘彬彬.pdf

该【神经网络化简非多项式混合布尔算术表达式 刘彬彬 】是由【金钏】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【神经网络化简非多项式混合布尔算术表达式 刘彬彬 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。小型微型计算机系统
JournalofChineseComputerSystems
ISSN1000-1220,CN21-1106/TP
《小型微型计算机系统》网络首发论文
题目:神经网络化简非多项式混合布尔算术表达式
作者:刘彬彬,凤维杰,郑启龙,李京
收稿日期:2022-04-06
网络首发日期:2022-09-30
引用格式:刘彬彬,凤维杰,郑启龙,
式[J/OL].小型微型计算机系统.
.
网络首发:在编辑部工作流程中,稿件从录用到出版要经历录用定稿、排版定稿、整期汇编定稿等阶
段。录用定稿指内容已经确定,且通过同行评议、主编终审同意刊用的稿件。排版定稿指录用定稿按照期
刊特定版式(包括网络呈现版式)排版后的稿件,可暂不确定出版年、卷、期和页码。整期汇编定稿指出
版年、卷、期、页码均已确定的印刷或数字出版的整期汇编稿件。录用定稿网络首发稿件内容必须符合《出
版管理条例》和《期刊出版管理规定》的有关规定;学术研究成果具有创新性、科学性和先进性,符合编
辑部对刊文的录用要求,不存在学术不端行为及其他侵权行为;稿件内容应基本符合国家有关书刊编辑、
出版的技术标准,正确使用和统一规范语言文字、符号、数字、外文字母、法定计量单位及地图标注等。
为确保录用定稿网络首发的严肃性,录用定稿一经发布,不得修改论文题目、作者、机构名称和学术内容,
只可基于编辑规范进行少量文字的修改。
出版确认:纸质期刊编辑部通过与《中国学术期刊(光盘版)》电子杂志社有限公司签约,在《中台上创办与纸质期刊内容一致的网络版,以单篇或整期出版形式,在印刷
出版之前刊发论文的录用定稿、排版定稿、整期汇编定稿。因为《中国学术期刊(网络版)》是国家新闻出
版广电总局批准的网络连续型出版物(ISSN2096-4188,CN11-6037/Z),所以签约期刊的网络版上网络首
发论文视为正式出版。
网络首发时间:2022-09-3011:46:49
网络首发地址:.
小型微型计算机系统
JournalofChineseComputerSystems
神经网络化简非多项式混合布尔算术表达式
111,21
刘彬彬,凤维杰,郑启龙,李京
1
(中国科学技术大学计算机科学与技术学院,合肥230026)
2
(中国科学技术大学安徽省高性能计算重点实验室,合肥230026)
E-mail:******@
摘要:混合布尔算术表达式是指混合使用了位运算符和算术运算符的表达式,
淆方法虽然能够化简特定类型的混合布尔算术表达式,
一种字符串到字符串的解决方案NeuSim,,本文分别构建
,本文生成一个大规模的非多项式混合布尔算术表达式数据集,它
,NeuSim可以将一个非多项式混合布尔算术表达式化简为等价
,NeuSim的化简正确率是已有方法的8倍,.
关键词:混合布尔算术表达式;表达式化简;序列到序列神经网络;图序列神经网络
中图分类号:TP391文献标识码:A
SimplifyingNon-PolynomialMixedBoolean-ArithmeticExpressionsbyNeuralNetwork
LIUBin-bin1,FENGWei-jie1,ZHENGQi-long1,2,LIJing1
1(SchoolofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,Hefei,230026,China)
2(AnhuiKeyLaboratoryofHighPerformanceComputing,UniversityofScienceandTechnologyofChina,Hefei230026,China)
Abstract:MixedBoolean-Arithmetic(MBA)expression,whichmixesbooleanandarithmeticoperations,isanadvancedsoftware
.
However,thesemethodshavealimitedeffectonsimplifyingnon-,weproposeamethod
namedNeuSim,astring-to-stringsolutionbasedontheneuralnetworktolearnandsimplifynon-,
weconstructsequence-to-sequenceandgraph-to-sequenceneuralnetworkstoreducenon-,we
developalarge-scaledatasetincludingonemilliondiversifiednon-,
NeuSimcanreduceanon--of-the-artwork,the
evaluationresultshowsthatNeuSimcansimplify8Xmorenon-polynomialMBAexpressions,anditssimplificationtimeislessthan
.
Keywords:MixedBoolean-Arithmeticexpression;expressionsimplification;sequence-to-sequenceneuralnetwork;
graph-to-sequenceneuralnetwork
其是一种先进的软件混淆技术[4,5].混合布尔算术混淆技术可
1引言
以将一个简单的表达式替换为一个复杂的但语义等价的表
混合布尔算术(MixedBoolean-Arithmetic,MBA)表达式达式,如将x替换为(x^y)+y−2∗(~x&𝑦).因此,混合布尔算
[4,6-9]
[1,2]是指混合使用位运算符(如&,|,~等)和算术运算符(如+,-,*术混淆技术已经被多个学术界和工业界项目所采用.
等)的表达式,如表达式3∗(x&𝑦)−y+[1,3]给出混合布尔算术表达式的大范围应用促使研究人员探索
了混合布尔算术表达式的形式化定义,并将其分类为多项式如何反混淆混合布尔算术表达式,也就是化简混合布尔算术
,文献[1,3],目前已有的计算数学软件都不能
[10,11]
法来产生大量的混合布尔算术恒等式,如x=(x^y)+y−2∗
[4,11][12]
(~x&𝑦).混合布尔算术表达式主要被用于软件混淆领域中,的化简方法,包括:语义等价变换方法,bit-blasting,模式
匹配[13],程序合成技术[14],和基于深度学习的解决方案[15,16].
收稿日期:2022-04-06收修改稿日期:2022-08-24基金项目:国家核高基重大专项项目(2012ZX01034-001-001):刘彬彬,男,1990
年生,博士研究生,研究方向为软件安全与深度学习;凤维杰,男,1995年生,博士研究生,研究方向为深度学习;郑启龙,男,1969年生,硕士,副教授,CCF会员,
研究方向为编译优化与机器学习;李京,男,1966年生,博士,教授,CCF高级会员,研究方向为机器学习与区块链.
2小型微型计算机系统
虽然这些方法都能够化简特定形式的混合布尔算术表达式,
但是相关实验结果表明[3,11],这些方法都不能有效处理非多算术恒等式主要被用于软件混淆(softwareobfuscation)领域
,文献[3]提出使用安全性更高[4,5],
的非多项式混合布尔算术表达式替代已有的多项式混合布以将一个简单的表达式等价替换为一个复杂的等价表达式,
,化简非多项式混合布尔算术表达式是一并用其来复杂化程序代码.

为了化简非多项式混合布尔算术表达式,本文提出一种低廉,该技术已被多个学术界和工业界项目所采纳[4,6-9],其也
字符串到字符串的解决方案NeuSim,该解决方案基于神经可被用于算法优化中[17].另一方面,研究人员开始探索如何
,在序列到序列和反混淆混合布尔算术表达式,也就是理解复杂的混合布尔算
图序列神经网络架构的基础上,
其次,针对相关数据集匮乏的问题,本文收集并生成一个大规知[10,11],常用的SMT求解器和符号计算软件都不能化简混合
模的数据集,该数据集包含1,000,,研究人员提出多种不同的解决方案来
,本文在生成的数据集上训练处理混合布尔算术表达式,包括:基于语义等价变换的技术
NeuSim,,与已有[4,11],bit-blasting[12],模式匹配[13],程序合成技术[14],和基于深
工具的化简结果相比,NeuSim的化简正确率是已有解决方度学习的方法[15,16].这些化简方法都可以处理特定类型的混
案的8倍,并且化简时间可以忽略不计().合布尔算术表达式,其中基于语义等价变换的方法是最有效
本文的主要贡献总结如下:的,,在
,已有的方法都表现出
项式混合布尔算术表达式,并且构建了相应的序列到序列和了明显的不足[3,11].并且,文献[3]提出使用安全性更高的非多

.

尔算术表达式数据集,其包括各种形式的非多项式混合布尔文献[15]探索了如何使用神经网络化简多项式混合布尔
,其提供了一个大规模的线性混合布尔算术表达
,相较于已有的化简方式(多项式混合布尔算术表达式的特例)数据集,并且用该数
法,NeuSim的化简正确率至少提高7倍,并且化简时间至少据集训练相关的序列到序列神经网络模型,实验结果表明其
,与本研究相关的资源(代码,数据集,[16]注
经网络模型)可在如下网址公开获意到已有的基于序列到序列模型在解决数学表达式时存在
取:,进而提出使用图序列神经网络来处理数学表达
本文接下来的组织如下:,图序列神经网络相较于序列到序列模型,
达式的相关背景知识;第3部分介绍本文提出的字符串到字在处理有关数学表达式任务时具有更高的正确率.
符串的解决方案NeuSim;第4部分介绍相关实验结果及其分此外,已有多个研究工作使用神经网络模型来处理数学
析;[18,19]使用序列到序列的模型来处理数学表达
式,如表达式重写和数学表达式问答;文献[20]使用树神经网
2相关工作
,对于本文所研究的非多项式混合布
,目前业界尚无相关工作.
文献[1,2]提出了混合布尔算术表达式的概念其是指混合使
,3化简非多项式混合布尔算术表达式
用位运算符(如&,|,~等)和算术运算符(如+,-,*等)的表达式,定义1

简单的等价表达式,本节将详细介绍一种字符串到字符串的
布尔算术表达式不符合定义1,那么它将属于非多项式混合布尔
解决方案NeuSim,该方案使用神经网络来学习和化简非多
算术表达式[1,3],这说明多项式和非多项式混合布尔算术表达式

之间是补集的关系.
的各类数学表达式计算模型,本文构建并实现了两类神经网
(1)所示,其
络模型:
中ai为整数常量,ei,j(x1,…,xt)为n-bit变量x1,…,xt的位运算前业界缺乏非多项式混合布尔算术表达式数据集,本文在相
,生成了一个大规模的非多项式混合布尔算
术表达式数据集.
∏
∑ai(j∈Jiei,j(x1,…,xt))(1)
i∈
[21]
文献[1]设计了一种基于真值表的矩阵乘法方法,并用其本文基于编码器-解码器架构来实现NeuSim,其结构
:负责从输入表达式中学习隐藏模式的编码
尔算术恒等式的基础上,文献[3]提出多种形式化的方法来产器,以及根据学到的知识预测表达式化简结果的解码器,模型
刘彬彬等:神经网络化简非多项式混合布尔算术表达式3
、的神经元,从而避免模型产生过拟合的现象.
[23]的
过学习输入数据的特征,,它的结构更加
、,该模型的编码器首先构
成,通过预先设定的字典,NeuSim可以将解码器的输出重构造一个嵌入层以独热编码方式向量化输入的非多项式混合
成一个简单的表达式,也就是对应的非多项式混合布尔算术布尔算术表达式,并用dropout策略随机丢弃该层的神经元
,
其被用以学习输入表达式中各个字符之间的隐藏关系(如相
同字符间的时序关系),并将这种隐藏关系抽象为隐藏向量.
随后,
入层、单层GRU以及全连接层构建,全连接层依据字符字典
将输出的向量转换成相应的字符串,即输入表达式的化简结
果.
本文构建的第三个模型是基于注意力机制[24]的NeuSim.
图模型结构示意图
1NeuSim注意力机制是目前自然语言处理领域最为有效的方法,其是
、全部采用线性层的模型策略,且能够对
为了全面比较不同的神经网络模型之间的性能差异本
,表达式序列中有价值的部分赋予更高的注意力(即权重),进
文采用两类不同的神经网络架构来构建的编码器
NeuSim:
序列到序列的模型和图序列的模型其中构建基于长短期记
.,进的基于注意力机制模型之一的BERT机制,并将其作为编
忆网络[22]门控循环单元[23]和注意力机制[24]的
LSTM,GRU,,模型首先使用一个嵌入层将输入
[25]
序列到序列的模型;同时,构建基于图卷积架构的图序列的非多项式混合布尔算术表达式以独热编码方式转换成向
网络模型在序列到序列的模型中直接将输入的长
.,NeuSim量;然后构建一个由8头注意力层和一个位置前馈层组成的
度可变的非多项式混合布尔算术表达式输出给编码器在图
.基本单元,该基本单元内的各个组件之间通过正则化层进行
序列模型中首先需要对输入的非多项式混合布尔
,NeuSim连接;随后,将该基本单元前后连接若干次(本文使用5个基
算术表达式进行预处理将输入的表达式转换成有向无环图
(本单元).编码器的输出为一个隐藏向量,并将其输出给解码
图然后将图输出给图卷积编码器
(DAG)),,每个基本单元由掩码
序列到序列神经网络模型
、8头注意力层以及位置前馈层组成,基本单元
混合布尔算术表达式多以字符串的形式进行保存和处
,解码器的输出向量依据字
理故本文首先研究如何构造一个基于序列到序列架构的
,符字典,通过全连接层转换成一个表达式,也即输入表达式的
在序列到序列的模型中编码器和解码器都由循环
NeuSim.,化简结果.
神经网络组成其输入输出也是由字符组成的、长度可变的
,
字符串为了对比各种不同的序列到序列神经网络模型对
.在序列到序列的模型中,以字符串形式呈现的混合布尔
性能的影响本研究采用三种广泛使用的循环神经
NeuSim,算术表达式不利于神经网络学习表达式中某些隐藏信息,例
网络长短期记忆网络[22]门控循环单元[23]和注
(LSTM,GRU,如在字符串序列表示中,算符的优先级需要通过添加额外的
意力机制[24]作为编码器和解码器的核心构
BERT)NeuSim括号来明确化(如表达式x+(3∗y)).为了克服序列到序列神
件接下来将详细介绍这三种神经网络模型的结构
,.经网络模型在处理数学表达式方面的潜在不足,目前已有研
本文构建的第一个模型是基于长短期记忆网络

[22]的是自然语言处理领域最为经典的
,例如视
神经网络模型之一,它可以较好地解决长输入中相同字符相频标签生成、图像分类、蛋白质分子分类和化合物生成等任
隔较远导致模型无法捕获长期依赖的问题首先在模型的编
.,,首先需要
码器中构造一个嵌入层作为输入的非多项式混合布尔算术
将输入的表达式转换成图,如抽象语法树(AST树)和有向无
表达式接收器该嵌入层通过独热编码的方式将输入的表达
,环图(DAG图),该图在保留表达式相关语法语义信息的同时,
式向量化在嵌入层之后编码器构造了激活函数为的
.,tanh4可以丢弃无用的辅助信息(如括号).之后,模型对转换后的图
层层通过时间依赖的迭代学习编码器可以从输入的
LSTM.,进行处理,并且输出相应的结果表达式.
表达式中学习到相应地隐藏模式,并将这些隐式信息抽象化本文构建的最后一个模型是基于图序列神经网络[25]的
为一个固定大小的隐藏向量在解码器中其首先构造一个嵌
.,,NeuSim需要对输入的非多项式混合布尔算术
入层该嵌入层以隐藏向量作为输入并将其输出给一个由
,,
层组成的神经网络最后解码器的输出向量通过一个
LSTM.,成对应的有向无环图(DAG图).基于该DAG图生成相应的
全连接层重新编码成一个新的表达式该表达式即为对应输
,特征矩阵和邻接矩阵,拼接这两类矩阵后将其送入到模型的
入表达式的化简结果为了避免模型训练时的过拟合本模型
.,,后接一个全局
采用随机丢弃策略该策略可以随机丢弃神经网络中
dropout,最大池化层,
4小型微型计算机系统
出为一个隐藏向量,,
[26]
入层、GRU以及全连接层构成,通过序列化学习生成一个输每一个等式的正确性(Eg≡Ec),本文使用Z3求解器对其
出向量,并通过字符字典得到输出向量对应的表达式,也即输进行验证,并且保证数据集中的每一条数据都通过了该验证.
,数
综上所述,
络模型,,并且产生的表达式字符长度介于20
,这是第一个大规模的非多项式混合
Table1ModellayersandsizeofNeuSim布尔算术表达式数据集.
LSTMGRUBERT图序列模型表2数据集中的表达式示例
模型编码器2155Table2Samplesinthedateset
层数解码器2151EgEc
模型参数(百万)~(−x)+1+(x|y)−(x^y)−(x&𝑦)
∗(−y)(~(y−1)&𝑥)∗(~(y−1)|x)
为了得到更好的化简效果,NeuSim需要大规模的数据+(~(y−1)&~𝑥)∗(~(~(𝑦−1))&𝑥)
,相关文献[3,6,17]只提供了少量非多项式混x+y2∗((((x|y)+(x&𝑦))|𝑧))−(((𝑥^𝑦)
合布尔算术表达式(约1,000个表达式)示例,这对于训练和测+2∗(x&𝑦))^𝑧)−𝑧
[3,6]
,本文根据相关文献中提出x|y|z((x+(~x&𝑦))^𝑧)+((𝑦+(𝑥&~𝑦))&𝑧)

入为一个简单的表达式,输出为一个复杂的等价非多项式混4实验与结果分析
合布尔算术表达式.

通过进一步观察发现,文献[3,6]生成的非多项式混合布尔
本文方法的实验环境为:实验操作系统为64-bitUbuntu
算术表达式具有一定的规律性和一致性[4],这些特性造成在
,CPU型号为Intel(R)Core(TM)i9-10980XE@
,为了增加非多项式混合
,
布尔算术表达式的多样性和随机性,本文提出如下的表达式

等价变换方法(用于替换的等价表达式均由文献[1]所提出的
用Python3编程语言,基于PyTorch框架以及PyTorch
相应方法随机产生):
Geometric库实现本文所提出的相关神经网络模型,同时使
1)(子)表达式中的变量进行等价变
用PythonAST库实现图序列模型中的预处理操作.
换,以期得到一个新的等价表达式,如将(x&𝑦)变换为
,本文使用相同的
(((x|y)+(x&𝑦)−𝑦)&𝑦).
,都对这些模型进行1000次的
2)(子)表达式中的常量替换为一个
迭代训练,
等价的表达式,如将常量1替换为(x&𝑦)−(x|y)−(~x&~𝑦).
过程中使用早停技术,该技术监控验证集损失下降程度来判
3)
断是否需要提前终止训练过程,,本
价替换,如将((x|y)+(x&𝑦))替换为x+y.
文使用Adam优化器来学习神经网络模型中的参数,模型的
4),来产
初始学习率设置为1e−3,并在模型迭代的过程中使用
生一个新的等价表达式,如将表达式x+y+z=
,在模型预
((((x|y)+(x&𝑦))|𝑧))+(((𝑥^𝑦)+2∗(𝑥&𝑦))&𝑧)和表达式
测阶段,本文使用Z3求解器来判断模型的输出与输入的表
z=(z|y)−(~z&𝑦),线性组合为一个新的表达式x+y=
达式是否语义等价.
((((x|y)+(x&𝑦))|𝑧))+(((𝑥^𝑦)+2∗(𝑥&𝑦))&𝑧)−

(𝑧|𝑦)+(~𝑧&𝑦).

综上所述,本文首先通过文献[3,6]产生一个原始的非多项
机采样100,000条样本用以训练NeuSim的四个不同的神经
式混合布尔算术表达式,之后使用等价变换方法对生成的原
网络模型,其中90%的数据作为模型的训练集,10%的数据作

,以确保
非多项式混合布尔算术表达式,但是从训练和测试NeuSim
每一个测试样本都不会出现在训练集中,测试集共含有
的实际出发,本文构建一个包含1,000,000条非多项式混合布
10,000个非多项式混合布尔算术表达式及其对应的等价简
[10]指出,在实际的软件混淆场
单表达式.
景下使用的都是3变量及其以下变量的混合布尔算术表达
为了度量表达式的复杂度,本文使用以下三个指标来测
,数据集中包含800,000个3变量及其以下变量的非
量非多项式混合布尔算术表达式的复杂度,指标数值越大,也
多项式混合布尔算术表达式,200,000个多变量非多项式混
就意味着该表达式越复杂.
合布尔算术表达式.
1),所有的变
数据集中的每一条数据都是一个二元组(E,E),E表示
gcg量重复出现的总次数.
一个简单的表达式,E表示相应等价的非多项式混合布尔算
c2),布尔操作符
刘彬彬等:神经网络化简非多项式混合布尔算术表达式5
,其通过学习混合布尔
3),该字符算术表达式的语义,产生一个语义等价但更简单的表达式.

表3数据集复杂度统计结果本文使用以下三个指标来全面测试非多项式混合布尔
Table3Statisticofthedatasets’complexity算术表达式化简工具的化简性能:
训练集测试集1)正确率:经过相关工具化简之后,化简结果与原表达式