Fuzzing software: common challenges and potential solutions 정리

Fuzzing software: common challenges and potential solutions

원문 글

• https://securitylab.github.com/research/vlc-vulnerability-heap-overflow/
• https://securitylab.github.com/research/fuzzing-challenges-solutions-1/
• https://securitylab.github.com/research/fuzzing-software-2/

1. Fuzzing command-line arguments

- Boolean arguments  ->  1bit
- Float and integer arguments  ->  4/8 bytes
- Variable-length string  ->  fixed-size array

각 설정의 타입을 예측하고, 이 모든 설정 값들을 나타낼 수 있는 block 하나를 생성하여 input file 앞에 붙인다.

ex) zeroed block + input file = new input file

이런 식으로 데이터를 생성하면, 결과적으로 zeroed block에 해당하는 데이터(= arguments) 역시 fuzzer에 의해 mutate된다.

harness에서 input 파일의 zeroed block에 해당하는 데이터를 읽어들여서 argument를 구성하고, argument를 제외한 input file 데이터를 인자로 넣어서 프로세스를 실행하게 하면 끝.

2. Splitting up comparisons

만약 다음과 같은 코드가 존재할 때, random으로 데이터를 mutate하는 AFL의 경우 새로운 path를 찾기 매우 힘들다. 랜덤으로 mutate하여 32-bit의 특정 값을 찾아내는 것은 매우 비효율적이며 code coverage를 증가시키기 힘들다.

if (getData(buf) == 0x12345678){
    bugTrigger();
}

이를 해결하기 위한 방법은 Symbolic Execution을 이용한 방법 등 몇 가지가 존재하는데, 그 중 한 가지 방법은 다음과 같이 이 4 bytes 데이터를 1 byte씩 쪼개는 것이다.

if (getData(buf) >> 24 == 0x12 ){
    if ((getData(buf) & 0xff0000) >> 16 == 0x34){
        if ((getData(buf) & 0xff00) >> 8 == 0x56){
            if ((getData(buf) & 0xff) == 0x78){
                bugTrigger();
            }
        }
    }
}

비슷하게 switch case 문 역시 if-else 조건 문으로 변경한다.

이러한 동작을 수행해주는 것으로 Laf-intel이라는 AFL plugin이 존재하며, LLVM 컴파일 시간에 위와 같은 "deoptimized" 동작을 수행해준다.

다양한 AFL plugin이 적용된 AFL++는 역시 위의 plugin까지 포함하고 있다. 다음과 같은 옵션을 통해 적용이 가능하다.

export AFL_LLVM_LAF_SPLIT_SWITCHES=1
export AFL_LLVM_LAF_TRANSFORM_COMPARES=1
export AFL_LLVM_LAF_SPLIT_COMPARES=1
export AFL_LLVM_LAF_SPLIT_FLOATS=1

2. Providing a custom dictionary

앞에서 설명한 접근법으로도 해결하지 못하는 상황이 있을 수 있다. 애초에 Fuzzer로 constant value를 예측하는 것이 매우 비실용적이고 비효율적이기 때문에, custom dictionary를 구축하는 것이 더 유용한 경우도 있다.

ex) GUID 같이 긴 string value를 다루는 경우

본문에서는, 이런 비교하는 긴 string 값을 알아내기 위하여, CodeQL을 사용해서 strcmp / memcmp 등의 함수에서 비교하는 인자의 string 값을 읽어오는 방식을 사용했다.

import cpp

from StringLiteral l, Call fc
where l.getFile().getBaseName() = "ogg.c"
        and (fc.getTarget().getQualifiedName() = "memcmp" or fc.getTarget().getQualifiedName() = "strcmp")
        and fc.getAnArgument() = l
select l.getValueText()

'''
"index"
"fLaC"
"SPOTS\0\0"
...

'''

import cpp

from GlobalVariable gb
where gb.getFile().getBaseName() = "libasf_guid.h"
select gb

'''
0xFD3CC02A, 0x06DB, 0x4CFA, {0x80, 0x1C, 0x72, 0x12, 0xd3, 0x87, 0x45, 0xE4}
...

'''

AFL에는 XML 등의 형태로 custom dictionary를 다룰 수 있는 다양한 plugin이 존재하는데, 느려서 structure-aware fuzzing이 더 유용하다고 한다.

또한, 종종 command-line arguments 중 token으로 dictionary를 제공할 수 있는 경우가 존재한다. 이러한 경우에는 argument를 유용하게 사용할 수 있다.

3. Dealing with checksums

Fuzzer가 실행되면서 checksum 루틴에서 종료되는 경우가 있다. 이러한 경우 취할 수 있는 전략은 총 두 가지인데, 다음과 같다.

• Re-calculate checksum
  fuzzer input에 대한 checksum을 다시 계산하여 input에 집어넣는다.
• Patch software
  software에서 checksum 비교하는 부분을 패치하여 제거하고, 코드 상에서 동작하는 checksum 필드의 값을 input의 checksum 값으로 변경한다.

종종 project를 빌드하는 과정에서 crc 기능을 없앨 수 있는 flag가 존재하는 경우가 있다. 이러한 경우 disable-crc 등의 기능을 유용하게 사용할 수 있다.

본문에서는 다음과 같은 형태로 코드를 패치했다.

/* Compare */
if( memcmp(chksum,page+22,4)) {
/* D’oh. Mismatch! Corrupt page (or miscapture and not a page at all) */
/* replace the computed checksum with the one actually read in */
memcpy(page+22,chksum,4)

4. Custom Coverage

분석하려는 타겟이 다양한 모듈을 사용할 때, 내가 분석하려는 모듈 이외에 다른 모듈로 path를 탈 수 있다. 예를 들어, ogg 파일을 input으로 집어 넣어 ogg demux(demultiplexer)에 대한 coverage를 측정하고 있을 때, 파일의 시그니처 부분이 mutate가 되어 avi demux로 path가 튈 수도 있다.

이러한 경우를 피하기 위해서 AFL++의 "whitelist" 기능을 사용할 수 있다. 컴파일 시 AFL_LLVM_WHITELIST 옵션을 사용하여 해당 기능을 이용할 수 있다.

5. More than ASAN

Sanitizer는 real-time에 취약점을 찾을 수 있는, compile-time에 활성화되는 라이브러리 Set 이다. 대표적으로 ASAN(Address Sanitizer) 이 있으며, 이는 다음과 같이 동작한다.

• 실제 메모리의 하나의 byte와 연관되어있는 각 bit를 같는 shadow memory bitmap을 생성한다.
• 컴파일 타임에 메모리 접근 함수/연산자들을 Intercept 한다.
• 인접한 메모리 영역(ex. 배열) 내의 변수에 대한 접근을 오염시킨다.

LLVM과 같은 컴파일러에서 ASAN을 활성화시키기 위해서는 다음과 같은 옵션을 추가하면 된다.

-fsanitize=address

이와 비슷하게 Undefined Behavior Sanitizer (UBSAN)과 Memory Sanitizer (MSAN)이 있다.

Undefined Behavior Sanitizer (UBSAN)

UBSAN은 undefined behavior를 탐지한다. UBSAN은 다음의 명령어로 활성화시킬 수 있다.

-fsanitize=undefined

UBSAN은 잠재적으로 높은 False Positive (실제 음성인데 결과는 양성일 경우)를 갖기 때문에, UBSAN의 몇 가지 옵션은 기본적으로 비활성화된다.

해당 옵션들까지 포함한 UBSAN의 옵션을 살펴보면 다음과 같다.

• undefined
  • Misaligned or null pointers
  • Signed integer overflows
  • Conversion to, from, or between floating-point types which would overflow the destination
• implicit-conversion
  • Checks for suspicious behavior of implicit conversions
• integer
  • Checks for undefined or suspicious integer behavior (e.g. unsigned integer overflow)
• nullability
  • Checks for nullability violation, e.g. passing null as a function parameter, assigning null to an lvalue, or returning null from a function
• local-bounds
  • It can catch cases missed by array-bounds

이러한 옵션은 다음과 같이 사용하여 활성화시킬 수 있다.

-fsanitize=address,undefined,implicit-conversion,integer,nullability

Memory Sanitizer (MSAN)

MSAN은 uninitialized read를 탐지한다. MSAN은 다음과 같은 옵션으로 활성화시킬 수 있다.

-fsanitize=memory

Options

만약 특정 함수를 Sanitizer 범위에 포함시키지 않고 싶다면 다음과 같이 함수의 정의(function definition) 전에 no_sanitize 특성을 사용하면 된다.

__attribute__((no_sanitize("integer")))
...
__attribute__((no_sanitize("implicit-conversion")))
__attribute__((no_sanitize("undefined")))

또한, UBSAN은 프로그램의 fail이 탐지되어도 crash를 생성하지 않는다. 따라서 AFL이 UBSAN issue를 찾게하려면, abort_on_error=1 옵션을 추가해야 한다.

알아두면 좋은 다른 옵션은 다음과 같다.

• check_initialization_order=true
  • 초기화 순서 문제를 탐지하는 것에 초점을 맞춰 컴파일된 프로그램에 체크 루틴을 삽입함
• detect_stack_use_after_return=true
  • 변수가 함수의 범위를 벗어나서도 사용되었을 때, 경고해줌
• strict_string_checks=true
  • 문자열 인자가 적절히 null로 끝나는지 검사함
• detect_invalid_pointer_pairs=2
  • 다른 포인터 쌍(포인터가 각자 다른 객체에 속해있는 경우)에 대한 연산자(<, <=, >, >=)를 찾음. 값이 클수록 찾기가 힘듬

퍼징의 경우 ASAN과 MSAN은 양립할 수 없다. (UBSAN은 예외). 모든 경우의 검사 세트를 수행하기 위해서는 타겟 소프트웨어에 대하여 다음의 두 가지의 세트로 진행해야 한다.

• ASAN + UBSAN
• MSAN

ASAN의 경우 아주 많은 량의 메모리를 소비하기 때문에, AFL의 옵션 중 메모리의 한계를 없애는 -m none 옵션을 적절히 사용해야 한다.

위에서 언급한 내용을 반영하여 AFL로 ASAN을 활성화시킨뒤, 퍼징하는 작업은 다음과 같은 command line을 사용할 수 있다.

ASAN_OPTIONS=verbosity=3,detect_leaks=0,abort_on_error=1,symbolize=0,check_initialization_order=true,detect_stack_use_after_return=true,strict_string_checks=true,detect_invalid_pointer_pairs=2 afl-fuzz -t 800 -m none -i ./AFL/afl_in/ -o './AFL/afl_out' -- ./myprogram -n -c @@

이와 비슷하게, 커널의 경우에 Kernel Sanitizer가 존재한다. KASAN, KMSAN, KCSAN... 등

More than Coverage

Coverage-guided fuzzing이란, 반복되는 퍼징 작업을 가이드하기 위해 code coverage를 일종의 feedback으로서 삼는 것이다. 이러한 접근 방법으로 인해, fuzzer는 사용자의 도움없이도 새로운 execution path를 찾는 것이 가능하다.

이러한 유형의 fuzzer는 feedback-driven fuzzer라는 더 넓은 범주에 속한다. 이 범주에는 새로운 input case를 생성하는데에 어느 정도의 feedback을 사용하는 모든 fuzzer가 속한다.

feedback-driven fuzzer의 좋은 예시로 FuzzFactory가 있다. FuzzFactory는 스스로 다음과 같이 설명한다.

FuzzFactory is an extension of AFL that generalizes coverage-guided fuzzing to domain-specific testing goals.

이 설명은 간단하지 않으므로 몇 가지 예시를 들어 설명하겠다.

• Execution path length를 최대화 한다.
  • 실행 경로가 더 깊은 곳에 도달하는 input이 더 높은 score를 받는다. 더 많은 명령어를 실행하는 input을 우선시한다.
• 동적 메모리 할당을 최대화하는 input
  • C/C++과 같은 메모리 unsafe 언어의 경우 동적 메모리 관리가 취약점의 원인이 된다는 것은 잘 알려진 사실이다. 그런 이유로, 메모리 할당 함수의 호출을 최대화하는 것은 새로운 버그를 찾는 데에 좋은 전략이 될 수 있다.
• Failed assertions의 수를 최소화한다.
  • assert의 조건을 충족시키지 못하여 프로세스가 일찍 종료되는 것을 피한다.

모든 예시가 coverage-guide fuzzing와 양립할 수는 없기 때문에, 좋은 code coverage를 찾은 후에 새로운 input case를 만드는데에 적용하는 보완법으로 사용할 수 있다.

Custom Mutators

Structure-aware-fuzzing은 퍼징 커뮤니티 내에서 유행어로서 사용되어 왔다. 앞서 언급했듯, 구조화된 코드 패턴을 다루기 위하여 일련의 딕셔너리를 사용할 수 있다. 그러나 이러한 접근 방식은 XML 같은 복잡한 문법을 갖는 경우에 대해서 꽤 부적절하기 때문에, 복잡한 문법을 갖는 경우에 structure-aware-fuzzing을 사용할 수 있다.

structure-aware-fuzzing을 생각하는데 도움이 되는 한 가지 방식은 custom mutator를 사용하는 것이다. 일반적으로, AFL은 사용자의 input corpus에 대하여 단순한 랜덤(bit/byte flipping, integer additions, blocks splice/deletion) mutator를 사용한다. 그러나 custom mutator의 사용을 통해 자신만의 structure-aware mutation을 사용할 수 있다.

예를 들어 다음과 같은 문법을 갖는 custom mutator를 만들었다고 하자.

expression    =    atom    |    list
atom        =    number    |    symbol
number        =    [+-]?['0'-'9']+
symbol        =    ['A'-'Z']['A'-'Z''0'-'9'].*
list        =    '(', expression*, ')'

AFL++는 두 가지 방식으로 custom mutator의 사용을 허용할 수 있다.

• C/C++ API AFL_CUSTOM_MUTATOR_LIBRARY envvar
• Python module AFL_PYTHON_MODULE envvar

다음에서는 C/C++ custom mutator를 어떻게 사용할 수 있는지 설명한다.

//Build your target using afl as usual
CC=”afl-clang-fast” ./configure
make

//Now, we build our custom mutator
gcc -shared -Wall -fPIC -O3 my_custom_mutator.c -o my_custom_mutator.so

//We should export the path to the generated .so
export AFL_CUSTOM_MUTATOR_LIBRARY="/home/user/my_custom_mutator.so"

//Now, we can run AFL fuzzer
afl-fuzz -i ‘./AFL/afl_in/’ -o ‘/AFL/afl_out/’ -- ./fuzzTest @@

만약 잘 되었다면, fuzzer의 display 화면의 fuzzing strategy yields 부분에서 custom에 해당하는 값이 증가하는 것을 확인할 수 있을 것이다.

자세한 사항은 AFL++ docs에서 확인할 수 있다.

또한 AFL++의 libprotobuf-mutator 라이브러리를 이용할 수도 있다. .proto 파일을 자신의 문법에 맞게 정의하여 사용하면 된다.

structure-aware-fuzzing은 과연 유용한가?

• 화자는 다음과 같은 시나리오에서 유용하다는 것을 발견했다.
  • software pipeline architecture를 퍼징할 때 (CPU pipelining을 혼란스럽게 하면 안됨)
  • 이러한 경우에, 각 요소의 output이 다음 요소의 input이 되는 패턴을 보인다.
  • 예를 들어, 컴파일러나 인터프리터에서 lexical 에러가 발생하면 다음의 semantic analysis가 수행되지 않는다.
• 모듈성이 적은 소프트웨어를 퍼징할 때, 예를 들어 많은 전역변수를 갖는 소프트웨어의 경우
• 복잡한 제약을 처리할 때, 예를 들어 request 순서가 결정적인 Web API.
  • 이러한 경우, input이 엄격한 순서로 오지 않으면, 실행 흐름은 빠른 단계에서 종료됨.

그와 반대로, structure-aware-fuzzing이 유용한 옵션이 아닌 경우는 다음과 같다.

• 소프트웨어가 높은 모듈성을 가질 경우
  • 이러한 경우, 각 모듈을 독립적으로 퍼징하는 것을 추천함.
• 상수를 다룰 경우
  • 대신에, 딕셔너리를 활용해라.
• Checksum이나 CRC를 다룰 경우
  • checksum을 계산하는 코드를 통해 퍼저를 복잡하게 만느느니, 차라리 코드 상에서 단순히 CRC를 비활성화해라.

각 접근 방식의 장단점을 서로 비교해야하는 많은 시나리오가 있으니, 알아서 고민해서 잘 해라. 예를 들어, input이 암호화되거나 압축되는 경우처럼

=> 결론적으로 input의 포맷에 민감한 경우 structure-aware-fuzzing이 유용하다.

More than just Crashes

일반적으로, 퍼징은 memory corruption 취약점을 찾는 기술이라고 알려져있다. 대부분 리포트되는 C/C++ 소프트웨어 버그가 이러한 유형이기 때문에. 이는 AFL과 LibFuzzer와 같은 Fuzzer는 fatal signal을 찾기 때문이다. 이러한 fatal signal은 보통 타겟 소프트웨어의 crash의 결과를 갖는다.

그러나 많은 사람들의 믿음과 대조적으로, 퍼징은 메모리 부실관리 취약점 탐지에만 국한되지 않는다. 퍼징을 통해서 logical bug를 찾는 것도 가능하다. 이러한 목적을 위해서 우리의 fuzzing triage pipeline을 "crash monitoring"에서 "event monitoring"으로 진화시켜야 한다.

이러한 문제를 해결하기 위해 다른 창의적인 방법이 있겠지만, 두 가지 접근법을 소개하도록 하겠다.

• Dead barrier를 추가하기
  • 코드 상에서 도달해서는 안되는 곳에 "dead barriers"를 추가한다.
  • 예를 들어 Apache 서버를 타겟으로 퍼징하고 있을 때, Login 이후의 코드에 다음과 같은 코드를 삽입한다.

  • void DeadBarrier(){
        memcpy(0, "deadhere", 10);
    }
    
    ...
    
    if (OK == rv){
        // authentication success!
        DeadBarrier();
         ...
    }

  • 만약 퍼징 작업동안 해당 취약점이 발견된다면, Apache authentication을 우회할 수 있는 취약점을 발견할 수 있을 것이다.
  • 이와 비슷하게 login을 비롯한 다른 위치의 코드에도 적용하여 logic 버그와 같은 프로그램의 상태 변화에 대한 취약점을 찾을 수 있을 것이다.
  • 프로그램의 특정 단계의 조건을 검사하는 assert을 작성하여 이를 구현할 수도 있다.
• External monitoring
  • 이 범주는 퍼징된 타겟의 결과를 외부에서 모니터링하는 것을 기반으로 하는 모든 기술을 포함한다. 다시 말해서, 퍼저가 그 자신의 이벤트를 "catch"한다는 것이 아니라, 타겟 소프트웨어 안에서의 퍼저가 만든 side effect를 모니터링하는 것이다.
  • Output/Logs monitoring
    • 이는 real-time monitoring이나 "a posteriori" (e.g. using log analytics)이 될 수 있다.
    • 단순한 접근 방식으로는 관련있는 단어나 일반적인 패턴을 찾기 위해 딕셔너리나 정규식을 사용할 수 있을 것이다. (이와 비슷한 것이 Burp Suite와 Zap 프록시가 동작하는 방식이다.)
    • 다른 복잡한 대안으로는, 패턴 인식 알고리즘이나 신경망을 이용할 수도 있을 것이다.
    • 두 가지 모두, ELK Stack와 Pattern같은 외부 라이브러리로 구현할 수 있다.
  • Monitoring/intercepting system call
    • 예를 들어, auditctl이나 syscall_intercept를 사용할 수 있다.
    • 파일 시스템의 read/write 이벤트를 모니터링하여 잠재적인 privilege를 조작할 수 있는 버그를 찾을 수 있다.

Conclusion

퍼징 작업을 향상시키고 리얼 월드 소프트웨어의 더 많은 취약점을 찾을 수 있는 다양한 테크닉에 대해 살펴봤다. 로직 버그에 대한 퍼징의 개념에 대하여 소개했으며, 앞으로 더 많은 퍼징 방법론과 기술의 비슷한 발전과 사용가능한 프로그램을 볼 수 있기를 기대한다.

현재 퍼징은 초기 단계이며, 앞으로 이 분야에서 많은 발전을 보게 될 것이다. 그러나 아무리 퍼징 기술이 발전할지라도, 리얼 월드 취약점을 찾기 위해서는 인간의 창의성과 독창적인 사고의 불꽃이 필요하다.

[https://github.com/AFLplusplus/AFLplusplus/blob/master/docs/custom_mutators.md]: