启发式搜索算法进阶
继续来学启发式搜索
多的其实没啥好讲了的,因为概念问题在前一篇博文已经讲的很清楚了。主要就是训练寻找估值函数,多点题目练习能应对不通场景下的启发式搜索。
例题洛谷上的p2324骑士精神
题目描述
主要就是说有个空格,然后所有马都走日,没有马脚,只能跳到空格里面去,然后问你是否能在15步以内达到。如果可以则输出最短步数,否则输出-1,因为空格只有一个我们不考虑跳马,考虑跳空格。
递归最大深度15层能确定了,但是任意一个状态可以延伸出最少2中最多八种情况。15作为指数时间上还是遭不住,考虑启发式搜索。那么估值函数需要怎么写呢?
估值函数这里再补充点估值函数的知识。
f(n)=g(n)+h(n)
估值函数一般表达式如上,g(n)为当前状态,h(n)为未来最优状态产生的花费,或者是其它。估值函数为两者和,由于当前状态我们很容易获取,所以算出未来最优状态即可等于获得了估值函数。可能前面讲的有点小问题,但是还是不妨碍的,因为我们平时写也基本是
123if(f(n)+value>ans){ dfs(n+1);}
所以问题不大。
题目分析在本题中,我们的 ...
启发式搜索算法
来快乐学算法了。
启发式搜索启发式搜索(英文:heuristic search)是一种改进的搜索算法。它在普通搜索算法的基础上引入了启发式函数,该函数的作用是基于已有的信息对搜索的每一个分支选择都做估价,进而选择分支。简单来说,启发式搜索就是对取和不取都做分析,从中选取更优解或删去无效解。
在此之前,本蒟蒻一直就只会dfs和bfs,今天来学学新的搜索算法。经过多重资料的 查阅也是大概得知启发式搜索的大概思路,每次搜索会对之后可能的最优状态估值,如果估出来的值不如当前某些状态,那么我就直接舍弃这个状态。就比如经典01背包问题,我对每一个物品的抉择都有选或者不选两种选择,我发现我不选这个物品,选其它物品所产生的最优解不如我当前选这个解的状态好,那么我直接考虑选择这个而不去搜索不选择这个物品的状态。
估值函数这里需要解释一下我如何判断当前状态是否优于之后的最优状态,那么这里需要这么一个估值函数,估值函数不是真的对那个情况做具体分析,那样的话跟暴力没区别了。我这样考虑,如果剩下所有物品全能放进去都不如我一个放进去价值大,那么我肯定得放这个物品(前提是放得进去,放不进去就别讨论了)。那么这个 ...
RoarCTF2019 polyre writeup writeup
buu刷题记录-RoarCTF2019 polyre
初步分析拿到文件ida打开,发现是很绝望的究极无敌的代码混淆——控制流平坦化。
控制流平坦化介绍控制流平坦化(control flow flattening)的基本思想主要是通过一个主分发器来控制程序基本块的执行流程,例如下图是正常的执行流程
在经过控制流平台化的混淆之后,会变成如下的结构
流程图看起来就像是同一级的关系,块之间失去了层次分明,逻辑可读性变得更差。
就好比我们平时做的堆菜单题,选择菜单的时候,逻辑基本就是
1234567891011121314151617181920while(1){ menu(); int num=getnum(); switch(num){ case 1: add(); break; case 2: edit(); break; case 3: delete(); break ...
校园网模拟登录
学校更新了校园网之后,用的宽带就需要每天早上进行一遍网页登录才能有网,非常的麻烦,我就萌生出了想写个模拟登录的脚本的想法。
抓包获得请求方式这里我用wireshark抓包,只抓从登录到登录成功这个时间段的包,这里主要分析我们发送的http的流量包。
可以发现主要有两个流量包出现了username字段,那么主要分析这两个包内容的参数。第一个流量包内容如下
请求api为http://10.110.74.99/cgi-bin/get_challenge
主要有四个参数,callback,username,ip,和_。callback参数不太确定,但是可以确定username是自己登录校园网的账号,ip就是自己本机在这个局域网下的ip,而_很明显就是时间戳。而可以看到call_back后面也有一个类似时间戳的参数。这个暂且不确定,但是后面反复抓包可以发现,这个参数就是固定的。至于本次请求是返回了什么我们可以照着参数打进去看看返回了什么数据,本人很菜,不是打web的,不会用burpsuite只能用这种办法了。
可以发现返回了一串json数据,里面主要有一个challenge字段, ...
RC4加密的学习
最近有点颓废了,想学内核很难进行,逆向光刷题看着也很难,pwn刷题就是处于刷的感觉似曾相识,没有一点提升的感觉,所以我决定先攻一下逆向,把常见加解密算法先学了,今天先来这个RC4
RC4加密我初识RC4是在国赛,记得很清楚的一点就是不停地取模256,那题当时靠着网上资料勉强算过去了。但是还是想系统地学一下,网上教程千篇一律,我决定自己模拟一边它的算法过程然后再理解一遍。
既然是加密,脱离不了三个概念,明文,密文,密钥。RC4是对称加密,我也才知道,一直以为是不可逆的那种hash加密,所以既然它是对称加密,那么对于加密和解密过程,他们所用的密钥相同。它生成密钥的过程如下:
生成密钥需要一个长度不多于256长度的字符串作为种子生成随机密钥,这是我自己的理解,因为它确实给我的感觉就是这样的随机。它初始生成了一个长度为256的S串,初始S[i]=i,后面根据用字符串种子作为一个变换规则T,交换S密钥里的各个值,这样的交换好处在于我们可以保证S串密钥为一个双射(满足单射和满射,这个概念高中应该讲过,不赘述)。然后给的一个字符串种子呢,就会被放进T中,T的长度也为256,如果所给字符 ...
pwnable.kr input
学习Linux输入的五种方式
正则表达式的使用
最近在和战队一起的比赛中又出现了诸多想要学习的知识点,那就是re和QRcode,今天先学一下这个正则吧。
那么我已开始接触正则呢,应该是在学爬虫的时候,因为当时爬虫学的不太好也就没有接着学正则匹配。后来在换了linux系统之后经常会用到一个很有用的东西,那就是|grep。不得不说这个在找东西的时候真的是很有用的,比如
1$ls -l | grep ""
那么本次和Nepnep战队参加xctf分区赛也是有一道修复二维码的题目,当时师傅们可能有些点没注意到,导致最后修复的二维码多达16000的扫描结果。
得到结果之后本以为要经历漫长的人工过滤,可是咱们战队的一位爷爷直接solved,而这位爷爷就是直接用了正则匹配。
正则表达式正则表达式(英语:Regular Expression,常简写为regex、regexp或RE),又称正则表示式、正则表示法、规则表达式、常规表示法,是计算机科学的一个概念。正则表达式使用单个字符串来描述、匹配一系列匹配某个句法规则的字符串。在很多文本编辑器里,正则表达式通常被用来检索、替换那些匹配某个模式的文本。
许多程序设计语言都 ...
SWPUCTF_2019_p1KkHeap writeup
buu刷题记录—SWPUCTF_2019_p1KkHeap
这波又刷新了我对2.27版本libc的认知。那就是tcache struct ,话不多说看题。
静态分析64位保护全开,习惯就好。载入IDA查看发现plt表有很多函数,其中有mmap和prctl,prctl最常见的就是设置沙箱规则,mmap最常见的就是直接给一个可读可写可执行的一片内存区域,那么我们返回终端查看一下沙箱规则。
这个有点复杂,不过大概率就可以认为他给你禁用了execve,其它的基本不用管,大概意思就是write函数的count必须非负,且大小在32位int范围内,并且不能=0x10,有一说一这个0x10并不理解为啥限制这个不能等于0x10,因为我读flag一般是读0x40
我们看看初始化函数,可以看到mmap分配了一片很大的内存并且是可读可写可执行的权限,那么开了沙箱之后我们就能往里面写orw的shellcode,然后再劫持某些东西让它跳转到这个区域。
分析逻辑, 经典堆菜单题目,包含了增删改查,但是有一个全局变量一直在++并且循环并非while 1,可以发现这个初始值为0x12,意味着我们只能 ...
npuctf_2020_level2 writeup
buu刷题记录—npuctf_2020_level2
这题刷新了我对格式化字符串的利用,来康康吧。
静态分析十分简单,就是主函数while循环输入然后格式化字符串漏洞,但是不同的是这个格式化字符串并不在stack段而是在bss段上的。那就考虑考虑字符串在bss段和在stack段的区别,我们平时做的都是在stack段的,因为buf输入一般都是在printf调用之前,所以printf的栈帧会比buf低,而参数在高地址,那么此时printf的参数我们就可控,在buf上写上一个地址然后算出偏移用%n格式串去写就能基本达到任意title写的目的。但是如果它在bss段上或者是在堆上,那么格式化字符串的参数控制不了我们就得另寻方法了。其实也还好,第一步我们可以先控制一个栈的参数,栈里面都会有存函数的ebp,那么可以通过这个来写一个目的地址,再通过目的地址任意写我们想写的内容。讲简单一点其实也就是控制一个栈的地址然后写上目的地址,最后再往目的地址写东西,有格式化字符串漏洞那么基本stack,code和libc地址跟送的一样随便泄露。
动态调试先gdb起这个程序,然后运行到printf这边观察栈情况 ...
de1ctf_2019_weapon writeup
buu刷题记录—de1ctf_2019_weapon
静态分析checksec一波,保护全开,ida分析,发现时经典的堆菜单题目。有add,delete和edit操作,没有show函数,并且保护全开无法劫持got表。那么这题大概率是要用IO来泄露libc了。
add函数把堆块申请范围限制在了0x60以内,也就是说我们只能申请fastbin大小的堆块。edit函数就是中规中矩的按照之前的size修改堆块的内容。delete函数在堆块被free之后没有把指针置空存在UAF的漏洞。那么我们的思路大概就是先通过uaf进行堆块重叠然后修改size,free之后得到一个unsorted bin,然后再修改回fastbin将它申请到stdout附近通过IO泄露libc地址,最后再来一次fastbin attack劫持malloc hook放上onegadget 去getshell,这题需要用realloc 调整栈来适应onegadget,我们后面再说。
泄露libc的地址因为地址都是未知的,所以一开始要通过释放两个相同大小的fastbin来让其中一个fastbin中留下另一个fastbin的地址 ...