[Fuzzing] Lecture 2. Lexical Fuzzing : Mutation-Based Fuzzing

Mutation-Based Fuzzing

:  대부분의 무작위로 생성된 입력은 구문적으로 잘못되어 처리 프로그램에서 빠르게 거부된다. 입력 처리 외의 기능을 테스트하려면 유효한 입력을 얻을 가능성을 높여야 한다. 이를 위해 기존 입력에 작은 변화를 주어 유효성을 유지하면서도 새로운 동작을 유도하는 변이 퍼징(mutational fuzzing)이 있다. 이번에는 변이 생성 방법과 이를 이용해 미처 test 되지 않은 code 를 탐색하는 방법을 다룬다. 이는 유명한 AFL 퍼저(AFL fuzzer)의 핵심 개념을 적용한 것이다.

 

 

 

• MutationFuzzer class : 기존의 유효한 입력을 변이시켜 새로운 입력을 생성하는 클래스이다.

def mutate(s: str) -> str:
    """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)

from .Fuzzer import Fuzzer

class MutationFuzzer(Fuzzer):
    """Base class for mutational fuzzing"""

    def __init__(self, seed: List[str],
                 min_mutations: int = 2,
                 max_mutations: int = 10) -> None:
        """Constructor.
        `seed` - a list of (input) strings to mutate.
        `min_mutations` - the minimum number of mutations to apply.
        `max_mutations` - the maximum number of mutations to apply.
        """
        self.seed = seed
        self.min_mutations = min_mutations
        self.max_mutations = max_mutations
        self.reset()

    def reset(self) -> None:
        """Set population to initial seed.
        To be overloaded in subclasses."""
        self.population = self.seed
        self.seed_index = 0

class MutationFuzzer(MutationFuzzer):
    def mutate(self, inp: str) -> str:
        return mutate(inp)

class MutationFuzzer(MutationFuzzer):
    def create_candidate(self) -> str:
        """Create a new candidate by mutating a population member"""
        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

class MutationFuzzer(MutationFuzzer):
    def fuzz(self) -> str:
        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

 

1. seed: 변이의 초기 입력 문자열 list
2. create_candidate(self) -> str : 새로운 후보 문자열을 생성하는 메소드. population 에서 임의의 문자열을 선택하고, 최소 min_mutations 에서 최대 max_mutations 까지 random 한 횟수만큼 mutation 을 적용하여 새로운 문자열을 생성
3. fuzz(self) -> str : 새로운 입력을 생성하는 메소드. seed list 에 있는 초기 입력을 순차적으로 사용하다가, 모든 입력을 사용하면 create_candidate() 를 통해 mutation 된 새로운 입력을 생성한다. 

 

• MutationCoverageFuzzer class : input 의 population 을 유지하며, 이를 진화시켜 coverage 를 maximize 한다.

from .Coverage import Coverage, population_coverage, Location

class MutationCoverageFuzzer(MutationFuzzer):
    """Fuzz with mutated inputs based on coverage"""

    def reset(self) -> None:
        super().reset()
        self.coverages_seen: Set[frozenset] = set()
        # Now empty; we fill this with seed in the first fuzz runs
        self.population = []

    def run(self, runner: FunctionCoverageRunner) -> Any:  # type: ignore
        """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

 

주어진 runner 객체를 사용하여 입력을 실행하고, 그 실행 중에 발생한 커버리지를 추적한다. new_coverage는 runner.coverage() 메서드를 호출하여 얻은 커버리지 정보를 frozenset으로 변환하여 저장한다. 이는 변경 불가능한 세트로, 커버리지의 중복을 방지하고 새로운 커버리지를 추적하기 용이하다.

 

예제를 살펴보자.

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

 

mutation_fuzzer = MutationCoverageFuzzer(seed=[seed_input])
mutation_fuzzer.runs(http_runner, trials=10000)
mutation_fuzzer.population[:5]

 

Fuzzing with Mutations

: 2013년 11월, American Fuzzy Lop(AFL)의 첫 번째 버전이 출시되었다. 그 이후로 AFL은 가장 성공적인 퍼징 도구 중 하나가 되었으며, 여러 가지 변형으로 제공된다. AFL은 자동 취약점 탐지에서 퍼징을 인기 있는 선택으로 만들었다. 특히, 많은 보안 관련 실제 애플리케이션에서 자동으로 취약점을 대규모로 탐지할 수 있음을 처음으로 보여주었다.

 

 

Fuzzing a URL Parser

: 많은 프로그램은 입력이 특정 형식으로 되어야만 처리할 수 있다. 예를 들어, 웹 주소인 URL을 받는 프로그램을 생각해 보자. URL은 프로그램이 처리할 수 있는 유효한 형식이어야 한다. 무작위 입력으로 퍼징할 때 실제로 유효한 URL을 생성할 확률은 얼마나 될까?

 

URL 은 여러 요소로 구성된다.

scheme://netloc/path?query#fragment

• scheme : 사용할 프로토콜 
  ex) http, https, ftp, file ...
• netloc : 연결할 호스트의 이름
  ex) www.google.com
• path : 호스트의 경로
  ex) search
• query : 키/값 쌍의 목록
  ex) q = fuzzing
• fragment : 가져온 문서에서 위치를 나타내는 표시
  ex) # result
  
  

Python 에서는 urlparse() 함수를 사용하여 URL 을 파싱하고 그 부분을 나눌 수 있다.

from urllib.parse import urlparse
urlparse("http://www.google.com/search?q=fuzzing")

 

 

전달된 URL이 유효한지 확인하도록 해보자. URL이 유효하면 True를 반환하고, 그렇지 않으면 예외를 발생시킨다.

def http_program(url: str) -> bool:
    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

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

 

이제, 1000개의 random input 을 fuzzing 해보고 성공 여부를 확인해보자.

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

 

실제로 유효한 URL을 생성할 확률은 얼마나 될까? 문자열이 "http://" 또는 "https://"로 시작해야 한다. "http://"의 경우 특정한 7개의 문자가 필요하다. 96개의 문자 범위에서 이러한 7개의 문자를 무작위로 생성할 확률은 1/96^7 이다.
" https://"의 경우 확률은 더 낮아진다. 1/96^8로, 총 확률은 다음과 같다.

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

 

이 확률을 기반으로 유효한 URL scheme 을 생성하는 데 필요한 평균 실행 수는 다음과 같다.

1 / likelihood
>> 74370059689055.02

 

이제, http_program() 의 한 번 실행에 걸리는 시간을 측정해보자.

from Timer import Timer
trials = 1000
with 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
>> 2.51829...

 

한 번 실행하는데 약 2.5초 밖에 안걸리지만, 많은 실행을 해야 한다.

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

 

이는 아래와 같이 변환된다. (시간, 일, 년)

hours_until_success = seconds_until_success / 3600
days_until_success = hours_until_success / 24
years_until_success = days_until_success / 365.25

years_until_success
>> 59.34719...

 

아무리 병렬화해도 몇 달에서 몇 년이 걸린다. 이는 http_program() 을 더 깊이 test 할 수 있는 하나의 성공적인 실행을 얻기 위한 것이다.

 

기본 fuzzing 이 잘 수행할 수 있는 것은 urlparse() 를 test 하는 것이다. 이 parsing function 에 오류가 있으면 발견할 가능성이 높다. 그러나 valid 한 input 을 생성하지 못하는 한, 더 깊은 function 에 도달할 가능성이 없다.

 

 

Mutating Inputs

: random string 을 처음부터 생성하는 것에 대한 대안으로 주어진 valid한 input 으로 시작하여 이후에 이를 mutate 시키는 방법이 있다. 이 맥락에서 변이는 간단한 문자열 조작이다. 예를 들어, random 문자를 삽입하거나, 문자를 삭제하거나, 문자 표현에서 비트를 뒤집는 것 등을 말합니다. 이를 mutational fuzzing 이라고 하며, 이전에 논의된 generational fuzzing 기술과 대조된다.

 

다음은 변이를 시작할 수 있는 몇 가지 예이다.

1. 문자 삭제

import random
def delete_random_character(s: str) -> str:
    """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))

 

참고로, repr(x)은 객체 x 를 문자열로 반환하는 함수이다.

 

2. random 문자 삽입

def insert_random_character(s: str) -> str:
    """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)))

 

3. 비트 뒤집기

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)
    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)))

 

아래는 위의 3가지 변이 중 어떤 변이를 적용할 지 random 하게 select하는 random mutate 함수이다.

def mutate(s: str) -> str:
    """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")))

 

이제 valid 한 input 이 있다면 위의 변이 중 하나를 적용하여 더 많은 input candidate 를 생성할 수 있다. 이것이 어떻게 작동하는지 살펴보기 위해 다시 URL로 돌아가 보자. 

 

Mutating URLs

URL 파싱 문제로 돌아가 보자. input 이 http_program()에서 수용 가능한지 확인하는 함수 is_valid_url()을 만들어 보자.

def is_valid_url(url: str) -> bool:
    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에 mutate() 함수를 적용하고 몇 개의 유효한 입력을 얻는지 확인해 보자

seed_input = "http://www.google.com/search?q=fuzzing"
valid_inputs = set()
trials = 20

for i in range(trials):
    inp = mutate(seed_input)
    if is_valid_url(inp):
        valid_inputs.add(inp)

 

원래의 input 을 mutate 함으로써 높은 비율의 유효한 입력을 얻을 수 있음을 알 수 있다.

len(valid_inputs) / trials
>> 0.8

 

그렇다면, http: 샘플 시드 입력을 변이하여 https: 접두사를 생성할 확률은 얼마나 될까?

 

올바른 문자 's'(1 / 96) 를 올바른 위치(1 / l)에 삽입(1/3)해야 합니다. 여기서 l은 seed input 의 길이다. 평균적으로 필요한 실행 횟수는 다음과 같다.

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

 

from Timer import Timer
trials = 0
with 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

 

물론, "ftp://" 접두사를 얻으려면 더 많은 변이와 실행이 필요하다. 그러나 가장 중요한 것은 여러 번의 변이를 적용해야 한다는 것이다.

 

Multiple Mutations

지금까지 우리는 샘플 문자열에 단일 변이만 적용했다. 그러나 여러 번의 변이를 적용하여 더 변경할 수도 있다. 예를 들어 샘플 문자열에 20번의 변이를 적용하면 어떻게 될까?

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

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

 

원래의 시드 입력은 거의 알아볼 수 없게 되었다. 입력을 계속 변이시키면 입력의 다양성이 증가한다.

 

이러한 여러 변이를 단일 패키지에 구현하기 위해 MutationFuzzer 클래스를 도입해 보자. 이 클래스는 시드(문자열 목록)와 최소 및 최대 변이 수를 입력으로 받는다.

from Fuzzer import Fuzzer
class MutationFuzzer(Fuzzer):
    """Base class for mutational fuzzing"""

    def __init__(self, seed: List[str],
                 min_mutations: int = 2,
                 max_mutations: int = 10) -> None:
        """Constructor.
        `seed` - a list of (input) strings to mutate.
        `min_mutations` - the minimum number of mutations to apply.
        `max_mutations` - the maximum number of mutations to apply.
        """
        self.seed = seed
        self.min_mutations = min_mutations
        self.max_mutations = max_mutations
        self.reset()

    def reset(self) -> None:
        """Set population to initial seed.
        To be overloaded in subclasses."""
        self.population = self.seed
        self.seed_index = 0

 

이후에 MutationFuzzer를 개발하여 더 많은 메서드를 추가해 보자. Python 은 모든 메서드를 단일 연속 단위로 정의해야 하지만, 우리는 하나씩 메서드를 도입하고자 한. 이 문제를 피하기 위해 특별한 hack 을 사용한다: C라는 클래스에 새 메서드를 도입하려는 경우, 다음과 같은 구문을 사용한다.

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

 

이는 C를 자기 자신의 하위 클래스로 정의하는 것처럼 보이지만 실제로는 이전 C 클래스의 하위 클래스로 새로운 C 클래스를 도입한 다음 이전 C 정의를 그림자로 만드는 것이다. 이렇게 하면 new_method()를 메서드로 가진 C 클래스를 얻게 되며, 우리가 원하는 바로 그 것이다. (이전에 정의된 C 객체는 이전 C 정의를 유지하므로 다시 빌드해야 한다.)

 

이 hack 을 사용하여 이제 위의 mutate() 함수를 실제로 호출하는 mutate() 메서드를 추가할 수 있다. mutate()를 메서드로 가지는 것은 나중에 MutationFuzzer를 확장할 때 유용하다.

class MutationFuzzer(MutationFuzzer):
    def mutate(self, inp: str) -> str:
        return mutate(inp)

 

이제 우리의 전략으로 돌아가서 인구의 커버리지 다양성을 최대화해 보자. 먼저, 현재 인구( self.population )에서 무작위로 입력을 선택한 다음 min_mutations에서 max_mutations 사이의 변이 단계를 적용하여 최종 결과를 반환하는 메서드 create_candidate()를 만들어 보자.

class MutationFuzzer(MutationFuzzer):
    def create_candidate(self) -> str:
        """Create a new candidate by mutating a population member"""
        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() 메서드는 먼저 시드를 선택하도록 설정되어 있다. 시드가 사라지면 변이를 적용한다.

class MutationFuzzer(MutationFuzzer):
    def fuzz(self) -> str:
        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

 

여기 fuzz() 메서드의 작동 방식이 있다. fuzz()를 새로 호출할 때마다 여러 변이가 적용된 또 다른 변형을 얻는다.

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' # seed

mutation_fuzzer.fuzz()
>> 'http://www.gogl9ecom/earch?qfuzzing'

mutation_fuzzer.fuzz()
>> 'htotq:/www.googleom/yseach?q=fzzijg'

 

입력의 다양성이 높아지면 유효하지 않은 입력이 나올 위험도 커진다. 성공의 열쇠는 이러한 변이를 안내하는 데 있다. 즉, 특히 가치 있는 변이를 유지하는 것이다.

 

 

Guiding by Coverage

기능을 최대한 많이 다루기 위해서는 "커버리지" 장에서 논의한 대로 명시된 기능이나 구현된 기능에 의존할 수 있다. 지금은 프로그램 동작의 명세가 있다고 가정하지 않겠다. (물론 명세가 있는 것이 좋다). 하지만 test 할 프로그램이 존재하며, 그 구조를 활용하여 테스트 생성을 안내할 수 있다고 가정하자.

 

테스트는 항상 해당 프로그램을 실행하므로 실행에 대한 정보를 항상 수집할 수 있다. 최소한 test 가 통과했는지 실패했는지를 결정하는 데 필요한 정보가 있다. 테스트 품질을 결정하기 위해 커버리지를 자주 측정하기 때문에 테스트 실행의 커버리지를 가져올 수 있다고 가정해 보자. 그렇다면 커버리지를 활용하여 test 생성을 안내할 수 있는 방법은 무엇일까?

 

특히 성공적인 아이디어 중 하나는 인기 있는 퍼저인 American fuzzy lop, 줄여서 AFL에 구현되어 있다. 위의 예시들처럼 AFL은 성공적인 test case 를 발전시킨다. 그러나 AFL에서 "성공"은 프로그램 실행을 통해 새로운 경로를 찾는 것을 의미한다. 이렇게 해서 AFL은 새로운 경로를 발견한 입력을 계속 변이할 수 있다. 그리고 입력이 또 다른 경로를 찾으면 그것도 유지된다.

 

이러한 전략을 구축해 보자. 주어진 함수에 대한 커버리지를 포착하는 Runner 클래스를 소개하는 것으로 시작한다. 먼저, FunctionRunner 클래스이다.

from Fuzzer import Runner
class FunctionRunner(Runner):
    def __init__(self, function: Callable) -> None:
        """Initialize.  `function` is a function to be executed"""
        self.function = function

    def run_function(self, inp: str) -> Any:
        return self.function(inp)

    def run(self, inp: str) -> Tuple[Any, str]:
        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_runner.run("https://foo.bar/")
>> (True, 'PASS')

 

이제 커버리지를 측정하도록 FunctionRunner 클래스를 확장할 수 있다. run()을 호출한 후, coverage() 메서드는 마지막 실행에서 달성한 커버리지를 반환한다.

from Coverage import Coverage, population_coverage, Location
class FunctionCoverageRunner(FunctionRunner):
    def run_function(self, inp: str) -> Any:
        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) -> Set[Location]:
        return self._coverage

http_runner = FunctionCoverageRunner(http_program)
http_runner.run("https://foo.bar/")
>> (True, 'PASS')

 

다음은 커버된 첫 다섯 개 위치이다.

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

 

이제 주요 클래스로 넘어간다. 우리는 인구와 이미 달성한 커버리지 집합(coverages_seen)을 유지한다. fuzz() 도우미 함수는 입력을 받아 주어진 function()을 실행한다. 커버리지가 새로우면(즉, coverages_seen에 없으면) 입력이 population에 추가되고 커버리지는 coverages_seen에 추가된다.

class MutationCoverageFuzzer(MutationFuzzer):
    """Fuzz with mutated inputs based on coverage"""

    def reset(self) -> None:
        super().reset()
        self.coverages_seen: Set[frozenset] = set()
        # Now empty; we fill this with seed in the first fuzz runs
        self.population = []

    def run(self, runner: FunctionCoverageRunner) -> Any:
        """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

 

성공! 우리의 인구에서는 이제 모든 입력이 유효하며, 스키마, 경로, 쿼리 및 조각의 다양한 조합에서 비롯된 다른 커버리지를 가지고 있다.

all_coverage, cumulative_coverage = population_coverage(
    mutation_fuzzer.population, http_program)
import matplotlib.pyplot as plt
plt.plot(cumulative_coverage)
plt.title('Coverage of urlparse() with random inputs')
plt.xlabel('# of inputs')
plt.ylabel('lines covered');

 

이 전략의 좋은 점은 더 큰 프로그램에 적용할 때 하나의 경로에서 다른 경로로 기쁘게 탐색할 수 있다는 것이다. 필요한 것은 커버리지를 포착할 수 있는 수단이다.