基于同余方程和改进的压扁控制流的混淆算法

doi:10.11772/j.issn.1001-9081.2017.06.1803

计算机应用 ›› 2017, Vol. 37 ›› Issue (6): 1803-1807.DOI: 10.11772/j.issn.1001-9081.2017.06.1803

基于同余方程和改进的压扁控制流的混淆算法

王岩^1,2,3, 黄章进^1,2,3, 顾乃杰^1,2,3

1. 中国科学技术大学计算机科学与技术学院, 合肥 230027;
2. 中国科学技术大学安徽省计算与通信重点实验室, 合肥 230027;
3. 中国科学技术大学先进技术研究院, 合肥 230027

收稿日期:2016-11-15 修回日期:2016-12-21 出版日期:2017-06-10 发布日期:2017-06-14
通讯作者: 黄章进
作者简介:王岩(1991-),男,山东济南人,硕士研究生,CCF会员,主要研究方向:软件技术、程序优化;黄章进(1980-),男,湖北天门人,副教授,博士,CCF会员,主要研究方向:计算机图形学、图形处理器计算;顾乃杰(1961-),男,江苏南通人,教授,硕士,CCF会员,主要研究方向:并行算法、并行处理、并行体系机构。
基金资助:
安徽省自然科学基金资助项目（1408085MKL06）；高等学校学科创新引智计划项目（B07033）。

Obfuscating algorithm based on congruence equation and improved flat control flow

WANG Yan^1,2,3, HUANG Zhangjin^1,2,3, GU Naijie^1,2,3

1. School of Computer Science and Technology, University of Science and Technology of China, Hefei Anhui 230027, China;
2. Anhui Province Key Laboratory of Computing and Communication Software, University of Science and Technology of China, Hefei Anhui 230027, China;
3. Institute of Advanced Technology, University of Science and Technology of China, Hefei Anhui 230027, China

Received:2016-11-15 Revised:2016-12-21 Online:2017-06-10 Published:2017-06-14
Supported by:
This work is partially supported by the Anhui Provincial Natural Science Foundation (1408085MKL06), the Program for Innovation of the Discipline Higher Education (B07033).

摘要/Abstract

摘要： 针对现有控制流混淆算法的混淆结果单一的问题，提出了一种基于同余方程和改进的压扁控制流混淆算法。首先，使用密钥和一组同余方程来生成源代码的基本块中需要使用的不透明谓词；其次，基于Logistic混沌映射提出了一种新的N态不透明谓词构造算法，并将其应用到现有的压扁控制流算法中，对现有的压扁控制流算法进行改进；最后，将上述两个对源码进行混淆的算法结合，以此来增加源代码中控制流的复杂度，使其更难被破解。与现有的基于混沌不透明谓词的压扁控制流算法相比，所提混淆算法使混淆后代码的防篡改攻击时间平均提高了22%以上，总圈复杂度平均提高了34%以上。实验结果表明，所提算法能够保证混淆后程序执行结果的正确性并且具有很高的圈复杂度，能够有效地抵抗静态攻击和动态攻击。

关键词: 代码混淆, N态不透明谓词, 同余方程, 压扁控制流算法

Abstract: Aiming at the simple obfuscating result of the existing control flow obfuscating algorithm, an obfuscating algorithm based on congruence equation and improved flat control flow was presented. First of all, a kind of opaque predicate used in the basic block of the source code was created by using secret keys and a group of congruence equation. Then, a new algorithm for creating N-state opaque predicate was presented based on Logistic chaotic mapping. The proposed algorithm was applied to the existing flat control flow algorithm for improving it. Finally, according to the combination of the above two proposed algorithms for obfuscating the source code, the complexity of the flat control flow in the code was increased and make it more difficult to be cracked. Compared with the flat control flow algorithm based on chaotic opaque predicate, the code's tamper-proof attack time of the obfuscated code was increased by above 22% on average and its code's total cyclomatic complexity was improved by above 34% on average by using the proposed obfuscating algorithm. The experimental results show that, the proposed algorithm can guarantee the correctness of execution result of the obfuscated program and has a high cyclomatic complexity, so it can effectively resist static and dynamic attacks.

Key words: code obfuscation, N-State opaque predicate, congruence equation, flat control flow algorithm

中图分类号:

TP311.56

王岩, 黄章进, 顾乃杰. 基于同余方程和改进的压扁控制流的混淆算法[J]. 计算机应用, 2017, 37(6): 1803-1807.

WANG Yan, HUANG Zhangjin, GU Naijie. Obfuscating algorithm based on congruence equation and improved flat control flow[J]. Journal of Computer Applications, 2017, 37(6): 1803-1807.

参考文献

[1] 苏庆,吴伟民,李忠良,等.混沌不透明谓词在代码混淆中的研究与应用[J].计算机科学,2013,40(6):155-159.(SU Q, WU W M, LI Z L, et al. Research and application of chaos opaque predicate in code obfuscation[J]. Computer Science, 2013, 40(6):155-159.)
[2] COLLBERG C, THOMBORSON C, LOW D. A taxonomy of obfuscating transformations, TR #148[R]. Auckland, New Zealand:University of Auckland,1997.
[3] COLLBERG C, THOMBORSON C, LOW D. Manufacturing cheap, resilient, and stealthy opaque constructs[C]//Proceedings of the 25th ACM SIGLAN-SIGACT Symposium on Principles of Programming Languages. New York:ACM, 1998:184-196.
[4] COLLBERG C, THOMBORSON C, LOW D. Breaking abstractions and un-structuring data structures[C]//ICCL'98:Proceedings of 1998 International Conference on Computer Languages. Piscataway, NJ:IEEE, 1998:28-38.
[5] COLLBERG C S, THOMBORSON C D, LOW D W K. Obfuscation techniques for enhancing software security:US, 6668325[P]. 2003-12-23.
[6] ARBOIT G. A method for watermarking Java programs via opaque predicates[C/OL]//Proceedings of the 2002 International Conference on Electronic Commerce Research.[2016-10-16]. http://profs.scienze.univr.it/~giaco/download/Watermarking-Obfuscation/sp-paper.pdf.
[7] MYLES G, COLLBERG C. Software watermarking via opaque predicates:implementation, analysis, and attacks[J]. Electronic Commerce Research, 2006, 6(2):155-171.
[8] 袁征,冯雁,温巧燕,等.构造一种新的混淆Java程序的不透明谓词[J].北京邮电大学学报,2007,30(6):103-106.(YUAN Z, FENG Y, WEN Q Y, et al. Manufacture of a new opaque predicate for Java programs[J]. Journal of Beijing University of Posts and Telecommunications, 2007, 30(6):103-106.)
[9] WANG C X. A security architecture for survivability mechanisms[D]. Charlottesville, VA:University of Virginia, 2001:65-68.
[10] 吴伟民,林水明,林志毅.一种基于混沌不透明谓词的压扁控制流算法[J].计算机科学,2015,42(5):178-182.(WU W M, LIN S M, LIN Z Y. Chaotic-based opaque predicate control flow flatten algorithm[J]. Computer Science, 2015, 42(5):178-182.)
[11] 陈代梅,范希辉,朱静,等.基于同余方程和中国剩余定理的混淆算法[J].计算机应用研究,2015,32(2):485-488.(CHEN D M, FAN X H, ZHU J, et al. Obfuscation algorithms based on congruence equation and Chinese remainder theorem[J]. Application Research of Computers, 2015, 32(2):485-488.)
[12] 王兴元,朱伟勇.二维Logistic映射中混沌与分形的研究[J].中国图象图形学报,1999,4(4):340-344.(WANG X Y, ZHU W Y. Researches on chaos and fractal of the coupled Logistic map[J]. Journal of Image and Graphics,1999, 4(4):340-344.)
[13] 潘承洞,潘承彪.简明数论[M].北京:北京大学出版社,1998:150-162.(PAN C D, PAN C B. Simplified Number Theory[M]. Beijing:Peking University Press, 1998:150-162.)
[14] 赵玉洁,汤战勇,王妮,等.代码混淆算法有效性评估[J].软件学报,2012,23(3):700-711.(ZHAO Y J, TANG Z Y, WANG N, et al. Evaluation of code obfuscating transformation[J]. Journal of Software, 2012, 23(3):700-711.)
[15] LACCHIA M. Radon:a code metrics tool in Python[EB/OL].[2016-10-16]. https://pypi.python.org/pypi/radon.

基于同余方程和改进的压扁控制流的混淆算法

Obfuscating algorithm based on congruence equation and improved flat control flow

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

[1]	房鼎益, 党舒凡, 王怀军, 董浩, 张凡. 具有时间多样性的JavaScript代码保护方法[J]. 计算机应用, 2015, 35(1): 72-76.
[2]	周治平庄学波. 基于P-ECC和同余方程的分簇WSN节点身份认证机制[J]. 计算机应用, 2014, 34(1): 104-107.
[3]	姜子峰曾光裕王炜高洪博. BIOS陷门实现机理及检测技术研究[J]. 计算机应用, 2013, 33(02): 455-459.
[4]	郑天翔. 基于三次同余方程的增强的Rabin密码体制[J]. 计算机应用, 2009, 29(07): 1803-1805.
[5]	李伟方江涛郝林 . 同余方程加密方案的研究[J]. 计算机应用, 2006, 26(9): 2114-2115.