Journal of the Korea Society of Computer and Information (한국컴퓨터정보학회논문지)

Korean Society of Computer Information (한국컴퓨터정보학회)
권호 표지
DOI QR코드

DOI QR Code

Constructing Software Structure Graph through Progressive Execution

점진적 실행을 통한 소프트웨어의 구조 그래프 생성

  • 이혜련 (아주대학교 컴퓨터공학과) ;
  • 신승훈 (아주대학교 소프트웨어융합학과) ;
  • 최경희 (아주대학교 컴퓨터공학과) ;
  • 정기현 (아주대학교 전자공학과) ;
  • 박승규 (아주대학교 소프트웨어융합학과)
  • Received : 2013.02.12
  • Accepted : 2013.05.09
  • Published : 2013.07.31
Download PDF
⟨ Previous Next ⟩

Abstract

To verify software vulnerability, the method of conjecturing software structure and then testing the software based on the conjectured structure has been highlighted. To utilize the method, an efficient way to conjecture software structure is required. The popular graph and tree methods such as DFG(Data Flow Graph), CFG(Control Flow Graph) and CFA(Control Flow Automata) have a serious drawback. That is, they cannot express software in a hierarchical fashion. In this paper, we propose a method to overcome the drawback. The proposed method applies various input data to a binary code, generate CFG's based on the code output and construct a HCFG (Hierarchical Control Flow Graph) to express the generated CFG's in a hierarchical structure. The components required for HCFG and progressive algorithm to construct HCFG are also proposed. The proposed method is verified through constructing the software architecture of an open SMTP(Simple Mail Transfer Protocol) server program. The structure generated by the proposed method and the real program structure are compared and analyzed.

소프트웨어의 취약성을 검증하기 위하여 소프트웨어의 구조를 유추하여 유추된 구조를 활용하여 테스트하는 방법이 주목받고 있다. 이와 같은 방법을 사용하기 위해서 효과적인 소프트웨어의 구조 유추 방법이 요구된다. 많이 사용되는 DFG(Data Flow Graph), CFG(Control Flow Graph) 이나 CFA(Control Flow Automata)와 같은 그래프나 트리 방식은 소프트웨어 모델을 구조적으로 표현하지 못하는 단점을 가진다. 본 논문에서는 이러한 단점을 극복할 수 있는 방법을 제시한다. 제시된 방법은 바이너리 코드에 다양한 입력데이터 들을 부여하여 입력데이터별 CFG를 생성하고, 생성된 CFG들이 구조적으로 표현될 수 있도록 계층적 제어 흐름 그래프(Hierarchical Control Flow Graph, HCFG)를 작성한다. 또한 제안하는 HCFG을 생성하는데 요구되는 그래프의 구성요소와 점진적 그래프 생성 알고리듬도 제시한다. 제안한 방법론을 공개된 SMTP(Simple Mail Transfer Protocol) 서버 프로그램에 적용시켜 소프트웨어의 모델을 작성하는 실험을 수행하고, 생성된 모델과 실제 소프트웨어 구조를 비교 분석한다.

Keywords

References

  1. P. Godefroid, M.Y. Levin, and D. Molnar. "Automated Whitebox Fuzz Testing," Technical Report MS-TR-2007-58, Microsoft, May 2007.
  2. Jackson, Daniel, and Martin Rinard, "Software analsis:a roadmap." Processdings of the Conference on the Future of Sftware Engineering, ACM, pp.133-145, May, 2000.
  3. A.Gargantini and C.Heitmeyer, "Using Model Checking to Generate Tests from Requirements Specifications," in Proceedings of the Joint 7th Eur. Software Engineering Conference and 7th ACM SIGSOFT International Symposium on Foundations of Software Engineering. pp.146-162, Sep. 1999.
  4. Jungsup Oh Kyunghee Choi Gihyun Jung, "Automatic Test Case Generation Through 1-to-1 Requirement Modeling," KIPS, D, Vol. 17D, No. 1, pp. 41-52, Oct. 2010. https://doi.org/10.3745/KIPSTD.2010.17D.1.041
  5. Ki-Tae Kim, Je-Min Kim, Weon-Hee Yoo, "Static Control Flow Anlaysis of Binary Codes," The Korea Contents Association, Vol. 10, No. 5, pp,70-79, May. 2010,
  6. Ajitha Rajan, "Automated requirements-based test case generation," Newsletter of ACM SIGSOFT Software Engineering Notes, Vol.31, No. 6, pp.1-2, Nov. 2006.
  7. The MathWorks, http://www.mathworks.com/
  8. Godefroid, Patrice, Michael Y. Levin, and David A. Molnar. "Active property checking." Proceedings of the 8th ACM international conference on Embedded software. ACM, pp.207-216, Oct, 2008.
  9. P. Godefroid, A. Kiezun, M. Y. Levin, "Grammar-based Whitebox Fuzzing," in Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, pp,206-215, Jun. 2008.
  10. P S. Anand, P. Godefroid, and N. Tillmann. "Demand-driven compositional symbolic execution," In Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp 367-381, April. 2008.
  11. Zijiang Yang, "Mixed Symbolic Representations for Model Checking Software Programs," in processdings of the Formal Methods and Models for Co-Design, 2006. MEMOCODE '06. Proceedings. Fourth ACM and IEEE International Conference on, pp17-26, July. 2006.
  12. D. Beyer, T.A. Henzinger, R. Jhala, and R. Majumdar, "The Software Model Checker Blast: Applications to Software Engineering," Int'l J. Software Tools for Technology Transfer, vol. 9, pp. 505-525, Sep. 2007. https://doi.org/10.1007/s10009-007-0044-z
  13. Mark M. Seeger, "Using Control-Flow Techniques in a Security Context A Survey on Common Prototypes and their Common Weakness," in Proceedings of the 2011 International Conference on Network Computing and Information Security, pp.133-137, May. 2011.
  14. IVANCIC, F., YANG, Z., GANAI, M. K., GUPTA, A., AND ASHAR, "Efficient SAT-based bounded model checking for software verification" Theoret. Comput. Sci. 404, 3, pp.256-274. 2008. https://doi.org/10.1016/j.tcs.2008.03.013
  15. Z. Yang, C. Wang und A. Gupta. "Model checking sequential software programs via mixed symbolic analysis," Journal of ACM Transactions on Design Automation of Electronic Systems (TODAES), Vol 14. No. 1, pp.1-26. Jan. 2009.
  16. M. Pezze and M. Young, Software Testing and Analysis: Process, Principles, and Techniques, Draft Version of 31st, Chap. 14.5, Mar. 2000.
  17. Hangbae Chang, Sang-Soo Yeo, Seong-eon Cho, Heau-Jo Kang, "The Study on Improvement of the Program that Traces the Binary Codes in Execution," Journal of Security Engineering, Vol. 5, No 3, pp209-218, Jun. 2008
  18. M. Christodorescu and S. Jha, "Static Analysis of Executables to Detect Malicious Patterns", in Proceedings of the 12th USENIX Security Symposium, vol. 12, pp. 169-186, Aug. 2003.
  19. J Kinder, "Static Analysis of x86 Executables," Fachbereich Informatik Technische Universitat Darmstadt, Chapter5. Sep. 2010
  20. D. G. Fritz and R. G. Sargent, "An overview of Hierarchical Control Flow Graph Models," in Proceedings of the 1995 Winter Simulation Conference, pp. 1347-1355, Dec. 1995.
  21. C. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood, "Pin: building customized program analysis tools with dynamic instrumentation," in Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 190-200, Jun. 2005.
  22. A Dynamic Binary Instrumentation Tool, http://www.pintool.org/
  23. Hye-ryun Lee, Seung-hun Shin, Kyung-hee Choi, Ki-hyun Chung, Seung-kyu Park, Jun-yong Choi, "Detecting the vulnerability of software with cyclic behavior using Sulley," in Proceedings of the Advanced Information Management and Service (ICIPM), 2011 7th International Conference on, pp,83-88, Dec. 2011.
  24. SMTP Server Download, http://www.codeproject.com/Articles/20604/SMTP-Server