精华内容
下载资源
问答
  • 常见的两种搜索方法
    万次阅读 多人点赞
    2019-06-05 22:22:03

    目录

     

    广度优先搜索(BFS)

    深度优先搜索(DFS)

    爬山法(Hill Climbing)

    最佳优先算法(Best-first search strategy) 

    回溯法 (Backtracking)

    分支限界算法(Branch-and-bound Search Algorithm)

    A*算法


    广度优先搜索(BFS)

    这个不用我多说了吧……

    深度优先搜索(DFS)

    同上……

    爬山法(Hill Climbing)

    DFS的变形,不同的是每次选择的是最优的一个子结点,即局部最优解

    例如,对于8数码问题,设置一个函数表示放错位置的数目,每次选择子结点中放错最少的结点

    步骤:

    1.建立一个栈,将根结点放入栈

    2.判断栈顶元素是否是目标结点,如果是,算法结束,如果不是,进入第三步

    3.栈顶元素出栈,根据评估函数计算的顺序将此结点的子结点入栈

    4.如果栈空,则输出失败,否则,进入第二步

    最佳优先算法(Best-first search strategy) 

    是DFS和BFS的结合

    每次找到的是所有结点中最好估计值的那个结点

    找到的是全局最优解

    步骤:

    1.根据评估函数建立一个堆(或用优先队列),将根结点放入堆中

    2.判断栈顶元素是否是目标结点,如果是,算法结束,如果不是,进入第三步

    3.移出堆顶元素结点,将此结点的所有子结点加入堆

    4.如果堆空,输出失败,否则,进入第二步

    回溯法 (Backtracking)

    找到所有选择,走不通则回溯

    假定问题的解是一个向量(a1,a2,a3,...,an),其中的每个元素ai都是问题的一个元素

    步骤:

    建立一个问题的部分解v=(a1,a2,...,ak)

    若这个部分解是可行解,则继续,若不是可行解,删除ak,加入ak情况的另一种可能

    若ak的可能已经遍历完,回溯并寻找ak-1的下一个可能

    算法改进:搜索剪枝

     剪枝(pruning)可以帮助我们减少搜索空间,更快的找到解

    剪枝的思想就是就是通过某种判断,避免一些不必要的遍历过程,就是如果发现此分支不可能找到最优解,就立刻回溯

    剪枝的策略需要具体问题具体分析,这里不细讲

    回溯法框架:

    递归法

    Backtrack(k,X[1...K-1])
        if(k>n) output(X[1...N])
        else
            for each element x in S(k):
                   if(constraint(x,X[1...k-1]))
                        X[k]=x
                        backtrack(k+1,X[1...k])

    迭代法

    IterativeBacktrack()
        k=1
        while k>0
            while set S(k) is not empty
                get a new element x from set S(k)
                if(constraint(x,X[1,k-1]))
                    X[k]=x
                    if(solution(X)) output(X)
                    else k++
            k--

    分支限界算法(Branch-and-bound Search Algorithm)

    分支限界法与回溯法的区别
    1.求解目标不同 
         1.回溯法的求解目标是找出解空间树中满足约束条件的所有解
         2.分支限界法的求解目标则是尽快找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解
         3.分支限界法通常用于解决离散值的最优化问题
    2.搜索方式不同 
         1.回溯法以深度优先的方式(遍历结点)搜索解空间树
         2.分支限界法以广度优先或最小耗费优先的方式搜索解空间树
    3.对扩展结点的扩展方式不同 
         1.分支限界法中,每一个活结点只有一次机会成为扩展结点
          2.活结点一旦成为扩展结点,就一次性产生其所有儿子结点
    4.存储空间的要求不同 
         1.分支限界法的存储空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大 

    转载自最佳优先搜索(Best-First Search) 

    分支限界算法可以用来寻找最优解,在平均情况下不必穷尽搜索

    分支限界算法的搜索类似于最佳优先算法并做了一些改进(比如剪枝)

    两个要点:

    如何产生分支

    如何产生界限

    基本思想:

    用一种方法分开解空间

    用一种方法预测一系列解的最小界(lower bound),用一种方法预测最优解的最大界(upper bound)

    如果一个解的最小界超出了整个解空间的最大界,那么这个解不可能是最优的,我们就可以提前终止此分支

    分支界限适合最小化问题

    平均情况下,许多分支能较早被终止,但许多NP难问题在最坏情况下仍是指数级的

    A*算法

    个人感觉类似最佳优先算法,都是维护一个优先队列或堆,将结点按照某个值优先的情况放进去,不同的是这次需要一个估计函数h(n)

    算法思想:对于优先队列,每取出一个结点n,将他的所有儿子结点n'放入优先队列,优先级由函数f(n)计算出

    g(n):起点到结点n的代价

    h(n):结点n到终点的估计代价

    f(n)=g(n)+h(n)

    A*算法是一种启发式算法

    设h*(n)为结点n到目标结点的实际最小代价

    只要h(n)<=h*(n),那么代价就不会被高估,这个算法就可以找出最优解

    A*算法使用最佳优先策略,用来解决优化问题

    步骤:

    1.把起点放入优先队列

    2.重复如下过程:

    • 取出优先级最高的结点n,即f(n)最小的结点,作为当前要处理的结点
    • 将这个结点放入一个close表中,这个表储存父结点子结点等信息
    • 对于此结点可达的结点n':
    • ①若这个结点不在队列中,计算g(n'),h(n'),f(n'),将其加入队列,并将n设为n'的父亲
    • ②若n'在队列中,计算由n到n'的g(n')值,更小的g(n')意味着这是更好的路径,如果g(n')更小,则将n设为n'的父亲,并重新计算g(n')和f(n')
    • 停止,当:
    • ①终点被找到
    • ②队列为空,此时查找失败

    3.保存路径,从终点开始,沿着父结点移动至起点,即为路径

    更多相关内容
  • 两种常见的点云配准方法ICP&NDT

    千次阅读 2020-05-15 18:30:00
    用数学的话描述就是最小化如下一个目标函数: 求解的方法有很多,这里只介绍SVD方法 目标函数简化 我们定义两组点集的中心为 注意到最后一项 从而原式可化简为 其中 , 该目标函数的最优解求解可以分为部分,先...

    点击上方“3D视觉工坊”,选择“星标”

    干货第一时间送达

    作者:于凡

    https://zhuanlan.zhihu.com/p/96908474

    本文转载自知乎,作者已授权,未经许可请勿二次转载。

    迭代最近点算法ICP(Iterative Closest Point)

    问题描述

    假设我们有两组点集,注意这里的 P和Q 分别相对于变换前和变换后的相机参考系。我们要解决的问题是找一组 R 和 T ,使得$\mathbf{P}$中的每一个点经过变化后同 Q 中的最近点的误差之和最小。用数学的话描述就是最小化如下一个目标函数:  求解的方法有很多,这里只介绍SVD方法

    目标函数简化 

    我们定义两组点集的中心为 

      注意到最后一项

    从而原式可化简为

    其中 该目标函数的最优解求解可以分为两部分,先求第一项,再求第二项(实际上第二项最优解始终为0)

    即最小化目标函数等价于最大化

    SVD求解

    在上一步的基础上,有  

    引理1:对任意正定对称阵$AA^T$和任意正交阵$B$,有

     这个引理用Schwarz不等式很容易得到,不在这里证明了。我们的目的是什么呢?根据(1.5),我们的目的是要找一个R使得Tr(RH)最大。那由上面这个引理,我们很容易想到,如果RH是一个对称正定的形式,那对任何旋转矩阵R,显然迹只会不增。因此我们对H做SVD分解, ,那么 就是我们要找的R。因为

    是正定对称阵,则由引理1可知,对任意旋转矩阵(正交)B,都有

    即X是使得(1.5)式最大的R。

    迭代过程

    实际上刚才我们只完成了一次计算,而ICP的全称是Iterative Closest Point,即迭代最近点。我们来理解一下整个过程

    1.对P中的每个点,在Q中找到匹配的最近点。这里需要注意,并不是每次的点云都是一一匹配,点云的数量是一方面,另外可以预见的是,很容易出现多对一最近点匹配,当然,可以通过一些额外的限定在达到一对一匹配的效果。

    2.根据上述过程计算最优的R和T.

    3.利用得到的位姿作用于P,如果此时的误差大于阈值,则重新进行迭代,直到迭代次数达到阈值或者误差小于阈值。

    简单的理解,有点像梯度下降寻找极值点的过程,同样的,一个好的初值对加快ICP的收敛过程也十分重要。另外点对点的计算量十分大,复杂度为$O(mn)$,在一维的情况下,二分查找是常见的优化,对高维的情况,一个类似的过程是通过KD树来实现的。

    KD树优化匹配过程

    KD树原理

    KD树是每个节点均为K维数值的二叉树,其上的每个节点代表一个超平面,该超平面垂直于当前划分维度的坐标轴,并在该维度上将空间一分为二。其构建过程是循环选取数据点的各个维度来作为切分维度,将当前维度的中值作为划分点,递归处理各子树,直到所有数据点挂载完毕。

    KD树的一些优化

    切分维度选择的时候,一般优先选择方差大的维度开始切分。选择中值时,对数据量较大的维度,不一定严格取中值,可以随机采样一定的数据,并取采样的中值作为划分点,加快划分过程。

    一个例子

    以二维平面点(x,y)的集合(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)为例结合下图来说明k-d tree的构建过程。

    对应的是将一个二维平面逐步划分的过程

    KD树最近邻搜索过程

    我们构建KD树的目的是为了加快最近点搜索过程,那么KD树如何进行最近邻搜索呢?假设我们要搜索同(3,5)最近的点。1)从根节点(7,2)出发,将当前的最近邻设为(7,2),对KD树做深度优先遍历。以(3,5)为圆心,到(7,2 )的距离为半径画圆。对在圆外的点,如果位于左侧,则忽略左子树,位于右侧,则忽略右子树。下图忽略(8,1)的右子树。2)深度遍历子节点。以(5,4)为根节点,判断(5,4)比(7,2)更近,更换最近点,并重新剪枝。此时,(7,2)的右子树均被忽略。3)深度遍历子节点,直到遍历结束,返回最近点。

    完整伪代码如下图

    KD树构建的复杂度为O(log(m)),查找的复杂度为O(mlog(n)),所以利用KD查找最近邻的复杂度为O(mlog(n)),远小于O(mn)。

    正态分布变换NDT(Normal Distribution Transform)

    简介

    目前的配准方法,前提都是环境大部分是不变的,但是完全不变的环境其实也是很少的,比如一辆车飞驰而过,一个人走过等。我们更多应该考虑的是允许小部分差异的配准,这时候点对点匹配比如ICP就会出现一些问题,而NDT则可以很好地解决细微差。我们知道,如果随机变量满足正态分布,那么对应的概率密度函数(PDF)为

    对随机向量则有

    其中D表示维数, 表示协方差矩阵。简单来说,一维的数变成了高维的向量。

    目标函数

    与ICP不同,NDT假设点云服从正态分布,我们的目的是找一个姿态,使得当前扫描点位于参考扫描平面上的可能性最大。假设当前扫描得到的点云为 ,用空间转换函数 来表示使用姿态变换 来移动 。我们的目标是最大化似然函数: 

    等价于最小化负对数似然,这么做还有一个好处,加法对求导更友好

    基本步骤

    在上一部分中我们没有解释p函数,当然你可能会说不就是概率密度函数吗?是,但是我们并没有先验的概率密度函数,怎么得到的。这里唯一可以利用的即使参考点云,我们将参考点云网格化,然后计算每个网格的多维正态分布参数。用 表示一个网格内的所有扫描点,则

    均值:

    协方差矩阵:

    概率密度函数:

    实际上这里f不是正态分布也可以 下一步就是如何求解

    对目标函数进行数学上的简化

    如下图所示,直接取负对数会出现无穷大的点,这样偶然扫到的一些异常点可能会对本来表现很好的结果产生很大的影响导致被舍弃,为了避免这种情况,在原函数的基础上做了一些限制。

    这时候我们的目标函数中的单项就变成 

    我们之前也提到了,加法对求导比较友好,但是log函数对求导不友好,而在求解优化问题的时候,经常会利用到一阶二阶导数(比如梯度下降,牛顿法),所以我们想办法对上述函数做一个近似,如果你对函数图像有一定的敏感性的化,很容易发现上面这两个绿色的函数好像还挺像?也就是说我们可以利用高斯函数来拟合负对数

    利用x=0, 解得近似参数为

    这样,我们可以得到不同项对NDT结果的贡献(偏移项是一致的,可暂时忽略),注意这里多了一个负号,我的理解应该是为了之后求导时前面的负号正好可以消掉

    原目标函数变成

    牛顿法求解

    这公式实在长,直接截图了,牛顿法的关键就是通过梯度矩阵g和海森矩阵H求解步长

    这里对上面的结果求导可得

    举一个简单的二维的例子来说明上面的$x_k$对$p_i$的求导过程

    最后结合流程图梳理一下NDT的流程

    1)划分网格

    2)计算各网格的PDF

    3)对每个点云数据,找到对应的网格点,并根据PDF和评分函数计算结果

    4)根据结果更新g和H,计算新的步长

    5)判断是否收敛或达到迭代次数,是则跳出,否则继续步骤3-5

    对NDT实验结果的一些优化

    1.cell size. 太大了容易导致损失一些局部特征,太小了则会增加很多计算量,太小会导致失去统计普适性,部分数据对结果影响过大。另外,作者直接舍弃掉少于五个数据的网格(因为会造成协方差矩阵不可逆)。

    2.Fixed discretization。固定大小是最常见的划分方式,操作简单,而且容易找到每个点对应的网格。缺点的话见底下几种方法

    3.Octree discretization。如何快速找到每个点对应的网格是搜索速度的关键,八叉树结构是常见的三维搜索树。

    4.Iterative discretization。好的初始位置可以加快收敛过程,一个常见的方法就是起始位置迭代,将上一次的终点位姿作为本次的起点位姿

    5.Adaptive clustering。非固定大小网格划分的一种方法,采用K均值聚类(其他聚类方式类似)划分,更能表现出每个局部数据的特征。

    6.Linked cells。上面提到数据少于五的网格会被舍弃,导致会出现一些空网格,损失了一些完整性,一个改进措施是将这些空网格用指针连接到最近的非空网格上,以该处的PDF代替,由于处于边缘,值还是很小,但是保证了数据的完整性。

    7.Trilinear interpolation。插值的逻辑就是固定划分实际上会出现边缘不连续的情况,插值法相当于做了一个平滑,计算的时候考虑所有含该数据点的网格取最优值,计算量大约是原来的4倍,但效果也有较大的改善。示意图如下

    其他一些配准方法

    1.Iterative dual correspondences (IDC) algorithm。ICP的一种改进,主要是采用极坐标代替笛卡尔坐标系进行最近点搜索

    2.Probabilistic iterative correspondence (PIC) method。这个方法考虑了噪声和初始位姿的不确定性

    3.Gaussian fields。采用高斯混合模型,类似NDT

    4.Conditional random fields (CRFs) 。条件随机场,还没细看

    5.Branch-and-bound strategy 。分支定界法,没看。

    6.Registration using local geometric features。结合图像的局部特征进行匹配

    7.除此之外最近还有一些结合深度学习的方法,比如百度无人车团队2019CVPR的工作:L3-Net: Towards Learning based LiDAR Localization for Autonomous Driving。输入包括实时激光点云,地图和IMU数据,输出位姿结果。

    推荐阅读:

    吐血整理|3D视觉系统化学习路线

    那些精贵的3D视觉系统学习资源总结(附书籍、网址与视频教程)

    超全的3D视觉数据集汇总

    大盘点|6D姿态估计算法汇总(上)

    大盘点|6D姿态估计算法汇总(下)

    机器人抓取汇总|涉及目标检测、分割、姿态识别、抓取点检测、路径规划

    汇总|3D点云目标检测算法

    汇总|3D人脸重建算法

    那些年,我们一起刷过的计算机视觉比赛

    总结|深度学习实现缺陷检测

    深度学习在3-D环境重建中的应用

    汇总|医学图像分析领域论文

    大盘点|OCR算法汇总

    重磅!3DCVer-学术论文写作投稿 交流群已成立

    扫码添加小助手微信,可申请加入3D视觉工坊-学术论文写作与投稿 微信交流群,旨在交流顶会(ICRA/IROS/ROBIO/CVPR/ICCV/ECCV等)、顶刊(IJCV/TPAMI/TIP等)、SCI、EI等写作与投稿事宜。

    同时也可申请加入我们的细分方向交流群,目前主要有3D视觉CV&深度学习SLAM三维重建点云后处理自动驾驶、CV入门、三维测量、VR/AR、3D人脸识别、医疗影像、缺陷检测、行人重识别、目标跟踪、视觉产品落地、视觉竞赛、车牌识别、硬件选型、学术交流、求职交流等微信群,请扫描下面微信号加群,备注:”研究方向+学校/公司+昵称“,例如:”3D视觉 + 上海交大 + 静静“。请按照格式备注,否则不予通过。添加成功后会根据研究方向邀请进去相关微信群。原创投稿也请联系。

    ▲长按加微信群或投稿

    ▲长按关注公众号

    3D视觉从入门到精通知识星球:针对3D视觉领域的知识点汇总、入门进阶学习路线、最新paper分享、疑问解答四个方面进行深耕,更有各类大厂的算法工程人员进行技术指导。与此同时,星球将联合知名企业发布3D视觉相关算法开发岗位以及项目对接信息,打造成集技术与就业为一体的铁杆粉丝聚集区,近1000+星球成员为创造更好的AI世界共同进步,知识星球入口:

    学习3D视觉核心技术,扫描查看介绍,3天内无条件退款

     圈里有高质量教程资料、可答疑解惑、助你高效解决问题

    展开全文
  • 在Web安全领域,XSS和CSRF是最常见的攻击方式。

    前言

    该篇文章还待更新、补充更多相关知识。

    笔者还是个小白,如果大家发现有啥错误记得及时指出!!


    在Web安全领域,XSS和CSRF是最常见的攻击方式。

    XSS(跨站脚本攻击)

    XSS(Cross Site Scripting)是跨站脚本攻击。跨站脚本攻击是一种安全漏洞,
    恶意攻击者可以利用这种漏洞在Web页面中插入一些恶意内容(Script代码)。当用户浏览该页面的时候,那么嵌入到web页面中Script代码会执行,从而达到恶意攻击用户的目的。

    恶意内容一般包括 JavaScript,但是,有时候也会包括 HTMLFLASH 或是其他浏览器可执行的代码。XSS 攻击的形式千差万别,但他们通常都会:将 cookies 或其他隐私信息发送给攻击者,冒充受害者,将受害者重定向到由攻击者控制的网页,或是经由恶意网站在受害者的机器上进行其他恶意操作。

    XSS 攻击可以分为3类:存储型(持久型)、反射型(非持久型)、DOM 型

    存储型 XSS

    注入型脚本永久存储在目标服务器上。当浏览器请求数据时,脚本从服务器上传回并执行。

    比如我现在做了一个博客网站,然后攻击者在上面发布了一篇文章,内容是如下:<script>window.open("www.gongji.com?param="+document.cookie)</script>如果我没有对该文章进行任何处理的话,直接存入到数据库中,那么下一次当其他用户访问该文章的时候,服务器会从数据库中读取后然后响应给客户端,那么浏览器就会执行这段脚本,然后攻击者就会获取到用户的cookie,然后会把cookie发送到攻击者的服务器上了。

    存储型XSS的攻击步骤如下:

    • 攻击者将恶意代码提交到目标网站数据库中。
    • 用户打开目标网站时,网站服务器将恶意代码从数据库中取出,然后拼接到html中返回给浏览器中。
    • 用户浏览器接收到响应后解析执行,那么其中的恶意代码也会被执行。
    • 那么恶意代码执行后,就能获取到用户数据,比如上面的cookie等信息,那么把该cookie发送到攻击者网站中,那么攻击者拿到该cookie然后会冒充该用户的行为,调用目标网站接口等违法操作。
      在这里插入图片描述

    这种攻击常见于带有用户保存数据的网站功能,如论坛发帖、商品评论、用户私信等。前端可以进行一些处理,比如将script标签等特殊字符替换成HTML 转义。

    反射型 XSS

    当用户点击一个恶意链接,或者提交一个表单,或者进入一个恶意网站时,注入脚本进入被攻击者的网站。Web服务器将注入脚本,比如一个错误信息,搜索结果等 返回到用户的浏览器上。由于浏览器认为这个响应来自"可信任"的服务器,所以会执行这段脚本。

    比如:攻击者通过电子邮件等方式将包含注入脚本的恶意链接发送给受害者,当受害者点击该链接的时候,注入脚本被传输到目标服务器上,然后服务器将注入脚本 "反射"到受害者的浏览器上,从而浏览器就执行了该脚本。

    反射型XSS的攻击步骤如下:

    1. 攻击者在url后面的参数中加入恶意攻击代码。
    2. 当用户打开带有恶意代码的URL的时候,网站服务端将恶意代码从URL中取出,拼接在html中并且返回给浏览器端。
    3. 用户浏览器接收到响应后执行解析,其中的恶意代码也会被执行到。
    4. 攻击者通过恶意代码来窃取到用户数据并发送到攻击者的网站。攻击者会获取到比如cookie等信息,然后使用该信息来冒充合法用户的行为,调用目标网站接口执行攻击等操作。
      在这里插入图片描述
      反射型 XSS 漏洞常见于通过 URL 传递参数的功能,如网站搜索、跳转等。由于需要用户主动打开恶意的 URL 才能生效,攻击者往往会结合多种手段诱导用户点击。

    基于 DOM 的 XSS

    通过修改原始的客户端代码,受害者浏览器的 DOM 环境改变,导致有效载荷的执行。也就是说,页面本身并没有变化,但由于DOM环境被恶意修改,有客户端代码被包含进了页面,并且意外执行。

    DOM 型 XSS 的攻击步骤:

    1. 攻击者构造出特殊的 URL,其中包含恶意代码。
    2. 用户打开带有恶意代码的 URL。
    3. 用户浏览器接收到响应后解析执行,前端 JavaScript 取出 URL 中的恶意代码并执行。
    4. 恶意代码窃取用户数据并发送到攻击者的网站,或者冒充用户的行为,调用目标网站接口执行攻击者指定的操作。
      在这里插入图片描述

    DOM 型 XSS 跟前两种 XSS 的区别:DOM 型 XSS 攻击中,取出和执行恶意代码由浏览器端完成,属于前端 JavaScript 自身的安全漏洞,而其他两种 XSS 都属于服务端的安全漏洞。

    防御措施

    • 前后端分离(前端负责渲染、后端负责数据)。
    • 对 HTML 转义。

    在服务器端设置cookie的时候设置HttpOnly, 这样就可以防止用户通过Document.cookie获取cookie。此预防措施有助于缓解跨站点脚本(XSS)攻击。

    CSRF(跨站请求伪造)

    跨站请求伪造(Cross-site request forgery),也被称为 one-click attack 或者 session riding,通常缩写为 CSRF 或者 XSRF, 是一种挟制用户在当前已登录的Web应用程序上执行非本意的操作的攻击方法。跟XSS相比,XSS 利用的是用户对指定网站的信任,CSRF 利用的是网站对用户网页浏览器的信任。

    跨站请求攻击,简单地说,是攻击者通过一些技术手段欺骗用户的浏览器去访问一个自己曾经认证过的网站并运行一些操作(如发邮件,发消息,甚至财产操作如转账和购买商品)。由于浏览器曾经认证过,所以被访问的网站会认为是真正的用户操作而去运行。这利用了web中用户身份验证的一个漏洞:简单的身份验证只能保证请求发自某个用户的浏览器,却不能保证请求本身是用户自愿发出的。

    假如一家银行用以运行转账操作的URL地址如下:
    http://www.examplebank.com/withdraw?account=AccoutName&amount=1000&for=PayeeName
    那么,一个恶意攻击者可以在另一个网站上放置如下代码:
    <img src="http://www.examplebank.com/withdraw?account=Alice&amount=1000&for=Badman">
    如果有账户名为Alice的用户访问了恶意站点,而她之前刚访问过银行不久,登录信息尚未过期,那么她就会损失1000资金。

    攻击者并不能通过CSRF攻击来直接获取用户的账户控制权,也不能直接窃取用户的任何信息。他们能做到的,是欺骗用户浏览器,让其以用户的名义运行操作

    攻击流程如下:

    • 受害者登录a.com,并保留了登录凭证(Cookie)。
    • 攻击者引诱受害者访问了b.com。
    • b.com 向 a.com 发送了一个请求:a.com/act=xx。浏览器会默认携带a.com的Cookie。
    • a.com接收到请求后,对请求进行验证,并确认是受害者的凭证,误以为是受害者自己发送的请求。
    • a.com以受害者的名义执行了act=xx。
    • 攻击完成,攻击者在受害者不知情的情况下,冒充受害者,让a.com执行了自己定义的操作。

    防御措施

    检查Referer字段

    HTTP头中有一个Referer字段,这个字段用以标明请求来源于哪个地址。在处理敏感数据请求时,通常来说,Referer字段应和请求的地址位于同一域名下。以上文银行操作为例,Referer字段地址通常应该是转账按钮所在的网页地址,应该也位于www.examplebank.com之下。而如果是CSRF攻击传来的请求,Referer字段会是包含恶意网址的地址,不会位于www.examplebank.com之下,这时候服务器就能识别出恶意的访问。

    这种办法简单易行,工作量低,仅需要在关键访问处增加一步校验。但这种办法也有其局限性,存在攻击者攻击某些浏览器,篡改其Referer字段的可能。

    SameSite 属性设置为Strict 或 Lax。

    用于敏感信息(身份验证)的 Cookie 的生存期应较短,并且 SameSite 属性设置为Strict 或 Lax。在支持 SameSite 的浏览器中,这样做的作用是确保不与跨域请求一起发送身份验证 cookie,因此,这种请求实际上不会向应用服务器进行身份验证。

    • Strict最为严格,完全禁止第三方 Cookie,跨站点时,任何情况下都不会发送 Cookie。换言之,只有当前网页的 URL 与请求目标一致,才会带上 Cookie。(浏览器将只在访问相同站点时发送 cookie。)
    • Lax与 Strict 类似,但导航到目标网址的 Get 请求除外。导航到目标网址的 GET 请求,只包括三种情况:链接,预加载请求,GET 表单。(默认值)

    设置了Strict或Lax以后,基本就杜绝了 CSRF 攻击。当然,前提是用户浏览器支持 SameSite 属性。


    待补充更多细节!!

    展开全文
  • 图的两种遍历方法

    千次阅读 2021-05-31 22:00:01
    图的遍历过程根据搜索方法的不同,又可划分为两种搜索策略 1.深度优先遍历 2.广度优先遍历 算法思想 1.深度优先遍历(dfs) 深度优先遍历的步骤 访问顶点V 依次从顶点V的未被访问的邻节点出发,进行深度优先搜索,...

    图的遍历

    图的遍历是指,从给定图中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着图的边访问图中的所有顶点,使每个顶点仅被访问一次,这个过程称为图的遍历。

    图的遍历过程根据搜索方法的不同,又可划分为两种搜索策略

    1.深度优先遍历
    2.广度优先遍历

    算法思想

    1.深度优先遍历(dfs)

    深度优先遍历的步骤

    • 访问顶点V
    • 依次从顶点V的未被访问的邻节点出发,进行深度优先搜索,直至和V有路径相通的顶点都被访问到。
    • 对于连通图进行遍历时,从一个顶点出发即可访问图中所有的顶点。
    • 对于非连通图进行遍历时,若图中尚有顶点未被访问,则另选一未曾访问的顶点作为起始点,进行深度优先搜索,直至所有顶点都被访问

    访问过程如图所示
    在这里插入图片描述
    遍历结果:v1,v2,v4,v8,v5,v3,v6,v7,v9,v10

    2.广度优先遍历

    从顶点V出发广度优先搜索的步骤

    • 访问顶点V
    • 依次访问顶点V的各个未被访问的临接点(横向访问)
    • 从V的这些邻接点出发依次访问他们的邻接点,致使“先被访问的顶点的邻接点先于"后访问的顶点的邻接点"被访问,直至图中所有已被访问的顶点的邻接点均被访问。
    • 对于非连通图进行遍历时,若图中尚有顶点未被访问,则另选一未曾访问的顶点作为起始点,进行广度优先搜索,直至所有顶点都被访问
      遍历的过程:
      在这里插入图片描述
      遍历的结果:V1,V2,V3,V4,V5,V6,V7,V8,V9,V10

    具体代码实现:

    //深度优先搜索(DFS)
    void DFS(AMGraph G, int v){
    cout<<G.vex[v];
    visit[v]=1;
    for(j=0;j<G.vexnum;j++){
    if(G.arcs[v][j]&&!visited[j]) DFS(G,j)
        }
    }
    void DFSTraverse(AMGraph G){
    for(v=0;v<G.vexnum;v++) 
       visited[v]=0;
       for(v=0;v<G.vexnum;v++)
       if(!visited[v])DFS(G,v);
    }
    
    
    
    //广度优先搜索(BFS)
    void BFSTracerse(AMGraph G){
    for(v=0;v<G.vexnum;v++) visited[v]=0;
    InitQueue(Q);
    for(v=0;v<G.vexnum;v++){
         if(!visited[v])
         {
         cout<<G.vexs[v];  
         visited[v]=1;
         EnQueue(Q,v);
         while(!QueueEmpty(Q)){
         DeQueue(Q,u);
         for(j=0;j<G.vexnum;j++){
             if(G.arcs[u][j]==1&&!visited[j])
                {
                      cont<<G.vexs[j];
                      visited[j]=1;
                      EnQueue(Q,j);
                      }
                    }
                }
            }
        }
    }
    
    展开全文
  • javascript 中搜索数组的四种方法

    千次阅读 2022-05-18 10:09:24
    前端经常要通过 javaScript 来处理数组中的数据,其中就包括检查...现在我们可以通过内置的使用方法来完成在数组中搜索值的常见任务。 本文将介绍 Array.includes()、Array.indexOf()、Array.fiind() 和 Array.filter
  • 二分查找也称折半查找(Binary Search),它是一效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 查找过程 首先,假设表中元素是按升序排列,将表...
  • 数据结构——图的两种遍历方法

    万次阅读 2018-12-24 15:37:19
    /* 邻接矩阵存储,从顶点v出发,对图g进行深度优先搜索*/ int j; printf("%d ",g.vexs[v]); visited[v]=1; /*标识v被访问过*/ for(j=0;j;j++); /* */ { if( g.arcs[v][j]==1&&visited[j]==0)/*j为v的邻接点,...
  • halcon的三种模板匹配方法总结 halcon有三种模板匹配方法:即...上图介绍的是形状匹配做法的一般流程及模板制作的两种方法。 先要补充点知识:形状匹配常见的有四种情况 一般形状匹配模板shape_model、线性变
  • 图的两种遍历方式

    万次阅读 2019-03-08 10:58:27
    图的两种遍历方式 图的遍历 &nbsp;... 从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一...根据遍历路径的不同,通常有两种遍历图的方法:深度优先遍历和广度优先遍历。...
  • 这里写目录标题实验目的实验内容实验要求六排序方法细解直接插入排序冒泡排序简单选择排序希尔排序快速排序归并排序六排序好坏分析代码段运行结果 实验目的 1.能够清楚表述主要内部排序方法的设计思路。 2....
  • 常见的几优化方法

    千次阅读 2016-12-12 11:27:14
    常见的几最优化方法 1. 梯度下降法(Gradient Descent)  梯度下降法是最早最简单,也是最为常用的最优化方法。梯度下降法实现简单,当目标函数是凸函数时,梯度下降法的解是全局解。一般...
  • 机器学习中常见的几优化方法

    万次阅读 2016-06-08 15:11:36
    机器学习中常见的几优化方法 声明:本文为转载,原文作者为:Poll的笔记,原文链接为:http://www.cnblogs.com/maybe2030/p/4751804.html#rd,尊重原创 阅读目录 1. 梯度下降法(Gradient ...
  • 两种常用MySql查询时间段的方法

    千次阅读 2021-01-18 18:08:32
    MySql查询时间段的方法很多,下面就为您介绍几最常用的MySql查询时间段方法,如果您在MySql查询时间段方面遇到过问题,不妨一看。MySql的时间字段有date、time、datetime、timestamp等,往往我们在存储数据的时候...
  • ML之FE:数据处理—特征工程之特征选择常用方法之基于搜索策略的三分类、基于评价准则划分的三分类(Filter/Wrapper/Embedded)及其代码实现 目录 Wrapper包裹式/封装式——基于搜索策略的三类 T1、全局...
  • 字符串的常见方法总结:

    千次阅读 2022-02-20 19:31:03
    字符串的方法有:字符串的比较,字符串的搜索,截取字符串,去除首尾空白字符串,替换字符串,分割字符串,拼接字符串,格式化字符串,字符串的类型转换,转换为char[]字符数组,字符编码,延伸阅读。 一、字符串的...
  • 今天小编不是向大家介绍电脑的应用,而是想要和大家分享一下关于电脑截图的几种方法。 1、Print Screen SysRq Print Screen SysRq键是截电脑屏幕的电脑快捷键,这个电脑截屏的快捷键只能截取电脑当前的整个页面,...
  • 分享者:iweb2020 阅读量:3748 小金子学院目录最新收录:投资寓言故事之鸡的故事D 囻 囼9困 囱 囲㊣男Windows2012重启的两种方法:cmd命令关机重启分享一,windows2012使用cmd命令关机重启。方法如下:1、点击开始...
  • 中文分词常见方法

    万次阅读 2017-07-25 12:32:06
    常见的基于词典的分词算法分为以下几: 正向最大匹配法、逆向最大匹配法 和 双向匹配分词法 等。 基于词典的分词算法是应用最广泛、分词速度最快的。很长一段时间内研究者都在对基于字符串匹配方法进行优化,...
  • 关于删除WORD文档页眉横线,网上搜索均可查找到2种常见方法,即:1、将页眉样式改为正文样式;2、清除格式。 两种方式虽然均可以达到清除横线的目的,但效果却相差很大。 1、使用之后将页眉样式改为正文样式方式...
  • 常见的9大数据分析方法

    万次阅读 2019-01-23 16:01:30
    数据分析是从数据中提取有价值信息的过程,过程中需要对数据进行各种处理和归类,只有掌握了正确的数据分类方法和数据处理模式,才能起到事半功倍的效果,以下是数据分析员必备的9数据分析思维模式: 1. 分类 ...
  • 常见的几最优化方法

    万次阅读 2017-02-23 21:55:50
     在机器学习中,基于基本的梯度下降法发展了两种梯度下降方法,分别为随机梯度下降法和批量梯度下降法。  比如对一个线性回归(Linear Logistics)模型,假设 下面的h(x)是要拟合的函数,J(theta)为损失函数...
  • 你在互联网使用搜索的时候,关键词推荐可能是你经常使用到的一个辅助工具。如各种搜索引擎搜索框的下拉提示;google 结果页会有“XXX”的“相关搜索”;... 而这些常见的关键词推荐是怎么得到的呢?我总结了一下
  • 以上方法若无效则建议带到手机售后服务中心检修。 二、设备出现系统或者程序错误 打开应用程序时提示无法打开或者强行关闭,一般是程序冲突造成的 将手机恢复出厂设置(恢复出厂设置会清空手机资料,请注意...
  • 机器学习中常见的几最优化方法

    万次阅读 2016-06-07 10:02:17
    1. 梯度下降法(Gradient Descent) ...4. 启发式优化方法  5. 解决约束优化问题——拉格朗日乘数法 我们每个人都会在我们的生活或者工作中遇到各种各样的最优化问题,比如每个企业和个人都要考虑的一个问题
  • 二、LoadRunner12的两种安装方法方法一:通过可执行文件安装法(有的可能点了没有反应,可以使用第二种方法方法二:通过可执行文件直接进行安装 三、后期查找安装证书的位置: 首先了解LoadRunner12相比...
  • 9常用的数据分析方法

    万次阅读 2020-08-17 11:09:23
    对比法就是用两组或两组以上的数据进行比较,是最通用的方法。 我们知道孤立的数据没有意义,有对比才有差异。比如在时间维度上的同比和环比、增长率、定基比,与竞争对手的对比、类别之间的对比、特征和属性对比等...
  • 常见的7排序算法

    万次阅读 多人点赞 2018-06-10 11:37:21
    则冒泡排序的具体过程可以描述为:首先从数组的第一个元素开始到数组最后一个元素为止,对数组中相邻的个元素进行比较,如果位于数组左端的元素大于数组右端的元素,则交换这个元素在数组中的位置,此时数组最...
  • SpringMVC实现文件下载的两种方法

    万次阅读 多人点赞 2018-05-28 20:31:20
    天玩spring的过程中遇到了一个很常见的问题——文件下载。以往很多时候都是直接给一个文件的静态链接,这种方法有很多局限性,其中一个很明显的局限性就是不易统计下次状态,还有就是需要http服务器来保存文件,...
  • 本博客将在win10+MySQL5.7的环境下,演示一些MySQL服务的两种开启方式。 MySQL服务的开启、关闭 这一步很有必要,有时当你打开一些数据库图形操作界面,会报错说无法连接,这一般都是MySQL服务没有开启的锅。 方法一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 299,214
精华内容 119,685
热门标签
关键字:

常见的两种搜索方法