计算机工程

• 安全技术 • 上一篇    下一篇

基于嵌套复杂度的控制流混淆算法

王磊,侯整风,向润昭,史兆鹏   

  1. (合肥工业大学 计算机与信息学院,合肥 230009)
  • 收稿日期:2015-11-16 出版日期:2016-11-15 发布日期:2016-11-15
  • 作者简介:王磊(1989—),男,硕士研究生,主研方向为软件保护技术、网络与信息安全;侯整风,教授;向润昭、史兆鹏,硕士研究生。
  • 基金项目:
    国家自然科学基金(61272540);安徽省自然科学基金(11040606M138)。

Control Flow Obfuscation Algorithm Based on Nesting Complexity

WANG Lei,HOU Zhengfeng,XIANG Runzhao,SHI Zhaopeng   

  1. (School of Computer and Information,Hefei University of Technology,Hefei 230009,China)
  • Received:2015-11-16 Online:2016-11-15 Published:2016-11-15

摘要: 采用随机插入策略的垃圾代码控制流混淆算法,存在混淆强度和额外开销的不确定性。针对该问题,提出一种基于嵌套复杂度的控制流混淆算法OB_NC,对混淆所引入的开销进行定量计算,采用嵌套复杂度对控制流复杂度进行度量,基于分组背包思想构造背包决策表,综合考虑混淆强度和开销来选择垃圾代码插入点,在开销阈值内尽可能提升混淆强度。分析和实验结果表明,OB_NC算法的混淆强度高于采用随机插入策略的控制流混淆算法,且能够有效控制混淆所产生的额外开销。

关键词: 代码保护, 控制流图, 混淆算法, 分组背包, 嵌套复杂度

Abstract: The garbage code control flow obfuscation algorithm based on random insertion strategy has uncertain obfuscation potency and extra overhead.To solve the problem,a control flow Obfuscation algorithm based on Nesting Complexity(OB_NC) is proposed.The algorithm quantitatively calculates the overhead introduced by obfuscation,measures the complexity of control flow with nesting complexity metric and selects the insertion point of garbage code considering the intensity and cost of obfuscation with the idea of decision table based on group knapsack theory,which improves the obfuscation potency as much as possible within the threshold.Analysis and experiment results show that compared with the control flow obfuscation algorithm based on random insertion strategy,the OB_NC algorithm has higher obfuscation potency and can effectively control the extra overhead caused by obfuscation.

Key words: code protection, Control Flow Graph(CFG), obfuscation algorithm, group knapsack, nesting complexity

中图分类号: