学习打卡7：scanf()函数和鲸鱼优化算法

鲸鱼优化算法"/>

学习打卡7：scanf()函数和鲸鱼优化算法

督促自己：2020-9-15

学习记录：

《逆向工程权威指南》上

scanf（）函数：

• 局部变量x：

#include<stdio.h>
int main(){int x;printf("Enter X:\n");scanf("%d",&x);printf("You entered %d...\n",x);return 0;
}

X86

• MSVC

  汇编：

• 序言中，PUSH ECX指令作用不是为了保存EXC的值，是为了在栈内分配4个字节的空间、用来储存局部变量x。

• 汇编宏_x$(其值为-4)用于访问局部变量x，而ESP寄存器用来存储栈当前帧的指针。

• lea eax,DWORD PTR _x$[ebp]指令将变量x的地址放入EAX寄存器。lea(load effective address)：将源操作数(第二个参数)给出的地址(offset)传送到目的寄存器（第一个参数）之中。这里相当于 lea eax [ebp -4]

• GCC

  GCC把printf() 换为puts()。

ARM

汇编：

scanf()函数同样要借助指针传递返回值。在本例里，编译器给它分配了一个整型变量的指针。整型数据占用4个字节的存储空间。但是返回数据的内存地址，可以直接放在CPU的寄存器中。

在生成的汇编代码里，变量x存在于数据栈中，被IDA标记为var_ 8,然而，此时程序完全可以直接使用。栈指针SP指向的存储空间，没有必要像上述代码那样机械式地调整SP分配栈空间。

此后，程序把栈指针SP (x的地址)存入R1寄存器，再把格式化字符串的偏移量存入RO寄存器，如此一来，scanf()函数就获得了它所需要的所有参数。在此之后，程序使用LDR指令把栈中的返回值复制到R1寄存器、以供printf)调用。

MIPS

全局变量x：

#include <stdio.h>
//now x is global variable
int x;
int main()
{printf ("Enter x: \n");scanf ("8d", &x);printf ("YoU entered d... \n", x);return 0;
};

• MSVC : x86

x变量的存储空间是数据段(_data 域)，反而没有使用数据栈。因此整个程序的所有指令都可以直接访问全局变量x。在可执行文件中，未经初始化的变量不会占用任何存储空间。

在某些指令在变量访问这种未初始化的全局变量的时候，操作系统会分配一段数值为零的地址给它。这是操作系统VM (虚拟内存)的管理模式所决定的。

当修改为int x = 10时，ida中可以看到很多"?"变量

这段代码里有很多带“?”标记的变量，这是未初始化的x变量的标记。这意味着在程序加载到内存
之后，操作系统将为这些变量分配空间、并填入数字零。但是在可执行文件里，这些未初始化的变量不占用内存空间。

• ARM

• 在ARM系统里，代码段的程序代码可存储于处理器的ROM (Read-Only Memory), 而可变变量存储于RAM (Random-Access Memory)中。

• 在后续代码段的指令中，程序给变量x分配了个指针(即off _2c)。此后，程序都是通过这个指针对x变量进行的操作。不这样做的话变量x可能被分配到距离程序代码段很远的内存空间，其偏移量有可能超过有关寻址指令的寻址能力。

  Thumb模式下，ARM系统的LDR指令只能够使用周边1020字节之内的变量;即使在32位ARM模式下，它也只能调用偏移量在+4095字节之内的变量。这个范围就是变量地址(与调用指令之间)的偏移量的局限。为了保证它的地址离代码段足够近、能被代码调用，就需要就近分配x变量的地址。由于在链接阶段(linker)x的地址可能会被随意分配，甚至可能被分配到外部内存的地址，所以编译器必须在前期阶段就把x的地址分配到就近的区域之内。

• MIPS

  • 无未初始值的全局变量
    以变量x为全局变量为例。我们把它编译为可执行文件，然后使用IDA加载这个程序。因为程序在声明变量x的时候没有对它进行初始化赋值，所以在IDA中变量x出现在.sbss ELF里。

  第18行处的指令对全局指针GP和一个负数值的偏移量求和，以此计算变量x在64KB数据缓冲区里的访问地址。此外，三个外部函数(puts()、 scanf()、printf()) 在64KB数据空间里的全局地址，也是借助GP计算出来的(第9行、第16行、第26行)。GP指向数据空间的正中央。经计算可知，三个函数的地址和变量x的地址都在数据缓冲区的前端。这并不意外，因为这个程序已经很短小了。

  • 有初始值的全局变量

变量x出现在了.data段里。这个段会被加载到常规的通用内存区域，我们可以在此看到变量的处理方法。

MTPS程序必须使用成对指令处理变量的地址。本例使用的是LUI(Load Upper Immediate)和ADDIU(Add Immediate Unsigned Word)指令时。

这个程序使用LUI和ADDIU指令对生成变量地址。地址的高地址位仍然存储于SS0寄存器，而且单条LW指令(Load Word)即可封装这个偏移量。所以，单条LW指令足以提取变量的值，然后把它交付给printf)函数。

scanf()函数的状态监测

​ scanf()函数在退出时会返回赋值的变量总数。

#include <stdio.h>
int main()
{int x;printf ("Enter X: \n");if (scanf ("&d", &X)==1)printf ("You entered 8d...\n", X);elseprintf ("What you entered? Huh?\n");return 0;
};

1. MSVC：x86

   • “一般地说"条件判断语句会出现成对的“CMP/cc"指令。此处cc是英文“condition code"的缩写。比较两个值的CMP指令会设置处理器的标志位。Jcc指令会检查这些标志位，判断是否进行跳转。

   • JNE（Jump if Not Equal）指令会依据ZF标志位的状态判断是否需要进行跳转。

     实际上CMP指令进行的操作是减法运算，而且，所有的“数学/算术计算”指令都会设置标志位。

2. ARM

   ARM: Optimizing Keil 6/2013 (Thumb模式)

• CMP：ARM系统的CMP与x86系统的同名指令相似。它们都是将两个参数相减，并设置相应的标志位。
• BEQ：BEQ是条件转移指令(BranchifEQual)，在CMP操作数相等的情况下进行跳转。如果CMP比较的两个值相同，则ZF标志寄存器的值就会是1，那么BEQ指令就会跳转到它指定的偏移量上去。它与x86的JZ指令作用相同。

3. MIPS

   scanf()函数通过$V0寄存器传递其返回值。地址为0x004006E4的指令负责比较$V0和$VI的值。其中，$V1在0x004006DC处被赋值为1。BEQ的作用是“Branch Equal”(在相等时进行跳转)。如果两个寄存器里的值相等，即成功读取了1个整数，那么程序将会从0x0040070C处继续执行指令。

鲸鱼算法

1、引言：

鲸鱼通常以群居为主，而其在捕食的过程中在海的表面包围着猎物（鱼和虾）同时吐出螺旋形状的气泡来捕食，该捕食行为称为气泡捕食法。气泡捕食法具体为鲸鱼首先潜入水深约 15 米处，以螺旋形姿势向水面上游动，游动过程中伴随着吐出许多大小不等的气泡，使最后吐出的气泡与第一个吐出的气泡同时上升到水面，与此同时，所吐出的气泡便构成了类似于圆柱状或管状的气泡网，有如蜘蛛所编织的网，把猎物紧紧地包围起来，并逼向网的中心，而后鲸鱼便在气泡圈内几乎直立地张开大嘴，吞下网集的猎物，如图：

鲸鱼优化(Whale Optimization Algorithm, WOA)算法是澳大利亚格里菲斯大学的Mirjalili 等于2016年提出的一种新型的群体智能优化方法，它的思想来源于海洋中座头鲸独有的特殊捕食行为，算法通过鲸鱼包围、气泡攻击猎物等过程实现优化搜索目的。该算法具有原理简单、操作简易，易于实现，需调整的参数少及鲁棒性强等特点。在函数优化方面，WOA 算法在求解精度和稳定性上要明显优于粒子群（PSO）、差分进化（DE）和 引力搜索（GSA）等算法。同时WOA 算法在许多领域得到了广泛的应用，如经济调度，光伏MPP系统，电容选址和图像分割等。

2、数学模型:

假设：鲸鱼种群的规模：N；求解问题空间的维度：D；则：

第i只鲸鱼在D维空间对应的位置为:

最优鲸鱼的位置（捕食的猎物）对应全局的最优解。

2.1 鲸鱼的包围捕食

在鲸鱼算法中，假设待优化的问题解及问题变量为最优的鲸鱼也为领头鲸的位置（猎物）所在的位置。在定义最好的鲸鱼的位置后，别的鲸鱼将会朝向该鲸鱼的位置游去从而更新自身的位置。

在 WOA 算法中，首先需要求解个体与最优鲸鱼位置（猎物）之间的距离：

式中t表示当前的迭代,

表示第t代中最好的鲸鱼的位置（猎物的位置）,
为第t 代中鲸鱼个体的位置。
随着每次的迭代更新自身的位置。常数C为摆动因子。
摆动因子C由式（2.2）计算得出：

鲸鱼根据领头鲸的位置而更新，位置更新公式如下：

其中， A 为收敛因子，由式（2.4）计算得出：

在式（2.2）和式（2.4）中，r 为[ 1,0]之间的随机数，a 随着迭代次数的增加从 2 线性递减到 0.

2.2 鲸鱼的气泡捕食（局部搜索阶段）

为模拟鲸鱼的气泡捕食行为，两种策略可描述如下：

a. 摇摆包围捕食

此阶段中鲸鱼的位置更新是通过式（2.3）来获得的。收敛因子 A 在此阶段的范围随着a 的线性递减从 2 到 0 来实现。A 为 [-a,a]之间的随机值。当随机值 A 在 [−1,1]的之间，鲸鱼的下一个位置可能在鲸鱼当前的位置和猎物的位置之间的任何一个位置。

b. 螺旋吐气泡捕食

本阶段中，鲸鱼首先计算出自身到猎物（当前为止最好的位置）之间的距离，接着鲸鱼以螺旋形姿势向上游动并吐出大小不等的气泡捕食鱼虾。该行为的数学模型如下：

式中
为第i 只鲸鱼到食物的距离, l 为 [−1,1]之间的随机值，b 为螺旋形常数。

鲸鱼在捕食的过程中有摇摆包围捕食和螺旋姿势游动吐气泡捕食两种机制，因此，假设鲸鱼执行两种捕食行为的概率各为百分之五十，也就是说，假定鲸鱼用式（2.3）或式（2.6）更新自身位置的概率各为百分之五十，该数学模型如下：

式中， p 为 ]1,0[ 之间的随机数。鲸鱼的捕食行为除了气泡捕食以外，还会随机的寻找自
己视野范围内的猎物。

2.3 鲸鱼随机搜寻猎物（全局搜索阶段）

研究人员发现，鲸鱼在捕食过程中会跟随着伙伴们的位置变换而更新自身的位置。也就是说本阶段的鲸鱼将不再跟随着最好的鲸鱼的位置而更新自身位置，而是进行随机的大范围搜索猎物因此确定自身需要更新的下一个位置。因此，在本算法是根据收敛因子 A 的值的变化使得鲸鱼在本阶段进行更大范围的搜索。当 A>1的时候，鲸鱼将进行随机搜索猎物的行为，进行全局搜索，从而避免陷入局部最优，该阶段的数学表达式如下：

式中为当前种群中随机的一只鲸鱼（或者猎物）的位置。

3. 基本鲸鱼优化算法步骤

Step1  确定鲸鱼的种群规模X,随机产生X只鲸鱼的位置。初始化算法参数a,A,C,l,p和最大迭代次数 Max_Iter； 
Step2  计算每只鲸鱼的适应度值，并进行比较，确定当前适应度值最优的鲸鱼个体，定义为X* ； 
Step3  进入算法主循环，如果p<0.5且|A|<1，每只鲸鱼个体按照公式（2.3）更新当前位置，否则按照公式（2.9）更新鲸鱼个体位置。如果p≥0.5，则每只鲸鱼个体依据公式（2.6）更新位置； 
Step4  再次对整个鲸鱼种群进行评价，找到全局最优的鲸鱼个体及其位置； 
Step5  若满足算法的终止条件(最大迭代次数)，则结束；否则转到Step2，继续进行算法迭代。 
Step6  输出全局最优解X*。

流程图：

4.实验

代码来源：.cpp

// WOA.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//#include "pch.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <assert.h>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <time.h>
#include <ctype.h>
#include <memory>
#include <crtdbg.h>
#define dim 30 //变量数量
#define Max_iteration  500 //最大代数
#define SearchAgents_no 30 //个体的数量#define maxmum 0xffff
#define PI 3.141592653
double position[dim];
double leader_pos[dim] = { 0 };
double leader_score;
double Convergence_curve[Max_iteration] = { 0 };//Convergence_curve收敛曲线
double lb = -100;
double ub = 100;
struct individual
{double position[dim];double fitness;
}ptcle[SearchAgents_no];double function_fitness(double* position) {int i;double sum = 0;for (i = 0; i < dim; i++) {sum += position[i] * position[i];}return sum;}//初始化
void initialization() {for (int i = 0; i < SearchAgents_no; i++){for (int j = 0; j < dim; j++){double randx = (double)rand() / RAND_MAX;ptcle[i].position[j] = lb + (ub - lb) * randx;}}
}double GetRand()
{return 2.0 * rand() / RAND_MAX - 1.0;
}void function_WOA() {int i, j;leader_score = maxmum;int t = 0;while (t < Max_iteration) {for (i = 0; i < SearchAgents_no; i++) {for (j = 0; j < dim; j++){if (ptcle[i].position[j] > ub) {ptcle[i].position[j] = ub;}if (ptcle[i].position[j] < lb) {ptcle[i].position[j] = lb;}}ptcle[i].fitness = function_fitness(ptcle[i].position);if (ptcle[i].fitness < leader_score) {leader_score = ptcle[i].fitness;memcpy(&leader_pos, &ptcle[i].position, sizeof(double) * dim);}}double a = 2 - t * (2 / Max_iteration);double a2 = -1 + t * ((-1) / Max_iteration);for (i = 0; i < SearchAgents_no; i++) {double r1 = (double)rand() / RAND_MAX;double r2 = (double)rand() / RAND_MAX;double A = 2 * a * r1 - a;double C = 2 * r2;double b = 1;double l = (a2 - 1) * (double)rand() / RAND_MAX + 1;double p = (double)rand() / RAND_MAX;double x_rand[dim];double D_X_rand[dim];double D;for (j = 0; j < dim; j++) {if (p < 0.5) {if (abs(A) >= 1) {int	rand_leader_index = floor(SearchAgents_no * (double)rand() / RAND_MAX + 1);memcpy(&x_rand, &ptcle[rand_leader_index].position, sizeof(double) * dim);D_X_rand[j] = abs(C * x_rand[j] - ptcle[i].position[j]);ptcle[i].position[j] = x_rand[j] - A * D_X_rand[j];}else if (abs(A) < 1) {double D_leader = abs(C * leader_pos[j] - ptcle[i].position[j]);ptcle[i].position[j] = leader_pos[j] - A * D_leader;}}else if (p > 0.5) {double distance2Leader = abs(leader_pos[j] - ptcle[i].position[j]);ptcle[i].position[j] = distance2Leader * exp(b*l)*cos(l * 2 * PI) + leader_pos[j];}}}t = t + 1;Convergence_curve[t] = leader_score;printf("%.12f\n", Convergence_curve[t]);}}int main()
{initialization();function_WOA();}

参考文献：

[1]凌颖. 鲸鱼优化算法及其应用研究[D].广西民族大学,2018.

[2]陈亚环. 混合群智能算法及其在聚类分析中的应用研究[D].西安电子科技大学,2018.

 
 
明日任务：《逆向工程权威指南》上 第八章