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

摘要

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