Research on Code Detection and DFG Generation in CRCLA Compiler Front-End

doi:10.3778/j.issn.1002-8331.2301-0102

Abstract

Abstract: Aiming at the requirement of automatic mapping of cryptographic algorithms to reconfigurable cryptographic logic array（CRCLA） and providing accurate and concise data flow graph for back-end mapping, a front-end design of data flow graph generation and optimization is proposed. In this design, Flex and Bison are used as the compiler framework. The syntax tree is obtained by lexical and syntactic analysis of the code written by the high-level language C++, and the data flow graph is generated by semantic analysis according to the instruction characteristics of cryptographic algorithm and the hardware structure of CRCLA. There are functions implemented in different ways in the source code, such as S-box replacement and bit replacement, but they can be implemented in CRCLA instead of single operator. In order to solve such problems, this paper designs a graph embedding model based on attention mechanism for detection and recognition, and carries out graph structure replacement. At the same time, function expansion, redundant node elimination and data flow graph layering are used to optimize the data flow graph. The experimental results show that the simplified data flow graph is generated automatically after code identification and optimization, and the performance is improved by about 37% compared with other compiler front-end.

Key words: reconfigurable cryptographic logic array, front end, lexical syntax analysis, data flow graph, attention mechanism, graph embedding

摘要： 针对密码算法自动映射到可重构密码逻辑阵列（CRCLA）的需求，并为给后端映射提供准确、精简的数据流图，提出了一种数据流图生成与优化的前端设计。该前端以Flex、Bison为编译框架，对高级语言C++编写的代码进行词法、语法分析得到语法树，并依据密码算法指令特点和CRCLA硬件结构进行语义分析生成数据流图；源代码中存在不同方式实现的功能如S盒替换、比特置换，但其在CRCLA中可用单算子代替实现。设计了基于注意力机制的图嵌入模型进行检测识别，并进行图结构替换；同时函数展开、冗余节点消除与数据流图分层等操作优化了数据流图。实验结果表明，该设计经代码识别、优化后，实现了精简的数据流图自动化生成，与其他编译器的编译前端相比性能提高了约37%。

关键词: 可重构密码逻辑阵列, 前端, 词法语法分析, 数据流图, 注意力机制, 图嵌入

YANG Chenguang, LI Wei, DU Yiran. Research on Code Detection and DFG Generation in CRCLA Compiler Front-End[J]. Computer Engineering and Applications, 2023, 59(23): 63-72.

杨晨光, 李伟, 杜怡然. CRCLA编译前端中代码检测与DFG生成技术研究[J]. 计算机工程与应用, 2023, 59(23): 63-72.

References

[1] 谢羽威.REmusⅡ可重构处理器优化任务编译环境前端设计[D].上海：上海交通大学，2013.
XIE Y W.The optimized frontend compiling system design for REmus II reconfigurable processor[D].Shanghai：Shanghai Jiao Tong University，2013.
[2] KOEPLINGER D，FELDMAN M，PRABHAKAR R，et al.Spatial：a language and compiler for application accelerators[J].ACM SIGPLAN Notices，2018，53（4）：296-311.
[3] BAGHDADI R，RAY J，ROMDHANE M B，et al.Tiramisu：a polyhedral compiler for expressing fast and portable code[C]//Proceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization，2019：193-205.
[4] 刘谷.可重构众核流处理器上的编译与程序优化技术[D].合肥：中国科学技术大学，2013.
LIU G.Compiler and program optimization on reconfigurable manycore stream processors[D].Hefei：University of Science and Technology of China，2013.
[5] 李艳杰，高新阳.C语言微型编译器的实现[J].现代信息科技，2018，2（10）：112-113.
LI Y J，GAO X Y.Implementation of C language mini compiler[J].Modern Information Technology，2018，2（10）：112-113.
[6] 刘书勇.面向FPGA的可重构编译器研究[D].哈尔滨：哈尔滨工程大学，2017.
LIU S Y.Research on reconfigurable compiler oriented to FPGA[D].Harbin：Harbin Engineering University，2017.
[7] 徐金光.C编译器语法分析的设计与实现[D].成都：电子科技大学，2016.
XU J G.The design and implementation of the C compiler grammar analysis[D].Chengdu：University of Electronic Science and Technology of China，2016.
[8] 王文龙，林中.基于词法和语法分析技术对FED解析的优化[J].计算机工程与设计，2010，31（9）：2052-2056.
WANG W L，LIN Z.Optimize of FED analysis based on technologies of lexical analysis and syntax analysis[J].Computer Engineering and Design，2010，31（9）：2052-2056.
[9] 杨劭君，苏小红，王甜甜，等.C语言词法语法分析工具CParser的设计与实现[J].智能计算机与应用，2014，4（5）：69-71.
YANG S J，SU X H，WANG T T，et al.Design and implementation of lexical and syntax analysis tool Cparser for C language[J].Intelligent Computer and Applications，2014，4（5）：69-71.
[10] 陈嘉颖，于炯，杨兴耀.一种融合语义分析特征提取的推荐算法[J].计算机研究与发展，2020，57（3）：562-575.
CHEN J Y，YU J，YANG X Y.A feature extraction based recommender algorithm fusing semantic analysis[J].Journal of Computer Research and Development，2020，57（3）：562-575.
[11] 朱龙珠，田诺，张全.基于语义分析的语音情感在线识别方法研究[J].电子设计工程，2021，29（11）：151-154.
ZHU L Z，TIAN N，ZHANG Q.Research on speech emotion online recognition method based on semantic analysis[J].Electronic Design Engineering，2021，29（11）：151-154.
[12] 蒋楚，王永杰.一种基于表达式树的gadget语义分析技术[J].计算机工程，2021，47（1）：109-116.
JIANG C，WANG Y J.A technique of gadget semantic analysis based on expression tree[J].Computer Engineering，2021，47（1）：109-116.
[13] 梁瑶，谢春丽，王文捷.基于图嵌入的代码相似性度量[J].计算机科学，2022，49（S2）：801-806.
LIANG Y，XIE C L，WANG W J.Code similarity measurement based on graph embedding[J].Computer Science，2022，49（S2）：801-806.
[14] CAI H Y，ZHENG V W，CHANG K C C.A comprehensive survey of graph embedding：problems，techniques and applications[J].IEEE Transactions on Knowledge & Data Engineering，2018，30（9）：1616-1637.
[15] 王玉联，鲁鸣鸣.可解释的基于图嵌入的Android恶意软件自动检测[J].计算机工程与应用，2021，57（23）：122-128.
WANG Y L，LU M M.Interpretable automatic detection of Android malware based on graph embedding[J].Computer Engineering and Applications，2021，57（23）：122-128.
[16] 李智杰，韩津津，李昌华，等.面向图嵌入的改进图注意机制模型[J].计算机工程与应用，2023，59（17）：152-158.
LI Z J，HAN J J，LI C H，et al.Improved graph attention mechanism model for graph embedding[J].Computer Engineering and Applications，2023，59（17）：152-158.
[17] VASWANI A，SHAZEER N，PARMAR N，et al.Attention is all you need[C]//Advances in Neural Information Processing Systems（NIPS），2017：5998-6008.
[18] 杨善良，常征.基于图注意力神经网络的中文隐式情感分析[J].计算机工程与应用，2021，57（24）：161-167.
YANG S L，CHANG Z.Chinese implicit sentiment analysis based on graph attention neural network[J].Computer Engineering and Applications，2021，57（24）：161-167.
[19] 刘华玲，张国祥，马俊.图嵌入算法研究进展[J].浙江大学学报（理学版），2022，49（4）：443-456.
LIU H L，ZHANG G X，MA J.Research progress of graph embedding algorithms[J].Journal of Zhejiang University（Science Edition），2022，49（4）：443-456.
[20] NAIR A，ROY A，MEINKE K.FuncGNN：a graph neural network approach to program similarity[C]//Proceedings of the International Symposium on Empirical Software Engineering and Measurement（ESEM），2020.
[21] WANG Y，GU Y，ZHOU J，et al.A graph-based approach for semantic similar word retrieval[C]//2015 International Conference on Behavioral，Economic and Socio-cultural Computing （BESC），2015：24-27.
[22] 汪洁，王长青.子图相似性的恶意程序检测方法[J].软件学报，2020，31（11）：3436-3447.
WANG J，WANG C Q.Malware detection method based on subgraph similarity[J].Journal of Software，2020，31（11）：3436-3447.
[23] 李盛.分组密码专用描述语言及编译技术研究[D].郑州：战略支援部队信息工程大学，2020.
LI S.Research on the block cipher description language and compilation technology[D].Zhengzhou：Information Engineering University，2020.