차분 테스트

Differential testing

차분 테스트(차동 퍼징이라고도 함)[1]는 일련의 유사한 애플리케이션(또는 동일한 애플리케이션의 다른 구현)에 동일한 입력을 제공하고 실행의 차이를 관찰함으로써 버그를 검출하는 일반적인 소프트웨어 테스트 기술입니다.차분 테스트는 크래시 또는 어설션 실패와 같은 명백한 오류 동작을 나타내지 않는 시멘틱 또는 논리 버그를 발견하는 데 적합하기 때문에 기존의 소프트웨어 테스트를 보완합니다.차분 테스트는 백투백 테스트라고 불리기도 합니다.

차분 테스트는 상호 참조 오라클과 같은 기능의 다른 구현을 사용하여 의미 버그를 찾아내고, 동일한 입력에 대한 출력의 차이를 정확히 파악합니다. 즉, 동일한 입력에 대한 프로그램 동작 간의 불일치는 잠재적인 버그로 표시됩니다.

응용 프로그램 도메인

차분 테스트는 SSL/TLS [2][3][4][5]구현,[6] C 컴파일러,[7] Java 디컴파일러, JVM 구현,[8] 웹 애플리케이션 방화벽,[9] API [10]보안 정책 및 안티바이러스 소프트웨어 [4][11]등 다양한 도메인에서 성공적으로 시멘틱 버그를 찾아내기 위해 사용되어 왔습니다.다른 네트워크 프로토콜 [12]구현에서 자동으로 지문을 생성하기 위해 차등 테스트도 사용되었습니다.

투입생성

안내가 없다

안내되지 않은 차등 테스트 도구는 테스트 프로그램의 과거 입력에 대한 동작을 고려하지 않고 반복에 걸쳐 독립적으로 테스트 입력을 생성합니다.이러한 입력 생성 프로세스는 과거의 입력 정보를 사용하지 않으며, 기본적으로 엄청나게 큰 입력 공간에서 무작위로 새로운 입력을 생성합니다.이렇게 하면 단일 버그를 찾기 위해 대량의 입력을 생성해야 하므로 테스트 프로세스가 매우 비효율적일 수 있습니다.

유도되지 않은 입력 생성을 수행하는 차등 테스트 시스템의 예로는 "프랑켄 인증서"[2]가 있습니다.이 작품은 프랑켄증명서를 실제 증명서의 일부를 무작위로 조합하여 합성한 것입니다.구문적으로 유효한 증명서를 사용하여 여러 구현에 걸친 SSL/TLS 증명서 검증의 의미 위반을 테스트합니다.그러나 Frankencerts의 작성과 선택은 전혀 안내되지 않기 때문에 안내 도구에 비해 매우 비효율적입니다.

안내

유도 입력 생성 프로세스는 과거의 입력에 대한 프로그램 동작 정보를 고려하여 각 버그를 찾는 데 필요한 입력 수를 최소화하는 것을 목적으로 합니다.

도메인 고유의 진화적 가이던스

도메인 고유의 커버리지 가이드 입력 생성을 실행하는 차분 테스트 시스템의 예로는 Mucerts가 [3]있습니다.Mucerts는 X.509 증명서 형식의 부분 문법에 대한 지식에 의존하며 확률적 샘플링 알고리즘을 사용하여 프로그램 범위를 추적하면서 입력 생성을 유도합니다.

또 다른 연구 라인은 기존 입력으로부터 새로운 입력 생성 문제를 확률적 과정으로 모델링할 수 있다는 관찰에 기초한다.이러한 확률적 프로세스 모델링을 입력 생성에 사용하는 미분 테스트 도구의 예는 Chen [8]등의 도구이다.입력 생성을 위해 Markov Chain Monte Carlo(MCMC) 샘플링을 사용하여 Java Virtual Machine(JVM; Java 가상 머신)의 차등 테스트를 수행합니다.Java 클래스 파일 형식에 대한 자세한 지식을 활용하여 사용자 정의 도메인별 돌연변이를 사용합니다.

도메인에 의존하지 않는 진화 지침

NEZHA는[4] 도메인 독립적인 차등 테스트에 적합한 경로 선택 메커니즘을 가진 차등 테스트 도구의 한 예입니다.여러 테스트 애플리케이션의 동작 간에 관찰된 비대칭성을 요약하고 정량화하는 특정 메트릭(델타 다양성 더빙)을 사용합니다.관찰된 프로그램 동작의 상대적 다양성을 촉진하는 이러한 지표는 도메인 독립적이고 블랙박스 방식으로 차등 테스트를 적용하는 데 효과적이라는 것을 보여 줍니다.

자동 학습 기반 안내

유한 스테이트 오토마타(FSA)를 사용해 정확하게 모델화할 수 있는 크로스 사이트 스크립팅(XSS) 필터나 X.509 증명서 호스트명 검증등의 애플리케이션의 경우, 반례에 근거한 FSA 학습 기술을 사용해 [9][5]버그를 검출하기 쉬운 입력을 생성할 수 있습니다.

심볼릭 실행 기반

심볼릭 실행은[13] 프로그램을 상징적으로 실행하고, 다른 경로를 따라 제약을 계산하며, 제약 해결사를 사용하여 각 경로를 따라 수집된 제약을 충족하는 입력을 생성하는 화이트박스 기술입니다.심볼릭 실행을 사용하여 차분 [12][14]테스트를 위한 입력을 생성할 수도 있습니다.

특히 여러 테스트 프로그램이 사용되는 차등 테스트의 맥락에서 심볼릭 실행 지원 테스트 도구의 고유한 한계인 경로 폭발 및 확장성은 더욱 확대됩니다.따라서 여러 대형 프로그램의 차등 테스트를 수행하기 위해 심볼릭 실행 기술을 확장하는 것은 매우 어렵습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ 윌리엄 M. McKeeman, "소프트웨어에 대한 차등 테스트", 디지털 기술 저널, 제10권, 제1호, 페이지 100–107, 1998.
  2. ^ a b C. 브루베이커, S. Jana, B.Ray, S. Kurshid, V.Shmatikov, 2014년 IEEE 보안 및 사생활 심포지엄(S&P) 속 "Frankencerts를 사용하여 SSL/TLS 구현에서의 증명서 검증의 자동 적대적 테스트"IEEE Computer Society, 2014, 페이지 114–129.
  3. ^ a b Y. Chen과 Z.Su, 제10회 소프트웨어 엔지니어링 기초 합동회의(FSE)의 속행에서 "SSL/TLS 실장에서의 증명서 검증의 차분 테스트 가이드"ACM, 2015, 페이지 793–804.
  4. ^ a b c Petsios, T., Tang, A., Stolfo, S., Keromytis, A. D. 및 Jana, S. (2017, 5월)NEZHA: 도메인에 의존하지 않는 효율적인 차분 테스트.제38회 IEEE 보안과 프라이버시에 관한 심포지엄의 속행(새너제이, 캘리포니아).
  5. ^ a b S. Sivakorn, G. Argyros, K.Pei, A. D. Keromytis 및 S. Jana, "HVLearn:SSL/TLS 구현에서의 호스트명 검증의 자동 블랙박스 분석", 2017 IEEE 심포지엄, 보안 및 프라이버시(S&P), 새너제이, CA, USA, 2017, 페이지 521-538.
  6. ^ X. 양, YChen, E. Eide 및 J. Regehr, 제32회 프로그래밍 언어 설계 및 구현에 관한 ACM SIGPLAN 회의(PLDI) 속 "C 컴파일러 버그 검색 및 이해"ACM, 2011, 페이지 283–294.
  7. ^ Harrand, Nicolas; Soto-Valero, César; Monperrus, Martin; Baudry, Benoit (2020). "Java decompiler diversity and its application to meta-decompilation". Journal of Systems and Software. 168: 110645. arXiv:2005.11315. doi:10.1016/j.jss.2020.110645. S2CID 218870447.
  8. ^ a b Y. Chen, T. Su, C. Sun, Z.Su와 J. Zhao는 제37회 ACM SIGPLAN Conference on Programming Language Design and Implementation(PLDI; 프로그래밍 언어 설계 및 구현에 관한 회의)에서 "JVM 구현의 커버리지 지향 차등 테스트"에 대해 설명합니다.ACM, 2016, 85-99페이지.
  9. ^ a b G. Argyros, I. Stais, S. Jana, A. D. Keromytis 및 A.키야스, "SFADiff:자동 회피 공격 및 블랙박스 차등 자동 학습 기능을 이용한 지문 채취"는 '2016 ACM SIGSAC Conference on Computer and Communications Security (CCS) Proceedings'에 수록되어 있습니다.ACM, 2016, 페이지 1690–1701.
  10. ^ V. 스리바스타바, M. D. 본드, K. S. 맥킨리, V.Shmatikov, "보안 정책 오라클:복수의 API 구현을 사용한 보안 취약점 검출" ACM SIGPLAN Notice, vol. 46, no. 6, 페이지 343–354, 2011.
  11. ^ S. Jana와 V.Shmatikov, 2012년 IEEE 보안 및 프라이버시에 관한 심포지엄(S&P)의 속행에서 "재미와 이익을 위해 악성코드 검출기에서의 파일 처리 남용"IEEE Computer Society, 2012, 페이지 80~94.
  12. ^ a b D. 브럼리, J. 카발레로, Z.량, J. 뉴섬, D.송씨는 제16회 USENIX 보안 심포지엄(USENIX Security '07)에서 "오류 검출 및 지문 생성 응용 프로그램을 통한 바이너리 구현에서의 편차 자동 검출을 지향한다"고 밝혔다.USENIX Association, 2007.
  13. ^ J. C. King, "심볼릭 실행 및 프로그램 테스트", ACM의 통신, vol. 19, no. 7, 페이지 385-394, 1976.
  14. ^ D. A. 라모스, D.R. Engler, "실제적이고 노력성이 낮은 실제 코드 동등성 검증", 국제 컴퓨터 지원 검증 회의.Springer, 2011, 669–685페이지.