🔔 최근 트렌드
mutation based fuzzing은 기존에 program-agonistic fuzzing이었다.
그러나 요즘 program-adaptive fuzzing으로 변화하는 추세이다.
program-agonistic fuzzing
타겟 프로그램과는 상관 없이 fuzzing을 하는 기법이다. ex) AFL
어떤 프로그램이 오더라도, 각 mutation operator들이 선택될 확률은 동일하다.program-adaptive fuzzing
타겟 프로그램을 더 잘 테스팅할 수 있도록 mutation 전략이나 seed selection 전략을 이용하는 기법이다.
MOPT
Program Adaptive Mutation Based Fuzzing 기법이다.
테스트할 프로그램에 따라서, 성능을 올릴 수 있는 변이 operator가 다르다.
-> ❗ havoc stage ❗ 에서 최적의 mutation strategy를 찾는 것이 MOPT의 목표이다.
프로그램 a를 테스팅할 때에는 1bit flip이 가장 좋은 operator라면 distribution에서 1bit flip operator가 더 많이 사용되도록 확률을 조정해줄 수 있다.
프로그램 b를 테스팅할 때에는 2byte flip에서 가장 좋은 mutant들이 만들어졌다면 해당 확률을 높게 조정해준다.
그렇다면, 확률을 어떻게 줄 것인가?!
=> customized particle swarm optimization 알고리즘을 사용한다.
🔔 particle swarm optimization
particle = 한 operator가 선택될 확률
swarm = 여러개의 operator이 선택될 확률적 분배 (particle의 집합)
1) swarm을 k개만큼 초기화한다. ( k= 5)
초기 swarm = 각 operator들이 적용될 확률이 랜덤하지만 uniform하게 한다.
이렇게 5개의 확률 분포가 다른 swarm을 만들어 낸다.2) 해당 swarm으로 mutant를 만든다. 이 mutant를 만들 때 각 operator가 적용될 확률은 각 swarm 내 operator의 확률에 따른다.
3) interesting mutant를 만들 때 operator가 기여한 바를 확인한다.
4) mutant가 여러개 만들어졌는데, interesting한 mutant를 만들 때 어떤 oeprator가 적용되었는지 확인한다. 그리고 해당 operator의 확률을 높이고, 아닌 operator의 확률을 낮춘다.
🌳 Local Efficiency
하나의 swarm 에서의 하나의 particle의 local efficiency를 구한다.
ex) swarm 1에서 1bit flip의 local efficiency
swarm 1에서 10개의 mutant가 만들어 졌고, 그 중 3개의 interesting mutant가 있다. 이 떄 1bit flip이 적용된 횟수를 카운트한다.
전체 5번 적용됐고, 3개의 interesting mutant에서는 2번 적용됐다.
-> 1bit flip의 local efficiency = 2/5가 된다.
이와 같은 방식으로 아래와 같이 각 swarm의 각 particle의 local efficiency를 구할 수 있다.
🌳 global effieciency 구하기
모든 swarm을 기준으로, 각 operator가 얼마나 interesting mutant 만들 때 기여했는지를 확인한다.
5개의 swarm에서 만들어진 mutant가 50개, interesting mutant 20개라고 가정하자.
1bit flip이 전체에서 적용된 횟수 20, interesting mutant 만들 때 적용된 횟수 10이라면 global efficiency = 10/20 = 0.5이다.
이와 같이 각 operator의 local, global efficiency를 구한 후 해당 operator이 sampling될 확률을 높여준다. 이 과정을 반복하게 된다.
👇 효과성
AFL에 비해서 MOPT는 더 많은 Crash를 일으킬 수 있는 입력을 찾아 냈다.
코드 커버리지 관점에서도 더 많은 path를 커버했다.
-> program agonistic에서 program adaptive 방법으로 가는 트랜드 !
