代码混淆技术作为一类重要的软件保护方法，常用于现代工业工程中的控制与调度软件保护领域，基本思想是对代码在功能等价的前提下进行转换，令转换后的代码更难于阅读和理解软件功能的设计与算法^[1]。在代码混淆效果的度量方面，Collberg等^[2]提出了4个评价标准：健壮性、弹性、隐蔽性和执行代价。其中健壮性是指混淆算法对程序增加的复杂度，例如程序长度复杂度、圈复杂度、嵌套复杂度、数据结构复杂度、数据流复杂度和扇出/扇入复杂度等；执行代价是指由代码转换带来的系统开销，包括内存空间和运行时间等。在一定程度上，各项复杂度可以作为混淆效果的直观反映。然而，某些复杂度之间可能会存在冲突。例如应用压扁控制流技术进行代码混淆时，会在增大圈复杂度的同时可能降低嵌套复杂度。因此，采用多目标优化进化算法(multi-objective evolutionary algorithms，MOEAs)成为解决此问题的方法之一。基于快速非支配排序和精英策略的多目标优化遗传算法NSGA-II (fast and elitist non-dominated sorting in genetic algorithms)^[3]是多目标优化算法中的经典算法，目前被广泛地运用在各行各业以寻找最优方案，例如多目标电网规划^[4]、水资源优化配置^[5]和航空运输优化^[6]等应用场合。Martinez^[7]、Bertholon等^[8]曾经提出运用多目标优化遗传算法解决代码混淆问题，但对遗传算法的部分核心操作进行了简化，例如省略了极其重要的交叉操作，并且实验使用的代码混淆技术对目标函数影响较小而导致复杂度增减速率过慢。

在实际应用中，往往需要反复调用代码混淆技术获得具有理想的复杂度的程序以尽量保证足够安全。本文从工业工程实践的角度，应用NSGA-II算法解决在多次、多种调用代码混淆技术过程中的复杂度冲突问题，从代码健壮性和执行代价这两方面的多项复杂度作为优化目标，运用树形编码设计，完整实现选择、变异和交叉操作，最终获得较优的代码混淆技术调用序列作为可行解。

1 基于NSGA-II的代码混淆问题算法设计 1.1 多目标优化代码混淆问题的数学模型

多目标代码混淆问题可以描述为：对于原代码P，存在代码混淆技术集合Τ，多次应用t_i∈Τ作用于P，直至得到满足代码复杂度指标集合C的混淆后代码P'。即

$ \begin{split} &\qquad f(C) = \max \left\{ {{f_{\rm{h}}}\left( {{c_{\rm{h}}}} \right),{f_{\rm{c}}}\left( {{c_{\rm{c}}}} \right),{f_{\rm{n}}}\left( {{c_{\rm{n}}}} \right),{f_{{\rm{ds}}}}\left( {{c_{{\rm{ds}}}}} \right)} ,{f}_{\rm{d}\rm{f}}\left({c}_{\rm{d}\rm{f}}\right),\right.\\ &{f}_{\rm{f}}\left({c}_{\rm{f}}\right),{f}_{\rm{m}}\left({-c}_{\rm{m}}\right), {f}_{\rm{t}}\left({-c}_{\rm{t}}\right)\}{\text{。}} \end{split}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! $

(1)

式(1)中， $C=\{{c}_{\rm{h}},{c}_{\rm{c}},{c}_{\rm{n}}, {c}_{\rm{d}\rm{s}}{,c}_{\rm{d}\rm{f}},{c}_{\rm{f}},{c}_{\rm{m}},{c}_{\rm{t}}\}$ ，分别为以下8种常用的软件复杂度指标^[1,7]。

程序长度复杂度c_h 　 c_h = η₁ + η₂，η₁为程序P中不同运算符的个数，η₂为程序P中不同操作数的个数。

圈复杂度c_c 　 c_c = E – ω + 2，E为控制流图中的边数，ω为控制流图中的节点数。

嵌套复杂度c_n 　 c_n=λ−1，λ为程序P中代码块的最大嵌套深度。

数据结构复杂度c_ds 　为方便计算并且不影响评估效果，将c_ds简化定义为 $ {c}_{\rm{d}\rm{s}}= {\vartheta }_{\rm{b}}+{2\vartheta }_{\rm{s}}+4{\vartheta }_{\rm{i}}+8{\vartheta }_{\rm{l}}+$ $4{\vartheta }_{\rm{c}}+4{\vartheta }_{\rm{f}}+8{\vartheta }_{\rm{d}}+4{\vartheta }_{\rm{b}\rm{o}\rm{o}\rm{l}}$ ，其中ϑ_b、ϑ_s、ϑ_i、ϑ_l、ϑ_c、ϑ_f、ϑ_d、ϑ_bool分别为程序P中byte、short、int、long、char、float、double和boolean类型常量和变量的个数。

数据流复杂度c_df 　 ${c_{{\rm{df}}}}\; =\; {d_{{i_1}}} \;+ \;{d_{{i_2}}} \;+\; \cdots \;+ \;{d_{{i_o}}} $ (o=1, 2, ···)，d_ij为程序P中变量i_j在其他代码块中的操作总次数。

扇入扇出复杂度c_f 　 c_f=f_inf_out，f_in为程序P中扇入总次数，f_out为程序P中扇出总次数。

内存空间复杂度c_m 　 c_m=k₁+k₂+k₃，k₁、k₂和k₃分别为程序P中对象头占用字节数、实例数据占用字节数和对齐填充占用字节数。

时间复杂度c_t 　 c_t=t₂−t₁，t₁为程序P开始运行时时间节点，t₂为程序P运行结束时的时间节点。

1.2 NSGA-II与代码混淆的适配

为设计将NSGA-II适配于求解代码混淆问题的算法框架，首先给出以下定义。

定义1(个体)：由类、类属性、类方法以及类外部属性所组成的一份完整可运行的程序代码，记作I；当表示第n代个体时，记作Iⁿ(n=1, 2, ···)。

定义2(原始个体)：对原代码使用一次代码混淆技术所得到的代码，也称作初代个体，记作I⁰。

定义3(种群)：由多个相同进化代数的个体I组成的集合，记作 ${\xi }^{j}=\left\{{I}_{1}^{j},{I}_{2}^{j},\cdots,{I}_{i}^{j}\right\}$ ， $(i,j={\rm{1,2}},\cdots ,n) $ ，其中j为种群代数。记ξ¹为原始种群。

定义4(退化个体)：当I具有以下情况之一时，称为退化个体。退化个体记作I_err：

1) 不能通过编译器编译；

2) 编译后程序执行出错；

3) 对于同一输入，其输出与源代码的输出不一致。

定义5(变异操作)：在第n代中任意选择 $I_i^n $ ，(i=1, 2, ···, n)使用一次代码混淆技术的过程，记作τ。

定义6(交叉操作)：在第n代中任意选择 $I_i^n$ ， $I_j^n $ ，(i, j=1, 2, ···, n)(i≠j)，将 $I_i^n $ 和 $ I_j^n$ 中的部分染色体进行交换的过程，记作σ。

定义7(选择操作)：令 $ {\xi }^{n+{n}'}=\left\{{{I}_{1}^{n},{I}_{2}^{n},\cdots ,{I}_{i}^{n},{I}_{1}^{{n}'},}\right.$ $\left. {{I}_{2}^{{n}'},\cdots ,{I}_{i}^{{n}'} }\right\} , \; i={\rm{1,2}},\cdots ,n$ ，其中 ${\xi }^{{n}'}=\left\{{I}_{1}^{{n}'},{I}_{2}^{{n}'},\cdots ,{I}_{i}^{{n}'}\right\}$ 为由 ${\xi }^{n}=\left\{{{I}_{1}^{n},{I}_{2}^{n},\cdots ,{I}_{i}^{n}}\right\}$ 经过若干次τ和σ操作后得到。对ξ^n+n'进行带精英策略的非支配排序和适应度计算后筛选出有效个体I组成 ${\xi }^{n+1}=\left\{{I}_{1}^{n+1},{I}_{2}^{n+1},\cdots ,\right.$ $\left.{ {I}_{i}^{n+1}} \right\}, \; i={\rm{1,2}},\cdots ,n$ ，记作ρ。

定义8(个体验证)：对 ${\xi }^{{n}'}=\left\{{I}_{1}^{{n}'},{I}_{2}^{{n}'},\cdots ,{I}_{i}^{{n}'}\right\}$ ， $(i= $ ${\rm{1,2}},\cdots ,n) $ 验证 ${I}_{?}^{{n}'}$ 是否符合I_err特征，若不符合，则将 ${I}_{?}^{{n}'}$ 加入ξⁿ⁺¹。

定义9(个体评价)：通过代码复杂度指标集合C进行衡量I的质量。本文设 $C=\{{c}_{\rm{h}},{c}_{\rm{c}},{c}_{\rm{n}}, {c}_{\rm{d}\rm{s}}{,c}_{\rm{d}\rm{f}},{c}_{\rm{f}},$ $ {c}_{\rm{m}},{c}_{\rm{t}}\}$ 。每个I的复杂度维度记作 $I({c}_{\rm{h}},{c}_{\rm{c}},{c}_{\rm{n}}, {c}_{\rm{d}\rm{s}}{,c}_{\rm{d}\rm{f}},{c}_{\rm{f}},$ $ {c}_{\rm{m}},{c}_{\rm{t}})$ 。

基于NSGA-II解决代码混淆问题的算法设计框架如图1所示，主要步骤如下。

Step1 　设定软件复杂度目标函数及其他参数，包括确立目标函数集合C、种群数量m、最大进化代数g_max和迭代更新个体量q。

Step2 　初始化原始个体的种群。令g=1，对原代码P多次执行τ操作，得到若干个个体组成初代种群 ${\xi }^{1}=\left\{{I}_{1}^{1},{I}_{2}^{1},\cdots , {I}_{m}^{1}\right\}$ ，计算复杂度和适应度，并进行快速非支配排序。

Step3 　种群进化。在第g代种群 ${\xi }^{g}=\left\{{{I}_{1}^{g},{I}_{2}^{g},\cdots, }\right.$ $\left. {{I}_{m}^{g}}\right\}, \; (g\in {\rm{N}}^{+},g {\text{≤}} {g}_{\rm{m}{\rm{a}}{\rm{x}}}) $ 中选择 ${I}_{i}^{g}, \;{I}_{j}^{g}, \;\left(i,j={\rm{1,2}},\cdots ,m\right)(i\ne $ j)执行σ操作；然后选择 ${I}_{i}^{g},(i={\rm{1,2}},\cdots ,m)$ 执行τ操作；产生的子代通过个体验证后加入临时种群ξ^g'。直至|ξ^g'|=q时，执行ρ操作，得到第g+1代种群ξ^g+1，g=g+1。

Step4 　判断是否满足NSGA-II结束条件。若g≤g_max，则返回Step3，否则退出。

Step5 　根据Pareto解集获取可行解，即混淆后代码集合。

1.3 树形结构编码设计

采用二叉树结构编码的遗传算法，最终能收敛到全局最优解，该结论可推广至一般树形结构编码的遗传算法。因此采用抽象语法树(abstract syntax tree, AST)^[9]结构对个体基因进行编码，以描述代码如何从文法的初始符号开始推导出任意句子。在AST中，从左到右依次联结所有叶子节点则可生成该树所表示的代码。

定义10(基因)：使用AST结构描述I。AST中的每个结点都为I的基因。基因分为2类：语句基因和文法基因。AST中的叶子结点属于语句基因，是保存代码语句信息的遗传因子；非叶子结点属于文法基因，是保存子结点文法信息的遗传因子。

定义11(染色体)：染色体由基因组成。用A → X₁. X₂. $ \cdots$ . X_n表示I的染色体，其中A代表语句基因，X_i代表文法基因。其本质是一个路径表达式，即AST中从根结点到叶子结点所产生的路径。例如代码System.out.println(“Hello World”)的AST可用图2表示。其中，System→MethodInvocation. TypeName. Package OrTypeName为一条染色体。

树型结构可采用Common LISP语言^[10]中的前置标识表达式来描述成字符串，如下所示

$ \begin{split} & \qquad T\left( {\chi ,A} \right) = \left( {{\chi _1}\left( {{\chi _2}\left( { \cdots \left( { \cdots {A_1}} \right) \cdots } \right) \cdots } \right.} \right. \left. {\left. {{\chi _n}\left( { \cdots \left( { \cdots {A_n}} \right) \cdots } \right)} \right)} \right),\\ & \;\;{n \in {N^ + }} {\text{。}} \end{split}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! $

(2)

式(2)中，A_i代表叶子节点(语句基因)，χ_i代表非叶子节点(文法基因)。

在进行结构编码时,源点总是根结点,在S式中位于第一个“(”之后；父结点与子结点以一对括号相隔；兄弟结点位于同一对括号内；左右括号总是成对出现。例如，图2可用S式表示为T = (MethodInvocation (TypeName (PackageOrTypeName System) (.) (out)) (.) (println) (“(“) (argumentList (expression (literal “Hello World”))) (“)”))。

采用AST进行代码的编码具有明显优势：

1) 当需要对某种类型的代码进行定位时，可通过文法基因迅速找到所有的代码位置；

2) 当进行染色体突变或互换时，可直接在AST的子树上修改或嫁接。

2 NSGA-II算法中的关键操作 2.1 变异算子操作策略

变异操作是个体中的染色体发生突变产生新个体的过程，可分为变量/常量变异和方法变异。

1) 变量/常量变异。指携带变量/常量基因的染色体发生突变，例如字符串加密混淆技术可把字符串常量加密成密文；改变变量存储方式混淆技术可将所有变量改用数组存储。

2) 方法变异。在一般情况下，代码中的一个方法包含有多条染色体。例如，压扁控制流代码混淆技术会改变程序结构，导致基因重组成新的染色体，从而达到方法变异的目的。图3展示了个体I中的某方法fun(其结点产生路径为···χ₁χ₄)的变异过程。首先对方法fun应用某种代码混淆技术得到功能等价的fun′；然后将fun′替换fun，此时个体I演变为I′。I′仍然需要通过个体验证方可加入种群。

然而需要注意，对于一份待混淆代码，可使用的混淆技术大致上可分为3大类：可任意重复应用的技术、混淆技术之间存在制约关系的技术^[11]和仅可应用一次的技术。变异操作需要注意保持多样性和进化效率之间的平衡：过于强调保持多样性，即为了获得较大的搜索范围，则有可能导致进化方向性不够集中，导致收敛速度慢；过于强调进化效率，即过于“贪婪”则收敛速度快，但容易陷入局部最优。所以，注重种群多样性的策略搜索能力强但进化效率往往较低；注重进化效率的策略搜索能力则速度快但往往多样性保持不佳。

在多目标优化算法执行周期中，应当根据混淆技术的特征，在周期的各个阶段调用各种混淆技术时有所侧重：在初期阶段，应当尽量多调用可重复应用的混淆技术，尽可能少用仅能应用一次的混淆技术；在中期阶段，可能适当增大调用混淆技术之间存在制约关系的混淆技术的概率；在后期则可以考虑使用仅能调用一次的混淆技术。多目标优化算法执行周期的分段会影响算法的性能，应当尽量保证算法在初期可以获得较大的搜索范围，而在后期可以快速收敛至全局最优。

本文通过计算迭代过程中相关决策方案的匹配概率，使用轮盘赌策略进行自适应选择，并分配决策执行相关代码混淆的方案。定义代码混淆的解决方案域solution={D₁,D₂,D₃}为3个元素的非空有限集合，表示决策方案的属性集，分别为可重复应用的技术、混淆技术之间存在制约关系的技术、仅可应用一次的技术。

决策方案D₁当前决策匹配概率Η₁的计算如下

$ \qquad {H}_{1}\left(x\right)={H}_{0}{\rm{e}}^{-\theta x}{\text{。}} $

(3)

式中，H₀、θ分别为区间[0,1]上的非0系数，而x∈[0,x_max]，x为当前迭代次数，x_max为最大的迭代次数，随着迭代次数的增加，H₁(x)单调递减。

决策方案D₂当前决策匹配概率H₂的计算如下

$ \qquad {H}_{2}\left(x\right)={\rm{e}}^{-\frac{{(x-\mu )}^{2}}{2{\varepsilon }^{2}}}-0{\text{。}} $

(4)

式中，μ、ε分别为区间[0,1]上的非0系数，而μ∈[0,x_max/2]，而x∈[0,x_max]。当x=μ时，H₁(x)取最大值，H₁(μ)=1，为使匹配概率均衡，则ε与μ数量级相同。

决策方案D₃当前决策匹配概率H₃的计算如下

$ \qquad {H_3}\left( x \right) = \left\{ {\begin{array}{*{20}{l}} {\!\!\!1 - {H_1}\left( x \right) - {H_2}\left( x \right),} & {{H_1}\left( x \right) + {H_2}\left( x \right) {\text{＜}} 1};\\ {0,} & {{H_1}\left( x \right) + {H_2}\left( x \right) {\text{≥}} 1}{\text{。}} \end{array}} \right. $

(5)

式(5)中，H₁和H₂分别是当前决策方案D₁和D₂的匹配概率，D₁、D₂、D₃决策方案的当前匹配概率相加为1。

2.2 基于树型编码的PMX交叉算子

交叉操作是指将两个个体之间的部分染色体进行互换。在代码混淆问题中，则是指选择两份代码，把两份代码内部中具备相同功能的代码块进行交换，从而产生两份新的源代码。本文采用部分映射交叉(partially-mapped crossover，PMX)算子^[12]，通过建立两份代码的常量、变量和方法的映射关系，必要时修改与交叉内容相关的基因值以解决常量、变量、方法交换后无法正常运行代码的问题。在交叉过程中，以AST树为具体的操作对象，采用节点交叉的策略，将AST的子树作为一个整体进行交叉，即在两个父代个体中选择可对应的交叉点，以交叉点作为根结点的子树进行交换，生成两棵新的AST树，即两个新个体。例如选择两份代码中用途相同但名字不同的常量进行交叉，需先建立常量名之间的映射关系，在两个常量交换后再根据映射关系修改所有使用到这两个常量名的代码。

在采用PMX算子时，需要先对父代作常规的两点交叉，再根据交叉区域内各基因值之间的映射关系来修改交叉区域之外的各个基因座的基因值。通过映射关系修改交叉区域外的染色体可确保个体的结构完整性,提高交叉后的存活率。本文中个体采用的树型基因编码会发生染色体长度不一的情况，因此不可采用传统PMX算子中相同长度染色体下基因一一映射的方式，而是应当根据染色体中的代码语句功能是否相同来确定是否进行映射，例如，I₁和I₂中的交叉区域同时包含变量名的语句基因即可进行映射。本文提出基于树型编码的PMX交叉算子，实施步骤如下。

Step1 　对选定的个体I₁和I₂，确定I₁和I₂中的交叉点r₁和r₂，分别以r₁和r₂为根结点的子树为待交叉区域，要求子树包含的代码为变量、常量声明语句或方法。

Step2 　交换I₁和I₂的交叉区域，如图4所示。

Step3 　根据交叉区域建立变量或常量映射关系并修改。把交叉区域中具有相同功能但名字不同的变量或常量χ₁、χ₂节点建立映射关系，通过映射关系把I₁所有操作χ₁语句中的χ₁修改成χ₂，同理对I₂操作。

Step4 　扇出检测。检查I₁交叉区域中所调用的某些方法是否存在产生的子代中，如果不存在，则嫁接该方法的子树至子代中，以确保子代能够正常运行。

加入扇出检测改进后的PMX算子的搜索空间更广，局部搜索能力得到增强，更容易跳出局部最优。对于多目标优化来说，在Pareto前沿的完整性、均匀分布性和收敛性上都会有显著改善。

将基于树型编码的PMX算子引入NSGA-II算法避免了因搜索范围扩大，导致局部最优以及进化过程不稳定的问题，使Pareto最优解能均匀地扩展到整个Pareto域，提高Pareto最优解的质量，并将此算法应用于代码混淆问题中，可提供尽可能多的具有代表性的非劣解，而且有利于获得更合理的混淆方案。

2.3 交叉率p_σ和变异率p_τ的确定

遗传算法在进化过程中，进化进程与交叉率和变异率的取值有很大关系，p_σ取值越大，新个体产生的速度越快；但当p_σ取值过小时会使搜索过程缓慢甚至停滞。当变异概率p_τ取值过小时，不易产生新的结构；当p_τ取值过大时，遗传算法就会变成纯粹的随机搜索算法。本文采取自适应的遗传算法^[13]。根据交叉率和变异率对遗传算法群体进化过程中的影响，设计如下公式进行自适应调整。

$ \qquad {p_{\text{σ}}} = \left\{ {\begin{array}{*{20}{c}} {{p_{{{\text{σ}}_{\rm{1}}}}} - {p_{{{\text{σ}}_{\rm{2}}}}}\dfrac{{{\rm{fi}}{{\rm{t}}_{\rm{c}}} - {\rm{fi}}{{\rm{t}}_{{\rm{avg}}}}}}{{{\rm{fi}}{{\rm{t}}_{{\rm{max}}}} - {\rm{fi}}{{\rm{t}}_{{\rm{avg}}}}}},}\\ {{p_{{{\text{σ}}_1}}},} \end{array}} \right.\;\;\;\;\;\begin{array}{*{20}{c}} \!\!\!\!\!{{\rm{fi}}{{\rm{t}}_{\rm{c}}} {\text{≥}} {\rm{fi}}{{\rm{t}}_{{\rm{avg}}}};}\\ {{\rm{fi}}{{\rm{t}}_{\rm{c}}} {\text{＜}} {\rm{fi}}{{\rm{t}}_{{\rm{avg}}}}{\text{。}}} \end{array} $

(6)

$ \qquad {P_{\text{τ}}} = \left\{ {\begin{array}{*{20}{c}} {{P_{{{\text{τ}}_1}}} - {P_{{{\text{τ}}_2}}}\dfrac{{{\rm{fi}}{{\rm{t}}_{\rm{c}}} - {\rm{fi}}{{\rm{t}}_{{\rm{avg}}}}}}{{{\rm{fi}}{{\rm{t}}_{{\rm{max}}}} - {\rm{fi}}{{\rm{t}}_{{\rm{avg}}}}}}},\\ {{P_{{{\text{τ}}_1}}}}, \end{array}} \right.\;\;\begin{array}{*{20}{c}} {{\rm{fi}}{{\rm{t}}_{\rm{c}}} {\text{≥}} {\rm{fi}}{{\rm{t}}_{{\rm{avg}}}};}\\ \;\;\;{{\rm{fi}}{{\rm{t}}_{\rm{c}}} {\text{＜}} {\rm{fi}}{{\rm{t}}_{{\rm{avg}}}}{\text{。}}} \end{array} $

(7)

式中，fit_c为两个交叉父代个体中适应度值较大的个体；fit_avg为每一代群体的平均适应度值；fit_max为群体中适应度值最大的个体。

当个体的适应度值小于平均值时，采用较高的p_σ和p_τ，使个体进化成为优秀个体的概率增大；当个体的适应度值大于平均适应度值时，采用较低的p_σ和p_τ，这样可以确保优秀个体的结构不容易被改变。

2.4 基于锦标赛制的选择操作

采用二元锦标赛选择法进行选择操作。通过τ、σ产生的子代记作 ${\xi ^{n'}} = \left\{ {I_1^{n'},I_2^{n'}, \cdots ,I_q^{n'}} \right\},( {n' \in {{\rm{N}}^ + },}$ $ n' {{\text{≤}} g} )$ ，在ξⁿ∪ξ^n'中包含m+q个个体，采用随机配对方式对所有I个体进行比较选择，具体步骤如下。

Step1 　对ξⁿ∪ξ^n'进行非支配排序。利用I的多个复杂度进行比较，其中c_h、c_c、c_n、c_ds、c_df、c_f数值较大的I支配数值较小的I；对于c_m，则数值小的I支配数值大的I。计算每一维的支配数Oⁱ与被支配数Kⁱ，得到 $\zeta =\displaystyle \sum\limits _{n=1}^{i}{O}^{n}$ ， $\gamma =\displaystyle \sum\limits _{n=1}^{i}{K}^{n}$ ，其中ζ+γ=m+q−1。ζ越高、γ越低的I支配等级越高，以此对ξⁿ∪ξ^n'从高到低的支配等级排序。

Step2 　计算ξⁿ∪ξ^n'的适应度。在8种代码复杂度中可选择一种作为适应度，本文选择c_t作为适应度，因为只有c_t在合理的范围中，才能被称作“生存能力”强的个体。

Step3 　选择比较个体。在ξⁿ∪ξ^n'中，不以个体中的支配等级、适应度、复杂度作比较，使用随机选择算法选出I_iⁿ和I_jⁿ, $i,j={\rm{1,2}},\cdots ,m ; \; i\ne j$ 。

Step4 　选出列入ξⁿ⁺¹的I。在I_iⁿ和I_jⁿ中使用锦标赛制比较，以支配等级和适应度作为比较指标，指标高的 $I_?^n $ 列入ξⁿ⁺¹，另一个 $ I_?^n$ 则返回ξⁿ∪ξ^n'中。重复Step3直到ξⁿ⁺¹的总数为m。

3 实验验证

本文实验验证选取了一份具有含类、方法、全局变量、局部变量、静态变量、for循环结构、while循环结构、if条件结构和switch结构的典型源代码作为混淆前原代码。为使实验结果更具代表性，选用4种对各项代码复杂度影响较大、应用较为广泛的代码混淆技术：插入垃圾代码(T_trash)、字符串加密(T_encrypt)、不透明谓词^[14](T_opaque)和压扁控制流^[15](T_chenxify)。实验分为3组，分别为包含c_h&c_t和c_df&c_m的两目标方案组、c_c&c_df&c_m和c_ds&c_df&c_m的三目标方案组和c_c&c_h&c_n&c_ds&c_df&c_f&c_m的七目标方案组。通过两目标实验方案可在平面上观察Pareto最优解集在图的分布；利用两目标和三目标实验方案的典型性，可把目标函数推广至3个以上，再最后实现七目标实验方案。在实验过程中设定如下参数：种群规模为20；每代种群产生的新个体数为10；种群进化代数上限为20。

在实验目标选择的复杂度组合中，由于各目标在进化过程中会产生冲突，所以在实验结果中根据某一代的种群数据绘制出Pareto曲面图，其中，横纵坐标轴所表示的是目标复杂度的倒数，通过绘制其倒数图使数据在图中更好地展示结果，且不影响最终Pareto曲面。

测试用例源代码的原各项复杂度如表1所示。本文进行了两目标、三目标和七目标等多种组合的实验，选取部分有代表性的结果进行描述。

3.1 两目标实验组

为了不失一般性，本文分别选取了c_h&c_t和c_df&c_m两种两目标方案的结果进行展示。

3.1.1 c_h & c_t

实验1比较了c_h和c_t的数据，其中，图5、图6展示了第13代、第16代的Pareto曲面，将复杂度取倒数构造更便于观察Pareto曲面图。图中线相连的个体即为Pareto最优解集，可发现进化代数越高最优的解集会更多，说明更多的个体在逼近最优解。图7展示了第1代—第20代种群的平均c_h和平均c_t，由于程序复杂度数值较大，难以和时间复杂度清晰地展示在同一张图，因此，图7的平均c_h数据是原有数值上缩小100倍所得。c_h和c_t的总体趋势是越来越大，但也会有局部下降，是因为由于目标冲突而产生了无效个体会被抛弃，所以图7中第5代—第6代数据有减少。

在本次实验结果中选择第20代中c_h为6 077、c_t为3的个体展示其混淆技术应用序列^[16]，即T_trash→T_chenxify→T_trash→T_encrypt→T_opaque→T_encrypt→T_opaque→T_trash →T_chenxify→T_encrypt→T_trash →T_opaque→T_chenxify→T_opaque。

3.1.2 c_df & c_m

实验2比较了c_df和c_m的数据，其中图8、图9显示了第10代、第17代的Pareto曲面图，实验2收敛的速度比实验1更快，在第10代中已经产生了4个最优解，并且在进化至17代的过程中更逼近限定的目标范围。图10展示了个体进化过程中平均c_df和平均c_m的数据图，可以发现每次执行代码混淆技术都提高了代码的复杂度，因此图10的总体趋势是上升的。

在本次实验结果中选择第20代中c_df为2 388、c_m为482的个体展示其混淆技术应用序列，即T_encrypt→T_trash→T_encrypt→T_chenxify→T_trash→T_trash→T_opaque→T_trash→T_opaque→T_trash→T_encrypt→T_opaque→T_trash→T_chenxify→T_trash→T_opaque→T_trash→T_encrypt→T_trash。

通过两组两个目标的数据，可以发现个体在进化的过程中可产生Pareto最优解集，解集中包含多个个体，可作为当代的最优个体；在种群进化过程中，目标值的趋势是越来越大，但也会产生一些超过目标函数范围的无效个体。最终求解的结果是一个解集，选择的个体仅仅展示了最优解集中的其中一个有效解。由此证明运用NSGA-II算法解决在限定的两个目标下确定最优代码混淆技术调用序列问题的可行性。

3.2 三目标实验组

三目标实验组选取了c_c & c_df & c_m和c_ds & c_df & c_m两种方案。

3.2.1 c_c & c_df & c_m

实验结果展示了个体进化过程中平均c_c和平均c_df、平均c_m的数据图，如图11所示；并选择第20代中c_c为160、c_df为11 172、c_m为520的个体展示其混淆技术应用序列，即T_trash →T_trash →T_chenxify→T_trash→T_encrypt→T_encrypt→T_encrypt→T_trash→T_encrypt→T_opaque→T_opaque→T_trash→T_encrypt→T_encrypt→T_encrypt→T_chenxify→T_trash→T_encrypt→T_encrypt→T_chenxify。

3.2.2 c_ds & c_df & c_m

实验结果展示了个体进化过程中平均c_ds和平均c_df、平均c_m的数据图，如图12所示；并选择第20代中c_ds为337、c_df为5 567、c_m为416的个体展示其混淆技术应用序列，即T_trash→T_encrypt→T_opaque→ T_chenxify→T_encrypt→T_encrypt→T_trash→T_chenxify→T_opaque→T_trash→T_chenxify→T_trash→T_encrypt→T_opaque。

3.3 七目标实验组

选取c_c & c_h & c_n & c_ds & c_df & c_f & c_m作为七目标实验组方案，实验结果展示了个体进化过程中平均c_c、平均c_h、平均c_n、平均c_ds、平均c_df、平均c_f和平均c_m的数据图，如图13所示。当7个目标同时评价的时候可以发现虽然数据上升的趋势依然是越来越大，但增加的幅度没有两个或3个目标大；图中16和17代也因多目标冲突而发生数据下降的趋势；显然限定7个目标去确定代码混淆技术调用序列更具有有效性。

4 结束语

本文从工程实践的角度去解决代码混淆应用的问题，结合NSGA-II算法，设计了一个面向多目标的代码混淆模型，针对该模型提出基于AST的树型基因编码，完善了交叉、变异和选择操作，应用8种代码复杂度指标作适应度评估，并设计不同目标种类和个数的实验方案进行了验证。实验结果表明，利用基于NSGA-II算法思想设计的代码混淆模型可以在确定代码混淆技术应用序列的基础上，最终获得质量较理想的混淆代码。未来的工作将会利用此模型继续展开研究，考虑不同的角度评价代码质量以及增加更多的代码混淆技术完善应用工具，深入关于生成最优混淆代码的方法研究。