Arya

Mutation-Based Fuzzing
[+] 日不落教练今天竟然没有放日不落![+] 晚上去买了开心果,剥着吃就很开心[+] 我想吃橙子,明天去买0x0...
扫描右侧二维码阅读全文
20
2019/01

Mutation-Based Fuzzing

[+] 日不落教练今天竟然没有放日不落!
[+] 晚上去买了开心果,剥着吃就很开心
[+] 我想吃橙子,明天去买

0x01 一个url的模糊生成器

在写fuzzer的时候,大部分情况下生成的随机输入在语法上都是无效的,且很多情况下的输入都有着要求,比如输入电话号码必须是11位,邮箱地址里必须有@,所以我们在写一个fuzzer的时候一定要考虑到生成的随机输入是否符合对应的语法规则。

例如,假设我们现在要对一个程序进行fuzzing,而输入的要求必须是url,所以我们的fuzzer必须生成符合url格式的字符串,所以在此之前要先了解一下url的组成

scheme://netloc/path?query#fragment

scheme:该url的协议协议,如http,https,ftp,file……
netloc:要连接到的主机的名称,例如l www.google.com
path:该主机上的相对路径,例如 search
query:一个键/值对的列表,例如 q=fuzzing
fragment :查询搜索的部分,需要向服务器传入参数,就在这输入。通过"?"连接到path后面,如#result

在python中,我们可以使用urlparse()将url解析成各个部分

import fuzzingbook_utils
try:
    from urlparse import urlparse      # Python 2
except ImportError:
    from urllib.parse import urlparse  # Python 3
print(urlparse("http://www.google.com/search?q=fuzzing"))

ParseResult(scheme='http', netloc='www.google.com', path='/search', params='', query='q=fuzzing', fragment='')

我们可以看到url的各部分是如何组成的

那么,假设我们现在有一个需要url作为输入的程序,所以我们现在需要写一个可以随机生成url的fuzzer。本着一步一步来的思想,我们首先先检测我们生成的url是否是有效的,代码如下

def http_program(url): 
    supported_schemes=["http","https"]    result=urlparse(url)  
    if result.scheme not in supported_schemes:        raise ValueError("Scheme must be one of " + 
repr(supported_schemes)) 
    if result.netloc=='':
        raise ValueError("Host must be non-empty")    return True

然后我们利用之前写的Fuzzer来测试生成的字符串是否符合输入要求

from Fuzzer import fuzzer
fuzzer(char_start=32, char_range=96)

我们利用fuzzer()可以随机生成100串字符串,然后测试是否生成能够符合url格式的字符串

for i in range(1000):
    try:
        url = fuzzer()
        result = http_program(url)
        print("Success!")
    except ValueError:
        pass

当然我们可以手动计算一下获得这种合法url输入的概率有多大,首先,我们需要满足url的开头是"http://" "https://",假设我们现在要满足开头是"http://" 的情况,因为我们可以生成的字符范围为96个不同的字符(
char_range=96),所以能够成功组成"http://" 的概率为1/96^7,也就是1/75144747810816;假设要满足"https://" ,则概率为1/7213895789838336,所以成功生成这两种字符的成功概率是

>>>likelihood = 1 / (96 ** 7) + 1 / (96 ** 8)
>>>likelihood

1.344627131107667e-14
我们现在可以计算一下,http_program()所需要的运行时间

from Timer import Timer

trials = 1000with Timer() as t:
    for i in range(trials):
        try:
            url = fuzzer()
            result = http_program(url)
            print("Success!")
        except ValueError:
            pass

duration_per_run_in_seconds = t.elapsed_time() / trials
duration_per_run_in_seconds

7.3461787e-05
当然这只是测试了生成字符串并通过测试的概率,那么正确获得这两种字符的概率呢

>>>seconds_until_success = >>>duration_per_run_in_seconds * (1 / likelihood)
seconds_until_success

4140024896.9668455
也就是说需要4140024896.9668455秒=131.18947248735154年
(大概可以算到龙族结局的时候,滑稽

所以显而易见,我们想获得一个争取的url协议,就需要这么多年,是根本不现实而,所以我们需要想一个办法,来快速实现获得正确的url

0x02 对输入的字符串进行改变

显然如果只是杂乱无章的输入,我们根本无法获得任何正确的输入,那么我们可以考虑对原有的正确的字符串进行删减、增加或者修改,比如将https://www.baidu.com/改为https://www.googlecom/以便于生成格式正确且内容不同的新字符串,我们可以先尝试删除原有字符串中的字符

import random

def delete_random_character(s):
    """Returns s with a random character deleted"""
    if s == "":
        return s

    pos = random.randint(0, len(s) - 1)
    # print("Deleting", repr(s[pos]), "at", pos)
    return s[:pos] + s[pos + 1:] #删除字符
    
seed_input = "A quick brown fox"
for i in range(10):
    x = delete_random_character(seed_input)
    print(repr(x))

'A uick brown fox'
'A quic brown fox'
'A quick brown fo'
'A quic brown fox'
'A quick bown fox'
'A quick bown fox'
'A quick brown fx'
'A quick brown ox'
'A quick brow fox'
'A quic brown fox'

那么已经删除成功,那么现在尝试,添加新的字符

def insert_random_character(s):
    """Returns s with a random character inserted"""
    pos = random.randint(0, len(s))
    random_character = chr(random.randrange(32, 127))
    # print("Inserting", repr(random_character), "at", pos)
    return s[:pos] + random_character + s[pos:]#增加字符
    for i in range(10):
    print(repr(insert_random_character(seed_input)))

'A quick brvown fox'
'A quwick brown fox'
'A qBuick brown fox'
'A quick broSwn fox'
'A quick brown fvox'
'A quick brown 3fox'
'A quick brNown fox'
'A quick brow4n fox'
'A quick brown fox8'
'A equick brown fox'

我们也可以将字符串内的字符直接进行变异,而不改变长度, 插入删除都改变了长度

def flip_random_character(s):
    """Returns s with a random bit flipped in a random position"""
    if s == "":
        return s

    pos = random.randint(0, len(s) - 1)
    c = s[pos]
    bit = 1 << random.randint(0, 6)#这里也可以不这么写,也可以随机赋一个ASCII码值g给new_c
    new_c = chr(ord(c) ^ bit)
    # print("Flipping", bit, "in", repr(c) + ", giving", repr(new_c))
    return s[:pos] + new_c + s[pos + 1:]
    
 
for i in range(10):
    print(repr(flip_random_character(seed_input)))

'A quick bRown fox'
'A quici brown fox'
'A"quick brown fox'
'A quick brown$fox'
'A quick bpown fox'
'A quick brown!fox'
'A 1uick brown fox'
'@ quick brown fox'
'A quic+ brown fox'
'A quick bsown fox'

接下来作者将这三种方法放入一个列表中,然后随机使用一种方法,生成新的字符串

def mutate(s):
    """Return s with a random mutation applied"""
    mutators = [
        delete_random_character,
        insert_random_character,
        flip_random_character
    ]
    mutator = random.choice(mutators)
    # print(mutator)
    return mutator(s)
for i in range(10):
    print(repr(mutate("A quick brown fox")))

'A qzuick brown fox'
' quick brown fox'
'A quick Brown fox'
'A qMuick brown fox'
'A qu_ick brown fox'
'A quick bXrown fox'
'A quick brown fx'
'A quick!brown fox'
'A! quick brown fox'
'A quick brownfox'

0x03 生成不同的url

上面阐述了生成相同格式的不同字符串的方式,即利用增删改的方式添加字符,而不改动整体字符串的结构。接下来可以使用这种思想来生成不同的ur,首先写创建一个函数is_valid_url()来检测输入是否正确

def is_valid_url(url):
    try:
        result = http_program(url)
        return True
    except ValueError:
        return False

测试一下代码是否可行

assert is_valid_url("http://www.google.com/search?q=fuzzing")
assert not is_valid_url("xyzzy")

均未报错,可以正确运行
接下来我们可以利用上面的三种方法,随机生成url并检测

我们可以查看生成了的符合条件的url的比例

len(valid_inputs) / trials

0.8

那么如果我们要生成https:那么我们就要把s正确的插入到对应的位置,那么我们能够正确选择插入方法的概率是1/3,能够正确生成s的概率是1/96,能够正确插入到指定的位置的概率是1/L(L为输入的字符串的长度)

我们可以简单的计算一下这个概率的分母

>>>trials = 3 * 96 * len(seed_input)
>>>trials

10944

from Timer import Timer

trials = 0with Timer() as t:
    while True:
        trials += 1
        inp = mutate(seed_input)
        if inp.startswith("https://"):
            print(
                "Success after",
                trials,
                "trials in",
                t.elapsed_time(),
                "seconds")
            break

Success after 3656 trials in 0.010541436000494286 seconds

如果我们需要生成ftp://前缀,那需要的过程就更加复杂

到目前为止我们只对样本字符串的一个字符进行变异,当然我们可以对样本中的多个字符进行变异,如果要进行20个地方的改变

seed_input = "http://www.google.com/search?q=fuzzing"mutations = 50

inp = seed_inputfor i in range(mutations):
    if i % 5 == 0:
        print(i, "mutations:", repr(inp))
    inp = mutate(inp)

0 mutations: 'http://www.google.com/search?q=fuzzing'
5 mutations: 'http:/L/www.googlej.com/seaRchq=fuz:ing'
10 mutations: 'http:/L/www.ggoWglej.com/seaRchqfu:in'
15 mutations: 'http:/L/wwggoWglej.com/seaR3hqf,u:in'
20 mutations: 'htt://wwggoVgle"j.som/seaR3hqf,u:in'
25 mutations: 'htt://fwggoVgle"j.som/eaRd3hqf,u^:in'
30 mutations: 'htv://>fwggoVgle"j.qom/ea0Rd3hqf,u^:i'
35 mutations: 'htv://>fwggozVle"Bj.qom/eapRd[3hqf,u^:i'
40 mutations: 'htv://>fwgeo6zTle"Bj.\'qom/eapRd[3hqf,tu^:i'
45 mutations: 'htv://>fwgeo]6zTle"BjM.\'qom/eaR[3hqf,tu^:i'

这样我们就完成了不同次数的变异

我们现在可以使用之前的Fuzzer函数,为了实现在一个包对字符串多重突变,我们可以创建一个MutationFuzzer类,同时我们也要定义这个类生成的字符串的最大和最小突变次数

from Fuzzer import Fuzzer

class MutationFuzzer(Fuzzer):
    def __init__(self, seed, min_mutations=2, max_mutations=10):
        self.seed = seed
        self.min_mutations = min_mutations
        self.max_mutations = max_mutations
        self.reset()

    def reset(self):
        self.population = self.seed
        self.seed_index = 0

为了完善这个类,我们要向其中不断增加新的方法,但是直接在类的内部增加过多方法会使这个类从结构上变得冗长而且繁杂,我们可以使用这种形式,向一个类中填充不同的方法

class C(C):
    def new_method(self, args):
        pass

这种方式看上去是将类C定义为它的子类,是一种无效的操作,然而实际上是将一个新的类C作为子类引入了旧的类C中,然后隐藏了旧的类C的定义,但是这种方式可给类C定义一个新的方法,new_method(),而且我们也可以直接引用外部在类的外部已经定义好的函数,作为新增的方法

我们使用这种方式向类C中添加方法mutate()来扩充这个类

class MutationFuzzer(MutationFuzzer):
    def mutate(self, inp):
        return mutate(inp)

继续回到刚才的思路,我们需要不断地生成进行了不同程度的变异的字符串,因此我们定义一个方法create_candidate()用来随机生成字符变异程度在min_mutationsmax_mutations之间的新的字符串

class MutationFuzzer(MutationFuzzer):
    def create_candidate(self):
        candidate = random.choice(self.population)
        trials = random.randint(self.min_mutations, self.max_mutations)
        for i in range(trials):
            candidate = self.mutate(candidate)
        return candidate

利用fuzz()方法用来生成不同的字符串

    def fuzz(self):
        if self.seed_index < len(self.seed):
            # Still seeding
            self.inp = self.seed[self.seed_index]
            self.seed_index += 1
        else:
            # Mutating
            self.inp = self.create_candidate()
        return self.inp

接下来进行测试以上的代码

seed_input = "http://www.google.com/search?q=fuzzing"
mutation_fuzzer = MutationFuzzer(seed=[seed_input])
mutation_fuzzer.fuzz()

'http://www.google.com/search?q=fuzzing'
我们可以不断调用函数,生成新的字符串

mutation_fuzzer.fuzz()

'http://www.gogl9ecom/earch?qfuzzing'

'htotq:/www.googleom/yseach?q=fzzijg'

0x04 测试正确生成url的类的覆盖率

我们已经可以生成符合结构url结构的任意url,那么我们现在来测试一下生成这个url的代码的覆盖率

我们引入第二节写的Runner类,并且定义一个新的类FunctionRunner来继承Runner,这个类用来测试我们生成的url是否正确且符合url格式

from Fuzzer import Runner

class FunctionRunner(Runner):
    def __init__(self, function):
        """Initialize.  `function` is a function to be executed"""
        self.function = function

    def run_function(self, inp):
        return self.function(inp)

    def run(self, inp):
        try:
            result = self.run_function(inp)
            outcome = self.PASS
        except Exception:
            result = None
            outcome = self.FAIL

        return result, outcome
http_runner = FunctionRunner(http_program)#调用已定义的http_program方法
http_runner.run("https://foo.bar/")

运行结果通过
(True, 'PASS')

我们现在可以拓展类FunctionRunner,定义类FunctionCoverageRunner继承类FunctionRunner,来测量函数的覆盖率,继续引入之前写方法coverage()

from Coverage import Coverage, population_coverage
class FunctionCoverageRunner(FunctionRunner):
    def run_function(self, inp):
        with Coverage() as cov:
            try:
                result = super().run_function(inp)
            except Exception as exc:
                self._coverage = cov.coverage()
                raise exc

        self._coverage = cov.coverage()
        return result

    def coverage(self):
        return self._coverage

读取被覆盖代码的的前五行

print(list(http_runner.coverage())[:5])

[('urlsplit', 402), ('http_program', 10), ('http_program', 3), ('__exit__', 25), ('urlparse', 373)]

接下来我们创建一个主类,用来生成一个统计每次覆盖的集合,以及输出利用fuzzer()生成的正确格式的ur列表(self.population中)

class MutationCoverageFuzzer(MutationFuzzer):
    def reset(self):
        super().reset()
        self.coverages_seen = set()
        # Now empty; we fill this with seed in the first fuzz runs
        self.population = []

    def run(self, runner):
        """Run function(inp) while tracking coverage.  If we reach new coverage, add inp to population and its coverage to population_coverage """
        result, outcome = super().run(runner)
        new_coverage = frozenset(runner.coverage())
        if outcome == Runner.PASS and new_coverage not in self.coverages_seen:
            # We have new coverage
            self.population.append(self.inp)
            self.coverages_seen.add(new_coverage)

        return result

执行

seed_input = "http://www.google.com/search?q=fuzzing"
mutation_fuzzer = MutationCoverageFuzzer(seed=[seed_input])
mutation_fuzzer.runs(http_runner, trials=10000)
mutation_fuzzer.population

['http://www.google.com/search?q=fuzzing',
'http://www.goog.com/search;q=fuzzilng',
'http://ww.6goog\x0eoomosearch;/q=f}zzilng',
'http://uv.Lboo.comoseakrch;q=fuzilng',
'http://ww\x7fw.gog+.com/s>earch;q=fuzzing',
'Http://www.g/ogle.com/earchq=fuzzing',
'httP://ww\x7fw.gog+.coM-s>earch;q=fuzzine',
'http://www.gokgl.#om/searsh?q}fuzzing',
"http://$\x7fw,gokgl.#om/searsh'?3q}fuziFng",
'httP://ww\x7fw.gog+.coEM-s>aarch;q=fuzzine',
'http://ww.6goog\x0eoomsearch;/=f}zzilng',
'httP://ww\x7fw.gog+.c#oM-s>earch;q=fuzine',
'httP://ww\x7fu/go+.coMA\rs<ercx;q=fuzine',
'httP://ww\x7fw.gog+.c#nM-s>eavch;q=fuzine',
'http://wuw/6goo\x0eoomosrch;/q=f}zzilng',
'httpS://wuw/6go\x0eoomosrch;/qq=f}zzilng',
'http://wwwXq.gokgl/;#om/e!rsh7?q}f(uzzi]ng',
'httP://ww\x7fwgog+.coM-)s?earc;q=fuzine',
'http://wwK.google.com/search?q=fuzzing',
[还有很多就不一一写出来了]

我们可以看见成功生成了符合条件的字符串,同时使用matplotlib.pyplot模块做出增长趋势图像,观察每次随机输入的url的覆盖率

all_coverage, cumulative_coverage = population_coverage(
    mutation_fuzzer.population, http_program)

import matplotlib.pyplot as pltplt.plot(cumulative_coverage)
plt.title('Coverage of urlparse() with random inputs')
plt.xlabel('# of inputs')plt.ylabel('lines covered');

Image6-1.png

大功告成~

[+] 学会了如何写一个符合输入要求的随机输入模块
[+] 如何对输入进行突变

Last modification:January 20th, 2019 at 11:12 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment