More Web Proxy on the site http://driver.im/

research-article

Statically-directed dynamic automated test generation

Authors:

Domagoj Babić,

Lorenzo Martignoni,

Stephen McCamant,

Dawn SongAuthors Info & Claims

ISSTA '11: Proceedings of the 2011 International Symposium on Software Testing and Analysis

Pages 12 - 22

https://doi.org/10.1145/2001420.2001423

Published: 17 July 2011 Publication History

Abstract

We present a new technique for exploiting static analysis to guide dynamic automated test generation for binary programs, prioritizing the paths to be explored. Our technique is a three-stage process, which alternates dynamic and static analysis. In the first stage, we run dynamic analysis with a small number of seed tests to resolve indirect jumps in the binary code and build a visibly pushdown automaton (VPA) reflecting the global control-flow of the program. Further, we augment the computed VPA with statically computable jumps not executed by the seed tests. In the second stage, we apply static analysis to the inferred automaton to find potential vulnerabilities, i.e., targets for the dynamic analysis. In the third stage, we use the results of the prior phases to assign weights to VPA edges. Our symbolic-execution based automated test generation tool then uses the weighted shortest-path lengths in the VPA to direct its exploration to the target potential vulnerabilities. Preliminary experiments on a suite of benchmarks extracted from real applications show that static analysis allows exploration to reach vulnerabilities it otherwise would not, and the generated test inputs prove that the static warnings indicate true positives.

References

[1]

R. Alur and P. Madhusudan. Adding nesting structure to words. Journal of the ACM, 56(3), May 2009. Article 16.

Digital Library

[2]

G. Balakrishnan and T. Reps. Analyzing memory accesses in x86 executables. In Proc. of the Int. Conf. on Compiler Construction, LNCS, pages 5--23. Springer, 2004.

[3]

G. Balakrishnan and T. Reps. WYSINWYX:What you see is not what you eXecute. ACM Trans. Program. Lang. Syst., 32(6), August 2010. Article 23.

Digital Library

[4]

G. Balakrishnan and T. W. Reps. Recency-abstraction for heap-allocated storage. In Proc. of the Int. Symp. on Static Analysis, volume 4134 of LNCS, pages 221--239. Springer, 2006.

Digital Library

[5]

T. Ball, R. Majumdar, T. Millstein, and S. K. Rajamani. Automatic predicate abstraction of C programs. In Proc. of the Conf. on Programming Language Design and Implementation, pages 203--213. ACM Press, 2001.

Digital Library

[6]

D. L. Bird and C. U. Munoz. Automatic generation of random self-checking test cases. IBM System Journal, 22:229--245, 1983.

Digital Library

[7]

D. Brumley, C. Hartwig, Z. Liang, J. Newsome, D. Song, and H. Yin. Automatically identifying trigger-based behavior in malware. In Botnet Detection, volume 36 of Advances in Information Security, pages 65--88. Springer, 2008.

[8]

J. Burnim and K. Sen. Heuristics for scalable dynamic test generation. In Proc. of the Int. Conf. on Automated Software Engineering, pages 443--446. IEEE Comp. Soc., 2008.

Digital Library

[9]

C. Cadar, D. Dunbar, and D. Engler. KLEE: unassisted and automatic generation of high-coverage tests for complex systems programs. In Proc. of the Conf. on Operating Systems Design and Implementation, pages 209--224. USENIX Association, 2008.

Digital Library

[10]

C. Cadar, V. Ganesh, P. M. Pawlowski, D. L. Dill, and D. R. Engler. EXE: automatically generating inputs of death. In Proc. of the Conf. on Computer and Communications Security, pages 322--335. ACM, 2006.

Digital Library

[11]

D. R. Chase, M. Wegman, and F. K. Zadeck. Analysis of pointers and structures. In Proc. of the Conf. on Programming Language Design and Implementation, pages 296--310. ACM, 1990.

Digital Library

[12]

E. M. Clarke, O. Grumberg, and D. A. Peled. Model checking. MIT Press, Cambridge, MA, USA, 1999.

Digital Library

[13]

S. A. Cook. The complexity of theorem-proving procedures. In Proc. of the Symp. on Theory of Computing, pages 151--158. ACM Press, 1971.

Digital Library

[14]

P. Cousot and R. Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proc. of the Symp. on Principles of Programming Languages, pages 238--252. ACM, 1977.

Digital Library

[15]

C. Csallner and Y. Smaragdakis. DSD-Crasher: a hybrid analysis tool for bug finding. In Proc. of the Int. Symp. on Software Testing and Analysis, pages 245--254. ACM, 2006.

Digital Library

[16]

L. de Moura and N. Bjørner. Z3: An efficient SMT solver. In Proc. of the Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems, volume 4963 of LNCS, pages 337--340. Springer, 2008.

Digital Library

[17]

E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.

Digital Library

[18]

S. Edelkamp, S. Leue, and A. Lluch-Lafuente. Directed explicit-state model checking in the validation of communication protocols. Int. J. Softw. Tools Technol. Transf., 5(2):247--267, 2004.

Digital Library

[19]

S. Eker. Associative-commutative rewriting on large terms. In Proc. of the Int. Conf. on Rewriting Techniques and Applications, pages 14--29. Springer-Verlag, 2003.

Digital Library

[20]

P. Godefroid and S. Khurshid. Exploring very large state spaces using genetic algorithms. Int. J. Softw. Tools Technol. Transf., 6(2):117--127, 2004.

Digital Library

[21]

P. Godefroid, N. Klarlund, and K. Sen. DART: directed automated random testing. In Proc. of the Conf. on Programming Language Design and Implementation, pages 213--223. ACM, 2005.

Digital Library

[22]

A. Groce and W. Visser. Heuristic model checking for Java programs. In Proc. of the Int. SPIN Workshop on Model Checking of Software, pages 242--245. Springer-Verlag, 2002.

Digital Library

[23]

B. S. Gulavani, T. A. Henzinger, Y. Kannan, A. V. Nori, and S. K. Rajamani. SYNERGY: a new algorithm for property checking. In Proc. of the Int. Symp. on Foundations of Software Engineering, pages 117--127. ACM, 2006.

Digital Library

[24]

Hex-Rays. IDAPro disassembler, 2010.

[25]

G. J. Holzmann. Design and Validation of Computer Protocols. Prentice-Hall, Inc., 1991.

Digital Library

[26]

ISO. ISO C standard 1999. Technical report, ISO, 1999.

[27]

J. Kinder, F. Zuleger, and H. Veith. An interpretation-based framework for control flow reconstruction from binaries. In Proc. of the Int. Conf. on Verification, Model Checking, and Abstract Interpretation, volume 5403 of LNCS, pages 214--228. Springer, 2009.

Digital Library

[28]

J. C. King. Symbolic execution and program testing. Communications of the ACM, 19(7):385--394, 1976.

Digital Library

[29]

A. Lal, J. Lim, M. Polishchuk, and B. Liblit. Path optimization in programs and its application to debugging. In Proc. of the Eur. Symp. on Programming Languages and Systems, pages 246--263. Springer, 2006.

Digital Library

[30]

J. R. Larus and P. N. Hilfinger. Detecting conflicts between structure accesses. In Proc. of the Conf. on Programming Language Design and Implementation, pages 24--31. ACM, 1988.

Digital Library

[31]

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 Proc. of the Conf. on Programming Language Design and Implementation, pages 190--200. ACM, 2005.

Digital Library

[32]

J. P. Marques-Silva and K. A. Sakallah. GRASP: A search algorithm for propositional satisfiability. IEEE Transactions on Computers, 48(5):506--521, 1999.

Digital Library

[33]

M. Müller-Olm and H. Seidl. Analysis of modular arithmetic. ACM Trans. Program. Lang. Syst., 29(5), 2007.

Digital Library

[34]

F. Nielson, H. R. Nielson, and C. Hankin. Principles of Program Analysis. Springer, 2005.

Digital Library

[35]

C. Okasaki. Red-black trees in a functional setting. Journal of Functional Programming, 9(4):471--477, July 1999.

Digital Library

[36]

G. Ramalingam, J. Field, and F. Tip. Aggregate structure identification and its application to program analysis. In Proc. of the Symp. on Principles of Programming Languages, pages 119--132. ACM, 1999.

Digital Library

[37]

T. Reps, G. Balakrishnan, and J. Lim. Intermediate-representation recovery from low-level code. In Proc. of the Symp. on Partial Evaluation and Semantics-based Program Manipulation, pages 100--111. ACM, 2006.

Digital Library

[38]

T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proc. of the Symp. on Principles of Programming Languages, pages 49--61. ACM, 1995.

Digital Library

[39]

T. Reps, S. Schwoon, S. Jha, and D. Melski. Weighted pushdown systems and their application to interprocedural dataflow analysis. Sci. Comput. Program., 58:206--263, 2005.

Digital Library

[40]

A. Rybalchenko and R. Singh. Subsumer-first: Steering symbolic reachability analysis. In Proc. of the Int. SPIN Workshop on Model Checking Software, pages 192--204. Springer-Verlag, 2009.

Digital Library

[41]

P. Saxena, P. Poosankam, S. McCamant, and D. Song. Loop-extended symbolic execution on binary programs. In Proc. of the Int. Symp. on Software Testing and Analysis, pages 225--236. ACM, 2009.

Digital Library

[42]

B. Schwarz, S. Debray, and G. Andrews. Disassembly of executable code revisited. In Proc. of the Working Conference on Reverse Engineering, pages 45--55. IEEE Comp. Soc., 2002.

Digital Library

[43]

M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications, chapter 7, pages 189--234. Prentice-Hall, 1981.

[44]

D. Song, D. Brumley, H. Yin, J. Caballero, I. Jager, M. G. Kang, Z. Liang, J. Newsome, P. Poosankam, and P. Saxena. BitBlaze: A new approach to computer security via binary analysis. In Proc. of the Int. Conf. on Information Systems Security, volume 5352 of LNCS, pages 1--25. Springer, 2008.

Digital Library

[45]

F. Tip. A survey of program slicing techniques. Technical report, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1994.

Digital Library

[46]

H. S. Warren. Hacker's Delight. Addison-Wesley, 2002.

Digital Library

[47]

M. Weiser. Program slicing. In Proc. of the Int. Conf. on Software Engineering, pages 439--449. IEEE Press, 1981.

Digital Library

[48]

C. H. Yang and D. L. Dill. Validation with guided search of the state space. In Proc. of the Annual Design Automation Conference, pages 599--604. ACM, 1998.

Digital Library

[49]

M. Zitser, R. Lippmann, and T. Leek. Testing static analysis tools using exploitable buffer overflows from open source code. In Proc. of the Int. Symp. on Foundations of Software Engineering, pages 97--106. ACM, 2004.

Digital Library

Cited By

Liu SMa WWang JXie XFeng RLiu YShrivastava ASui Y(2024)Enhancing Code Vulnerability Detection via Vulnerability-Preserving Data AugmentationProceedings of the 25th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3652032.3657564(166-177)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652032.3657564
Yongxu HYing ZPengzhi XZhen G(2024)Research on Buffer Overflow Vulnerability Mining Method Based on Deep Learning2024 2nd International Conference on Big Data and Privacy Computing (BDPC)10.1109/BDPC59998.2024.10649293(28-36)Online publication date: 10-Jan-2024
https://doi.org/10.1109/BDPC59998.2024.10649293
Sun HCui LLi LDing ZLi SHao ZZhu H(2024)VDTriplet: Vulnerability Detection with Graph Semantics Using Triplet ModelComputers & Security10.1016/j.cose.2024.103732(103732)Online publication date: Jan-2024
https://doi.org/10.1016/j.cose.2024.103732
Show More Cited By

Index Terms

Statically-directed dynamic automated test generation
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Automated test data generation and stubbing method for C/C++ embedded projects
Abstract
Automated test data generation for unit testing C/C++ functions using concolic testing has been known for improving software quality while reducing human testing effort. However, concolic testing could face challenging problems when tackling ...
Combined Static and Dynamic Analysis

Static analysis is usually faster than dynamic analysis but less precise. Therefore it is often desirable to retain information from static analysis for run-time verification, or to compare the results of both techniques. However, this requires writing ...
Directed test generation for effective fault localization
ISSTA '10: Proceedings of the 19th international symposium on Software testing and analysis

Fault-localization techniques that apply statistical analyses to execution data gathered from multiple tests are quite effective when a large test suite is available. However, if no test suite is available, what is the best approach to generate one? ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA '11: Proceedings of the 2011 International Symposium on Software Testing and Analysis

July 2011

394 pages

ISBN:9781450305624

DOI:10.1145/2001420

General Chair:
Matthew Dwyer
University of Nebraska
,
Program Chair:
Frank Tip
IBM T.J. Watson Research Center

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

In-Cooperation

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ISSTA '11

Sponsor:

SIGSOFT

ISSTA '11: International Symposium on Software Testing and Analysis

July 17 - 21, 2011

Ontario, Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

90
Total Citations
View Citations
673
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)5

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu SMa WWang JXie XFeng RLiu YShrivastava ASui Y(2024)Enhancing Code Vulnerability Detection via Vulnerability-Preserving Data AugmentationProceedings of the 25th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3652032.3657564(166-177)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652032.3657564
Yongxu HYing ZPengzhi XZhen G(2024)Research on Buffer Overflow Vulnerability Mining Method Based on Deep Learning2024 2nd International Conference on Big Data and Privacy Computing (BDPC)10.1109/BDPC59998.2024.10649293(28-36)Online publication date: 10-Jan-2024
https://doi.org/10.1109/BDPC59998.2024.10649293
Sun HCui LLi LDing ZLi SHao ZZhu H(2024)VDTriplet: Vulnerability Detection with Graph Semantics Using Triplet ModelComputers & Security10.1016/j.cose.2024.103732(103732)Online publication date: Jan-2024
https://doi.org/10.1016/j.cose.2024.103732
Wu BLiu SXiao YLi ZSun JLin SChandra SBlincoe KTonella P(2023)Learning Program Semantics for Vulnerability Detection via Vulnerability-Specific Inter-procedural SlicingProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616351(1371-1383)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616351
De Castro Pinto TRollet ASutre GTobor I(2023)Guiding Symbolic Execution with A-StarSoftware Engineering and Formal Methods10.1007/978-3-031-47115-5_4(47-65)Online publication date: 31-Oct-2023
https://doi.org/10.1007/978-3-031-47115-5_4
Busse FGharat PCadar CDonaldson ARyu SSmaragdakis Y(2022)Combining static analysis error traces with dynamic symbolic execution (experience paper)Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3533767.3534384(568-579)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1145/3533767.3534384
Gorjiara HLuo WLee AXu GDemsky BJhala RDillig I(2022)Checking robustness to weak persistency modelsProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523723(490-505)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523723
Groß TSchleier TMüller TSuga YSakurai KDing XSako K(2022)ReFuzz - Structure Aware Fuzzing of the Resilient File System (ReFS)Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security10.1145/3488932.3523260(589-601)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1145/3488932.3523260
Bose PDas DChen YFeng YKruegel CVigna G(2022)SAILFISH: Vetting Smart Contract State-Inconsistency Bugs in Seconds2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833721(161-178)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833721
Yi QYang G(2022)Feedback-Driven Incremental Symbolic Execution2022 IEEE 33rd International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE55969.2022.00055(505-516)Online publication date: Oct-2022
https://doi.org/10.1109/ISSRE55969.2022.00055
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents