Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (8): 352-358.doi: 10.11896/jsjkx.220600149

• Information Security • Previous Articles     Next Articles

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)

238

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

CLC Number: 

  • 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/.
[1] ZHOU Sheng-yi, ZENG Hong-wei. Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution [J]. Computer Science, 2021, 48(12): 107-116.
[2] HUANG Zhao,HUANG Shu-guang,DENG Zhao-kun,HUANG Hui. Automatic Vulnerability Detection and Test Cases Generation Method for Vulnerabilities Caused by SEH [J]. Computer Science, 2019, 46(7): 133-138.
[3] SU Qing, LIN Ze-ming, LIN Zhi-yi, HUANG Jian-feng. Code Obfuscation Effectiveness Assessment Model Based on Nonlinear Fuzzy Matrices [J]. Computer Science, 2019, 46(4): 197-202.
[4] FANG Hao, WU Li-fa, WU Zhi-yong. Automatic Return-to-dl-resolve Exploit Generation Method Based on Symbolic Execution [J]. Computer Science, 2019, 46(2): 127-132.
[5] YE Zhi-bin,YAN Bo. Survey of Symbolic Execution [J]. Computer Science, 2018, 45(6A): 28-35.
[6] LI Hang, ZANG Lie, GAN Lu. Search of Speculative Symbolic Execution Path Based on Ant Colony Algorithm [J]. Computer Science, 2018, 45(6): 145-150.
[7] ZHANG Jing, ZHOU An-min, LIU Liang, JIA Peng and LIU Lu-ping. Review of Crash Exploitability Analysis Methods [J]. Computer Science, 2018, 45(5): 5-14.
[8] DENG Wei and LI Zhao-peng. State Merging for Symbolic Execution Engine with Shape Analysis [J]. Computer Science, 2017, 44(2): 209-215.
[9] SU Qing and SUN Jin-tian. Research on Opaque Predicate Obfuscation Technique Based on Chaotic Opaque Expression [J]. Computer Science, 2017, 44(12): 114-114.
[10] CHEN Yong and XU Chao. Symbolic Execution and Human-Machine Interaction Based Auto Vectorization Method [J]. Computer Science, 2016, 43(Z6): 461-466.
[11] LIANG Jia-biao, LI Zhao-peng, ZHU Ling and SHEN Xian-fei. Symbolic Execution Engine with Shape Analysis [J]. Computer Science, 2016, 43(3): 193-198.
[12] LI Hua, XING Yi and ZHANG Yu-rong. Modeling OpenStack Single Plane Network Based on Token Selection [J]. Computer Science, 2016, 43(11): 66-70.
[13] WU Wei-min, LIN Shui-ming and LIN Zhi-yi. Chaotic-based Opaque Predicate Control Flow Flatten Algorithm [J]. Computer Science, 2015, 42(5): 178-182.
[14] XIE Xin, LIU Fen-lin, LU Bin and GONG Dao-fu. Quantitative Evaluation for Effectiveness of Code Obfuscation Based on Multi-level Weighted Attributes [J]. Computer Science, 2015, 42(3): 167-173.
[15] WANG Zhi-wen,HUANG Xiao-long,WANG Hai-jun,LIU Ting and YU Le-chen. Program Slicing-guied Test Case Generation System [J]. Computer Science, 2014, 41(9): 71-74.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.