Dijkstra(最短路径)算法在网络安全中的应用

AlexFrankly 2018-3-15 原创推荐 0 0

本文作者crown prince:全国青少年信息学奥赛选手、算法爱好者

Dijkstra算法是一种求解最短路径问题的经典算法,C++中利用了贪心思想与优先队列,具体来说:“设定一个保存到每个点最短路径的数组:shortlen[],默认为-1,代表无通路。从起点开始,用每一个与起点相连的且没有被访问过的点的距离对shortlen数组进行更新,例如:第i个点与起始点的距离为x,x小于无穷,那么就把shortlen[i]的值更新为x。”只要有通路的点,全部放入优先队列然后把这个点记为被访问过。 然后就从队列里取出队头,将其当做新的起点,重新进行上面的操作。 当队列为空时跳出循环,这个时候shortlen数组的值就是起点到各个点的最短距离。

 

应用一:入侵意图识别系统

入侵意图识别系统中,通过结合实时更新的我方主机脆弱性(程度)、入侵者攻击成功概率大小两个因素,通过量化两台主机的连接关系,构建了我方的主机“网络”图。通过Dijkstra算法,迭代寻找出安全性最低的路径,同步进行相应防御。

(上图来自《计算机与现代化》上的论文)

 

应用二:路由算法

路由算法旨在找到一条从源路由器到目的路由器的“好”路径(即费用最低),路由算法提高了路由协议的功能,而Dijkstra算法恰恰满足了这一需求。

在应用时,Dijkstra算法需要整个网络拓扑和各链路的长度(或链路时延、费用),设置源结点后,一步步地寻找,每次找一个结点到源节点的最短路径,指导把所有的点都找到为止

如下为C++代码:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;

    struct node{
        int fe, v; //v是最短链路长度
    };

    int num[510], w[510], weight[510];

    struct edge{
        int ne, v, t;
    };

    struct queuee{
        int i, v;
        friend bool operator < (queuee a, queuee b){ //优先级队列如果插入的节点是结构体类型,则要在结构体中重载比较操作符函数 return a.v > b.v;
        }
    };

    node a[110];
    edge b[20100];
    priority_queue<queuee>c; //优先队列
    int n, m, p;
    int start, ending;

    int putedge(int i, int j, int v);
    int dijkstra(int s, int t);

    int main(){
        int i, x, y, z, ans; // i是循环变量, ans是两个路由间的最短距离

        scanf("%d %d %d %d", &n, &m, &start, &ending); //路由数、链路数

        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        while(!(c.empty())) //初始化队列
            c.pop();
        for(i = 1; i <= n; i++)
            a[i].v = -1;
        p = 1; // P的第一个位置
        for(i = 1; i <= m; i++){ //路由X、路由Y与链路长度 cin >> x >> y >> z;
            putedge(x, y, z);
        }
        //for(i = 1; i < p; i++)
        //    cout << b[i].t << b[i].v << b[i].ne << endl;
        //for(i = 1; i <= n; i++)
        //   cout << i << a[i].fe << endl;
        ans = dijkstra(1, n);
        cout << ans << endl;

        return 0;
    }

    int dijkstra(int s, int t){
        queuee x;
        a[s].v = 0;
        x.i = s;
        x.v = 0;
        c.push(x);
        int i, j;
        while(c.top().i != t){
            cout << c.top().i << endl; if(c.top().v == a[c.top().i].v){ i = c.top().i; j = a[i].fe; while(j){ if((a[b[j].t].v == -1) || (a[b[j].t].v > a[i].v + b[j].v)){
                        a[b[j].t].v = a[i].v + b[j].v;
                        x.i = b[j].t;
                        x.v = a[b[j].t].v;
                        c.push(x);
                    }
                    j = b[j].ne;
                }
            }
            c.pop();
        }
        return a[t].v;
    }

    int putedge(int i, int j, int v){
        b[p].t = j;
        b[p].v = v;
        b[p].ne = a[i].fe;
        a[i].fe = p;
        p++;
        b[p].t = i;
        b[p].v = v;
        b[p].ne = a[j].fe;
        a[j].fe = p;
        p++; // P的第二个位置
        return 0;
    }

 

应用三:辅助域渗透提权分析

进入内网后,我们并不是总能提权成功,这时,我们往往会选择基于当前机器,收集域、sqlserver里面的相关信息,包括所有的用户,所有的电脑,以及相关关键的组的信息。目前,已经有一款叫做Bloodhound的工具,可以帮助我们可视化、半自动化的进行域渗透。

Github地址:https://github.com/adaptivethreat/Bloodhound

可以帮助梳理攻击路径、梳理域结构

*文章为华盟网投稿原创文章,作者:crown prince。如若转载请保证文章完整并注明出处:华盟网*

转载请注明来自华盟网,本文标题:《Dijkstra(最短路径)算法在网络安全中的应用》

喜欢 (0) 发布评论