생각

• Beacon의 precond-infer 사용.
• has the potential to improve the performance of other directed fuzzers 라는데 유의깊게 볼구절인가? 해결 : RQ3이다.
• 이런것도 symbolic execution으로 볼 수 있나?

개요

2024 다중 지향성 퍼징 중국 논문. 타깃간 상관 고려

배경

PAFL: Extend fuzzing optimizations of single mode to industrial parallel mode

• deploying multiple concurrent fuzzer instances
• 여러 타깃을 위해 이걸 쓰는건 impractical
• Most other directed fuzzers [2], [10]–[14] do not support reproducing multiple targets simultaneously anyway

Some other tries w/ avg. CFG dist.

• [15]–[18] have endeavored to address multiple targets simultaneously using general feedback, e.g., average control-flow distance,
• their effectiveness significantly diminishes when tackling multiple target
• \(\S\) 5.1 : AFLGo는 멀티타깃 지원하니 멀티로 한번에 넣은 걸 -Multi, 하나씩 넣고 병렬 돌리는 걸 -Single이라고 말하자.
• AFLGo-Multi [15] 에 넣어보니, 그냥 AFLGo-Single 병렬로 한 뻐저보다 3.2x 느림, 각 타깃 reproduce하는 데 든 평균시간이. AFLGo-Single 병렬뻐저가 쓴 시간을 다 더하면, AFLGO-Multi보다 3.6x 느림.
• 문제의식 → 좀 나아져야 한다

문제

synergy ignorance problem

타깃간 상관(correlation)을 이용치 못함

• bias (avoid hard-to-reach), lowering prob. of exploring
• massive redundant executions
  • 타깃1과 3가는 패스가 다를때, 패스 상관을 모르는 뻐저는 1과 3을 동시에 못감을 모르고 갈팡질팡한다

전략

직관

타깃 상관 ≒ 타깃의 feasible condition간 상관, 특히 independence와 contradiction

contradiction

eg_ b가 인풋의 2번째 coordinate라 하자. 아! 타깃1과 2는 b≤1조건이 다르구나. contradiction. 그러면 타깃1은 b≤1인 시드A가, 2는 b>1인 시드B가 가자.

independence

multiple input bytes could affect different targets independently

즉, a와 d가 indep.니까 a와 d를 동시에 변형시켜 타깃1과 3 동시에 노리자 (타깃1은 최소한 a>5조건이 있어야 가고, 타깃3은 d가 수문장임)

핵심

CFG대신 path condition으로 디렉팅.

synergy-aware scheduling strategy

finds the seed potentially reaching the most targets with a fine-grained ranking of the seeds

multi-target-oriented mutation

여러타깃 동시접근해서, fewer executions needed

실제

Instrumentation (on LLVM BC)

현재는 cheap, precise한 정적분석으로 타깃상관 밝힘

eg_ We can use the correlation, \(conflict(b, l_5, t_1, t_2)=true\), to know that the var. b defined at Line 2 influences targets 1 and 2.

결과 : The set of correlation, C(S), of the seed S is:

Synergy-aware scheduling strategy

seed가 있을 때, 타깃 필터링…

위 예제 이어서 ..- 시드 A, B가 타깃 1,2를 가야 한다고 보자. A, B 실행시켰을때 된 b의 값으로 A가 1, B가 2 가야 한다는걸 알게됨.

구체적으로, A=(a=6, b=3, c=1, d=1)에서 (T_res, T_conf, T_ind에 대한, 그리고 자세한, 알고리즘은 Algorithm 2)

…하고 우선순위 정하자

The seed input whose value satisfies the conditions for most variables should be prioritized.

Multi-target-oriented mutation

B_ti를, 직접 바꾸고 돌려봐서 구하긴 하지만, 모든 B_ti를 2^n개 다 하진 않는다.

1. dynamically infer the input bytes that can influence the values of the variables in the independent correlations using inference-based taint analysis [22FairFuzz], [25RedQueen], [26GreyOne].
2. mutate the bytes that influence the independent variables respectively

그래서 구현은?

For each byte, b, of seed, S, we measure the number of its influenced targets that have not been triggered as inf(b). We choose the bytes with probability, p, defined as follows: 이제 선택 안된 바이트 중, 선택된 것들과 indep.한 타깃을 공략하는 바이트를 또 flip한다.

inf(b)는 어떻게 구하나?

C(S)가 뭔가? variable마다 그게 reachability에 관여할 수도 있는 타깃을 모아 놨다. 그러면 이제 그 variable을 움직이는 byte들을 생각할 수 있다. ㅅㅇ. 생각보다 많을거 같은데..

벤치마크

• MAGMA : CVEs chosen from nine programs (that are freq’ly used for evaluating fuzzers). 이 중 6개만 쓴다.
  • 최근에 추가된 lua는 어떤 state-of-the-art fuzzer도 제대로 안돌아가므로 않으므로 뺀다.
  • sqlite3와 PhP는 파마산이 안돌아가므로 뺀다.
• MAGMA와 state-of-the-art directed fuzzer가 쓴 프로그램의 최신버전의 CVE들.
  • for reproducing ‘real vulnerabilities’ and detecting incomplete fixes of the previously reported bugs in the newest version of the programs.

통계

• We use the Mann-Whitney U Test to demonstrate the statistical significance of our framework’s contribution

결과

• Titan may require longer pre-analysis for larger programs, e.g., openssl and php, it is acceptable because the analysis time could be spent offline, and Titan saves more time during the fuzzing period.
• 결과는 Table 4에 있는데, 버그찾는 시간 (reproduction time)을 비교했다. Ratio (Titan보다 몇배 걸렸는지) 보니 Titan이 전반적으로 우수하다 (멀티타깃으로 실험해서 그런걸지도). 근데 Table5보니까 Ratio를 산술평균 낸거같은데.. 기하평균이나 조화평균이 낫지 않으려나 싶다. pvalue가 <0.01인게 많으니, 확실히 나아졌다고 보인다.

감상

멀티타깃은 역시 정적분석인데, 그걸 Beacon을 그대로 끌어서 내다니 부러운 연구다. 성능이 너무 많이 좋아졌는데, 자신들이 ‘멀티 타깃에서 타깃간의 관계를 고려한 첫 사람들’이라는 점을 강조하니, 납득이 일견 가면서도, 정적분석으로 구간이 이렇게 명확히까지 나뉘나? 라는 게 의구심이 든다. 또한, 타깃으로 갈 가능성이 있는 input bit flip까지 체크하면서도 깃헙코드가 짧아서, 어떻게 돌아가는지 볼 이유가 있다. 즉 테크니컬한 면이 궁금하다.