计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (8): 352-358.doi: 10.11896/jsjkx.220600149

• 信息安全 • 上一篇    下一篇

无尺寸约束的不透明谓词构建算法

王雨芳1,2, 乐德广2,3, Jack TAN3, 肖乐2, 龚声蓉2   

  1. 1 苏州大学计算机科学与技术学院 江苏 苏州 215006
    2 常熟理工学院计算机科学与工程学院 江苏 苏州 215500
    3 威斯康星大学欧克莱尔分校计算机系 威斯康星 欧克莱尔54701
  • 收稿日期:2022-06-16 修回日期:2022-11-16 出版日期:2023-08-15 发布日期:2023-08-02
  • 通讯作者: 乐德广(ledeguang@cslg.edu.cn)
  • 作者简介:(3489819475@qq.com)
  • 基金资助:
    国家自然科学基金(61972059);江苏省产学研合作项目(BY2021280);江苏省自然科学基金(BK20191475);江苏省高校“青蓝工程”中青年学术带头人培养对象项目(2019);江苏省教育科学“十四五”规划课题(C-b/2020/01/29)

Opaque Predicate Construction Algorithm Without Size Constraints

WANG Yufang1,2, LE Deguang2,3, Jack TAN3, XIAO Le2, GONG Shengrong2   

  1. 1 School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China
    2 School of Computer Science and Engineering,Changshu Institute of Technology,Suzhou,Jiangsu 215500,China
    3 Department of Computer Science,University of Wisconsin-Eau Claire,Eau Claire,Wisconsin 54701,USA
  • Received:2022-06-16 Revised:2022-11-16 Online:2023-08-15 Published:2023-08-02
  • About author:WANG Yufang,born in 1997,postgra-duate.Her main research interests include information security and so on.
    E Deguang,born in 1975,Ph.D,asso-ciate professor.His main research intere-sts include information security and cryptography.
  • Supported by:
    National Natural Science Foundation of China(61972059),Production and Research Cooperation Project of Jiangsu Province(BY2021280),Natural Science Foundation of Jiangsu Province,China(BK20191475),Qing Lan Project of Jiangsu Province in China(2019) and Program of 14th Five Year Plan of Jiangsu Province Education Science(C-b/2020/01/29).

PDF (PC)

605

摘要： 结合不透明谓词,控制流混淆可以进行语义保持的变换,从而达到代码保护的目的。然而,现有的不透明谓词容易遭受符号执行攻击且存在小符号变量问题。为了解决上述问题,结合符号变量和数组利用单数组元素嵌套和符号变量模加运算设计不等条件表达式,并提出无尺寸约束的不透明谓词构建算法。基于该算法构建的不透明谓词混淆可以令攻击者错误地将不透明谓词识别为普通谓词或者将普通谓词识别为不透明谓词,从而有效抵御符号执行攻击。此外,利用不透明谓词检测以及虚假控制流去除等测试程序,对应用了无尺寸约束的不透明谓词混淆后程序的强度、弹性及开销进行实验测试分析。测试结果表明,基于所提算法实现的不透明谓词混淆不仅具有高强度和低开销,而且在新测试环境下仍然具有较高的抗反混淆弹性。

关键词: 不透明谓词, 符号内存, 数组嵌套, 代码混淆, 符号执行

Abstract: Combined with opaque predicate,control flow obfuscation enables semantics-preserving transformations,which can achieve the purpose of code protection.However,existing opaque predicate is easily attacked by symbolic execution and has the problem of small symbolic variable.To solve the above problems,combined with symbolic variable and array,this paper designs the conditional expression of inequality by single array nesting and modulo add operation of symbolic variable,based on which an algorithm for constructing opaque predicate without size constraints is proposed.The opaque predicate obfuscation based on the proposed algorithm can incur not only false negative but also false positive issues to attackers,which effectively defends against symbolic execution attacks.Besides,the potency,resilience and cost of the program obfuscated by opaque predicate without size constraints are experimentally tested and analyzed by measuring procedures such as opaque predicate detection,bogus control flow removal and so on.Experimental results show that the opaque predicate obfuscation based on the proposed algorithm not only demonstrates excellent potency and efficient cost,but also has high resilience to anti-deobfuscation in new test environment.

Key words: Opaque predicate, Symbolic memory, Array nesting, Code obfuscation, Symbolic execution

中图分类号: 

  • TP309
[1]SCHRITTWIESER S,KATZENBEISSER S,KINDER J,et al.Protecting software through obfuscation:Can it keep pace with progress in code analysis? [J].ACM Computing Surveys,2016,49(1):1-37.
[2]HOSSEINZADEH S,RAUTI S,LAUREN S,et al.Diversifica-tion and obfuscation techniques for software security:A syste-matic literature review [J].Information and Software Technology,2018,104(5):72-93.
[3]XU H,ZHOU Y F,MING J,et al.Layered obfuscation:A ta-xonomy of software obfuscation techniques for layered security [J].Cybersecurity,2021,9(3):1-18.
[4]COLLBERG C,THOM BORSON C D,DOUGLAS L.A taxo-nomy of obfuscating transformations [R].Auckland:Department of Computer Science,University of Auckland,1997.
[5]COLLBERG C,THOMBORSON C D,DOUGLAS L.Manufacturing cheap,resilient,and stealthy opaque constructs [C]//Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages(POPL'98).New York,NY,USA:ACM,1998:184-196.
[6]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.
[7]SU Q,WU W M,ZHANG Z L,et al.Research and application of chaos opaque predicate in code obfuscation [J].Computer Science,2013,40(6):155-159.
[8]XIE X,LIU F L,LU B,et al.Mixed obfuscation of overlapping instruction and self-modify code based on hyper-chaotic opaque predicates[C]//Proceedings of 2014 Tenth International Conference on Computational Intelligence and Security.New York,NY,USA:ACM,2014:524-528.
[9]SU Q,SUN J T.Research on opaque predicate obfuscation technique based on chaotic opaque expression [J].Computer Science,2017,44(12):114-119.
[10]BALACHANDRAN V.Quantum obfuscation:Quantum predi-cates with entangled qubits[C]//Proceedings of the Eleventh ACM Conference on Data and Application Security and Privacy(CODASPY '21).New York,NY,USA:ACM,2021:293-295.
[11]TUNG Y J,HARRIS I G.Zero footprint opaque predicates:Synthesizing opaque predicates fromnaturally occurring inva-riants[C]//Proceedings of the 2021 International Conference on Detection of Intrusions and Malware,and Vulnerability Assessment.Berlin:Springer,2021:299-318.
[12]ZHANG Y F,CHEN Z B,SHUAI Z Q,et al.Multiplex symbo-lic execution:exploring multiple paths by solving once[C]//Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering.New York,NY,USA:ACM,2020:846-857.
[13]BALDONI R,COPPA E,CONO D D,et al.A survey of symbo-lic execution techniques [J].ACM Computing Surveys,2018,51(3):1-39.
[14]MING J,XU D P,WANGL,et al.LOOP:Logic-oriented opaque predicate detection in obfuscated binary code[C]//Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security.New York,NY,USA:ACM,2015:757-768.
[15]XU H,ZHOU Y F,KANG Y,et al.Manufacturing resilient bi-opaque predicates against symbolic execution[C]//Proceedings of 2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks(DSN).New York,NY,USA:IEEE,2018:666-677.
[16]LIANG H L,YU W Q,AI L,et al.A practical concolic execution technique for large scale software systems[C]//Proceedings of the Evaluation and Assessment in Software Engineering(EASE'20).New York,NY,USA:ACM,2020:312-317.
[17]XU H.Software obfuscation with layered security [D].Hong Kong:The Chinese University of Hong Kong,2018.
[18]UNIVERSITY OF ARIZONA.Tigress software [EB/OL].https://tigress.wtf/addOpaque.html.
[19]RUNOOB.Fibonacci program [EB/OL].https://www.runoob.com/cprogramming/c-examples-fibonacci-series.html.
[20]MUSLIJA A,ENOIU E.On the measurement of software complexity for PLC industrial control systems using TIQVA[C]//Proceedings of the 35th Annual ACM Symposium on Applied Computing.New York,NY,USA:ACM,2020:1556-1565.
[21]ZHAO Y J,TANG Z Y,WANG N,et al.Evaluation of code obfuscating transformation [J].Journal of Software,2012,23(3):700-711.
[22]MENST.Research trends in structural software complexity[EB/OL].https://arxiv.org/abs/1608.01533v1.
[23]CAMPWOOD.Source Moniter software [EB/OL].https://www.campwoodsw.com/sourcemonitor.html.
[24]ANGR.Angr software [EB/OL].http://angr.io/.
[25]BLUESADI.Debogus program [EB/OL].https://github.com/bluesadi/debogus.
[26]HEX RAYS.IDA Pro [EB/OL].https://hex-rays.com/IDA-pro/.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发