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

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

 

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

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

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

 

应用二:路由算法

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

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

如下为C++代码:

[sourcecode language="plain"]
#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;
}

[/sourcecode]

 

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

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

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

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

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

 

*本文为华盟网原创投稿文章,作者:crown prince,如需转载请保证文章未删减并注明出处:华盟网*

本文由 华盟网 作者:AlexFrankly 发表,其版权均为 华盟网 所有,文章内容系作者个人观点,不代表 华盟网 对观点赞同或支持。如需转载,请注明文章来源。

0

相关文章

发表评论

电子邮件地址不会被公开。