python에서는 urlparse 기능을 제공하여 위와 같이 구성 목록을 확인할 수 있다.
URL을 입력으로 하는 프로그램이 있다고 가정하고, URL이 올바르면 True, 아니라면 예외를 발생시킨다.
1 2 3 4 5 6 7 8 9 10 11
defhttp_program(url: str) -> bool: supported_schemes = ["http", "https"] result = urlparse(url) if result.scheme notin supported_schemes: raise ValueError("Scheme must be one of " + repr(supported_schemes)) if result.netloc == '': raise ValueError("Host must be non-empty")
# Do something with the URL returnTrue
위 프로그램을 완전 랜덤 퍼징으로 진행해본다.
1 2 3 4 5 6 7
for i inrange(1000): try: url = fuzzer() result = http_program(url) print("Success!") except ValueError: pass
올바른 URL을 얻을 확률은 얼마나 될까?
먼저 “http://“, “https://“ 로시작하는 문자열이 필요하다.
또한 url 구조에 알맞은 형태로 값이 들어가야 한다.
성공적으로 랜덤 input을 만들기까지 몇 달에서 몇년이 걸릴 것이며 이는 http_program()에 들어갈 하나의 성공적인 실행을 얻기 위한 것이다.
Mutation Inputs
처음부터 랜덤 input을 생성하는 것의 대안은 주어진 유효한 입력으로 시작한 다음 그 입력을 mutate하는 방식이다.
mutate 방식에는 문자 삽입, 문자 삭제, 비트 플립이 있다.
이러한 방식을 Mutation fuzzing이라 부른다.
1 2 3 4 5 6 7 8
defdelete_random_character(s: str) -> str: """Returns s with a random character deleted""" if s == "": return s
classMutationFuzzer(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()
defreset(self) -> None: """Set population to initial seed. To be overloaded in subclasses.""" self.population = self.seed self.seed_index = 0
classMutationFuzzer(MutationFuzzer): defmutate(self, inp: str) -> str: return mutate(inp) defcreate_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 inrange(trials): candidate = self.mutate(candidate) return candidate deffuzz(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 함수를 살펴보면 먼저 seed 리스트에 있는 문자열을 한 번씩 사용 후, create_candidate()함수를 호출해 mutate하게 된다.
input의 다양성이 높을수록 유효하지 않은 값이 생길 수 있다. 하지만 이러한 mutation을 guide하는 것이 핵심 아이디어다.
즉 가치있는 mutation을 유지하는 것이다.
Guiding by Coverage
테스트는 항상 프로그램을 실행하므로 실행 정보를 수집할 수 있다.
최소한 테스트의 통과 여부를 결정하는데 필요한 정보는 필요하다.
커버리지는 테스트 품질을 결정하기 위해 자주 측정되므로 테스트 실행의 커버리지도 검색할 수 있다 가정한다.
우리는 어떻게 커버리지를 to guide test generation 하기 위해 활용할 수 있을까?
성공적인 아이디어는 AFL이라는 퍼저에서 구현된다.
AFL은 성공적인 테스트 사례를 발전 시킨다.
AFL에서 “성공”은 프로그램 실행을 통해 새로운 경로를 찾는 것이다.
이런식으로 AFL은 지금까지 새로운 경로를 찾았던 입력을 계속 mutate할 수 있으며,
입력이 다른 경로를 찾더라도 이 또한 유지가 된다.
urlparse를 대상으로 이를 구현해본다.
FunctionRunner Class
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classFunctionRunner(Runner): def__init__(self, function: Callable) -> None: """Initialize. `function` is a function to be executed""" self.function = function
classMutationCoverageFuzzer(MutationFuzzer): """Fuzz with mutated inputs based on coverage"""
defreset(self) -> None: super().reset() self.coverages_seen: Set[frozenset] = set() # Now empty; we fill this with seed in the first fuzz runs self.population = []
defrun(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 notin self.coverages_seen: # We have new coverage self.population.append(self.inp) self.coverages_seen.add(new_coverage)
